Notes and hints on Programming Project 2

Corrections to the original assignment handed out in class:

1. for operations on tree2, use call the function search not searchb
2. use the fucntion (quit), as it says in the Lisp Reference Guide, not (exit)

other notes

1. For part I, all you have to do is type things in (with quotes where necessary). For some of these, you won't get anything interesting when you type in quotes. The other option is to type in a (complex) cons function that is equivalent to the expression, and see what lisp returns.
2. Some of you have noticed that common lisp's idea of converting an sexpression to lisp form as much as possible is slightly different from what we did in class. In class we said that a list has to be either nil, or a cons cell whose cdr is a list. If it's a list, then you have parentheses around the number of items (even if some of these items might be dotted pairs that can't be lists). Otherwise, we said to use the dotted pair notation, with parentheses around each pair. What common lisp does instead, though, is to pretend that something is a list, and drop the dot if the cdr points to a cons cell (whether or not it is actually a list). So, for (cons 'a (cons 'b 'c)), where we would have said in class that this should be: (A . ( B . C)), common lisp will return (A B . C) If you are asked to do simplifications, you could use either form.
3. When you use setq to bind the top level value of an atom, you will see the following warning from common lisp:

   Warning:  Declaring  special.
   

   Just ignore this.
   ( For those who are really interested in what it means: special is common lisp's way of indicating a dynamically scoped variable. There are two ways to decide on the scope of a variable - this means if you haven't defined it in the local environment, how do you look elsewhere for the value. lexical scoping says you should look in the place where the environment was defined to see if there's a binding of the parent. An example is in slide lp30, the variable z was used in the lambda expression but not defined - this was borrowed from the surrounding lambda. Most algol-like langauges use lexical scoping. The other choice is called dynamic scoping, where the fucntion will look for the definition that called it. Most early lisp implementations used dynamic scoping. This was known for a while as the dynamic scoping bug, since it can lead to unpredictable results if you are not careful. Scheme and some more modern lisps used lexical scoping (fixing the bug). When they defined common lisp, many people wanted to use dynamic scoping as well, for backward compatibility. So common lisp is a compromise: it has both kinds of scoping - variables defined as the parameters to functions are (generally) static, and variables defined by setq are special (dynamic). You can actually mix and match these and get some very weird results in common lisp!)