So it seems I understood it correctly. My implementation of a Y-like combinator, (define (y f) ((lambda (x) (f (delay (x x)))) (lambda (x) (f (delay (x x)))))) works well - except that the combinated function needs to call ((force f) ...) instead of (f ...)
Guess I just missed the part where Hal mentioned that their y-combinator only works in "normal-order" and not "applicative-order" evaluation. (This is from the video lectures, by the way - not the book) On Wed, Aug 4, 2010 at 17:25, Matthias Felleisen <matth...@ccs.neu.edu>wrote: > > SICP's treatment of the Y combinator is uninformed by existing programming > language theory (1960s and 70s stuff) and is therefore wrong. To their > credit, they allude to the problem with words such as normal-forms, > reduction, and applicative etc. That's wrong too but at least it warns > readers of potential problems. > > You have discovered one of the essential problems. > > For a thorough discussion, though in an unusual style see the discussion > The Little Schemer, nee The Little LISPer (also MIT Press). For a very old > draft of this material, visit > > http://www.ccs.neu.edu/home/matthias/misc.html > > and look into Why of Y. > > hth -- Matthias > > > > > On Aug 4, 2010, at 12:20 PM, The Configurator wrote: > > > 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 > >
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
