4 ms·

When I took Fundamentals of Programming Languages 20 years ago - I nearly failed the class. Lambda calculus was simply too esoteric for me to appreciate and muc

When I took Fundamentals of Programming Languages 20 years ago - I nearly failed the class. Lambda calculus was simply too esoteric for me to appreciate and much less understand intuitively. Fast forward 20 years, and I see the fundamentals of Alonzo Church’s system in every computation problem I encounter. It’s one of those concepts that age like wine. The only other concept I put on the same level is Shannons “informational entropy” and maybe Wolfram’s Ruliad.

_delirium 2y ago
It's kind of interesting that the history is in the order it is. I could completely imagine it being reversed: first, 1000 programming languages are invented, then later, in an attempt to put order to this madness, and understand whether some of them are in a fundamental sense equivalent to others or not, you invent minimalist languages like Turing machines or the lambda calculus, and start developing a theory of reductions. Kind of odd that the Turing machines and lambda calculus predate almost all the others! I mean there are good reasons for it, especially if you try to put yourself in a 1930s mathematics mindset (which is why it actually happened that way), but it is, I'd submit, a bit surprising to learn from a 2020s perspective if you didn't already know it.
- andoando 2y ago
  Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete.
  - Zambyte 2y ago
    There are certain concurrent properties that cannot be modeled with a Turing machine: https://en.wikipedia.org/wiki/Unbounded_nondeterminism https://en.wikipedia.org/wiki/Unbounded_nondeterminism There is also a very interesting intersection between the history of the Actor Model and Lambda Calculus: https://research.scheme.org/lambda-papers/ https://research.scheme.org/lambda-papers/
  - mindcrime 2y ago
    > Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete. See also: https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation
- thesz 2y ago
  Before LC there were combinators [1]. [1] https://en.wikipedia.org/wiki/Combinatory_logic https://en.wikipedia.org/wiki/Combinatory_logic These are even more primitive.

_delirium 2y ago

It's kind of interesting that the history is in the order it is. I could completely imagine it being reversed: first, 1000 programming languages are invented, then later, in an attempt to put order to this madness, and understand whether some of them are in a fundamental sense equivalent to others or not, you invent minimalist languages like Turing machines or the lambda calculus, and start developing a theory of reductions. Kind of odd that the Turing machines and lambda calculus predate almost all the others! I mean there are good reasons for it, especially if you try to put yourself in a 1930s mathematics mindset (which is why it actually happened that way), but it is, I'd submit, a bit surprising to learn from a 2020s perspective if you didn't already know it.

andoando 2y ago
Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete.
- Zambyte 2y ago
  There are certain concurrent properties that cannot be modeled with a Turing machine: https://en.wikipedia.org/wiki/Unbounded_nondeterminism https://en.wikipedia.org/wiki/Unbounded_nondeterminism There is also a very interesting intersection between the history of the Actor Model and Lambda Calculus: https://research.scheme.org/lambda-papers/ https://research.scheme.org/lambda-papers/
- mindcrime 2y ago
  > Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete. See also: https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation
thesz 2y ago
Before LC there were combinators [1]. [1] https://en.wikipedia.org/wiki/Combinatory_logic https://en.wikipedia.org/wiki/Combinatory_logic These are even more primitive.