Re: First Class Routines [Long again]

Re: First Class Routines [Long again]

[Bertrand Meyer]

    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.

Re: First Class Routines [Long again]

[Pierre Jouvelot]

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)

Re: First Class Routines [Long again]

[G. Ewing]

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.

Re: First Class Routines [Not long this time]

[Dave Berry]

In article <118@eiffel.UUCP> bertrand@eiffel.UUCP (Bertrand Meyer) writes:
>    First-class functions are great in [...] modern functional languages,
>especially Robin Milner's ML and David Turner's Miranda.
>    [...]
>    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.

Standard ML supports all three of these requirements.  I believe Miranda
does as well.  The separate compilation schemes used in New Jersey ML
and Poly/ML are rather different from those used by conventional
languages, but this is mainly because ML is an interactive language,
not because of the static type checking.

Perhaps the problem is harder if you have type parameterisation instead
of (or as well as) universal polymorphism?

>    More generally, the problem is one of language design.

I think that routine arguments combine rather nicely with the other
features of eiffel, at least what I've seen of it (a few journal articles).
But it's your language, not mine.  Is your book available in the U.K.,
by the way?

Follow-ups to comp.lang.eiffel, I should think.

Dave Berry,	Laboratory for Foundations of Computer Science, Edinburgh.
		db%lfcs.ed.ac.uk@nss.cs.ucl.ac.uk
		<Atlantic Ocean>!mcvax!ukc!lfcs!db

Re: First Class Routines [Long again]

[Henk Cazemier]

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