[racket] Y combinator

From: Matthew Johnson (mcooganj at gmail.com)
Date: Tue Feb 11 02:24:46 EST 2014

Thanks, i think i understand that (lambda (e) (e x)) is a function,
and that evaluating it produces a new function (the one we use in the
recursive call - let's call it rf1).

Is your meaning that rf1 protects the self-replicator embedded in the
'else' clause from triggering, and so protects us from ongoing
re-production? When we get to it, a fresh call to (lambda (e) (e x))
--> rf2, which again protects the replicator (the mental image i have
is of a popcorn kernel awaiting the heat).

Thanks for your patience & sorry if i am being a little dense - this
is all very new to me.

best regards


On 11/02/2014, at 3:23 AM, Hendrik Boom <hendrik at topoi.pooq.com> wrote:

> On Mon, Feb 10, 2014 at 09:52:18PM +0000, Matthew Johnson wrote:
>> Thank-you all for your help with my Y-combinator question.
>> I've now got myself a copy of *The Little Schemer*, and think that i'm
>> getting there.
>> Some googling on the lambda calculus and fixed point combinators introduced
>> me the formalism:
>> ((lambda (x) (x x)) (lambda (x) (x x)))
>> The general setting helped me see what was going on with (make-list
>> make-list) etc ... in an abstract sense (i've never studied CS) however i
>> do remain a little puzzled by Matthias' second hint:
>> "when you have an expression e and you know it will evaluate to a function
>> if the evaluation terminates but it may not terminate, you can write
>> (lambda (x) (e x)) to make sure that it is a function NOW. That way you can
>> pass this quasi-e to another function and it can make the decision to
>> evaluate it or not.  If you had written the derivation in #lang lazy as
>> opposed to #lang racket, you would not need this trick. In a lazy language
>> e is passed as an argument without being evaluated to start with."
>> Why does (lambda (x) (e x)) make it evaluate once and stop? I mean how come
>> when the evaluator gets to the call it doesn't get stuck in a loop?
> Because when you evaluate (lambda (x) (e x)) you get a function.  If
> that function is ever called, it will take an argument x, evaluate the
> expression e, and then call the value of e passing it x as argument.
> If evaluating e never terminates, that isn't relevant until you
> actually evaluate e, which doesn't happen until you *call* (lambda (x)
> (e x)).
> -- hendrik

Posted on the users mailing list.