ajk@wren.cs.rmit.OZ.AU (Alan Kent) (04/12/91)
Can someone tell me if I am missing something obvious? I cannot see how to
do this nicely in Eiffel.
I have a tree structure of nodes. These nodes are not all of exactly the
same class. To be precise, the tree is a parse tree for a language so you
have IF nodes, operator nodes, CASE nodes and so on. What I need to do
frequently is walk the tree and perform operations on nodes. For example,
count the number of variable declaration nodes, determine that maximum
stack depth needed by the function by examining expressions, determine
the number of nodes in the graph, determine the maximum depth of nesting
of loops and so on. I also wish to be able to add new nodes with different
structures at any time, so I cannot define a single superclass which can
walk the tree - each node type must have its own methods for walking down
into subnodes (eg: CASE has a list of alternatives, binary operators have
exactly two subnodes, who knows what I will want in the future).
Frankly, I dont not know how to do this nicely. I only want to write the
tree walking code once and I really want to be able to pass as a parameter
somehow the operation to be done. I can do this in C by passing a pointer to
a function. I could not see anything similar in Eiffel. I also got wondering
how you would do it in general in an OO language. I guess you could
(1) Pass a method name which is to be sent to each node in the tree
(2) Same as (1), but pass arguments to the method.
but this means that the node definition must contain the code I wish to do
on the tree nodes. For example, if I want to count the number of IF nodes
by using a "count_if_nodes" method, then the node superclass must contain
such a method. This has the disadvantage if I want to write some new little
function, I have to change my central class definition. Yuck. The alternative
I guess would be
(3) Pass a method name and an object to send the method to with the
current node as a parameter.
This seems similar to the hetrogeneneous discussion going on. If I understand
what has been said, this sort of thing would be easy in a dynamically typed
language. For a statically typed language for this to be completely safe,
you need to be able to specify a function or method with types for parameters.
I guess this is possible in ANSI-C.
Anyway, any suggestions appreciated. Comments about nice ways of doing this
if you could design your own language features would also be of interest to me.
Dr Alan Kent
ajk@goanna.cs.rmit.OZ.AUbrh@hare.udev.cdc.com (brian r hanson x6062) (04/12/91)
Please post any responses to this query to this news group as I would also be interested in possible solutions. Brian Hanson
richieb@bony1.bony.com (Richard Bielak) (04/15/91)
In article <ajk.671419932@wren> ajk@wren.cs.rmit.OZ.AU (Alan Kent) writes: >Can someone tell me if I am missing something obvious? I cannot see how to >do this nicely in Eiffel. > >I have a tree structure of nodes. These nodes are not all of exactly the >same class. To be precise, the tree is a parse tree for a language so you >have IF nodes, operator nodes, CASE nodes and so on. What I need to do >frequently is walk the tree and perform operations on nodes. For example, >count the number of variable declaration nodes, determine that maximum >stack depth needed by the function by examining expressions, determine >the number of nodes in the graph, determine the maximum depth of nesting >of loops and so on. I also wish to be able to add new nodes with different >structures at any time, so I cannot define a single superclass which can >walk the tree - each node type must have its own methods for walking down >into subnodes (eg: CASE has a list of alternatives, binary operators have >exactly two subnodes, who knows what I will want in the future). > [...] You can do exactly what you need by using the "reverse assigment" in Eiffel. Reverse assigment is one of few ways, in which you can check that two objects are type compatible. Here is how this might work: visit (n : NODE; t : SPECIFIC_TYPE_OF_NODE) is do t ?= n; -- reverse assigment if not t.Void then -- here t referes to the specific type -- so apply whatever things t.specific_routine end; end; -- visit This routine can then be called for every node in your tree. In the above example, I assume that NODE is a parent of SPECIFIC_NODE_TYPE. The "?=" will return a non-void value only when "n" actually references SPECIFIC_NODE_TYPE. Hope this helps. ...richie -- *-----------------------------------------------------------------------------* | Richie Bielak (212)-815-3072 | Programs are like baby squirrels. Once | | Internet: richieb@bony.com | you pick one up and handle it, you can't | | Bang: uunet!bony1!richieb | put it back. The mother won't feed it. |
rick@tetrauk.UUCP (Rick Jones) (04/15/91)
In article <ajk.671419932@wren> ajk@wren.cs.rmit.OZ.AU (Alan Kent) writes: >Can someone tell me if I am missing something obvious? I cannot see how to >do this nicely in Eiffel. > >I have a tree structure of nodes. These nodes are not all of exactly the >same class. To be precise, the tree is a parse tree for a language so you >have IF nodes, operator nodes, CASE nodes and so on. What I need to do >frequently is walk the tree and perform operations on nodes. For example, >count the number of variable declaration nodes, determine that maximum >stack depth needed by the function by examining expressions, determine >the number of nodes in the graph, determine the maximum depth of nesting >of loops and so on. I also wish to be able to add new nodes with different >structures at any time, so I cannot define a single superclass which can >walk the tree - each node type must have its own methods for walking down >into subnodes (eg: CASE has a list of alternatives, binary operators have >exactly two subnodes, who knows what I will want in the future). > >Frankly, I dont not know how to do this nicely. I only want to write the >tree walking code once and I really want to be able to pass as a parameter >somehow the operation to be done. I can do this in C by passing a pointer to >a function. I could not see anything similar in Eiffel. I also got wondering >how you would do it in general in an OO language. It can be done nicely, and there is a clue in the cursor_tree and iterator classes which come with Eiffel 2.3 (or are you still on 2.2 or before?). The iterator classes are in beta-release form anyway even in 2.3, and although I've not used them directly I'm not sure that they are the cleanest way to do it. Anyway, I'll outline the general approach: First, you DO need an abstract definition of a node, from which all nodes inherit. All this has to do is define is the essential features for navigating the tree. Using this, you build a deferred class NODE which defines the required features, some or all of which will be deferred. The minimum set of features is probably (without exhaustive thought): parent: NODE -- returns the parent node child: NODE -- returns current child child_start -- positions to point to first child child_forth -- moves to next child child_off: BOOLEAN -- true if "child" points to a void arity: INTEGER -- number of children add (n: like child) -- attach a new child You can get this by inheriting from one of the library TREE classes, but you may want to build your own. If you do the latter, you can cater for all the different node implementations you describe with a common interface. Every one of your actual node classes must inherit from this class. You'll probably want more than one level - say the first level giving you different implementations, then inheriting from these for the different properties. You then need an ITERATOR class. This will contain routines to iterate over the subtree of a node. You can have separate routines to iterate in different orderings. The iterator class is also deferred, since it will contain a deferred "perform" feature which is called at each step of the iteration. For each actual operation you write which involves iteration, you write a new descendant of ITERATOR, defining the "perform" routine to do what you want. Although each operation requires a new class, only the "perform" routine needs to be written, all the iteration code is inherited and thus shared. It looks something like this (untested :-): deferred class ITERATOR export iterate feature iterate (n: NODE) is -- this iterates over all sub-nodes require not n.Void do perform (n) ; from n.child_start until n.child_off loop iterate (n.child) ; n.child_forth end ; end ; perform (n: NODE) is deferred end end Now say you want an iterator to count the total number of nodes. This would be: class NODE_COUNTER export repeat ITERATOR, count inherit ITERATOR define perform feature count: INTEGER ; perform (n: NODE) is do count := count + 1 ; end end To use this from a client class, illustrated as a function to count the nodes, is just: number_nodes (n: NODE): INTEGER is local nc: NODE_COUNTER ; do nc.Create ; nc.iterate (n) ; Result := nc.count ; end If you want an iterator which has to deal with only certain types of nodes, you can make use of Eiffel's reverse assignment. This handles your problem: > For example, if I want to count the number of IF nodes >by using a "count_if_nodes" method, then the node superclass must contain >such a method. This has the disadvantage if I want to write some new little >function, I have to change my central class definition. Yuck. Yuck indeed! No, you can do it this way. Let's say you have a class IF_NODE (a descendant of NODE), and an iterator IF_NODE_COUNTER. This latter class looks exactly like the NODE_COUNTER above, except that the perform routine is: perform (n: NODE) is local if_n: IF_NODE ; do if_n ?= n ; if not if_n.Void then count := count + 1 ; end end The Eiffel reverse assignment only succeeds if the actual object on the RHS is in fact conformant to the type of the variable on the LHS. You can think of this as Eiffel's solution to at least semi-heterogeneous collections; it has the advantage of being a very controlled solution. Apart from counting them, you can of course have iterators which call features of specific node types using the same principle, and it's completely type-safe! >This seems similar to the hetrogeneneous discussion going on. If I understand >what has been said, this sort of thing would be easy in a dynamically typed >language. For a statically typed language for this to be completely safe, >you need to be able to specify a function or method with types for parameters. >I guess this is possible in ANSI-C. Possible, but not the only, or indeed the best, way. There is nearly always an elegant solution in Eiffel, provided you orient your brain in the right direction! If you can't do it the way some other languages might let you, you should start to suspect that the other way is perhaps a hack. I use the following golden rules: Find the abstractions, and encapsulate as deferred classes If there is a multi-way choice of undetermined scope, implement using polymorphism If you think you need a function pointer, use an object (they contain functions!) It usually leads to the right answer. -- Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp Any fool can provide a solution - the problem is to understand the problem
bertrand@eiffel.UUCP (Bertrand Meyer) (04/16/91)
From <ajk.671419932@wren> by ajk@wren.cs.rmit.OZ.AU (Alan Kent): > Can someone tell me if I am missing something obvious? I cannot see how to > do this nicely in Eiffel. > > [Description of a need to iterate variously over trees] Reuse class C_TREE_ITER from the Iteration Library. If you need several types of iteration in the same context, use repeated inheritance. If the assumptions made by that class do not conform to your particular type of tree, and you do not want to change your data structures, imitate and adapt the ideas from C_TREE_ITER and other iteration classes from the library. If this happens please tell us (eiffel@eiffel.uucp) about your experience so that we can improve the library; or, better yet, submit an improved version to the Eiffel shelf, the mechanism for distributing reusable software components (shelf@eiffel.uucp). -- Bertrand Meyer Interactive Software Engineering Inc., Santa Barbara bertrand@eiffel.uucp
ajk@wren.cs.rmit.OZ.AU (Alan Kent) (04/16/91)
richieb@bony1.bony.com (Richard Bielak) writes: >In article <ajk.671419932@wren> ajk@wren.cs.rmit.OZ.AU (Alan Kent) writes: >>I have a tree structure of nodes. These nodes are not all of exactly the >>same class.... >You can do exactly what you need by using the "reverse assigment" in >Eiffel. Reverse assigment is one of few ways, in which you can check >that two objects are type compatible. Here is how this might work: > visit (n : NODE; t : SPECIFIC_TYPE_OF_NODE) is > do > t ?= n; -- reverse assigment > if not t.Void then > -- here t referes to the specific type > -- so apply whatever things > t.specific_routine > end; > end; -- visit >This routine can then be called for every node in your tree. >In the above example, I assume that NODE is a parent of >SPECIFIC_NODE_TYPE. The "?=" will return a non-void value only when >"n" actually references SPECIFIC_NODE_TYPE. First, I assume you mean t is local, not an argument? I thought you were not allowed to assign to arguments. Also, I am not sure how this solves my problem. Say I have 30 different "specific_routine"s. Do I have to then write 30 different visit functions with 30 different walk functions to call the visit functions? Also, what class is visit a method of? In my case I wanted to write some code that could be applied to every node in the tree without chaning the definition of the tree nodes. For example, if I want to count the number of IF nodes in the tree. To me it seems pretty yucky to have to have to change my definition of an IF node (and possibily all the other nodes too) just so somewhere else I can count the number of IF nodes in the tree. Someone asked me to post any mail I got, so here is a suggestion I got in the mail a bit back (I have been off air for a while). > I think you define a new class and override the one or two methods > of interest, and perhaps add or augment a few other methods. Much cleaner > than passing a function pointer around. On the other hand, it could lead > to a lot of useless classes. In the worst case, I guess you could just > write some C code and hook it into Eiffel. -- > -- Ari Halberstadt > ari@eleazar.dartmouth.edu The best I could think up is to try and do something like lists in Eiffel. ie. make the tree walking code keep a current state so you can do code like start at top node in tree while more nodes to be examined do whatever on current node move to next node end Thinking about it a few seconds more this does appear to solve my problem. You could probably write breadth first and depth first tree walking routines if you wanted to. The tree walk code might be a bit tricky, but not too bad. Maybe also provide methods to do things like return parentage array, current depth and so on. Can anyone see anything wrong with this? Thanks Alan Kent ajk@goanna.cs.rmit.oz.au
richieb@bony1.bony.com (Richard Bielak) (04/17/91)
In article <ajk.671767919@wren> ajk@wren.cs.rmit.OZ.AU (Alan Kent) writes: >richieb@bony1.bony.com (Richard Bielak) writes: > >>In article <ajk.671419932@wren> ajk@wren.cs.rmit.OZ.AU (Alan Kent) writes: >>>I have a tree structure of nodes. These nodes are not all of exactly the >>>same class.... > >>You can do exactly what you need by using the "reverse assigment" in >>Eiffel. Reverse assigment is one of few ways, in which you can check >>that two objects are type compatible. Here is how this might work: > >> visit (n : NODE; t : SPECIFIC_TYPE_OF_NODE) is >> do >> t ?= n; -- reverse assigment >> if not t.Void then >> -- here t referes to the specific type >> -- so apply whatever things >> t.specific_routine >> end; >> end; -- visit > >>This routine can then be called for every node in your tree. > >>In the above example, I assume that NODE is a parent of >>SPECIFIC_NODE_TYPE. The "?=" will return a non-void value only when >>"n" actually references SPECIFIC_NODE_TYPE. > >First, I assume you mean t is local, not an argument? >I thought you were not allowed to assign to arguments. You are right. "t" above could not be a parameter. It could be local. > >Also, I am not sure how this solves my problem. Say I have 30 different >"specific_routine"s. Do I have to then write 30 different visit functions >with 30 different walk functions to call the visit functions? > You could create a class like so: class WALK_TREE [S] is feature t : S; visit (foo : NODE) is deferred end; -- visit [.. whatever common code is needed for walking a tree ..] end; Now, for various types of nodes you'd have to inherit specifying the actual type "S". So, if you need to do 30 different things for different types of nodes, you will have to write 30 different "visit" routines. But you should only have to write the code to walk the tree once. Actually, I believe that the library TREE class is already set up this way. It has routines to scan the tree, and an action routine than can be redefined in an heir, that will be called for each node scanned. ...richie -- *-----------------------------------------------------------------------------* | Richie Bielak (212)-815-3072 | Programs are like baby squirrels. Once | | Internet: richieb@bony.com | you pick one up and handle it, you can't | | Bang: uunet!bony1!richieb | put it back. The mother won't feed it. |