Path: utzoo!attcan!uunet!clyde.concordia.ca!hercule!marcap From: marcap@hercule.cs.concordia.ca (PAWLOWSKY) Newsgroups: comp.lang.eiffel Subject: Re: Passing functions as parameters Message-ID: <1843@clyde.concordia.ca> Date: 7 Feb 90 17:24:15 GMT References: <1832@clyde.concordia.ca> Sender: usenet@clyde.concordia.ca Reply-To: marcap@hercule.CS.Concordia.CA (PAWLOWSKY) Organization: Concordia University, Montreal Quebec Lines: 302 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