Re: A numerical methods viewpoint on OO/FP/Relational

Richard MacDonald wrote

>"peter_douglass" <baisly_at_gis.net> wrote in message
>news:3b44a4a2$1_at_tobjects.newsource.com...

>> > The punchline:
>> > The relational world and the OO world
>> > correspond to the Z | H(Z)=0 form
>> > The functional world corresponds to the Y=F(X) form.
 

>> Another way to look at functional programming is this. When you apply a
>> function to a value, you get the Y = F(X) form, but when you _define_ a
>> function, you use something similar to Z | H(Z)=0 form, i.e. least fixed
>> points. The form of a least fixed point would be something like:
 

>> minimum { Z | H(Z) = Z }
>> for some definition of minimum.

>So the *definition* of a function is to "create" a variable that "is" this
>function? Pardon the quotes and/or clarify them.

A function definition is an equation or system of equations where the value we solve for is the function. When we write

x = 4 + 7

we are defining x to be the value that is found by solving that equation.

In functional languages we could write

f = \ x -> (x * x)

which would define f to the value which happens to be a function ( read "\" as "lambda" ) which takes some argument and returns the square of that argument. A function is a value just like any other value, it just has the added property that you can apply a function to an argument to get a new value.

>> If squares and rectangles are ubiquitous in OO
>> examples, the lowly factorial
>> is ubiquitous as a functional programming example.
 

>> fact 0 = 0
>> fact n = n * (fact (n-1))

>> In this definition, it is fact that plays the role of
>> Z in your form above.
 

>I'm interested, but how can Z have an argument n?

Z in this case is a function, and functions take arguments. If it bothers you that 0 and n appear on the left hand side of the equations, consider a system of equations

AX = B where A is a known matrix, B a vector, and X is the vector we are looking for. If I wanted to, I could have re-written fact as a single equation with only fact on the left hand side, but it would not be as clear a definition.

>> Now the factorial function is a fixed point of these equations, but so is
>> the function that always returns an error. If functions are ordered by
>> their information content, and an error is treated as "so much
 information
>> that it is inconsistant", i.e. the top of the hierarchy, then the
 factorial
>> function is the least fixed point, as well as _a_ fixed point.
 

>Sigh. I'm completely overwhelmed by that paragraph. Do I need
>an "FP for dummies" or "FP in 15 days" book :-?

Sorry. Let me try to explain. Y | F(Y) = 0, should more properly be written { Y | F(Y) = 0 }. That is the solution is a set of values. Sometimes this set is empty. Sometimes it has a singleton member, sometimes it has many members. Consider the exquation

x = x. It has a an unlimited number of solutions. Do we say that it defines x to be the value 7? The value 7 certainly satisfies the equation. No, we say that it "defines" x to be "undefined". In FP lingo, we would say that it defines x to be "bottom" (written "_|_". Undefined or bottom is a legal "value" in the FP world, and is the value of any expression for which the evaluation process doesn't terminate. Bottom has the least amount of information in it, of all values. So bottom is the "least fixed point" of the equation x=x. That is how we avoid having the declaration x=x assign a value of 7 to x. Probably clear as mud right?

>> > Relational model:
 

>> > The relational model is declarative. It defines the variables
>> > and defines the constraints that the variables must satisfy.
>> > It doesn't say how these constraints must be satisfied.
>> > It simply accepts or rejects values for the variables depending
>> > on whether these values satisfy the constraints or not.
 

>> > Note, however, that the relational model also has a
>> > provision for explicitly defining dependent variables as
>> > functions of other variables.
 

>> > Functional model:
 

>> > The functional model says that the function is fundamental.
>> > This is F. The function accepts input X and produces output
>> > Y. The functional model "subsumes" variables by making them
>> > the identity function, i.e., X=F(X). So everything can be
>> > thought of as functions.
 

>> I'm not sure where the idea that in the functional paradigm, everything
 can
>> be thought of as functions, comes from. I've seen that idea expressed a
>> number of times, but it goes against my view of FP. Of course it is
>> trivially true. For every value, there is a constant function that
 returns
>> that value. But I don't see what this has to do with FP. A more
 important
>> relationship between functions and values is that in FP, functions are
 first
>> class values.
 

>By "first class values", do you mean that functions *are* values?

I mean more than "functions are values". I mean that functions are given the same status in the language as other values. You can assign them to variables. You can pass them as arguments to functions. You can return them as the results of functions. And so on.

>Can you say (should you say / is it useful to say) that in FP everything
>can be thought of as values of which functions are one kind.
>(Just fishing here.)

Yes.

[snip]

>> I'm not sure where to go with this, but one
>> though occurs to me. Input into
>> a system with constraints is quite different
>> from finding a value satisfying constraints.
>> IOW, it is easier to check that H(Z)=0 for a
>> given Z, then it is to find such a Z.
 

>In your last sentence, the first aspect is a query
> and the second aspect is an action. That doesn't
> jive with the previous sentence "input into a system
>with constraints". I agree with your last sentence, of
> course, but I took your previous sentence to mean
> "altering the system of constraints is different
>from finding the solution that satisfies them". At some
> high level, its useful to think of these as *not* different,
> but any practical implementation needs to separate
> them, at the very least to deal with transactions.

The difference that I was trying to illustrate is the difference between, say a logic program and a relational database. In the logic program, we take all the constraints and search for all solutions to those constraints. In a relational database, the user "enters" a solution, and the database only verifies that the data entered is in fact a solution to the constraints.

>> With every language, the programmer has some intuitive
>> model for how her program will be evaluated. We might consider
>> declarative and procedural to be opposite poles, but no program
>> is entirely one or the other. The trade-off of going too far in the
>> declarative direction is that we don't capture important information
>> that might greatly reduce the effort
>> needed for evaluation. Going too far in the
>> procedural direction and we lose sight of what
>> we _want_ to accomplish in the mountain of
>> details of _how_ it will be done. Thus, I wouldn't
>> argue that either one of Y=F(X)
>> or Z | H(Z) = 0 is necessarily better. Often the
>> specifications of problems are in the form
>> Z | H(Z) = 0, but to get an efficient solution we
>> transform them into Y = F(X).
 

>Very nicely put. The difference between mathematicians (I'm done if I show
>it could be solved :-) and engineers (who have to solve it in this
>lifetime).
 

>OTOH, I believe we'll steadily march in the direction of declarative,
>because that's less work for us programmers -- the final bottleneck.

Yup. Progress lies expanding our ability to automate the translation of declarative statements into efficient code. :-)

--PeterD Received on Sat Jul 07 2001 - 19:31:17 CEST