Programming in Standard ML

Preface......Page 3
I Overview......Page 14
1.1 A Regular Expression Package......Page 16
1.2 Sample Code......Page 25
II The Core Language......Page 26
2.1 Evaluation and Execution......Page 28
2.2 The ML Computation Model......Page 29
2.2.1 Type Checking......Page 30
2.2.2 Evaluation......Page 32
2.3 Types, Types, Types......Page 34
2.5 Sample Code......Page 36
3.1 Variables......Page 37
3.2.1 Type Bindings......Page 38
3.2.2 Value Bindings......Page 39
3.3 Compound Declarations......Page 40
3.4 Limiting Scope......Page 41
3.5 Typing and Evaluation......Page 42
3.6 Sample Code......Page 45
4.1 Functions as Templates......Page 46
4.2 Functions and Application......Page 47
4.3 Binding and Scope, Revisited......Page 50
4.4 Sample Code......Page 52
5.1.1 Tuples......Page 53
5.1.2 Tuple Patterns......Page 55
5.2 Record Types......Page 58
5.3 Multiple Arguments and Multiple Results......Page 61
5.4 Sample Code......Page 63
6.1 Homogeneous and Heterogeneous Types......Page 64
6.2 Clausal Function Expressions......Page 65
6.3 Booleans and Conditionals, Revisited......Page 66
6.4 Exhaustiveness and Redundancy......Page 67
6.5 Sample Code......Page 69
7 Recursive Functions......Page 70
7.1 Self-Reference and Recursion......Page 71
7.2 Iteration......Page 74
7.3 Inductive Reasoning......Page 75
7.4 Mutual Recursion......Page 78
7.5 Sample Code......Page 79
8.1 Type Inference......Page 80
8.2 Polymorphic Definitions......Page 83
8.3 Overloading......Page 86
8.4 Sample Code......Page 89
9.1 List Primitives......Page 90
9.2 Computing With Lists......Page 92
9.3 Sample Code......Page 94
10.1 Datatype Declarations......Page 95
10.2 Non-Recursive Datatypes......Page 96
10.3 Recursive Datatypes......Page 98
10.4 Heterogeneous Data Structures......Page 101
10.5 Abstract Syntax......Page 102
10.6 Sample Code......Page 104
11.1 Functions as Values......Page 105
11.2 Binding and Scope......Page 106
11.3 Returning Functions......Page 108
11.4 Patterns of Control......Page 110
11.5 Staging......Page 112
11.6 Sample Code......Page 115
12 Exceptions......Page 116
12.1.1 Primitive Exceptions......Page 117
12.1.2 User-Defined Exceptions......Page 118
12.2 Exception Handlers......Page 120
12.3 Value-Carrying Exceptions......Page 123
12.4 Sample Code......Page 125
13.1 Reference Cells......Page 126
13.2 Reference Patterns......Page 128
13.3 Identity......Page 129
13.4 Aliasing......Page 131
13.5 Programming Well With References......Page 132
13.5.1 Private Storage......Page 133
13.5.2 Mutable Data Structures......Page 135
13.6 Mutable Arrays......Page 137
13.7 Sample Code......Page 139
14.1 Textual Input/Output......Page 140
14.2 Sample Code......Page 142
15 Lazy Data Structures......Page 143
15.1 Lazy Data Types......Page 145
15.2 Lazy Function Definitions......Page 146
15.3 Programming with Streams......Page 148
15.4 Sample Code......Page 150
16.1 Sample Code......Page 151
17.1 Sample Code......Page 152
III The Module Language......Page 153
18.1 Signatures......Page 155
18.1.1 Basic Signatures......Page 156
18.1.2 Signature Inheritance......Page 157
18.2.1 Basic Structures......Page 160
18.2.2 Long and Short Identifiers......Page 161
18.3 Sample Code......Page 163
19 Signature Matching......Page 164
19.1 Principal Signatures......Page 165
19.2 Matching......Page 166
19.4 Sample Code......Page 170
20.1 Ascribed Structure Bindings......Page 171
20.2 Opaque Ascription......Page 172
20.3 Transparent Ascription......Page 175
20.4 Sample Code......Page 177
21.1 Substructures......Page 178
21.2 Sample Code......Page 186
22.1 Combining Abstractions......Page 187
22.2 Sample Code......Page 194
23.1 Functor Bindings and Applications......Page 195
23.2 Functors and Sharing Specifications......Page 198
23.3 Avoiding Sharing Specifications......Page 200
23.4 Sample Code......Page 204
IV Programming Techniques......Page 205
24.1 Specifications......Page 207
24.2 Correctness Proofs......Page 209
24.3 Enforcement and Compliance......Page 212
25.1 Exponentiation......Page 215
25.2 The GCD Algorithm......Page 220
25.3 Sample Code......Page 224
26.1 Natural Numbers......Page 225
26.2 Lists......Page 227
26.3 Trees......Page 228
26.4 Generalizations and Limitations......Page 229
26.5 Abstracting Induction......Page 230
26.6 Sample Code......Page 232
27.1 Regular Expressions and Languages......Page 233
27.2 Specifying the Matcher......Page 235
27.3 Sample Code......Page 241
28 Persistent and Ephemeral Data Structures......Page 242
28.1 Persistent Queues......Page 245
28.2 Amortized Analysis......Page 248
28.3 Sample Code......Page 251
29.1 The n-Queens Problem......Page 252
29.2 Solution Using Options......Page 254
29.3 Solution Using Exceptions......Page 255
29.4 Solution Using Continuations......Page 257
29.5 Sample Code......Page 259
30 Higher-Order Functions......Page 260
30.1 Infinite Sequences......Page 261
30.2 Circuit Simulation......Page 264
30.3 Regular Expression Matching, Revisited......Page 267
30.4 Sample Code......Page 269
31.1 Cacheing Results......Page 270
31.2 Laziness......Page 272
31.3 Lazy Data Types in SML/NJ......Page 274
31.4 Recursive Suspensions......Page 276
31.5 Sample Code......Page 277
32 Data Abstraction......Page 278
32.2 Binary Search Trees......Page 279
32.3 Balanced Binary Search Trees......Page 281
32.4 Abstraction vs. Run-Time Checking......Page 285
32.5 Sample Code......Page 286
33.1 Sample Code......Page 287
34.1 Sample Code......Page 288
35.1 Sample Code......Page 289
36.1 Sample Code......Page 290
V Appendices......Page 291
A The Standard ML Basis Library......Page 292
B Compilation Management......Page 293
B.3 Sample Code......Page 294
C Sample Programs......Page 295