Book: "The Optimal Implementation of Functional Programming Languages"

Massimo Dentico
Sat, 04 Sep 1999 20:31:17 +0200

>From Cambridge University Press:

The Optimal Implementation of Functional Programming Languages

Andrea Asperti - University of Bologna
Stefano Guerrini - Queen Mary and Westfield College


All traditional implementation techniques for functional languages
(mostly  based on supercombinators, environments or continuations)
fail  to  avoid useless repetition of work; they are not 'optimal'
in  their implementation of sharing, often causing a catastrophic,
exponential explosion in reduction time. Optimal reduction  is  an
innovative  graph reduction technique for functional  expressions,
introduced  by  Lamping in 1990, that solves the sharing  problem.
This book, the first in the subject, is a comprehensive account by
two of its leading exponents. Practical implementation aspects are
fully  covered  as  are  the  mathematical  underpinnings  of  the
subject.  The relationship to the pioneering work of LÚvy  and  to
Girard's more recent Geometry of Interaction are explored; optimal
reduction  is  thereby  revealed as  a  prime  example  of  how  a
beautiful  mathematical theory can lead to practical benefit.  The
book   is  essentially  self-contained,  requiring  no  more  than
familiarity  with  functional languages. It will  be  welcomed  by
graduate   students  and  research  workers  in  lambda  calculus,
functional programming or linear logic.

Is this technique well-known?

Massimo Dentico