bertrand@eiffel.UUCP (Bertrand Meyer) (03/12/89)
From <1297@wasatch.UUCP>, by gilad%cs.utah.edu@wasatch.UUCP (Gilad Bracha), regarding my earlier posting (<114@eiffel.UUCP>, in response to the question asked in <112@eiffel.UUCP>) on how to implement iterators in Eiffel: > Bertrand Meyer proposes a solution, using > a combination of deferred classes and constrained genericity. > The solution proposed is inadequate. It requires us to define > a special class for every function of every type we might want to > use over a list (or set, or whatever structure). > We would have to have classes for INTEGERs with action SQR, INTEGERs > with action CUBE, INTEGERs with action SQRT, etc. And then we would > need classes for BOOLEANs with action NOT, LISTs with action LENGTH etc. First let me introduce a couple of terms for the sake of this discussion. I will call ``repository'' any data structure used to hold elements of a certain type; this type will be called the ``carrier type'' of the repository. For example a set of integers is a repository, with carrier type INTEGER. Repositories are also called ``container data structures''. In Eiffel, repositories are obtained as instances of generic classes; their carrier types are represented by the generic parameters. Now to the point raised by Mr. Bracha. The basic idea of object-oriented programming is data abstraction; in other words, the observation that data is (are?) not properly described until you have specified the associated operations. The solution I suggested - and I reaffirm that, in my view, it is the proper one in Eiffel - simply says that, if you want to write a repository class that supports, among its features, the iteration of a certain operation (which I will call ``repeatable_operation'') over repository elements, then you must specify that the carrier type supports such a ``repeatable_operation''. Since the possible carrier types are represented by the generic parameter, say V, of the repository class (called ACTIVE_SET in the example discussed in the earlier posting), the Eiffel technique is simply to say that V is not an arbitrary type but any class that inherits from a certain class (which I called VALTYPE). This is supported by constrained inheritance, with the following syntax: class ACTIVE_SET [V -> VALTYPE] ... VALTYPE is a deferred class that simply includes the specification of the repeatable operation. Specification, not implementation: contrary to what Mr. Bracha wrote in the message extract reproduced above, VALTYPE does not need to express what ``repeatable_operation'' is (e.g. square root or cube computation), but simply to specify its signature (types of its arguments and results), plus any semantic properties, expressed through assertions. Specifying the signature is required for static type checking. In class VALTYPE, repeatable_operation is a deferred routine, that is to say a routine specified but not implemented. [As an example of semantic information, if one feature of ACTIVE_SET was a ``reduction operation'' in the sense of APL or vector computers, where ``sigma'' is the reduction of ``plus'', ``big pi'' is the reduction of ``times'' etc., we may want to express that the operation has a zero element.] > The question is really whether there is a way to abstract over > routines. As another example, suppose we wish to define a MAP > function, roughly like mapcar in LISP. > [...] > > According to OOSC, Eiffel does not have a type "routine", or in other > words, routines are not first-class values in the language. So there is > no way to express the type of MAP, and thus, no way to express MAP at all. > > [...] > > So the question is, should Eiffel be extended with first-class > routines, or should a more restricted mechanism (like iterators > in CLU) be used. The answer to the question ``is there a way to abstract over routines'' is clear: Yes, using deferred routines. A deferred routine is precisely that: an abstract routine - specified by its signature and semantic properties, but not implemented. The answer to the comment ``there is no way to express the type of MAP'' is: An iterator routine (in a repository class such as ACTIVE_SET) corresponding to the Lisp MAP will have a perfectly defined Eiffel type. If, on the other hand, you are thinking of the MAP function as it exists in Lisp, the question is moot since such a function cannot be expressed in the same form in Eiffel. [An important comment about the iterator routine in ACTIVE_SET: this routine will NOT be deferred. Non-deferred routines that call deferred routines are one of the fundamental Eiffel techniques for implementing advanced levels of reusability; see section 10.3.8 of OOSC, ``factoring out common behaviors''. This is only a half-page paragraph but I now believe that the ideas it expresses are among the four or five really essential concepts of the whole object-oriented approach.] My answer to the last question, ``should Eiffel be extended with first-class routines'' is clear: no. I have nothing against first-class functions and iterators, but they do not belong in Eiffel, where the equivalent effect is obtained by the techniques described in my previous posting and (I hope) reinforced here. First-class functions are great in Lisp - although in fact I wouldn't use Lisp as my favorite example in this case, since Lisp shows its age in such matters; instead I would quote more modern functional languages, especially Robin Milner's ML and David Turner's Miranda (Backus's FP is perhaps another contender). But what works in one context is not necessarily appropriate in another. There is room in this world for functional languages; Eiffel is something else. Technically, it would be extremely unpleasant to have higher-order functions in Eiffel. The problem is type checking. Typed languages have not been very good at accommodating routine arguments (by ``routine argument'' I mean ``an argument to a routine, where the argument itself represents a routine''). Pascal did a rather imperfect job, as analyzed by Welsh, Sneeringer and Hoare in their article ``Ambiguities and Insecurities in Pascal'', published in Software, Practice and Experience, 7, 1977, pages 685-696. Algol 68 fared better, but I don't know if Algol 68 compilers were able to reconcile this feature with separate compilation. Interestingly enough, one strongly typed language (perhaps the only one) that achieved an effect similar to that of routine arguments, while being expressly designed for separate compilation, is Ada. But then Ada doesn't have routine arguments either: the technique it uses is to have routine as *generic* arguments to packages. Conceptually, this relies on the same idea as the Eiffel technique: specify in advance the signature of the operations that may be applied to any actual carrier type. (No semantics can be specified in Ada because of the lack of assertions.) One way to summarize this discussion is to say that I do not know of any good way to reconcile the following three language traits: 1. Routine arguments (in the above sense, i.e. routine arguments to routines). 2. Static type checking. 3. A language design that makes it possible to have separate compilation of modules. If you take two of these requirements, then solutions exist: 1-2 (Algol 68), 2-3 (Ada, Eiffel, each with its own techniques to achieve the effect of 1), 1-3 (compiled functional languages, although the ones I can think of are usually interpreted rather than compiled). However the combination of 1, 2 and 3 appears a rather tough challenge, and I don't think this challenge needs to be addressed in Eiffel because of the availability of a clean and simple object-oriented solution. More generally, the problem is one of language design. The principle followed throughout Eiffel is that if the language supports one good way to achieve a certain important category of goals (such as deferred routines and classes, combined with constrained genericity, where the goal is to enable the implementation of iterators), then it does not need to support two, and in fact it should not. This means that everybody's favorite language features are not necessarily to be found in Eiffel. (In fact, some features I do like are absent.) Language design is a choice and is defined as much by what is excluded as by what is included. [Here I am really repeating myself; I discussed these issues in an article that recently appeared in ``Structured Programming'', a journal published by Springer-Verlag, v. 10, no.1, 1989, pages 19-39; the title is ``From Structured Programming to Object-Oriented Design: The Road to Eiffel''. See section 6.] So Eiffel is not Lisp, nor is it C or Modula. I don't think there is any need to apologize for this, although it is perfectly understandable why someone should prefer to program in Lisp, C or Modula. Well, I really meant in Lisp or in Modula. -- Bertrand Meyer.
jouvelot@mit-vax.LCS.MIT.EDU (Pierre Jouvelot) (03/13/89)
In article <118@eiffel.UUCP> bertrand@eiffel.UUCP (Bertrand Meyer) writes: > One way to summarize this discussion is to say that I do not know of any >good way to reconcile the following three language traits: > > 1. Routine arguments (in the above sense, i.e. routine arguments to > routines). > 2. Static type checking. > 3. A language design that makes it possible to have separate > compilation of modules. These points are addressed in the design of the FX-87 programming language (Gifford. D. K., Jouvelot, P., Lucassen, J. M. and Sheldon, M. A. "The FX-87 Reference Manual". MIT/LCS/TR-407, September 1987 and Gifford, D. K., and Lucassen, J. M. "Polymorphic Effect Systems". In Proceedings of ACM POPL Conference, January 1988): . FX-87 allows first-class higher-order functions (point 1). . FX-87 is statically type-checked. Its type system has the power of the second-order polymorphic lambda-calculus. It uses an effect system to determine, at compile-time, the side-effects potentially performed by the evaluation of expressions, thus allowing "safe polymorphism" in the presence of mutation (point 2). . FX-87 allows separate compilation. Modules can be simulated by polymorphic functions that are abstracted over the abstract type T and the signature (the type of records of functions) of T (point 3). A prototype version of FX-87 (Jouvelot, P., and Gifford, D. K. "The FX-87 Interpreter". In Proceedings of the 2nd Int. Conf. on Comp. Lang. IEEE, October 1988) written in Scheme and running under CommonLISP is available on request at fx-request@brokaw.lcs.mit.edu. The current redesign of FX will improve the third point by introducing first-class explicit modules (seen as a variety of existential types) and type inference while preserving the other aspects of FX-87. J'espere que cette information sera utile, Pierre -- Pierre Jouvelot . CAI, Ecole des Mines de Paris, France (JOUVELOT@FREMP11.bitnet) . LCS, MIT, Cambridge (JOUVELOT@BROKAW.LCS.MIT.EDU)
greg@cantuar.UUCP (G. Ewing) (03/14/89)
Bertrand Meyer (bertrand@eiffel.UUCP) writes: > One way to summarize this discussion is to say that I do not know of any >good way to reconcile the following three language traits: > > 1. Routine arguments (in the above sense, i.e. routine arguments to > routines). > 2. Static type checking. > 3. A language design that makes it possible to have separate > compilation of modules. What about Modula-II? As far as I can see, it copes quite well with all three of these. Note that I'm not questioning your choice to leave routine arguments out of Eiffel. I just don't see where the necessary conflict arises between these three things. Greg Ewing Internet: greg@cantuar.uucp Spearnet: greg@nz.ac.cantuar Telecom: +64 3 667 001 x8357 UUCP: ...!{watmath,munnari,mcvax,vuwcomp}!cantuar!greg Post: Computer Science Dept, Univ. of Canterbury, Christchurch, New Zealand Disclaimer: The presence of this disclaimer in no way implies any disclaimer.
henkc@cognos.uucp (Henk Cazemier) (03/17/89)
In article <118@eiffel.UUCP> bertrand@eiffel.UUCP (Bertrand Meyer) writes: > From <1297@wasatch.UUCP>, by gilad%cs.utah.edu@wasatch.UUCP >> Bertrand Meyer proposes a solution, using >> a combination of deferred classes and constrained genericity. >> The solution proposed is inadequate. It requires us to define >> a special class for every function of every type we might want to >> use over a list (or set, or whatever structure). > > class ACTIVE_SET [V -> VALTYPE] ... > > VALTYPE is a deferred class that simply includes the specification of >the repeatable operation. Specification, not implementation: contrary >to what Mr. Bracha wrote in the message extract reproduced above, >VALTYPE does not need to express what ``repeatable_operation'' is >(e.g. square root or cube computation), but simply to specify >its signature (types of its arguments and results), plus any semantic >properties, expressed through assertions. Specifying the signature is >required for static type checking. In class VALTYPE, repeatable_operation >is a deferred routine, that is to say a routine specified but not >implemented. > This approach leads to an environment where there will be a separate class for each different specification of the signature. Using this approach as a general solution generates a large number of classes, which only contain a single routine. I used this approach at one time and quickly discovered that there should be a better way to accomplish this functionality. I implemented a class called <routine>, which has an attribute <routineAddress> and <context>. <routineAddress> is obtained by using a feature similar to 'eif_attr' and <context> is any object that inherits from the class <RoutineClient>. Some of the features are: setToRoutineInObject (rname: String; obj: RoutineClient) setToRoutineInClass (rname: String; cname: String) callProcedure callOne (obj: RoutineClient) callProcedureFor (context: RoutineClient) The call* features use a routine similar to the 'eif_rout' feature. (The 'eif_attr' and 'eif_rout' features were published by Dr. Meyer about a week ago.) The disadvantage is that there is absolutely no compile time or run time checking, though the parameters passed on the 'call' features are enforced, there is no check that you use the right 'call' feature. This is a big disadvantage, but I think that the language can be extended such that routines are treated as first class objects. > One way to summarize this discussion is to say that I do not know of any >good way to reconcile the following three language traits: > > 1. Routine arguments (in the above sense, i.e. routine arguments to > routines). > 2. Static type checking. > 3. A language design that makes it possible to have separate > compilation of modules. > The use of routines as objects can be checked at compile time by using a syntax that the defines the signature. Maybe something like: Routine <zero or more generics> <optional return> the feature 'execute' would do the actual call for an instance of this. Like: CLASS VeryComplicatedStructure EXPORTS processUntil FEATURE ..... processUntil (proc: Routine[T->Comparable, Integer]: Boolean) is local done : Boolean; rank : Integer; element: Comparable do FROM element := firstElement UNTIL element.void OR done LOOP done := proc.execute (element, rank); rank := rank + 1; element := element.next END end; END; -- VeryComplicatedStructure This allows you to make classes like: CLASS myApplication FEATURE theCollection: VeryComplicatedSturcture; ..... printSomeElements (element: Comparable; rank: Integer): Boolean is do -- print the elements contents and the rank.... howMany := howMany - 1; result := howMany < 0 end; processAllElements (element: Comparable; rank: Integer): Boolean is do -- print the elements contents and the rank.... result := FALSE end; howMany : Integer; ... printElements is do -- if want to print a little then do howMany := 10; theCollection.processUntil ([printSomeElements]); -- if want to print all do theCollection.processUntil ([processAllElements]); end; end; Classes may also contain attributes that are Routine objects, something like: theActionProc : Routine[T->Comparable, Real, Real]; Using this approach the compiler will be able to determine whether a routine is used properly. I look forward to seeing this construct supported by Eiffel in the not so distant future. -- Henk Cazemier P.O. Box 9707 Cognos Incorporated 3755 Riverside Dr. VOICE: (613) 738-1338 x5220 FAX: (613) 738-0002 Ottawa Ontario, CANADA K1G 3Z4 UUCP: decvax!utzoo!dciem!nrcaer!cognos!henkc