Introduction to Lisp
In this first programming assignment we will be introduced to the programming language Lisp. Lisp stands for LISt Processing, and is one of the oldest languages in continual use, having been developed in the 1950s. (Fortran is another language of similar age). There are a number of dialects of Lisp, the two most common being Scheme and Common Lisp. The book spends a fair amount of time talking about Scheme, however we will do our programming assignment in Common Lisp.
The actual programming assignment here is minimal. The major intent for this assignment is to make sure you know how to use the Lisp system on the college of engineering machines, as well as the web-based submission procedure. We will be using Lisp for the first several assignments.
The first part is a guided introduction to Lisp, which you should go through on your own but will not be gathered or graded. Notice, however, that homework 1 does cover much of the same material as the study section, and is graded.
The Lisp system we will use is called Gnu Common Lisp, and is started in response to the command gcl on the college of engineering machines. Lisp is an interactive language, which means that the user types commands in response to a prompt (the right angle bracket on our platform) and the expression is immediately evaluated and printed. Try entering the following:
% gcl GCL (GNU Common Lisp) Version(2.3) Mon Oct 16 15:28:00 PDT 2000 Licensed under GNU Library General Public License Contains Enhancements by W. Schelter > 3 3 > 3.14159 3.1415899999999
Note the roundoff errors in the value of pi. There are a few predefined values. The value t represents the boolean value true. the name nil represents both an empty list (more on that later) and the boolean value false. Try typing both of these and see what is returned:
> t > nil
(Hereafter I will simply print the expression to be evaluated, and you should enter it in the gcl system to see the result. You may want to write the result on this paper to help you remember what is going on).
Another feature of Lisp is the idea of a symbolic constant. A symbol, as it is known for short, is simply an unevaluated name. It has no other property than its name. A symbol can be formed by placing a quote mark before an identifier:
> `A
The major data structure in this language is the list. A list is constructed by placing the values in the list in a parenthesis. A quote mark must precede the parenthesis in order to avoid having the list be evaluated (more on that in a moment). Inside a quoted list it is not necesssary to quote symbols again:
> `(A B C)
Try leaving off the quote mark. You will get an error message and be dumped into a debugger. We aren't going to use the debugger in this class, so you can simply type :q (thats a colon mark followed by a q) to get out of the debugger.
The elements in a list can be anything; numbers, symbols, or even other lists.
> `(A (2 C))
The list is a universal data type. It can be used to represent almost anything. In particular, a list can be interpreted as an expression if we assume the first element is an operator and the remaining elements are values, in the fashion of a postfix polish expression:
> (+ 2 3)
(Make sure you leave off the quote mark, since this time we want to evaluate the expression, not simply create a list). There are certain advantages of this representation. For example, the number of arguments to an addition instruction need not be restricted to two:
> (+ 2 3 4 5)
Operations that in other languages would generate a boolean value will, in common Lisp, return either t or nil. Try entering a few expressions that evaluate true, and some that evaluate false:
> (< 2 3) > (= 2 3)
The comment indicator in Common Lisp is the semicolon. Any text between a semicolon and the end of line is ignored. Most often this features is useful when input is read from a file (see the end of this document on how to do this), however it can be used any time Lisp commands are read:
(+ 2 3) ; this shows a command and a comment
If lists are our basic data type, then we need operations to build up a list, and operations to break apart a list. The first is called cons, which is short for construction. The cons operator takes as arguments a value and a list, and creates a new list by attaching the value to the front:
> (cons 2 `(3 4)) > (cons `a `(b c))
A list containing only a single element can be formed by cons-ing the value on to the empty list:
> (cons 2 nil)The function append takes as argument two lists, and connects them end to end:
> (append `(a b) `(c d))Make sure you understand the difference between cons and append. Contrast, for example, the above expression with the following:
> (cons `(a b) `(c d))A value can be placed at the end of a list by combining cons with append. First a cons with a nil list is used to create a list with one element, and then this list is appended to the end of the first list: > (append `(2 3) (cons 4 nil)) To break a list apart the functions are called car and cdr (the latter pronounced could-er). These rather unusual names come from a pair of assembly language instructions on the IBM 704, the first machine used to write the Lisp interpreter. The function car returns the first element in a list, while a cdr returns the list with the first element removed:
> (car `(2 3 4)) > (cdr `(2 3 4))These operations can be applied repeatedly to access elements nested inside of nested lists:
> (car `((a b) c)) > (cdr `((a b) c)) > (car (car `((a b) c))) > (cdr (car `((a b) c)))Lisp is a functional programming language. It is also sometimes called an expression language. the latter refers to the fact that everything is evaluated as an expression. Even conditional instructions such as an if statement result in a value. Try entering the following:
> (if (< 2 3) 7 12)There are a number of predicate functions that test various properties of a value. For example, null will return true if the argument is the empty list, atom will return true if the argument is an atom (that is, a number of a symbol), symbolp is true if the argument is a symbol, numberp if the argument is a number, listp if the argument is a list. These are most often used in conjunction with an if expression:
> (atom 3) > (symbolp 3) > (symbolp `a) > (listp `a) > (null (cdr `(a)))Question, is the empty list an atom? a symbol? how would you find out? New functions are defined using the keyword defun. After the name of the function is the list of argument names, and finally the expression that will be evaluated to return the result. here is an example:
> (defun plusOne (x) (+ 1 x)) > (plusOne 42)Here is an example function that takes two arguments. The function returns a list with a value tacked on to the end, using the technique we investigated earlier:
> (defun addToEnd (x y) (append y (cons x nil))) > (addToEnd 5 `(2 3))Because lists are defined as a recursive data structure, Lisp programs tend to be highly recursive. Here is a program that will return the length of a list:
> (defun length (x) (if (null x) 0 (plusOne (length (cdr x))))) > (length `(a b c))Trace carefully the execution of this example so you can see what is going on.
; a comment is often used to describe the ; purpose and creator for a file (+ 2 3) ; this just adds two numbers (defun silly (x) (+ 3 x)) (silly 42)Note that these do not have the prompt, just the Lisp commmands. Now, restart the Lisp interpreter by typing gcl, and enter the following command:
> (load "LispTest")You should see some lines that indicate the file has been read. Now enter the following alternative version of the command:
> (load "ListTest" :print t )You should see the output from each line of the file executed one by one. For the Lisp programming assignments I want you to place your commands into a file, named progZero, similar to the one you just created. Place comments at the beginning of the file to indicate your name and the assignment number and date, but leave off your student ID number. To help you debug your programs I will give you a test script (from a link in the web page). To test your progran, load your file, then load the test script. The test script will print values in pairs, first your output and then the correct output:
> (load "progZero") ... > (load "testScript" :print t ) (a b c) (a b c) (2 3) (2 3) ...When you think you have the entire problem solved, hand in just your file using the college of engineering web-based form. At some later point I will evaluate your solutions using a different test script, and e-mail back your grade. For the zeroth programming assignment, create a file containing just a single recursive function, named sum, that will recursively compute the sum of the elements of an argument list. You can examine the testing script to see examples of input and output. Note that I want you to solve this problem using only the features of Lisp I have described in this document. In particular, there are Lisp statements (such as set or replaca) that allow you to program in an imparative style, if you want. I do not want. I want you to restrict yourself to the functional style.