undefined | Better HN

0 pointstromp2y ago0 comments

In what language do you want to implement the lambda calculus? I think that while Church's writings are great background material, they do not make the best guides for implementation.

0 comments

2 comments · 1 top-level

jekude2y ago· 1 in thread

I have a secret goal to simulate a Turing Machine in the Lambda Calculus, and vice versa, so I was hoping to implement both in the same language so that interoperability would be easier.

I chose Go for the Turing Machines because I enjoy writing it, and planned to blindly use Go again for the Lambda Calculus for the reason above, but if you have a recommendation I'd love to hear it!

trompOP2y ago

Go is similar to C in that neither supports closures (in the form of lambda expressions with untyped arguments). For my own implementation of lambda calculus in C, I chose to implement a so-called Krivine machine, which is one of the simplest abstract machines for the call-by-name lambda-calculus.

Although I never wrote a Turing Machine interpreter in the lambda calculus, I did write one for its close cousin, the Brainfuck language [2].

[1] https://www.irif.fr/~krivine/articles/lazymach.pdf

[2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

j / k navigate · click thread line to collapse