CS 2360 Fall 95 (lab 03v.02)

alex@cc.gatech.edu (Section A)
lyman@cc.gatech.edu (Section B)

Announcements

There is a midterm on Thursday. Asgn 3 will be out late this evening. Asgn 1 should be returned to you by now.

Today's Topics

The topics to be covered today are:

The labs explores some ADT terminology. It also looks at functions as first class data objects and at the abstraction of processes.

Prerequisites

Today's Lab requires that you have already completed the previous labs. You should know what an Abstract Data Type is and have good grasp of the material up through and including lecture 5 on Applicative programming. For this lab you will need to initially take these first two steps.

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 file ~cs2360/public/labs/lab3.lisp. Then open the lab3.lisp file. Don't evaluate it just yet.

ADT Fundamentals

Many of the functions your created for assignment 2 operated on the List Abstract Data Type (ADT). 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.

Other classes may have used different terminology for talking about ADT. In this section you will learn about some terms that help you categorize the functions associated with an ADT. 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 your choice of the underlying 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.

In your solution file for this lab replicate the following table with the answers filled in, of course. For the List ADT classify this functions associated with the ADT.[Hand In]. 

         Function                      Classification

       

          append                         _________________

          reverse                        _________________

          first                           _________________

          second                         _________________

          rest                           _________________

          member                         _________________

          subseq                         _________________

          make-list                      __________________
If you perused Steele you will find out that a List is a type of Sequence. All the Sequence operators work on Lists (as well as any other specialized type of Sequence).

First Class Functions

In Common Lisp (and all more strictly Functional Programming Languages) functions are first class datatypes. A first class datatype is datatype that can be used in the ways that primitive datatypes can be used. Namely, variables may be assign/bound a function for a value. Functions may be passed to another function as an argument. And a function may be returned result of a another function.

The special form function is like quote. Only it returns a function instead of a symbol or a list. Try the following in the Listener. 

           ?  (function car )

            ?  (defun mumble ( arg1 arg2 ) (cons arg2 arg1 ) ) 

            ?  (function mumble )

            ?  #'mumble
The last is the Common Lisp shorthand for calling function. It is similar to the shorthand for calling quote.

No Named Functions

You can create a function that isn't bound to any name using lambda. This function is going to return a function as it's result. In order to capture the functional value it returns you must wrap a call to function around it (or place the shortcut in front). In a strictly functional language this wouldn't be necessary but you'll just have to remember this as a special case. For example the above mumble function is really not all that interesting enough to give it a permanent name. Try the following in the Listener. 

         ?  #'(lambda ( arg1 arg2 ) (cons arg2 arg1 ) )
MCL will probably tell you that this is some sort of function or lexical closure. What exactly a closure is will be covered in the following weeks. For now you need on know that this is a function. How do you know? Just ask the Listener. 

          ? (functionp #'(lambda ( arg1 arg2 ) (cons arg2 arg1 )) )

                 T
Test to see if #'cons and #'car are functions too.

You may invoke functions by using the function funcall. Take a gander at what the Listener returns when you type in the following. 

         ? (funcall #'+ 1 2 3 4 5 6 )

         ? (funcall #'cons 'ds9 '( stng  st ) )

          ? (funcall #'max 3 5 2 7 3 )

         ? (funcall #'(lambda ( arg1 arg2 ) (cons arg2 arg1 ) )

                     '( stng st ) 'ds9 )
There is another function where the arguments must come in the form of a list. See the lab3.lisp file for examples of it. The name of this function is apply. The last argument to this function must be a list. Otherwise, it behaves just list funcall.

You should start to get the feeling to there is more to the functional programming stuff that simple Lisp hacking.......

Abstraction of Procedures/Processes

Remember your solution to substitute on assignment 2. It probably look a something like the following (with the args rearranged a bit): 

         (defun my-subseq ( mylist new-elem  old-elem )

            (cond ( (null mylist) nil )

                   ( (eql old-elemnent (first mylist ))

                     (cons new-elem (subseq (rest mylit ) new-elem old-elem )

                   (t (cons (first mylist )(subseq (rest mylist) new-elem old-elem))))))
From lecture you should remember that Abstraction is the process of removing the unimportant details and leaving behind what is important. In that frame of mind we might abstract the above and convert it into: 

         (defun general-replace ( mylist new-elem  predicate )

           (cond ( (null mylist) nil )

                  ( (funcall predicate (first mylist ))

                    (cons new-elem 

                          (general-replace (rest mylit ) new-elem predicate )

                 (t (cons (first mylist )(

                           (general-replace (rest mylist) new-elem predicate))))))
This doesn't look all that much different. However, the predicate that was used to trigger the replacement has been abstracted out. The new function can be presented with any predicate and do replacement. Evaluate the above function in the file lab3.lisp. Then try the examples that are outlined in that file.

You are to write the following six functions and hand them in [Hand In]. The name of the function is in the left column and the predicate you might find useful is in the right. 

                   Fcn Name                               Predicate

                   replace-all-atoms                      atom

                   replace-all-lists                      listp

                   replace-all-negatives                  negativep

                   replace-all-zeros                      zerop

                   replace-all-integers                   integerp
You are to replace with the expression '(replaced) so you can tell what get replaced. Examples: 

       (replace-all-atoms '( (a b ) c ( d e ) )   ==> ( (A B ) (REPLACED) ( D E ) )

       (replace-all-lists '( (a b ) c ( d e ) )  ==> ( (REPLACED) C (REPLACED ) )

       (replace-all-negatives '( -1 (A B) 2.0 ) ==>  ( (REPLACED) ( A B ) 2.0 ) )

       (replace-all-postivies '( -1 ( A B) 2.0 ) ==> ( -1 ( A B ) (REPLACED) ) )

       (replace-all-integers  '( -1 ( a b ) 2.0 ) ==> ( (REPLACED ( A B ) 2.0 )  )
There is a hard way to do this. And then there is the easy way. The easy way might involve using our abstracted/generalized friend up above.

Mapping Over Lists

Sometimes you would like to apply a function to a whole list of items. The mechanism for doing that is called mapping. There are server mapping functions available in Lisp. The one you'll probably use the most is mapcar. Mapcar applies a given function to each of its arguments and collects the result of each application into a list. This list is returned as the result. Try out the following 

         ? (mapcar #'atom '( a b (c d ) )

          ? (mapcar #'1-   '( 1 2  3 4 5 ) )

          ? (mapcar #'+    '( 1 2 3 4) '(10 20 30 40 ))

          ? (mapcar #'remove-duplicates '( (1 1 1 2 3 )( a b c d e e ) (+ + - -)))
There is a functions and exercises for you to complete in lab3.lisp.

Epilogue

This lab should have given you a feel for what you can do with functions. You now know about a function that creates a function, lambda. A function that can invoke a function, funcall. And a function that can invoke a function a bunch of times and create a new list of answers, mapcar.

You should have inserted the material to be handed in into a new buffer. In this buffer put your name and then print out your solutions.