Comment by joseda-hg
It's too basic for what you need but the video from eyesomorphic [1], is a wonderful conceptual introduction
It's too basic for what you need but the video from eyesomorphic [1], is a wonderful conceptual introduction
> Yet all that separates the λ-calculus from one modern programming language, Haskell, is a layer of syntactic sugar on top, and a runtime that effectuates its pure IO actions. We can in fact compile Haskell programs using just stdin/stdout for IO into terms of the untyped lambda calculus, as wonderfully demonstrated in Ben Lynn's IOCCC entry [1].
That's what Turing completeness means, though; you can do the same thing with C, with the same provisos. (Conal Elliott has an amusing satire on this: http://conal.net/blog/posts/the-c-language-is-purely-functio... .) It's not that the lambda calculus isn't sufficiently expressive, just that it's not a language in which humans want to write.
> I wasn't just claiming Turing completeness of Haskell. I was pointing out that every language construct, every subexpression in Haskell, directly represents a corresponding lambda term, with corresponding semantics (e.g. laziness).
I was referring to the Turing completeness of the lambda calculus, not of Haskell. But, again, I think that trying to work directly with lambda expressions everywhere, even if it is possible and, as you say, straightforward for "vanilla" Haskell, quickly shows why we put some semantic sugar over it. That is to say, it's certainly true that, in an obvious sense, the layer of semantic sugar is thinner for Haskell than for C, but it's still "just" semantic sugar, and still just as conceptually important, in both cases.
For anyone who's interested - Ben Lynn also has a series of articles that explain the creation of that compiler and add further enhancements:
video author is using 3b1b's manim (https://github.com/3b1b/manim). wonderful presentation.
> Whilst it certainly isn't a contender for modern programming languages
Yet all that separates the λ-calculus from one modern programming language, Haskell, is a layer of syntactic sugar on top, and a runtime that effectuates its pure IO actions. We can in fact compile Haskell programs using just stdin/stdout for IO into terms of the untyped lambda calculus, as wonderfully demonstrated in Ben Lynn's IOCCC entry [1], or equivalently, into BLC programs.
[1] https://www.ioccc.org/2019/lynn/index.html