Pattern Calculus: Computing with Functions and Structures [Hardcover]

Barry Jay (Author)

Book Description

Publication Date: August 12, 2009 | ISBN-10: 3540891846 | ISBN-13: 978-3540891840 | Edition: 1

The pattern calculus is a new foundation for computation, in which the expressive power of functions and of data structures are combined within pattern-matching functions. The best existing foundations focus on either functions, as in the lambda-calculus, or on data structures, as in Turing machines, or on compromises involving both, as in object-orientation. By contrast, a small typed pattern calculus is able to support all the main programming styles, including functional, imperative, object-oriented and query-based styles, and there is evidence that it can support a language for Web services, able to exploit data structures about which almost nothing is known. The book is divided into three parts, on terms, types and programs, and contains many new results. Part I introduces static and then dynamic pattern calculus. The former supports path polymorphic functions, able to traverse arbitrary paths through data structures. It also shows how Lisp is more than just lambda-calculus. The dynamic calculus allows any term to be a pattern, so that patterns can be discovered, combined and simplified on the fly. Part II supports a family of type systems for pattern calculi that build on novel typings of lambda-calculus. The type system for query calculus allows database queries to be applied uniformly to arbitrary data structures, while still guaranteeing that evaluation terminates. Subtyping and type parameters combine to produce type inequalities, whose solutions provide an expressive account of object-orientation. Also, typing can be made implicit, which simplifies implementation. Part III realises all these ideas in a new programming language, bondi, where the various programming styles can be combined, including algebraic data types and object-oriented classes. This book is useful for researchers with an interest in the foundations of computing, programming language design, the integration of existing programming styles, or the development of new programming styles. The reader is supported throughout with proofs and examples, both in text and in bondi, the source code of which is freely available online.

Editorial Reviews

Review

From the reviews: "In this book the author will make you have second thoughts about the possibility and desirability of compiling away pattern matching ... It is amazing that the dynamic pattern calculus is syntactically almost as simple as the pure lambda-calculus, yet it is much more expressive." (Eugenio Moggi, University of Genoa) “More than anyone else, he has systematically explored both the theory and practice of pattern matching. More importantly, the knowledge thus gained has been largely transcribed into this book. Carefully written, it concisely explains the concepts surrounding the integration of pattern matching into both the operational semantics and the type system of two programming paradigms--functional and object-oriented. … The audience for this book is researchers in programming language design; for them, I highly recommend this book.” (Jacques Carette, ACM Computing Reviews, January, 2010)

Product Details

• Hardcover: 230 pages
• Publisher: Springer; 1 edition (August 12, 2009)
• Language: English
• ISBN-10: 3540891846
• ISBN-13: 978-3540891840
• Product Dimensions: 9.4 x 6.3 x 0.3 inches
• Shipping Weight: 1.1 pounds (View shipping rates and policies)
• Average Customer Review: 4.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #991,204 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

6 of 9 people found the following review helpful:

4.0 out of 5 stars Tour de force but a hard read, October 21, 2009

By 

Litsios James - See all my reviews
(REAL NAME)   

This review is from: Pattern Calculus: Computing with Functions and Structures (Hardcover)

You will buy this book as a faithful if you have been writing software for more than thirty years and are confronted with the tear and wear in its current theoretical and practical foundations. The eternal question is "how to blend data and functions together so as be rigorously expressive but also to allow later growth of design"? This book presents one of the strongest answers this question in the form of a theoretical presentation of pattern calculus and its implementation as a programming language. Conceptually that would deserve five stars. But... style wise the book is terse and it takes sheer will power to read it carefully because the writing is linear and it does become a bit monotonous. Thus the four stars only score!

You need at least notions of type theory to read the book.

1 of 2 people found the following review helpful:

5.0 out of 5 stars Next step in theory of computations, August 25, 2010

By 

Surinder - See all my reviews

This review is from: Pattern Calculus: Computing with Functions and Structures (Kindle Edition)

Software developers know the painful truth that it takes very high caliber people to produce an average to poor quality product. The reason : software developers do not have a set of tools that construction engineers have, by which they repeatedly check their work before, during and after construction.

Pattern calculus is the next step in filling that void, next step for those who have understood Turing machines, Lambda Calculus and other forms of discrete mathematics, i.e., the state of art of computer theory. It has taken many decades for someone to come up with the next step of computation theory because this is not an easy step. To comprehend the next step requires an ability jumping from concrete to abstract thinking, the kind of jump that was required to understand Lambda calculus by arithematicians. The author has used an easy to understand style with simple examples to help us towards that.

The success of the book and the next revolution in theoretical computer science depends on the ability of a critical mass of computer scientists, understanding the concepts and realizing their significance. It is bound to happen.