Design and Analysis of Purely Functional Programs

by Christian Rinderknecht

The aim of this book is to introduce postgraduate students to the design and analysis of algorithms expressed in a first-order, purely functional language based on term-rewriting. Analysis encompasses efficiency (cost) analysis and proofs of properties like correctness, termination, equivalence etc. The other angle is the design of fast functional programs and their implementation, where the analysis of memory usage becomes particularly relevant. The presentation does not depend on a specific programming language, but translations to Erlang and Java are presented and specific aspects of sequential programming in Erlang are detailed, like program transformation into tail form, higher-order functions and continuation-passing style. This book differs from traditional textbooks in that it does not cover many algorithms and data structures, nor many programming language features, nor does it present the most advanced analytic methods. Instead, its originality lies in constantly tying functional programming, cost analysis, proofs and implementation. As such, it is an eclectic companion for other readings, suitable for different courses, like functional programming, formal logic and analysis of algorithms.

614 pages, Paperback

First published January 23, 2012

Reviews

[Kirill · Rating 2 out of 5]

Too little design too much analysis : a lot of boring (at least for me) maths.