<p>What Sam said.</p>

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

<p>Terms </p>

<p>$$M ::= x \mid (M \, M) \mid (\lambda x . M)$$</p>

<p>Values</p>

<p>$$V = (\lambda x . M)$$</p>

<p>Evaluation contexts</p>

<p>$$E ::= [\:] \mid ([\:] M) | (V [\:])$$</p>

<p>The (only) reduction rule:</p>

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

<p>where $.\mathrm{subst}$ denotes capture-avoiding substitution.</p>

<p>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, <em>Semantics Engineering with Redex</em>.</p>

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

CC BY-SA 3.0
2012-06-04T22:29:26.133Z
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'
CC BY-SA 3.0
2012-06-05T04:47:42.683Z
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
CC BY-SA 3.0
2012-06-05T04:48:39.377Z
Also, I probably shouldn't call it a calculus; this is really more of a reduction semantics.
John Clements
CC BY-SA 3.0
2012-06-04T19:49:36.190Z
2012-06-04T22:42:10.797Z
2012-06-04T22:42:10.797Z
John Clements
<p>All you really need is the definition of the untyped $\lambda$-calculus, which you can find in numerous places.  Everything else follows from that.</p>

CC BY-SA 3.0
2012-06-04T15:00:51.810Z
2012-06-04T15:00:51.810Z
Sam Tobin-Hochstadt
<p>In the preface of Friedman and Felleisen's book The Little Schemer it states:</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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. </p>

CC BY-SA 3.0
2012-06-04T07:52:20.777Z
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
CC BY-SA 3.0
2012-06-04T21:32:40.617Z
I agree with chazisop, this doesn't look like a real question.
Kaveh
CC BY-SA 3.0
2012-06-05T04:49:37.453Z
No, I disagree, OP is just following up on a footnote, looking for references.
John Clements
CC BY-SA 3.0
2012-06-08T06:19:28.807Z
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
<computability><recursion><lisp><scheme>
Mathematical explanation of recursion and lambda (referenced in The Little Schemer)
hawkeye
# Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

(Asked by: username_0 on 2012-06-04)

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.

**Tags:** computability, recursion, lisp, scheme

> **Comments:**
> **username_1**: 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.  
> **username_2**: I agree with username_1, this doesn't look like a real question.  
> **username_3**: No, I disagree, OP is just following up on a footnote, looking for references.  
> **username_4**: 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.  

---

## 2 answers

### Answer by username_3 on 2012-06-04. Score: 4 | Accepted answer

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

> **Comments:**
> **username_5**: There's more to Scheme than the call-by-value lambda-calculus, like there's more to mathematics than the ZF(C) axioms.  
> **username_3**: 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.  
> **username_3**: Also, I probably shouldn't call it a calculus; this is really more of a reduction semantics.  

---

### Answer by username_6 on 2012-06-04. Score: 3

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


---

