31–40 of 73 posts
(The relevant part is the "Lambda calcul pur" one")
Earlier quoted context omitted.
Hey tromp, do you have any recommendations for grokking Lambda calculus properly? I've read a few tutorials and introductions, and I understand the notions of alpha- and beta-reductions, abstractions vs application, but I still have issues with practical examples like the above. Am I missing something here or should I just go back to the basics?
> I still have issues with practical examples like the above. What issues would those be? Do you see that λf.λx.n f(f x)) is the Church numeral n+1 ? I think there's few better ways to grok lambda calculus than working through examples like these step-by-step.
Cool article, BUT! it leaves so many terms unexplained: - What's the distinction between a "parameter`, a "variable", and an "argument"? - What is "body" as in "Body M"? - What's a "bound" variable? - What exactly is a "function call"? - In "... a value that is mapped to itself by the function.", what do "mapped to itself", and, more specifically, "mapped" mean? Would appreciate the answers!
I'll take one of these. > In "... a value that is mapped to itself by the function.", what do "mapped to itself", and, more specifically, "mapped" mean? A mathematical function is something more general than a function in programming. In maths, a function consists of two sets known as the domain and codomain and a rule which "maps" things in the domain into the associated things in the codomain[1]. You can think abou…
For programmers, you can think of the rule of the function as being like the function body when you write a function in a computer program. The codomain is like the return type of the function (except in maths you're really talking about a set and in maths a set and a type are somewhat different things).
The domain is like the type of the function inputs (although it's also a set not a type). So if you have a function where the rule is f(x) = x^2 you can hopefully see that if the domain is the real numbers that's a different function from if the domain is the complex numbers.
I mentioned the image set of the function in my previous post, so just to finish off the explanation, say we have f where the domain and codomain are the reals and the rule of f is f(x) = x^2. The image set of f is actually going to be all the real numbers greater than or equal to zero (even though the codomain is all real numbers). The reason for this is if you (hypothetically) went through every value in the domain and applied the rule you would always get a value from zero to positive infinity. None of the real numbers when mapped by the function (squared) will return a negative number.
The domain is the type of all the inputs, so if you have a function which takes multiple inputs, the domain will be a set of tuples (think of them like coordinates) and likewise for functions which have multiple outputs, the co-domain and image set will contain tuples.
(1) Black on white is much easier to read than white on black. That includes code snippets in blocks.
(2) If you insist on ignoring (1), at least make your white text bright enough that it can be read without serious eye strain. Particularly if the white on black is code snippets surrounded by black on white article text.
Note to article writers: (1) Black on white is much easier to read than white on black. That includes code snippets in blocks. (2) If you insist on ignoring (1), at least make your white text bright enough that it can be read without serious eye strain. Particularly if the white on black is code snippets surrounded by black on white article text.
Earlier quoted context omitted.
> I still have issues with practical examples like the above. What issues would those be? Do you see that λf.λx.n f(f x)) is the Church numeral n+1 ? I think there's few better ways to grok lambda calculus than working through examples like these step-by-step.
What's a church numeral?
It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the saying "Everything should be made as simple as possible, but not simpler." The untyped lambda calculus, they made it even simpler.
Yes, you can reduce everything to a very tiny number of combinators, but at the cost of making everything ugly. It is much cleaner to use Lisp and reduce everything to a slightly larger set of primitives. Ironically (?) one of the best explanations of this is PG's own The Roots Of Lisp - https://languagelog.ldc.upenn.edu/myl/llog/jmc.pdf
I'd really like to understand why my brain screams NO when I try to grok lisp and especially the Y combinator. It's like it's anti-interesting to me or something. I know it's cool, and useful to know, but I just can't get there. Maybe it's a stack overflow in my head? Is it just me? [Edit] Re:082349872349872 - I grew up in a world of assembler programming, BASIC and Pascal. It wasn't unusual to have all sorts of self…
It's a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing. It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…
Is that really true? ISTR you can impose the type (A -> A) -> A on the Y combinator.