![]() ![]() My hope is that this series has shed some light on what lambda calculus is. And that representation looks no different than any other data you manipulate in your daily programming job. You are now the proud author of an interpreter! Compilers and interpreters usually look like mythical beasts, but they are simply programs that manipulate some representation of a program. Uncaught RangeError: Maximum call stack size exceeded Victory! We can also blow the Node.js interpreter by asking it to evaluate the never-ending term Ω we introduced in part 3. Since we start at top level, evaluation uses an empty context. We define the identity function using our representation, and then ask to evaluate its application to the number 3. Let’s open a Node.js REPL and load our file with the definition of the constructors and the evaluate function. This corresponds to the notion of head normal form, which one usually hears in the context of laziness in Haskell. If your application does not have a function in front, we also stop evaluation. The rest of the cases are left unchanged: if you have a function, we do not look inside the body. As a result, we can use the de Bruijn index in a variable literally as an index for that list! case 'var': By doing so, the list is ordered from innermost to outermost argument. The fact that a has been added at the front of the context is not an arbitrary choice. ![]() For example, the application of the identity function to the number 3 is going to look as follows: The technical name for this is reification: we turn something that only existed implicitly that we couldn’t inspect into something we can manipulate within our language. Instead, we are going to introduce a data structure that explicitly represent our lambda terms. The first step is to stop using JavaScript expressions to represent our lambda terms. So at the end of this post, you’ll have an interpreter for lambda calculus running on top of an interpreter for JavaScript! You know, it’s turtles all the way down. Wait a minute! Weren’t we already representing lambda terms as JavaScript functions? Indeed, that’s what we were doing in the previous parts of the series: use the fact that JavaScript is a superset of lambda calculus to piggyback on an interpreter to execute our lambda terms. In this post, we are going to step back and write our own evaluator for lambda terms. It has been a fun ride, and we have seen how numbers, recursion, data types, everything can be encoded within the three restrictive rules we described in part 1. Welcome to the final installment of our lambda calculus using JavaScript tour. ![]() This article was originally published at on February 10, 2021. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |