[plt-scheme] a few questions (was: Scheme questions?)

On Dec 4, 2005, at 5:08 PM, Matthias Felleisen wrote:

>
>> I don't know if the Y combinator had been devised when McCarthy was
>> trying to computerize recursion theory,
>
> 1930s.

Are you sure? I know lambda calculus was developed in the 1930's, but  
didn't Dana Scott develop domain theory (where you get fixed points  
for continuous functions) in the 1970's.

Incidentally, here's something I wrote for another list after seeing  
the fix point operator in Haskell. I still have a hard time believing  
it actually worked (and yes, I know, it's an explicit definition, no  
Scott topology or continuous functions):



Maybe this is an overly esoteric example (in reality, it is very
fundamental), but suppose we were able to define a function Y (called
the fixed point combinator, or sometimes the "paradoxical operator")
that when applied to a function f returns (if it returns at all) a new
function Y f that *fixes* f. There are many ways to do this, but the
most famous is


> (define Y
>
     (lambda (z)
       ((lambda (f) (f f))
        (lambda (f)
          (z (lambda (x) ((f f) x)))))))

(Does your head hurt? That definition certainly makes my head hurt!)

Okay, we've defined Y. What's it good for? Remember that the factorial
function (n! = 1 * 2 * ... * n) satisfies

fact(n) = n * fact (n - 1), if n > 0

But, more to the point, this is a way of *transforming* a function
according to a definite rule and getting the same function back. Supose
that all we know about the factorial is that it satisfies this rule,
and we're not smart enough to figure out that multiplying the integers
from 1 to n will work. What can we do? Well, let's express our
transformation rule in Scheme


> (define f
>
     (lambda (g)
       (lambda (n)
         (cond
           ((= n 0) 1)
           (else
            (* n (g (- n 1))))))))

>
>

Now, let's apply Y to f and call the result fact


> (define fact (Y f))
>
>

What can we do with fact?


> (fact 0)
>
1

> (fact 1)
>
1

> (fact 2)
>
2

> (fact 3)
>
6

> (fact 4)
>
24

>
>



===
Gregory Woodhouse
gregory.woodhouse at sbcglobal.net

"Without the requirement of mathematical aesthetics a great many  
discoveries would not have been made."
-- Albert Einstein