[racket] Y combinator

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