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

(1:59)`letrec`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.