Problem Solving Lab #3
Lisp

This lab is being done in order to help you learn various topics discussed in lecture. For attendance, you will all be asked to submit to try. You should work in pairs, but if there are free machines you can work alone. You are not required to do anything if you don't finish (although you may want to try some of the exercises to increase your understanding of the material).

Part I - The Basics of Lisp

We are going to use the CMU Common Lisp version of Lisp that is found on the Sun machines. If you type lisp at the command prompt, you will go into the Lisp interpreter. You can type (quit) while in the interpreter you can exit back to the shell prompt. During this lab you may run into an error condition. In this case, you can type :abort in order to exit out of that particular interpreter error state.

As long as you are editing a file with the .lisp extension, emacs should enter lisp mode automagically. If it doesn't, then you can force it to enter lisp mode by with: M-x lisp-mode. You can also start lisp up in emacs by using M-x run-lisp. The lisp that emacs runs should be CMUCL Lisp.

If you would like more of a development environment, please read Using Emacs as a Lisp IDE (pdf doc).

If you would like to look at CMUCL documentation, please see the manual.

For now, let's get started on lisp. Please enter the lisp interpreter and do the following:

• Type the command (+ 2 3)
  You should see a 5 appear. Congratulations, you've just run your first piece of Lisp code!

• Remember that the first argument after a "(" will almost always be interpreted as a function. I say almost, because it won't be interpreted if it's quoted. So, if I want to make a list of numbers, I can do it like this:

  (setq my-list '(1 2 3 4))

  The quote in front of the list keeps all the arguments from being evaluated (in the case of lists of lists) and is is shorthand for writing:

  (setq my-list (quote (1 2 3 4)))

  Since all arguments are kept from evaluation, I can't write:

  (setq my-list '(1 (+ 2 2) 3 4))

  and have the resulting list be (1 4 3 4)). See the Quote Hints page for information on when you should quote and when you shouldn't. You can use the functions list, append, and cons in order to construct lists.

• If you want some arguments in a list to be evaluated and some not to, then you use a backquote and commas for everything that should be evaluated. Here's an example:

  (setq my-list `(1 ,(+ 2 2) 3 4))

• You should also be aware that the car function will return the first element of a list and the cdr function will return the rest of a list. car and cdr are old Lisp names that come from their implementation on the IBM 704 computer. car meant contents of the address portion of a register and cdr meant contents of the decrement portion of a register. In Common Lisp the newer functions first and rest are more often used.

  In Lisp, all list manipulations can be achieved with first and rest. Try creating a function for third and fourth for instance.

• Speaking of which, we should be able to define functions. The form of a function definition in Lisp is:

  (defun name-of-func ( params-sep-by-spaces ) ( function-body ) )

  Try defining a simple function to add two of its arguments together and call the function add-two. Then use the function and make sure it works. The last item evaluated in a lisp function will be its return value.

• At this point you might want to print out the one page Lisp document available on-line from here. If you want to download and just read it, use the ghostview postscript reader on the Suns. Look at the examples and run them to figure out how conditionals and loops work.

  At this point you should be able to create simple functions and run them.

  ---

  Working with Recursion

  The algorithm for summing a list of numbers is: add the first number to the second and then the running sum to the third and so on until the end of the list. Please write an iterative version of this loop in Lisp.

  Why not use Java if we're just going to write code like this? It would have a heck of a lot fewer parentheses and we wouldn't have to learn a new language. We should remember that in lisp our functions are supposed to be recursive. Write the same function, but make it recursive. Now look at your function. Is it tail recursive? If not, then write your sum function in a tail recursive manner. It helps the compiler and interpreter with efficiency.

  We still haven't made special use of Lisp, although we're already doing better than Java. Even with optimization (-O) turned on, a Java program with a recursive sum function runs out of stack space at fairly small numbers (try 10000). The Lisp program happily chugs along. If you want it to chug faster, put your sum function in a file called something like sum.lisp, then compile it with the command:

  (compile-file "sum.lisp")
  

  You can then load the function into the interpreter with:

  (load "sum")
  

  For practice, turn your sum function into a factorial function. As a reminder, the factorial of 5 would be 5*4*3*2*1. Try playing around with factorial in lisp. For large numbers you can get lisp to crash, but long before that java gives wrong answers and runs out of stack space. Because of the symbolic nature of lisp's numbers, you don't have to worry about whether they should be short, int, or long. Notice that Lisp's basic number crunching abilities appear to work well.

  ---

  Working with Recursion

• Download all the extras.lisp file and look at it.

• A note on variable naming conventions: names that look like +varname+ are normally constants in the program, names that look like *varname* are globals, and names are normally all lower case and separated by a minus sign.

• Currently, the replace function is written with an iterative loop. Rewrite it using recursion and test your code. Note that the difference between let and let* is that let* allows you to use the variable you just defined in the current variables definition, whereas let doesn't enforce the order of definitions, so you can't really do this.

• mapcar is an iterator that applies a function repeatedly, to each element of a list and returns a list of the results. It is a very useful function. See the definition of mapcar here. Write a call to mapcar that will return a list of the first elements of a bunch of lists.

• lambda is like an anonymous function in Lisp. Write a lambda function that will multiply its argument by 2 and then use mapcar to call this anonymous function on a list of numbers.

• (Extra) If you've done all the above, then start making your way through this Lisp tutorial and answer the exercises.

  ---

  Submission

  Each of you should submit (from your own account) to try an empty file called: here.txt. In order to create the file, type:

  % touch here.txt

  You will be told the command to use for submitting the file in your lab.

  Each of you should submit (from your own account) a file called reflections.txt after the lab is over. The lab will be due Thursday night. The goal of the file is for you to reflect on what you have learned in the lab, what you had problems with, what I could do better next time, what you would have liked to do, and to give me feedback about the lab. In order to submit this file, type:

  % try jdb-grd project33-1 reflections.txt

  This file will be due this Thur. at 11:59pm. with the late deadline being Friday at 11:59pm.