I'll hijack the thread since I've been meaning to ask about the Y combinator. >From SICP I've seen that the Y combinator is the function (define (y f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
This makes mathematical sense, since (y f) = ((lambda (x) (f (x x))) (lambda (x) (f (x x)))) = (f ((lambda (x) (f (x x))) (lambda (x) (f (x x))))) = (f (y f)) But when actually applying it: // g improves a function to get a ceiling function. The fixed point would be similar to (lambda (x) (inexact->exact (ceiling x))) (define (g f) (lambda (x) (if (<= x 0) 0 (+ 1 (f (- x 1)))))) > ((g (g (g (g (g #f))))) 3.3) 4 Now let's step through ((y g) 3.3) = (((lambda (x) (g (x x))) (lambda (x) (g (x x)))) 3.3) = ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))) 3.3) now, to get the (g ...) result we need to apply g to it's operand. For that, we need to evaluate it: = ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))) 3.3) = ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))))) 3.3) = ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))))))) 3.3) And I just ran out of memory. What am I missing here? It seems obvious to me that if we add a delay/force or somesuch thing it solves the problem. But that's not the y-combinator I was shown.
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev