Traversal-enabled Pharo objects

Objects form complicated graphs. Understanding complicated graphs requires a broader perspective on these graphs. Yet, developers are most often exposed to only one node at a time, and there are limited tools available to navigating and slicing these graphs.

To understand graphs, you need to traverse them. This need is often observed in traversal methods directly written inside the domain classes. For example, to get all subclasses of a given class, we have Object>>#allSubclasses. The current implementation is less readable because it does not use recursion, but a possible implementation would look like:

     | all |
     all := OrderedCollection new.
     self allSubclassesDo: [:each | all add: each ].
     ^ all 
Object>>allSubclassesDo: aBlock
     self subclasses do: [:each |
          aBlock value: each.
          each allSubclassesDo: aBlock ] 

This method has two components:

  • a deep traversal of the tree by following the result of executing #subclasses to each traversed object, and
  • a construction of the result collection.

Interesting enough, in the Moose image, we have four allSubclasses methods in different hierarchies, and all of them essentially work in the same way only with different types of objects.

Traversing structures is a general pattern and it can be seen in other occasions as well. For example:

Morph>>allMorphsDo: aBlock
     submorphs do: [:m | m allMorphsDo: aBlock].
     aBlock value: self 

Hardcoding the traversal inside the code is a possibility but it requires tedious construction of the traversal code. A different way of approaching this problem is to model a generic traversal that can be parameterized. This idea was coined by Lieberherr etal (see Traversals of Object Structures: Specification and Efficient Implementation). If we take this way, the solution consists in modeling a traversal as a first class object.

DeepTraverser== is a small package that provides this solution. Using ==DeepTraverser== finding all subclasses of Object requires a simple instruction:
Object deepCollect: #subclasses

How does this work?

The code above starts at Object and traverses all objects retrieved by sending #subclasses to each traversed object. The implementation is available by default in the Moose image and it can be loaded in a fresh Pharo 3.0 image by executing:

Gofer new
   url: '';
   package: ‘ConfigurationOfDeepTraverser’;
(Smalltalk globals at: #ConfigurationOfDeepTraverser) loadDevelopment.

The main class is the DeepTraverser and it has three responsibilities:

  1. Traverse objects,
  2. Mark the traversed objects, and
  3. Trigger actions for each traversed object and each relation between two connected traversed objects.

Traversing objects is delegated to a DeepTraversal, and the action triggering is delegated to DeepActionStrategy.

To provide a more concrete idea, here is an example that traverses the class hierarchy starting with Number and displays on the transcript each class and each inheritance relationship. The example shows how to create a full instance of a DeepTraverser and how to trigger it on an input object:

traversal := DeepCustomTraversal new
                         traversalBlock: [ :each | each subclasses ].
action := DeepCustomActionStrategy new
                         objectAction: [ :each | Transcript show: each ; cr ];
                         relationAction: [ :from :to | Transcript show: from; show: ‘ <-- '; show: to; cr ].
DeepTraverser new
     traversal: traversal;
     action: action;
     traverse: Number

To make the API more fluent, the implementation comes with several Object extensions. The above snippet is equivalent to saying:

     deep: #subclasses
     do: [ :each | Transcript show: each ; cr ]
     relationDo: [ :from :to | Transcript show: from; show: ' <-- '; show: to; cr ]

The do: block is triggered on every traversed object, while the relationDo: block is triggered on every relation specified by the traversal between two traversed objects. In our case, the transcript will print every subclass of Number and every inheritance relationship between these classes.

The examples above referred to trees of objects. What happens when we start dealing with graphs that contain cycles?

The DeepTraverser can traverse any kind of graphs due to a simple cycle detection in the traversal algorithm (this solution was inspired by a first implementation by Mariano Martinez Peck).

For example, PetitParser parsers can potentially form cyclic graphs. For example, if we want to draw a graph of the PPSmalltalkGrammar, we can easily map the traversal to a Roassal visualization (this code is executable in a Moose image):

view := ROMondrianViewBuilder new.
PPSmalltalkGrammar new
     deep: [:each | each children ]
     do: [ :each | view node: each ]
     relationDo:  [ :from :to | view edge: from->to from: from to: to ].
view forceBasedLayout.
view open 


There are several utility methods in Object that come with the existing implementation:

  • deep:collect:
  • deep:collect:as:
  • deep:do:
  • deep:do:relationDo:
  • deep:flatCollect:
  • deep:flatCollect:as:
  • deepCollect:
  • deepCollectAsSet:
  • withDeep:do:
  • withDeep:do:relationDo:

Perhaps having all these methods in Object can be seen as expensive given that all subclasses inherit them. But, traversing objects is a recurring requirement. On the one hand, we have all existing hardcoded traversals that essentially implement the same thing over and over again. On the other hand, when traversals become directly available all the time, you can craft advanced analyses during inspection time more cheaply. And this is at the very heart of humane assessment.

Posted by Tudor Girba at 11 December 2013, 4:14 pm with tags moose, pharo, tooling, analysis, assessment link