Writing a compiler. Term reduction via substitution
This is the first 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 define the language's AST and implement a tree-walking interpreter that does term reduction by substitution. We also explore ways to encode recursion via a fixpoint combinator as well as lazy and eager evaluation strategies.
00:00:00 Intro
00:01:53 High-level compiler structure
00:03:55 Plan
00:05:44 Project setup
00:10:02 Defining AST
00:15:51 Defining example lambda terms by hand
00:19:06 Evaluation by term reduction
00:21:20 Evaluating literals
00:22:47 Evaluating builtins: arithmetic
00:27:24 Evaluating builtins: comparison
00:29:37 Evaluating conditionals
00:30:59 Evaluating abstraction
00:32:31 Evaluating application
00:40:53 Evaluating variables
00:42:25 Debugging eval function
00:44:57 Bug found, continuing with more examples
00:48:27 Fixpoint combinator and recursion
00:56:43 Speed of evaluation
01:00:48 Eager vs lazy evaluation
01:05:55 Next up