{Begin SubSec Variable Bindings}
{Title Variable Bindings}
{Text

{index Free variable access}
{index Local variables}
{index Special variables}
{index Global variables}

Different implementations of lisp use different methods of accessing free variables.  The binding of variables occurs when a function or a {fn PROG} is entered.  For example, if the function {lisp FOO} has the definition {lisp (LAMBDA (A B) {arg BODY})}, the variables {lisp A} and {lisp B} are bound so that any reference to {lisp A} or {lisp B} from {arg BODY} or any function called from {arg BODY} will refer to the arguments to the function {lisp FOO} and not to the value of {lisp A} or {lisp B} from a higher level function.  All variable names (litatoms) have a top level value cell which is used if the variable has not been bound in any function.   In discussions of variable access, it is useful to distinquish between three types of variable access: local, special and global.  Local variable access is the use of a variable that is bound within the function from which it is used.  Special variable access is the use of a variable that is bound by another function.  Global variable access is the use of a variable that has not been bound in any function.  We will often refer to a variable all of whose accesses are local as a "local variable."  Similarly, a variable all of whose accesses are global we call a "global variable."

{index Deep binding}

In a "deep" bound system, a variable is bound by saving on the stack the variable's name together with a value cell which contains that variable's new value.  When a variable is accessed, its value is found by searching the stack for the most recent binding (occurrence) and retrieving the value stored there.  If the variable is not found on the stack, the variable's top level value cell is used.

{index Shallow binding}

In a "shallow" bound system, a variable is bound by saving on the stack the variable name and the variable's old value and putting the new value in the variable's top level value cell.  When a variable is accessed, its value is always found in its top level value cell.

The deep binding scheme has one disadvantage: the amount of cpu time required to fetch the value of a variable depends on the stack distance between its use and its binding.  The compiler can determine local variable accesses and compiles them as fetches directly from the stack.  Thus this computation cost only arises in the use of variable not bound in the local frame ("free" variables).  The process of finding the value of a free variable is called free variable lookup.

In a shallow bound system, the amount of cpu time required to fetch the value of a variable is constant regardless of whether the variable is local, special or global.  The disadvantages of this scheme are that the actual binding of a variable takes longer (thus slowing down function call), the cells that contain the current in use values are spread throughout the space of all litatom value cells (thus increasing the working set size of functions) and context switching between processes requires unwinding and rewinding the stack (thus effectively prohibiting the use of context switching for many applications).

Interlisp-D uses deep binding, because of the working set considerations and the speed of context switching.  The free variable lookup routine is microcoded, thus greatly reducing the search time.  In benchmarks, the largest percentage of free variable lookup time was 20 percent of the total ellapsed time; the normal time was between 5 and 10 percent.

One consequence of Interlisp-D's deep binding scheme is that users may significantly improve performance by declaring global variables in certain situations.  If a variable is declared global, the compiler will compile an access to that variable as a retrieval of its top level value, completely bypassing a stack search.  This should be done only for variables that are never bound in functions, such as global databases and flags.

Global variable declarations should be done using the {filecom GLOBALVARS} file package command ({PageRef FileCom GLOBALVARS}).  Its form is {lisp (GLOBALVARS  {arg VAR{sub 1}} {ellipsis} {arg VAR{sub N}})}.

Another way of improving performance is to declare variables as local within a function.  Normally, all variables bound within a function have their names put on the stack, and these names are scanned during free variable lookup.  If a variable is declared to be local within a function, its name is not put on the stack, so it is not scanned during free variable lookup, which may increase the speed of lookups.  The compiler can also make some other optimizations if a variable is known to be local to a function.

A variable may be declared as local within a function by including the form {lisp (DECLARE (LOCALVARS {arg VAR{sub 1}} {ellipsis} {arg VAR{sub N}}))} following the argument list in the definition of the function.  Note: local variable declarations only effect the compilation of a function.  Interpreted functions put all of their variable names on the stack, regardless of any declarations.


}{End SubSec Variable Bindings}