Lambda Calculus in 383 Bytes (2022)

The best way to wrap your mind around the core concept and internalize them into a mental model is writing an interpreter yourself. It's been abundantly clear to me since young that for anything involving math, you don't internalize it if you merely passively let someone else explain it, whether that's reading a textbook/blog or attending a professor's lecture or watching a YouTube video. You have to do the exercises.

Lambda calculus is the same. You can easily define the data structure to represent a program in untyped lambda calculus and then write an interpreter for it. Then go implement some interesting concepts such as the Y combinator or the Omega combinator. If you find lambda calculus too difficult to do things like arithmetic or linked lists, you don't have to stick with Church numerals or Scott encodings. Just introduce regular natural numbers and lists as ground types; when you later have a better understanding, write programs to transform regular numerals from and to Church numerals and bask in the fact that they are isomorphic.

I think the most ELI5 approach is Alligator Eggs [0] which was built for 8-year-olds to play like a game. You can find a lot of the advanced concepts outside of the core also explained in terms of Alligator Eggs and some software visualizers, but there's also something to be said about hands on learning and about printing it out yourself on some cardstock or cardboard paper, cutting it out, personalizing it with crayons, and playing it with a child or at least your inner child.

[0] https://worrydream.com/AlligatorEggs/

It's too basic for what you need but the video from eyesomorphic [1], is a wonderful conceptual introduction

[1] https://www.youtube.com/watch?v=ViPNHMSUcog

"To mock a mockingbird" (https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird) is a wonderful introduction to something that's sufficiently more abstract than lambda calculus that you'll probably find the latter pleasingly concrete afterwards, but it takes only tiny, bite-sized steps (err, mixed metaphors) to get you to understanding.

You might find my practical introduction to lambda calculus and combinatory logic based on javascript helpful. [1]

Its mostly based on other introductory resources but I tried to write it from a practical step by step perspective I found most useful for myself.

[1]: https://static.laszlokorte.de/combinators/

If you have some time to spare, read SICP [0] and do the exercises :) (probably easiest to use DrRacket [1] as the interpreter)

[0] https://mitp-content-server.mit.edu/books/content/sectbyfn/b...

[1] https://docs.racket-lang.org/sicp-manual/SICP_Language.html

Spending time with pure functional programming (languages like Haskell) will open up these concepts in a real-world programming environment. Obviously languages like Haskell are more complex than this, but they're all fundamentally based on lambda calculus. That could be the first step away from the imperative thinking you describe.

(That was certainly my way in to this world anyway!)

sorry for not providing explanations, but check this out: https://tromp.github.io/cl/diagrams.html

did you see https://news.ycombinator.com/item?id=42256394 (The Art and Mathematics of Genji-Ko 172 points, by olooney, 49 days ago, 10 comments)? very tangentially related, but also mesmerizing stuff, i think..

Justine - thanks so much for all these amazing projects. You're an inspiration.

One thing I saw you write recently is that chasing the newest fads is a distraction. That makes sense, but if you don't mind me asking, what do you think one should focus on instead? Which are the classic languages, tools, mindsets, and CS concepts that one must master?

I don't know if it will work for you, but I wrote a Quicksort using lambda calculus in Python, and I explained the process of writing it here:

https://lucasoshiro.github.io/software-en/2020-06-06-lambdas...

Please note that I'm not an expert in lambda calculus, just a curious nerd and it won't explain everything, like the reductions, combinators and so on. But there I explain how to implement simple types (int, boolean, pairs and lists) using Church encoding, let expressions and recursion using the Y combinator (yay, I finally used the expression "Y combinator" on HN!). Everything that we need to implement a quicksort (which is a relatively complex algorithm) using the almost nothing that we have in lambda calculus.

Another point is that it's all implemented in Python, using the Python notation instead of the lambda calculus notation, so you can run the code in your machine and play with the examples

In case the other answers aren't sufficient, the first step is to understand the λ-calculus[0]. Then, De Bruijn indices[1]. Now, observe that the language we have only has (you need familiarity with the λ-calculus to understand those terms (… pun unintended)) 1/ applications, 2/ abstractions, 3/ integers representing variables [introduced by abstractions]. For example:

    (λ (λ 1 (λ 1)) (λ 2 1))

    00      means abstraction   (pops in the Krivine machine)
    01      means application   (push argument continuations)
    1...0   means variable      (with varint de Bruijn index)

      s/9/11111111110/g
      s/8/1111111110/g
      s/7/111111110/g
      s/6/11111110/g
      s/5/1111110/g
      s/4/111110/g
      s/3/11110/g
      s/2/1110/g

[0]: https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-L...

[1]: https://en.wikipedia.org/wiki/De_Bruijn_index

I found this helpful https://brilliant.org/wiki/lambda-calculus/

Lisp is fairly similar and easy to pick up

The 43-byte implementation might define only a subset of the functionality provided by the full VM, enough to "bootstrap" into the full implementation, most likely.

In fact, if the VM is Turing complete, it can theoretically emulate any computation, including its full implementation, even from a small subset of operations.

The point is that the 43-byte implementation does not need to encode the entire VM explicitly. For example, if the VM has built-in primitives for looping, branching, and memory management, the minimal implementation can leverage these to rebuild the remaining functionality.

Binary Lambda Calculus uses de-Bruijn indices [1], thereby avoiding the need for alpha renaming.

[1] https://en.wikipedia.org/wiki/De_Bruijn_index

It doesn't work on modern Apple Silicon macs with M1-4 chips (although Rosetta [1] might be able to handle it somehow), but it works fine on my older x86 based iMac.

[1] https://en.wikipedia.org/wiki/Rosetta_(software)