🚀 go-pugleaf

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