VariableBindings

Overview

This topic discusses changes to the SemanticAnalyzer in its treatment of variable bindings. The current binding system is fairly minimal, relying on recreating the symbol bindings at runtime in a separate Environment structure. The SemanticAnalyzer likewise has little knowledge of the handling of SpecialVariables? . The support for LispDeclarations? in the spring of 2005 made it possible for a programmer to specify special bindings for variables. The SemanticAnalyzer now classifies non-special variables as ParameterOnly? , LocalOnly? , or ClosureAllocation. This enables the IntermediateCodeGeneration to create more efficient runtime code than that of the existing dynamic Environment lookup.

See the LocalAllocation topic for details of code generation using the lambda reference data.

References

HyperSpec	CLtL
link 1	Link 2

Implementation

Bindings are created whenever the execution encounters a LambdaExpression? or a LetForm? . A later version of the compiler will utilize more sophisticated algorithms such as ContinuationPassing? and ClosurePassing? which transform a LetForm? to a LambdaExpression? . But for now, this approach is sufficient. NOTE: A LetStarForm? is transformed into a set of LetForms? in the SemanticAnalyzer.

Lambda Reference Data Structure

When the SemanticAnalyzer encounters a binding expression, it replaces the car and the cadr of the expression with a new data structure that carries the information needed by the IntermediateCodeGeneration. The data structure is a list where the car is either compiler::%lambda or compiler::%let (NOTE: this may coalesce in a later version). The CDR of the list is an association list of information needed for the IntermediateCodeGeneration. The current tags are

• :bindings - information on the bindings of the variables bound in this form
• :symbol-table - information on the symbols found in this form
• :closure - information needed to allocate a closure object (see ClosurePassing? )
• :parent - reference to the enclosing lambda reference data

Each variable binding is also an association list where the tag is the specific variable. The CDR of a binding is a property list giving details of the specific binding.

Bindings

The special operators that create new bindings are LAMBDA and LET (with LET* being a variant). There are four binding properties that constitute the set of general bindings. These are:

• :type - the CL type of the variable. Defaults to T.
• :allocation - the allocation type, one of (:parameter . pn) or (:local . pl). Note that the allocation value is NIL if the scope is :dynamic.
• :scope - one of :lexical or :dynamic.
• :init-form - the initialization form for the binding of the variable. If none is supplied, the form is NIL. This property is used by both the LAMBDA and LET special forms, although they have slightly different semantics in each case.

Init Form Semantics

The :init-form property is a form that may be evaluated at runtime and in the enclosing environment. The form may be a constant (including a load time value) or a form to be evaluated in the enclosing lexical environment. In the context of a LET form, the init form will always be evaluated at runtime to produce the initial binding for the variable.

The runtime actions in the context of a LAMBDA form are slightly different. LAMBDA init forms are legal only when the variable is an optional or keyword argument. The forms are evaluated only in an application when the variable is not specified in the argument list.

The binding semantics also differ. In a LET form, the bindings are defined in parallel with no interaction between them. In a LAMBDA form, the bindings are defined sequentially allowing the init form of one binding to refer to the variable in a previous binding. This is similar to the action of LET* where each binding creates a new binding envirionment. The action of the SemanticAnalyzer is to essentially Curry a function application.

Additional Properties of LAMBDA Bindings

LAMBDA bindings contain additional properties that help in decoding the application of the function to arguments.

• :usage - the usage of the parameter as required, optional, rest, keyword, or aux. These are distinguished as the keyword :required (default), :optional, :rest, :aux, or :present, or a list whose car is :keyword. All of these except for :present correspond directly to the &optional, &rest, &keyword, and &aux lambda list keywords. :present corresponds to the variable that indicates the presence or absence an optional or keyword argument. It's type is Boolean.
• :required - indicates that the argument list must provide a value for this parameter. It is the default.
• :optional - indicates that the parameter is optional in an argument list. The :init-form will be used to provide a default value when there is no corresponding argument. The default is NIL.
• :rest - indicates that the parameter is bound to the remaining values in the argument list. The default value is NIL.
• :keyword - this entry is a list starting with the :keyword symbol. The cadr of the list is the symbol that forms the actual key in an argument list. The default is the name of the binding variable interned in the KEYWORD package.
• :aux - indicates that this is a local binding environment much as a LET form at the start of the function body.
• :present - indicates that the value of this parameter is set based on the presence of the previous binding in the actual argument.

Type

This property specifies the type of a bound variable. Currently this value is taken from a declaration associated with the Lambda or Let form. In later versions it may also be inferred from context. The value can be any CommonLisp type. The default value is T. Note: in a later version, the type specification can also be any valid Java type specification. The ICG will use the Java type associated with the CommonLisp type to specify the Java type of the variable.

Allocation

This property specifies where the variable is allocated at runtime.

• (:parameter . pn) - the variable is considered as an argument to the implementing Java method. Pn is the positional specification for the order of the parameters to the function. Used when the binding environment is defined by a LAMBDA. The initial value of the :parameter property is 1 to account for the JVM use of position 0 for this.
• (:local . ln) - the variable is stack-allocated as a local variable to the JVM. ln is the internal number of the stack-local variable defined by this binding. Used when the binding environment is defined by a LET.

The ICG uses the allocation value to determine where the variable is allocated and generates references appropriately. See LocalAllocation.

Scope

This property specifies the CommonLisp scope type.

• :lexical - the variable has lexical scope in the binding environment of the lambda or let form
• :dynamic - the variable has dynamic scope (considered as a special variable) in the binding environment of the lambda or let form.

In the case of a lexical binding, the ICG uses the :allocation value to generate a reference to the parameter, local, or closure reference. In the case of a dynamic binding, the ICG generates code to bind and unbind the dynamic (global) value of the symbol. All references to the variable are to the symbol itself.

Init Form

This property holds the initialization Lisp form. This form is evaluated in the immediately enclosing binding environment. The value is stored in the local variable as specified in the :allocation property. If there is no initialization form specified in the LET binding, the default form is system::*unbound-value*. This property is defined only for compiler::%let bindings. NOTE: there may be initialization forms for other systems such as CLOS.

Symbol Table

The symbol table is a list of the free symbols found in a binding environment. The properties of the symbol table are:

• :type - the CL type of the variable. Defaults to T.
• :scope - one of :lexical or :dynamic. The values are the same as for :bindings.
• :binding - the value can be either :free implying that it is not bound anywhere in the binding tree, or it can be a reference to the lambda reference data containing the closure where the symbol is bound. It is an error if the :binding value is :free and the value of :scope is :lexical.
• :allocation - One of:
  • a reference to the lambda binding where the symbol is allocated to a JVM local variable. This is used in a non- lambda expression.
  • (:local . ln) - the symbol is stored in a stack-allocated as a local variable to the JVM. ln is the internal number of the stack-local variable. This is used in a lambda expression. Similar to the allocation binding parameter.

Closure

The closure defines the set of variables that are free in some nested binding and are first bound in this binding. The CDR of the closure specification is an association list whose keys are the symbols in the closure. The properties of the symbol elements are:

• :references - the number of references to the free variable
• :position - the ordinal position of the variable in the closure defined in this binding.

Parent

The parent entry is a reference to the enclosing lambda reference data structure or NIL. This facilitates the scan for enclosing bindings.

Core Java Classes	Javadoc Links

Illustrations

Overall Example of Binding, Free Variables, and Closure

Lambda Reference Lists

The following are the lambda reference lists generated for the illustration above. Symbols of the form #ref-n# mean a reference to the lambda representation list of the nth entry.

1. (compiler::%lambda
   (:bindings
   (x :type T :allocation (:parameter . 1) :scope :lexical)
   (y :type T :allocation (:parameter . 2) :scope :lexical)
   (z :type T :allocation (:parameter . 3) :scope :lexical)
   )
   (:symbol-table (s :type T :scope :dynamic :binding :free))
   (:closure
   (x :position 0 :references 3)
   (y :position 1 :references 1)
   )
   (:parent nil)
   )
2. (compiler::%lambda
   (:bindings
   (a :type T :allocation (:parameter . 1) :scope :lexical)
   (b :type T :allocation (:parameter . 2) :scope :lexical)
   )
   (:symbol-table)
   (:closure
   (b :position 0 :references 1)
   )
   (:parent #ref-1#)
   )
3. (compiler::%lambda
   (:bindings
   (x :type T :allocation (:parameter . 1) :scope :lexical)
   (a :type T :allocation (:parameter . 2) :scope :lexical)
   )
   (:symbol-table (b :type T :scope :lexical :binding #ref-2#))
   (:closure)
   (:parent #ref-2#)
   )
4. (compiler::%lambda
   (:bindings
   (y :type T :allocation (:parameter . 1) :scope :lexical)
   )
   (:symbol-table (x :type T :scope :lexical :binding #ref-1#))
   (:closure)
   (:parent #ref-2#)
   )
5. (compiler::%lambda
   (:bindings
   (a :type T :allocation (:parameter . 1) :scope :lexical)
   (y :type T :allocation (:parameter . 2) :scope :lexical)
   )
   (:symbol-table (x :type T :scope :lexical :binding #ref-1#))
   (:closure
   (a :position 0 :references 1)
   )
   (:parent #ref-1#)
   )
6. (compiler::%lambda
   (:bindings
   (c :type T :allocation (:parameter . 1) :scope :lexical)
   )
   (:symbol-table (d :type T :scope :dynamic :binding :free))
   (:closure)
   (:parent #ref-5#)
   )
7. (compiler::%lambda
   (:bindings
   (x :type T :allocation (:parameter . 1) :scope :lexical)
   )
   (:symbol-table (a :type T :scope :lexical :binding #ref-1#))
   (:closure)
   (:parent #ref-5#)
   )
8. (compiler::%lambda
   (:bindings
   (x :type T :allocation (:parameter . 1) :scope :lexical)
   )
   (:symbol-table (y :type T :scope :lexical :binding #ref-1#))
   (:closure)
   (:parent #ref-1#)
   )

Current Status of VariableBindings

Status:

Release Level:

Open bug count:

Test Suites

Links to JUnit results

-- JerryBoetje - 12 Jul 2003