Understanding fabric.lisp

by Matt Wright, Jan 5, 2004

Some help in understanding Common Lisp, CLM, and the fabric.lisp cellular automaton example.

The make-cells function

The first definition in the file is pure Common Lisp; it defines a function called make-cells that creates an array that will represent the cells of the cellular automaton. Here is the definition:

(defun make-cells (arg)
  (let* ((size (if (listp arg)
		   (length arg)
    (make-array size
		:initial-contents (if (listp arg)
				    (loop repeat size 
				      collect (if (< (random 1.0) 0.5) 0 1))))))

Defun defines a function; see Dissecting simp.ins for an explanation. Documentation for defun

Let* is for "binding" multiple variables sequentially. This means creating variables, evaluating expressions that provide the values of these variables, and then evaluating an expression using those variables. In this example, only one variable is created, size, whose value comes from an if expression. The "body" of the let* expression is the invocation of make-array; inside the call to make-array, the variable size has the value that came from evaluating the if expression. Documentation for let and let*.

If is for making two-way decisions: "If A then B, otherwise C". An if expression consists of the symbol if, a "test" expression which is evaluated to produce a true or false value, an expression to be evaluated and returned if the test expression is true, and an expression to be evaluated and returned if the test expression is false. Documentation for if.

Listp is a function that checks whether its argument is a list or not. The "p" in its name stands for "predicate", which means a function that returns true or false. Documentation for lots of functions that check whether the input is of a given type.

Length is a function that returns the number of elements in a given sequence. Documentation for lots of functions that perform simple operations on sequences

We can now understand this expression that determines the value of the size variable:

(if (listp arg)
    (length arg)

This could be translated into English as "If arg is a list, return the length of that list; othersize return arg itself."

Make-array, believe it or not, is a function that makes an array. The first argument determines the length of the array; in this example it comes from the size variable. There is also a "key" argument named :initial-contents that sets the initial contents of the array. Normal arguments in Common Lisp must come in a specific order, for example, the three arguments to if. "Key" arguments can come in any order (or not at all, since they can be optional) and are therefore always preceeded by the name of the argument, which in this example is :initial-contents.

Loop is a powerful and complicated part of Common Lisp that is used to execute something repeatedly. You can read page after page of documentation for loop. We recommend that you start with this much more user-friendly tutorial introduction to loop.

The step-cells function

The next definition in fabric.lisp is for the procedure step-cells. This procedure implements one "turn" or time-slice, taking in the old array of cells and applying the rules to produce the new array of cells.
(defun step-cells (cells)
  ;; cells is a one dimensional array, elements contain either
  ;; a zero (the cell is dead) or one (the cell is alive)
  (let* ((size (length cells))
	 (next (make-array size :initial-element 0)))
    (loop for i from 0 below size do
      (let* ((neighbors (list (aref cells i)
			      (aref cells (mod (+ i 1) size))
			      (aref cells (mod (+ i 2) size)))))
	;; set the guy in the middle to be born, hang on or die
	;; this implements the rule set of this automata
	(setf (aref next (mod (+ i 1) size))
	       ((equal neighbors '(0 0 0)) 0)
	       ((equal neighbors '(0 0 1)) 1)
	       ((equal neighbors '(0 1 0)) 1)
	       ((equal neighbors '(0 1 1)) 0)
	       ((equal neighbors '(1 0 0)) 1)
	       ((equal neighbors '(1 0 1)) 1)
	       ((equal neighbors '(1 1 0)) 0)
	       ((equal neighbors '(1 1 1)) 0)
	       ;; we should never get here...
	       (t nil)))))
    ;; return the next generation

It's tempting to look at this function line-by-line as a sequence of commands, like a C or Java program. But you'll understand Lisp a lot better if you can think in terms of nested expressions; that's what Lisp's parentheses are all about. Here's how to look at this definition in terms of nested expressions:

The body of the step-cells function is a single let* expression. The let* expression binds the two variables size and next, and its body is two expressions: a loop expression and the expression next. The value of the expression next is simply the value of the variable next, which is the new array whose contents, by the time we're done going through the loop expression, will be the new values of all our cells. The body of the loop expression is another let* expression that defines the variable neighbors and whose body is a setf expression.

List is a function that makes a list out of the given arguments. In this case there are three arguments to list, each an invocation of aref, so the result will be a three-element list. Documentation for lots of functions that operate on lists.

Aref is a function that looks up the given element of an array. The first argument is the array and the second argument is an integer that says which element we care about. Documentation for functions that access arrays.

Mod is the modulus function, documented in here somewhere.

Setf changes the value of a variable. It can also be used, as in this example, in conjunction with aref to change the value of an element of an array. The first argument is the "place" into which the new value will be stored, and the second argument determines the new value that will be stored there. Documentation for setf and for Common Lisp variables in general.

Cond is for making a series of decisions; it's equivalent to a big set of if expressions. Documentation for cond.

Equal is a predicate that tests whether its two arguments are equal to each other. Documentation on Common Lisp's equality predicates.

Some examples

The rest of the file fabric.lisp is a series of examples to be executed directly from the Lisp interface. These call the make-cells and step-cells functions.

  (format t "~%")
    with cells = (make-cells '(0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0))
    repeat 20
    (loop for cell across cells do (format t "~a" (if (= cell 1) "*" " ")))
    (format t "~%")
    (setf cells (step-cells cells))))

Progn evaluates a series of expressions in order. In this case there are two: the invocaion of format and the invocation of loop. Documentation for progn.

Format is for producing formatted text strings. If the first argument is t, as in these examples, then the formatted text is printed to the screen (instead of written into a Common Lisp string). There are tons of features to this function. Documentation for format.

You've already seen all of the other elements of this example. The outer loop sets up the initial array to be a single 1 in a series of zeros, then iterates the cellular automaton 20 times, each time printing the status of all the cells.

Finally, here's the first of the sound examples:

(with-sound ()
    ;;; start with a non-random state for all cells
    with cells = (make-cells '(0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0))
    repeat 50
    for time from 0 by 0.2
    for population = (population cells)
    (fm-violin time 0.1 (hertz (+ 60 population)) 0.1)
    (setf cells (step-cells cells))))

With-sound is the part of CLM that arranges for the samples that your program computes to be written into a sound file and played. We saw this last quarter in 220a. Documentation for with-sound.

FM-violin is an instrument that is defined in the file v.ins. It's not a part of Common Lisp or of CLM; it's an instrument that was written in CLM. There isn't really any documentation except for the source code itself. At this point all you need to know is that every time you call fm-violin it synthesizes a note in the output, and that these are the four arguments:

  1. starttime: At what time (in seconds) in the output sound should the note begin?
  2. dur(ation): How long (in seconds) should the note last?
  3. frequency: What should be the frequency (in Hertz) of the note?
  4. amplitude: What should be the amplitude (on a linear scale, from 0 to 1) of the note?

Finding documentation for yourself

Unfortunately, there is no combined documentation for Common Lisp, Common Music, Common Lisp Music, and Common Music Notation all in one place. That means that if you want to look something up that you find in some Lisp code, you have to know (or guess) whether that thing is part of Common Lisp itself, part of CM, part of CLM, part of CMN, etc. In practice this means that occasionally you'll try to look something up in the wrong place, and you won't find it, and then you'll have to look for it somewhere else.

The best reference for Common Lisp is the online version of the book "Common Lisp the Language, 2nd edition". There's a nice index that you can use to look up specific Lisp functions.

There is an online manual for CLM that also has a nice index that you can use to look up specific functions.

There is an online home page for CM that has a dictionary of all the built-in functions, etc.

There is online documentation for CMN in one huge html file with an index at the bottom.

©2004 Matt Wright. All Rights Reserved.