Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 38 ยท Syntax and Evaluation

S-expressions and How Evaluation Works

Learn how Lisp code is built from S-expressions and how the evaluator reduces them: atoms, lists, the substitution model, special forms and the quote operator.

Almost all the syntax in Racket and Scheme comes from one idea: the S-expression (symbolic expression). An S-expression is either an atom (a number, string, symbol, boolean) or a parenthesized list of S-expressions. That is the whole grammar. Once you understand how an S-expression is evaluated, you understand how every program in the language runs.

Examples run on the course's JavaScript stand-in interpreter, which follows the same evaluation rules described here.

Atoms and lists

RACKET
42            ; a number
"hello"       ; a string
#t            ; the boolean true
apple         ; a symbol (a name)
(+ 1 2)       ; a list of three things: +, 1, 2
(* (+ 1 2) 3) ; a list whose second element is itself a list

Whitespace separates elements and line breaks do not matter. Indentation is purely for people, but good editors indent code automatically, and Lisp programmers read the indentation rather than counting parentheses.

The evaluation rules

An evaluator needs only a few rules:

  1. A number, string or boolean evaluates to itself.
  2. A symbol evaluates to the value bound to that name.
  3. A list whose first element is a special form keyword (if, define, lambda, quote, ...) is evaluated by that form's own rule.
  4. Any other list is a function call: evaluate every element (the first is the function, the rest are the arguments), then apply the function to the argument values.
flowchart TD
    A["Expression"] --> B{"What is it?"}
    B -->|"number, string, boolean"| C["Return itself"]
    B -->|symbol| D["Look up its value"]
    B -->|"list with a special form first"| E["Apply the special rule"]
    B -->|"other list"| F["Evaluate every element, then call the function"]

The four evaluation cases.

The substitution model

You can predict the result of an expression by rewriting it step by step, replacing each call with its result. Take (* (+ 1 2) (- 10 4)):

TEXT
(* (+ 1 2) (- 10 4))
(* 3 (- 10 4))        ; evaluate the first argument
(* 3 6)               ; evaluate the second
18

For a function you define, replace the call with the body, putting the argument values in place of the parameters:

RACKET
(define (square x) (* x x))
(square (+ 2 1))
;; (square 3)
;; (* 3 3)
;; 9

This rewriting is exactly what DrRacket's Stepper shows.

Evaluate nested expressions

Order of evaluation of arguments

Because arguments are evaluated before the call, an argument with a side effect happens first. In Racket, arguments are evaluated left to right, which you can rely on. (In standard Scheme the order is unspecified, so portable code avoids depending on it.)

Arguments are evaluated first

The output 1 2 3 6 is the three displayed values followed by the result 6. Each say ran before + did, in left-to-right order.

Special forms are not function calls

if cannot be an ordinary function, because a function evaluates all its arguments before running. (if test then else) must evaluate only one branch:

RACKET
(define (loop) (loop))
(if #t 1 (loop))   ; returns 1; the (loop) branch is never evaluated

Other special forms include define, lambda, let, cond, and, or, quote, set! and begin. Each has its own rule, which you will learn in turn.

Only one branch runs

and and or also short-circuit: they stop as soon as the answer is known, so they are special forms too.

Quote: stopping evaluation

Sometimes you want a list as data, not as a call. The quote special form returns its argument unevaluated, and 'x is shorthand for (quote x):

RACKET
(+ 1 2)        ; => 3        evaluated as a call
'(+ 1 2)       ; => '(+ 1 2) a list of three elements
(quote (+ 1 2)) ; same as above
'apple         ; => 'apple   a symbol, not a variable lookup

Quote is how you write literal lists and symbols. You will use it constantly in the next chapters.

Quote versus evaluate

Reading Lisp

Because syntax is so uniform, reading a function takes three steps: find the function name (the first element of each list), find its arguments (the rest), and then repeat inside any nested list. Reindent code mentally by starting a new line for each nested call, with arguments aligned:

RACKET
(define (hypotenuse a b)
  (sqrt (+ (* a a)
           (* b b))))

The line breaks and alignment add no meaning; they simply expose the tree structure.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two kinds of S-expressions?

    An S-expression is an atom or a list of S-expressions.
  2. 2. Why can't if be an ordinary function?

    Ordinary calls evaluate every argument before running; special forms like if control which parts are evaluated.
  3. 3. What does '(+ 1 2) return?

    Quote returns its argument as data without evaluating it.
  4. 4. In the substitution model, what is (square (+ 2 1)) rewritten to first?

    The argument (+ 2 1) is evaluated first, giving (square 3); then the body is substituted.

Summary

  • Everything is an atom or a list; a list is usually a function call written function-first.
  • Evaluation: self-evaluating atoms, symbol lookup, special forms, and ordinary calls that evaluate arguments left to right.
  • The substitution model rewrites calls step by step and matches the Stepper.
  • if, and, or, define and friends are special forms, not functions.
  • quote (') turns code into data.

Next: Numbers and Booleans