4 ms·

Hey John, huge fan, and thank you for the link! I've been struggling with which paper to use to implement the Lambda Calculus (I prefer original source material

by jekude 3y ago

Hey John, huge fan, and thank you for the link! I've been struggling with which paper to use to implement the Lambda Calculus (I prefer original source material, because I feel that I learn a little more that way). I started with "An Unsolvable Problem of Elementary Number Theory" [1], but have now temporarily settled on Church's book "The Calculi of Lambda-Conversion" [2] which is a bit more explanatory and is less focused on the decision problem. Curious if you have a recommendation? [1] https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/c... [2] https://compcalc.github.io/public/church/church_calculi_1941.pdf https://compcalc.github.io/public/church/church_calculi_1941...

tromp 3y ago
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.
- jekude 3y ago
  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!
  - tromp 3y 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 https://www.irif.fr/~krivine/articles/lazymach.pdf [2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#brainfuck https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

by jekude 3y ago

tromp 3y ago

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.

jekude 3y ago
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!
- tromp 3y 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 https://www.irif.fr/~krivine/articles/lazymach.pdf [2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#brainfuck https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...