6.001 Recitation #7                                        Fall 1997
Prof. Albert R. Meyer

  5-minute-problem #13: Environment Diagram for INSTALL-MARKING-PACKAGE!
     (posed in email, 10/29/97, 1:45pm for presentation Fri, 10/31)

In Problem Set 6 we used a mechanism to install shared procedures which
worked essentially as follows:

1. In the global environment, some variables were defined to hold
needed procedure values:

(define (marked? node) 'uninitialized)
(define (mark! node) 'uninitialized)
(define (adjacent-nodes node) 'uninitialized)


2.  An INSTALL-MARKING-PACKAGE! procedure to install the needed procedures
was then defined in the global environment.  Its definition had the form:

(define (install-marking-package! graph)
  (begin
    (set! marked? <marked?-value>)           ;export MARKED?
    (set! mark! <mark!-value>)               ;export MARK!
    (set! adjacent-nodes <adjacent-nodes-value>) ;export ADJACENT-NODES
    <command to clear marks in graph>))

where the expressions enclosed in pointy brackets can be expected to
reference the parameter GRAPH.


3.  A SEARCH procedure using the marking package was defined
    in the global environment.  Its definition had the form:

(define (search graph)
  (define (aux node)  <aux-value>)
  (begin (install-marking-package! graph)
         (aux node)))

where the <aux-value> expression references the global variables MARK!,
MARKED?, and ADJACENT-NODES.


A problem with this organization is that variables MARK!, MARKED?, and
ADJACENT-NODES are in the global environment.  But these variables are
reset every time SEARCH is applied to a graph, G: the first thing SEARCH
does is call (INSTALL-MARKING-PACKAGE! G) which does the resetting.  So
these variables should properly be kept local to the SEARCH procedure.

A natural way to keep these procedure variables where they belong would be
to include local variables MARK!, MARKED?, and ADJACENT-NODES within the
definition of SEARCH:

(define (search graph)
  (let ((marked? (lambda (node) 'uninitialized))
        (mark! (lambda (node) 'uninitialized))
        (adjacent-nodes (lambda node) 'uninitialized))
    (define (aux node)
      ...(adjacent-nodes node)
      ...(mark! node)...)
    (begin (install-marking-package! graph)
           (aux node))))

Unfortunately, this does not work!  Explain why, showing the structure of
the environment diagram which results from evaluating:



(define (marked? node) 'uninitialized)
(define (mark! node) 'uninitialized)
(define (adjacent-nodes node) 'uninitialized)

(define (install-marking-package! graph)
  (begin
    (set! marked? <marked?-value>)           ;export MARKED?
    (set! mark! <mark!-value>)               ;export MARK!
    (set! adjacent-nodes                     ;export ADJACENT-NODES
        (lambda (node) ... graph ...))
    <command to clear marks in graph>))

(define (search graph)
  (let ((marked? (lambda (node) 'uninitialized))
        (mark! (lambda (node) 'uninitialized))
        (adjacent-nodes (lambda node) 'uninitialized))
    (define (aux node) <aux-value>)
    (begin (install-marking-package! graph)
           (aux node))))

(define G <some graph suitable for SEARCHing>)

(search G)



If you have time, also briefly indicate a way (there are many) in which
the variables can correctly be kept local to SEARCH.