2.3 Structures

Structures are entities created out of the primitive types by the use of dotted-pairs. Lists are structures very commonly required as actual parameters to functions. Where a list of homogeneous entities is required by a function this class will be denoted by <xxx-list> where xxx is the name of a class of primitives or structures. Thus a list of ids is an id-list, a list of integers an integer-list and so on.

A list is recursively defined as NIL or the dotted-pair (any . list). A special notation called list-notation is used to represent lists. List-notation eliminates extra parentheses and dots. The list (a . (b . (c . NIL))) in list notation is (a b c). List-notation and dot-notation may be mixed as in (a b . c) or (a (b . c) d) which are (a . (b . c)) and (a . ((b . c) . (d . NIL))). In BNF lists are recognized by the grammar:
<left-part> ::= ( <left-part> <any>

<list> ::= <left-part>) <left-part> . <any>)

Note: () is an alternate input representation of NIL.

An association list; each element of the list is a dotted-pair, the CAR part being a key associated with the value in the CDR part.
A cond-form is a list of 2 element lists of the form:


The first element will henceforth be known as the antecedent and the second as the consequent. The antecedent must have a value. The consequent may have a value or an occurrence of GO or RETURN as described in the “Program Feature Functions”, section 3.7 on page 39.

A LAMBDA expression which must have the form (in list notation): (LAMBDA parameters body). “parameters” is a list of formal parameters for “body” an S-expression to be evaluated. The semantics of the evaluation are defined with the EVAL function (see “The Interpreter”, section 3.14 on page 66).
A LAMBDA expression or a function-pointer to a function. A function is always evaluated as an EVAL, SPREAD form.