# Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states:

We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a reader who understands that page has little need for that book.

Has anyone got an online link to the equivalent of this mathematical summary of The Little Schemer in a single page? Presumably this would cover recursion, lambda and the y-combinator.

• Voted to close as not a real question. It is obvious that the authors want to focus on succictness versus explanatory power, in a statement similar to asymptotic statements on running times. For example, if the technical description was a page and a half or two pages, this would not change the idea the statement tries to convey. – chazisop Jun 4 '12 at 7:52
• I agree with chazisop, this doesn't look like a real question. – Kaveh Jun 4 '12 at 21:32
• No, I disagree, OP is just following up on a footnote, looking for references. – John Clements Jun 5 '12 at 4:49
• This is a real question. The OP wants a succinct reference for the mathematical background for a book. It is not obvious that this reference exists. "Read the book and summarise it yourself" isn't really a good answer. – Vijay D Jun 8 '12 at 6:19

What Sam said.

Also, it's really well under a page. If you're familiar with evaluation contexts, you can specify the call-by-value lambda calculus like this:

Terms

$$M ::= x \mid (M \, M) \mid (\lambda x . M)$$

Values

$$V = (\lambda x . M)$$

Evaluation contexts

$$E ::= [\:] \mid ([\:] M) | (V [\:])$$

The (only) reduction rule:

$$E[((\lambda x . M) V)] \to E[M.\mathrm{subst}(V,x)]$$

where $.\mathrm{subst}$ denotes capture-avoiding substitution.

Again, though, the background knowledge involved in reading this definition is by no means self-evident. There are many free places on the web to read about it. For a tidy and well-typeset presentation, you might also be interested in Felleisen/Flatt/Findler's book, Semantics Engineering with Redex.

Holey Moley! I just googled for it, and got the full PDF online. Well, that won't last...

• There's more to Scheme than the call-by-value lambda-calculus, like there's more to mathematics than the ZF(C) axioms. – Gilles 'SO- stop being evil' Jun 4 '12 at 22:29
• Hey, thanks for the nice-looking edit! Your comment is bang on, as well; OP seemed to be following up on a note, and I'm hoping that this provides what he's looking for. – John Clements Jun 5 '12 at 4:47
• Also, I probably shouldn't call it a calculus; this is really more of a reduction semantics. – John Clements Jun 5 '12 at 4:48

All you really need is the definition of the untyped $\lambda$-calculus, which you can find in numerous places. Everything else follows from that.