Tuples, routine objects and iterators
This technical note is the text of proposal submitted by
ISE to the Nonprofit International Consortium for Eiffel
(NICE). It describes a set of extensions to Eiffel.
This is a working document and is currently under discussion.
Because the note followed earlier discussions within the language
committee of NICE, it lacks the customary "introduction" and
"rationale" parts explaining the purpose of the proposed
extensions. The rationale and applications should, however,
quickly become clear to any reader familiar with Eiffel.
1. Tuple types
A new Kernel Library class is introduced: TUPLE.
Alone among all classes, class TUPLE has a variable number
of generic parameters.
Conformance rules:
[CONF1]
For n >= 0
TUPLE [U1, U2, ..., Un, Un+1] conforms to
TUPLE [U1, U2, ..., Un]
(and hence to TUPLE [T1, T2, ..., Tn] if each of
the Ui conforms to each of the Ti for 1 <= i <= n.)
In particular all tuple types conform to TUPLE, with no
parameter.
[CONF2]
For n >= 0
If *every* one of the types T1, T2, ..., Tn conforms
to a type T, then TUPLE [T1, T2, ..., Tn] conforms
to ARRAY [T].
Definition: a "tuple type" is any type based on class TUPLE,
i.e. any type of the form TUPLE [T1, T2, ..., Tn] for any n
(including 0, for which there is no generic parameter).
(Note 1: CONF1 should be understood in terms of the underlying
mathematical model. Mathematically, TUPLE [T1, T2, ..., Tn]
is the set TUPLEn of all partial functions f from N+ (the set of
non-negative integers) to T1 U T2 U ... Tn, such that:
The domain of f contains the interval 1..n (in other
words, f is defined for any i such that 1 <= i <= n).
For 1 <= i <= n, f (i) is a member of Ti.
With this definition, TUPLEn is indeed a subset of TUPLEn+1,
and in particular TUPLE0, the empty set, is a subset of
TUPLEn for any n.)
Semantics: an instance of TUPLE [T1, T2, ..., Tn] is a tuple
whose first element is an instance of T1, the second element
being an instance of T2 etc. (The precise definition is the
mathematical one given in note 1.) Note that there can be more
than n elements to the tuple: for example a tuple with first element
5 and second element "FOO" is an instance of all of the following
tuple types: TUPLE; TUPLE [INTEGER]; TUPLE [INTEGER, STRING].
(Note 2: It may seem restrictive at first to permit only
one class, TUPLE, to have an arbitrary number of actual
generic parameters. Why not have a general mechanism
for declaring any class C so that all of C [X],
C [X, Y] etc. are valid?
But in fact this is not really a restriction. To obtain
this effect without any complicated language convention,
just declare C as
C [G -> TUPLE]
and then use the generic derivations
C [TUPLE [X]]
C [TUPLE [X, Y]]
and so on. This also makes it possible to have the effect
of some fixed parameters and some variable ones, as in
C [G, H, I -> TUPLE]
so we have all the necessary flexibility.)
2. Tuple expressions
Let e1, e2, ..., en be expressions of respective types
T1, T2, ..., Tn. Then the expression
[TE1]
<>
denotes an instance of TUPLE [T1, T2, ..., Tn], whose first
element is e1, the second element being e2 etc.
It is permitted in certain cases to omit the delimiters
<< and >>, giving just
[TE2]
e1, e2, ..., en
This is legal in the following cases for which there is
no ambiguity:
n > 1
If the tuple expression is used as routine argument
(see section 3), in which case the parentheses remove
the ambiguity.
Outside of these cases form TE2 would be ambiguous, since
assuming e.g. e1 of type INTEGER then e1 could be understood
as an expression of type TUPLE [INTEGER] as well as INTEGER.
The form with delimiters is also necessary in case of nesting:
for example
<<1, 2, 3>>
is a tuple with three elements (representing an instance
of TUPLE [INTEGER, INTEGER, INTEGER]), whereas
<<1, <<2, 3>>>>
is a tuple with two elements, the second one itself a
tuple; the overall expression represents an instance
of TUPLE [INTEGER, TUPLE [INTEGER, INTEGER]].
3. TUPLE features
I haven't completely worked out the features of class TUPLE but
here are some of them:
count (number of significant elements)
item (i), with the obvious precondition: the i-th element,
of type Ti.
put (x, i), with the obvious precondition: replace i-th element
with x. Argument x must be of type Ti.
is_equal: redefined to consider only the first n elements,
where n is the smaller length.
Maybe something like
stripped (i): a tuple of type
TUPLE [T1, T2, Ti-1, Ti+1, ..., Tn], derived from the
current one by removing the i-th component, again with
the obvious precondition.
wedged (x, i): a tuple with one more element, inserted
at position i.
infix "+": tuple concatenation
infix "++": element concatenation; t ++ x is the same thing as
t.wedged (x, t.count + 1)
In addition, there may be in class GENERAL the following three
features:
acceptable_tuple (t: TUPLE): BOOLEAN
-- Is `t' convertible into an object of the current
-- type?
associated_tuple: TUPLE
-- Tuple made of all of this object's field
ensure
acceptable_tuple (Result)
make_from_tuple (t: TUPLE)
-- Reset from `t'.
require
acceptable_tuple (t)
ensure
equal (associated_tuple, t)
4. What have we gained so far?
First we have solved the only case in the Eiffel language in which
an expression has no precisely defined type: polymorphic manifest
arrays. We don't have manifest arrays any more, but manifest tuples,
with a precisely defined type. No incompatibility is introduced
thanks to rule CONF2.
Second, we can define functions that return multiple results.
This is a quite significant increase in expressive power.
No common language has that. (You have to look at Lisp and
functional languages.) Just define TUPLE [...] as the
result type; in the function, you will write things like
Result := <>
Also, from a theoretical viewpoint, feature calls are simpler
and more homogeneous: every feature takes exactly one tuple as
argument and returns exactly one tuple as a result. (Either of
these tuples may be empty: the first for a feature with no
argument, the second for a procedure.) The syntax for a
call becomes
Feature [Arguments]
with Arguments defined as
'(' Tuple_expression ')'
where the Tuple_expression can be in either of the forms
given in section 2, TE1 and TE2. This means, by the way,
that instead of
[CALL2]
f (a, b, c)
(form TE2) you can also write
[CALL1]
f (<>)
CALL2 can in fact be viewed as an abbreviation for CALL1.
5. Routine objects
We introduce three new kernel classes:
deferred ROUTINE [TARGET_TYPE, ARGUMENT_TYPE -> TUPLE]
PROCEDURE [TARGET_TYPE, ARGUMENT_TYPE -> TUPLE]
inherit
ROUTINE [TARGET_TYPE, ARGUMENT_TYPE]
FUNCTION [TARGET_TYPE, ARGUMENT_TYPE -> TUPLE, RESULT_TYPE]
inherit
ROUTINE [TARGET_TYPE, ARGUMENT_TYPE]
A type of the form
FUNCTION [TARGET_TYPE, TUPLE [T1, T2, ..., Tn], RES]
represents functions applicable to targets of type TARGET_TYPE,
with n arguments of respective types T1, T2, ..., Tn, returning
results of type RES.
Same thing for PROCEDURE types except that there is no RES.
(Note 2: the presence of TARGET_TYPE indicates that as
compared to their mathematical equivalents the routines
have been curried on their first argument, as is proper
in O-O development.)
(Note 3: the symmetry between arguments and results is not
complete since, of the last two formal generic parameters of
FUNCTION, only ARGUMENT_TYPE is constrained to TUPLE.)
Definitions: a routine class is a descendant of ROUTINE. A routine
type is a type whose base class is a routine class. Similarly,
"procedure class", "function class", "procedure type" and
"function type". A routine object is an instance of a
routine type; similarly, "procedure object" and "function object".
(Note 4: A procedure class is also a routine class; so is a function
class. A procedure type is also a routine type; so is a function type.
A procedure object is also a routine object; so is a function object.)
Conformance:
[CONF3]
All routine types conform to POINTER.
(Note 5: The result of assigning a routine object to a POINTER
entity is to assign the address of the routine. This will
probably require making POINTER a reference rather than
expanded type.)
Features of routine classes:
call (target: TARGET_TYPE; arguments: ARGUMENT_TYPE)
deferred in ROUTINE, effected by the two heirs. This
calls the associated routine on target `target' with
arguments `arguments'. This has the precondition
target /= Void.
In addition, FUNCTION has the feature
last_result: RESULT_TYPE
giving the result of the last call to `call' (Void if none).
One can also use the boolean-valued function
eval (target: TARGET_TYPE; arguments: ARGUMENT_TYPE): BOOLEAN
which calls `call' and returns the value of`last_result'.
Rather than r.call (targ, args), it is possible (I think
this is useful, but am not sure) to use
r.set_target (targ)
r.set_arguments (args)
r.apply
In addition it would be nice to have the feature
precondition: FUNCTION [TARGET_TYPE, ARGUMENT_TYPE, BOOLEAN]
giving the precondition of the routine, but this may be a
hassle to implement.
Expressions of routine type, other than entities declared of
a routine type, include "Address expressions" of the form
$r
where r is a routine of the enclosing class. The value
is a routine object representing the application of `r'
to the current object.
(Note 6: this was previously taken to be of type POINTER.
Thanks for the conformance rule CONF3 no existing code
will be broken.)
6. Signature types
Let rout be an entity declared of a routine type:
rout: ROUTINE [TARGET_TYPE, TUPLE [T1, T2, ..., Tn]]
Then the notation
signature rout
denotes the type TUPLE [T1, T2, ..., Tn].
(The syntax is similar to that of `like anchor', which
also denotes a type defined in relation to an entity.).
This is particularly useful if rout is a formal argument
of a routine. Assume a routine of the form
some_proc (rout: FUNCTION [T, TUPLE, REAL];
target: T;
args: signature rout)
then a call of the form
some_proc (my_routine, my_target, my_arguments)
is valid only if my_target is a valid target for my_routine,
and my_arguments is a valid set of arguments for my_routine.
This guarantees that within `some_proc' we can have a type-safe
call of the form
rout.call (target, args)
For example, the following call to some_proc will be valid,
in class FIGURE which we assume to have a feature
`distance (p: POINT): REAL', assuming also that FIGURE
conforms to T and that my_point is of type POINT:
some_proc ($distance, Current, my_point)
The following, however, are not valid:
some_proc ($print_distance, Current, my_point)
(if print_distance is a procedure)
some_proc ($distance, Current, my_rectangle)
some_proc ($distance, my_point, my_point)
etc.
7. Example: Iterators
In class LINEAR [G]:
do_while (action: PROCEDURE [G, TUPLE];
test: FUNCTION [G, TUPLE, BOOLEAN];
action_arguments: signature action;
test_arguments: signature test) is
require
action_exists: action /= Void
test-exists: test /= Void
do
from
start
until
after or else not test.eval (item, test_arguments)
loop
action.call (item, action_arguments)
forth
end
end
In a client class, also using a class SOME_CLASS:
some_proc (x: SOME_CLASS; n: INTEGER; b: BOOLEAN) is do ... end
some_test (x: SOME_CLASS; r: REAL): BOOLEAN is do ... end
my_list: LINKED_LIST [SOME_CLASS]
-- LINKED_LIST is a descendant of LINEAR
create my_list.make (...)
... Fill in the list ...
my_list.do_while ($some_proc, $some_test, <<3, False>>, <<3.141592>>)
================= END ROUTINE OBJECTS =================================