Binding time analysis
So we want to have a couple of scopes:
- global scope
- function scope
- local scope
Next to that (regarding variable names):
- local variables hide (shadow) function arguments and global variables
- function arguments hide (shadow) global variables
- variable names can have the same name as function names
Global scope
At the top of the program, we can define variables that can be used everywhere in the program.
Function scope
Function arguments can be used everywhere in the body of that function.
Local scope
Variables defined at the top of the function body can be used everywhere in the rest of the function.
Environments
It seems necessary to introduce a concept of an environment (or 'namespace', but I find 'environment' a better term):
- functions environment
- variables environment
We keep track of all the defined functions in the functions environment. Since the grammar forbids recursive function definitions, this environment (FunEnv
) can be reached from all points in a program.
The variables environment (VarEnv
) can take different forms depending on the current position in a program. In the global part of a program (Decl+
) it should contain all VarDecl
s. In some function (FunDecl
) the variables environment is backed up, and the environment is duplicated. In the duplicate (VarEnvFun
for clarity), the environment is changed according to the following rule:
- Function arguments with the same name as an existing global variable overwrite that existing global variable (effectively masking the variable in
VarEnv
).
In the function body, the same happens. We keep the VarEnvFun
and copy it to a new instance: VarEnvBody
, for example. Then the following rules are followed:
- Local variables with the same name as function arguments overwrite those function arguments (effectively masking the variable in
VarEnvFun
) - Local variables with the same name as global variables overwrite those global variables (effectively masking the variable in
VarEnvFun
).
In the function body, the variables environment used is VarEnvBody
. This contains all variables with the correct scope.
After the function ends, we discard VarEnvBody
and VarEnvFun
, continue to the next function with the original VarEnv
and repeat the above process.
Binding time analysis
Now we have two environments that contain all the information needed about a program at any time. The only thing left to do is to check in which scope we are and use the corresponding environments:
- global scope
FunEnv
VarEnv
- function scope
FunEnv
VarEnvFun
- local scope
FunEnv
VarEnvBody
We can then simply check at each declaration whether the environment accepts that declaration (i.e. use of defined variables, defined functions).