Categorical Combinators, Sequential Algorithms and Functional Programming (Progress in Theoretical Computer Science) [Hardcover]

P.-L. Curien (Author)

Book Description

Publication Date: January 1, 1993 | ISBN-10: 0817636544 | ISBN-13: 978-0817636548 | Edition: 1

This book is a thoroughly revised edition of a monograph that presents an approach to the design and implementation of sequential programming languages based on the relationship between lambda-calculus and category theory. The foundations of a new "categorical" combinatory logic are laid down. Compilation and evaluation techniques are investigated. A simple abstract machine, called the Categorical Abstract Machine, is presented: it has served as the core of the implementation of the language CAML, of the ML family, developed at INRIA-Roquencourt and Ecole Normale Superieure, and first released in 1987. The main characteristics of this approach are conceptual simplicity and compactness, with bearings on portability, efficiency, and correctness proofs. A mathematical semantics of sequentiality is proposed, in which "sequential algorithms" rather than functions are used to interpret procedures. The theoretical investigation has led to the development of a programming language, CDSO, in which basic and functional types are not differentiated. The evaluation framework is a demand-driven data flow network. The model of sequential algorithms is fully abstract with respect to this language: two procedures have the same denotation if and only if they have the same behaviour. Background on full abstraction is given. The new edition covers new results, and introduces new connections, as suggested by the following non-exhaustive fist of keywords: confluence properties of categorical combinators, explicit substitutions, control operations, linear logic, geometry of interaction, strong stability.

Product Details

• Hardcover: 403 pages
• Publisher: Birkhäuser Boston; 1 edition (January 1, 1993)
• Language: English
• ISBN-10: 0817636544
• ISBN-13: 978-0817636548
• Product Dimensions: 9.3 x 6.1 x 1.1 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 3.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #3,988,998 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

3.0 out of 5 stars Nothing introductory about it., April 4, 2006

By 

K. Rhodes "masukomi" (Cambridge, MA USA) - See all my reviews
(REAL NAME)   

This review is from: Categorical Combinators, Sequential Algorithms and Functional Programming (Research notes in theoretical computer science) (Paperback)

This book requires serious familiarity with calculus to get through. If equations filled with Greek symbols makes your head spin then stay away.

As for the Functional programming part:
"The language described is called CDS0, and should be the 'machine language' of a higher level programming lannguage CDS taking some features of ML (mostly data abstraction facilities); hence CDS should be compiled into CDS0 before execution. Only the material of sections 2 and 3 (i.e. the calculus of the expressions of CDS0, without type control), is already implemented."

This book Looks like it has a lot of good content but it's by no means an introductory text to the topics in the title. Being anything but comfortable in calculus and not even remotely interested in learning functional programming at such a low level I can't really comment on the quality of the content.