Trees, Recursion, Reentrancy & LVOOP

[LAVA 1.0 Content]

Hi folks,

The data in my project is naturally trees. LVOOP seems like a elegant concept to encapsulate trees. So I made a class hierarchy to encapsulate a tree and it seems to be elegant and works perfectly.

BUT. There is a big BUT. Recursion is a natural way to deal with trees. In previous versions of LV, I was able to deal with tree like data structures by calling re-entrant VIs dynamically. This was not always the best performing method as dynamic calls took quite a while but it was elegant and worked perfectly. I was hoping that I can combine recursive handling of trees with the elegance of encapsulation provided by LVOOP. But it seems I cannot.

Trees are naturally handled by recursive operations. In my project where I use trees I cannot think of any other simple enough way to implement one of the central features of the program except recursively navigating trough the trees. The problem now is that I find no way to implement recursion with dynamic class methods. The dynamic class methods don't allow reentrant calls and therefore don't also allow recursive calls. Dynamic methods are needed, since the objects in the tree are not the same and need to be handled each different way. The example below helps to understand the problem.

Download File:post-4014-1156366399.zip

In the attached example I have created an example of the situation. I have an encapsulated the tree concept into three classes. The first class is "Tree Object" and each item in a tree are always tree objects. In addition I chose to have only two types of "Tree Objects": "Nodes" and "Leaves" both of which inherit from the class "Tree Object". Of course in reality I would have much more different kinds of tree objects but this is just a simple example. Each "Node" can contain any number of "Tree Objects" where as each "Leaf" is on the top of the tree. I have a few methods: getType is dynamic and common for all three objects and is used to identify each object type. Another dynamic method that is common to all three classes is "toControl". That is meant for populating a tree control using the content of the tree. "Nodes" have two additional methods "addItem" and "getItems" which add and get new "Tree Objects" from the tree.

The "toControl" method represents a general problem of navigating trough the tree and executing some code for each object in the tree. The executed code needs to depend on the type of the object. I tried to implement it using recursive calls to the toControl method. There were no compile time errors, so I was very hopeful that it will also run correctly. To my disappointemt when I run the code, it fails to execute because of recursive calls.

Can anybody think of any other way to implement tree class structure of heterogeneous trees elegantly and allowing recursive navigation trought the tree so that the top-level class doesn't need to know which kind of items there are in the tree and the decendent classes don't need to know about other decendent classes. For the moment I cannot think of any way... This problematics is super simple in C++ and Java. I don't care if it becomes a little more complicated in LabVIEW as long as I just can do it elegantly i.e. preserving the class structure and encapsulation.

Also a special question for Aristos, what is NI recommendation for this kind of problems?

[PJM_labview]

This is not a direct answer to your question but more a general answer about recursion and LabVIEW.

Typically in LV you can implement recursion in 2 ways:

• The reentrant self Call By Reference (CBR) is the first way (this is the method you mentioned in your question).
  
• The while loop stack method (Stack) is another way. In the Stack method, the work to do is store in a shift register and after every iteration of the loop more work may be added to this stack. The recursion ends when there are no more work to do. Note: The Stack implementation is almost always faster than the reentrant CBR.
  

I read somewhere, a long time ago, that every recursive algorithm can be implemented using the 2 previously mentioned methods (in other word, you can convert a CBR implementation to a Stack one and vice versa) and so far it is my experience that this is true.

So, back to your issue; it might be possible for you to convert your recursive CBR implementation to a Stack implementation.

PJM

[bsvingen]

In the NI white paper about LVOOP it was mentioned that a by ref system tree could be made by using the parent object in the class of a child object. I didn't quite understand how, but it should be possible (according to the paper)

[LAVA 1.0 Content]

In the NI white paper about LVOOP it was mentioned that a by ref system tree could be made by using the parent object in the class of a child object. I didn't quite understand how, but it should be possible (according to the paper)

Yes, see my example above. That however wasn't the problem but rather executing functions on the tree. Edit: The problem is recursing trough the tree.

[Aristos Queue]

Also a special question for Aristos, what is NI recommendation for this kind of problems?

Reentrancy is a nasty problem for dynamic dispatching. I won't go into the details here. There's all sorts of weird ideas kicking around the LV team on how to handle it, none of them exactly satisfactory yet.

There's a couple of answers.

• The first answer I can offer today is the refuge of CS theory: Any function that can be written recursively *CAN* (provably) be written iteratively. The trick is figuring out how to do it for your particular algorithm, and there is no magick bullet. Most solutions use a stack data structure. Using the Queues I've managed to get several recursive algorithms implemented in G. Tree traversal tends to be easy if you want breadth first traversal -- enqueue the root, then inside the loop dequeue an element, operate on that element, then enqueue the element's children, if any. Continue looping until the queue is empty. Depth traversal is done the same way, only using Enqueue At Other End prim. This works even if your tree is implemented as an array with stored indicies for left and right children -- just enqueue indicies instead of the elements themselves.
  
• The other answer is to have a non dynamic function that is reentrant and recursive that calls a dynamic subVI. The subVI "does whatever" and returns enough information for the non-dynamic portion to decide which node to recurse on next.
  

[LAVA 1.0 Content]

• The first answer I can offer today is the refuge of CS theory: Any function that can be written recursively *CAN* (provably) be written iteratively.
  
• The other answer is to have a non dynamic function that is reentrant and recursive that calls a dynamic subVI. The subVI "does whatever" and returns enough information for the non-dynamic portion to decide which node to recurse on next.
  

I try these out. I kind of thought of these already, but my intuition says there may be a few problems especially in the case of OOP.

Consider tree structure of files and directories. You can think of class structure FileSystemObject to be the parent class and File and Directory both being child classes of FileSystemObject. Now the FileSystemObject in common denominator for both Files and Directories. Files can hold data and Directories can hold other FileSystemObjects. This can be implemented in LVOOP and is very similar to the example I posted above.

The problem is that in OOP the Files unlike Directories are not containers of other FileSystemObjects. That means that the common super class FileSystemObject cannot be container of other FileSystemObjects. So in a strict sense it cannot contain a method to do the recursion, either iteratively or using reentrant calls. The only place the recursion can take place is in the method of Directory class. But then neither of the methods Aristos mentioned work, since both of them need to be executed from the FileSystemObject level. At least that is what my intuition says. I'll try it out.

To summarize the problem is that if one wants to recurse trough a tree structure, one needs to violate the OOP encapsulation paradigm and include properties and methods to the parent class that are really not properties and methods of all the child classes. One can of course hide the implementation from the class user. However from the class developer point of view, the class reusability suffers. In order to add new kind of child class to a tree class hierarchy class developer may need to modify the top most class parameters and methods to do the recursion properly. This requires that the implementation of the tree class hierarchy cannot be hidden from the class developers. Hiding the implementation also from class developers is one corner stone of object oriented programming paradigm.

I'll try out if my above described analyzes really holds or if I'm thinking something wrong.

Edit:

Ok. Now I have implemented the recursion by stack. I was able to implement stack recursion easily. However as I suspected I failed to keep classes clean, i.e. I was forced to include methods to the parent class that really didn't belong there. I kept these methods protected so that the dirtyness is not visible the class user but only the class developers. The new version of the example is below.

Download File:post-4014-1156502334.zip

In the example the Tree Object class is the parent class for Node and Leaf classes. I was forced to include _getItems and _hasSubItems methods to the Tree Object class, both of which are protected. I use _ to indicate that a method is protected. These items do not naturally belong to Tree Object class, since objects of Leaf class can never have sub items and sub items is not there fore a common concept of both Node and Leaf classes. Can anybody find a way around this elegancy problem that perhaps only arises from my puristic mind

[Aristos Queue]

Edit:

Ok. Now I have implemented the recursion by stack. I was able to implement stack recursion easily. However as I suspected I failed to keep classes clean

Ok... new idea:

A variation on the "Vistior" pattern (see Gang of Four textbook)

Add a method to FileSystemObject called DoTraverse.vi. This VI takes as inputs a FileSystemObject (dynamic dispatch input) and a TraverseVisitor. The TraverseVisitor object has a method "Enqueue Next Element" and a member field that is a queue refnum. A standalone VI obtains an unnamed queue and uses that queue refnum. Enqueue the root of the tree in the queue. Then in a loop the VI dequeues, calls DoTraverse, until the loop is empty.

Result: You now have a generic traversal of the tree. The TraverseVisitor can be subclassed to provide different data/services to the DoTraverse.vi implementations. The parent class FileSystemObject does not have anything about "next" or "child" in its definition, only a method of what to do during the traversal.

----------------

More general note about this conversation: It's a very strange feeling. I have programmed LV, JAVA, C++ and half a dozen other languages. In all of these, I could quickly identify a hack as distinct from a good implementation. With LV and OO, I have only vague feelings about whether something is a hack or not. I've never worked with a programming system this new before. Very cool, in some ways, very odd in others. This conversation needs to be tracking two aspects: 1) the search for good implementations and cannonical patterns and 2) the holes that need new language syntax to patch over. Distinguishing what is a hole that needs to be patched from a bad idea that should be avoided is the root of the design decisions that lead to the current LabVOOP implementation, only now there's a working model to see if the theory tests out. ;-)

----------------

[Later Edit] We could simplify this purity problem you're having. In the file directory use case, you could argue that every FileSystemObject should have a GetNext function... after all a shortcut is a file that might want to traverse to its real file, or a .zip file might want to traverse to the files contained within it. "When the problems get hard, redefine the solution."

[LAVA 1.0 Content]

Ok... new idea:

I've to give it a try another day. I found a frustrating bug when I tried to make a copy of my class structure which prevents me from going on today. The project file gets corrupted and LV crashes when adding my class hierarchy to a new library (lvlib). I posted the bug report to NI techical support as well as to here.