Pattern Calculus (eBook)

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