;; My proc for printing trees
(define (print-tree node)
(define (pt-help node depth)
(begin (d-print depth)
(display (datum node))
(newline)
(for-each (lambda (x) (pt-help x (+ depth 1)))
(children node))))
(define (d-print depth)
(if (= depth 0)
(display "o ")
(begin (display " ")
(d-print (- depth 1)))))
(newline)
(pt-help node 0)
(newline))
;;;;;;;;
;;
;; A more interesting example of tree recursion:
;;
;; Remember this from yesterday:
(define (square x) (* x x))
(define (square-tree node)
(make-node (square (datum node))
(map square-tree (children node))))
(define t1 (make-node 7 (list (make-node
3
(list (make-node 1 '())
(make-node 11 '())
(make-node 21 '())))
(make-node 14 (list (make-node 12 '())
(make-node 3 '())
(make-node 4 '())))
(make-node 12 '()))))
(print-tree t1)
(define t1-squared (square-tree t1))
(print-tree t1-squared)
;;
;; Works because map is applying a function that treats nodes
;; independently.
;;
;; But what if we want procs where the new datum for a node
;; depends on values of previous data?
;;
(define (times-depth node)
(define (td-help node cur-depth)
(make-node (* cur-depth (datum node))
(map (lambda (x) (td-help x (+ 1 cur-depth)))
(children node))))
(td-help node 0))
(define t2 (times-depth t1))
(print-tree t2)
;;
;; This is how you pass information (e.g. the current depth)
;; down the tree.
;;
;; Challenge: How do you pass information up the tree or
;; across the tree?
;;
;; Consider a proc that takes a node as an argument and
;; returns a new tree (with the same structure) where
;; each datum has been replaced with the order it would
;; be evauluated in a pre-fix depth-first search
;;
;; General idea: pass down a cur-val that indicates the
;; next number to be evaluated -- the first child uses this
;; number and then passes back up a new number indicating
;; how many numbers it used. The next child will start
;; with this new number, recursively.
;;
;; Not so easy since we now have two return values: the tree
;; that we are trying to build and the cur-val that should
;; be used next -- but scheme only allows one return value!
;;
;; What can we do?
;;
(define (order-nodes node)
(car (on-help node 0)))
;; Takes a single node and the number to attach to it.
;; Will recursively number its children and then return
;; a pair where the car is the list of numbered children
;; and the cdr is the next number to use as a label.
(define (on-help node cur-depth)
(if (null? (children node))
(cons (make-node cur-depth '())
(+ cur-depth 1))
(let ((r-val (on-help2 (children node) (+ cur-depth 1) '())))
(cons (make-node cur-depth
(car r-val))
(cdr r-val)))))
;; Takes a (possibly empty list of nodes to label, the
;; next number to use as a label, and the list of nodes
;; evaulated so far.
;;
;; Returns a pair where the first is the list of labeled
;; nodes and the cdr is the next label to use.
(define (on-help2 node-list cur-depth so-far)
(if (null? node-list)
(cons so-far cur-depth)
(let ((cnode (on-help (car node-list) cur-depth)))
(on-help2 (cdr node-list)
(cdr cnode)
(append so-far (list (car cnode)))))))
(define t2 (order-nodes t1))
(print-tree t2)
;;
;; Complex, yet powerful idea: compound return values!
;; First example of a non-trivial scheme procedure.
;;
;;
;; Today: Tagged Data
;; Data Directed
;;
;;
;; Tomorrow: Message Passing
;; Dyadic Ops
;; Finally, we are out of cs3 land!!
;;
;; Techniques for controlling complexity:
;; o Abstraction
;; o Higher order procs
;;
;; o Tagged Data
;; o DDP
;; o Message Passing
;;
;; The problem:
;;
;; Consider a geometry program:
;; We want to have shapes (circles and squares)
;; and do operations on them: area and perimeter
;;
;; Basic way : Just use abstraction
;;
(define pi 3.14)
(define (make-circle r)
r)
(define (get-circle-side c)
c)
(define (make-square s)
s)
(define (get-square-side s)
s)
(define (area-circle c)
(* pi (get-circle-side c) (get-circle-side c)))
(define (area-square s)
(* (get-square-side s) (get-square-side s)))
(define (perimeter-circle c)
(* 2 pi (get-circle-side c)))
(define (perimeter-square s)
(* 4 (get-square-side s)))
(area-circle (make-circle 2))
(perimeter-square (make-square 3))
;;
;; This works, but not very well.
;;
;; For each data type, we require new constructors,
;; selectors, AND operating procedures. It would be
;; nice if there were just one 'area' procedure
;; that we could call on any shape.
;;
;; Even worse, we must constanly keep track of which
;; shape we are dealing with and use only the proper
;; procedures on it.
;;
;;
;;
;; Version 2: Tagged Data
;;
;; The big idea: The data maintains a label of what
;; kind of object it is -- procedures can then use
;; that label to determine what to do with a piece
;; of data.
;; Data tagging interface
(define attach-tag cons)
(define type-tag car)
(define contents cdr)
;; Shape interfaces use tagging abstraction
(define (make-square side)
(attach-tag 'square side))
(define (make-circle radius)
(attach-tag 'circle radius))
;; General area and perimeter funcs know about tags
;; and use them to figure out which kind of shape they
;; are dealing with.
(define (area shape)
(cond ((eq? (type-tag shape) 'square)
(* (contents shape) (contents shape)))
((eq? (type-tag shape) 'circle)
(* pi (contents shape) (contents shape)))
(else (error "Unknown shape -- AREA"))))
(define (perimeter shape)
(cond ((eq? (type-tag shape) 'square)
(* 4 (contents shape)))
((eq? (type-tag shape) 'circle)
(* 2 pi (contents shape)))
(else (error "Unknown shape -- PERIMETER"))))
(area (make-circle 2))
(perimeter (make-square 3))
;;
;; Advantage: Fewer, more general procedures.
;; We (the programmer) don't have to keep
;; track of the types of each object.
;;
;; Disadvantage: Each new type needs a tag and
;; (even worse) I have to change every single
;; procedure must be changed to recognize
;; the new type.
;;
;;
;;
;;
;; A new type requires a change in many different
;; places. Remember: this is what we were trying
;; to avoid with abstraction.
;;
;;
;;
;; Version 3: Data Directed Programming
;;
;; The general idea: the data itself tells you
;; the operations that you should perform on it
;;
;; Tagged data was close, in that from an object's
;; type, you could infer what procedure to invoke.
;; But we are going to do one better by having a
;; centralized location where the procedures are
;; stored, and then a very general procedure that
;; finds the proper procedure for its data and
;; uses it.
;; Put and get are the interface to an n-dimensional
;; table where you can use any object as a coordinate:
(put 'square 'area (lambda (s) (* s s)))
(put 'circle 'area (lambda (r) (* pi r r)))
(put 'square 'perimeter (lambda (s) (* 4 s)))
(put 'circle 'perimeter (lambda (r) (* 2 pi r)))
(get 'circle 'perimeter)
(get 'square 'perimeter)
;; The ultra-general procedure takes a general function to
;; perform and a piece of data to perform it on.
(define (operate op obj)
(let ((proc (get (type-tag obj) op)))
(if proc
(proc (contents obj))
(error "Unknown operator for type"))))
(operate 'area (make-circle 2))
;; The procs 'area' and 'perimeter' are then just shorthand
;; for calls to the general operator
(define (area shape)
(operate 'area shape))
(define (perimeter shape)
(operate 'perimeter shape))
(area (make-circle 2))
(perimeter (make-square 3))
;;
;; Advantages: Adding a new type requires changes to
;; only 1 location (the table). All other procedures
;; will automatically work with the new type -- no
;; need to pry open area and perimeter to add the type.
;;
;;
;; Beware: Data directed programming is not just putting
;; procs in tables!
;;
;; Rather, DDP is any scheme whereby the data objects
;; themselves dynamically dictate the operations to be
;; performed.
;;
;; Simple examples:
;; Non-DDP
;; (lambda (x) (* x x))
;;
;;
;; DDP
;; (lambda (x y z) (if x y z))
;;
;; You can think of IF as being a data directed construct
;; since its behavior changes with the value of the test
;; clause.
;; Usually, however, we reserve the name DDP for something
;; more complex than ifs!
;;
;; A really neat example of DDP
;;
;; Terminology: A compiler takes expressions of one
;; language and translates them into the basic, low-level
;; language of the computer.
;; Olden days: If you wanted to invent (and implement)
;; a new language, you have to write a compiler from
;; scratch.
;;
;; Nowadays: Just describe the formal syntax of your
;; language and use a 'compiler compiler' to turn
;; your formal syntax into a compiler.
;; Formal Syntax of Scheme (In your reader)
==> | |
| |
| |
==> ( lambda )
==> ( * ) | | ( + . )
==> *
==> ( define )
| ( define ( ) )
| ( begin * )
==> * | + .
==> *
==>
==> ( if )
==>
==>
==> |
;;
;; 'Lex' (lexical analyzer maker) will take the syntax
;; and produce a procedure (program) that will take
;; a piece of code in your language and spit out
;; the evaluation tree that that code corresponds to!
;;
;; BNF --> [lex] ---
;; |
;; v
;; source --> [lexical analyzer] --> syntax tree
;;
;;
;; (lambda (x) (* 3 x)) --> lambda
;; / \
;; x *
;; / \
;; 3 x
;; New stuff
;; For both tagged data and DDP, we are following the
;; conventional use of operators and data: (smart)
;; operators are functions and (dumb) shapes are data.
;; However, our trend has been to put more 'smarts' in
;; in the data and less in the operators. So, lets
;; take it all the way:
;; We'll makes shapes as (smart) functions, and operators
;; just (dumb) pieces of data (names):
(define (make-square side)
(lambda (message)
(cond ((eq? message 'area)
(* side side))
((eq? message 'perimeter)
(* 4 side))
(else (error "Unknown message")))))
(define (make-circle radius)
(lambda (message)
(cond ((eq? message 'area)
(* pi radius radius))
((eq? message 'perimeter)
(* 2 pi radius))
(else (error "Unknown message")))))
(define (operate op obj)
(obj op))
(define c1 (make-circle 3))
(define s1 (make-square 3))
(c1 'area)
(s1 'perimeter)
(operate 'area c1)
;;
;; What do we have now?
;;
;; 1. Like tagged-data, we no longer have
;; to worry about types from a programmer's
;; perspective.
;;
;; 2. Adding a new type requires changes in
;; only 1 place: the constructors and
;; selectors. We don't have to crack
;; open working code!
;;
;;
;; What is the huge problem here ??
;; Very hard to add operations!
;;
;; What if we wanted to add a num-sides operation?
;;
;; We'd have to make changes to the constructors of
;; each type! This is symmetric to the original problem
;; of having to make changes everywhere with a new type.
;;
;; Have we just taken a giant step backwards??
;;
;; No! When we get to OOP, you'll see techniques for
;; making the addition of operators easy. The net effect:
;; all of the good (of message passing) and none of
;; the bad! (I promise.)
;;
;; You've seen message passing in scheme before!
;;
(define (cons x y)
(lambda (message) (cond ((equal? message 'car) x)
((equal? message 'cdr) y)
(else (error 'oops')))))
(define (car x)
(x 'car))
(define (cdr x)
(x 'cdr))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Dyadic Operations
;;
;;
;; Terms:
;; 1 arg : unary monadic
;; 2 args: binary dyadic
;; The problem: dyadic operations can have
;; two differently typed args.
;; From a table-based DDP:
;;
;; Our original version had two dimensions:
;; One for operation to do, one for type
;;
;; Now, just add one dimension:
;; One for op, one for first type, one for second
(put 'add 'int 'rat (lambda (int rat)
(make-rat (+ (* int (denom rat))
(numer rat))
(denom rat))))
(define (operate op arg1 arg2)
(let ((proc (get op arg1 arg2)))
(if proc
(proc arg1 arg2)
(error "I don't know how to do this!"))))
;;
;; What is the order of growth for # of procs as
;; a function of # of types?
;;
;; In general, you can't do better than that.
;; However, if your types obey a certain property,
;; then you can improve it. Which property? The
;; ability to _coerce_ one type to another.
;; Example: numbers
;;
;; int -> rat -> real -> complex
;;
;; So, we just need procs for adding ints and ints,
;; rats and rats, etc. AND procs for coercing (raising)
;; ints to rats, rats to reals, etc.
;;
;; Order of growth for # procs as a function of #types?
;;
;; Much better!
;; Still, coercion isn't a panacea:
;;
;; Point 1:
;;
;; Consider 1/3 + (2 + 3i)
;; Best answer: (7/3 + 3i)
;; We'll get : (2.333333 + 3i)
;;
;; Our system loses precision over time!
;;
;;
;; Point 2:
;;
;; Raising only works for trees of types!
;; Consider more shapes (rhombus)
;; Where do we raise square?
;;
;; Point 3:
;;
;; How do you mix dyadic operations and message passing?
;;
;; 2 + 3 --> (2 '+ 3)
;;
;; What is the order of growth here?
;;
;; Big idea:
;;
;; You can make slight improvements at the cost of
;; complexity -- but no general solution to the problem
;;
;;
;; Summary: Table of types and procs
;;
;;
;;
;; If time: 1 More tree recursion
;;
;;
;; Want to rotate a node: its first child becomes the root,
;; and it becomes a child.
;;
;;
;; Idea: create new node where datum is datum of
;; first child, children are children of first child,
;; and a new node with datum = the datum of the
;; original node and children = the rest of the
;; original children
(define (rotate node)
(cond ((null? (children node)) node)
(else (let ((orig-children (children node)))
(let ((newroot (car orig-children))
(restchildren (cdr orig-children)))
(make-node (datum newroot)
(append (children newroot)
(list (make-node
(datum node)
restchildren)))))))))
(define t1 (make-node 1 (list (make-node
2
(list (make-node 3 '())
(make-node 4 '())
(make-node 5 '())))
(make-node 6 (list (make-node 7 '())
(make-node 8 '())
(make-node 9 '())))
(make-node 10 '()))))
(print-tree t1)
(define t1-rot (rotate t1))
(print-tree t1-rot)
;;
;; What's the point? To give you some examples of more complicated
;; procedures. You should be able to (given enough time) write
;; something as complex as the above and be able to analyze
;; such a procedure if it is given to you.
;;
;;
;; Peer Instruction:
;;
;; We want procedures to implement a trinary tree.
;;
;; Design decisions:
;; 1. Allow empty trees
;; 2. Either exactly 0 children or exactly 3 ordered ones
;;
;; Give a decent interface and implementation for this.
;; (define (make-tri