Although I don’t really have to worry about the allocation of memory and tracking of memory addresses to implement a stack, These explanations are giving me some ideas for how I could build a call stack-like structure.
I’m seeing a lot of answers about how the stack frame is formed, but one point I’m still trying to figure out is, how does the caller know which non-parameter local variables need to go on the stack for the instruction code. Where is this information stored in a compiled language? I can see that in PunyPy, we have the World object for globals, but as I implement local scope using the World model, I realize that communicating between the World and the function caller is a mystery to me!
Where ‘all the code’ goes in memory…
And these are related to my question about the local static variables that are copied into the stack frame during a function call after the parameters.
This next SO thread reveals there is dispute over whether or not static variables declared within functions are initialized at program startup, or when the function is invoked and the particular line of code executed.
From this last Stanford pdf handout, I’m making the connection that the World class in this PunyPy interpreter stores what might be called the ‘prototype’ for the function. That is, it stores names of all the declared variables in the function without actually allocating or initializing them (unless they are static variables, in which case, their value is determined before run time). Here’s an excerpt about an activation record (stack frame) protocol:
Activation Protocol
The code generated by the compiler must implement some consistent protocol for
passing control and information from calling function to called function and back.
Different languages and even different compilers within a language may use slightly
different protocols. Most protocols depend on the caller and callee having access to a
"prototype" description of the interface of the routine.
A protocol also needs to specify the general arrangement of space in an activation
record. We are going to choose a very simple arrangement for the ease of our
discussion. In our protocol, parameters will be pushed on the stack in right-to-left
order, (there is an important reason why it must be right to left for any C compiler
which we will learn later), followed by the saved return address, and then the local
variables in top-to-bottom order. We’ll assume that the return value from the
function won’t be placed on the stack, but instead will be written in the special register
RV. Note this won’t allow for return values that are larger than the word size of the
machine, but usually those are handled in a complicated (and often somewhat
4
expensive) way which we won’t be interested in. As is true on most current
architectures, the activation stack will grow downward, from higher addresses down to
lower. Given the Simple function declaration from page 1, here is its activation record
layout:
activation record of calling function:
* b
* a
* saved PC (return address)
* temp1
* temp2 <—"Top" of stack (Stack Pointer or SP)
Given the arrangement of parameters and local variables in our protocol, we can think
of an activation record as similar to 2 neighboring structs, one for the local variable
block and another block for the parameter, with the saved return address in the middle.
The SP is pointing to the base address of the local variable block, the return address
follows, and the parameter block begins right after that.
Given the arrangement of parameters and local variables in our protocol, we can think
of an activation record as similar to 2 neighboring structs, one for the local variable
block and another block for the parameter, with the saved return address in the middle.
The SP is pointing to the base address of the local variable block, the return address
follows, and the parameter block begins right after that.
struct SimpleActivationLocal {
int temp2; // offset 0 (from SP)
int temp1; // offset 4
};
struct SimpleActivationParameters {
int a; // offset 12 (from SP)
int b; // offset 16
};
In compiled code, each function refers to its local variables and parameters by their
respective offsets from the end of the stack. For example, in the Simple function, the
parameter b is an offset of 16 bytes from the stack pointer. Notice that:
•The protocol allows the compiler to generate code without knowing exactly
where the activation will actually end up in memory at runtime. All variables
are identified via their address, which is always the value in the SP, plus the
relevant offset.
•The code works equally well for any activation of that function.
• No trace of the actual identifiers used in the source is left in the code. The type
information for any particular variable is not explicit in the code, but is implicit
in the operations the compiler generates to work on that data.
So what I’m trying to figure out is, "Where, when and how this “prototype” for the local variables derived from the function definition?"
TODO: I can definitely go on with my interpreter without the answer to this question, but I’m really curious to know. Before I continue searching for the answer, I need to change the World’s children attribute from a list() of child worlds, to a dict() of child Worlds where the key is the function name. Then the function call will copy the world stored with the key to the FuncDef’s ‘call’ method. The FuncDef or the World will need a method for ensuring that symbol lookups will search back through some kind of call stack.
I CAN DO THIS!!!
Ok… I couldn’t help myself. I’m pretty sure that this Princeton lecture pdf has the best explanation of how local variables are handled in the compiler. (An article from the Many Finite blog is a more verbose explanation of topic). The professor takes a simple function in written in C, calls it and then goes through the disassembled code step-by-step. From what I can tell, the local variables are created dynamically. ie, they are not declared at compile time. Rather, they are declared at the time the callee’s block of code is executed. I suppose it’s possible that some compilers perform this step ahead of time, but from the disassembled code in the lecture slides, I can’t see that it happens in this particular instance.
What does this mean for my PunyPy? I get the feeling that this is where Python differs from C. From what I’ve read about Python code execution, the analyzer does indeed keep a record of all the local variables before code execution. Somehow, the caller passes this record from to the callee and the that creates a local symbol table before the local code executed That step probably happens in the analyzer, or maybe the interpreter when the code block is entered… This is why we see ‘variable referenced before assignment’ errors from the interpreter.
That’s another thing. From what I can remember, the Python interpreter only invokes these “declaration heads” one the block is actually invoked. For example:
def func(x):
if x == 1:
r = None
return "BASE CASE"
else:
s = func(x-1)
q = 5
print(q)
return q
print(func(3))
In this recursive function, ‘r’ will not be declared until we recurse to the point where the base case is evaluated True. That means it will not appear in any kind of symbol table for the func() in either the analyzer or the interpreter until that particular function call occurs. Similarly, ‘q’ and ‘s’ will only be allocated for calls where the base case is not met.
I have a sense that contrasts to what I read about C: all functions must be defined globally, but internally they have local scope at run time.
So now what? My interpreter will be a mix of the two, i.e. functions can be defined within another function’s definition scope, but the internal variables will be declared in the symbol table while the function/block code is being executed line-by-line (specifically, at variable assignment).
The discussion of ‘lexical scope’ is really complicated by the fact that in Python, variable declaration happens at assignment.
>>> x = "global x"
>>> def hello():
... x = "local x"
... return x
...
>>> print(x)
global x
>>> print(hello())
local x
>>> print(x)
global x
In Python, the ‘hello()’ assignment of x instantiates a local version automatically without seeing the global x. Declaration is implicit.
I guess that in another language (possibly in C), the x referenced in ‘hello()’ would point to the global x because x wasn’t explicitly declared in ‘hello’. Declaration must be explicit to be in local scope. Maybe that’s where C might check the previous stack frame to see if the variable was declared there. Or, if there’s a global table, it might check the global table… not sure how name collisions would be handled for recursive calls though. C doesn’t have namespaces or anything, so I’m guessing it’s (un)masking name visibility through the call stack.
Man, I really wish I could have time to learn C, but right now I need real job skills (javascript)! My dream is to one day study computer science in school. I really enjoy this stuff!
Here’s another tutorial with C code and its disassembled instructions.
This one is interesting because it’s from the perspective of a security exploit: the buffer overflow.
This comment on SO makes an important point about the difference between activation records and stack frames. Although a stack frame is a kind of activation record, activation records can be implemented without a stack based memory structure. They’re ‘platform specific’.
When we call function, we need someplace to store callers and callees’ context, this place is called activation record(AKA stack frame).
Yes, activation records compose call stack, however, that doesn’t mean activation records must be stack-based. It is implementation specific.
This archived page explains the conflicting meanings of the word ‘static’ and goes into detail of its particular significance in C++
https://web.archive.org/web/20100328062506/http://www.acm.org/crossroads/xrds2-4/ovp.html
Here is a video from UofT covering the basics of how Python handles the stack during function calls.
I like this one because it’s specific to Python and the narrator takes care to accurately describe actions like assignment.
edit: PYTHON SCOPE REVELATION!
I’m running experiments on function scope in Python. These tests are modelling the kind of semantics I’d like to see in my interpreter.
Here I’m trying to see if the value of x is determined when the function is defined or when it is called.
>>> x = "global"
>>> def hello():
... print("hello x:", x)
...
>>> def caller():
... x = "caller"
... hello()
...
>>> caller()
hello x: global
So it looks as though the value is established when the function is defined. This is static scope and I think implementation will be a little difficult. It means that I have to go back to my analyzer and change how the visitor methods work for function definitions.
Next, I’m going to verify how function calls like “input()” affect scope.
>>> def hello():
... print("hello x:", x)
...
>>> def caller():
... x = "caller"
... hello()
...
>>> x = input()
"global after def"
>>> caller()
hello x: "global after def"
>>> del x
>>> caller()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in caller
File "<stdin>", line 2, in hello
NameError: name 'x' is not defined
Ok here we go. Now it’s clear that even though the ‘caller’ environment has a local ‘x’ variable, the ‘hello’ always scopes out to the environment where it was defined, ie ‘global’. Once ‘x’ is deleted from the global scope, ‘hello’ throws an exception.
Now I’m going to see what happens to the scope when the function defining environment is a recursive function itself.
######SCRIPT:
#!/usr/bin/env python3
def recursive_caller(x):
if x == 1:
print("BASE CASE x ==1")
else:
caller_level = 4 - x
print(f">>>ENTER caller level:{caller_level} x:{x}")
def hello():
print("hello x: ", x)
hello()
recursive_caller(x-1)
print(f"<<<EXIT caller level:{caller_level} x:{x}")
hello()
recursive_caller(3)
###OUTPUT
>>>ENTER caller level:1 x:3
hello x: 3
>>>ENTER caller level:2 x:2
hello x: 2
BASE CASE x ==1
<<<EXIT caller level:2 x:2
hello x: 2
<<<EXIT caller level:1 x:3
hello x: 3
So, when the calling environment is recursive, each variable is ‘stacked’ according to its recursion depth. This means that I need to stack values in the symbols/variables dict of the World object.
After reading about the stack, I thought I was ready to go, but that would’ve resulted in a dynamically scoped language. I might still implement a call stack-like structure for managing return values from function calls, but my scoping will use lists the way I described above.
That’s the thing about theory… it’s easy to think I understand a concept by just running the model in my head (EDIT: or in the case of my interpreter, on paper). However, if I want to use a concept to solve a big problem, I’d better first implement that concept in the simplest possible scenario to reveal its fundamental constraints and parameters.
1 Like
idea: scrap nested/tree structure for World object scope representation. See about going back to a centralized function dict and using a hash table to give each instance of a function definition its own unique lookup. I believe this would make a stack-like structure unnecessary for the function definition’s representation.
I think it would be something like how this page describes hash tables for implementing scope.
Among all, symbol tables are mostly implemented as hash tables, where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.
A hash table might be most practical way to implement static scope.
More experiments with scope:
Judging by these tests, variable scope in regards to assignment and expression is complex.
This test passes x as a parameter:
>>> def sub1(y):
... x = y - 1
... print("sub1 x: ", x)
...
>>> x = 3
>>> sub1(x)
sub1 x: 2
>>> x
3
>>>
The parameter, ‘y’ passes the value of global ‘x’ (evaluating as a local ‘y’ with value 3) to the function ‘hello’. The function body of ‘hello’ assigns the value 2 to a local symbol which is also called ‘x’.
Here’s a variation without the parameter, ‘y’. The function, ‘sub2’ can’t see a local ‘x’ in its table, but it has no problem evaluating ‘x’ based on the value of ‘x’ from the caller’s scope.
>>> def sub2():
... print("sub2 x: ", x)
...
>>> def sub2():
... print("sub2 (x-1): ", x - 1)
...
>>> x = 3
>>> sub2()
sub2 (x-1): 2
>>> x
3
Here’s another example where an expressions in an assignment statement follows different rules than unassigned expressions. Assignments must evaluate all variable expressions
>>> def sub3():
... y = x - 1
... print("sub3 x pre-assignment: ", x)
... x = y
... print("sub3 x post-assignment: ", x)
...
>>> x = 3
>>> sub3()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in sub3
UnboundLocalError: local variable 'x' referenced before assignment
I think this point will be very important to implementing static scope.
>>> def sub4():
... y = x - 1
... print("sub4 y: ", y)
...
>>> x = 3
>>> sub4()
sub4 y: 2
In assignment, the expression side always checks the local scope first. If the variable name is declared at a point after the assignment, the assignment will fail because the analyzer will analyze the entire block before the interpreter evaluates the expression side of the assignment statement.
This is further complicated that there is a del() keyword which supposedly removes a variable from the symbol table. I don’t know what kind of structures I can use to solve this. I found an interesting article about python internals, starting with the symbol table.
https://eli.thegreenplace.net/2010/09/18/python-internals-symbol-tables-part-1/
I’ll check this out and see if I can run some more tests based on what I might learn.
The word of the day is closure.
CLOSURE
I’m pretty certain Zed implements a variation of this idea in his solution by copying the environment variables into a new world, but I didn’t understand the details of it when I first read them.
Video on implementing variable scope
This…
From what I’m hearing, when a function is defined, it is stored as an instance of itself and a snapshot of its nesting environment at the moment the function was defined. This is what is known as a closure. It’s a combination of a function and the function’s environment variables.
Questions:
-
Doesn’t copying the entire environment for each function definition require a lot of memory overhead? I’ll start with that method, but I imagine there’s a better way.
-
Do all the variables in any expressions or statements in the function definition need to be evaluated before being stored in the table, or is it enough to just store them together and perform the evaluation at run time? I would guess the latter. However, it might be wise to have each variable expression be able to ‘see’ itself in the environment during analysis.
Anyhow, the really fascinating thing about this video is that he’s saying to use the same data structure (environment, code) within the local table of the closure itself to support recursion (so the closure can call itself).
TODO: The visitor method for FuncDef must store the function definition along with a copy of the current environment as a unified data structure in the enclosing function’s symbol table. Have a look at Zed’s interpreter solution to see how he copies the environment and see if anything needs changing to better emulate python semantics.
Then, the function call will copy the call’s arguments to the definition’s parameters and establish a return value pointer/reference (whatever… I don’t know c). Finally, the function definition will copy its own locals from the environment with which it was bundled before evaluating itself and returning a value.
IDEA:
Analyzer stage… Instantiating closure… Gather all local and nested expression-variable names by creating a local symbol table and passing it around to any nested function definitions so that all nested variable names also get included in the local symbol table. This operation happens in a chain that goes deeper into all nested functions. Each nested symbol table should get smaller (fewer elements) as the nesting goes deeper.
Function calls run the closure by first passing the environment symbol table to the function’s call method. Then the function arguments are copied to the parameters (not sure if this is analyzer or interpreter stage)
Interpreter stage: assignment starts by evaluating the expression, then overwriting the value in the local symbol table as well as within any nested symbol tables all the way up parse-tree branches.
I read this interesting slide from a lecture on the role of symbol tables in semantic analysis.
Generally, symbol table is only needed to answer those two questions,
i.e., once all declarations have been processed to build the symbol
table, and all uses have been processed to link each ID node in the
abstract-syntax tree with the corresponding symbol-table entry, then
the symbol table itself is no longer needed, because no more lookups
based on name will be performed (In practice, symbol table often
keeps through the entire compilation and sometimes even beyond)
I The process of building symbol table, you are able to check the
scoping rules
So the symbol table is meant to be thrown away after semantic analysis. What about the functions’s environment? Is that only built at run time?
I am really enjoying this series of articles. It answers my questions about the semantic analyzer stage and symbol tables.
https://eli.thegreenplace.net/2009/11/28/python-internals-working-with-python-asts
https://eli.thegreenplace.net/2010/09/18/python-internals-symbol-tables-part-1/
https://eli.thegreenplace.net/2010/09/20/python-internals-symbol-tables-part-2
https://docs.python.org/3/library/symtable.html
https://eli.thegreenplace.net/2012/03/23/python-internals-how-callables-work
I also found the Execution Model summary from the official Python 3 docs. It explains naming, binding and name resolution. It seems as though non-local variables used in a code block are considered ’free’ variables. I don’t know where that information about the variable’s scope comes from. I’m guessing it’s during analysis, and then maybe the entry symbol table is used by the interpreter to know what kind of action to perform for the variable lookup. Blahdeblahblah.
Here’s an example of how free variables work in python.
4.2.4. Interaction with dynamic features
Name resolution of free variables occurs at runtime, not at compile time. This means that the following code will print 42:
i = 10
def f():
print(i)
i = 42
f()
The eval() and exec() functions do not have access to the full environment for resolving names. Names may be resolved in the local and global namespaces of the caller. Free variables are not resolved in the nearest enclosing namespace, but in the global namespace. [1] The exec() and eval() functions have optional arguments to override the global and local namespace. If only one namespace is specified, it is used for both.
This was a startling read. I tested the code myself and I think this is a feature that is particular to Python. Function definitions are not inserting themselves as closures in the symbol table as I had learned from watching videos using functional languages. The local values for the enclosing block are not being copied into a snapshot which is stored with the function code.
This is actually a relief. It means that we only need one instance of each symbol table and that the names of the free variables are allowed to point directly to their entries in the enclosing block’s symbol table. I’ll illustrate with this example.
script:
#!/usr/bin/env python3
# this test illustrates how free variables point to table entries from the enclosing scope
# rather than copying the values from in the environment into their own local symbol table
def caller():
x = "caller's x BEFORE def hello"
def hello():
print(">>>hello x: ", x)
print("CALLER:hello()")
hello()
x = "caller's x AFTER def hello"
return hello
print("GLOBAL: glo_hello = caller()")
glo_hello = caller()
print("GLOBAL: glo_hello()")
glo_hello()
output:
GLOBAL: glo_hello = caller()
CALLER:hello()
>>>hello x: caller's x BEFORE def hello
GLOBAL: glo_hello()
>>>hello x: caller's x AFTER def hello
HAHA! So now it’s clear. There is no ‘snapshot’ of the values in the function definition’s enclosing environment. If the value of x changes after the definition is made, the free x within the enclosed function will reflect that change.
I think you’ve really found your interest in CS Austen. In fact, learning how to implement languages is probably the only thing I consider “core” to CS. Nearly everything else changes and is kind of based on hand wavy “logic” while languages seems to be rather solidly based, especially parsing. About the only part of languages that is total BS would be the type theory folks and their abuse of abstract algebra to justify making the . work like it’s some kind of “math”.
1 Like
Thank you for the validation! I’ve had a chance to look at some academic papers on elements of language design and I have to say, reading that stuff is very humbling. I have absolutely no idea of what’s going on. Nevertheless, I hope that one day I can put my limited understanding to practical use.
I did this test where the nested function definitions referencing free variable, ‘x’, are stored in an accumulator.
I wanted to see what would happen if the enclosing recursive function had a chance to spit out a nested function object from multiple recursion depths. I figured an accumulator would let me call all those returned functions from the global scope. The output demonstrates that, even though the free variable ‘x’ always refers back to the ‘env_func’ scope, free variable ‘x’ has multiple values depending on the recursion depth of ‘env_func’.
#!/usr/bin/env python3
# This script tests lexical scope where a function, 'env_func', recursively
# stores a function object, 'free_func', in an accumulator. 'free_func' prints a
# free variable, 'x'.
# recursive function for enclosing scope
def env_func(x, acc):
if x == 1:
return
else:
def free_func():
# 'x' is the free variable within free_func
print(f"free x == {x}")
# push definition onto accumulator
acc.append(free_func)
env_func(x-1, acc)
free_func_accumulator = list()
env_func(5, free_func_accumulator)
# call each definition and display value of free variable 'x'
for i in range(len(free_func_accumulator)):
print(f"free_func_accumulator[{i}](): " )
free_func_accumulator[i]()
Output:
free_func_accumulator[0]():
free x == 5
free_func_accumulator[1]():
free x == 4
free_func_accumulator[2]():
free x == 3
free_func_accumulator[3]():
free x == 2
It looks as though I’ll need to stack the symbol table values after all.
I’m back with a facepalm moment.
This week I rewrote my analyzer. I was thinking through the structure to support recursive lexical scope. After some testing and debugging, I think I’ve got it in a rudimentary form. There’s only one problem… my language doesn’t have condition statements or cases with which to test the recursion, much less make it useful. Hahahahahahaha. The best I could do is print out values from each call of the recursive function before it finally raises a “maximum recursion depth exceeded”
So now I have to see if it’s a big deal to implement conditions or if I should just move on with the interpreter and forget about doing a proper recursion implementation
Oh well. At least I should be able to implement local scope for function calls.
…getting warmed up…
I’m definitely skipping control flow so I can get this project wrapped up.
Now my head is spinning with how to interpret function definitions and function calls!
Here’s what I’m imagining:
- Take the existing world_stack from the analyzer and begin traversing the AST (parse-tree).
- When the function definition is encountered, skip it! It should have already been declared in the enclosing scope during the analysis phase.
- When the function call is encountered grab the function’s ‘AST-scope’ tuple from the symbol table
- The function call pushes a world/frame onto the function’s internal scope and invokes the FuncDef’s run() to initialize all the variables.
- The function call then copies all the arguments to the function’s local symbol table by finding corresponding FuncDef parameters for each FuncCall argument.
- The function call then passes the local scope/world to the FuncDef’s ‘call()’ method and the code is executed, assigning values to the variables.
I have intentionally left out an implementation of ‘return value’ to keep function calls as simple as possible.