It is fascinating how there are such wildly different models of programming, yet they all reflect the same fundamental concept of computation. Exploring the apparent differences between these models provides a lense to explore computation. One such exploration I did was to implement a lambda calculus interpreter in prolog, or a lambda calculator. This page is a summary and additional notes to what I did. The full write-up can be found here.

Lambda calculus is a fairly well-known mathematical foundation for computation. Another, slightly-less-well-known-one, is first-order predicate logic. These mathematical ideas are translated to practical programming languages through Scheme and Prolog, respectively. (Of course there are other languages, but those are likely the two best-known ones.) I would say the fundamental “unit” of computation for lambda calculus is the beta-reduction, and for predicate logic it’s unification.

I wanted to shine a bit more light on how different these two models of computation are. Of course in the most important ways they’re equivalent, Turing-equivalent, but I’m also interested in the pragmatics.

The Project

So I wrote a lambda “calculator” in Prolog. Perhaps a default thing would be to write a version of Scheme in Prolog, but I wanted to do something a bit more fundamental. It is an 83-line Prolog program that includes a lambda calculator, ability to “sugar” and “desugar” saved expressions, and a parser for a Scheme-like CLI language. Again, the full write-up can be found here.

The Take-Aways

I really liked this project. It was a good excuse to finally use Prolog in-depth, and I think the differences (and similarities) it lights up between lambda calculus and predicate logic is just fascinating. Some highlights:

• The difference between a model of computation (the “lambda calculator”) and the larger structure that supports some kind of environment. This has been a pet peeve of mine for a while, where people say “Scheme is just lambda calculus” — it’s not! The extra work needed to support a namespace helps illustrate that.
• Prolog’s model of computation is fascinating in part because it allows for a kind of super-general pattern matching. By analogy to an IO model, whatever parameters you don’t provide as input will be computed as output! This allows predicates to run “in reverse”. This is all a coarse analogy, to be clear, and I hope you see the difficulty to even describe what’s happening only speaks more to the fascinating power here.
• If you read enough about Scheme or Lisp you’ll find adulations to the Macro: It allows you to define your own syntax! It is something subtly different from function evaluation! It is, but there are limits. I’ve found this project to be a nice small foray into really exploring what macros are.

So I hope you read my full write-up and find this all equally fascinating. I have retired this project and will not take it further; it’s done for me, but I’d be glad for any comments or questions.

Additional Resources

I say as much in the write-up pdf, but the key resources I read to implement this project are:

• The Art of Prolog, which I read cover-to-cover and found really interesting. It is helpful to have some prior experience. After reading this it felt very natural to use Prolog for this project.
• An Introduction to Functional Programming through Lambda Calculus, a terrific read of building up a scheme-like language from just the core building blocks of lambda calculus. It’s not about an actual implementation, but a conceptual one.