Programming in Standard ML

Preface......Page 3
I Overview......Page 12
1.1 A Regular Expression Package......Page 14
1.2 Sample Code......Page 23
II The Core Language......Page 24
2.1 Evaluation and Execution......Page 26
2.2 The ML Computation Model......Page 27
2.2.1 Type Checking......Page 28
2.2.2 Evaluation......Page 30
2.3 Types, Types, Types......Page 32
2.5 Sample Code......Page 34
3.1 Variables......Page 35
3.2.1 Type Bindings......Page 36
3.2.2 Value Bindings......Page 37
3.3 Compound Declarations......Page 38
3.4 Limiting Scope......Page 39
3.5 Typing and Evaluation......Page 40
3.6 Sample Code......Page 43
4.1 Functions as Templates......Page 44
4.2 Functions and Application......Page 45
4.3 Binding and Scope, Revisited......Page 48
4.4 Sample Code......Page 50
5.1.1 Tuples......Page 51
5.1.2 Tuple Patterns......Page 53
5.2 Record Types......Page 56
5.3 Multiple Arguments and Multiple Results......Page 59
5.4 Sample Code......Page 61
6.1 Homogeneous and Heterogeneous Types......Page 62
6.2 Clausal Function Expressions......Page 63
6.3 Booleans and Conditionals, Revisited......Page 64
6.4 Exhaustiveness and Redundancy......Page 65
6.5 Sample Code......Page 67
7 Recursive Functions......Page 68
7.1 Self-Reference and Recursion......Page 69
7.2 Iteration......Page 72
7.3 Inductive Reasoning......Page 73
7.4 Mutual Recursion......Page 76
7.5 Sample Code......Page 77
8.1 Type Inference......Page 78
8.2 Polymorphic Definitions......Page 81
8.3 Overloading......Page 84
8.4 Sample Code......Page 87
9.1 List Primitives......Page 88
9.2 Computing With Lists......Page 90
9.3 Sample Code......Page 92
10.1 Datatype Declarations......Page 93
10.2 Non-Recursive Datatypes......Page 94
10.3 Recursive Datatypes......Page 96
10.4 Heterogeneous Data Structures......Page 99
10.5 Abstract Syntax......Page 100
10.6 Sample Code......Page 102
11.1 Functions as Values......Page 103
11.2 Binding and Scope......Page 104
11.3 Returning Functions......Page 106
11.4 Patterns of Control......Page 108
11.5 Staging......Page 110
11.6 Sample Code......Page 113
12 Exceptions......Page 114
12.1.1 Primitive Exceptions......Page 115
12.1.2 User-Defined Exceptions......Page 116
12.2 Exception Handlers......Page 118
12.3 Value-Carrying Exceptions......Page 121
12.4 Sample Code......Page 123
13.1 Reference Cells......Page 124
13.2 Reference Patterns......Page 126
13.3 Identity......Page 127
13.4 Aliasing......Page 129
13.5 Programming Well With References......Page 130
13.5.1 Private Storage......Page 131
13.5.2 Mutable Data Structures......Page 133
13.6 Mutable Arrays......Page 135
13.7 Sample Code......Page 137
14.1 Textual Input/Output......Page 138
14.2 Sample Code......Page 140
15 Lazy Data Structures......Page 141
15.1 Lazy Data Types......Page 143
15.2 Lazy Function Definitions......Page 144
15.3 Programming with Streams......Page 146
15.4 Sample Code......Page 148
16.1 Sample Code......Page 149
17.1 Sample Code......Page 150
III The Module Language......Page 151
18.1.1 Basic Signatures......Page 153
18.1.2 Signature Inheritance......Page 155
18.2 Structures......Page 157
18.2.1 Basic Structures......Page 158
18.2.2 Long and Short Identifiers......Page 159
18.3 Sample Code......Page 161
19 Signature Matching......Page 162
19.1 Principal Signatures......Page 163
19.2 Matching......Page 164
19.4 Sample Code......Page 168
20.1 Ascribed Structure Bindings......Page 169
20.2 Opaque Ascription......Page 171
20.3 Transparent Ascription......Page 173
20.4 Transparency, Opacity, and Dependency......Page 175
20.5 Sample Code......Page 176
21.1 Substructures......Page 177
21.2 Sample Code......Page 185
22.1 Combining Abstractions......Page 186
22.2 Sample Code......Page 193
23.1 Functor Bindings and Applications......Page 194
23.2 Functors and Sharing Specifications......Page 197
23.3 Avoiding Sharing Specifications......Page 199
23.4 Sample Code......Page 203
IV Programming Techniques......Page 204
24.1 Specifications......Page 206
24.2 Correctness Proofs......Page 208
24.3 Enforcement and Compliance......Page 211
25.1 Exponentiation......Page 214
25.2 The GCD Algorithm......Page 219
25.3 Sample Code......Page 223
26.1 Natural Numbers......Page 224
26.2 Lists......Page 226
26.3 Trees......Page 227
26.4 Generalizations and Limitations......Page 228
26.5 Abstracting Induction......Page 229
26.6 Sample Code......Page 231
27.1 Regular Expressions and Languages......Page 232
27.2 Specifying the Matcher......Page 234
27.3 Sample Code......Page 240
28 Persistent and Ephemeral Data Structures......Page 241
28.1 Persistent Queues......Page 244
28.2 Amortized Analysis......Page 247
28.3 Sample Code......Page 250
29.1 The n-Queens Problem......Page 251
29.2 Solution Using Options......Page 253
29.3 Solution Using Exceptions......Page 254
29.4 Solution Using Continuations......Page 256
29.5 Sample Code......Page 258
30 Higher-Order Functions......Page 259
30.1 Infinite Sequences......Page 260
30.2 Circuit Simulation......Page 263
30.3 Sample Code......Page 266
31.1 Cacheing Results......Page 267
31.2 Laziness......Page 269
31.3 Lazy Data Types in SML/NJ......Page 271
31.4 Recursive Suspensions......Page 273
31.5 Sample Code......Page 274
32 Data Abstraction......Page 275
32.2 Binary Search Trees......Page 276
32.3 Balanced Binary Search Trees......Page 278
32.4 Abstraction vs. Run-Time Checking......Page 282
32.5 Sample Code......Page 283
33.1 Sample Code......Page 284
34.1 Sample Code......Page 285
35.1 Sample Code......Page 286
36.1 Sample Code......Page 287
V Appendices......Page 288
The Standard ML Basis Library......Page 289
Compilation Management......Page 290
36.4 Sample Code......Page 291
Sample Programs......Page 292