![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
todo: a lot of this affects language semantics, not just implementation. Move elsewhere.
If inner functions can access local variables from enclosing lexical scopes ('upvariables'), then how are references to these variables implemented?
If local variables are allocated on the stack, then typically they are referenced via a known offset from the beginning of the current stack frame (for example, local variable 'a' might be found at offset 5 from the current stack frame, local variable 'b' might be found at offset 7, etc). In essence, after compilation, the name of the local variable 'a' is 'local variable #5'. However, a local variable from an enclosing scope will be stored before the beginning of the current stack frame.
It is not sufficient to use a constant negative offset, because, due to recursion (eg if the inner function calls itself), there may be a variable number of frames in between the current frame and the referenced variable.
For example, Lua's VM provides bytecode instructions GETUPVAL and SETUPVAL which access upvariables. Confusingly, Lua refers to this concept as 'upvalues' rather than 'upvariables', implying immutability, although actually Lua 'upvalues' are mutable (todo: am i understanding this correctly?).
If upvariable are mutable, another design choice is whether or not the state of these variables are local to each closure (see below), or are shared between all functions with lexical access to the upvariable. For example, Golang's closures each have their own copy of each upvariable.
Another class of solution, which i will call 'upvalues' (although i mean something different from what Lua means here), is to allow references to the values of variables in enclosing scopes, but not to allow them to be mutated. This semantics can allow an implementation to copy each relevant outer local variable into the stack frame of the inner function at the time the inner function is 'instantiated' in the outer scope. The inner function can perceive these local variables as immutable, or they can mutate them, but in the latter case these mutations will not affect the outer function's copy of these variables. The time of 'instantiation' can vary; if a first-class function value is created, the values of the variables could be copied at that time, or alternately they could only be copied at the time that function is actually called.
If mutability is desired, a related 'solution' is global variables; don't allow access to local variables from enclosing scopes, but instead, allow global variables. Then when such access is desired, declare the variable in both the enclosing scope and the inner scope to be global. This solution has the usual disadvantages of global variables: (a) if some other function is called which happens to use the same global variable name for something different, there will be a conflict. One can partially ameliorate this by having 'module-scoped globals', eg each module has its own global variable namespace (we assume that each module is written by one team, and a module's team can take care not to reuse their own names). But this still leaves another disadvantage: (b) you cannot have multiple distinct instances of the same global variable at different points in the call stack; for example, if function 'outer' uses global variable 'g', and then calls function 'inner', and 'inner' then calls function 'outer' again, then this instance of function 'outer' cannot change the value of global variable 'g' without overwriting the old value, which will be seen by the first instance of 'outer'. So global variables really don't substitute for upvariables.
For example, Python's solution is upvalues. At parsing time, Python determines which variable references in an inner scope are upvalues; a variable reference is taken to be an upvalue reference if that same variable is never written to in the inner scope (note that the classification of variables as local mutable vs. upvalues is per-scope; even if a variable is first read from and then later written to, the later write causes this variable to be categorized as a local mutable variable, not an upvalue, even for the earlier read). For first-class functions, upvalues are read at function call time, not function creation time. To see this behavior of Python, consider these examples:
Python example 1:
def outer():
a = 1;
def inner():
print 'inner: %s' % a
a = 5
print 'inner after: %s' % a
f = inner
print 'outer before: %s' % a
a = 2
f()
print 'outer after: %s' % a
outer()
Result:
... ----> 5 print 'inner: %s' % a ... UnboundLocalError: local variable 'a' referenced before assignment
Here, the variable 'a' was written to in the inner scope, causing it to be classified as a mutable local variable at parse time, not as an upvalue. It was read to before it was assigned to, causing a UnboundLocalError? at runtime.
Python example 2:
def outer():
global a
a = 1;
def inner():
global a
print 'inner: %s' % a
a = 5
print 'inner after: %s' % a
f = inner
print 'outer before: %s' % a
a = 2
f()
print 'outer after: %s' % a
outer()
Result:
outer before: 1 inner: 2 inner after: 5 outer after: 5
Here the variable is a module-scoped variable (all globals in Python are really module-scoped 'globals'). It appears to be behaving similarly to an upvariable; but see the next example.
Python example 3:
def outer(x):
global a
a = 1;
def inner():
global a
print 'inner: %s' % a
a = 5
outer(0)
print 'inner after: %s' % a
f = inner
print 'outer %d before: %s' % (x, a)
a = 2
if x:
f()
print 'outer %d after: %s' % (x, a)
a = 20
outer(1)
Result:
outer 1 before: 1 inner: 2 outer 0 before: 1 outer 0 after: 2 inner after: 20 outer 1 after: 20
If this were really an upvariable, and not a global variable, then the 'a = 20' in the recursive call to 'outer' would not have any effect on the caller, because upvariables are lexically scoped, and 'inner' is not an enclosing lexical scope to 'outer'. This example shows the difference between upvariables and global variables.
Finally, the following two examples show that upvalues (not upvariables) are supported by Python:
Python example 4:
def outer():
a = 1;
def inner():
print 'inner: %s' % a
f = inner
print 'outer before: %s' % a
a = 2
f()
print 'outer after: %s' % a
outer()
Result:
outer before: 1 inner: 2 outer after: 2
Python example 5:
def outer(x):
a = 1;
def inner():
print 'inner: %s' % a
outer(0)
print 'inner after: %s' % a
f = inner
print 'outer %d before: %s' % (x, a)
a = 2
if x:
f()
print 'outer %d after: %s' % (x, a)
a = 20
outer(1)
Result:
outer 1 before: 1 inner: 2 outer 0 before: 1 outer 0 after: 2 inner after: 2 outer 1 after: 2
Here, because the variable is a local, not a global, the assignment 'a = 20' at the end of the recursive call to 'outer' had no effect on the caller.
What about dynamically bound variables? (todo a lot of this should be moved out of the implementation section, to the scoping section) How do they differ from upvariables? They differ by whether or not variables not in the local scope are looked for in dynamic scopes (up the call stack; first in the caller, then in the caller's caller, etc) or by lexical scopes (first in the lexically enclosing function, then in the function lexically enclosing that one, etc). For example:
def outer():
a = 3
def inner
print a
return inner
def other():
f = outer()
a = 5
f()
other()
would print 5 with dynamic variables but 3 with lexical upvalues or upvariables. The dynamic answer would be 5 because at the time f() is called, 'a' is not found in f's local scope, so we look up the call stack, starting with the caller, which it 'other'. The lexical answer would be 3 because we would look up the chain of lexical scopes, starting with the enclosing lexical scope, which is 'outer'.
Dynamically scoped variables vs. globals: with dynamically scoped variables, if a change is made to a variable's value, that change is seen by functions beneath the changer in the call chain, but not by functions above the changer. For example:
def outer():
a = 3
def inner
print a
return inner
def other():
f = outer()
a = 5
f()
a = 3
other()
print a
would print '5' followed by '3' using dynamic variables, but '5' followed by '5' using global variables. The 'a = 5' inside other() would not affect the outer scope.
The upvalue approach is also taken in Java [1].
Links:
If a closure can be created, then the values of the variables stored in the closure must be able to persist past the time when the function that originally created the closure returns. Note that this is necessary if continuations other than escape continuations are supported.
The typical implementation of local variables inside stack frames does not suffice for this, because those stack frames will be lost when the function that created the closure returns. One solution is to allocate all 'stack frames' on the heap instead of the stack (this is why a more general term for 'stack frame' is 'activation record'). However, this is slower than using the stack.
Optimizations include static analysis to deduce which activation records need to be created on the heap and which can be placed on the stack.
Another solution is similar to 'upvalues', above; at closure creation time a copy is made of the values of the variables in the closure. In this solution, different instances of the same closure cannot share mutable variable state (unlike typical closures, in which any instance of the closure created in the same calling scope can share upvariable state). This works well with languages with immutable data, such as ML [2].
The term "funarg problem" refers to the design choice of whether and how to implement first-class closures (how to pass around first class functions, or function arguments, which refer lexically to variables defined in the enclosing scope). It is divided into the 'downward funarg problem' (how to pass closures down the call stack) and the 'upward funarg problem' (how to pass closures up the call stack).
https://en.wikipedia.org/wiki/Funarg_problem
https://en.wikipedia.org/wiki/Parent_pointer_tree#Use_in_programming_language_runtimes
http://matt.might.net/articles/closure-conversion/
(see also https://en.wikipedia.org/wiki/Parent_pointer_tree#Use_as_call_stacks )
https://en.wikipedia.org/wiki/Trampoline_%28computing%29#High-level_programming
https://en.wikipedia.org/wiki/Tail_call#Through_trampolining
todo
http://akkartik.name/post/swamp
https://en.wikipedia.org/wiki/Continuation-passing_style
todo
" This style adds an additional item to each function call (you could think of it as a parameter, if you like), that designates the next bit of code to run (the continuation k can be thought of as a function that takes a single parameter). For example you can rewrite your example in CPS like this:
(defun f (x y k) (a x y k))
(defun a (x y k) (+ x y k))
(f 1 2 print)
The implementation of + will compute the sum of x and y, then pass the result to k sort of like (k sum).
Your main interpreter loop then doesn't need to be recursive at all. It will, in a loop, apply each function application one after another, passing the continuation around. " -- http://stackoverflow.com/a/5986168/171761
another example: " Direct style
(define (pyth x y) (sqrt (+ (* x x)(* y y))))
CPS style (k is the continuation)
(define (pyth& x y k) (*& x x (lambda (x2) (*& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k)))))))) (define (*& x y k) (k (* x y))) (define (+& x y k) (k (+ x y))) (define (sqrt& x k) (k (sqrt x))) "
" The main interest of CPS is to make explicit several things that are typically implicit in functional languages: returns, intermediate values (= continuation arguments), order of argument evaluation...
Like for SSA, the main interest is to ease optimizations. Theoretically, SSA and CPS are equivalent: a program in SSA form can be transformed into a CPS program and vice versa.
Previous program can be rewritten as: x2=x+x y2=y*y x2py2=x2+y2 res=sqrt(x2py2) " -- http://www.montefiore.ulg.ac.be/~geurts/Cours/compil/2014/05-intermediatecode-2014-2015.pdf
https://en.wikipedia.org/wiki/Threaded_code
see also [3]