Explain this: Lisp programs are trees of expressions

Question

I'm learning Clojure at the moment. I keep reading the following statement:

"Lisp programs are trees of expressions"

I'm not quite sure I understand it. Could someone explain it to me?

Thanks!

Answer 1

For a code like this:

(+ (* 8 8) (* 4 4))

You will have the following tree:

I recommend to read about "Abstract Syntax Tree" and Lisp S-Expressions.

Answer 2

We think of a Lisp program as data/S-expressions/trees because of the existence of the reader, the first part of Lisp your program sees. The reader

• turns your program text into a data structure ...
• which you can manipulate (using macros).

This data structure is recursive - its elements can be similar data structures - and so it goes and so on.

For example, the expression in Chiron's answer, (+ (* 8 8) (* 4 4)), is converted by the reader into

(clojure.lang.PersistentList
 [clojure.lang.Symbol +]
 (clojure.lang.PersistentList
  [clojure.lang.Symbol *]
  [java.lang.Long 8]
  [java.lang.Long 8])
 (clojure.lang.PersistentList
  [clojure.lang.Symbol *]
  [java.lang.Long 4]
  [java.lang.Long 4]))

Where each element has its type in front of it.

• literals such as 4 are completely evaluated;
• symbols such as + and data structures such as lists are recognized and constructed.

You can see lists representing sub-expressions inside the list representing the whole expression.

Lisp regards each list as the application of the first element - the operator - to the other elements as arguments. So each operator has a number (which may be zero) of elements under it. Thus we think of the hierarchy of lists as a tree.

• This does not apply to the other manifest data structures: vectors, sets, and maps.
• If the operator is a function, it works when the program runs. If it is a macro, it works at once in the structure built by the reader.

The read-string function shows you the structure the reader will produce from a text expression. This isn't informative by itself, as printing it simply reconstructs the text in a standard format.

(read-string "(+ (    * 8 8)
         (* 4 4))")
; (+ (* 8 8) (* 4 4))

---

The function that exposed the structure tagged with its types is

(defn typed [form]
  (if (sequential? form)
    (cons (type form) (map typed form))
    [(type form) form]))

called thus:

(typed (read-string "(+ (* 8 8) (* 4 4))"))