The book addresses ways and means of organizing computations, highlighting the relationship between algorithms and the basic mechanisms and runtime structures necessary to execute them using machines. It completely abstracts from concrete programming languages and machine architectures, taking instead the lambda calculus as the basic programming and program execution model to design various abstract machines for its correct implementation.
The emphasis is on fully normalizing machines based on full-fledged beta-reductions as essential prerequisites for symbolic computations that treat functions and variables truly as first-class objects. Their weakly normalizing counterparts are shown to be functional abstract machines that sacrifice the flavors of full beta-reductions for decidedly simpler runtime structures and improved runtime efficiency. Further downgrading of the lambda calculus leads to classical imperative machines that permit side-effecting operations on the runtime environment.
Author(s): Werner Kluge
Series: Texts in Theoretical Computer Science. An EATCS Series
Publisher: Springer
Year: 2005
Language: English
Pages: 399
Cover......Page 1
Abstract
Computing
Machines......Page 4
Texts in Theoretical Computer Science
An EATCS Series......Page 3
ISBN 3540211462......Page 5
Preface......Page 8
Acknowledgments......Page 10
Contents......Page 12
1
Introduction......Page 16
2
Algorithms and Programs......Page 26
3
An Algorithmic Language......Page 52
4
The λ-Calculus......Page 66
5
The se(m)cd Machine and Others......Page 104
6
Toward Full-Fledged λ-Calculus Machines......Page 128
7
Interpreted Head-Order Graph Reduction......Page 164
8
The B-Machine......Page 186
9
The G-Machine......Page 208
10
The π–red Machinery......Page 230
11
Pattern Matching......Page 268
12
Another Functional Abstract Machine......Page 286
13
Imperative Abstract Machines......Page 304
14
Real Computing Machines......Page 336
A
Input/Output......Page 362
B
On Theorem Proving......Page 376
References......Page 384
Index......Page 392
