Lecture overview -- Keyboard shortcut: 'u'  Previous page: The Challenge -- Keyboard shortcut: 'p'  Next page: Introduction to higher-order functions [Section] -- Keyboard shortcut: 'n'  Lecture notes - all slides together  Annotated slide -- Keyboard shortcut: 't'  Alphabetic index  Help page about these notes  Course home    Recursion and Higher-order Functions - slide 11 : 35

Development of the Y-combinator

We do a step-wise development that leads to the Y-combinator - following the trail devised by Richard Gabriel in The Why of Y.

y-1.scm
Wishful thinking - the goal of our work: Generating a recursive factorial function from an almost recursive factorial function.
y-2.scm
The starting point - again.
y-3.scm
After simple currying.
y-4.scm
Abstracting (f f) out of if.
y-5.scm
After a simple renaming of fac to i.
y-6.scm
Introducing n as parameter to (lambda (h) ...).
y-7.scm
After currying.
y-8.scm
The lambda expression bound to g has been moved out.
y-9.scm
Empty let removed.
y-10.scm
Introduce function for (let ((i ..)) ...).
y-11.scm
A small but irritating detail.
y-12.scm
Factoring self application stuff out.
y-13.scm
The end result.