An Introduction to the Lambda Calculus (2015) | Hacker News Reader

An Introduction to the Lambda Calculus (2015)

learningclojure.com

206 pointstosh34 comments

Any introduction to anything should start with a clear statement of what it is and why you might want to use it. I find this a particular problem with computer language topics; I don't know yet why The Author find This Thing so useful so tell me up front a few benefits I might get from investing my time in learning it. Unfortunately, the people who are best at using something are not always the best at communicating it.

This is particularly important for audiences like teenagers, who already have multiple private and public actors competing for their attention and future economic potential.

Any example like what you said?

I agree with you. So, I want to know examples out there that have a great explanation about something.

There was a thread a day or two about about a book called The Scientist's and Engineer's guide to digital Signal Processing which I think is the best-written technical book I've ever encountered. The other one that springs to mind is C: How to Program by Deitel and Deitel. They've done multiple programming cooks but that's the only one I've owned.

No problem. Anyway, thank you.

I try to use the Why, What, How, What If framework..

Why - Why should you care about this, why does this matter. What - What is it. How - How does it work. What If - Here is the thing you can do right now to get started...

If you have an Android phone/tablet and want to play around with the lambda calculus, I made an app that lets you build and evaluate expressions using a touch interface:

https://play.google.com/store/apps/details?id=com.alangpierc...

https://www.youtube.com/watch?v=0OzpqDDniDs

It's lower-level than the stuff in the post (you need to build booleans and math yourself) and doesn't have any instructional content built-in at the moment, but I think it's a nice way to see how far you can get using only lambda expressions. The most complicated thing I've done with it is used the Y combinator (among other things) to compute 6! = 720, which is a fun exercise.

Very cool idea! Is it open source or are you thinking about it?

Yep, it's on GitHub:

https://github.com/alangpierce/lambdacalculusplayground

I actually got mostly done porting it to React Native, but never totally finished it, so the GitHub repo is React Native and has some bugs. But you can go back in the git history to find the native Android SDK version that's currently on the Play Store.

Did I find the right point in the history?

https://github.com/alangpierce/LambdaCalculusPlayground/tree...

Yep, that should work. Two commits earlier is the actual 1.1.0 release, before some restructuring to make room for the React Native stuff, so that may be a little better to work with.

https://github.com/alangpierce/LambdaCalculusPlayground/comm...

Just out of curiosity, is there a particular reason why some people refer to lambda calculus with a definite article?

My professor in CS Theory would refer to it as "the" lambda calculus, but another professor I had chose not to (I call it "lambda calculus").

This is totally trivial, I'm just wondering if there's a reason why you, or some people, say "the" lambda calculus.

Good question. I think it's just an oddity/ambiguity of English (and other languages as well, I'm sure). I know that calculus (with derivatives and integrals) has been called "the calculus" in the past. I mostly just say "the lambda calculus" because that's what I've heard.

Another way that it seems consistent in my mind is that there are many calculi (systems for computing things) out there, and the lambda calculus is one particular calculus that uses lambda expressions as the building block. The pi calculus is another example. The "the" feels a little more appropriate when "lambda" is seen as a modifier specifying which calculus I'm referring to.

In other cases, I'll drop the "the", though. For example, I might say "There are three types of lambda calculus expressions.".

Your final case isn't specific to "lambda calculus". In that sentence, you're using "lambda calculus" as a modifier for the general term "expressions", rather than referring to it on its own. Consider that you would say "There are three types of ceiling lights", but you would still say "the ceiling".

"<x> calculus" without an article is an activity, whereas "the <x> calculus" is a concept. That's the way I've always parsed it internally. For example, you would never say to someone "Do you know about SKI Calculus?" because it's not something people do. You would say "Do you know about the SKI Calculus", referring to the abstract notion that someone constructed. We often use the phrase "calculus" for the calculus of derivatives and the calculus of integrals because it's something people do as an activity very often. Same with the lambda calculus.

That may work for your internal parsing, but it's not correct with respect to any standard of English grammar. Consider that any activity can also be a topic of knowledge, and it doesn't change article usage: "do you know about football?"

"The", the definite article, has a couple of purposes in English, but by far the most common is to refer to an individual member of a set of nouns. The decision to use it or not in this case depends on how the the words "lambda calculus" are interpreted:

1. "Lambda calculus" is a compound noun that describes a unique or uncountable object or concept. In this case, "lambda calculus" is in effect the only member of the set to which it belongs, and so "the" is not used. Compare with any other conceptual noun, e.g. "mathematics".

2. "Lambda calculus" is a compound noun, but is not unique - that is, there are multiple things that could be referred to as "lambda calculus". In this case, "the" is used to select a particular lambda calculus. An extended phrase might be "the lambda calculus introduced by Alonzo Church, as opposed to the lambda calculus introduced by Joe Shmoe." Note also that in general parlance, "the" can be used alone to refer to the most common one of something, as if that member of the set were always considered an antecedent to current conversation. For example, in certain circles in California, "the industry" refers to the entertainment industry. Because it's so common to refer to that particular member of the set of all industries, "the" on its own is sufficient to select it.

3. "Lambda calculus" is a generic noun (calculus) with a modifier (lambda) that makes it unique. In this case, similar to (2), "the" must be used, as it along with "lambda" serves to select the particular calculus being referred to. Compare with "the Nile River" - "Nile River" is unique, but since "Nile" is a modifier for a generic noun the article is required. (Following the final point from (2), saying simply "the calculus" would under this interpretation normally refer to the calculus of derivatives and integrals, since that's by far the most common.)

4. Same as (3), but "calculus" is not countable in the same way, and so it does not make sense to refer to the set of all things known as "calculus". In this case, "lambda calculus" refers to a portion of the singular concept "calculus" rather than a member of a set, and so "the" is not used.

I think the most common intentions are (3) and (4) for using or not using "the", respectively. (4) is more common among non-mathematicians for whom "calculus" is a singular subject in school, while (3) is more common among people who are aware that "calculus" is a general term for "form of calculation", and who might refer to the particular "calculus" taught in high school as "the calculus of derivatives and integrals". I'm normally partial to (1), myself (i.e., "lambda calculus" and "integral calculus" are each topics of knowledge, grammatically identical to "mathematics").

Great read - I worked through it in JavaScript in the console. Writing Scheme-ish code in JS is so much nicer with ES6 than it was with ES5!

    const iterativeImprove = (guess, improve, goodEnough) => 
      goodEnough(guess) ? 
        guess : 
        iterativeImprove(improve(guess), improve, goodEnough);

I think the example used (and the intermediate functions) come straight from SICP. I always intend to do the exercises in this book, but never have... This post actually got me to do it, so hat's off to you!

Yea I immediately thought this is from SICP

On that note(SICP in Clojure) there is also this which has been mentioned here on HN before:

http://www.sicpdistilled.com/

No word wrap, horizontal scroll is hijacked and the content goes off screen (Chrome on Android) the topic sounds interesting but the post is unreadable

The Wikipedia page [1] for Lambda calculus is also a great read (even for those who don't know anything about it before).

[1] https://en.wikipedia.org/wiki/Lambda_calculus

Personally I prefer this introduction by Barendregt (his books on Lambda calculus are really good): ftp://ftp.cs.ru.nl/pub/CompMath.Found/lambda.pdf

I highly recommend the book "To mock a mockingbird" for gentle and fun introduction to combinatorial logic.

Does learning about the Lambda calculus have any take-aways for programming in modern languages, or is it more of a cool toy/mostly of interest for language designers and academics?

It gives a pretty facinating point of view onto computation in general.

You only the ability to define and call functions. Functions can only recombine their input. And somehow it is still as powerful as, say, python!

Don't need some built in math , invent numbers using function definitions. Don't need built in recursion, just implement it using functions as the y-combinator!

There are also some practical usages of the whole implement-data-as-functions idea. There are some libraries in haskell that do this, for instance, which means that the compiler can optimize dsl's.

I've found understanding the lambda calculus goes a long way to understanding functional programming—in particular, it does a wonderful job demonstrating just how simple the core ideas underlying languages like Haskell are, contrary to their reputations.

It's also a great way to get a deeper understanding of computation and how it relates to logic. The lambda calculus is special for being an incredibly minimal model of computation that's still expressive enough to write programs (albeit a little awkwardly). Expressing something you care about in lambda calculus is way easier than using a Turing machine directly or even programming in assembly!

I think lambda calculus encodes computable functions, but not algorithms, because changing evaluation order can make you go from O(n) to O(n^2) etc. To define time and space complexity, you need to assume something like Haskell's graph reduction. That's more complicated than starting with assembly and counting steps.

The lambda calculus teaches you how to build computation from a very simple evaluation rule called "beta reduction" which is just a fancy name for "search and replace" with function parameters. If you can find a system that can rewrite terms in such a fashion, you can compute whatever you want using the tricks you learn in lambda calculus.

For example, C++ templates were not meant to be Turing-complete, but they work by rewriting terms [1], so you can encode lambda calculus in it, and run arbitrary programs at compile time.

Philip Wadler does a better job than me at getting excited by lambda calculus. He calls it "the omniversal programming language", and claims that aliens will probably have discovered it [2].

[1]: http://matt.might.net/articles/c++-template-meta-programming... [2]: https://www.youtube.com/watch?v=IOiZatlZtGU

Besides the uses of the lambda calculus for functional programming, Church Encoding is also a powerful tool for algorithmics, program architecture, and performance improvement.

I actually found myself factoring my code differently after learning lambda calc. It at the very least seemed to result in better code (c#) so I would say there is practical benefits.

At the end, when talking about number notations:

> Mathematicians worry about that sort of thing. Engineers don't. Sometimes aeroplanes crash. Mostly they don't.

I would argue this statement which (to me) wrongly blames the intrinsic lack of exactness in applied science, otherwise a good read.

Factorials in pure lambda calculus:

http://www.flownet.com/ron/lambda-calculus.html

(2015)

So many parens. Much cumbersome.

Why not Haskell?

This is my opinion as to why not Haskell. I do on the whole prefer lazy languages where the parens are not mandatory, but let's be honest about the drawbacks.

So in Haskell you have "name1 name2 name3 name4 name5;" which is the application of some function to some arguments, of course, so this seems like a win compared to having to parenthesize the same thing. But when you have name1 name2 name3 + name4 name5, you had better want (name1 name2 name3) + (name4 name5) because that's the precedence. I think in some scenarios you can throw $ at the expression to get a more advantageous interpretation. And for fun you can do name1 name2 `name3` name4 name5 which will make things interesting.

And then there's name1 name2 . name3 name4 name5 which in some contexts might mean the coder is using point-free style, which is NOT named after a lack of periods. But point-free style is considered cool by some Haskellers.

Some LISPers like the long row of closing parens on the last line of a definition, so one man's meat, right?

There's no such thing as free syntax.

(I invite technical corrections, I'm still learning Haskell).

Reply on news.ycombinator.com