The list data type is the characteristic composite data type in all Lisp languages, and as such also in Scheme. Interesting enough, the surface form of a Lisp program is a list itself. This is an important practical observation. Below, we will study the list data type of Lisp and Scheme.

6.1.  Proper lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Lists are recursively composed. We start with the main points regarding the recursive construction of lists.

Below we illustrate how the list (d c b a) is built. The web version of the material gives the best impression of the construction process, via animation (refresh the web presentation to restart the animation). The paper version of the material only shows the end result of the construction.

In the items below we emphasize the decomposition of the cons cell made by (cons e f), where e is an arbitrary expression and f is a list. Notice that we assume that the variable x is bound to (cons e f).

The constructor function cons takes an element e and a list f and constructs a new list. As illustrated above cons makes exactly one new cons cell, and no kind of list copying is involved at all.

The selector car returns the first element of the list. A better name of car would be head .

The selector cdr returns the list consisting of all but the first element in the list. A better name of cdr would be tail .

6.2.  Symbolic expressions and improper lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

As illustrated above, the cons function can be used to construct linear linked lists. It should not come as a surprise, however, that cons can be used to make binary tree structures as well. The reason is that each cons cell can refer to two other cons cells.

In Figure 6.2 we show a binary tree structure made by use of the the cons function. The light blue box labeled Sexpr is a variable, the value of which is the binary tree structure. In Exercise 2.2 you are encouraged to construct the tree.

Figure 6.2    A symbolic expression which illustrates the most general form it can take - a binary tree

In Figure 6.3 we show the exact same structure in a slightly different layout, and with another coloring. This layout emphasizes the understanding of the structure as an improper list. The first element is the green tree, the second is the brown tree, the third is the symbol g, and the improper list element is the symbol h.

Figure 6.3    The same symbolic expression laid out as a list. The expressions is a proper list if and only if h is the empty list. If h is not the empty list, the symbolic expression is an improper list.

As a matter of terminology, we use the name symbolic expressions, or S-expressions, for the structures we have shown above.

6.3.  Practical list construction
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

On this page we address topics related to 'practical list construction'. Often, cons is too low level for construction of lists. Instead we use the list function or quoted expressions. A quoted expression is taken for face value; The quote form ´(e) prevents evaluation. The quasiquote form `(e) is a variant of quote, which allows non constant constituents in a quote form. Please notice the use of 'normal quote' and 'back quote' before the parentheses. For details of the quasiquote special form you should consult section 4.2.6 in the Scheme report [Abelson98] .

(cons 1 (cons 2 (cons (+ 1 2) '())))

(1 2 3)

(list 1 2 (+ 1 2))

(1 2 3)

(quote (1 2 (+ 1 2)))

(1 2 (+ 1 2))

'(1 2 (+ 1 2))

(1 2 (+ 1 2))

(quasiquote (1 2 (unquote (+ 1 2))))

(1 2 3)

`(1 2 ,(+ 1 2))

(1 2 3)

  (every-second-element '(a b c)) => (a c)

  (every-second-element '(a b c d)) => (a c)

6.4.  List functions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

On this page we will review a number of important list functions, which are part of Scheme and described in section 6.3.2 of the Scheme report [Abelson98] .

It should be noticed that the first element is designated as element number 0. Thus (list-ref '(a b c) 1) returns b

6.5.  Association lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Association lists are often used to associate two pieces of data. Association lists in Lisp and Scheme correspond to a particular implementation of associative arrays, cf. [knoopnotes]

In the table below we shows simple examples and applications of association lists. Try them out yourself!

(define computer-prefs 
 '((peter . windows) (lars . mac)
   (paw . linux) (kurt . unix)))

(assq 'lars computer-prefs)

(lars . mac)

(assq 'kurt computer-prefs)

(kurt . unix)

(define computer-prefs-1
 (cons (cons 'lene 'windows) 
  computer-prefs))

computer-prefs-1

((lene . windows)
 (peter . windows) 
 (lars . mac)
 (paw . linux)
 (kurt . unix))

  (pair-up '(a b c) (list 1 2 3))

  ((a . 1) (b . 2) (c . 3))

  ((a . 1) (b . 2) (c . 3))

  (a 1 b 2 c 3)

6.6.  Property lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Property lists are closely related to association lists. On this page - in Table 6.3 - we compare the two kinds of lists with each other. In Program 6.1 we give examples of property lists from LAML, which uses property lists for attributes in HTML, XML, and CSS.

((peter . "windows")
 (lars . "mac")
 (paw . "linux")
 (kurt . "unix"))

(peter "windows"
 lars "mac"
 paw "linux"
 kurt "unix")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(load (string-append laml-dir "laml.scm"))
(laml-style "simple-xhtml1.0-transitional-validating")


(write-html 'raw
 (html 'xmlns "http://www.w3.org/1999/xhtml"
  (head 
   (meta 'http-equiv "Content-Type" 
         'content "text/html; charset=iso-8859-1") 
   (title "Attribute Demo"))
  (body 'id "KN" 'class "generic"

    (p "Here comes a camouflaged link:")

    (p (a 'href "http://www.cs.auc.dk" 'css:text-decoration "none"
          'target "main" "Link to the CS Department"))

    (p "End of document."))))


(end-laml)

You should consult Section 27.2 if you want to learn more about the handling of attributes in LAML.

6.7.  Tables as lists of rows
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In this material we are especially interested in studying examples from the web domain. In HTML, tables are represented as collections of rows. It is therefore obvious to use lists of lists as a concrete Lisp representation of tables. In Table 6.4 we show such a table, tab1, its rendering, and a number of manipulations of the table (transpositions, row eliminations, and column eliminations). The table operations will be studied in further details in Exercise 4.6 .

tab1

(("This" "is" "first" "row")
 ("This" "is" "second" "row")
 ("This" "is" "third" "row")
 ("This" "is" "fourth" "row")
)

(show-table tab1)

(show-table (transpose-1 tab1))

(show-table (eliminate-row 2 tab1))

(show-table (eliminate-column 4 tab1))

In the program below we show a possible implementation of the show-table function, which we used in Table 6.4 The function table-1 is one of the LAML convenience functions, which we have used in the past. There are others and more interesting ways to deal with tables in LAML. You should consult Program 18.6 for details.

1
2
3
4
5
6
7

(define (show-table rows)
 (let ((row-lgt (length (first rows))))
   (table-1
      0 
      (make-list row-lgt 50) 
      (make-list row-lgt green1)
      rows)))

6.8.  Programs represented as lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The purpose of this section is to remind you that Scheme programs are themselves list structures. At this point of the material, it should not be a big surprise to the readers.

1
2
3
4
5
6
7
8
9

(define (as-number x)
  (cond ((string? x) (string->number x))
        ((number? x) x)
        ((char? x) (char->integer x))
        ((boolean? x) (if x 1 0))  ; false -> 0, true -> 1
        (else
         (error
          (string-append "Cannot convert to number "
                         (as-string x))))

Is it possible to access the list source program of a Scheme definition? In other words, is it possible to introspect and reflect about a Scheme program from another Scheme program. Or even more interesting perhaps, is it possible for a function to introspect and affect its own source code? Using the standard Scheme functions the answers are 'no'. However, some Scheme systems allow it nevertheless, through use of non-standard functions. Using more traditional Lisp languages, the answers are 'yes'.