Closure

After delving into the article and exploring other resources on closures, I feel compelled to jot down my thoughts here to solidify my understanding. The design proposal for closure is primarily derived from the article to which I refer.

1 Terminology

Some terms are described here before we proceed to the next section.

A declaration is used to inform the compiler of the existence of an entity. This entity can be a variable, function, class etc. The name of the identifier in the declaration identifies that entity.

Due to space limitations, we focus on the variable entity as an example in this section. BTW, in languages with first-class functions, functions are treated like ordinary variables with a function type.

A variable is an abstract storage location which stores a specific type of data (such as integer, float, string, etc.) typically referred to as value. Variable name is commonly used to access that value. This is achived eventually by compiler translating variable name to the corresponding data’s location.

int x = 1;      // A variable named **x** is declared.
int get()       // A function named `get` is declared.
{
    return x;   // A use of x
}
int main()      // A function named `main` is declared.
{
    int x = 2;  // A variable named **x** is declared.
    get();
    return x;   // A use of x
}

In the above case, the use of x appears at line 4 and line 10 respectively. Which entity declared does x in each use refer to? In other words, how do we correctly resolve/bind the name to an entity? Scope rules are used to determined whether a name binding in a particular part of a program is valid or not.

Scope has two categories:lexical/static scope and dynamic scope.

• Lexical/static scope means a name binding can be determined at edit/compile time by the program text only and is typicalliy known as early binding. Under static scope, x at line 4 generally references to the entity declared at line 1 and x at line 10 references to the entity declared at line 8.
• Dynamic scope means a name binding can only be determined at runtime and is known as late binding. To acheive that, a name lookup upward to the call stack is often needed. Under dynamic scope, x at line 4 and line 10 generally references to the same entity declared at line 8.

A local variable is a variable declared within a given local scope such as function scope and block scope. It creates during the execution of that scope and is visible until the execution flow leave that scope.

A automatic variable is a local variable which is preserved on the call stack and thus features being allocated/created and deallocated/destroyed automatically when the scope is entered and exited. In most languages, automatic variable and local variable are used interchangeably.

The static local variable in C languages is an exception. A static local variable is visible only during each exection of that scope but has an application-wide lifetime.

Under the call-by-value semantics, a function parameter is a new local variable declared in the function scope with initial value copied from a corresponding argument.

Free variable and bound variable are concepts originated from mathematics and extended into the computer programming. The exact term definition is as follows:

The term free variable refers to variables used in a function that are neither local variables nor parameters of that function. The term non-local variable is often a synonym in this context.

In article, they are defined as follows:

Bound variables are declared within the scope. They are parameters and local variables.

Free variables are declared externally. They are also called non-local variables.

In the subsequent sections of this article:

• A scope is lexical/static.
• A function call is with call-by-value semantics.
• A parameter thereby is a local variable.
• A local variable is synonymous with automatic variable.
• A function is treated as an ordinary variable.

2 Closure Concept

function outer() {
    let cnt = 0;
    function inner() {
        return ++cnt;
    }
    cnt = 2;
    return inner;
}
let inn = outer();
console.log(inn());
console.log(inn());

A regular/plain function operates strictly within its lexical scope and cannot access local variables in enclosing functions.

If we consider inner as a regular/plain function, an error will occur during compilation. This is because local variable cnt is declared and defined within the lexical scope of outer function rather than that of inner function.

A function featuring this capability of accessing to local variables outside its own lexical scope is referred to as closure. We refer to such local variable as closed-over or captured variables. For instance, the cnt variable.

In wikipeida, closure is describled as follows:

A closure is a record storing a function together with an environment.The environment is a mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created.

In another book, it is defined as follows:

A closure is a function plus a connection to the variables that exist at its “birth place”.

In the following sections, a function is treated as a closure at runtime even it never access free variables.

3 Closure Design

A local variable typically cannot outlive the immediately enclosing scope. In the program text, the variable cnt arises at line 2 and available to use until the closing curly at line 8. At runtime, local variables are typically allocated on the stack. Once the outer function execution finishes, cnt’s stack memory will be automatically reclaimed through the process of stack pointer adjustment.

So, how does the inner closure at runtime still retain valid access to cnt even the outer function execution finishes?

To provide a comprehensive solution to this question, let’s explore a broader scenario:

function outer() {
    let cnt = 0;
    function middle()
    {
        function inner() {
            return ++cnt;
        }
        return inner;
    }

    cnt = 2;

    function dec()
    {
        return --cnt;
    }
    dec();
    return middle;
}

let mid = outer();
let inn = mid();
console.log(inn());
console.log(inn());

outer function is declared at line 1 and called at line 21. During the call to outer, three local variables cnt, middle and dec come into being. According to the program text, cnt is captured by inner and dec.

As we mentioned above, cnt is valid only during the execution of outer. dec closure is created at line 13 and at that time, cnt is still available. We can preserve cnt into dec closure and then the cnt will be always available for dec closure no matter when it is called in the future.

However, middle is never called during the execution of outer, leading to inner yet-to-be-created. The question arises: how does inner access a valid cnt when it is created by the call to middle somewhere in the future. It naturally comes to mind that preserving cnt into inner’s immediatedly enclosing function middle which even never use it. Data preserved into a closure’s immediately enclosing function must be available at least until the closure is created. Therefore, function middle thus will be created as a closure used to preserve the variable cnt captured by its nested function inner.

One question arises: should we preserve the value of the captured variable or the reference to that variable? The choice between preserving value or reference depends on the semantics regulated by the language specification.

If a closure stores the value of a captured variable, then it means the closure contains the value copy of that variable. Any operations performed on the variable within the closure will not impact the value of original variable declared in the enclosing function. Additionally, these operations will also not affect the value of the same variable captured in others closures if any.

If a closure stores reference to a captured variable, it can be understood as that variable’s storage location. This implies that at any given time, the value to which the variable name is bound has only one instance and no other copies in the memory, and any changes made to that variable either in the enclosing function or in other closures will be reflected to that singular instance and visible to all uses of that variable.

In this article, we will focus on discussing the latter case.

function outer() {
    let cnt = 0;
    cnt = 2;
    return cnt;
}

If outer contains only above three lines of code, it’s ok to allocate cnt on the stack and deallocate it automatically once the outer execution finishes. In this example below, however closure middle and dec will preserve the reference to cnt and the reference preserved should be valid even after the outer exectuion finishes.

function outer() {
    let cnt = 0;
    function middle()
    {
        function inner() {
            return ++cnt;
        }
        return inner;
    }

    cnt = 2;

    function dec()
    {
        return --cnt;
    }
    dec();
    return middle;
}

let mid = outer();
let inn = mid();
console.log(inn());
console.log(inn());

PS: To facilitate viewing, the example shown before is copied here.

One approach is to create every declared local variable directly on the heap and preserve the reference to it into middle and dec. The approach sounds promising but it has one significant shortcoming: performance degradation. It triggers dynamic allocation on the heap for each local variable at their birthplace which comes at a non-negligible price.

Furthermore, whereas all uses of cnt in the scope of outer were previously implemented by directly accessing its value on the stack with an index calculated at compile time. By this approach, we need first to obtain its reference on the stack with an index calculated at compile time. And then retrieving its value by dereferencing it. This obviously requires more operations compared with the old way.

cnt is captured by closure middle and dec which may access cnt outside its enclosing function. Moving cnt from stack to heap thereby is inevitable but we can minimize the performance degradation by delaying the moving until the cnt is about to go out of the scope,i.e., at the end of its enclosing function outer. When middle and dec are created in outer, we preserve the reference to cnt on the stack into these two closures. We move cnt to heap and update the preserved reference in these these closures merely before the execution of outer ends. Then, the way code accessing the captured value in the enclosing scope will remain unchanged, i.e. getting the value from stack directly.

By the way, there is an optimisation opportunity: we can determine whether the closures will outlive their immediately enclosing function at compile time by performing escape analysis. If all closures that capture the cnt have the same liftspan as cnt, then there is no need to move cnt at the end of outer. In this example, dec has the same lifespan as the cnt but middle does not. middle escapes the enclosing function outer by being returned. Therefore we need to move cntfrom stack to heap but only update the preserved reference in the middle closure.

Due to the constraints of space limitations and one-pass parser’s simplicity, we do not implement such analysis and at runtime we treat all functions as closures. In this article, we adopt the way to move a captured variable at the end of its immediately enclosing function and update preserved references in corresponding closures.

4 Closure Implementation

Compiler and Runtime should conspire together to make the above mechanism eventually happen. Let’s dive into that example again. To facilitate viewing, the example shown before is copied here.

function outer() {
    let cnt = 0;
    function middle()
    {
        function inner() {
            return ++cnt;
        }
        return inner;
    }

    cnt = 2;

    function dec()
    {
        return --cnt;
    }
    dec();
    return middle;
}

let mid = outer();
let inn = mid();
console.log(inn());
console.log(inn());

At line 1, a global variable outer is created with type of closure. outer references no captured variables.

And then outer is called at line 21. Let’s take a closer look at the outer function. Local variables cnt and middle is created at line 2 and line 3 respectively.

At compile time, compiler easily know how many variables the middle closure need to capture. In this example, only 1. At line 3, the code emitted by compiler will create a closure object for middle on the heap. It contains an array with length of 1 which is also allocated on the heap. The array is used to build connection to captured variables for the closure middle.

And then the compiler need to emit code to initialize the array to make sure each element in that array references to right variable. The emitted code create an object on the heap at runtime and set its location to the array element indexed at 0. The object represents a captured variable shortly called UpValue and will be filled with the location of that captured variable. It serves as a middle layer providing indirection access to the genuine entity of that variable. middle closure accesses cnt through this object no matter where it is moved in the future. At this moment, the captured variable cnt is still available on the stack and compiler knows its exact stack location because the location at runtime and compile time matches. The compiler thereby emits the code to get the stack location and set it into the UpValue object.

At this moment, the memory will looks like this below. Current Runtime Status

By the way, inner closure will be created at line 5 each time middle is called. And then the code emitted by compiler will initialize that array owned by inner. It will copy the location of that UpValue object not from stack but from first element of middle’s array to the first element of inner’s array. We will get to it later.

At line 11 cnt = 2;, the access to cnt will remain the same as that to other local variables not captured. i.e. compiler emits the code to assign 2 to cnt pointed by fp plus index 1. The outcome sees below.

Current Runtime Status

Closure dec is created at line 13. It captures the cnt as well. If we conform to these steps we describe above, it will also create an UpValue object and form the status below.

Current Runtime Status

It looks redundant. We maintain two UpValue objects which refer to the same entity. To avoid this, we need to check if there already exists an UpValue object refer to the same entity or not. If yes, we just use that one instead of creating a new one to populate the up_value_array. The ideal way looks like this below.

Ideal Runtime Status

So how to check that? if the cnt also contain a reference to the UpValue object, then we can easily check that at runtime. But it will make the Value structure cumbersome. In this article, a vm global variable openUpValues is created and used to thread all the UpValue objects which still refer to entity on the stack. And each time a new UpValue is to be created to reference a value on the stack, the UpValue objects threaded by openUpValues will be checked. If a UpValue object contains the location of that value on the stack, then it is our target UpValue object and there is no need to create a new one. The check process should be also applied to the middle creation. To support this idea, we need to add extra field named UpValue* next. By the way, we must recognize that it will incur extra overhead. In most case, it is negligible.

To facilitate viewing, the example shown before is copied here.

function outer() {
    let cnt = 0;
    function middle()
    {
        function inner() {
            return ++cnt;
        }
        return inner;
    }

    cnt = 2;

    function dec()
    {
        return --cnt;
    }
    dec();
    return middle;
}

let mid = outer();
let inn = mid();
console.log(inn());
console.log(inn());

Then at line 17, the dec is called and the value of cnt is decresed by 1. Current situation is as follows.

Current Runtime Status

The call to outer will return at line 18 and the cnt on the stack will become invalid. As we said in section Closure Design, we need to move the cnt from the stack to the heap to extend its lifespan. One way is to allocate the Value on the heap and copy the value of cnt on the stack to it and then set the location into corresponding UpValue object. Another way is to add a field of Value into the UpValue object directly and we move the cnt on the stack into that field directly. We select the latter and status is as follows.

Current Runtime Status

When the execution reaches the line 22, mid is called. and at line 5, the inner closure is created. The compiler know the cnt used in inner comes from the first element of the middle closure’s up_values_array. So it will emit code at compile time to copy that first element into inner’s up_values_array at runtime.

Well, we roughly go through the runtime behavior and compiler behavior for closure.