3.4 Mark 2: Making it lazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.5 Mark 3:
let(re)
expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.6 Mark 4: Adding primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.7 Mark 5: Towards b etter handling of arithmeti . . . . . . . . . . . . . . . . . . . 119
3.8 Mark 6: Adding data strutures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.9 Mark 7: Further improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.10 Conlusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4 TIM: the three instrution mahine 143
4.1 Bakground: How TIM works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.2 Mark 1: A minimal TIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.3 Mark 2: Adding arithmeti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.4 Mark 3:
let(re)
expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.5 Mark 4: Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.6 Mark 5: Strutured data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
4.7 Mark 6: Constant appliative forms and the o de store
y
. . . . . . . . . . . . . . 189
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5 A Parallel G-mahine 196
5.1 Intro dution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.2 Mark 1: A minimal parallel G-mahine . . . . . . . . . . . . . . . . . . . . . . . . 200
5.3 Mark 2: The evaluate-and-die mo del . . . . . . . . . . . . . . . . . . . . . . . . . 209
5.4 Mark 3: A realisti parallel G-mahine . . . . . . . . . . . . . . . . . . . . . . . . 212
5.5 Mark 4: A b etter way to handle blo king . . . . . . . . . . . . . . . . . . . . . . 214
5.6 Conlusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
6 Lamb da Lifting 217
6.1 Intro dution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.2 Improving the
expr
data typ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.3 Mark 1: A simple lambda lifter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
6.4 Mark 2: Improving the simple lamb da lifter . . . . . . . . . . . . . . . . . . . . . 230
6.5 Mark 3: Johnsson-style lambda lifting . . . . . . . . . . . . . . . . . . . . . . . . 231
6.6 Mark 4: A separate full laziness pass . . . . . . . . . . . . . . . . . . . . . . . . . 236
3
