Week 9 Discussion/Lab Notes

Administrivia

• stk is finally working on the lab machines, so you can use it to draw box-and-pointer or environment diagrams. Here are the instructions.
• Lab 10 next week is a big thought exercise. I expect everyone to think about it, but I won't require check-off.
• Remember to load tables.scm for your HW9 code.

Discussion Outline

(The long list of things I planned to talk about but was too tired to go through. Sorry!)

• hw6
• 2.79, 2.80 equ? and zero?
• when should you attach type-tags?
• type-tagging #t or #f is not necessary; they are not compound data
• even worse, tagging them as numbers is completely inappropriate!
• hw7
• side-effects vs. return values
• hw9
• 3.16 incorrect count-pairs
• you can only use 3 pairs!
• don't forget the initial pointers in your diagrams
• 3.17 correct count-pairs
• you should use your answers from 3.16 as test cases
• test cases like (count-pairs '(1 2 3)) are meaningless!
• don't use a global data structure
• memq vs. member
• 3.27 memo-fib
• just show a trace, don't draw the diagrams!
• using PC Scheme?
• set!, set-car!, set-cdr!
• are they special forms? why?
• set-car! and set-cdr! take pairs as their first argument
• Wilson Cheung's exercise:
• (define x (list (list 'a 'b) (list 'c 'd) (list 'e 'f)))
• how to change a to g?
• why is it important whether or not we create new pairs?
• (define L1 (list 'a 'b))
  (define L2 L1)
  (set-car! L1 'c)
  what's L2 now?
• MT1 box-and-pointer question
• efficiency
• recreating memory structures is expensive
• equality revisited
• eq? : equal? :: memq : member
• data structures
• tables
• below-the-line: list of subtables
• why does the textbook's implementation have *table* at the beginning?
• queues
• FIFO: first in, first out
• analogy: people standing in a line
• stacks
• LIFO: last in, first out
• analogy: a physical stack of dinner plates
• memoization
• store results so we don't have to recompute them

Data Structures

Now that we have mutable data, we have a lot more flexibility to manipulate lists.

It turns out that the list is a very flexible data structure. We can use a list to create a lot of other structures. (See the foreword to the SICP textbook, top of page xiv.)

Although data structures are the topic of CS61B, I think it's important to be introduced to several of them now. Two of the most common data structures used in computer science are the queue and the stack.

Queues

A queue is a data structure that stores some arbitrary items. Items in a queue are like people waiting in line; the items are handled on a first-come, first-serve basis. Queues are thus a FIFO (first in, first out) buffer.

Following the analogy to a line of people, the ends of a queue are known as the front and the rear. Items can only be added to the rear and can only be removed from the front.

Adding an item to the rear of a queue often is called enqueuing, and removing the front item is called dequeuing.

Queues are discussed and implemented in section 3.3.2 of the textbook.

Stacks

In contrast to queues are stacks. Items in a stack are like dinner plates arranged one on top of another; a plate can only be added to or be removed from the top. Stacks are thus a LIFO (last in, first out) buffer.

Following the analogy to a physical stack of plates, the ends of a stack are known as the top and the bottom.

Adding an item to the top of a stack is known as as pushing, and removing the top-most item is known as popping.

Exercise: Implementing stacks

Implementation: Why Dummy Headers?

Why do we need *table* as the first element in the implementation for tables?

First, as we already know, when we deal with many different kinds of abstract data types, it's often a good idea to use type-tags to distinguish one type from another. Dummy headers can perform this role.

This, however, isn't a complete answer, because in the case of tables, the *table* header really isn't optional. Why not?

(If you've completed my stack exercise, hopefully you already should understand the need for dummy headers. If you haven't done the exercise yet, go do it!)

The problem is that set! cannot mutate structures. set! can only modify bindings. To exemplify this, let's try to add an item to the beginning of a list without using dummy headers:

   (define (insert-front! lst item)
     (set! lst (cons item lst)) )  ;; WRONG

To add an item from the front of a list, we must change the initial pointer to the list. Is this possible with set!? Using the above definitions, will the following code work as intended?

   (define meta-vars (list 'foo 'bar 'baz))

   (insert-front! meta-vars 'qux) ;; WRONG
                                  ;; this does not mutate meta-vars!

The problem is that insert-front! cannot truly modify the initial pointer to the meta-vars list. When we invoke insert-front! we create a new frame and create a copy of the original pointer. When insert-front! calls set!, it's only re-assigning its local copy of the pointer, not the original one in the global environment.

This is a common problem when dealing with programming languages that use call-by-value behavior. Whenever a procedure is called, the procedure's parameters are bound to copies of the arguments. Scheme, like most other programming languages, behaves in this fashion.

(Note that when we invoke a procedure with a pair structure as an argument, a copy of the initial pointer is made, not a copy of the structure!)

The common workaround to this is to use an extra level of indirection. This means that we create an extra pointer to the item we really want to modify. In the cases of mutable data structures in Scheme, we create an extra, dummy cons pair to accomplish this.

Memoization

Memoization (not memorization, but the same idea) is the process of saving return values so we don't have to recompute them later. This is very useful when we need to perform expensive calculations repeatedly. Often the cost of of storing a value and looking it up again later is much less than recomputing the value from scratch.

Keep in mind, however, that memoization only saves return values. Consider what happens when we introduce side-effects!

First, here's a more general version of memoize that handles functions with any number of arguments:

   (define (memoize f)
     (let ((table (make-table)))
       (lambda args     ;; lambda equivalent of dotted-tail notation
         (let ((previously-computed-result (lookup args table)))
           (or previously-computed-result
               (let ((result (apply f args)))
                 (insert! args result table)
                 result) )) )) )

Now, for some examples with side-effects:

   (define x 0)

   (define count (lambda ()
                   (set! x (+ x 1))
                   x) )

   (define memo-count (memoize (lambda ()
                                 (set! x (+ x 1))
                                 x) ))

   (define hello (lambda ()
                   (display "Hello, world!")
                   (newline)
                   'okay) )

   (define memo-hello (memoize (lambda ()
                                 (display "Hello, world!")
                                 (newline)
                                 'okay) ))

What happens when we first call (memo-count) and (memo-hello)? What happens when we call them again? How is this different from repeatedly calling their unmemoized versions?