# [racket] Y combinator

 From: Hendrik Boom (hendrik at topoi.pooq.com) Date: Tue Feb 11 07:54:16 EST 2014 Previous message: [racket] Y combinator Next message: [racket] Multiple ellipses after judgment form premises? Messages sorted by: [date] [thread] [subject] [author]

```On Tue, Feb 11, 2014 at 08:24:46AM +0100, Matthew Johnson wrote:
> Thanks, i think i understand that (lambda (e) (e x)) is a function,
> and that evaluating it produces a new function (the one we use in the
> recursive call - let's call it rf1).
>
> Is your meaning that rf1 protects the self-replicator embedded in the
> 'else' clause from triggering, and so protects us from ongoing
> re-production?

I'm not really clear on the 'else' clause, because I jumped into this
discussion midway, but I presume what you mean is that in the actual
function passed in as 'e', the places where recursion would
occur are guarded by some kind of condition.

In any recursive
situation, such conditions are needed to stop infinite
recursion.

> When we get to it, a fresh call to (lambda (e) (e x))
> --> rf2, which again protects the replicator (the mental image i have
> is of a popcorn kernel awaiting the heat).

Yes.

This mechanism of passing a functino to itself is actually useful
sometimes, not just theoretically.

Years ago I had to write a function that printed a recursive tree
structure.

It looked like

(define f (lambda (thing)
(cond
( (one kind of thing)
(print that one kind of thing, calling f recurively for
subthings) )
( (next kind of thing)
(print that next kind of thing, calling f recurively for
subthings) )
(else (print message about invalid thing))
))

Later I wanted to call this function where there was some kind of
exceptional thing.  Now the obvious method wouold be to add another
case to the cond clause.

But if f were to get itself passed in there was another technique.

(define f (lambda (fp thing)
(cond
( (one kind of thing)
(print that one kind of thing, calling fp recurively for
subthings) )
( (next kind of thing)
(print that next kind of thing, calling fp recurively for
subthings) )
(else (print message about invalid thing))
))

and then normally print things by calling (f f thing)

Now define a special-f

(define special-f (lambda (sfp thing)
(if (thing is special)
(print thing specially, calling sfp for recursion)
(f special-f thing)
))

This is somewhat convoluted, but I've found it useful in situations
where I need several slightly different print mechanisms.

When you figure all this out, you might want to try a more difficult
exercise:

Make a special-f that takes an extra integer parameter and stops
recursion after that many levels of nesting.

Hint: where special-f calls f, you're not
going to be able to merely pass special-f in as the argument for
f, because f would pass it the wrong number of arguments when
clling it back.  Instead, you'll have to pass in a lambda expression
that takes the right number of arguments and does something with the
counter internally.

>
> Thanks for your patience & sorry if i am being a little dense - this
> is all very new to me.

That's what we're here for!

-- hendrik
```

 Posted on the users mailing list. Previous message: [racket] Y combinator Next message: [racket] Multiple ellipses after judgment form premises? Messages sorted by: [date] [thread] [subject] [author]