/schemer

Schemer

Definitions

S-Expression

A symbolic expression, or S-expression, sexpr, sexp for short, in the Lisp family of languages denotes either an atom or a list.

  • Atoms are immutable objects that represent a number or a symbol.
  • Lists represent data or code, and are modifiable (depending on the dialect).

When representing code, a list is written in the Polish (prefix) notation, where the first s-expression is a function or an operator.

Pairs | Dotted Pairs | Cons Cells

  • Lists are expressed as cons cells in the form (sexp-1 . sexp-2).
  • Cons cells are ordered pairs and thus S-expressions are binary trees.
  • Nested cons cells such as (a . (b . (c . (d . NIL)))) can be written in a simpler form as (a b c d).
  • The ordered pair (also called the dotted pair notation) is also referred to as the internal representation, while the simpler form is syntactic sugar and referred to as the external representation.
  • NIL or () is a symbol for termination.

In memory, the cons cells are represented as linked lists. Each node in the list is a single cons cell, where the first S-expression is an atom or a list and second S-expression represents an atom or pointer to the next cons cell. The list is terminated with NIL.

In the language, we describe a cons cell as consisting of two parts, the car and a cdr. The car points to the first element in the pair and the cdr points to the rest of the list.

The length of a list is the number of dotted pairs in the list. The empty list (NIL or ()) has length 0. The elements in the list are all the car elements of successive pairs.

Strictly speaking, a pair is a list if it is terminated with the empty list (NIL or ()).

Propert Lists and Improper Lists

A proper list is a sequence of pairs that end with the empty list. On the contrary an improper list does not terminate with an empty list.

Examples of proper lists:

;; The empty list, ()
'()

;; A list with two elements, (1 2)
'(1 2)

;; The list (1)
(cons 1 '())

;; The list (1 2)
(cons 1 '(2))

;; The list (1 2 3)
(cons 1 (cons 2 '(3)))

;; The list (4 5 6)
(cons 4 (cons 5 (cons 6 '())))

Examples of improper lists:

;; The list (1 . 2)
(cons 1 2)

;; The list (3 . 4)
'(3 . 4)

A Recursive Defintion for Lists

The following is a recursive definition for a list:

  • An empty list (i.e. ())
  • A pair whose cdr value is a list

Toys

Atoms

;;; Atoms

;; A strring of characters beginning with a letter
'atom

;; A special function for declaring an atom
(quote atom)

;; A string of characters beginning with a letter
'turkey

;; A string of digits
1492

;; A single character which is a letter
'u 

;; A string of characters containing both letters and special
;; characters other than '(' or ')'
'*abc$

Lists

;;; Lists

;; An atom enclosed by parenthesis
'(atom)

(quote (atom))

;; A collection of atoms enclosed by parenthesis
'(atom turkey or)

(quote (atom turkey or))

;; Not a list. Two seperate S-expressions, one is a list the other is
;; an atom
'(atom turkey) or

;; A list containing a list and an atom. Two S-expressions enclosed in
;; parenthesis. Compare to previous example.
'((atom turkey) or)

;; All atoms are S-expressions
'xyz

;; All lists are S-expressions
'(x y z)

'((x y) z)

;; A list is a collection of S-expessions enclosed by parenthesis
'(how are you doing so far)

;; There are 6 S-expressions in the previous example, they are:
'how
'are
'you
'doing
'so
'far

;; A list is a collection of S-expessions enclosed by parenthesis
'(((how) are)((you) (doing so)) far)

;; There are 3 S-expressions in the previous example, they are:
'((how) are)
'((you) (doing so))
'far

;; A list with zero S-expressions. Also called a null or empty list.
;; A null list is not an atom. A null list is an S-expression.
'()

;; A list of null lists
'(() () () ())

Car

;;; car

;; The car of (a b c) is a, the firs atom in the list.
(car '(a b c))

;; The car of the following list is (a b c), the first S-expression in
;; the list.
(car '((a b c) x y z))

;; The argument to car must always be a pair. The following is a
;; contract violation.
(car 'hotdog)

;; The argument to car must always be a pair. The following is a
;; contract violation.
(car '())

**The Law of Car**: The primitive car is defined only for non-empty lists.

;;; car

;; The car of the following list is ((hotdocs)), the first
;; S-expression in the list.
(car '(((hotdogs)) (and) (pickle) relish))

;; The car of the following list is (hotdogs).
(car (car '(((hotdogs)) (and))))

References