λ-calculus compiler in F#, part 1: term reduction via substitution
source link: https://www.youtube.com/watch?v=qRHJ4qcFbNE
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
430 subscribers
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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK