Introduction to the λ-Calculus(lawrencecpaulson.github.io)
lawrencecpaulson.github.io
Introduction to the λ-Calculus
https://lawrencecpaulson.github.io/2024/09/30/Intro_Lambda_Calculus.html
19 comments
That's because it is
She was fond of curry as well.
Dana Stewart Scott is a he, if I'm not mistaken.
Hmmm you are taking all fun out /i
> Extensionality fails in most dependent type theories
Is this a reason to use Isabelle?
I remember Bob Harper being interested in dependent typing. What is his take on extensionality?
Is this a reason to use Isabelle?
I remember Bob Harper being interested in dependent typing. What is his take on extensionality?
What is the benefitsof the lambda notation over a more intuitive arrow notation like x->x+1?
I heard it evolved from Bertrand Russell, who used a notation such as \hat{x}.(x+1) to mean similar in Principia Mathematica. Church and maybe others in the logic community originally used the same notation but Church's publisher, not having latex, was unable to print it. So they wanted to move the hat in front of the letter, such as ^x.(x+1). The hat symbol either wasn't available or the instruction got mangled during production into the similar-looking lambda.
Lovely explanation! Everytime I encounter the lambda I will think of the relation to the hat symbol. The latter we used a lot at school.
What about expressing something a bit more complex like: λf. (λx. f (x x))(λx. f (x x))
It is so complex that i don't even know how to start reading it (not that i am a reference of mathematical complexity). Does the x each time mean something else?
It’s a joke. That particular lambda expression is the Y combinator.
f ↦ (x ↦ f (x x))(x ↦ f (x x))
Not much, but you immediately know it's a function (abstraction).
Besides, the standard notation for the "arrow function" is maplet (x ↦ x + 1) in mathematics. I assume λ notation sees frequent uses in logic and computation theory.
Besides, the standard notation for the "arrow function" is maplet (x ↦ x + 1) in mathematics. I assume λ notation sees frequent uses in logic and computation theory.
The characters in OP's arrow function have the benefit of being available on a standard keyboard layout. This has proven to be an important syntactic feature, imo.
Haskell uses a single backslash \ in place of λ
One benefit could be to emphasize the distinction between regular mathematical functions (e.g. x ↦ x+1) and λ-terms (e.g. λx. x+1): strictly speaking, those are different kind of objects.
Different how?
Well, λ-terms are defined by the rules of the λ-calculus[0], or variants of it, while mathematical functions have their own, distinct definition[1]. Essentially, the axioms used to define either are fundamentally different.
Not all mathematical functions can be expressed/represented by λ-terms; a famous example would be the halting problem[2]. Generally, keep in mind that the λ-calculus — as Turing machines — can only express computable functions[3].
You could also try to think about how to perform usual mathematical function operations on λ-terms: limits, differentiation, integration, etc.
[0]: https://en.wikipedia.org/wiki/Lambda_calculus
[1]: https://en.wikipedia.org/wiki/Function_(mathematics)
[2]: https://en.wikipedia.org/wiki/Halting_problem
[3]: https://en.wikipedia.org/wiki/Computable_function
Not all mathematical functions can be expressed/represented by λ-terms; a famous example would be the halting problem[2]. Generally, keep in mind that the λ-calculus — as Turing machines — can only express computable functions[3].
You could also try to think about how to perform usual mathematical function operations on λ-terms: limits, differentiation, integration, etc.
[0]: https://en.wikipedia.org/wiki/Lambda_calculus
[1]: https://en.wikipedia.org/wiki/Function_(mathematics)
[2]: https://en.wikipedia.org/wiki/Halting_problem
[3]: https://en.wikipedia.org/wiki/Computable_function
I always assumed it was related to Haskell Curry, the logician.