lyman@cc.gatech.edu
Step 1. loaded (or evaluated) the init.lisp file that you downloaded in Lab 1.
Step 2. You should download the file ~gt7510f/2360/lab2.lisp at this time, also.
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.]
The 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. We 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. Stop once you get to the Visualizing Recursion point in the file. The introduction for that code is outlined in the next section.
To do this we're going to use MCL's trace facility. Like step, almost every implementation of Lisp has a trace facility. 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.
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.
Next let's try to trace the function factorial. 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 0
FIB returned 1
Calling (FIB 1)
FIB returned 1
FIB returned 2
2
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.]
step and trace are used as debugging tools. Now that you know about them
you can use them as such. You can also continue use them as learning aids too.
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 have to "Abort" and go back to the "Top Level." This section discusses more about effectively utilizing the debugger.
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 next line will tell you the name of the function that balked at processing your input. In
this example the error occured 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 discuss how to do that in a few.
Well in lisp, it is kind of a combination of both. You can insert a breakpoint by adding a function call. [NOTE: this is an example of non-functional programming. This function is called merely for it's side effect of stopping the execution. Nobody said that functional programming was a good paradigm for programs that do not work. :-) ]
At this time evaluate the two functions in the "Using the Debugger" section of lab2.lisp
buffer ( my-length-tr and my-length-tr-hlp )
Then evaluate the following expression.
? (my-length-tr '(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-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 dialog box by pressing on the "Cancel" button.
Select "Continue" from the Eval menu or select the "Return From Break" option and press OK. [ Effectively both of these do the same thing. ]
[NOTE: sometimes when you are N breaklevels deep and you just want to exit them all you can select the "Return to toplevel" restart, instead of using the "Abort" command N times.]
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 inpsector might be interesting.].
Click on my-length-tr-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-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.
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.]
Or three you can work on your homework. The Touretzky stuff is not required. They are just more tools to help turn you Lisp Environment into a better Learning Environment.
Open the link to "load_dst.lisp". Then choose "Save File As..." from the file menu and save the file to the 2360 folder on you gt-volume. Ditto for the MCL versions of dtrace.lisp and sdraw.lisp.
Load in the load_dst.lisp file into MCL. This will load all the other code to make the tools from the book work right.
You can learn more about these tools by looking in the book (see the index for the page numbers). Here are some very short descriptions.
(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 bother would probably lead to a mess, if it worked at all.)
(sdraw '(abc cbs nbc fox upn wb ) )
(scrawl '( (abc cbs nbc ) fox upn wb ))
Also you could try placing a break in one of the functions you traced (untrace the function first). And use that as an opportunity to examine the stack of a recursive function.