CS 2360 Winter 95 (lab 04v.02)

lyman@cc.gatech.edu

Announcements

This lab has some code that you need to turn in; unlike previous labs.

Today's Topics

The topics to be covered today are:

The lab covers some topics that appeared to be problematical on the midterm. Additionally, it is a brief case study on using and constructing Abstract Data Types (ADT).

Prerequisites

Today's Lab requires that you have completed the previous labs. Additionally, it assumes that you have seen and at least partially absorbed the material up to from Lecture 7. It also assumes that you have:

Step 1. loaded (or evaluated) the init.lisp file that you downloaded in Lab 1.

Step 2. You should download the file ~gt7510f/2360/lab4.lisp at this time, also. Do not evaluate this file. Simply open it into a Fred Buffer.

P.S. For the actual lab sessions there were two files. lab4.1.lisp and lab4.2.lisp. This a, hopefully, a clearified version (v02 ) of the handout and there is one file lab4.lisp which is a superset of the material that is in the split versions. [ There is an additional very tricky evaluation example and a more "powerful" use of trace used. ]

Evaluation Revisited

There is a common intuition that people learn from their mistakes. This is only true is an analysis is done that determines why the mistake was made in the first place. When someone is using an interactive system and the system doesn't do what you expect it to, you have what is called, by people who study this sort of thing, an "expectation failure". We're going to practice "expecting" what evaluation will do.

The first section in the lisp file for this lab contains some expression that you will evaluate using the stepper. What you are to do is before evaluating the expression you should type into your file the value you expect to be returned in the appropriate spot. Then evaluate the expression. For example 

                   (step   (cons  '7 '(cdr '(a b))) )

                   ;;; Expectation:

                   ;;; Actual:
Note, you can ignore the step wrapped around the inner expression. Step will only return the value of the expression that is passed in. Remember also that step is a special form so its arguments are not evaluated. It is simply called for the "side effect" of allow you to step through the evaluation process.

Let say that I expected this expression to evaluate to ( 7 B ). I would enter this expression under the expression to be stepped before executing the step. Next I would position the cursor just to the right of the right most parenthesis and type Ctrl-C Ctrl-E to evaluate this expression. After stepping through the expression I would enter the actual result underneath my expectation. If the two do not match try to figure out why. If you are mystified as to what happened then ask your TA (or your neighbor or hack around with the Listener a bit).

Warning: not all of the expression are legal expressions. Some may drop you into the debugger.

By the way the above evaluates to: 

                             ( 7 CDR ( Quote ( A B )))

Numbers are self evaluating, but quoting them doesn't hurt (it is unnecessary though, you'd never should do that in real code.). The trick to this expression is that the cdr expression is quoted. Which means it will not be evaluated. So it becomes a list. Effectively the two following expression produce the exact same thing. 

                             (list 'cdr (list 'quote (list 'a 'b)))

                             '(cdr (quote (A b ))
At this point do the evaluation exercises in the lab4.lisp file now. Stop when you get to the section on Stepping Through a Search. The prelude to that is described in the next section.

ADT Fundalmentals

The lab4.lisp file contains a tree ADT. This ADT is used in a binary. All ADTs consist of two parts. An implementation and a set of operators. The implementation is a particular way of constructing the ADT from "lower", simpler, datatypes. These are the details that are being hidden from the user of the data type. The set of operators provided for the ADT usually fall into four types

Constructors and destructors create and destroy, respectively, instances of the ADT. All ADT have these operators. (Actually, in Lisp the destructors aren't necessary. We will always let the garbage collector clean up after us in this class.). After you implementation has been finalized you can write your constructors. Predicates answer true/false questions about your ADT. Selectors are functions that return "pieces" of information contained within the ADT. Operations are "actions" you can preform with your ADT. Ideally, these "actions" correspond closely with the "actions" that the algorithm you are trying to implement wants to perform.

So algorithms influence the design of ADTs and ADTs influence the design of algorithms. A sort of ying-yang sort of thing.

At this point, highlight from the start of the Tree ADT down to and including the search function. [Hold the mouse down and move to the bottom of the buffer. It will scroll automagically for you. Stop once have included everything including search. The place to stop is marked in the file.] From the Eval menu, select Evaluate Selection. [There is a way to do something similar in GNU Emacs.]

You could sit there and read all the operators that are defined for the tree ADT. They all have the prefix tree- . Or you go to the Tools Menu and select"List Definitions" and get an overview of the operations that are currently specified.

The Tree you are going to play with looks like this 

                                       Alexander

                                        /     \

                                      Moog     Worf

                                               /

                                             Kurn
Currently a tree has the following implementation. 

         A tree is either the empty tree  --->    ()

                             or an interior node --->   ( id  left-sub-tree 

                                                            right-sub-tree )

         where left-sub-tree and right-sub-tree are also trees. ( a recursive definition)

         A tree of height one might look like

                             (worf () () )

         The tree you are going to play with looks like:

                             (alexander  (moog () () ) ( worf ( kurn () () ) ()  )

Stepping Through a Search

Now let's step through a search of this tree. 

                   ( step   ( tree-search   'Worf   *tree1*  )   )
While you are steeping through this search try to anticipate what the tree-* operators will do before you enter that call. You may step over operators if you wish. If you step over the recursive call then all you will see is the answer.

An aside on Key arguments

We haven't used them in class but lisp functions can take optional and key arguments. These arguments are usually used to provide extra "nifty" features or to give the capability to modify the default behavior. Key arguments can be though of as "named" arguments. It allows the user to specify a particular arguments value. This is useful when there are multiple default behaviors that can be modified.

Or you can think of key arguments as optional arguments with names. Sometimes you would like to express a new value for the third "optional" argument without expressing values forthe first two. This is when key arguments come in handy.

The name of a key argument is given by a keyword. A keyword is a symbol prefixed with a colon. For example. 

                   :test

                   :initial-element

                   :foobar
are all keywords.

For example, type in the following two expressions into the Listener. (By default member uses eql to test for equality. ) 

                   (member '(a) '( (a) b c ))

                   (member '(a) '( (a) b c ) :test #'equal )
In the latter the argument with the name :test is given the value of #'equal. Its default value is #'eql. [ Try evaluating #'equal in the Listener if you are not sure what its value is. ]

You may see keyed arguments in some of your TA's and/or Instructor's code. Your functions need not provide them. They may be useful to use from time to time though.

Here are some more examples of using key arguments ( the first two aren't but they'll help you see why the second two look the way they do ).. 

                   (sort '( 1 5 4 2 ) #'>  )

                   (sort '("a" "b" "c" "d") #'string> )

                   (sort '((1 "a" ) (5 "b" ) (4 "c") (2 "d" )) #'> :key #'first )

                   (sort '((1 "a" ) (5 "b" ) (4 "c") (2 "d" )) #'string> :key #'second )

Tracing Through a Search

Go to the section of the lab4.lisp file that is marked "Tracing Through a Search". Read the directions and evaluate the necessary functions and/or expressions. When you get to trace that involves a key argument read the following paragraph.

So what does 

        (trace (tree-search  :before :print :step step-on-worf ) )
do? What this will do is "trace" the function tree-search. However, it will only print upon entering the function ( and not at all on exit ). And it will start the stepper when the step-on-worf function returns T. [ See the "Its Tool Time" page under the alternative resources homepage for more information on using the stepper and trace facilities for both MCL and LCL. ]

You should try tracing at this point. Once you land in the stepper press the EVAL button on the stepper window. Enter tree as the expression to evaluate.

As you should be able to see we've "skipped over" stepping through the other parts of the original tree. This is very useful when you know here you want to stop and step, but need to traverse a tangle of function calls to get there.

The downside is that you have to be able to write the correct Lisp expression that will stop you in the right place.

The example following this one in the lisp file uses break-step-on-worf which will drop you into the debugger. If you continue you'll drop into the stepper. This is useful if you want to check out the backtrace before you start stepping.

At this point you should have a pretty good understanding of what the opertors of the tree ADT do and what the implementation of the ADT looks like. You will modify and extend this ADT in the next section.

Modification of an ADT

Now we get to the "fun" part. Mr. Phelps, your job, should you choose to accept it, is to fly into Bosnia and rescue the ambassador...... Ooops wrong lab.

Your job is modify the tree ADT so that it can handle n-ary trees and so that each tree node contains some more information than is there now.

Currently a non-empty tree node contains the following information:

An empty tree is represented with the empty list, NIL.

Your job is to modify this ADT to handle trees with the following information:

To do this you did to follow four steps:

HINT: Do you really need to change the operator's interface or just their internals?

HINT: Do you need to change the tree-search code at all?

WARNING: As you change the ADT operators make sure to evaluate them. If you change them incrementally remember which ones have been changed and which ones haven't. If you have a new operator calling an old operator you likely to get inconsistant results.

NOTE: Interpret tree-left-child and tree-right-child to return the leftmost and rightmost children respectively. For a binary tree this is obvious. For an k-ary tree this is different.

NOTE: if you want to keep the old versions of these functions do a "Save As..." to save the file under a different name before you start to make modifications.

Life without ADTs

There is also a tree ADT operator called tree-messy-search. Here the writer violated the provided abstraction barrier willy-nilly. You job is to get tree-messy-search to work now that you have changed the underlying implementation. [ Once again, don't use the tree ADT operators. Write the appropriate Lisp code. ]

There is a tradeoff in layering your ADT operators. If you define you more sophisticated operators in terms of the more simpler ones then making a change to the implementation doesn't propogate into as many ADT operators as when you do not. However, you pay some "speed" cost in traversing the extra level of functions.

In this example tree-search is not an essential ( or fundalmental ) tree operator. So it kind of makes sense to use the more fundalmental operators to implement it.

Epilogue

You may turn in your code to your TA through email. You should really finish this in the next day or so. So as not to interfere with your work on Asgn 3.

You may also take the emacs competency test during lab also.