September 22, 1999 | Perl and the Lambda Calculus | Slide #31 |

Y =f.(x.(f(xx))x.(f(xx)))

Actually many others are possible, but this is the simplest

Claim: (

`Y`*f*) = (*f*(`Y`*f*))Let's see:

(Yf)

(f.(x.(f(xx))x.(f(xx)))f)

(x.(f(xx))x.(f(xx)))

(f(x.(f(xx))x.(f(xx))))

Why look, that's exactly (

*f*(`Y`*f*)).This is

*f*making a recursive callIf another recursive call is needed the new (

`Y`*f*) will generate oneEtc.

Next | Copyright © 1999 M-J. Dominus |