Letrec 0 — encoding redux (0:59)
Our encoding of letrec works for functions, but it’s not as general as letrec in plai-typed.
Letrec 1 — letrec (6:37)
A closer look at letrec and how it might be implemented in terms of plai-typed’s letrec.
This video is a little out of date, because the (define x x)
and (define x (list x))
examples now raise an exception (which is a better “
escape hatch”
) instead of producing an #<undefined>
result. That difference carries through, but the overall point holds that it doesn't work to use letrec
directly to implement letrec
, and using a lambda
to delay does work.
Letrec 2 — metacircular interp (2:54)
Filling in interp and trying it out. See letrec-mc.rkt. The term metacircular refers to the idea of implementing a feature using the same feature in the implementation language—as we have done before, and in this case, implementing letrec using letrec. (Again, the example now raises an exception, instead of producing <undefined>.) A metacircular implementation can tell us some things, but in this case, we usually want to move on...
Letrec 3 — assignment-based encoding (3:05)
Another way to implement letrec in terms of let is to use set!. We can use that idea even if we don’t provide set! in our language. See letrec.rkt.
Letrec 4 — cyclic data (6:25)
Beyond letrec: cyclic data other than functions. The demonstration shows shared in the racket language, but shared is also available in plai-typed.