SEB1525@draper.COM ("Steve Bacher ", Batchman) (09/12/88)
From: CCFVX3::SEB1525 "Steve Bacher (Batchman)" 12-SEP-1988 07:12 To: IN%"jeschke@iuvax.cs.indiana.EDU",SEB1525 Subj: RE: Re: Intermediate Lambda Calculus --> Machine code Would you say that Alonzo Church's book on lambda calculus is a prerequisite to the Peyton-Jones book? Or is it reasonable to dig in without a thorough background in lambda calculus? (John McCarthy once admitted that he had understood only a small part of Church's lambda calculus prior to inventing Lisp - he didn't read the whole book.)
gjs@ZOHAR.AI.MIT.EDU (Gerald Jay Sussman) (09/12/88)
Church's book is pretty irrelevent and unnecessary these days. If you want something theoretical about Lambda Calculus read Stoy. You certainly don't need anything more hairy than SICP to read Peyton-Jones.
windley@CHEETAH.UCDAVIS.EDU (Phil Windley) (09/12/88)
I've seen a book by Barendregt (I think the spelling's right) on lambda calculus. Is it any good? Phil Windley | windley@iris.ucdavis.edu Division of Computer Science | ucbvax!ucdavis!iris!windley College of Engineering | (916) 752-7324 (or 3168) University of California, Davis | Davis, CA 95616
kfr@zippy.eecs.umich.edu (Karl F. Ruehr) (09/13/88)
"The Lambda Calculus: its Syntax and Semantics", Henk Barendregt.
North-Holland (first edition, 1981; revised edition, 1984). Approx.
$35.00 in paperback (look in a library first).
This is the modern encyclopedic reference work on the lambda calculus
and combinatory logic. It is probably not of much use to anyone who
isn't really committed to deep study: the first 70 pages (of 611
total) are probably more than sufficient introduction for most needs,
and it does not generally address computer science-related issues.
A wonder of modern typography. Photographs of several famous
theorists. At least one fun exercise (6.8.14 on page 149.
"Introduction to Combinators and Lambda Calculus", Roger Hindley and
Jonathan Seldin. London Mathematical Society Student Texts #1,
Cambridge U. Press, 1986. Price unknown, but probably < $35.00.
This is a shorter, more relaxed introduction to the subject (not much
model theory, for example, though see Chapter 12). More suitable for
curiosity-seekers, but still not exactly oriented toward the computer
scientist specifically. Produced from typewriter proofs. Cute
Appendix # 3.
"The Calculi of Lambda Conversion", Alonzo Church. Princeton
University Press, 1941.
The original work (or very close to it) on lambda calculus (for
combinatory logic, see Curry & Feys' "Combinatory Logic" or
Schoenfinkel's work of 1924 (reprinted in "The Sourcebook for
Mathematical Logic" (title?))). Of mostly historical interest,
though not to be dismissed. Not much relevance to programming.
The only books/works I can think of that would be helpful for
functional language implementers, etc. would be:
-- the Peyton-Jones book mentioned in the original article;
-- perhaps a recent book by Glaser, Tinkin and Hill (the names are only
approximate); I haven't read the book, but I recall that it has a chapter
on lambda calculus. "Functional Programming" probably in title.
-- "Functional Programming" by Peter Henderson. Prentice-Hall,
"red-and-white binding series". Perhaps the best bet besides
Peyton-Jones.
-- "Recursive Programming Techniques" by Burge (a bit out of date, but
a real gold-mine of techniques, etc.psa@otter.hple.hp.com (Patrick Arnold) (09/14/88)
The book is Principles of Functional Programming by Glaser, Hankin and Till. It's so long since I read it it must be introductory!!