[racket-dev] using the Y combinator to...

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 <matthias at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20100804/dc8d24b1/attachment.html>