--- Kevin Toppenberg <[EMAIL PROTECTED]> wrote:
Continuing...
>
> To say that we want functions to treated as values seems a different
> point than saying that to accomplish this would require the converse
> situation of values being treated the same as functions (i.e.
> requiring an entry in the symbol table.
This is where the recursive aspect of computability theory enters the
picture. In any programming language, you will express a functions in
some way, so that you have a template for carrying it out. That doesn't
make much sense does it? We can return to this point if you like, but
the essential point is that you need language allowing you to talk
about what you're doing without having to explicitly enumerate the
things you might do (give them names). It isn't an essential point just
now.
>
> > We need a
> > way to create *anonymous* functions. If we introduce LAMBDA as a
> kind
> > of place holder, a keyword standing place of the function name,
>
> Again I am lost. Isn't the name of the function already a
> placeholder
> for it's entry point?
No, it's not a placeholder, it's a name for a function. Going back to
the example of ordinary integers, 2 is not a placeholder for a number,
it is a name we assign to a specific number. In
SUCC(N) ;
Q N+1
the N "acts like" a placeholder for an arbitrary integer, but in
reality it consumes a slot in your symbol table, and if you don't later
NEW it, you'll run into trouble with
SUCC2(N) ;
D
.;bunch of stuff
.;including
.;S N=3
Q N+1
then you'll run into trouble. That probably seems rather trivial, but
it does illustrate a mechanism through which unwanted coupling between
your code and the environment in which it runs can arise.
> It sounds like you are talking to a feature
> such as "function pointers" that exist in pascal (and c++ I think),
Not in standard Pascal, anyway, but function pointers are part of C
(and, of course, C++).
> whereby a variable can hold a reference to (or more exactly the
> address of) a function. And the language ensures proper placement of
> the parameters on the stack etc during call.
But no, I'm not talking about function pointers here. Function pointers
*do* allow you to do many things like express functions acting on other
functions (in a limited way), but functions are never first class
values. What function pointers really do is gived you a way of
indirectly invoking code that is statically defined elsewhere.
Maybe this is an overly esoteric example (in reality, it is very
fundamental), but suppose we were able to define a function Y (called
the fixed point combinator, or sometimes the "paradoxical operator")
that when applied to a function f returns (if it returns at all) a new
function Y f that *fixes* f. There are many ways to do this, but the
most famous is
> (define Y
(lambda (z)
((lambda (f) (f f))
(lambda (f)
(z (lambda (x) ((f f) x)))))))
(Does your head hurt? That definition certainly makes my head hurt!)
Okay, we've defined Y. What's it good for? Remember that the factorial
function (n! = 1 * 2 * ... * n) satisfies
fact(n) = n * fact (n - 1), if n > 0
But, more to the point, this is a way of *transforming* a function
according to a definite rule and getting the same function back. Supose
that all we know about the factorial is that it satisfies this rule,
and we're not smart enough to figure out that multiplying the integers
from 1 to n will work. What can we do? Well, let's express our
transformation rule in Scheme
> (define f
(lambda (g)
(lambda (n)
(cond
((= n 0) 1)
(else
(* n (g (- n 1))))))))
>
Now, let's apply Y to f and call the result fact
> (define fact (Y f))
>
What can we do with fact?
> (fact 0)
1
> (fact 1)
1
> (fact 2)
2
> (fact 3)
6
> (fact 4)
24
>
(If you find the definition of Y overly obscure, don't worry. You don't
really need it to follow the example. The only thing that matters is
that if finds a fixed point of f, i.e.f (Y f)) = f .)
Now, if you can find a way to do that with function pointers, I'll be
impressed!
>
> But M, with indirection, this can also be done.
>
> EXEC(FN,X)
> new Y
> xecute "set Y=$$"_FN_"("_X_")"
> quit Y
>
But the problem is the same. Your code still relies on the bindings in
effet at the time of its use. You can't disentangle it from the larger
program.
> ...
> > LAMBDA(X) {$S(+X=0:(X+1),1:BOTTOM) }
> >
>
> It seems to me that you are introducing unnecessary complexity.
> You
> are introducing a new syntax to do something that M syntax already
> provides:
>
> LAMBDA(X)
> quit $S(+X=0:(X+1),1:BOTTOM)
No, because LAMBDA isn't a name. You're thinking about it as if it were
a function itself. Perhaps a rough analogy with OOP would be the
difference between a factory method and the objects you create using
it.
>
> Note: I'm not sure what you are doing with this function.
> Input Values ---> Output Values
> ---------------- -------------------
> 0 1
> (all other values) <BOTTOM>
Perhaps it's bst to temporarily ignore this example. What I was
attempting to do is illustrate how Y works. Basically, if you start
"unwinding" the deginition of Y, you'll see that it takes it generates
a series of approximations to the function that converges for any given
argument. For example the approximations to fact, mighe be something
like
1 stuff
1*2 new stuff
1*2*3 still newer stuff
1*2*3*4 okay, you're done now
>
> Also, is LAMBA a new syntax you are proposing, or is the name of a
> sample function you are demonstrating?
Yes, it's a new syntax.
>
> > where BOTTOM is a magic value represnting a non-terminating
> program.
>
> So I would think of BOTTOM as a function pointer, meaning that when
> the function returns the value of <BOTTOM>, it in fact calls some
> function? Perhaps I am still thinking iteratively instead of the
> functional relationships you are trying to help us/me understand?
BOTTOM is more of a theoretical construct, not something you see in
real programs.
>
> In
> > functional style it might be defined like this
> >
> > S BOTTOM = LAMBDA() { BOTTOM() }
> >
>
> I guess we are putting the practical side of this out of mind,
> because
> I don't understand how this concept would have an application.
Right. What we're discussing here is theory of computation, and not
paractical programming. To illustrate the difference, if you were going
to define a factorial program in a real program, you'd "cheat" and
allow the definition to refer to itself, like this
> (define factorial
(lambda (n)
(cond
((= n 0) 1)
(else
(* n (factorial (- n 1)))))))
or, in MUMPS
FACT(N) ;
Q $S(N=0:1,1:N*$$FACT(N-1))
I didn't mean to giver the impression that functions could not be
written in recursive style in Lisp/Scheme in the way that you can in
MUMPS.
> Even
> if we are dealing with a language that has true function pointers,
> why
> would one have a function that is defined to iteratively return
> itself
> in an endless loop, like:
> FNP
> quit $$FNP
>
The reason it is theoretically interesting is that you can obtain all
computable functions by starting with BOTTOM and then following certain
combination rules. It's much like the Peano axioms in arithmetic where
you don't just assume all the natural numbers exist. You just start
with 0 (or even the empty set, if we're talking about models) and a
successor function. In both cases, the goal is the same: to develop a
logically consistent theory.
===
Gregory Woodhouse <[EMAIL PROTECTED]>
"Interaction is the mind-body problem of computing."
--Philip L. Wadler
-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems? Stop! Download the new AJAX search engine that makes
searching your log files as easy as surfing the web. DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
Hardhats-members mailing list
Hardhats-members@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/hardhats-members
