[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