LISP Workshop for Musicians #3

List Structures

Lisp is renowned for its handle of lists. In Fact, the name Lisp is a contraction for LISt Processing. In the previous section we have created lists that represent musical structures, now we will go into the details of how Lisp handle this lists, and how it stores them in memory.

Lets define a variable measure-1 as an empty list:

     (defvar measure-1 '())
     measure-1

As you can infer from evaluating measure-1, an empty list is equivalent to NIL in Lisp. This is represented in memory by a cell:

We can put a symbol inside this empty structure using the function cons:

     (cons 'c4 measure-1)
     measure-4

     Note that the value of measure-1 is still NIL, you have to setf 
     the variable to its new value:

     (setf measure-1 (cons 'c4 measure-1))
     measure-1

The cell representation of this object in memory is:
The first cell represents the car (first element) of the list, and it has a pointer to its cdr (the rest of the list): the empty list. This shows that the last cell of a list structure is always NIL. In the the case of a list with only one element (like measure-1) the rest (cdr) of the list is NIL: taking its first element away we have only its last cell. Note that this last cell is not pointing to other cells.

If we add another element to measure-1:

     (setf measure-1 (cons 'd4 measure-1))
     measure-1

     The duple-cell structure is now:



     (car measure-1)

     (cdr measure-1)

The function list constructs and returns a list of its arguments:

     (defvar measure-2 (list 'b3 'c4 'b3 'c4 'a3))

     Note that this is similar to do:

     (setf measure-2 
         (cons 'b3 (cons 'c4 (cons 'b3 (cons 'c4 (cons 'a3 nil))))))
 We can make one list out of two (or more) lists using the function append:
     (append measure-1 measure-2)

 The functions that operate on lists that we have cover until this class have no side effects, they construct lists and access elements from them without changing the original objects. The functions push and pop are the destructive versions of cons and car:
     (pop measure-2)
     measure-2

     (push 'b3 measure-2)

Identity Predicates

Lets create the following list structure:

      (defvar a-notes (list measure-1 measure-2 '(d4 c4)))

The cell structure of a-notes is:

          
                (car a-notes) ;;; this is measure-1
          (car (cdr a-notes)) ;;; this is measure-2
    (car (cdr (cdr a-notes))) ;;; the same as measure-1

The second element of both measure-1 and measure-2 are the same:

     (second (car a-notes))  or (second (first a-notes)) or (nth 1 (first a-notes))
     (second (cadr a-notes)) or (second (first (rest a-notes))) or (nth 1 (nth 0 (rest a-notes)))

     and the first and last elements of a-notes have the same content:

     (first a-notes)
     (second (rest a-notes))

The predicate eq can be used to compare Lisp forms:

     
     (eq (nth 1 (first a-notes)) (nth 1 (nth 0 (rest a-notes))))
     (eq (first a-notes) (second (rest a-notes)))

In the first case eq answers T, because this two objects are exactly the same: the symbol C4 is identical to itself. But in the second case eq answers NIL because the two list are stored in different memory allocations. Lisp has different predicates to compare forms at different levels. The predicate eq is the highest in the hierarchy of predicates, it can get you into trouble if you are dealing with anything but symbols:
```
     (eq 1.0 1.0)

     (eq "hello" "hello")
```

The following in the hierarchy is the predicate eql

     (eql 1.0 1.0)

     (eql (nth 1 (first a-notes)) (nth 1 (nth 0 (rest a-notes))))

     but:

     (eql (first a-notes) (second (rest a-notes)))

     (eql "hello" "hello")

Eql is less restrictive that eq but it still considers the two lists with the same contents to be different. One step further is the predicate equal:
```
 

     (equal (first a-notes) (second (rest a-notes)))

     (equal "hello" "hello")

     but:

     (equal 1 1.0)
```
The function equal treats two objects as equivalent if they are symbols and they are eq, if they are numeric constants and are eql, or if they are two objects of the same type and print the same way.
The less restrictive of all the equivalence predicates is equalp
```
     (equalp 1 1.0)

     (equalp "Hello" "HELLO")
```
Equalp returns T if its arguments are equal, or if its arguments are numbers that can be coerced to the same type and have the same value.

The hierarchy of the equivalence predicates is:

     eq
       eql
          equal
               equalp

List Modification

Lisp has tons of functions that operate over lists. Most of this functions are macros (functions of functions) that use a basic set of primitive functions, and combine them to create more complex functions. Here are some of the functions of this basic set.
As we will deal with some destructive functions, is a good idea to make a copy of the list we are using and modify it instead of the original object. The function copy-list creates a copy of a list in a different memory allocation:
```
     (setf a-notes-copy (copy-list a-notes))
```
We can reverse the objects inside a list:
```
     (reverse (nth 1 a-notes))
```

The destructive version of reverse is the function nreverse:

     (nreverse (nth 1 a-notes-copy))
     (nth 1 a-notes-copy)

We can remove an object of a list:
```
     (remove 'c4 (nth 0 a-notes))
```
The destructive version of remove is the function delete:
```
     (delete 'c4 (nth 0 a-notes-copy))
     (nth 0 a-notes-copy)
```
We can remove-duplicates from a list (or repeated notes from a score...):
```
     (remove-duplicates (nth 1 a-notes))
```
The destructive version of remove-duplicates is the function delete-duplicates:
```
     (delete-duplicates (nth 1 a-notes-copy))
     (nth 1 a-notes-copy)
```
And finally, we can substitute one element for another in a list (or change wrong notes from a score... which are them?):
```
     (substitute 'g4 'c4 (nth 0 a-notes))
```
The destructive version of substitute is the function nsubstitute:
```
     (nsubstitute 'g4 'c4 (nth 0 a-notes-copy))
     (nth 0 a-notes-copy)
```
Back to LispWorkshop main page.

©1996-98 by Juan Pampin, juan@ccrma.stanford.edu