Algorithmic Composition: A Gentle Introduction to Music Composition Using Common LISP and Common Music
Skip other details (including permanent urls, DOI, citation information): This work is protected by copyright and may be linked to without seeking permission. Permission must be received for subsequent distribution in print or electronically. Please contact [email protected] for more information.
For more information, read Michigan Publishing's access and usage policy.
Chapter 3: Introduction to Common LISP
Chapter 3 introduces you to the fundamentals of Common LISP and programming in LISP. You will learn about some of the various data types that Common LISP supports and many of its built-in functions called primitives . You will learn how to write your own functions and become familiar with typical error messages.
3.1 Data and Functions
Data is information. Common LISP supports several data types including numbers, symbols, and lists.
Numbers may take several forms including integers or whole numbers, ratios or fractions, and floating point numbers.
Another data type in Common LISP is a symbol. Symbols look like words and may contain any combination of letters and numbers along with some special characters like the hyphen (-) or underscore (_).
There are two special symbols in Common LISP: T and NIL. T represents TRUE or YES and NIL represents FALSE, NO, or NOTHING.
Another data type in Common LISP is a string. A string is a sequence of characters enclosed in double quotes.
A very important Common LISP data type is the list. Lists are at the heart of programming in LISP, which derived its name from LISt Processing. A list is a collection of one or more things enclosed in parentheses. If the list includes more than one thing, they are space delimited. Each thing in the list is called an element. Therefore the list (C-MAJOR D-MAJOR F-MAJOR) has three elements and the list(+ 4.5 23/8 .0007 -23) has 5 elements.
Lists may be represented in the computer's memory as a chain of cons cells. You may think of a cons cell as having two parts. The left part is referred to as the CAR and the right part is referred to as the CDR. Each part of a cons cell has a pointer. The CAR pointer points to an element in a list and the CDR points to the next element in the list. Figure 3.1.1 is a cons cell representation of the list (C-MAJOR D-MAJOR F-MAJOR). Notice that the cons cell chain ends in NIL.
Figure 3.1.1
Lists that consist of one level of a cons cell chain are called a flat list .
When a list contains another list, it is referred to as a nested list . An example of a nested list is (C-MAJOR (C E G)). The top-level of the chain of cons cells contains two elements: the symbol C-MAJOR and the list (C E G). The next level down of the chain of cons cells contains three elements namely the symbols C, E, and G. Figure 3.1.2 is a cons cell representation of the nested list (C-MAJOR (C E G)).
Figure 3.1.2
Lists that have the same number of left parentheses and right parenthesis are called well-formed lists . Both (C-MAJOR D-MAJOR F-MAJOR) and (C-MAJOR (C E G)) are well-formed lists.
Now that we are familiar with some Common LISP data types, it's important to learn how these data types relate to each other. Both numbers and symbols are categorized as atoms. An atom is the smallest object that cannot be represented by a cons cell. A list, on the other hand, is a chain of cons cells. Atoms and lists form what are called symbolic expressions. Figure 3.1.3 gives an overview of some Common LISP data types.
Figure 3.1.3
Each particular instance of a data type is called an object. Therefore 78.3, MY-CHORD, and (C-MAJOR (C E G)) are all objects.
3.2 LISP Primitives
Functions operate on data. Functions allow us to process data to achieve a result. Common LISP functions may be categorized as either primitives or user-defined functions. You may think of functions as procedures that operate on data. Evaluating an expression is referred to as evaluating a form. A form is simply some Common LISP expression.
A primitive is a built-in function or simply put, a function that LISP already knows about. LISP has many primitives that operate on numbers, symbols, and lists.
LISP primitives that function on numbers include basic arithmetic operations such as addition, subtraction, multiplication, and division as well as more advanced arithmetic operations such as square root.
The syntax for applying data to a function is to enter the function as the first element of a list followed by the input that is passed to that function. The template for calling a function is:(FUNCTION INPUT)
The best way to learn how Common LISP works is to use it. Follow along by typing these examples into your LISP interpreter.
Example 3.2.1
The reader enters the bold text into the interpreter. The information following the bold text is the evaluation returned by the interpreter.
Common Lisp appears in the COURIER font in all capital letters. Common Music appears in the helvetica font in all lower-case letters.
Notice how the subtraction primitive accepts more than two inputs. Some Common LISP functions accept a variable number of inputs. In this case, 6 is subtracted from 7 returning a value of 1. Next, 5 is subtracted from 1 returning a value of -4.
Functions may be nested. LISP evaluates nested functions by evaluating the innermost set of parentheses first and working toward the outer-most set of parentheses.
The primitive FLOAT returns a floating-point number .
The primitive ROUND returns the integer nearest to its input. If the input is halfway between two integers (for example 3.5), ROUND converts its input to the nearest integer divisible by 2.ROUND also returns the remainder of the rounding operation.
The primitive ABS returns the absolute value of its argument.
LISP has many primitives that function on lists. A useful function is LENGTH, which returns the number of elements found on the top-level of a list.
Notice that the list passed to LENGTH is preceded by a single quote. The single quote tells LISP not to evaluate the first element in the list as a function. The single quote or the LISP primitive QUOTE is helpful when you want to tell LISP not to evaluate something as a function or a variable. A variable is a place in memory where data is stored. Common LISP variables are named by symbols.
Try entering some of the quoted elements in the list a combination of upper case and lower-case letters. You will notice that LISP is not case sensitive for quoted lists.
LISP may have a list of no elements. A list of no elements is referred to as the empty list or NIL and is represented as () or the symbol NIL. Therefore NIL is both a symbol and a list.
You may point selectively to different elements in a list. The primitive CAR or FIRST returns the first element of a list by pointing to the first element of the list.
The primitive CDR or REST returns all but the first element of a list as a list.
From this, you may observe that FIRST and REST are complementary functions.
The FIRST and REST of NIL is defined as NIL.
Other LISP primitives selectively point to an element in a list such as second , THIRD, and so on.
The primitive LAST returns the last element of a list as a list.
The primitive BUTLAST returns the last N elements of a list. The first argument to BUTLAST is the list and the optional second argument is the number of elements to be omitted. If no second argument is given, BUTLAST assumes that only one element should be omitted.
The primitive REVERSE reverses the elements in a list such that what was first is now last and vice-versa.REVERSE operates on the top-level of the list.
The CONS primitive may be used to construct lists. The CONS function creates a cons cell. The CONS function requires two inputs and returns a pointer to a new cons cell whose CAR points to the first input and whose CDR points to the second.
Notice that the symbol A as well as the list (D E-FLAT) is quoted. The quote tells LISP not to evaluate the symbol A nor the list (D E-FLAT).
CONS may be used to create lists by CONS ing a symbol to NIL.
LIST creates lists from symbols and/or lists by simply adding a level of parentheses to its inputs.
Example 3.2.17
? (list '(c-major (c e g) d-major (d f-sharp a)))((C-MAJOR (C E G) D-MAJOR (D F-SHARP A)))
The primitive APPEND accepts two inputs. When APPEND is given two lists as its inputs, it returns a list that contains all of the elements of both lists as a list.
When APPEND is given a list followed by a symbol, it returns a dotted list. A dotted list is a chain of cons cell whose last CDR does not point to NIL.
Example 3.2.19
The cons cell representation of the list (C E G . B-FLAT) looks like Figure 3.2.1.
Figure 3.2.1
LISP evaluates dotted lists differently from flat lists. The evaluation of flat and dotted lists is best observed by comparing the results of LAST when applied to both flat and dotted lists.
In Example 3.2.20, appending two lists (C E) and (G B-FLAT) returns the list (C E G B-FLAT). The last element of the list is B-FLAT. Appending the list (C E G) with the symbol b-flat returns the dotted list (C E G . B-FLAT). The CAR of the last cons cell points to G and its CDR points to B-FLAT.
The primitives CONS, LIST, and APPEND seem very similar. Let's carefully examine how LISP evaluates these primitives when they are given two lists as input. Figure 3.2.2 show a cons cell representation of the input to CONS, LIST, and APPEND. Example 3.2.18 shows how LISP evaluates CONS, LIST, and APPEND given that input. The LISP evaluation is followed by a cons cell representation of the output.
The primitive RANDOM returns a random number.RANDOM expects a number as its input.RANDOM returns a random number between 0 (inclusive) and the value of its input (exclusive).
Example 3.2.22
3.3 LISP Predicates
Predicates are primitives that return a true or false evaluation. True in LISP is represented by the symbol T and false in LISP is represented by the symbol NIL.
An example of a simple predicate is SYMBOLP.SYMBOLP returns T if the data passed to the function is a symbol and NIL if it is not.
Another predicate is NUMBERP. It returns T if the data passed to it is a number and NIL if it is not.
The predicate FLOATP expects a number as input and returns T if its input is a float and NIL if it is not.
The predicate INTEGERP expects a number as input and returns T if its input is an integer and NIL if it is not.
Other predicates include ODDP and EVENP. These predicates expect a number as input and return a T or NIL evaluation if its input is a odd or even number.
The predicate ZEROP expects a number as input and returns a T if its input is 0 and NIL if its input is not zero.
The predicate PLUSP expects a number as input and returns T if the number is greater than zero and nil if the number is less than or equal to zero.
The predicate MINUSP expects a number as input and returns T if the number is less than zero.
The relational operators <, >, <=, >=, =, /= (not equal to) compare two or more numbers and return the result.
The predicate LISTP returns T if its input is a list and NIL if its input is not a list.
The predicate ENDP expects a list as input.ENDP returns T if its input is the empty list and NIL if its input is not an empty list.
Notice that many of the predicates presented thus far have ended in the letter P. There are some predicates that do not follow this naming convention.
The predicate ATOM returns T if its input is not a cons cell. Otherwise, ATOM returns NIL. Generally, anything that is not a list is an atom. The one exception is the empty list, which is both a list and an atom.
The predicate NULL returns T if its input is the empty list, otherwise NULL returns NIL.
Example 3.3.14
The logical operators AND and OR may be used to conjoin two or more forms. In LISP, numbers evaluate to T. Evaluation of AND and OR are based on the truth tables in Figure 3.3.1.
Figure 3.3.1
and
Form 1 | Form 2 | Evaluation |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
or
Form 1 | Form 2 | Evaluation |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
The predicates NOT and NULL return the same results.NULL is generally used to check for the empty list and NOT is used to reverse a T or NIL evaluation.
3.4 User-Defined Functions
To build programs that solve complex problems, it is necessary to write your own functions.DEFUN defines a named function . User-defined functions may be used just like the LISP primitives.
In Example 3.4.1, we define a function named my-c-chord that creates a list of the pitches C, E, and G.
The function name is MY-C-CHORD. The function does not expect any arguments as input. The function definition consists of a call to the primitive LIST that constructs a list of the atoms C, E, and G.
Call the function.
We call the function MY-C-CHORD with no inputs. The value returned by the function is the list (C E G).
In Example 3.4.2, we define a function that transposes a given key-number a given interval.
The function name is TRANSPOSE-MIDI-NOTE. The function expects two inputs, key-number and interval. The function definition is the sum of the two inputs. The value returned by the function is the summation of its inputs.
We call the function TRANSPOSE-MIDI-NOTE with inputs of 60 12 to transpose key-number 60 up 12 half steps.
We call the function TRANSPOSE-MIDI-NOTE with inputs of 60 -5 to transpose key-number 60 down 5 half steps.
In Example 3.4.3, we define a predicate function RANGEP that determines if its input is a valid MIDI keynumber, e.g. an integer in the range 0 - 127.
Example 3.4.3
The function RANGEP expects a number as input. The function definition uses AND to make certain that all three of the conditions are met before returning a T evaluation. The value returned by the function is T or NIL.
We call the function.
3.5 Getting help in LISP
It is a good idea to provide a documentation string for each function that you define. The documentation string is a string that describes the purpose of the function. For example, the function RANGEP documentation string may say, "A predicate function that determines if its input is a valid MIDI keynumber." The documentation string is added to the function definition after DEFUN but before the function definition.
To define a function that uses a documentation string, use the template:
You may access the documentation string of any function that includes a documentation string using the primitive DOCUMENTATION. The primitive expects two inputs: a name and if that name is a symbol or a function. Note that each of the inputs are preceded by a single quote so that LISP will not evaluate the inputs.
Using DOCUMENTATION, you may learn more about the user-defined function RANGEP.
Example 3.5.2
You may learn more about other Common LISP primitives such as CONSP using DOCUMENTATION.
Sometimes, you may find yourself wondering if LISP already has a certain function.APROPOS is a way to query LISP about its built-in functions.APROPOS returns the things that contain the object that is the argument to APROPOS.
APROPOS returns CONSP and describes CONSP as a function.
3.6 Error Messages
Error messages may be unsettling, but they are very informative when writing your own programs. Error messages may appear for many reasons, but one of the most common reasons is you did something Common LISP does not know about or the syntax has been violated.
Following, are some very common errors:
The prompt 1> indicates LISP has placed you in the debugger and that you've generated an error. Consult your Common LISP manual to learn how to your implementation returns you from the debugger to the interpreter.
Another common error is to pass the wrong data type to a function.
