Lecture 3: Information: When it rains, it pours

###
Lecture 3: Information: When it rains, it pours

1. reading: TLL ch 1-3 reading: Intermezzo, Sections 7, 9, 10
2. frogs
3. pop quiz: empty piece of paper -- what is `'michael 'lisa`

4. information comes in bundles
   1. We are translating information from the real world into the language of data in our programming langauge. Thus far, information was easy to translate. A radius is a measurement, so we translate it into a number. A claim about the world becomes true or false.
   2. Now let's represent some visual characteristics of people. two students -- describe distinguishing characteristics -- we list essential properties
   3. Planet -- list essential properties: position, speed, color
   4. Balls rolling on a table -- the essential property: position, it consists of two pieces -- x and y coordinates
5. since it is easy to lose track of which piece of information belongs to another one, a good programming language provides (many) mechanisms for bundling information -- we have listed properties, so we use (finite) lists today

       people properties:
       'josh   'blond-haired 'blue-eyed  'fair-skinned  'male   'big-feet
       'evelyn 'black-haired 'green-eyed 'black-skinned 'female 'small-feet

       ball position:
       12 14
       16 26
       20 38

       At what rate is the ball rolling? 4 in the x direction, 12 in the y direction

       ball speed:
        4 12

       again pairs of numbers

6. Let's make lists: how do we start when we make a list --- with the empty list
   and then -- we construct longer lists by putting together some item and a list

   So here are some Scheme lists:

       empty

       (cons 3 empty)
       (cons 'blond empty)
       (cons 'black empty)

       (cons 4 (cons 3 empty))
               ^^^^^^^^^^^^^^ is a list by above argument
       (cons 'josh (cons 'blond empty))
                     ^^^^^^^^^^^^^^ is a list by above argument
       (cons 'evenlyn (cons 'black empty))
                     ^^^^^^^^^^^^^^ is a list by above argument

   What items are on these lists?
7. Let's make an agreement:
   Points are represented by lists of two numbers.
   We already have an example. Let's make another one: `(cons 12 (cons 1 empty))`
8. Let's write a program that consumes a (representation of a) point and produces its distance to the origin.

       (define (distance a-point)
         ...)

   What do we need to do here? Aha, we need to find out the numbers on the list. How do we do that?

   We have seen how to construct lists. Now we need to destruct them. We get two operations. If x is a constructed list, (first x) and (rest x) can extract some information: the item and the list, respectively, that cons glued together.

       (first x) = 3  if x = (cons 3 (cons 4 empty))
                      if x = (cons 4 empty)
                      if x = (cons 4 L)

       (rest x) = (cons 4 empty) if x = (cons 3 (cons 4 empty))
       (rest x) = empty	  if x = (cons 4 empty)
       (rest x) = L              if x = (cons 4 L)

   Exercise: if x is guaranteed to be a list with two, three, four items, how do I get back the second item:

        (first (rest x))
        (first (rest (rest x)))
        (first (rest (rest (rest x))))

9. Now let's return to `distance-to-origin`.

       (define (distance-to-origin a-point)
         (sqrt
           (+ (square (first a-point))
              (square (first (rest a-point))))))

   Here is how we calculate with this thing:

         (distance-to-origin (cons 3 (cons 4 empty)))
       = (sqrt
           (+ (square (first (cons 3 (cons 4 empty))))
              (square (first (rest (cons 3 (cons 4 empty)))))))
       = (sqrt
           (+ (square 3)
              (square (first (rest (cons 3 (cons 4 empty)))))))
       = (sqrt
           (+ (square 3)
              (square 4)))
       = (sqrt
           (+ 9 16))
       = 5

10. This is difficult to read. -- When we think about bundles of informations, we need to introduce specific constructors and specific selectors. But we start by stating our agreement ...

        ;; A point is a list of two numbers:
        ;;   (cons number (cons number empty))

        (define (make-point x y)
          (cons x (cons y empty)))

        (define (point-x a-point)
          (first a-point))

        (define (point-y a-point)
          (first (rest a-point)))

    How do these things interact:

        (point-x (make-point 3 4)) = 3
        (point-y (make-point 3 4)) = 4
        ...

11. Time to rewrite distance-to-origin and to reuse these simple programs:

        (define (distance-to-origin a-point)
          (sqrt
            (+ (square (point-x a-point))
               (square (point-y a-point)))))

    Little homework:

          (distance-to-origin (make-point 3 4))

Matthias Felleisen | This page was generated on Mon Mar 29 09:23:13 CST 1999.