4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – chazisop Jun 4 '12 at 7:52
  • $\begingroup$ I agree with chazisop, this doesn't look like a real question. $\endgroup$ – Kaveh Jun 4 '12 at 21:32
  • $\begingroup$ No, I disagree, OP is just following up on a footnote, looking for references. $\endgroup$ – John Clements Jun 5 '12 at 4:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Vijay D Jun 8 '12 at 6:19
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ There's more to Scheme than the call-by-value lambda-calculus, like there's more to mathematics than the ZF(C) axioms. $\endgroup$ – Gilles 'SO- stop being evil' Jun 4 '12 at 22:29
  • $\begingroup$ 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. $\endgroup$ – John Clements Jun 5 '12 at 4:47
  • $\begingroup$ Also, I probably shouldn't call it a calculus; this is really more of a reduction semantics. $\endgroup$ – John Clements Jun 5 '12 at 4:48
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.