Re: First Class Routines [Long again]

[bertrand@eiffel.UUCP (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.