Notes for Lecture 4 - Tuesday September 14th, 2004

• Return to the main StudentFrontPage.

• Scribe = Mike Foss
• Editor =
• Editor =
• Editor =
• Editor =

See also September14SortInstructions

Administrivia

Add/Drop

Lynn will not be around after about midday tomorrow, but this is ok with Linda. If you have problems with the add/drop process, don't sweat it.

New Problem Set

The beginning of next problem set is posted now.

TA

Katie is a TA for this course! Yay Katie. Look for Katie to answer questions if Lynn is not around.

IM issue

When IMing Lynn, please let Lynn know who you are if your screenname is unrelated to your actual name.

First Half of Higher Order Procedures(to be continued Friday)

One of the properties that make Lisp Lisp is that it treats procedures just like everything else. It also allows you to isolate "environments" and use them later on in code. This is called a continuation. Today, we will explore how to use Lisp's treatment of procedures to create "higher order procedures" which manipulate other procedures.

Comparison

Let us first consider the scenario where we want to take several students and compare their birthdates, sorting them according to this comparison. It might look something like this:

(define sort 
   (lambda (students birthdate-comparer)
.
.
.
   (if (birthdate-comparer s1 s2)
      sorting stuff + recursion)) 

In this execution, we don't actually know how birthdate-comparer works, but we know that it will return a boolean based on the birthdates of the students given. We might write this as:

(define bday-comparer
   (lambda (s1 s2)
     (if (< (bday-of s1) (bday-of s2))
          #f
          #t))) 

This is an example of passing procedures in Lisp! In the sort function, we just said that we would need a birthday sorting procedure, but we actually created the procedure elsewhere. So in Lisp, you can pass procedures just as any other type of data. Thus, we can see this in action in the following example:

(sort focs bday-comparer)

This calls the sort function with our specific implementation of the comparator. Random note: It is not uncommon to see a new lambda expression in the middle of scheme code.

"Mapping," etc. Shown as Higher Order Procedures

Let's look at something we're pretty familiar with now:

(define (increment-all lst)
   (if (null? lst)
     '()
     (cons (+ 1 (car lst))
           (increment-all (cdr lst)))))

Thus, increment-all will add one to each element in the given list and return the modified list.

We could also do something else with this list, such as square it:

(define (square lst)
   (if (null? lst)
     '()
     (cons (sqr (car lst))
           (square (cdr lst)))))

So as we cdr down the list, we modify the car the same way each time. And by "the same way," I mean that we call the same procedure to work its magic. This is done so often that there is a special function called map which handles this. map looks like this:

(define (map proc lst)
   (if (null? lst)
     '()
     (cons (proc (car lst))
           (map proc (cdr lst)))))

So map will automatically cdr down the list for you! It takes the procedure you give it and applies it to the entire list in the same way we've been doing. So now we know another way to write square using our new procedure.

(define square
   (lambda (lst)
     (map sqr lst)))

And voila! We have a list with each element squared. There are two other built-in functions like this: filter (which only allows elements which pass some test procedure to be a part of the resulting list; and accumulate. These are 3 higher order procedures in that they manipulate other procedures. The important (big) idea is that we're passing procedures around in order to help break down problems. This is a valid way to process infinite data structures.

Some More Random Notes

Compiled languages have more types than interpreted.

Signal processing extractions are an important way to think about scheme.

We can use the filter paradigm rather than cdr down the list in order to implement a webcrawler.

Trees

What is a Tree?

The abstract data types we have talked about so far are lists, arrays, collections, stacks, & queues--all of which can be represented as a line. Not all data is structured this way, however. For instance, when you retrieve the shtml from a webpage, it is not initially structured as a linear list. For example: (3 + ((2 * 6) - 1)) This data structure is called a tree . The following is a better visual way to represent this:

     +
     /\
    3  -
       /\
      *  1
     /\
    2  6

Every operation (+, -, *) is a node of the tree. Each node may have children, which branch out from the node. If each node has no more than two children, the tree is known as a binary tree. In this case, each node has a left child and a right child. If we want to add the procedures insert, delete, and member? to a tree, we can implement it as a collection. But we need to know this: for any given node, what is its data and what is its children? Sadly, these are three pieces of information (datum, left child, right child) and Lisp is best suited for two pieces of information at a time (because of the basic unit of data, the cons cell). Thus, Lisp is optimized for lists and not trees, but there are still many ways that we might implement a tree. One common way to resolve this is this type of structure (picture it in terms of boxes):

(datum .(leftSubtree .(rightSubtree . ()))) or [datum| ]-->[leftSubtree| ]-->[rightSubtree|()]

So we can create an abstraction for Lisp to implement the tree data structure. It might consist of the following: (make-tree dat L R) ;; output the tree containing these data (node data, left child and right child) (tree-datum tree) ;; output the data in the top node of the tree (tree-left tree) ;; output the left subtree of the given tree (tree-right tree) ;; output the right subtree of the given tree (leaf? tree) ;; output the boolean whether the given tree is just a leaf (tree? tree) ;; output the boolean whether the given tree is actually a tree

In a structure based language, it may be easier: Tree: data datum; Tree left, right;

If you want to go up the tree, you may need a parent pointer. A nice algorithm exists for garbage collection pointing. A tree-walk is very commonly done in a functional style.

Another thing you may want to do with a tree is to print it out in a nice style such as in order traversal. Every time you go down to the left is an open parens, up to the right is a close. The result of such a traversal has this form: (Lchild datum Rchild). Representing the example tree in this form, we have (3 + ((2 * 6) - 1)).

Class Exercise

Now we compare three different sorting algorithms:

All of these algorithms are of the order O(n^2).

See also September14SortInstructions

Please add to this page if something is left out, something needs to be clarified, something needs to be pretty, or anything else!