Lambda Calculus

Introduction

This website has been created as a study of programming languages, and how one would build an interpreter for λ-calculus, the simplest programming language.

The purpose of this website is to demonstrate fundamental concepts about programming languages via a hands-on approach. This is mainly aimed at educators & students in computer science trying to teach & learn the foundations of programming languages, and how compilers/interpreters work. A good example of a course in which this could be used is CS 45600 @ Purdue University.

There are two main ways this website achieves this goal:

1. By presenting a working implementation of a recursive-descent parser & interpreter for λ-calculus
2. By introducing the paradigm of functional programming, a much more pure, fundamental & abstract way of coding, as compared to more widespread paradigms such as object-oriented programming or procedural programming

Recursive-Descent Parsing

The interactive λ-calculus interpreter that can be found further down on this page is implemented via recursive-descent parsing, wherein text is fed into a mechanism that attempts to match it against certain recursive rules — those that are written in reference to themselves.

The beauty with this technique is that once the text is matched with its rule, it's easy to provide JavaScript code (or any other language for that matter) that does exactly what the λ-code is supposed to do; in other words, a recursive descent parser written in JavaScript converts λ-calculus to JavaScript on the fly. Essentially, the rules become self-enforcing.

This exciting mechanism can be inspected at the GitHub repository of this project, which bears for all to see the elegant code that parses & interprets λ-calculus. There's a lot to learn from trying to understand how this code works, and I believe it provides an excellent example/case study to students in a course about programming languages.

Functional Programming

Now that we know how to evaluate λ-calculus, we turn to its fundamental yet far-reaching implications. The so-called "simplest programming language" ushers in an incredible style of coding, one which many coders have yet to experience.

Functional programming, in which functions can be created, destroyed & operated on like any other data type, is a direct consequence of λ-calculus. This paradigm is incredibly powerful, and draws upon fundamental concepts in computer science. λ-calculus contains the rudiments of important constructs in functional programming, which is why it's a great place to start learning the domain.

This website showcases said rudiments, and provides a hands-on learning experience where prospective coders & students alike can play around with λ-terms and understand how they interact in a non-rigorous setting.

• Enter a λ-expression into the input field
  • To enter the character 'λ', simply use the backslash key '\'
  • Hit enter or press Evaluate to evaluate the λ-expression
  • The evaluation will yield β- and η-reductions of the entered expression, as well as any α-equivalent terms present in the Formulæ list
  • Any λ-expressions that take longer than 100 ms to evaluate, or that result in a stack overflow will yield ⊥, which represents an irreducible term
    • Due to the way browsers run this script (most likely on a low-priority thread), λ-expressions may sometimes take longer than 100 ms to evaluate, and time out, yielding ⊥, regardless of whether they are theoretically reducible or not
    • This is especially the case when switching back to this tab after spending (CPU) time elsewhere – the tab would be backgrounded, and thus would take extremely long (> 100 ms) to compute λ-evaluations
    • The solution is simple – keep hitting Evaluate until the tab is foregrounded again and yields the correct evaluation
• Formulas that can be used in λ-expressions are found in the Formulæ dropdown list
  • A formula is an alias for an expression; It's a variable that is substituted for its corresponding expression during evaluation
  • An assortment of combinators are already preloaded into the list
  • Custom formulas can be added using the Add Formula button
• A λ-expression can be converted to an expression containing only the S, K & I combinators using the SKI button
  • Definitions for these combinators (the so-called SKI calculus) can be found in Formulæ section
• The source code for this website can be found at github.com/freddycoppa/lambda-js

?