alex@cc.gatech.edu (Section A) lyman@cc.gatech.edu (Section B)
For this lab you will be handing in a printout of a Lisp file that you'll create. It is clearly marked by [Hand in]. Directions on how to construct this file can be found in the Epilogue. As usual make sure you name is in the file (least you not be able to find it in the deluge of printouts at the end of the lab).
Step 1. Open the init.lisp file that you downloaded in Lab 1. Evaluate this buffer once opened.
Step 2. You have downloaded, into your 2360 folder on your GT volume, the files in ~cs2360/public/labs/ of load_dst.lisp, sdraw.lisp, dtrace.lisp, and lab2.lisp. Then open the lab2.lisp file. Don't evaluate it just yet.
To do this we're going to use MCL's stepper. Almost every implementation of Lisp has a stepper (at least the ones you pay real money for). They are all invoked the same way, but once you are in the stepper the user interface varies from implementation to implementation. MCL uses a graphical interface to its stepper (what did you expect its a Macintosh). This is talked about in section 25.3 of Steele. However, you'll have to see your implementation's User's manual to get all the gory detail
To invoke the stepper you simply "pass" the expression you want to evaluate to the special
form step. [NOTE: step must be a special form since the arguments to all regular
functions are evaluated before the function starts to execute.]
Enter the following into the Listener.
? (step (+ 1 (+ 2 3 ) ( + 4 5 ) ))MCL will open a Step Window at this point. Press the "Step" button to step through the evaluation of this function (alternatively you can just press the RETURN key. That is what is indicated by the "Step" button having that "double border"). Once you have finished stepping that example that window should contain something that looks like:
(+ 1 (+ 2 3) (+ 4 5))
(+ 2 3)
5
(+ 4 5)
9
15The first thing STEP will print in this window is the expression to be stepped. Next any arguments to this expression that need evaluating are stepped through. For this example
(+ 2 3 ) and (+ 4 5 ) must be evaluated before the most outer + can be called. These
arguments are evaluated beneath the expression with an indentation of one. So (+ 2 3)
is stepped through yielding 5 and (+ 4 5 ) is stepped through yielding 9. Now that all
arguments have been evaluated 1, 5, and 9 can be passed to +, resulting in 15. The answer
is also displayed in the Listener.
Next try stepping through the following.
? (step (* (/ 1 2 ) (+ 3 4 5 ) (1- 6 )))NOTE: that last subexpression uses the
1- function. the is one symbol, no spaces. It
subtracts one from its argument.
When you have finished stepping through that one, move the Step Window down a bit. [Put the mouse cursor in the Title Bar of the window. Hold the mouse button down and drag.] You'll see your previous stepping session back there behind this window. These sessions hang around until you close the window. [The "close box" is on the left hand side of the Title bar. Click there.]
If you haven't already open up a Fred Window onto the lab2.lisp code that you downloaded from Prism. [Go to the File menu and select Open...] Find the section called "Visualizing Evaluation" in the file.
Your are going to step through some more complicated examples that have already been typed in for you. Just follow the directions outlined in the comments. Note that the last two examples involve special forms. You'll learn about these in an upcoming lecture. Just observe what happens even if you don't understand the code. You can come back to this lab code later after the lecture and redo those examples again.
To evaluate the examples simply highlight them using the mouse and choose Evaluate Selection from the Eval menu.
Stop once you get to the end of this section of the file. The introduction for the code for the next section is outlined in the next lab section.
Lisp provides a wide variety of functions to create, modify, and manipulate Lists. However,
sometimes it helps to know what is going on at a lower level. Or to know what (this is
a list) means to Lisp. Some folks have a hard time visualizing what a list looks like in
box and pointer notation.
Old timers pretty much don't care about box and pointer notation because the functions provided by Lisp just work and there is no need to worry about the nitty-gritty details of the implementation. On occasion you may want to construct some weird "thing" with cons cells. In those situations you need to know what's going on.
However, there is always an interest in this stuff so we're going to use the sdraw tool to play around with some s-expressions and see what they look like on at the implementation level. Besides your friendly TA won't always be around at 3 a.m. when you're wondering what the box and pointer notation of some hairy construct looks like. This way you can just ask Lisp.
At this time choose Open File Menu and open the file load_dst.lisp. You will find a block commented code that looks like.
#|
;;; On a OIT Mac, if you place these files in your "gtXXXX" volume.
;;; at the top level then you should replace the XXXX with whatever
;;; your gt number
(load "cs2360:dtrace.lisp" )
(load "cs2360:sdraw.lisp")
|#Change that section in the following way.
? (sdraw 'a )
? (sdraw '(a b ) )
? (sdraw '(a . b ))
? (sdraw '( c a b ) )
? (sdraw '( c a . b ))
? (sdraw '( c ( a b ) ))After finishing with these try out a few of your own. Remember to visualize result and then use the tool.
There are two special forms used in debugging. They are called step and trace. We used
step earlier in the lab to visualize evaluation. In this section we'll be concentrating on
trace.
All Lisp implementations come with a debugger also. You've probably encounter the debugger already. We purposely invoked it in Lab 1 so I could show you how to "Abort" and go back to the "Top Level."
The remainder of this section introduces you to some features not previously covered.
Here's a typical Error Message.
>Error: the argument FOO is a BAR, I was expecting a BAZ
> While executing: FRAP-MAKER
> Type Command-/ to continue, Command-. to abort.
> If continued: Return from BREAK.
See the Restarts menu item for further choices.
1 >The first line is the error message that the programmer specified to put up. Usually most messages will print the value of the offending argument. And if it is a type mismatch then the type of the argument and the type that the function was expecting. The word Error may be replaced with a Warning or Break. Warning are not fatal so execution continues. We'll look at breaks later.
The next line will tell you the name of the function that refused to processing your input. In
this example the error occurred inside the function frap-maker. This part of the message
gives you a clue as to where to start looking for your bug. If this isn't one of your functions
then you're going to have fun trying to find out which one of your functions passed on
something bad (we'll defer discussing the backtrace facility for now).
The final lines continue some information about how to explore the options that you have available. Some errors are non-terminal, and the debugger will allow you to dynamic fix the input and continue.
Type in the following
? foobar
....
1 > foobaz
....
2 > foo
.....
3 >
You are at this point at the third break level in the debugger. From the Eval menu choose the Restarts item. There should be several options you can choose. Notice that one of the options was to give
foo a value and continue. Choose
Return to toplevelat this time.
Note: that Abort, Break, Continue, Restarts are all grouped together on the Eval menu. there are all commands for interacting with the debugger.
[NOTE: this is an example of non-functional programming. These function are called merely for their side effect of printing and/or stopping the execution. Nobody said that functional programming was a good paradigm for programs that do not work.:-)]
The first strategy, in Lisp, would involve using the print function. There is a much more
capable output function. print is handy for debugging. This function simply prints the
value of its argument to the screen and returns that value as its result. Try these examples:
? ( print 23 )
? ( print "Ta da " )
? ( + ( print 3 ) (print 4 ) )This means you can wrap print around any expression and that value will be printed. At this point examine the function
my-length-tr in the lab2.lisp. Then highlight that
function and its helper function. Choose Eval Selection from the Eval menu. They try the
function out.
? (my-length-tr `(abc nbc cbs ) )We shall see later that
trace provides for slight more intuitive output in many situations
The other strategy involved using breakpoints. You can insert a breakpoint by adding a
function call, break. Examine again and look at the function my-length-tr-1. then
evaluate the two function definitions. Then evaluate the following expression.
? (my-length-tr-1 '(abc cbs nbc ))Which should bring up the following message in the Listener.
>Break: Check Backtrace to see if OK
> While executing: MY-LENGTH-TR-1-HLP
> Type Command-/ to continue, Command-. to abort.
> If continued: Return from BREAK.
See the Restarts menu item for further choices.
1 >
Note that the debugger message begins with the word "Break". Which means that you have now dropped into the debugger on purpose. It also prints the string that was given as an argument to break. [Alternatively you could can place
(break) in your code and a
default message will be displayed.]
The standard part of the message says that you can continue or abort at this point. It also says that you can check the Restarts menu item (which is on the Eval menu) for further choices. Do that now.
You are presented with a short list of options in this case. You can choose any of these Restarts by click on it with the mouse and pressing the OK button. Or you can get rid of the window by clicking in the close box in the upper left hand corner.
Select "Continue" from the Eval menu or select the "Return From Break" option and press OK. [Effectively both of these do the same thing.]
The "Backtrace" Tool allows you to look at the stack. The top pane of this window shows the functions on the stack. The bottom pane of this window show the arguments to the function highlighted in the top pane. The middle pane displays some information about the function highlighted in the top pane. The Commands menu allows you to, among other things, inspect this function. [If you're interested in the associated assembler code for this function the inspector might be interesting.].
Click on my-length-tr-1-hlp to see what the arguments are.
Then select "Continue" from the Eval menu (or press Command - /).
Then once again bring up the backtrace and check my-length-tr-1-hlp `s arguments.
You can use backtrace to find out where you function went awry if the error message states that you landed in some function that you have never heard of. Simply examine to stack for a function you have heard of and examine the values there.
To do this we're going to use MCL's trace facility. Like step, almost every
implementation of Lisp has a trace. And they are all invoked the same way. However
some have fancy options that others do not. Again you can see Steele 25.3 for nonspecific
discussion and your User Manual for a lot more detail (or the Lisp Guild hall for some
mini-tutorials).
To trace any function you merely type:
? (trace function-name)or
? (trace function1 function2 ... )The latter traces all the function names listed.
Trace is a special form so you do not have
to quote the arguments. To see a list of all the functions currently being trace just enter
(trace) to the Listener. To turn off tracing of a function you simply call (untrace
function-name).
At this point go to the lab2.lisp buffer and evaluate the functions my-length,
factorial, and fib. The first two are examples of "linear" recursion and the third of
"tree" recursion. Turn on tracing for all of these functions. [Do not evaluate the functions
in the section marked "Using the Debugger" yet.]
First, let's trace through my-length. Try the following.
? (my-length '() )
? (my-length '(abc cbs nbc fox upn wb ) )You should be able to see why this is called "linear" recursion looking result of the trace. Your trace should resemble the following.
? (my-length '(abc cbs nbc fox upn wb ))
Calling (MY-LENGTH (ABC CBS NBC FOX UPN WB))
Calling (MY-LENGTH (CBS NBC FOX UPN WB))
Calling (MY-LENGTH (NBC FOX UPN WB))
Calling (MY-LENGTH (FOX UPN WB))
Calling (MY-LENGTH (UPN WB))
Calling (MY-LENGTH (WB))
Calling (MY-LENGTH NIL)
MY-LENGTH returned 0
MY-LENGTH returned 1
MY-LENGTH returned 2
MY-LENGTH returned 3
MY-LENGTH returned 4
MY-LENGTH returned 5
MY-LENGTH returned 6
6The call sequence "indents by one" with each recursive call. And does the reverse as it exits. If you rotated this trace counter-clockwise 90 degrees you would "see" a line that slopes up. It then comes to a "point" at the base case (or stopping condition). And then slopes down until exit. It is going to take O(n) time to calculate the answer to this function (both the tail and augmenting recursive methods are O(n) in time. The tail recursive one need not be O(n) in space though.)
Next let's try to trace the function factorial. First you must finish defining factorial.
The skeleton for the function is in the lab's lisp file [Hand In]. Try the following:
? (factorial 2 )Which results in:
Calling (FACTORIAL 2)
FACTORIAL returned 2
2Hey! How come it didn't trace? That's covered in the next subsection read on.
Alternatively, you can go back to the definition of factorial and uncomment the line.
;(declare (notinline factorial ))[Just remove the semicolon.] And then evaluate the definition.
Lisp allows the programmer to "talk" to the environment through calls to declare. In this
call we're telling MCL not to in-line, and therefore remove the recursion, of this function.
If you ever try and trace a function and it enters and exits with doing any recursion you
might try and add one of these declarations. Try tracing (factorial 2) now.
? ( fib 3 )That should result in the following.
Calling (FIB 3)
Calling (FIB 2)
Calling (FIB 1)
FIB returned 1
Calling (FIB 0)
FIB returned 1
FIB returned 2
Calling (FIB 1)
FIB returned 1
FIB returned 3
3
The "shape" of this trace looks different from the "linear" one. Here the answer to
(fib
3) depends not only on (fib 2) but also on (fib 1). If each call where a "node" then
is you connected who called whom you would have a tree. The above trace corresponds to
the following tree:
(FIB 3 )
(FIB 2 ) (FIB 1 )
(FIB 1 ) (FIB 0 )
Where (fib 1) and (fib 0) are the leaves of the tree. Why? .... because they are the
base cases of the recursion.
Try out a slightly larger example to see more of the tree.
[You may have heard there is a straight forward transformation between tail recursive functions and a process using iteration. Even most simple Lisp compilers can remove these. MCL also can remove recursion "patterns" that look like fibonacci. Why? Because fib is a standard Lisp benchmark is one reason. Because they (the MCL authors) could, is another.
This is why fib needs a notinline declaration too.]
The following appendix has more discussion on the code from Touretsky's book. That code will also load into LCL on the OIT Unix boxes. It is portable, however the sdraw package often does require some minor tweaks to get the I/O working properly. I made these for LCL and MCL.
There is also a short section on fixing broken recursive functions. A similar exercise will likely appear in next week lab so if you tackle it now you'll be one step ahead.
[ Hand In ]. To hand in your solution to the lab first create another Frew Window with
New from the File Menu. Cut and Paste the required functions into that window. Add
your name to the code and then print out this new buffer.
(dtrace function-name )
(duntrace function-name )These new tools don't clobber the default ones. You can only use one on a particular function at a time. (trying both would probably lead to a mess, if it worked at all.)
(sdraw '(abc cbs nbc fox upn wb ) )Some folks tend to get confused about the different between cons and append. Try to predict the result of each of the following and then use sdraw to see what the result really is. (i.e. just wrap the call to sdraw around each of the following.).
(cons 'a '( b c ) )
(cons '() '(b c ) )
(append '() '( b c ) )
(cons 'a '() )
(cons '(a) '() )
(append '(a) '() )
(cons '(a) '( b c ) )
(append '(a) '( b c ) )
(cons '((a)) '(b c ) )
(appeand '((a)) '(b c ) )
(cons '(a b ) '( b c ) )
(append '( a b ) '( b c ) )
(scrawl '( (abc cbs nbc ) fox upn wb ))Sometimes it is useful to be able to crawl around inside of a complicated s-expression. For instance you my wonder what calling:
( car ( cdr ( cdr ( car complicated-expression))))
would result in. You can do this with the scrawl function. At the Listener invoke the
following:
? (scrawl '( c ( a b ) ) )What should appear in the screen is something similar to the result of invoking sdraw. Notice that the prompt has changed now. You are no longer talking to the Listener. Your talking to the scrawl now. Type h now. (Not `h just h the character). The legal commands will be shown.
Use scrawl to move around in this expression. Enter Q to get back to the Listener.
Try this again on an expression, or two, of your own choosing.
First let me remind of two commands that are on the Eval menu. They are "Abort" and "Break". Abort will "kill" anything that is executing currently. "Break" will stop it and drop you into a break loop.
That said make sure that fib is still being traced.
?( trace )Then invoke the following in the Listener and then after a second or so select "Abort".
?(fib -1 )That is an example of a recursive program out of control. What would you do to fix this problem? I leave that as an exercise for the reader.
We are going to try and fix the last function that appears in lab2.lisp. Evaluate the function
find-id-in now. And then evaluate the following expressions. [You'll need to "Abort"
because it is broken.]
? (trace find-id-in )
? (find-id-in 'fox '(abc cbs nbc fox upn wb ))
After aborting you'll see the following:
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
Calling (FIND-ID-IN FOX (ABC CBS NBC FOX UPN WB))
A sure sign that a recursive function is broken is if the inputs do not change on each recursive call. Remember recursive means to break a problem into smaller pieces and recursively do the smaller piece. So now you know the symptom associated with that disease. What needs to be added to the function to make it recurse properly? Fix it and then check that your fix works. We're not done yet though....
Next try the following.
? (find-id-in 'hbo '(abc cbs nbc fox upn wb ))Abort when you see the pattern not changing. The non changing pattern is.
Calling (FIND-ID-IN FOX NIL )This is the symptom of the "I forgot to include the base case" disease. Add a base case to the function (i.e. return NIL if the id is not found.). Then Evaluate the function and see if it does now indeed work correctly.
[NOTE: you could have also invoked a "Break". This would have allowed you to then bring up a "Backtrace". That method is handy when you are not already tracing the function or if you are interested in the arguments to a function that called your errant function.]