Weaver/Yarn Pattern in Python

[Ype Kingma]

Christian Stork wrote:

> Hello everybody,
> 
> I am using Python to prototype a compression algorithm for tree-shaped
> data, e.g., XML data or abstract syntax trees.  I use a variant of the
> visitor design pattern--called weaver/yarn pattern--in order to
> traverse the tree that is being compressed or decompressed.  I do not
> know of any other interesting application of the weaver/yarn pattern,
> but it seems like a very suitable subject of study for different
> implementation strategies.  Essentially, I am asking for input on my
> design decisions.
> 
> First, let me give you a simple example of the traditional visitor
> pattern.  The following diagram illustrates a depth-first traversal of
> a mini tree by a visitor.  The basic idea is that the tree accepts a
> visitor and helps it to do a kind of type-dispatch based on the kind
> of nodes.
> 
...
> 
> The advantage of this ping-pong between the tree and visitor v is that
> v encapsulates related processing instructions.  Several different
> visitors can be maintained independently of each other and without
> forcing changes to the tree node classes.  The tree nodes only need to
> provide a node.accept(visitor) method.  Type-checking can ensure
> the match between the visitor and the tree data structure.
> 
> Normally, visitors encapsulate different processing passes, which are
> run one after the other, each time traversing the whole tree.  I have
> implemented the compression of trees as several (sub)visitors c1..cN
> even though they could have been implemented as one big visitor.
> Besides the easy recombinability of visitors this has the added
> advantage that I can use the same visitors for compression and
> decompression where this is appropriate.
> 
> But now I have a problem when decompressing.  In order to run one
> visitor after another the first one expects to traverse the whole
> tree.  But this is impossible in case of a decompressor.  It lies in
> the very nature of the application that the tree is being constructed
> while the visitors work on it.  Conceptually the solution is easy.
> The decompression subvisitors d1..dM have to process the partially
> available tree upto the point of traversal where it is available.  At
> each node execution has to iterate over the applicable code of d1..dM
> in the given order.  This necessitates a decomposition of visitors
> into something that we call yarns and these yarns are weaved by one
> visitor, which we call the weaver.  Thus the name "Weaver/Yarn
> Pattern" for this variation of the visitor pattern.
> 
> The following exemplifies my current implementation of the w/y pattern
> for a recursive descent (ie depth-first traversal) visitor.  For each
> (sub)visitor d1..dM the former d<i>.visitX(x) method is divided into
> several y.weaveX_...() methods.  At entry and exit the weaver invokes
> y.weaveX_First() and y.weaveX_Last().  Each descent into a child is
> surrounded by y.weaveX_Before(kidno) and y.weaveX_After(kidno) method
> calls.
> 
...
> 
> By now it should be obvious that the boilerplate for this approach
> becomes quite extensive and it would be desirable to reduce it.  To
> mitigate the problem I did three things:
> 
> - Automatically generate templates for yarn classes.  The actual code
>   can be filled in.  Disadvantage: No convenient way to deal with
>   changes to the tree data structure.
> 
> - The node.accept(weaver) methods are changed to call a "generic"
>   weaver.weave(node) method (instead of weaver.visitX(node)), which
>   hackishly constructs all the calls to the yarns by assembling the
>   method names from the __class__.__name__ and one of "First", "Last",
>   "Before", and "After".
> 
> This solution does pretty much what I want:
> 
> - Writing selected yarn methods allows me to express with little
>   overhead /what/ code to execute /when/ in the weaving process.
> 
> - Once the weaver/yarn interaction machinery is set up correctly, the
>   debugger points me to real code in case of bugs.  This is an
>   advantage over approaches that create classes at runtime, e.g., use
>   of metaclasses or the "new" module.
> 
> OTOH, I'm not perfectly happy with this solution since it's totally
> "hackish".  For example, I have to use a function, hand-written
> specifially for this purpose, in order to "type-check" the
> correspondence of the tree types and the yarns.
> 
...

Have a look at aspect oriented programming:

http://www.ccs.neu.edu/home/lieber/AOP.html

In theory it sounds like a good match for what you need.

I don't know how well Python supports this, perhaps you
can use a metaclass for this, but I'm not sure.


Have fun,
Ype


-- 
email at xs4all.nl