(This is a post for CS320 Boston University.)
In order to discuss environments, closures and functions, I would like to discuss free and bound variables first.
Take this as an example
lam (x) => x + y
Here we call
y occurrences (of
y). The first
x is called a binding occurence of
x, the second
x is called a bound occurence of
x, and the
y is a free occurence.
x in the argument list is like to decalre a name for the placeholder, and then the
x in the body will become a placeholder. Whenever such anonymous function get called with a parameter, all the placeholder
x will be replaced (or actually, bound) by the actual paremeter value. However, the
y is not defined in the argument list, thus it is not treated as a placeholder. However I call this anonymous function,
y won't have a concrete value. It is not bound, it's free.
fun add (x:int, y:int): int = x + y
Here, all the occurrences of variables in the body are bound, while those occurrences in the argument list are binding occurrences.
fun addclo (x:int):<cloref1> int = x + y
While here the
y in the body is a free occurrence.
Environments and Evaluation
When the interpreter evaluates a program, it needs to know the values of variables. Suppose I call
addclo with parameter
- Interpreter sees the binding occurrence of
x, therefore it binds
x, which is actually putting a key/value pair
(x,123)into the environment.
- Interpreter then evaluates the body. When it sees the bound occurence of
x, it looks up the environment, and replace it with
- When it sees the free occurence of
y, or we say it can't find a binding of
yin the current environment, it will take further actions.
- It either reports an error, and stops evaluating.
- Or continues to look up
yin a parent scope (if
yis defined somewhere outside this function).
We can see that a free variable may appear locally, but in a correct program, all variables have to be bound eventually.
Functions and Closures
In a function, every local variable has to be bound. This means every variable should have at least a binding occurence (either in the argument list, or in the body), and probably several bound occurences.
Closure is actually a function, plus an environment. The current environment is recorded by the interpreter when it first sees the definition of a closure. Later when it starts to evaluate the application of a closure, it will retrieve the original environment, and evaluate the closure application under it. We need the environment, and there is a reason.
In a closure definition, variables are not required to be bound (in its defining scope). But as we mentioned, it has to be bound somewhere else in order to be evaluated. Look at this.
implement main0 () = let val y = 1 fun addclo (x:int):<cloref1> int = x + y val z = addclo(123) in () end
Here, when the interpreter sees the definition
(y,1)into the environment).
- Record the definition of
addclo. That is to put the function/environemnt pair into a table. The environment contains
- It sees a closure application.
(addclo, env)from the table
xis a bound variable, it is bound to
123because of the binding occurrence of
xin the argument list.
yis bound to
1according to the
env, which is the environment when we define
124(123 + 1), and bind it onto
As you can see, if the closure is not accompanied by its environment, we will never know the value of
y. However, since all variables are bound in a function, it does not need to be accompanied by an environment.