Functional programming and parallel graph rewriting(free web version)

Charting the progress of the theory, implementation and applications of rewriting models of computation, this study represents a key resource for researchers. A major feature of the book is the presentation of theoretical advances such as a new theory of transfinite term rewriting, a single pushout categorical model of graph rewriting and an abstract interpretation for term graph rewriting. 1. An Introduction To Term Graph Rewriting / J. R. Kennaway, J. W. Klop, M. R. Sleep And F. J. De Vries -- 2. Partial Type Assignment In Left Linear Applicative Term Rewriting Systems / S. Van Bakel, S. Smetsers And S. Brock -- 3. How To Get Confluence For Explicit Substitutions / T. Hardin -- 4. An Infinitary Church-rosser Property For Non-collapsing Orthogonal Term Rewriting Systems / J. R. Kennaway, J. W. Klop, M. R. Sleep And F. J. De Vries -- 5. The Functional Strategy And Transitive Term Rewriting Systems / Y. Toyama, S. Smetsers, M. C. J. D. Van Eekelen And M. J. Plasmeijer -- 6. Graph Rewriting Systems For Efficient Compilation / Z. M. Ariola And Arvind -- 7. A Fibration Semantics For Extended Term Graph Rewriting / R. Banach -- 8. A New Term Graph Rewriting Formalism : Hyperedge Replacement Jungle Rewriting / A. Corradini And F. Rossi -- 9. Abstract Reduction: Towards A Theory Via Abstract Interpretation / M. C. J. D. Van Eekelen, E. Goubault, C. L. Hankin And E. Nocker --^ 10. A Lattice For The Abstract Interpretation Of Term Graph Rewriting Systems / E. Goubault And C. L. Hankin -- 11. Event Structures And Orthogonal Term Graph Rewriting / J. R. Kennaway, J. W. Klop, M. R. Sleep And F. J. De Vries -- 12. The Adequacy Of Term Graph Rewriting For Simulating Term Rewriting / J. R. Kennaway, J. W. Klop, M. R. Sleep And F. J. De Vries -- 13. Translations Into The Graph Grammar Machine / H.-j. Kreowski -- 14. An Algebraic Framework For The Transformation Of Attributed Graphs / M. Lowe, M. Korff And A. Wagner -- 15. Hypergraph Rewriting: Critical Pairs And Undecidability Of Confluence / D. Plump -- 16. A Quick Look At Tree Transductions / J.-c. Raoult -- 17. Paragon Specifications And Their Implementation / P. Anderson, D. Bolton And P. H. J. Kelly -- 18. Monstr: Term Graph Rewriting For Parallel Machines / R. Banach -- 19. A Graph Rewriting Model Enhanced With Sharing For Or-parallel Execution Of Logic Programs / W. Damm, F. Lui And T. Peikenkamp --^ 20. A New Process Model For Functions / J. Glauert, L. Leth And B. Thomsen -- 21. Parallel Execution Of Concurrent Clean On Zapp / R. G. Goldsmith, D. L. Mcburney And M. R. Sleep -- 22. Graph-based Operational Semantics Of A Lazy Functional Language / K. H. Rose -- 23. Graph Rewriting Using The Annotated Functional Strategy / P. W. M. Koopman, J. E. W. Smetsers, M. C. J. D. Van Eekelen And M. J. Plasmeijer -- 24. Implementing Logical Variables And Disjunctions In Graph Rewrite Systems / P. J. Mcbrien -- 25. Process Annotations And Process Types / M. C. J. D. Van Eekelen And M. J. Plasmeijer -- 26. Jalpa: A Functional Modular Programming Language Based On Extended Graphical Term Rewriting / H. Yamanaka. Edited By M.r. Sleep And M.j. Plasmeijer And M.c.j.d. Van Eekelen. Papers Presented At The Semagraph '91 Symposium, At The University Of Nijmegen, Dec. 10-12, 1991. Includes Bibliographical References And Index. "Charting the progress of the theory, implementations and applications of rewriting models of computation, this volume represents a key resource for researchers. Much of modern computer science - particularly 'new generation languages' - relies heavily on rewriting systems, and Term Graph Rewriting offers an insight into the very foundations." "A major feature of the book is the presentation of theoretical advances, such as: a new theory of transfinite term rewriting, a single pushout categorical model of graph rewriting, and an abstract interpretation for term graph rewriting." "In order to fully appreciate the practical but novel benefits offered by term and graph rewriting techniques, readers are here presented with the most comprehensive study conducted to date. A crucial theme throughout is the relationship between term and graph rewriting which provides a useful context for considering implementations - ranging from high performance sequential to parallel distributed memory, and applications - specifically to logic and functional programming."--BOOK JACKET Contents......Page 1 Preface......Page 2 1 Basic concepts......Page 17 2 Advanced concepts: Miranda......Page 52 3 The lambda-calculus......Page 92 4 Term rewriting systems......Page 127 5 Graph rewriting systems......Page 160 6 Type assignment systems......Page 197 7 Strictness analysis......Page 231 8 Clean - draft chapter......Page 263 8 Clean......Page 302 9 Translating Miranda to Clean......Page 349 10 Abstract ABC machine......Page 369 11 Translating Clean into ABC code......Page 390 12 Realizing the ABC machine......Page 414 13 Concurrency: Basic language concepts......Page 450 14 Parallel graph rewriting......Page 476 15 Concurrent Clean......Page 496 16 The parallel ABC machine......Page 508 17 Realizing the PABC machine......Page 528 A Syntax of example programs......Page 548 B Concurrent Clean syntax and library......Page 552 C ABC machine specification......Page 576 D PABC machine specification......Page 589 Bibliography......Page 601 Index......Page 610 Errata, 2001......Page 619 This volume charts the progress of the theory, implementation and applications of rewriting models of computation. It presents such theoretical advances as transfinite term rewriting, categorical models of graph rewriting and interpretations of term graph rewriting.