Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!spool.mu.edu!uunet!mcsun!ukc!pyrltd!tetrauk!rick
From: rick@tetrauk.UUCP (Rick Jones)
Newsgroups: comp.lang.eiffel
Subject: Re: How can I do this in Eiffel?
Message-ID: <1134@tetrauk.UUCP>
Date: 15 Apr 91 13:52:40 GMT
References: <ajk.671419932@wren>
Reply-To: rick@tetrauk.UUCP (Rick Jones)
Distribution: comp
Organization: Tetra Ltd., Maidenhead, UK
Lines: 174

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