/Я language (β)/Tutorials/Lambda calculus interpreter 1/

Full source code ⋅ Twitter discussion ⋅ Next chapter

We start with the most classic way to define AST and then gradually move to more sophistacated ones.

For the sake of simplicity, let identifiers be a single latin character (so only 26 unique variables are available).

So a regular term is either an abstraction, an application or a variable:

Since we never define our own datatypes here but rather construct from basic ones - patterns serve a role of constructors:

We declare all three options as a covariant functor, therefore their Sum composition is also a covariant functor - we can use its parameter as an embedding if we apply it to a fixpoint combinator:

Using this version of AST we can declare (abstraction) identity function this way:

And this is how we can provide an argument (application) to identity function:

These chunks of code look a bit too verbose, we can come up with more specialised patterns:

Now both abstraction an application of identity function fit in one line:

In other words verbosity is not an issue... Our issue is that Term is a functor and Recursive Term is not!

There is a way to fix that without sacrificing expressibility.