3.1.3.1 Evaluating Expressions and Executing Programs

In Scheme, the process of executing an expression is known as evaluation. Evaluation has two kinds of result:

• the value of the evaluated expression
• the side effects of the evaluation, which consist of any effects of evaluating the expression that are not represented by the value.

Of the expressions that we have met so far, define and set! expressions have side effects — the creation or modification of a variable — but no value; lambda expressions have values — the newly constructed procedures — but no side effects; and procedure invocation expressions, in general, have either values, or side effects, or both.

It is tempting to try to define more intuitively what we mean by “value” and “side effects”, and what the difference between them is. In general, though, this is extremely difficult. It is also unnecessary; instead, we can quite happily define the behaviour of a Scheme program by specifying how Scheme executes a program as a whole, and then by describing the value and side effects of evaluation for each type of expression individually.

So, some¹ definitions...

• A Scheme program consists of a sequence of expressions.
• A Scheme interpreter executes the program by evaluating these expressions in order, one by one.
• An expression can be
  • a piece of literal data, such as a number 2.3 or a string "Hello world!"
  • a variable name
  • a procedure invocation expression
  • one of Scheme's special syntactic expressions.

The following subsections describe how each of these types of expression is evaluated.

Evaluating Literal Data

When a literal data expression is evaluated, the value of the expression is simply the value that the expression describes. The evaluation of a literal data expression has no side effects.

So, for example,

• the value of the expression "abc" is the string value "abc"
• the value of the expression 3+4i is the complex number 3 + 4i
• the value of the expression #(1 2 3) is a three-element vector containing the numeric values 1, 2 and 3.

For any data type which can be expressed literally like this, the syntax of the literal data expression for that data type — in other words, what you need to write in your code to indicate a literal value of that type — is known as the data type's read syntax. This manual specifies the read syntax for each such data type in the section that describes that data type.

Some data types do not have a read syntax. Procedures, for example, cannot be expressed as literal data; they must be created using a lambda expression (see Creating a Procedure) or implicitly using the shorthand form of define (see Lambda Alternatives).

Evaluating a Variable Reference

When an expression that consists simply of a variable name is evaluated, the value of the expression is the value of the named variable. The evaluation of a variable reference expression has no side effects.

So, after

     (define key "Paul Evans")

the value of the expression key is the string value "Paul Evans". If key is then modified by

     (set! key 3.74)

the value of the expression key is the numeric value 3.74.

If there is no variable with the specified name, evaluation of the variable reference expression signals an error.

Evaluating a Procedure Invocation Expression

This is where evaluation starts getting interesting! As already noted, a procedure invocation expression has the form

     (procedure [arg1 [arg2 ...]])

where procedure must be an expression whose value, when evaluated, is a procedure.

The evaluation of a procedure invocation expression like this proceeds by

• evaluating individually the expressions procedure, arg1, arg2, and so on
• calling the procedure that is the value of the procedure expression with the list of values obtained from the evaluations of arg1, arg2 etc. as its parameters.

For a procedure defined in Scheme, “calling the procedure with the list of values as its parameters” means binding the values to the procedure's formal parameters and then evaluating the sequence of expressions that make up the body of the procedure definition. The value of the procedure invocation expression is the value of the last evaluated expression in the procedure body. The side effects of calling the procedure are the combination of the side effects of the sequence of evaluations of expressions in the procedure body.

For a built-in procedure, the value and side-effects of calling the procedure are best described by that procedure's documentation.

Note that the complete side effects of evaluating a procedure invocation expression consist not only of the side effects of the procedure call, but also of any side effects of the preceding evaluation of the expressions procedure, arg1, arg2, and so on.

To illustrate this, let's look again at the procedure invocation expression:

     (string-length (string-append "/home" "/" "andrew"))

In the outermost expression, procedure is string-length and arg1 is (string-append "/home" "/" "andrew").

• Evaluation of string-length, which is a variable, gives a procedure value that implements the expected behaviour for “string-length”.
• Evaluation of (string-append "/home" "/" "andrew"), which is another procedure invocation expression, means evaluating each of
  • string-append, which gives a procedure value that implements the expected behaviour for “string-append”
  • "/home", which gives the string value "/home"
  • "/", which gives the string value "/"
  • "andrew", which gives the string value "andrew"

  and then invoking the procedure value with this list of string values as its arguments. The resulting value is a single string value that is the concatenation of all the arguments, namely "/home/andrew".

In the evaluation of the outermost expression, the interpreter can now invoke the procedure value obtained from procedure with the value obtained from arg1 as its arguments. The resulting value is a numeric value that is the length of the argument string, which is 12.

Evaluating Special Syntactic Expressions

When a procedure invocation expression is evaluated, the procedure and all the argument expressions must be evaluated before the procedure can be invoked. Special syntactic expressions are special because they are able to manipulate their arguments in an unevaluated form, and can choose whether to evaluate any or all of the argument expressions.

Why is this needed? Consider a program fragment that asks the user whether or not to delete a file, and then deletes the file if the user answers yes.

     (if (string=? (read-answer "Should I delete this file?")
                   "yes")
         (delete-file file))

If the outermost (if ...) expression here was a procedure invocation expression, the expression (delete-file file), whose side effect is to actually delete a file, would already have been evaluated before the if procedure even got invoked! Clearly this is no use — the whole point of an if expression is that the consequent expression is only evaluated if the condition of the if expression is “true”.

Therefore if must be special syntax, not a procedure. Other special syntaxes that we have already met are define, set! and lambda. define and set! are syntax because they need to know the variable name that is given as the first argument in a define or set! expression, not that variable's value. lambda is syntax because it does not immediately evaluate the expressions that define the procedure body; instead it creates a procedure object that incorporates these expressions so that they can be evaluated in the future, when that procedure is invoked.

The rules for evaluating each special syntactic expression are specified individually for each special syntax. For a summary of standard special syntax, see See Syntax Summary.