Lecture 32: Zero, Once, Many Times

###
Lecture 32: Zero, Once, Many Times

1. Exam: Thursday next week, 7pm, same old location, 3 hours
2. Project: design review: Monday 25; due date: Friday 30; slip days: John Geriner
3. mutual references between objects (values, structures):

   A node in a family tree includes both information about the children and the parents of a person:

                    mother              father
                    ------              ------
                       \                /
                        \              /
                         \            /
                          \          /
                            ________
                            children

   How can we create nodes that contain references from, say, mother, to its children and from each child back to mothers?

       (define-struct person (name children mother father))

       (define Eve (make-person 'Eve-I empty #f #f))

       ;; at child birth:
       (make-person 'Abel empty Eve #f)

   but this does not update Eve.

       ;; create-child : sym person person -> person
       ;; Purpose: make a new person structure to represent name
       ;; Effect: add new person as child to mother and father
       (define (create-child name mother father)
         (local ((define new-child (make-person name empty mother father)))
           (begin
             (set-person-children! mother (cons new-child (person-children mother)))
             (set-person-children! father (cons new-child (person-children father)))
             new-child)))

   Lesson: Use structure modification to create structures with mutual references to each other.

   Problem: Given a node N in a family tree. Wanted: is X a name of a descendant or an ancestor of N.
   Now use data definitions to specify children-oriented family trees and parent-oriented family trees.

       A descendant tree is either
         * #f
         * (make-person symbol (listof dt) p1 p2) where
           dt is a descendant tree and p1, p2 are person
           structures.
       An ancestor tree is either
         * #f
         * (make-person symbol (listof p) at1 at2) where
           at1, at2 are ancestor trees and p are person
           structures.

   So now we can program as if we were in our good old structural world:

       ;; descendants# : descendant-tree -> num
       (define (descendants# dt)
         (cond
           ((boolean? dt) 0)
           (else (+ 1 (foldl + 0
       		 (map descendants#
       		   (person-descendants dt)))))))
       ;; ancestors# : ancestor-tree -> num
       (define (ancestors# at)
         (cond
           ((boolean? at) 0)
           (else (+ 1 (ancestors# (person-father at))
       	       (ancestors# (person-mother at))))))

4. representing graphs
   Instead of using a reachable-of relation, we can translate a graph into the following statements:

       (define A (create-node))
       (define B (create-node))
       ...
       (connect A to B)
       ...

   How?

       (define-struct node (stuff info reachables))
       ;; A node is (make-node boolean #f (listof node)).

       (define (create-node)
         (make-node #f 'anything empty))

       ;; connect : node node -> void
       ;; Effect: add b to the reachables of a
       (define (connect a to b)
         (set-node-reachables! a (cons b (node-reachables a))))
       (define to 'to)

   How do we find a route?

       (define (find-route from to graph)
         (cond
           ((eq? from to) (list to))
           ((node-stuff from) #f)
           (else
             (begin
       	(set-node-stuff! from #t)
       	(find-route/list (node-reachables from) to graph)))))

       (define (find-route/list lo-from to graph)
         (cond
           ((empty? lo-from) #f)
           (else (local ((define from (first lo-froms))
       		  (define route (find-route from to graph)))
       	    (cond
       	      ((boolean? route) (find-route/list (rest lo-froms) to graph))
       	      (else (cons from route)))))))

   Clean up: the graph nodes remain modified after a traversal. That's no good. We need to make sure that the "stuff" thingies are set back to #f after we have figured out the route:

       ;; find-route : node node (listof node) -> (listof node)
       ;; Purpose: find a route from, to in graph
       ;; Effect: -
       (define (find-route from to graph)
         (local ((define (find-route ...) ...)
       	  (define (find-route/list ...) ...)
       	  (define the-route (find-route ...)))
           (begin
             (for-each (lambda (x) (set-node-stuff! x #f)) graph)
             the-route)))

Matthias Felleisen | This page was generated on Wed Apr 14 06:40:24 CDT 1999.