The Optimal Implementation of Functional Programming Languages

Front Cover
Cambridge University Press, Dec 3, 1998 - Computers - 392 pages
All traditional implementation techniques for functional languages 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 work, the first on 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 basic familiarity with functional languages. It will be welcomed by graduate students and research workers in lambda calculus, functional programming or linear logic.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

III
1
V
4
VI
8
VII
14
IX
15
X
19
XI
20
XII
29
LXVIII
208
LXIX
209
LXX
212
LXXI
215
LXXII
216
LXXIII
217
LXXIV
220
LXXV
221

XIII
33
XIV
35
XV
38
XVI
39
XVII
41
XVIII
43
XIX
46
XX
50
XXI
52
XXII
60
XXIII
63
XXIV
66
XXV
71
XXVII
73
XXVIII
75
XXIX
76
XXX
80
XXXI
81
XXXII
83
XXXIII
86
XXXIV
88
XXXVI
89
XXXVII
91
XXXVIII
96
XXXIX
98
XL
101
XLI
105
XLII
108
XLIII
119
XLIV
122
XLV
124
XLVI
126
XLVII
129
XLVIII
138
XLIX
141
L
142
LI
144
LII
148
LIII
150
LIV
154
LV
159
LVI
168
LVII
178
LVIII
179
LIX
181
LX
184
LXI
185
LXII
189
LXIII
191
LXIV
196
LXV
199
LXVI
200
LXVII
206
LXXVI
222
LXXVII
223
LXXVIII
224
LXXIX
225
LXXX
227
LXXXI
229
LXXXII
231
LXXXIII
233
LXXXIV
235
LXXXV
239
LXXXVI
240
LXXXVII
243
LXXXVIII
244
LXXXIX
247
XC
248
XCI
250
XCII
257
XCIII
262
XCIV
265
XCV
268
XCVI
269
XCVII
272
XCVIII
273
XCIX
277
C
279
CI
281
CII
284
CIII
288
CIV
291
CV
296
CVI
302
CVII
303
CVIII
305
CIX
313
CXI
316
CXII
328
CXIII
329
CXIV
331
CXV
334
CXVI
342
CXVII
343
CXVIII
344
CXIX
351
CXX
352
CXXI
355
CXXII
361
CXXIII
365
CXXIV
370
CXXV
371
CXXVI
376
CXXVII
383
CXXVIII
390
Copyright

Common terms and phrases

Popular passages

Page 387 - In Automata, Languages and Programming. 24th International Colloquium, volume 1256 of Lecture Notes in Computer Science, pages 177-187.
Page 388 - Press, 1980. [LM96] Julia L. Lawall and Harry G. Mairson. Optimality and inefficiency: What isn'ta cost model of the lambda calculus? In 1996 ACM International Conference on Functional Programming, 1996.
Page 386 - S. Abramsky and G. McCusker. Linearity, sharing and state: a fully abstract game semantics for Idealized Algol with active expressions (extended abstract). In Proceedings of 1996 Workshop on Linear Logic, volume 3 of Electronic notes in Theoretical Computer Science. Elsevier, 1996.

Bibliographic information