| Playlist | schedule page slides as PDF |
Y 1 — introduction (3:21)
Plait includes a letrec form that supports local recursive functions. The let form doesn’t directly support recursive functions, but we will be able to encode letrec using lambda.
Y 2 — self-application (2:10)
Our first step in understaning the letrec encoding is to implement the factorial function in Plait without letrec.
Y 3 — isolate function body (5:39)
Our second step in understaning the letrec encoding is to separate the part of the factorial function’s implementation that is not specific to the factorial function.
Y 4 — parsing letrec
(1:59)
Our third and final step in understaning the letrec encoding is to convert the pieces into Curly notation and identify the equivalent expression that parse can produce for an input letrec form.
Y 5 — Y combinator (1:24)
The key part of our encoding, mk-rec is more commonly called the Y combinator. You may also see it described as a fixpoint operator. For other presentations of the derivation, search the web for “the why of Y.”
Y 6 — Y combinator (2:02)
A hint on implementing parse for letrec using quasiquote escapes.