[comp.lang.eiffel] Passing functions as parameters

marcap@hercule.cs.concordia.ca (PAWLOWSKY) (02/02/90)

A while back, the passing of functions as parameters was mentioned.  If
memory is correct (I don't have a list of comp.lang.eiffel postings, is 
someone out there keeping a ftp'able copy?) it ended up with someone
saying it is not needed since you can redefine the function as needed
in the class.

This is not always good enough.  Take the example of a class student, with
attributes gpa, name, id_no.  We also have a database called PUPILS.  In
PUPILS a function is needed to return a SORTED_LIST[STUDENT] by
id_no.  No trouble, just define the COMPARABLE operations in terms of id_no
in STUDENT.

BUT we also want to have a function return a SORTED_LIST[STUDENT] by gpa.
What do we do here?  

A solution would be to create a descendant of 
SORTED_LIST just for STUDENT's that would have hard coded the use of its
members gpa for comparison.  And if we wanted it by name, another class.
This could get quite large and messy if we need many different orderings.

I believe that a much better solution would be to have the function that
is to make the comparison passed.

Marc Pawlowsky   Concordia University      Montreal, Quebec, Canada

jacob@gore.com (Jacob Gore) (02/03/90)

/ comp.lang.eiffel / marcap@hercule.cs.concordia.ca (PAWLOWSKY) / Feb 2, 1990 /
> A while back, the passing of functions as parameters was mentioned.  If
> memory is correct (I don't have a list of comp.lang.eiffel postings, is 
> someone out there keeping a ftp'able copy?) it ended up with someone
> saying it is not needed since you can redefine the function as needed
> in the class.

I take this as confirmation that no, you can't pass functions as parameters
in Eiffel.

Could somebody tell me then what the inheritance-related trick is for
supplying a list class with the following routines:

    1.	apply-routine   -- like LISP's "mapcar": same operation repeatedly
				applied to all elements of the list

    2.	insert-function -- like APL's "/":
				given a list L such that nb_elements(L)>1
				and a fuction F,
					if L.nb_elements > 2 then
						return F(L.first, L.rest)
					else
						return F(L.first, L.second)

The one particularly useful in Eiffel is a combination of 1 and 2:

    3.	for-all		-- given a BOOLEAN function F and a list L,
				return 'true' if F(L.i_th(k)) returns true
				for all 1 <= k <= L.nb_elements

And, of course, a there-exists function is analogous.

Having such features in list classes would make writing assertions about
lists much easier.

Jacob
--
Jacob Gore		Jacob@Gore.Com			boulder!gore!jacob

jos@cs.vu.nl (Jos Warmer) (02/05/90)

In article <120012@gore.com> jacob@gore.com (Jacob Gore) writes:
>/ comp.lang.eiffel / marcap@hercule.cs.concordia.ca (PAWLOWSKY) / Feb 2, 1990 /
>> A while back, the passing of functions as parameters was mentioned.  If
>> memory is correct (I don't have a list of comp.lang.eiffel postings, is 
>> someone out there keeping a ftp'able copy?) it ended up with someone
>> saying it is not needed since you can redefine the function as needed
>> in the class.
>
>I take this as confirmation that no, you can't pass functions as parameters
>in Eiffel.
>
>Could somebody tell me then what the inheritance-related trick is for
>supplying a list class with the following routines:
>
>    1.	apply-routine   -- like LISP's "mapcar": same operation repeatedly
>				applied to all elements of the list
>

This is the `pre_order' or `post_order' from MY_TREE.
See later on.

>    2.	insert-function -- like APL's "/":
>				given a list L such that nb_elements(L)>1
>				and a fuction F,
>					if L.nb_elements > 2 then
>						return F(L.first, L.rest)
>					else
>						return F(L.first, L.second)

This one is not in MY_TREE, but the insert-function could be done
in analogy with `pre_order' and `bpre_order'.

>
>The one particularly useful in Eiffel is a combination of 1 and 2:
>
>    3.	for-all		-- given a BOOLEAN function F and a list L,
>				return 'true' if F(L.i_th(k)) returns true
>				for all 1 <= k <= L.nb_elements
>
>And, of course, a there-exists function is analogous.

Both for-all and there-exists can easily be implemented by `bpre_order'
or `bpost_order' from MY_TREE.
See later on. In the example, there-exists is shown.

By the way, eiffel naming conventions would call `there-exists' `has'.

>
>Having such features in list classes would make writing assertions about
>lists much easier.
>
>Jacob
>--
>Jacob Gore		Jacob@Gore.Com			boulder!gore!jacob

Yes I can tell you what trick I use. My trick is implemented for tree's, but
the idea remains the same for sets, list and so on.
I desperately needed a way to traverse complete tree's and perform
an action on each node.
Because this kind of functionality is needed very often in lists, trees, sets
and so on, I see the absense as a serious omission in the library.


		    DESCRIPTION OF THE METHOD

Class MY_TREE is an adaption of class TWO_WAY_TREE from the library.
It adds several routines for traversing the tree and performing actions
on each node of the tree. The routine `pre_order' will be taken as
an example. The remaining routines are in the class text below.

    pre_order( a : TREE_ACTION[T] ) is
	-- Traverses the tree of which `Current' is the root in preorder
	-- and performs `a.action' on each node.
    require
	not a.Void

The routine `pre_order' takes as parameter an entity `a' of
type TREE_ACTION[T].
TREE_ACTION is a deferred class with one function called `action':

    deferred class TREE_ACTION[T] export
	action

    feature
	action(t : MY_TREE[T], level : INTEGER) is deferred end;

    end -- class TREE_ACTION

`pre_order' traverses the tree in preorder and performs a.action(node, level)
for each node in the tree.  Level is the depth of the node in the tree.

To use it, define a descendant of class TREE_ACTION and give an
implementation of `action'.  I will call such a class an action class.
For example, a class to count the number of nodes in a tree:

    class COUNT_ACTION[T] export
	   action, nr_nodes

    inherit
	   TREE_ACTION[T];

    feature
       nr_nodes : INTEGER;

       action( t : MY_TREE[T], level : INTEGER ) is
       do
	   nr_nodes := nr_nodes + 1;
       end;
    end;

Usage:
     ...
     count: COUNT_ACTION[SOME_TYPE];
     tree : MY_TREE     [SOME_TYPE];

     ... is
     do
	 count.Create;
	 tree.post_order(count);
	 io.putint( count.nr_nodes ); io.new_line;
     end;

Disadvantages:

- For each routine you want to apply, you need to write a separate
  action class. This might result in lots of little classes.

Advantages:

- You can apply different routines to the elements of a tree.
  The method with redefining a function within TWO_WAY_TREE only
  gives you one routine.

- All data associated with the routine that is applied to each node
  can be local to the action class.
  Remind that in e.g. C you always need global variables for usage
  by the routine.

- If you need to apply complex operations on each node, then the
  action class can incorporate all needed routines and variables.
  I use action classes which are over 200 lines long.

Advantages 2 and 3 give much better information hiding then in
conventional languages.

Following is a shar-archive, which contains the classes I use for this
kind of traversals, including an example program.
I have used them for almost a year, so they should be reliable.

By the way, how do we define `production quality' ?

				  Jos Warmer


: This is a shar archive.  Extract with sh, not csh.
: This archive ends with exit, so do not worry about trailing junk.
: --------------------------- cut here --------------------------
PATH=/bin:/usr/bin:/usr/ucb
echo Extracting 'README'
sed 's/^X//' > 'README' << '+ END-OF-FILE ''README'
XREADME          : this file
XDESCRIPTION     : description of the method used, including (dis)advantages
X
XThe following four classes should reside in a library directory.
XThey implement all kinds of traversal for trees.
X
Xmy_tree.e	: adaption of two_way_tree with traversal routines
Xbtree_action.e  : deferred action's for traversing my_tree.
Xtraverse.e      : deferred action's for traversing my_tree.
Xtree_action.e   : deferred action's for traversing my_tree.
X
XThe following trhee classes show some examples using the library.
X
Xexample.e       : 'main' program
Xexists.e        : actual btree_action
Xprint_tree.e    : actual tree_action
+ END-OF-FILE README
chmod 'u=rw,g=rw,o=' 'README'
set `wc -c 'README'`
count=$1
case $count in
637)	:;;
*)	echo 'Bad character count in ''README' >&2
		echo 'Count should be 637' >&2
esac
echo Extracting 'DESCRIPTION'
sed 's/^X//' > 'DESCRIPTION' << '+ END-OF-FILE ''DESCRIPTION'
X
X
X		    DESCRIPTION OF THE METHOD
X
XClass MY_TREE is an adaption of class TWO_WAY_TREE from the library.
XIt adds several routines for traversing the tree and performing actions
Xon each node of the tree. The routine `pre_order' will be taken as
Xan example. The remaining routines are in the class text below.
X
X    pre_order( a : TREE_ACTION[T] ) is
X	-- Traverses the tree of which `Current' is the root in preorder
X	-- and performs `a.action' on each node.
X    require
X	not a.Void
X
XThe routine `pre_order' takes as parameter an entity `a' of
Xtype TREE_ACTION[T].
XTREE_ACTION is a deferred class with one function called `action':
X
X    deferred class TREE_ACTION[T] export
X	action
X
X    feature
X	action(t : MY_TREE[T], level : INTEGER) is deferred end;
X
X    end -- class TREE_ACTION
X
X`pre_order' traverses the tree in preorder and performs a.action(node, level)
Xfor each node in the tree.  Level is the depth of the node in the tree.
X
XTo use it, define a descendant of class TREE_ACTION and give an
Ximplementation of `action'.  I will call such a class an action class.
XFor example, a class to count the number of nodes in a tree:
X
X    class COUNT_ACTION[T] export
X	   action, nr_nodes
X
X    inherit
X	   TREE_ACTION[T];
X
X    feature
X       nr_nodes : INTEGER;
X
X       action( t : MY_TREE[T], level : INTEGER ) is
X       do
X	   nr_nodes := nr_nodes + 1;
X       end;
X    end;
X
XUsage:
X     ...
X     count: COUNT_ACTION[SOME_TYPE];
X     tree : MY_TREE     [SOME_TYPE];
X
X     ... is
X     do
X	 count.Create;
X	 tree.post_order(count);
X	 io.putint( count.nr_nodes ); io.new_line;
X     end;
X
XDisadvantages:
X
X- For each routine you want to apply, you need to write a separate
X  action class. This might result in lots of little classes.
X
XAdvantages:
X
X- You can apply different routines to the elements of a tree.
X  The method with redefining a function within TWO_WAY_TREE only
X  gives you one routine.
X
X- All data associated with the routine that is applied to each node
X  can be local to the action class.
X  Remind that in e.g. C you always need global variables for usage
X  by the routine.
X
X- If you need to apply complex operations on each node, then the
X  action class can incorporate all needed routines and variables.
X  I use action classes which are over 200 lines long.
X
XAdvantages 2 and 3 give much better information hiding then in
Xconventional languages.
X
XI have used them for almost a year, so they should be reliable.
X
XBy the way, how do we define `production quality' ?
X
X				  Jos Warmer
+ END-OF-FILE DESCRIPTION
chmod 'u=rw,g=rw,o=' 'DESCRIPTION'
set `wc -c 'DESCRIPTION'`
count=$1
case $count in
2488)	:;;
*)	echo 'Bad character count in ''DESCRIPTION' >&2
		echo 'Count should be 2488' >&2
esac
echo Extracting 'btree_action.e'
sed 's/^X//' > 'btree_action.e' << '+ END-OF-FILE ''btree_action.e'
X--  Function to apply during tree-traversal.
X--  See MY_TREE.
X--
X--  To use it, inherit from this class and define an implementation
X--  for `action'.
X
X--  Author      :  Jos Warmer , e-mail: jos@cs.vu.nl
X--  Organisation:  Department of Mathematics and Computer Science
X--      	   Vrije Universiteit Amsterdam
X--  Version     :  5 Februari 1990
X
Xdeferred class BTREE_ACTION[T] export
X
X    action
X
Xfeature
X
X    action(t : MY_TREE[T], level : INTEGER) : BOOLEAN is deferred end;
X
Xend -- class BTREE_ACTION
+ END-OF-FILE btree_action.e
chmod 'u=rw,g=r,o=' 'btree_action.e'
set `wc -c 'btree_action.e'`
count=$1
case $count in
506)	:;;
*)	echo 'Bad character count in ''btree_action.e' >&2
		echo 'Count should be 506' >&2
esac
echo Extracting 'count_action.e'
sed 's/^X//' > 'count_action.e' << '+ END-OF-FILE ''count_action.e'
X-- count all nodes in a tree
X
Xclass COUNT_ACTION[T] export
X
X       action, nr_nodes
X
Xinherit
X       TREE_ACTION[T];
X
Xfeature
X   nr_nodes : INTEGER;
X
X   action( t : MY_TREE[T], level : INTEGER ) is
X   do
X       nr_nodes := nr_nodes + 1;
X   end;
Xend;
+ END-OF-FILE count_action.e
chmod 'u=rw,g=rw,o=' 'count_action.e'
set `wc -c 'count_action.e'`
count=$1
case $count in
249)	:;;
*)	echo 'Bad character count in ''count_action.e' >&2
		echo 'Count should be 249' >&2
esac
echo Extracting 'example.e'
sed 's/^X//' > 'example.e' << '+ END-OF-FILE ''example.e'
Xclass EXAMPLE export
X
X    -- This class is ment to show the usage of the traverse routines in
X    -- MY_TREE.
X
Xfeature
X    tree : MY_TREE[STRING];
X
X    Create is
X    local
X	tree_printer : PRINT_TREE;
X	count        : COUNT_ACTION[STRING];
X    do
X	fill_tree;
X
X	tree_printer.Create("pre_order");
X	tree.pre_order(tree_printer);
X	tree_printer.close;
X
X	tree_printer.Create("post_order");
X	tree.post_order(tree_printer);
X	tree_printer.close;
X	
X	count.Create;
X	tree.post_order(count);
X	io.putint(count.nr_nodes); io.putstring(" nodes\n"); 
X	if there_exists("four") then
X	    io.putstring("four exists"); io.new_line;
X	else
X	    io.putstring("four exists not"); io.new_line;
X	end;
X	if there_exists("2") then
X	    io.putstring("2 exists"); io.new_line;
X	else
X	    io.putstring("2 exists not"); io.new_line;
X	end;
X    end;
X
X    fill_tree is
X	-- Put some strings in the `tree'.
X    local
X	tmp : MY_TREE[STRING];
X    do
X	tree.Create("root");
X	tree.child_put_right("three");
X	tree.child_put_right("two");
X	tree.child_put_right("one");
X
X	tree.child_start;
X	tmp := tree.child;
X	tmp.child_put_right("c");
X	tmp.child_put_right("b");
X	tmp.child_put_right("a");
X
X	tree.child_start;
X	tree.child_forth;
X	tree.child_forth;
X	tmp := tree.child;
X	tmp.child_put_right("3");
X	tmp.child_put_right("2");
X	tmp.child_put_right("1");
X    end;
X
X    there_exists( s : STRING ) : BOOLEAN is
X	-- Is string `s' part of the `tree' ?
X    local
X	exists : EXISTS [STRING];
X	tmp    : MY_TREE[STRING];
X    do
X        exists.Create(s);
X	tmp := tree.bpre_order(exists);
X	Result := not tmp.Void;
X    end;
X
Xend;
+ END-OF-FILE example.e
chmod 'u=rw,g=rw,o=' 'example.e'
set `wc -c 'example.e'`
count=$1
case $count in
1564)	:;;
*)	echo 'Bad character count in ''example.e' >&2
		echo 'Count should be 1564' >&2
esac
echo Extracting 'exists.e'
sed 's/^X//' > 'exists.e' << '+ END-OF-FILE ''exists.e'
Xclass EXISTS [T->COMPARABLE] export
X
X    action
X
Xinherit
X	BTREE_ACTION[T]
Xfeature
X
X    item : T;
X
X    Create( s : T ) is
X    do
X	item := s;
X    end;
X
X    action( node : MY_TREE[T] ; level : INTEGER ) : BOOLEAN is
X    do
X	Result := not (item >= node.item and item <= node.item);
X    end;
X
Xend;
X
X
+ END-OF-FILE exists.e
chmod 'u=rw,g=rw,o=' 'exists.e'
set `wc -c 'exists.e'`
count=$1
case $count in
295)	:;;
*)	echo 'Bad character count in ''exists.e' >&2
		echo 'Count should be 295' >&2
esac
echo Extracting 'my_tree.e'
sed 's/^X//' > 'my_tree.e' << '+ END-OF-FILE ''my_tree.e'
X--  This is a descendant of TWO_WAY_TREE, with routines added for
X--  traversing the tree and performing actions on each node.
X
X--  Author      :  Jos Warmer , e-mail: jos@cs.vu.nl
X--  Organisation:  Department of Mathematics and Computer Science
X--      	   Vrije Universiteit Amsterdam
X--  Version     :  5 Februari 1990
X
Xclass MY_TREE[T] export
X	repeat TWO_WAY_TREE,
X
X	    -- various traverse routines for
X	    -- complete tree or until boolean function returns false
X
X	post_order, pre_order, bpost_order, bpre_order,
X	traverse, search_pre,
X
X	    -- internal routines
X	do_post_order {MY_TREE}, do_pre_order {MY_TREE},
X	do_bpost_order {MY_TREE}, do_bpre_order {MY_TREE},
X	do_traverse { MY_TREE}
X
Xinherit
X	TWO_WAY_TREE [T] 
X		rename
X			Create as tree_create
X		redefine
X			parent, search_child
Xfeature
X	
X    parent: MY_TREE [T];		 -- Used as anchor.
X	
X    Create( v : T ) is
X	--  Just a copy of the TWO_WAY_TREE Create routine.
X    do
X	tree_create(v);
X    end;
X
X    search_pre( a : BTREE_ACTION[T] ) : like parent is
X	-- Traverses the tree after `Current' and performs `a.action'
X	-- on each node.
X	-- Stops when `a.action' returns FALSE and returns the
X	-- node on which FALSE was returned.
X	-- Returns Void when `a.action' returns FALSE nowhere.
X	-- Keeps on traversing at parent.
X    require
X	not a.Void
X    local
X	x : like parent;
X    do
X	from  x := right_sibling
X	until x.Void or not Result.Void
X	loop
X	    Result := x.bpre_order(a);
X	    x := x.right_sibling;
X	end;
X	if Result.Void and not parent.Void then
X	    Result := parent.search_pre(a);
X	end;
X    end;
X
X    bpre_order( a : BTREE_ACTION[T] ) : like parent  is
X	-- Traverses the tree of which `Current' is the root in preorder
X	-- and performs `a.action' on each node.
X	-- Stops when `a.action' returns FALSE and returns the
X	-- node on which false was returned.
X	-- Returns Void when `a.action' returns FALSE nowhere.
X    require
X	not a.Void
X    do
X	--  extra routine to supply level
X	Result := do_bpre_order(a, 0);
X    end;
X
X    do_bpre_order(a : BTREE_ACTION[T],level : INTEGER) : like parent is
X	-- This is the working routine for bpre_order.
X    local
X	tmp : like parent;
X    do
X	if not a.action(Current, level) then
X	    Result := Current;
X	else
X	    from  tmp := first_child
X	    until tmp.Void or not Result.Void
X	    loop
X		Result := tmp.do_bpre_order(a, level+1);
X		tmp    := tmp.right_sibling
X	    end;
X	end;
X    end;
X
X    bpost_order( a : BTREE_ACTION[T] ) : like parent  is
X	-- Traverses the tree of which `Current' is the root in postorder
X	-- and performs `a.action' on each node.
X	-- Stops when `a.action' returns FALSE and returns the
X	-- node on which false was returned.
X	-- Returns Void when `a.action' returns FALSE nowhere.
X    require
X	not a.Void
X    do
X	--  extra routine to supply level
X	Result := do_bpost_order(a, 0);
X    end;
X
X    do_bpost_order(a : BTREE_ACTION[T],level : INTEGER): like parent is
X	-- This is the working routine for bpost_order.
X    local
X	tmp : like parent;
X    do
X	from  tmp := first_child
X	until tmp.Void or not Result.Void
X	loop
X	    Result := tmp.do_bpost_order(a, level+1);
X	    tmp    := tmp.right_sibling
X	end;
X
X	if not a.action(Current, level) then
X	    Result := Current;
X	end;
X    end;
X
X    post_order( a : TREE_ACTION[T] ) is
X	-- Traverses the tree of which `Current' is the root in postorder
X	-- and performs `a.action' on each node.
X    require
X	not a.Void
X    do
X	--  extra routine to supply level
X	do_post_order(a, 0);
X    end;
X
X    do_post_order( a : TREE_ACTION[T], level : INTEGER ) is
X	-- This is the working routine for post_order.
X    local
X	tmp : like parent;
X    do
X	from  tmp := first_child
X	until tmp.Void
X	loop
X	    tmp.do_post_order(a, level+1);
X	    tmp := tmp.right_sibling
X	end;
X
X	a.action(Current, level);
X    end;
X
X    traverse( action : TRAVERSE[T] ) is
X	-- Traverses the tree of which `Current' is the root.
X	-- On each node, a.enter is called first,
X	-- then the children are traversed,
X	-- and after that a.leave is called.
X	--
X	-- This combines pre- and post-order traversal:
X	-- If a.enter is empty, this is the same as post_order.
X	-- If a.leave is empty, this is the same as pre_order.
X    do
X	do_traverse(action, 0);
X    end;
X
X    do_traverse( action : TRAVERSE[T], level : INTEGER ) is
X	-- This is the working routine for traverse.
X    local
X	tmp : like parent;
X    do
X	action.enter(Current, level);
X
X	from  tmp := first_child
X	until tmp.Void
X	loop
X	    tmp.do_traverse(action, level+1);
X	    tmp := tmp.right_sibling
X	end;
X
X	action.leave(Current, level);
X    end;
X
X    pre_order( a : TREE_ACTION[T] ) is
X	-- Traverses the tree of which `Current' is the root in preorder
X	-- and performs `a.action' on each node.
X    require
X	not a.Void
X    do
X	--  extra routine to supply level
X	do_pre_order(a, 0);
X    end;
X
X    do_pre_order( a : TREE_ACTION[T], level : INTEGER ) is
X	-- This is the working routine for do_pre_order.
X    local
X	tmp : like parent;
X    do
X	a.action(Current, level);
X
X	from  tmp := first_child
X	until tmp.Void
X	loop
X	    tmp.do_pre_order(a, level+1);
X	    tmp := tmp.right_sibling
X	end;
X    end;
X
X    search_child (sought: like parent; i: INTEGER) is
X	-- Move cursor under `i'-th occurence of `sought' if
X	-- exists among children; go child_offright if none.
X	--
X	-- NOTE: This is the correct version of `search_child'.
X	--       The version in the library is incorrect.
X    require
X	arguments_not_void: not sought.Void
X    local
X	j: INTEGER
X    do
X	-- child_mark;      -- COMMENTED OUT: this was in the library
X	from
X	    go_offleft
X	invariant
X	    child_position >= 0
X	variant
X	    arity - child_position
X	until
X	    child_offright or else (j = i)
X	loop
X	    child_forth;
X	    if (sought = child) then
X		j := j + 1
X	    end -- if
X	end;
X	-- child_return      -- COMMENTED OUT: this was in the library
X			     -- Using `child_mark' at the entrance and
X			     -- `child_return' at the end, will NEVER
X			     -- move the cursor.
X    end; -- search_child
X
Xend -- class MY_TREE
+ END-OF-FILE my_tree.e
chmod 'u=rw,g=r,o=' 'my_tree.e'
set `wc -c 'my_tree.e'`
count=$1
case $count in
5943)	:;;
*)	echo 'Bad character count in ''my_tree.e' >&2
		echo 'Count should be 5943' >&2
esac
echo Extracting 'print_tree.e'
sed 's/^X//' > 'print_tree.e' << '+ END-OF-FILE ''print_tree.e'
XClass PRINT_TREE export
X
X    action, close
X
Xinherit
X	TREE_ACTION[STRING]
Xfeature
X
X    Tablength : STRING is "    ";
X    file      : FILE;
X
X    Create( file_name : STRING ) is
X    do
X	file.Create(file_name);
X	file.open_write;
X    end;
X
X    action( node : MY_TREE[STRING] ; level : INTEGER ) is
X	-- Print `node', with `level' tabs indentation on `file'.
X    local
X	i : INTEGER;
X    do
X        from  i := 0
X	until i = level
X	loop
X	    file.putstring(Tablength);
X	    i := i + 1;
X	end;
X	file.putstring(node.item); file.new_line;
X    end;
X
X    close is
X    do
X	file.close;
X    end;
X
Xend;
+ END-OF-FILE print_tree.e
chmod 'u=rw,g=rw,o=' 'print_tree.e'
set `wc -c 'print_tree.e'`
count=$1
case $count in
583)	:;;
*)	echo 'Bad character count in ''print_tree.e' >&2
		echo 'Count should be 583' >&2
esac
echo Extracting 'traverse.e'
sed 's/^X//' > 'traverse.e' << '+ END-OF-FILE ''traverse.e'
X--  Functions to apply during tree-traversal.
X--  See MY_TREE.
X--
X--  To use it, inherit from this class and define an implementation
X--  for `enter' and `leave'.
X
X--  Author      :  Jos Warmer , e-mail: jos@cs.vu.nl
X--  Organisation:  Department of Mathematics and Computer Science
X--      	   Vrije Universiteit Amsterdam
X--  Version     :  5 Februari 1990
X
Xdeferred class TRAVERSE[T] export
X
X    enter, leave
X
Xfeature
X
X    enter( node : MY_TREE[T]; level : INTEGER ) is
X	--  Called at entering the node, before the children are
X	--  visited.
X    require
X	not node.Void;
X	level >= 0;
X    deferred
X    end;
X
X    leave( node : MY_TREE[T]; level : INTEGER ) is
X	--  Called at leaving the node, after the children are
X	--  visited.
X    require
X	not node.Void;
X	level >= 0;
X    deferred
X    end;
X
Xend;
+ END-OF-FILE traverse.e
chmod 'u=rw,g=r,o=' 'traverse.e'
set `wc -c 'traverse.e'`
count=$1
case $count in
799)	:;;
*)	echo 'Bad character count in ''traverse.e' >&2
		echo 'Count should be 799' >&2
esac
echo Extracting 'tree_action.e'
sed 's/^X//' > 'tree_action.e' << '+ END-OF-FILE ''tree_action.e'
X--  Function to apply during tree-traversal.
X--  See MY_TREE.
X--
X--  To use it, inherit from this class and define an implementation
X--  for `action'.
X
X--  Author      :  Jos Warmer , e-mail: jos@cs.vu.nl
X--  Organisation:  Department of Mathematics and Computer Science
X--      	   Vrije Universiteit Amsterdam
X--  Version     :  5 Februari 1990
X
Xdeferred class TREE_ACTION[T] export
X
X    action
X
Xfeature
X
X    action(t : MY_TREE[T], level : INTEGER) is deferred end;
X
Xend -- class TREE_ACTION
+ END-OF-FILE tree_action.e
chmod 'u=rw,g=r,o=' 'tree_action.e'
set `wc -c 'tree_action.e'`
count=$1
case $count in
494)	:;;
*)	echo 'Bad character count in ''tree_action.e' >&2
		echo 'Count should be 494' >&2
esac
echo Extracting '.eiffel'
sed 's/^X//' > '.eiffel' << '+ END-OF-FILE ''.eiffel'
XROOT: example
XUNIVERSE: 
X          /usr/local/eiffel/Eiffel/library/support
X	  /usr/local/eiffel/Eiffel/library/structures
XEXTERNAL:
XNO_ASSERTION_CHECK (N):
XPRECONDITIONS (Y): ALL
XALL_ASSERTIONS (N):
XDEBUG (N):
XTRACE (N):
XOPTIMIZE (N):
XGARBAGE_COLLECTION (Y)
XC_PACKAGE (N):
XC_EXTERNAL:
XMAKE:
XVISIBLE (N):
+ END-OF-FILE .eiffel
chmod 'u=rwx,g=rx,o=' '.eiffel'
set `wc -c '.eiffel'`
count=$1
case $count in
305)	:;;
*)	echo 'Bad character count in ''.eiffel' >&2
		echo 'Count should be 305' >&2
esac
exit 0
--
                                 Jos Warmer
				 jos@cs.vu.nl
				 ...uunet!mcvax!cs.vu.nl!jos

Florman@dsg.csc.ti.COM (Bruce) (02/08/90)

Jacob,

This is a response to your article from a week or so ago.  I am able to
read netnews from my site, but I can't post.  If, after reading this
response, you would care to post it to the net for me, I'd be much
obliged.

-- Bruce Florman

========================================================================

>/ comp.lang.eiffel / marcap@hercule.cs.concordia.ca (PAWLOWSKY) / Feb 2, 1990 /
>> A while back, the passing of functions as parameters was mentioned.  If
>> memory is correct (I don't have a list of comp.lang.eiffel postings, is 
>> someone out there keeping a ftp'able copy?) it ended up with someone
>> saying it is not needed since you can redefine the function as needed
>> in the class.
>
>I take this as confirmation that no, you can't pass functions as parameters
>in Eiffel.
>
>Could somebody tell me then what the inheritance-related trick is for
>supplying a list class with the following routines:
>
>    1.	apply-routine   -- like LISP's "mapcar": same operation repeatedly
>				applied to all elements of the list
>
>    2.	insert-function -- like APL's "/":
>				given a list L such that nb_elements(L)>1
>				and a fuction F,
>					if L.nb_elements > 2 then
>						return F(L.first, L.rest)
>					else
>						return F(L.first, L.second)
>
>The one particularly useful in Eiffel is a combination of 1 and 2:
>
>    3.	for-all		-- given a BOOLEAN function F and a list L,
>				return 'true' if F(L.i_th(k)) returns true
>				for all 1 <= k <= L.nb_elements
>
>And, of course, a there-exists function is analogous.
>
>Having such features in list classes would make writing assertions about
>lists much easier.
>
>Jacob
>--
>Jacob Gore		Jacob@Gore.Com			boulder!gore!jacob

I've been waiting for someone from ISE to respond to this, but the line
seems to have gone dead.  About a year ago (March 19th to be exact), Dr.
Meyer posted his solution to this problem, and I will present my
interpretation of that solution below.  I no longer have access to an
Eiffel compiler, so I haven't been able to run the code shown below, so
there may be typos.

Please note that Eiffel is not Lisp, or APL, or Modula, and therefore
one should not be surprised that the techniques employed while
programming in Eiffel are significantly different than those used when
programming in those other languages.  When the question of "mapping
functions" first came up, I had proposed a solution that required a new
class for each operation that could be applied to the elements of a
list.  This seems to be the solution which first springs into the minds
of most new Eiffel programmers with experience with other languages.
That may not be so for someone whose first programming language is
Eiffel, but I suspect that there aren't too many such people at the
present.  Anyway, the solution presented below uses a somewhat obscure
feature of Eiffel called repeated inheritance (see section 11.6 of
OOSC), and is quite unlike what one would use in any other language of
which I'm aware.

The first concept to think about is that of the "container." [Dr.  Meyer
introduced some new terminology in his article, but I'm going to revert
to more common terms.]  Containers are data structures which hold one or
more elements of another type.  Lists, arrays, trees, sets and such are
all containers.  All containers have an element type.  For example the
element type of an array of integers is INTEGER.  The solution suggested
by Dr. Meyer says that, if you want to define a container class that
supports iteration of an operation over its elements, then you must
specify that the element type of the container supports that operation,
and that the proper place to define such operations is in the container
class itself.

Since we would like to be able to iterate over the elements of any
container type, and not just lists, we start by capturing the common
elements of iteration in a deferred class:

------------------------------------------------
deferred class ITERATOR

  feature

    initialization is deferred end;
        -- How to start the iteration.

    completion: BOOLEAN is deferred end;
        -- Is the iteration done yet?

    action is deferred end;
        -- The operation to be applied on each iteration.

    advance is deferred end;
        -- Proceed to the next step in the iteration.

    iterate is
      do
        from initialization until completion loop
          action;
          advance;
        end;
      end; -- iterate

end -- class ITERATOR
------------------------------------------------

Now suppose that we want to define a (non deferred) class called MY_LIST
of linked list which can apply two operations, called "frob" and "crank"
to its elements.  The secret is to have MY_LIST inherit twice from
ITERATOR, renaming action to frob the first time, and to crank the
second.  The iterate routine must be renamed differently in each case as
well.  The choice of a list as the container type is expedient, as it
allows the iteration control routines "initialization", "completion" and
"advance", to be effectively defined by the LIST routines "start",
"offright" and "forth" respectively (i.e. it's less work for me).  For
most other container types the control routines will need to be defined
explicitly.

------------------------------------------------
class MY_LIST [T] export

    repeat LINKED_LIST, frob_all, crank_all

  inherit

    LINKED_LIST [T];

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth,
               action as frob,
               iterate as frob_all
        define start, offright, forth;

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth,
               action as crank,
               iterate as crank_all
        define start, offright, forth;

  feature

    frob is
      do
        -- Frob the item referenced by Current's cursor.
      end;

    crank is
      do
        -- Crank the item referenced by Current's cursor.
      end;

end -- class MY_LIST
------------------------------------------------

Clearly the technique can be extended to support an arbitrary number of
operations on the list elements by simply inheriting from ITERATOR an
arbitrary number of times.  Note that one could define an intermediate
class that did the redundant renaming and defining so that each repeated
inheritance of ITERATOR is somewhat less verbose.  Such an intermediate
class would look something like this:

------------------------------------------------
deferred class LIST_ITERATOR [T] export

    repeat LIST

  inherit

    LIST [T];

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth
        define start, offright, forth;

end -- class LIST_ITERATOR
------------------------------------------------

Now, using LIST_ITERATOR, the inheritance section of MY_LIST becomes
somewhat less verbose, as shown here:

  inherit

    LINKED_LIST [T];

    LIST_ITERATOR [T]
        rename action as frob,
               iterate as frob_all;

    LIST_ITERATOR [T]
        rename action as crank,
               iterate as crank_all;

The MY_LIST class demonstrates the "mapcar" behavior that was requested
(actually it's more like "mapc", since it doesn't return a new list).
Now suppose that we want a container called TESTABLE_CONTAINER (you can
probably come up with a better name) which implements the boolean
operations "any" and "every" (i.e.  "there_exists" and "for_all" in Mr.
Gore's article) which apply a test each element, looking for the first
result of true and false respectively.  Using this class one can easily
construct containers which perform all sorts of tests and searches.  The
iteration control becomes slightly more complex now, because we need to
provide a way to "short circuit" the iteration without processing all of
the elements.

------------------------------------------------
deferred class TESTABLE_CONTAINER

  inherit

    ITERATOR
        rename completion as done_any,
               iterate as iterate_for_any,
               action as apply_any_test;

    ITERATOR
        rename completion as done_every,
               action as apply_every_test,
               iterate as iterate_for_every;

  feature

    test_value: BOOLEAN;

    tested_last_element: BOOLEAN is deferred end;
        -- Have we exhausted the elements in the container?

    apply_any_test is do test_value := any_test end;

    any_test: BOOLEAN is deferred end;
        -- Test the current element.

    done_any: BOOLEAN is
      do
	Result := test_value or else tested_last_element;
      end;

    any: BOOLEAN is
      local
        old_test_value: BOOLEAN;
      do
        old_test_value := test_value;
        test_value := False;
        iterate_for_any;
        Result := test_value;
        test_value := old_test_value;
      end;

    apply_every_test is do test_value := every_test end;

    every_test: BOOLEAN is deferred end;
        -- Test the current element.

    done_every: BOOLEAN is
      do
        Result := not test_value or else tested_last_element;
      end;

    every: BOOLEAN is
      local
        old_test_value: BOOLEAN;
      do
        old_test_value := test_value;
        test_value := True;
        iterate_for_every;
        Result := test_value;
        test_value := old_test_value;
      end;

end -- class TESTABLE_CONTAINER
------------------------------------------------

At the end of his article, Dr.  Meyer included a comment that the use of
repeated inheritance causes the compiler to issue warnings, and that he
feels somewhat uneasy about compiler warnings in general (the argument
being: "either there is an error and you cannott compile, or there is no
error and you shut up").  He feels however, that from a pragmatic
standpoint, it is probably useful to inform the user when (s)he is using
an advanced feature of the language, since its use may be accidental.

Well, I've probably gone on way too long already, so I'll cut it off
here.  The examples above were inspired by Dr. Meyer's article, but have
been embellished by myself.  I therefore take full responsibility for
any errors in code or concept, and misrepresentations of Dr. Meyer's
technique.  My employers on the other hand, take no responsibility for
any of this.

Cheers,

    Bruce Florman
    florman@dsg.csc.ti.com

marcap@hercule.cs.concordia.ca (PAWLOWSKY) (02/08/90)

FORWARDED MESSAGE (respond to author)



========================================================================

>/ comp.lang.eiffel / marcap@hercule.cs.concordia.ca (PAWLOWSKY) / Feb 2, 1990 /
>> A while back, the passing of functions as parameters was mentioned.  If
>> memory is correct (I don't have a list of comp.lang.eiffel postings, is 
>> someone out there keeping a ftp'able copy?) it ended up with someone
>> saying it is not needed since you can redefine the function as needed
>> in the class.
>
>I take this as confirmation that no, you can't pass functions as parameters
>in Eiffel.
>
>Could somebody tell me then what the inheritance-related trick is for
>supplying a list class with the following routines:
>
>    1.	apply-routine   -- like LISP's "mapcar": same operation repeatedly
>				applied to all elements of the list
>
>    2.	insert-function -- like APL's "/":
>				given a list L such that nb_elements(L)>1
>				and a fuction F,
>					if L.nb_elements > 2 then
>						return F(L.first, L.rest)
>					else
>						return F(L.first, L.second)
>
>The one particularly useful in Eiffel is a combination of 1 and 2:
>
>    3.	for-all		-- given a BOOLEAN function F and a list L,
>				return 'true' if F(L.i_th(k)) returns true
>				for all 1 <= k <= L.nb_elements
>
>And, of course, a there-exists function is analogous.
>
>Having such features in list classes would make writing assertions about
>lists much easier.
>
>Jacob
>--
>Jacob Gore		Jacob@Gore.Com			boulder!gore!jacob

I've been waiting for someone from ISE to respond to this, but the line
seems to have gone dead.  About a year ago (March 19th to be exact), Dr.
Meyer posted his solution to this problem, and I will present my
interpretation of that solution below.  I no longer have access to an
Eiffel compiler, so I haven't been able to run the code shown below, so
there may be typos.

Please note that Eiffel is not Lisp, or APL, or Modula, and therefore
one should not be surprised that the techniques employed while
programming in Eiffel are significantly different than those used when
programming in those other languages.  When the question of "mapping
functions" first came up, I had proposed a solution that required a new
class for each operation that could be applied to the elements of a
list.  This seems to be the solution which first springs into the minds
of most new Eiffel programmers with experience with other languages.
That may not be so for someone whose first programming language is
Eiffel, but I suspect that there aren't too many such people at the
present.  Anyway, the solution presented below uses a somewhat obscure
feature of Eiffel called repeated inheritance (see section 11.6 of
OOSC), and is quite unlike what one would use in any other language of
which I'm aware.

The first concept to think about is that of the "container." [Dr.  Meyer
introduced some new terminology in his article, but I'm going to revert
to more common terms.]  Containers are data structures which hold one or
more elements of another type.  Lists, arrays, trees, sets and such are
all containers.  All containers have an element type.  For example the
element type of an array of integers is INTEGER.  The solution suggested
by Dr. Meyer says that, if you want to define a container class that
supports iteration of an operation over its elements, then you must
specify that the element type of the container supports that operation,
and that the proper place to define such operations is in the container
class itself.

Since we would like to be able to iterate over the elements of any
container type, and not just lists, we start by capturing the common
elements of iteration in a deferred class:

------------------------------------------------
deferred class ITERATOR

  feature

    initialization is deferred end;
        -- How to start the iteration.

    completion: BOOLEAN is deferred end;
        -- Is the iteration done yet?

    action is deferred end;
        -- The operation to be applied on each iteration.

    advance is deferred end;
        -- Proceed to the next step in the iteration.

    iterate is
      do
        from initialization until completion loop
          action;
          advance;
        end;
      end; -- iterate

end -- class ITERATOR
------------------------------------------------

Now suppose that we want to define a (non deferred) class called MY_LIST
of linked list which can apply two operations, called "frob" and "crank"
to its elements.  The secret is to have MY_LIST inherit twice from
ITERATOR, renaming action to frob the first time, and to crank the
second.  The iterate routine must be renamed differently in each case as
well.  The choice of a list as the container type is expedient, as it
allows the iteration control routines "initialization", "completion" and
"advance", to be effectively defined by the LIST routines "start",
"offright" and "forth" respectively (i.e. it's less work for me).  For
most other container types the control routines will need to be defined
explicitly.

------------------------------------------------
class MY_LIST [T] export

    repeat LINKED_LIST, frob_all, crank_all

  inherit

    LINKED_LIST [T];

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth,
               action as frob,
               iterate as frob_all
        define start, offright, forth;

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth,
               action as crank,
               iterate as crank_all
        define start, offright, forth;

  feature

    frob is
      do
        -- Frob the item referenced by Current's cursor.
      end;

    crank is
      do
        -- Crank the item referenced by Current's cursor.
      end;

end -- class MY_LIST
------------------------------------------------

Clearly the technique can be extended to support an arbitrary number of
operations on the list elements by simply inheriting from ITERATOR an
arbitrary number of times.  Note that one could define an intermediate
class that did the redundant renaming and defining so that each repeated
inheritance of ITERATOR is somewhat less verbose.  Such an intermediate
class would look something like this:

------------------------------------------------
deferred class LIST_ITERATOR [T] export

    repeat LIST

  inherit

    LIST [T];

    ITERATOR
        rename initialization as start,
               completion as offright,
               advance as forth
        define start, offright, forth;

end -- class LIST_ITERATOR
------------------------------------------------

Now, using LIST_ITERATOR, the inheritance section of MY_LIST becomes
somewhat less verbose, as shown here:

  inherit

    LINKED_LIST [T];

    LIST_ITERATOR [T]
        rename action as frob,
               iterate as frob_all;

    LIST_ITERATOR [T]
        rename action as crank,
               iterate as crank_all;

The MY_LIST class demonstrates the "mapcar" behavior that was requested
(actually it's more like "mapc", since it doesn't return a new list).
Now suppose that we want a container called TESTABLE_CONTAINER (you can
probably come up with a better name) which implements the boolean
operations "any" and "every" (i.e.  "there_exists" and "for_all" in Mr.
Gore's article) which apply a test each element, looking for the first
result of true and false respectively.  Using this class one can easily
construct containers which perform all sorts of tests and searches.  The
iteration control becomes slightly more complex now, because we need to
provide a way to "short circuit" the iteration without processing all of
the elements.

------------------------------------------------
deferred class TESTABLE_CONTAINER

  inherit

    ITERATOR
        rename completion as done_any,
               iterate as iterate_for_any,
               action as apply_any_test;

    ITERATOR
        rename completion as done_every,
               action as apply_every_test,
               iterate as iterate_for_every;

  feature

    test_value: BOOLEAN;

    tested_last_element: BOOLEAN is deferred end;
        -- Have we exhausted the elements in the container?

    apply_any_test is do test_value := any_test end;

    any_test: BOOLEAN is deferred end;
        -- Test the current element.

    done_any: BOOLEAN is
      do
	Result := test_value or else tested_last_element;
      end;

    any: BOOLEAN is
      local
        old_test_value: BOOLEAN;
      do
        old_test_value := test_value;
        test_value := False;
        iterate_for_any;
        Result := test_value;
        test_value := old_test_value;
      end;

    apply_every_test is do test_value := every_test end;

    every_test: BOOLEAN is deferred end;
        -- Test the current element.

    done_every: BOOLEAN is
      do
        Result := not test_value or else tested_last_element;
      end;

    every: BOOLEAN is
      local
        old_test_value: BOOLEAN;
      do
        old_test_value := test_value;
        test_value := True;
        iterate_for_every;
        Result := test_value;
        test_value := old_test_value;
      end;

end -- class TESTABLE_CONTAINER
------------------------------------------------

At the end of his article, Dr.  Meyer included a comment that the use of
repeated inheritance causes the compiler to issue warnings, and that he
feels somewhat uneasy about compiler warnings in general (the argument
being: "either there is an error and you cannott compile, or there is no
error and you shut up").  He feels however, that from a pragmatic
standpoint, it is probably useful to inform the user when (s)he is using
an advanced feature of the language, since its use may be accidental.

Well, I've probably gone on way too long already, so I'll cut it off
here.  The examples above were inspired by Dr. Meyer's article, but have
been embellished by myself.  I therefore take full responsibility for
any errors in code or concept, and misrepresentations of Dr. Meyer's
technique.  My employers on the other hand, take no responsibility for
any of this.

Cheers,

    Bruce Florman
    florman@dsg.csc.ti.com

bertrand@eiffel.UUCP (Bertrand Meyer) (02/17/90)

In article <1843@clyde.concordia.ca>, marcap@hercule.cs.concordia.ca
(PAWLOWSKY) comments on a series of postings on the absence of a mechanism
in Eiffel to pass routines as arguments to routines:

> [...]
> I've been waiting for someone from ISE to respond to this, but the line
> seems to have gone dead.  About a year ago (March 19th to be exact),
> Bertrand Meyer posted his solution to this problem [...]

There are two reasons for the recent lack of postings from Interactive
on this topic.

The first reason is precisely last year's message, as recalled
by Mr. Pawlowsky; in that message I trid to address the question as well
as I could, showing that there was no need for passing routines in Eiffel
since other mechanisms were available which were more in line with the
object-oriented method. When the question came up again on the net,
I felt that there was not much to add to that message.

The second reason is simply that none of us here at Interactive has been
able to digest the recent messages on the topic. Five or six articles  
at least, each several hundred lines long, and each well thought-out,
were posted recently. They deserve more than quickly drafted answers,
especially at a time when we are taking a hard look at the language with
the official aim of fixing it for many years. Give us some time.
-- 
-- Bertrand Meyer
bertrand@eiffel.com