match questions

[wand%corwin.ccs.northeastern.edu@RELAY.CS.NET]

Much as I like pattern matching as proposed by Chris, I think Andy may be on
to something, though I don't completely understand it.

   treenum ::= Leaf num | Branch treenum treenum

   sumtree :: treenum -> num
   sumtree (Leaf x) = x
   sumtree (Branch xt yt) = sumtree xt + sumtree yt

   To my mind, the following commonlispish program is superior.  For one
   thing, I can change the things that are in a branch without changing
   the sumtree program.  Note the absense of positional notation/
   information.

   (defstruct (leaf weight)
     (weight number))		;;; since this is lisp, type decls are optional

   (defstruct (branch left right)
     (right (or leaf branch))
     (left (or leaf branch)))

   ; This may win the hokiest accessor syntax award but it does
   ; suggest an obvious extension if multiple values are introduced....
   (define (sumtree tree)
     (cond ((leaf? tree) (leaf tree weight))
	   ((branch? tree) (+ (sumtree (branch tree left))
			      (sumtree (branch tree right))))
	   (else <halt and catch fire>)))

I guess I don't completely understand this.  If I understand it, the second
defstruct exports the following global definitions:

[Let's not argue about the word "global" and what happens if the defstruct
appears in an interior scope, OK?]

branch?
branch
left 
right

I guess I don't understand why there is both "branch" and "left/right" here.
If I understand it correctly, I couldn't have another defstruct that had a
different "left".  Is that right?

What Chris and I most commonly use matching for is as a rough-and-ready
device for decomposing variant record structures.  In general, one needs an
interface between the design of the record structure and the code that uses
that design.  There are a number of conflicting design goals:

1.  Locality of reference.  The code that uses the record should be readable
without reference to a textually-distant definition of the record structure.

2.  Control of the namespace.  The interface should garbage as little of the
global namespace as possible.  

Pattern-matching scores heavily on both these counts; in particular, it
uses no globally named access functions.  Andy's proposal seems deficient,
though again I'm not sure I understand it.

3.  Modifiability.  Changes in the record definition should not require
rewriting the code that uses that definition.  

This is where pattern-matching loses:  user code must be rewritten whenever
fields are reordered or added.  This is where defstruct's (eg Common Lisp's)
are on the right track.  Reordering or adding fields does not require recoding
of user functions.  

Common Lisp defstruct (and Chez Scheme define-structure) also do pretty well
on the side of not garbaging the global namespace: the names of the access
functions form a distinguished sublanguage (identifiers of the form
structname-fieldname, though I'd probably prefer structname->fieldname), so
the only "really global" identifiers established are structname (and
structname?). 

I think it is possible to get something at a higher level than defstruct that
still has the right properties, while increasing locality of reference, but I
haven't figured it out well enough to share it quite yet.

--Mitch