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