Notes for Lecture 3 - Friday September 10th, 2004

• Return to the main StudentFrontPage.

• Scribe = Katie Rivard
• Editor = Mike Foss
• Editor =
• Editor =
• Editor =

Problem set due Tuesday

Problem set is up(linked from StudentFrontPage). There is a new question to turn in. The problem set is not quite complete yet -- there will be a few more questions(hopefully by midnight tonight).

Handouts

1. Abstract Data Types - from Computer Algorithms

2. Orders of growth - from Data Structures and Algorithm Analysis

3. Quick page on scheme - from The schematics of computation

4. Essay "Revenge of the Nerds" on Lisp, by Paul Graham - from teh intarnet (google Paul Graham)

Chris made a Clicker without needing java applets

Isn't that cool? We all love clicker. You can find it at http://lemming.research.olin.edu/clicker/

More Scheme!

• === Regarding Queue stuff ===
  • ==== Count-atoms ====

    • The point: learn about cdring down a list.

    • Lists:
      • The empty list: [/] is a list

      • Any structure that ends in an empty list is also a list: [1|-]>[2|/]

      This is going to be like inductive proofs: a base case, and then do something to make every other case reduce to the base case.

      (define (count-elements lst)
        (if (null? lst)
            ;;0 elements in an empty list
            0
            ;; any other list is how many are in the cdr, plus one
             (+ 1 (count-elements (cdr lst)))))

      > (count-elements '(1 a (x.3)))
      3

      Which is correct -- three elements. Why does this work? Let's do a test case:

      • start with [1|-]>[a|-]>[[x|3]|/]

      • the list is not null, so next iteration: calculate for cdr!

        • [a|-]>[[x|3]|/] is not null, so next iteration: calculate for cdr!

          • [[x|3]|/] is not null, so next iteration: calculate for cdr!
            • [/] is null, so return 0
          • 0 + 1 is 1
        • 1 + 1 is 2
      • 2 + 1 is 3
      • 3 is the answer!

      Notice the first-in-last-out characteristic -- the first iteration has to wait until all other iterations have returned before it can proceed. This is a stack! When you get a "Stack overflow" when running a program, this is exactly what's happening -- you've pushed too many things onto the stack, and the computer is sad.

      Also notice that we didn't care what the precise structure or contents of the cons cells were, just that they were null or non-null.

    ==== Sum elements ====

    • This one actually cares what's in the car of the cons cell.

      (define (sum-elements lst)
        (if (null? lst)
            0
            (+ (car lst) (sum-elements (cdr lst)))))

      > (sum-elements '(1 3 4 5))
      13

      Which is correct.
    ==== Incrementor ====
    • We now have a structure that knows how to cdr down a list. It's one step further to make something that can operate on every element. We want a procedure that will increment every element of a list by 1, and return the new list.
    • Base case: empty list. Should return: empty list.

    • Other cases: do something on the result of the cdr of the list.

      • this "something" -- is to cons the car of the list plus one onto the result of the increment of the cdr. (whew)

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

      We can also add some error-checking, to make sure elements are numbers:

      (define (increment-all lst)
        (if (null? lst)
            '()
            (if (number? (car lst))
                (cons (+ 1 (car lst)) (increment-all (cdr lst)))
                (display "oops! bad data"))))

      number is a data type -- Scheme has lots of convenient *? procedures like this. This isn't precisely awesome error-checker, since if you give it bogus data it does this:

      > (increment-all '(1 2 3 "a" 5))
      oops! bad data
      (2 3 4 . #<void>)

      Because #<void> is what is returned by display. There are much more robust ways to error-check. Our procedure also doesn't check to see if it's been given a well-formed list, but bah.

      Notice how in increment-all we accumulated our answer using cons, and made our way down the list using cdr. These are very common ways to deal with lists in Lisp. Remember these. You should now have enough stuff to complete Queue. yay!

    ==== finally, the queue abstraction ====

    • enqueue elt q: the new q (adds elt to "back")

    • front q : the "front" elt

    • dequeue q : the new q (w/o "front" elt) enqueue:

      easy	prettier
      cons	cdr down the list, carrying elt with us cons up answer w/ new element

      "prettier" implementation:

      (define (enqueue elt q)
          (if (null? q)
              (cons elt '()) ; or (cons elt q)
              (cons (car q) (enqueue elt (cdr q)))))

      Main thing to note: for base case, previously we've just returned nil. Here, we're returning a new cons cell with the new element included.

      The prettier implementation makes dequeue and front really, really easy -- cdr and car of the queue, respectively. Using the easy implementation of enqueue, dequeue and front become the more complicated operations.

      A note: Scheme isn't "academic" -- it's Beautiful. :)

      In general, we want to ask appropriate questions to decide which implementation to use -- are we enqueueinig things a lot, and dequeueing things and fronting things not so much? Then easy is reasonable. In real life, we probably enqueue and dequeue equally, so this doesn't matter so much. However -- if we almost always call front before dequeueing, we certainly want the pretty version, because car is a much shorter operation(O(1)) than a string of cdrs(O(n)).

      There is a thing called a priority queue which dequeues things according to a value indicating how important they are, rather than simply by the order in which they were entered into the queue.

  ==== Common Orders of Growth ====
  • cons, car and cdr are all O(1) or \theta(1).
  • cdring down + consing up a list is \theta(n).
  • cdring down a list is \theta(n)
  === Tail Recursion ===

  • If you can write code in such a way where there are no deferred operations -- I don't need to do anything with whatever the guy in front of me gives me, I can just have him return his answer to whoever called me -- that is as efficient as a loop, does not require a stack, and can be done with far fewer resources (if your lisp machine is designed to take advantage of it. Most are).

    The following is a tail-recursive implementation of front for the "easy" front-of-list enqueuer.

    (define (front q)
      (if (null? (cdr q))
          (car q)
          (front (cdr q))))

    Note that the non-base case just returns the result of the next iteration -- doesn't need to do anything with it. Lisp will see this, and do the Right Thing. (tail recursion is not just Lisp-specific -- it is a special feature of most functional programming languages, and other languages which use recursion heavily in this way) To see if something is tail-recursive, take a look at the recursive call. If it stands alone as the return value of the procedure, and the thing doesn't need to do anything with that answer, then the procedure is tail-recursive.
  • === Queue: Array version ===
    • An array is a row of numbered mailboxes. For an array-queue, you would keep track of:
    • 0[] 1[] 2[] 3[] 4[] 5[] 6[] ...
    • front: -1 (empty queue)
    • back: 0 Upon adding to the queue:
    • 0[0] 1[3] 2[a] 3[] 4[] 5[] ...
    • front: 0
    • back: 3
    • Enqueue: `q[back] = elt;
      • back = back+1` (potentially mod q.length)

    • Front: q[front]

    • Dequeue: front = front + 1 (potentially mod q.length) Advantages: everything is order 1! Disadvantages: queue has a maximum length. This means you might run out of space, or if you allocate a big chunk to be sure, you waste memory. There is an alternate array implementation which lacks the disadvantage, but some of the operations increase to order(n).

For next time

1. Read the Paul Graham essay
2. If you like, read the other stuff, but it's not required.

3. Do WrittenAssignment1

4. Continue acquiring textbooks

Questions Lynn needs to remember to ask

• Have you gotten a textbook? How close are we to textbook happiness?

  • Everyone should theoretically obtain (access to) an algorithms book and a theory book. We'll be using a theory book on Sept 24. Please acquire access to a book by this time.

  • All the rest can probably be supplemented online.
• What do you (plan to) major in?
  • We're trying to extrapolate course needs in the next few semesters.