On Nov 22, 2005, at 8:28 PM, Gregory Woodhouse wrote:
Yes, but this is imperative code. In functional languages, you
don't "do" things, you describe them. A line of a program is not a
command that "does" something, it's a definition of a relationship
of some sort. In the spreadsheet example, when you say that a cell
should contain the sum of the contents of the cells above it, you
aren't actually adding anything, you're declaring a relationship
that must hold between the cells in your spreadsheet.
I guess it's a little uncool of me to leave you hanging like this. If
functional programs don't "compute" but instead "describe", then how
does anything ever get done? Well, that's a really good question, and
it turns out that the mathematical foundation of functional
programming is something known as lambda calculus (invented by Alonzo
Church). The syntax of lambda calculus is almost trivial. There are
only three things: variables, applications and lambda abstractions.
If you will allow me to use the backslash (\) in place of the lower
case Greek letter lambda, then a function (f) of one variable (x) is
written like this
\x . f
That's not very interesting unless you know something about f. But
there is something you can do with lambda expressions, you can
"reduce" them. For example \x . x represents the identity function
(in conventional notation, f(x) = x), because if you "apply" it to y,
you get the "reduction"
(\x . x) y ==> y
The way you apply the abstraction \x . x to y is to replace the x
bound by \x by y, thus obtaining y. This example isn't terribly
interesting, but consider the reduction
\x . (\y . plus 1) 2 ==> \x . add-1 2 ==> 1 + 2 = 3
where I've introduced the symbol
add-1 = \x . x + 1
for the function that adds 1 to its argument.
There is no guarantee that the process of reducing an expression will
ever stop (programs can go into infinite loops), but if it *does*
stop, a result known as the Church-Rosser theorem (technically, the
first Church-Rosser theorem) says the result is unique up to renaming
of bound variables (think formal parameters). An expression that
cannot be reduced further is called a normal form, and functional
programs compute by reducing expressions to normal form. It turns out
that the lambda calculus is exactly as expressive as Turing machines,
or partial recursive functions, or any of other various equivalent
formulations of computability.
===
Gregory Woodhouse
[EMAIL PROTECTED]
"It is foolish to answer a question that
you do not understand."
--G. Polya ("How to Solve It")
-------------------------------------------------------
This SF.Net email is sponsored by the JBoss Inc. Get Certified Today
Register for a JBoss Training Course. Free Certification Exam
for All Training Attendees Through End of 2005. For more info visit:
http://ads.osdn.com/?ad_id=7628&alloc_id=16845&op=click
_______________________________________________
Hardhats-members mailing list
Hardhats-members@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/hardhats-members
