# [racket] Y combinator

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