Writing a compiler. Environment, closures, let-bindings

This is the second video in a series focused on implementing a compiler backend for a small functional language which is a variation of the untyped λ-calculus. In this video we improve the tree-walking interpreter's performance 10x using environments and closures instead of explicit term substitution. Furthermore, we add support for recursive let-bindings which allow direct encoding of recursive functions without the use of the fix-point operator.

00:00 - Intro
01:02 - Recap
01:50 - Problems with function application
03:01 - Environment and closures
05:07 - Evaluation and Values
09:14 - Adding an environment
10:56 - Introducing closures
14:05 - Interpretation of function application
16:56 - Running the new intepreter
18:38 - Adding let-bindings to the language
21:44 - Handling recursive let-bindings
28:43 - Direct-style fibonacci
30:13 - Performance uplift and comparison with other languages
30:46 - Detecting bad recursive bindings
35:15 - How fast it works in other languages
37:52 - Summary and next up

[viniciusgajo]

Nice, thanks for the second video 👏👏👏

[torarinvik]

Excellent stuff. Love this series I learned a lot! Please make more compiler/interpreter stuff if you have the time!!!

[lucasontivero]

Awesome serie!. Memoization would make it really fast-