Y combinator
Thant Tessman
Over the last couple of years I've spent the occasional spare moment
implementing an interpreter for a programming language casually inspired
by (but not at all faithful to) Scheme, SML, and Dylan. The only thing
noteworthy about this effort (i.e. impressive or tragic depending on
your point of view) is that it's implemented in C++. (The intention is
that it's an interpreted extension language to C++.)
Anyway, in trying to get recursive functions working, I *think* I've
re-invented the Y combinator (which, assuming I have reinvented it, I
never really understood before now).
I have a question: At least in my implementation, the base function is
transformed to take an extra argument which of course will be the
function itself. This is fine for when the function is appiled solely
within the body of the function itself because I'll transform every use
of the function to pass in the extra argument. The problem is this: What
should happen if the function is passed to some other function not
expecting the extra argument? What if the recursive function returns
itself?
What do implementations typically do to handle this? (Or do I not really
understand the solution to the problem of recursive functions?)
-thant
Doug Ransom
http://www.codepedia.com/1/thunks
Doug Ransom
to mail me, open this hyperlink: http://tinyurl.com/2rdm
--
Thant Tessman
> I don't know what the Y combinator is [...]
A recursive function is of course a function that calls itself. (The
factorial function is the typical pedagogical example of a recursive
function.) The problem is that in a pure functional programming
language, you can't refer to a function until after it's been defined.
But if the function hasn't been defined yet, how can it refer to itself?
The Y combinator is a trick for tranforming a function so it can call
itself. With the kind help of Ralph Becket, I now understand that I had
reproduced the effect of the Y combinator, but that I was confused about
how it is supposed to be used in certain situations. (To be truthful,
out of impatience I wound up solving my problem with an 'impure'
solution, but at least now I have this nice shiny Y combinator in my
toolbox for next time.)
-thant
Tim Sweeney
> transformed to take an extra argument which of course will be the
> function itself. This is fine for when the function is appiled solely
> within the body of the function itself because I'll transform every use
> of the function to pass in the extra argument. The problem is this: What
> should happen if the function is passed to some other function not
> expecting the extra argument? What if the recursive function returns
> itself?
This should all work automatically if you're managing your
environments/closures properly.
If you are looking into a purely runtime solution, look for
information on closures (a combination of a function, and an "outer
environment" - a binding of values to all of the variables in outer
function contexts). In an ordinary language, at runtime, all
variables in lambdas "outside" the current lambda are guaranteed to
have well-defined values when it comes time to apply the current
lambda.
If you're looking for a compile-time solution, check out Luca
Cardelli's paper on "Explicit Substitutions". This is a compile-time
mechanism for keeping track of bindings, and scales well to complex
situations of functions calling functions recursively with functions
as parameters. See http://www.pps.jussieu.fr/~curien/ExplicitSub.pdf.
If this is too big a leap (the presentation is very technical) do a
Google search for "de Bruijn indices" for background.
Personally, I find it easiest to represent recursive functions without
the Y combinator approach (i.e. without passing a function "to
itself"). Instead, I use to distinct sets of de Bruijn indices:
"parameter indices" referring to the parameter passed to the function,
and "self indices" referring to the function itself. This approach is
a bit more compact, but more importantly, there tend to be different
compile-time evaluation semantics associated with self indices and
with parameter indices: you can't try to eagerly resolve self indices
or else you run into infinite loops. With the Y-combinator approach
it's not obvious whether a given parameter may be so recursive. This
probably doesn't matter in simple evaluations situations, but becomes
important in recursive dependent type systems.
-Tim