Lisp Expression Evaluation and Control Structures

Key Insight

Programming in Lisp often involves an interactive 'read-eval-print loop': the interpreter reads an expression, evaluates it, and prints the result. Expressions can be primitive, like a number such as 486, or compound. Compound expressions, called combinations, are formed by enclosing a list of expressions in parentheses, with the leftmost element serving as the operator (e.g., `+` or `*`) and the others as operands. The value of a combination is determined by applying the operator's procedure to the values of the operands, as seen in `(+ 137 349)` yielding 486. Lisp uses prefix notation, placing the operator before its operands, which supports procedures with an arbitrary number of arguments (e.g., `(+ 21 35 12 7)` yields 75) and allows for straightforward nesting of combinations to arbitrary depths, simplifying the structure of complex expressions.

A crucial aspect is using names to refer to computational objects. In Scheme, the `define` special form associates a value with a name (e.g., `(define size 2)`), creating a variable. This provides a simple but effective means of abstraction, allowing complex operations to be named, facilitating incremental program construction and testing, which often leads to programs composed of many simple procedures. The interpreter maintains an 'environment' (specifically, a global environment) to keep track of these name-object associations. The evaluation of a combination follows a recursive procedure: first, all subexpressions are evaluated, then the procedure corresponding to the operator is applied to the values of the operands. The values of primitive expressions (numerals, built-in operators, named objects) are determined by their literal form or their binding in the environment, emphasizing the environment's role in assigning meaning to symbols. `define` is an example of a 'special form' that deviates from the general evaluation rule, possessing its own unique evaluation logic.

Lisp offers a powerful abstraction technique through procedure definitions, allowing compound operations to be named as units, such as `(define (square x) (* x x))`. These user-defined procedures function identically to primitive ones and can be used as building blocks for even more complex procedures. The 'substitution model' conceptualizes the application of a compound procedure by evaluating its body with formal parameters replaced by actual arguments, providing a mental framework for understanding execution, though it is not how interpreters typically operate. Lisp primarily uses 'applicative-order evaluation,' where all arguments are evaluated before the procedure is applied, chosen for its efficiency and ease of handling complex procedures, contrasting with 'normal-order evaluation' which substitutes expressions first. For conditional logic, Lisp provides special forms like `cond` for multi-case analysis and `if` for binary decisions. `cond` evaluates predicates sequentially, executing the consequent of the first true predicate. Logical composition operations—`and`, `or` (both special forms), and `not` (an ordinary procedure)—allow for constructing complex predicates, such as `(and (> x 5) (< x 10))`.