Foundations of Programming Languages

Preface......Page 3
Contents......Page 7
Introduction......Page 13
Historical Perspective......Page 14
Models of Computation......Page 18
Origins of few Languages......Page 22
Language Implementation......Page 30
Types & Type Checking......Page 37
Chapter Summary......Page 39
Review Questions......Page 40
Solutions......Page 41
Terminology......Page 43
Backus Naur Form (BNF)......Page 45
Context-free Grammars......Page 46
Derivations......Page 47
Parse Trees......Page 49
Abstract Syntax Trees......Page 50
Lexical Analysis......Page 51
Parsing......Page 54
Top-Down Parsers......Page 55
Bottom-Up Parsers......Page 57
Other Forms of Grammars......Page 61
Limitations of Syntactic De
nitions......Page 62
Review Questions......Page 63
Solutions......Page 64
Assembly Language......Page 69
Overview of JCoCo VM......Page 70
Start......Page 73
IO......Page 76
IF-THEN-ELSE......Page 78
WHILE......Page 83
Exception Handling......Page 85
List Constants......Page 88
Calling a Method......Page 89
Iterating over List......Page 91
Range Objects & Lazy Evaluation......Page 93
Functions & Closures......Page 95
Recursion......Page 99
Support for Classes & Objects......Page 101
Review Questions......Page 110
Exercises......Page 111
Solutions......Page 112
OOP......Page 123
Java Environment......Page 126
C++ Environment......Page 128
Namespaces......Page 133
Dynamic Linking......Page 134
De
ning the Main Function......Page 135
IO Streams......Page 136
Garbage Collection......Page 137
Threading......Page 138
PyToken Class......Page 139
Inheritance & Polymorphism......Page 142
Interfaces & Adapters......Page 146
Functions as Values......Page 148
Anonymous Inner Classes......Page 149
Type Casting & Generics......Page 150
Auto-Boxing & Unboxing......Page 153
Exception Handling in Java & C++......Page 154
Scanner......Page 157
Parser......Page 160
Assembler......Page 163
ByteCode......Page 164
JCoCos Class & Interface Type Hierarchy......Page 167
Code......Page 169
Functions......Page 170
Methods......Page 172
JCoCo Exceptions & Tracebacks......Page 175
Magic Methods......Page 177
Dictionaries......Page 180
Chapter Summary......Page 183
Review Questions......Page 184
Exercises......Page 185
Solutions......Page 187
Functional Programming......Page 190
Imperative vs Functional......Page 192
Lambda Calculus......Page 193
Start with SML......Page 195
Expressions, Types, Structures & Functions......Page 196
Recursive Functions......Page 198
Characters, Strings & Lists......Page 201
Pattern Matching......Page 204
LET Expressions & Scope......Page 205
Datatypes......Page 208
Ef
ciency of Recursion......Page 211
Tail Recursion......Page 214
Currying......Page 215
Anonymous Functions......Page 217
Higher-Order Functions......Page 218
Continuation Passing Style......Page 223
IO......Page 224
Programming with Side-Effects......Page 225
Exception Handling......Page 227
Encapsulation in ML......Page 228
Type Inference......Page 230
Pre“x Calculator Interpreter......Page 231
Chapter Summary......Page 235
Exercises......Page 236
Solutions......Page 239
Compiling Standard ML......Page 246
ML-lex......Page 248
Small AST De“nition......Page 252
ML-yacc......Page 254
Compiling & running the Compiler......Page 259
Function Calls......Page 263
Let Expressions......Page 265
Unary Negation......Page 268
IF-THEN-ELSE......Page 270
Short-Circuit Logic......Page 273
De
ning Functions......Page 276
Reference Variables......Page 280
Chapter Summary......Page 283
Exercises......Page 284
Solutions......Page 287
Logic Programming......Page 288
Start with Prolog......Page 290
Fundamentals......Page 291
The Prolog Program......Page 292
Lists......Page 294
Accumulator Pattern......Page 295
Uni“cation & Arithmetic......Page 296
IO......Page 297
Structures......Page 298
Parsing in Prolog......Page 300
Prolog Grammar Rules......Page 304
Building an AST......Page 305
Attribute Grammars......Page 306
Chapter Summary......Page 309
Exercises......Page 310
Solutions......Page 312
SMLType Inference......Page 316
Why Static Type Inference......Page 317
Type Inference Rules......Page 319
Using Prolog......Page 320
Type Environment......Page 323
Integers, Strings & Boolean Constants......Page 324
List & Tuple Constants......Page 325
Identi
ers......Page 326
Function Application......Page 327
LET Expressions......Page 330
Patterns......Page 332
Matches......Page 336
Anonymous Functions......Page 337
IF-THEN & WHILE-DO......Page 338
Exception Handling......Page 339
Review Questions......Page 340
Exercises......Page 341
Solutions......Page 345
JCoCo VM Speci“cation......Page 347
Types......Page 348
JCoCo Magic & Attr Methods......Page 349
Global Built-in Functions......Page 350
VM Instructions......Page 351
Load & Store Instructions......Page 352
List, Tuple & Dictionary Instructions......Page 354
Conditional & Iterative Execution Instructions......Page 355
Function Execution Instructions......Page 357
Special Instructions......Page 358
Bool......Page 359
Int......Page 360
Real......Page 362
Char......Page 367
String......Page 368
List......Page 371
Array......Page 374
TextIO......Page 375
Biblio......Page 378