Announcements

Introduction

• Pairs as Universal Glue
  • n-dimensional points, lines, figures
• Data types and Data abstractions
  • The basic question is "what can you do with it?"
• Conventions for Usage and Standardization
  • Plugs and telephone connectors
  • lists are a standard usage of pairs in Scheme/Lisp (the rest of the world calls it "singly linked list")
  • trees are a common use of pairs, but they aren't standardized

Data Abstraction

• A data type is defined by what you can do to things of that type.
• Scheme makes all types first class so they all share 4 properties. They can be:
  1. given a name (using lambda, define, let, etc.)
  2. passed to a procedure as an argument
  3. returned as a value from a procedure
  4. put into a data structure (e.g. a pair or a list)
• Special additional operations define data types.
  • numbers have the arithmetic operations.
  • strings havestring-length, string-ref, and others.
  • procedures can be applied to arguments (i.e. use as the value of the first subexpression in a combination)
  • pairs have the operations car, cdr, etc.
• Abstract data (separate interface from implementation)
  • constructors, e.g. CONS for pairs
  • predicates, e.g. NUMBER?, STRING?, PROCEDURE?, PAIR?
  • selectors, e.g. CAR, CDR, STRING-REF
  • more sophisticated things, including readers, printers, mutators
  • specialized operators, e.g. + and > for numbers.

  Example of a List

     (define origin-3d (list 0 0 0))
     (define origin-3d (cons 0 (cons 0 (cons 0 '()))))
  

  

  Common Operations on Lists

  Predicate to test for a list:

  (define (list? l)
    (or (null? l)
        (and (pair? l) (list? (cdr l)))))
  

  We'd like to know how many dimensions a point has:

  (define (point.dimension pt) (length pt))
  
  (define (length l)
    (if (null? l)
        0
        (+ 1 (length (cdr l)))))
  

  We'd like the coordinate on a particular axis:

  (define (point.coord pt dim) (list-ref pt (- dim 1)))
  (define (point.x pt) (point.coord pt 1))
  (define (point.y pt) (point.coord pt 2))
  (define (point.z pt) (point.coord pt 3))
  
  (define (list-ref l n)
    (cond ((null? l) (error "..."))
          ((= 0 n) (car l))
          (else (list-ref (cdr l) (- n 1)))))
  

  We'd like to find distance from origin:

  (define (point.to-origin pt)
    (sqrt (add-up (map square pt))))
  
  (define (map fn list-of-values)
    ; Returns list of same length as list-of-values
    (if (null? list-of-values)
        '()
        (cons (fn (car list-of-values))
              (map fn (cdr list-of-values)))))
  

  Our first attempt to write add-up:

  (define (add-up list-of-numbers)
    (if (null? list-of-numbers)
        0
        (+ (car list-of-numbers)
           (add-up (cdr list-of-numbers)))))
  

  Or we can use a common higher-order abstraction:

  (define (accumulate initial-value operation list-of-elements)
    (if (null? list-of-elements)
        initial-value
        (operation (car list-of-elements)
                   (accumulate initial-value operation
                               (cdr list-of-elements)))))
  
  (define add-up (lambda (l) (accumulate 0 + l)))
  

  We'd like to filter out those that are more than 1 unit from the origin:

  (define (inside-unit-sphere? point)
    (<= (point.to-origin point) 1))
  
  (define (those-inside-unit-sphere list-of-points)
    (filter (lambda (pt) (<= (point.to-origin pt) 1))
            list-of-points))
  
  (define (filter test list)
    (cond ((null? list) '())
          ((test (car list))
           (cons (car list) (filter test (cdr list))))
          (else (filter test (cdr list)))))
  

  Now we can do things like:

  (define (how-many-in-unit-sphere points)
    (accumulate 0 +
      (map (lambda (pt) 1)
           (filter inside-unit-sphere? points))))
  

  Build the Standard Into the Language

  Once we've decided that lists "are the right thing" we can go beyond just writing procedures and "making them primitive for efficiency" like length, list-ref, map, and others (list-copy, reverse, append, sublist, list-head, list-tail).

  We can actually change the language so that lists have a special status.

  • Create a syntax for reading and printing them: (1 2 3)
  • Create syntax for procedures with arbitrary number of arguments:

    (define (add . numbers)
      (add-up numbers))
    
    (define (list . elements) elements)
    
    (define list (lambda elements elements))
    

  • Create a primitive procedure, apply, that can't be written in Scheme for applying a procedure to a list of arguments:

    (define (point.to-origin pt)
      (sqrt (apply + (map square pt))))
    

  Trees

  • Important and common, but not standardized in Scheme.
  • Made from leaves and nodes. We'll do "binary trees" meaning each node has two children. We'll assume that the tree has been ordered using a relation (like < or >=) so that one branch contains only leaves whose value is less than the value at the parent node, while the other branch contains only values greater-than or equal-to that of the parent node.. We'll assume that the leaves are all n-dimensional points.
  • See tree.scm for all of the code.
  • A typical tree recursion is needed to find the point farthest from the origin:

    (define (tree.farthest node-or-leaf)
      (if (is-node? node-or-leaf)
          (tree.farthest (node.outside node-or-leaf))
          node-or-leaf))
    

  • Sometimes we need a "generic operation" that can work on either a leaf or a non-leaf node in a tree:

    (define (distance node-or-leaf)
      (if (is-node? node-or-leaf)
          (node.distance node-or-leaf)
          (point.to-origin (leaf.point node-or-leaf))))
    

  • And a more complicated tree recursion: Note: The following code was presented in lecture, claiming to guarantee that a tree has the property that all the leaves in the node.on-or-in branch under a given node have a distance that is less-than-or-equal-to the distance to the given node, and that all leaves in the node.outside branch have a distance greater than that to the node. This is not true.

    (define (tree.valid? node-or-leaf)
      (if (is-node? node-or-leaf)
          (let ((smaller (node.on-or-in node-or-leaf))
                (not-smaller (node.outside node-or-leaf))
                (my-distance (node.distance node-or-leaf)))
            (and (< (distance smaller) my-distance)
                 (>= (distance not-smaller) my-distance)
                 (tree.valid? smaller)
                 (tree.valid? not-smaller)))
            #T))
    

    The following, more complicated program, does work correctly.

    Extra credit question: Can you draw a tree, t, for which (tree.valid? t) returns #T but for which (valid? t) returns #F?

    (define (valid? node-or-leaf)
      (define (min previous new)
        (if (and previous (<= previous new)) previous new))
    
      (define (max previous new)
        (if (and previous (>= prevous new)) previous new))
    
      (define (walk node-or-leaf min-OK max-OK)
        (if (is-node? node-or-leaf)
            (let ((smaller (node.on-or-in node-or-leaf))
                  (not-smaller (node.outside node-or-leaf))
                  (my-distance (node.distance node-or-leaf)))
              (and (or (not min-OK) (>= (distance smaller) min-OK))
                   (or (not max-OK) (<= (distance not-smaller) max-OK))
                   (walk smaller (min min-OK my-distance) max-OK)
                   (walk not-smaller min-OK (max max-OK my-distance))))
            #T))
    
      (walk node-or-leaf #F #F))