Jay Pattern Calculus

Computing with Functions and Structures
1. Auflage 2009
ISBN: 978-3-540-89185-7
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 213 Seiten

Over time, basic research tends to lead to specialization – increasingly narrow t- ics are addressed by increasingly focussed communities, publishing in increasingly con ned workshops and conferences, discussing increasingly incremental contri- tions. Already the community of programming languages is split into various s- communities addressing different aspects and paradigms (functional, imperative, relational, and object-oriented). Only a few people manage to maintain a broader view, and even fewer step back in order to gain an understanding about the basic principles, their interrelation, and their impact in a larger context. The pattern calculus is the result of a profound re-examination of a 50-year - velopment. It attempts to provide a unifying approach, bridging the gaps between different programming styles and paradigms according to a new slogan – compu- tion is pattern matching. It is the contribution of this book to systematically and elegantly present and evaluate the power of pattern matching as the guiding paradigm of programming. Patterns are dynamically generated, discovered, passed, applied, and automatically adapted, based on pattern matching and rewriting technology, which allows one to elegantly relate things as disparate as functions and data structures. Of course, pattern matching is not new. It underlies term rewriting – it is, for example, inc- porated in, typically functional, programming languages, like Standard ML – but it has never been pursued as the basis of a unifying framework for programming.

Autoren/Hrsg.

Jay, Barry

Inhaltsverzeichnis

1;Foreword;6
2;Preface;8
3;Contents;10
4;List of Figures;14
5;Part I Terms;17
5.1;Introduction;18
5.1.1;Programming Styles;18
5.1.2;A Motivating Problem;20
5.1.3;Pattern Matching;21
5.1.4;Types;22
5.1.5;bondi;23
5.1.6;Synopsis;25
5.1.7;How to Read This Book;26
5.2;Functions;28
5.2.1;Substitution;28
5.2.2;Pure -Calculus;29
5.2.3;-Reduction;32
5.2.4;Confluence;33
5.2.5;Fixpoints;35
5.2.6;Notes;37
5.3;Data Structures;38
5.3.1;Constructors and Operators;38
5.3.2;Ad Hoc Operators;39
5.3.3;Data Structures as Abstractions;41
5.3.4;Compound Calculus;43
5.3.5;Defined Operators;45
5.3.6;Notes;46
5.4;Static Patterns;47
5.4.1;Patterns;47
5.4.2;Static Pattern Calculus;48
5.4.3;Static Matching;49
5.4.4;Constructor Patterns;50
5.4.5;Generic Mapping;53
5.4.6;Generic Queries;54
5.4.7;Relating to Compound Calculus;57
5.4.8;Notes;58
5.5;Dynamic Patterns;59
5.5.1;First-Class Patterns;59
5.5.2;Dynamic Pattern Calculus;61
5.5.3;Matching;62
5.5.4;Confluence of Matching;64
5.5.5;String Matching;66
5.5.6;Encoding Static Patterns;67
5.5.7;Wildcards;68
5.5.8;Views;69
5.5.9;Notes;70
5.6;Objects;73
5.6.1;Records;73
5.6.2;Inheritance and Method Specialisation;75
5.6.3;Object Calculus;76
5.6.4;Notes;78
6;Part II Types;79
6.1;Parametric Polymorphism;80
6.1.1;Simply Typed -Calculus;80
6.1.2;Data Structures as Typed Abstractions;83
6.1.3;Quantified Types;84
6.1.4;System F;85
6.1.5;Reduction of Type Applications;86
6.1.6;Lists as Functions;87
6.1.7;Strong Normalisation;90
6.1.8;Notes;92
6.2;Functor Polymorphism;93
6.2.1;Ad Hoc Polymorphism;93
6.2.2;Typecases;94
6.2.3;System FM;96
6.2.4;Typecase Calculus;99
6.2.5;Combinatory Types;100
6.2.6;Functorial Mapping;101
6.2.7;Notes;102
6.3;Path Polymorphism;103
6.3.1;Typing Components;103
6.3.2;Query Calculus;105
6.3.3;Selecting;106
6.3.4;Terminating Queries;108
6.3.5;Typed Static Pattern Calculus;111
6.3.6;Selectors by Patterns;114
6.3.7;Notes;115
6.4;Pattern Polymorphism;116
6.4.1;Matchable Type Symbols;116
6.4.2;Typed Pattern Calculus;118
6.4.3;Matching Typed Patterns;119
6.4.4;Generic Equality;120
6.4.5;Notes;122
6.5;Inclusion Polymorphism;123
6.5.1;Methods Without Objects;123
6.5.2;Subtyping;126
6.5.3;Simply Typed Method Calculus;127
6.5.4;Method Types;128
6.5.5;Parametric Method Calculus;133
6.5.6;Subtyped Pattern Calculus;134
6.5.7;Coloured Circles;136
6.5.8;Notes;138
6.6;Implicit Typing;139
6.6.1;Extension Calculus;139
6.6.2;Linear Types;141
6.6.3;Typing Special Cases;142
6.6.4;Typing the Extension Calculus;143
6.6.5;Datum Types;145
6.6.6;Constrained Subtyping;146
6.6.7;Subtyped Extension Calculus;147
6.6.8;Notes;150
7;Part III Programming in bondi;152
7.1;Higher-Order Functions;153
7.1.1;From Calculus to Programming Language;153
7.1.2;Let-Terms;154
7.1.3;Notes;155
7.2;Algebraic Data Types;156
7.2.1;Type Declarations;156
7.2.2;Pattern-Matching Functions;158
7.2.3;Polymorphism in Data;161
7.2.4;Generic Functional Programming;162
7.2.5;Adding Cases to Existing Functions;164
7.2.6;The Expression Problem;166
7.2.7;Notes;167
7.3;Queries;168
7.3.1;Numerical Functions;168
7.3.2;Polymorphic Recursion;171
7.3.3;Searching and Modifying;172
7.3.4;Notes;175
7.4;Dynamic Linear Patterns;176
7.4.1;Generic Elimination;176
7.4.2;Salaries or Wages;178
7.4.3;Notes;178
7.5;State;179
7.5.1;References;179
7.5.2;Linked Lists;181
7.5.3;Notes;184
7.6;Object-Oriented Classes;185
7.6.1;Classifying Objects;185
7.6.2;Classes;186
7.6.3;Subclasses;189
7.6.4;Specialised Methods;190
7.6.5;Parametrised Classes;192
7.6.6;Building on Standards;195
7.6.7;Updating Salaries;198
7.6.8;Notes;203
7.7;Syntax;204
7.7.1;Untyped Terms;204
7.7.2;Types;205
7.7.3;Typed Terms;207
7.8;References;210
7.9;Index;215