Jones N.D.Partial evaluation and automatic program generation.1999

malloc, 243 Malmkj r, K., 372 marked, 86

Marquard, M., 224, 370, 371 Martens, B., 371

matches, 348

matrix multiplication, 340 Mazaher, S., 374 McCarthy, J., 347, 374 megastep, 182 memoization, 3 meta-interpreter, 194, 373 meta-language, 139 meta-logical predicates, 193 Meyer, U., 368

Miller, D., 12

Milner, R., 340

MIMD processor network, 283 minimal completion, 172 Miranda, 141

mix, 368

mix algorithm, 85 e cient, 86

mix equation, 4, 71, 337, 342 for lambda calculus, 169

mixed binding times, 149, 153, 271 mixed computation, 367

mixline partial evaluation, 153 Mixtus, 195

modular programming, 277

Mogensen, T. ., 163, 192, 224, 267, 278, 369, 370, 374

monovariant

binding-time analysis, 106 division, 96, 103

Moore, J.S., 374

Mosses, P., 375

Mossin, C., 371 mutable memory, 234 Mycroft, A., 310

N (natural numbers), 26 named function, 206 natural numbers N, 26 natural semantics, 38 negation by failure, 193 neural network training, 283 Nevryon, 277

Nielson, F., 110, 159, 310, 371, 372 Nielson, H.R., 110, 159, 371 Nirkhe, V., 368

non-oblivious algorithm, 286, 290 nonlocal side-e ect, 235

Index 411

normal form

in lambda calculus, 62

in pattern matching language, 348 of constraint set, 176

of constraint system, 180 normal order reduction, 48

normalization of constraint system, 180

oblivious

algorithm, 285, 287 Turing machine, 285 weakly, 289

obliviousness

a test for, 287 occurrence

bound, 45 free, 46

occurrence counting, 215 analysis, 205

o ine, 18, 122, 144, 372 advantages, 150 partial evaluation, 84 strategy, 84 termination, 298

Oliver, S., 284 on the y

compression, 104 unfolding, 104

online, 18, 122, 144, 372 advantages, 147 partial evaluation, 84 strategy, 84 termination, 297

operationally equivalent, 340 optimal, 139

optimality

of Lambdamix, 174 optimizing compilers

generation of, 150

•

Oskarsson, O., 367, 368 Ostrovski, B.N., 372 overhead

caused by interpretation, 138 overriding of function, 25

Pe (closure analysis function), 316, 317

Pv (closure propagation function), 316, 317 Pagan, F.G., 258, 372, 374

parameter, 44, 102

partial computational state, 77 partial deduction, 369

partial evaluation, 67, 370 applications of, 277

412 Index

by fold/unfold, 355 de nition, 4

for Ansi C, 258

for ow chart language, 67 for lambda calculus, 163 for Prolog, 192

for Scheme0, 101 for Scheme1, 204 mixline, 153 o ine, 84 online, 84 rede nition, 341

termination of, 297 partial evaluator, 2

type of, 337, 343 partial function, 24, 26

partially static, 223, 323, 370 array, 240

function, 212, 330 heap-allocation, 243 struct, 241

paths in a graph, 291 pattern matching, 28, 285 Paulson, L., 375

PE, see partial evaluation PEL (language), 329 pending, 86

pending loop, 252 Penello, T.J., 285 Perluette, 375 phases

in o ine partial evaluation, 145 in online partial evaluation, 145

Pingali, K., 284

Pleban, U., 375

Plotkin, G., 38, 218, 270, 340 pointer, 242

birth-place analysis, 244 pointer analysis, 254 pointwise division, 94

poly, 79 in nite, 83

polyvariant

binding times, 112 binding-time analysis, 122 division, 96, 103

mixed computation, 68 specialization, 68, 209, 232, 370

poor man's generalization, 152, 298 postphase, 145

unfolding, 104 compression, 104

postprocessing, 205 prephase, 145 preprocessing, 205 procedure cloning, 286 product, 26

Cartesian, 23

of projections, 325 type, 26, 325

program analysis, see analysis program point specialization, 3 program specialization, 67 program specializer, 71 projection, 323

absent, 324

admissible, 324{326, 328 complement, 332

Futamura, see Futamura projection product, 325

sum, 326 uniform, 327

projection-based binding-time analysis, 328 Prolog, 192, 369

Pugh, W., 368

R (Lambdamix), 185 ray-tracing, 278 re-opening closures, 286

recipe for self-application, 157 recursion equations, 50, 52

interpreter for, 53 recursive data type, 32, 326 recursive function theory, 335 redex, 47, 348

Redfun, 367, 368 reduction, 45

applicative order, 48 normal order, 48

of constraint system, 180 rules, 46

Refal, 367, 369 regular expression, 268

compilation of, 196 reordering

of side-e ects, 119 residual command, 91 residual program, 71 rewrite rules, 347 Richter, M., 194, 195, 370 Ritchie, D.M., 229 Rogers, A., 284

Rogers, H., 335, 336

Romanenko, S.A., 94, 125, 224, 368, 369, 371 Ruf, E., 148, 150, 372

Runge-Kutta integration, 287 running time, 41, 131

Rytz, B., 371

S-expression, 29

s-m-n function property, 336 s-m-n theorem, 72, 366

safe division, 331 safety

of binding-time analysis, 106 of closure analysis, 316

of speedup analysis, 135 of speedup interval, 133

Sahlin, D., 195, 369, 370

Sandewall, E., 367, 368 Sands, D., 370

Sardu, G., 369 scanner, 257

Scheme, 101, 204, 225, 368 Scheme0, 101, 102

specializer source code, 376 two-level, 110, 111

Scheme1, 206 two-level, 207

Scherlis, W., 373, 374 Schism, 263, 368 Schmidt, D.A., 371, 375 Sch•on nkel, M., 28 Schooler, R., 368 scienti c computing, 287 scope, 53

second Futamura projection, 13, 86, 344 selector, 28

self-application, 13, 88, 91, 116, 125, 194, 215, 256

double, 14 recipe for, 157

taming by BTA, 153 self-dependency, 306 self-interpretation

lambda calculus, 164 self-interpreter, 139, 336 semantically equivalent, 340 semantics of types, 26, 34, 339

semantics-directed compiler generation, 375 Semilux, 369

Sestoft, P., 101, 118, 367, 368, 370, 371 Shapiro, E., 373

Shepherdson, J.C., 195, 369 side-e ect, 119

analysis, 198 nonlocal, 235 static, 238

Index 413

under dynamic control, 236 Similix, 204, 264, 272, 368, 371

binding-time analysis, 322 simple loop, 134 single-valued, 24

Sintzo , M., 310 SIS, 375

size analysis, 302 Smith, D.A., 372 solution

of constraint set, 177 S ndergaard, H., 101, 367, 368, 370 sorting, 291

source program, 8, 39 sp-function, 205, 217 specialization, 205

kernel, 150 point, 217 Prolog goals, 198

specialized program point, 78, 103 speedup

bound, 128

falsely superlinear, 130 function, 128

in loop, 134 interval, 132, 134

safety of, 133 linear, 128 superlinear, 347

speedup analysis, 132 experiments, 136 safety of, 135

staging transformations, 373 state, 98

state transition, 98 statement

dynamic, 230 static, 230

static, 77, 102, 166, 197 always, 149

goal, 197 part, 324 perhaps, 145 projection, 324 statement, 230 variable, 301

Steensgaard, B., 224, 370, 371 store, 57, 302

store transformer, 57

string matching, see Knuth{Morris{Pratt struct specialization, 241

structural operational semantics, 38

414 Index

subject program, 2, 71 substitution, 46, 348 suits a variable, 171 SU(l) (speedup), 134 sum

of projections, 326 type, 31

Sundaresh, R.S., 370, 373 supercompilation, 358, 369 superlinear speedup, 347

falsely, 130 impossible, 131

suspension, 54 symbolic

composition, 360 computation, 3

run time address, 242 syntax tree, 35

tp(s; d) (running time), 41, 127 t X (type), 339

table-directed input, 284 tag, 31, 325

tagged value, 31 tagging

in online partial evaluation, 147 Takeuchi, A., 369

taming

of self-application, 153 target program, 8, 76 termination

ensured by binding-time analysis, 304 of o ine partial evaluation, 298

of online partial evaluation, 297 of partial evaluation, 297

the trick, 93, 116, 266, 271 theorems for free, 274

third Futamura projection, 14, 91 thunk, 54

Tofte, M., 375 top (>), 310 top-level redex, 47

total function, 23, 26

transition compression, 81, 99, 104 on the y, 82, 93

separate phase, 82 trick

the, 93, 116, 266, 271 truth values B, 26 tupling function, 336

Turchin, V.F., 358, 367, 369 Turing interpreter, 73 Turing machine, 73, 366

enumeration, 335 oblivious, 285 program, 335

two-level

Core C, 246

execution of Core C, 250 lambda calculus, 166 Scheme0, 110

Scheme1, 207 syntax, 105 type, 171

type system (Lambdamix), 171 type, 26

assumption, 29 environment, 29, 171 function, 26 inference, 29, 123, 175

rule, 30, 339 of compiler, 337

of interpreter, 337

of partial evaluator, 337 product, 26

semantics of, 26, 34, 339 sum, 31

system combined, 176 two-level, 171

two-level, 171

unfold

reasons not to, 355 unfolding, 3, 104, 237, 351, 374

strategy, 118 uni cation, backwards, 197 uniform congruence, 77, 331 uniform division, 77 uniform projection, 327

universal function property, 336 updating of function, 25 user-oriented language, 139, 283

van Harmelen, F., 373 variable

capture, 47 free, 46

splitting, 332, 371 variable description, 303 variable only requirement, 362 variant record, 31

vector spaces, 340 Venken, R., 369 video games, 277

Wadler, P., 358

Wand, M., 12, 164, 374 weak head normal form, 47 weakly oblivious, 289 Wegbreit, B., 374

Weise, D., 148, 150, 283, 368, 372, 374 well-annotated, 171

Core C, 248 well-behaved, 220

Index 415

well-typed expression, 29

language processor, 343

whnf (weak head normal form), 47

Y combinator, 49

Yn combinator, 49

Yv combinator, 50

Z (integers), 26