* Announcements Next homework will be out this weekend, another 2-week assignment. Next week we have Fall break on Monday-Tuesday. No office hours for me, IA/GSI will announce if they are moving theirs. Today: more depth on Lambda Lifting, which we covered too quickly before. * Review of Scope let x1 = e1, x2 = e2, x3 = e3, ... in e def f1(x11,...): e1 and def f2(x21,...): e2 and ... def fn(xn1,...): en in e let: *nested scope*: each xi is bound in e{i+1} and on and in e. Not bound in ei. def: *mutually recursive*: each fi is bound in all of the ei and e, the xji are only bound in ej In both cases we disallow the x1,... or the f1,... from defining the same name twice. But when nesting, we allow shadowing def f(x,..): e1 in let z = f(...) in def f(y,...): e2 in f(...) is allowed. * Why do we need lambda lifting? def mult(x, y): def loop(i): if i == 0: 0 else: x + loop(i - 1) in loop(y) in mult(5, 3) When we call loop, it needs to have access to at least x in each stack frame, so whenever loop is called, we need to push not just i, but also x. We can model this by a program transformation: def mult(x, y): loop(x, y) and def loop(x, i): if i == 0: 0 else: x + loop(x, i - 1) in mult(5, 3) You might say, why didn't we write the original this way, but note that the programmer didn't have to worry about the fact that x was getting captured! This is a nice convenience! General principle: Turn the program which has various *local* function definitions, which might *capture* variables in their containing scope, into a program where all functions are *lifted* to the top level as a bunch of mutually recursive functions. I.e., start with let x = 7 in def f(a,b,c): def g(z): def h(i,j,k): if i == a: g(z,b,q(k)) else: 17 in h(i,j,q(3))) and def q(r): x - r in g(c * x) in f(x, 14, 7) and turn it into something flattened: def f(x, a, b, c): g(c * x) and def g(a,b,z): h(a, i, j, q(x, 3)) and def h(a, i, j, k): if i == a: g(a, z, b, (q(x, k))) else: 17 and def q(x, r): x - r in f(x, x, 14, 7) where we have added extra arguments whereever necessary. * How to Lambda Lift We can break the lifting process into two stages: 1. Extend each function definition so that it takes all of its captured variables as arguments 2. Lift the local function definitions to the top level I.e., for our example above: def mult(x, y): def loop(i): if i == 0: 0 else: x + loop(i - 1) in loop(y) in mult(5, 3) becomes first something like def mult(x, y): def loop(x, i): if i == 0: 0 else: x + loop(x, i - 1) in loop(x, y) in mult(5, 3) and then we lift everything to the top level def mult(x, y): loop(x, y) and def loop(x, i): if i == 0: 0 else: x + loop(x, i - 1) in mult(5, 3) (Easy to fuse these if we want to) ** Variable Capture Take each function, and add as arguments, all the variables it will need to have in its stack frame at runtime. Additionally, add those arguments to every function *call*. How do we determine what variables to add to each function? Consider two things: 1. Correctness (most important) 2. Efficiency -- Class discussion --- let x = 7 in def f(a,b,c): def g(z): def h(i,j,k): if i == a: g(z,b,q(k)) else: 17 in h(i,j,q(3))) and def q(r): x - r in g(c * x) in f(x, 14, 7) def mult(x, y): def loop(x, y, i): if i == 0: 0 else: x + loop(x, y, i - 1) in loop(x, y, y) in mult(5, 3) let x1 = .. x2 = ... x3 = ... ... x100 = ... in def mult(x, y): def loop(i): if i == 0: 0 else: x + loop(i - 1) in loop(y) in mult(5, 3) Here's what I expect to hear: 1. All variables that are currently in scope? 2. All variables that occur syntactically in the body of the function? Why is (1) correct, but wasteful? Why is (2) wrong (but when it is correct, more efficient)? An example of a function where we need to capture a variable that does *not* syntactically occur in the body def f(a,b): def g(): b + h() and def h(): a in g() in f(0,1) def f(a,b): def g(a, b): b + h(a) and def h(a): a in g(a, b) in f(0,1) -- Example of (1) being *very* wasteful -- let x1 = ..., x2 = ... x3 = ... ... x100 = ... in def loop(i): if i == 0: 0 else: x1 + loop(i - 1) end loop(x2) + x100 Adds 100 variables to every stack frame!! -- Example of (2) being wrong -- def f(x): def g(a): a + h(a - 1) and def h(z): if z == 0: x else: g(a) in g(15) in ... How to improve on (2): Classical dichotomy in compilation: 1. Try to produce the best code at every stage (fixed point algorithm for determining what variables are captured) 2. Produce inefficient code but implement good optimizations *later* (implement a general purpose "unused argument removal" optimization pass) So we might have a later pass that optimizes def mult(x, y): loop(x, y, y) and def loop(x, y, i): if i == 0: 0 else: x + loop(x, y, i - 1) in mult(5, 3) into what we wrote manually. The answer (in this class) is almost always (2): for instance, the programmer might have included unused arguments in their code that you would want to get repaired anyway. If we are building an optimizing compiler anyway, let the optimizer do the work. -- Food for thought: are there settings where 1 would be more practical? -- Ok, so that's how we add in the extra arguments to the function definitions, but we also need to add the arguments to the function *calls*. -- How would you implement this? -- Regardless of how we propagate that information, there is a subtle bug(!) -- Challenge: come up with an example program such that the algorithm so far produces incorrect code -- ???????? Shadowing ??????? def f(a,b): def g(a,b): let a = 42 in b + h(a,b) and def h(a,b): a in g(a,b) in f(0,1) def f(a#0,b#0): def g(): let a#1 = 42 in b#0 + h() and def h(): a#0 in g() in f(0,1) Example: def f(x,y,z): def g(a): a + x + y in let x = 12, y = 13 in g(z) in f(1,2,3) becomes def f(x,y,z): def g(x, y, a): a + x + y in let x = 12, y = 13 in -- oh no!!! g(x, y, z) in f(1,2,3) ** Lifting The lifting is straightforward to implement once we've done this right? -- Challenge: come up with an example program that would break if we simply lift the functions to the top level -- let x = ... def f(a,b,c): e1 in ... , y = ... def f(i,j): e2 in ... in ... Shadowing is the culprit again(!) * Our Savior: Unique Identifiers Shadowing is completely reasonable for the source language syntax, but there's 0 benefit to allowing it in our source program. So why don't we get rid of it? The names of the variable itself doesn't really matter, we can always re-write the program so that there is no shadowing. Additionally, for function definitions, we will squash everything into mutual recursion, so we'll have to make everything different there. -- Discussion: at what point should we re-name variables uniquely ? -- How? Of course we'll use our handy tagging pass to give us some unique ids, then we can just append them to the names. Side benefit: once all names are uniq, you don't need to use linear environments as your data structure, and can instead reliably use HashMaps. * Updated Compiler Pipeline Source Program ---[ Parsing ] --> AST ---[ check_prog ]--> well-scoped AST --[ unique names ]--> well-scoped with unique names --[ lambda lift ]--> (AST, FunDefs) --[ sequentialize ]--> (SeqAST, SeqFunDefs) --[ codegen ]--> ASM