Pattern Calculus (eBook)

Computing with Functions and Structures

Barry Jay (Autor)

eBook Download: PDF

2009 | 2009
XVII, 213 Seiten
Springer Berlin (Verlag)
978-3-540-89185-7 (ISBN)

Infos

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.

Inhalt

Foreword 6
Preface 8
Contents 10
List of Figures 14
Part I Terms 17
Introduction 18
Programming Styles 18
A Motivating Problem 20
Pattern Matching 21
Types 22
bondi 23
Synopsis 25
How to Read This Book 26
Functions 28
Substitution 28
Pure -Calculus 29
-Reduction 32
Confluence 33
Fixpoints 35
Notes 37
Data Structures 38
Constructors and Operators 38
Ad Hoc Operators 39
Data Structures as Abstractions 41
Compound Calculus 43
Defined Operators 45
Notes 46
Static Patterns 47
Patterns 47
Static Pattern Calculus 48
Static Matching 49
Constructor Patterns 50
Generic Mapping 53
Generic Queries 54
Relating to Compound Calculus 57
Notes 58
Dynamic Patterns 59
First-Class Patterns 59
Dynamic Pattern Calculus 61
Matching 62
Confluence of Matching 64
String Matching 66
Encoding Static Patterns 67
Wildcards 68
Views 69
Notes 70
Objects 73
Records 73
Inheritance and Method Specialisation 75
Object Calculus 76
Notes 78
Part II Types 79
Parametric Polymorphism 80
Simply Typed -Calculus 80
Data Structures as Typed Abstractions 83
Quantified Types 84
System F 85
Reduction of Type Applications 86
Lists as Functions 87
Strong Normalisation 90
Notes 92
Functor Polymorphism 93
Ad Hoc Polymorphism 93
Typecases 94
System FM 96
Typecase Calculus 99
Combinatory Types 100
Functorial Mapping 101
Notes 102
Path Polymorphism 103
Typing Components 103
Query Calculus 105
Selecting 106
Terminating Queries 108
Typed Static Pattern Calculus 111
Selectors by Patterns 114
Notes 115
Pattern Polymorphism 116
Matchable Type Symbols 116
Typed Pattern Calculus 118
Matching Typed Patterns 119
Generic Equality 120
Notes 122
Inclusion Polymorphism 123
Methods Without Objects 123
Subtyping 126
Simply Typed Method Calculus 127
Method Types 128
Parametric Method Calculus 133
Subtyped Pattern Calculus 134
Coloured Circles 136
Notes 138
Implicit Typing 139
Extension Calculus 139
Linear Types 141
Typing Special Cases 142
Typing the Extension Calculus 143
Datum Types 145
Constrained Subtyping 146
Subtyped Extension Calculus 147
Notes 150
Part III Programming in bondi 152
Higher-Order Functions 153
From Calculus to Programming Language 153
Let-Terms 154
Notes 155
Algebraic Data Types 156
Type Declarations 156
Pattern-Matching Functions 158
Polymorphism in Data 161
Generic Functional Programming 162
Adding Cases to Existing Functions 164
The Expression Problem 166
Notes 167
Queries 168
Numerical Functions 168
Polymorphic Recursion 171
Searching and Modifying 172
Notes 175
Dynamic Linear Patterns 176
Generic Elimination 176
Salaries or Wages 178
Notes 178
State 179
References 179
Linked Lists 181
Notes 184
Object-Oriented Classes 185
Classifying Objects 185
Classes 186
Subclasses 189
Specialised Methods 190
Parametrised Classes 192
Building on Standards 195
Updating Salaries 198
Notes 203
Syntax 204
Untyped Terms 204
Types 205
Typed Terms 207
References 210
Index 215

Produkt-Details

• Erscheint lt. Verlag: 30.7.2009
• Zusatzinfo: XVII, 213 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• Schlagworte: bondi • data structure • data structures • Functional Programming • Imperative Programming • Lambda Calculus • LISP • object-oriented programming • OCaml • Pattern calculus • Pattern Matching • Polymorphism • programming • Programming language • Programming style • Query programming • type inference • Type Theory
• ISBN-10: 3-540-89185-4 / 3540891854
• ISBN-13: 978-3-540-89185-7 / 9783540891857