CS 2360 Fall 95 (lab 04v.02)
alex@cc.gatech.edu (Section A)
lyman@cc.gatech.edu (Section B)

Announcements

Assignment #2 should arrive back graded sometime before Friday. Maybe even Thursday. Solutions to Assignment #3 will arrive on the newsgroup later this evening.

Assignment #4 will be distributed next week. This is your week to catch up on your other classes. You should try to play around a bit with you favorite Lisp environment for a couple of hours sometime this week least you become rusty.

Remember to read the newsgroup.

The material to be handed in is marked [Hand In] in the lab. This lab make take longer than lab time to complete.....

Today's Topics

The topics to be covered today are:

Any other initial discussion, directions

Prerequisites

Today's Lab requires that you have completed the previous labs. In addition it assumes that you have already been introduced to the applicative programming functions (mapcar, apply, and funcall), and be familiar with all the material through Lecture 7 (the intro to data abstraction).

Step 1. Open the init.lisp file that you downloaded in Lab 1. Evaluate this buffer once opened.

Step 2. You should download the file ~cs2360/public/labs/lab4.lisp at this time, also. Then open the file. Don't evaluate it just yet.

Some More Conditionals

The lectures and book have almost exclusively made use of cond for doing conditional evaluation. There are three others that this section will introduce you to. The cond construct is actually the most flexible of the four and can be used in place of the others. The opposite is not true.

IF

This special form was introduced in the notes so I won't cover it again here.

WHEN

There is an alternate encoding for the case when you have an if with only the then expression. The format of the type of expression is: 

         ( when bool-expr expr [ expr ]*  )
The bool-expr is always evaluated. If the bool-expr is true then the following expression(s) are evaluated. The last becomes the value. So this is more accurately equivalent to a one condition cond expression than a if-then expression. Of course since you are only encoding functional programs you need only put one expression.

If the bool-expr is false NIL is returned.

In the lab4.lisp file you will find some expressions of this type to evaluate. Try them out now. [ NOTE: you may evaluate an expression by placing the cursor after the last right paren and pressing the Enter key. ]

UNLESS

This expression is the dual of when. Its expression(s) is only evaluated when the bool-expr is false and returns nil otherwise. The format is: 

         ( unless bool-expr expr [ expr ]*  )
In the lab4.lisp file you will find some expressions of this type to evaluate. Try them out now.

That Mapcar Thing....

In an effort to increase understanding what mapcar does your job is to implement it. In lab4.lisp you will find an augmenting recursive version of my-mapcar.

Your task is to implement my-mapcar-tr. The front end is already written for you also. All you need to do is add the helper function. [Hand In]

Next try the following. expressions 

         (trace my-mapcar my-mapcar-tr-hlpr )

         (my-mapcar #'(lambda (x) (cons 'a x)) '( () (b) (b c ) (b c d ) ) )

         (my-mapcar-tr #'(lambda (x) (cons 'a x)) '( () (b) (b c ) (b c d ) ) )

         (my-mapcar #'numberp '( 1 1.1  a "a" 2323 )

         (my-mapcar-tr #'mumberp '( 1 1.1 a "a" 2323 )

         (my-mapcar #'(lambda (x) 

                             (cond ((atom x ) x )

                                   (t 'some-list)))

                     '( 1 "a string "  ( a b c) 1.111 ) )

         (my-mapcar-tr ... same stuff as above ... )

That ASSOC Thing....

You next task is to write a more flexible assoc function. This function will allow the user to key on any component of the association. The code for bat-assoc is supplied as a reference. Your job is to write a new function called new-assoc. [Hand In] The skeleton of which is contained in the lab4.lisp file.

NOTE: the real version of assoc takes a variety of optional and keyword arguments to implement this.

You new function should take another parameter. Namely the function with which to extract the key from the association. Therefore, to make new-assoc behave like the assoc you would simply provide #'first as the extractor function (you could also supply car). Examples: 

         ?(new-assoc 'lyman '( (kurt prof ) (alex ta ) (lyman ta ) ) #'first )

          (lyman ta )

         ? (new-assoc 'ta   '( (kurt prof ) (alex ta ) (lyman ta ) ) #'first )

            NIL

          ? (new-assoc 'ta   '( (kurt prof ) (slex ta ) (lyman ta ) ) #'second ) 

            (alex ta )

          ? (new-assoc 'ta   '( (kurt prof ) (alex ta ) (lyman ta ) ) #'third ) 

            NIL

Assocation Lists and Binary Trees

In the Lecture on data abstraction you were introduced to he concept of graphs. And that graphs can be represent by lists and by association lists. Additionally, trees are special kinds of graphs. Namely there are graphs with no cycles. [where a cycle is a path that begins and ends on the same vertex/node]. We only going to play with a subclass of trees called binary trees. (For this exercises we'll also presume that the node are in sorted order.)

A binary tree of the form: 

                                       12 

                   7                                      14         

         6                   8                                      16

       3
Could be represented in an assoc-list in the following fashion. 

                   (  ( 12 7 14 )

                      ( 8 6  7 )

                      ( 6 3  nil )

                      ( 3 nil nil )

                      ( 7 nil nil )

                      ( 14 nil 16 )

                       ( 16 nil nil ) )
Now that you have had your background briefing. Your task is to implement the following functions. [Hand In]

Skeletons for these functions can be found in lab4.lisp. Examples provided below (to improve the presentation the tree above has been bound to the symbol *test-tree1* here and in the lisp file.) 

         (tree-right-child  12 *test-tree1* )  ==> 14

         (tree-right-child  14 *test-tree1* ) ===> 16

          (tree-right-child  16 *test-tree1* ) ====> nil

         (tree-left-child    12 *test-tree1* ) ===> 7

         (tree-left-child    6  *test-tree1* ) ===> 3

          (tree-most-left    12 *test-tree1* ) ===> 3

          (tree-most-left    8  *test-tree1* ) ====> 8

          (tree-most-left   14  *test-tree1* ) =====> 14
NOTE: is the code for most-left and most-right all that different. Could you write a function tree-in-most-direction-of which takes a function as an additional argument and implements both most-left and most-right when given the proper arguments? This is doing functional abstraction.

NOTE: the tree representation should not change while progressing through any recursive process.

NOTE: In actuality cyclic graphs are nice to represent with association lists. Tree, acyclic graphs, aren't as nice.

Regular Lists and Binary Trees

It turns out the Minister of Funny Walks doesn't particularly like association lists and what's you to implement the same ADT interface as in the previous section only using nested lists.

For example the tree. 

                                       12 

                   7                                      14         

         6                   8                                      16

       3
Could be represented in an assoc-list in the following fashion. 

                   (  12   (  7   

                                ( 6    (  3  nil nil ) )

                                ( 8  nil  nil ) )

                           (  14   nil 

                                   ( 16 nil nil ))   )

       

          Format:  empty tree NIL   otherwise   ( node  left-subtree right-subtree )
To differentiate from your previous solutions these will begin with two Ts. [Hand In]

Unlike the association list as you recurse the tree sent to the recursive call should be a smaller tree. The examples in the previous section should produce the demonstrate the same input/output behavior. There is a nested encoding of the above tree on the variable *test-ttree1* (Note the two Ts ).

Would you have to make any changes to the code that used this ADT interface?

Epilogue

Place all of the code you were required to write into a buffer and print it out with the usual info (like your Name).

You should feel comfortable with association lists, mapcar, and the benefits of data abstraction by the completion of this lab.