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 and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 2 - Page 11 : 35
Programming Paradigms
Recursion and Higher-order Functions
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.

 

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-1.scmWishful thinking - the goal of our work: Generating a recursive factorial function from an almost recursive factorial function.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-2.scmThe starting point - again.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-3.scmAfter simple currying.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-4.scmAbstracting (f f) out of if.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-5.scmAfter a simple renaming of fac to i.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-6.scmIntroducing n as parameter to (lambda (h) ...).


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-7.scmAfter currying.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-8.scmThe lambda expression bound to g has been moved out.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-9.scmEmpty let removed.


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-10.scmIntroduce function for (let ((i ..)) ...).


c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-11.scmA small but irritating detail.

Get 5 out the self application stuff.

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-12.scmFactoring self application stuff out.

Call it Y.

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/y-13.scmThe end result.