[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