Introduction to the λ-Calculus | Hacker News Reader

Introduction to the λ-Calculus

lawrencecpaulson.github.io

46 pointsmatt_d19 comments

Open articleView on HN

> (according to one rumour, because Dana Scott was fond of curry)

I always assumed it was related to Haskell Curry, the logician.

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?

What is the benefitsof the lambda notation over a more intuitive arrow notation like x->x+1?

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.

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 λ

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))

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.

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

Reply on news.ycombinator.com