Comment by mbivert
3 days ago
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))
Binary λ-calculus is then merely about finding a way to encode those three things in binary; here's how the author does it (from the blog post):
00 means abstraction (pops in the Krivine machine)
01 means application (push argument continuations)
1...0 means variable (with varint de Bruijn index)
The last one isn't quite clear, but she gives examples in `compile.sh`:
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
To check your understanding, you may want to try to manually convert some λ-expressions using those encoding rules, starting with simple ones, and check what you have with what `compile.sh` yields.
[0]: https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-L...
I never would have been able to understand lambda calculus well enough to write the blog post if I started with [0]. I say just pull out the shell and start coding things. Then read [0] later to appreciate things on a deeper level.
I think I must agree: while I went through [0] to build a λ-calculus interpreter, I already had a fair amount of practice with Church encoding (list, bool, int) using an arbitrary functional language, which retrospectively must have helped greatly to make Selinger's notes clearer.