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

 From: Gregory Woodhouse (gregory.woodhouse at sbcglobal.net) Date: Sun Dec 4 20:19:30 EST 2005 Previous message: [plt-scheme] a few questions (was: Scheme questions?) Next message: [plt-scheme] a few questions (was: Scheme questions?) Messages sorted by: [date] [thread] [subject] [author]

```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)))))))

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

```

 Posted on the users mailing list. Previous message: [plt-scheme] a few questions (was: Scheme questions?) Next message: [plt-scheme] a few questions (was: Scheme questions?) Messages sorted by: [date] [thread] [subject] [author]