Xref: utzoo comp.object:3351 comp.lang.misc:7608 comp.lang.eiffel:1537
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!mcsun!ukc!dcl-cs!cam-cl!news
From: pwd@cl.cam.ac.uk (Peter Dickman)
Newsgroups: comp.object,comp.lang.misc,comp.lang.eiffel
Subject: Re: A Hard Problem for Static Type Systems
Summary: CLU version + question about the question
Message-ID: <1991Apr24.144714.17740@cl.cam.ac.uk>
Date: 24 Apr 91 14:47:14 GMT
References: <1991Apr20.010347.28984@leland.Stanford.EDU> <1991Apr23.152110.6500@eua.ericsson.se>
Sender: news@cl.cam.ac.uk (The news facility)
Reply-To: pwd@cl.cam.ac.uk (Peter Dickman)
Organization: U of Cambridge Comp Lab, UK
Lines: 96

In article <1991Apr23.152110.6500@eua.ericsson.se> 
euaabt@eua.ericsson.se (Anders.Bjornerstedt) writes:
>I suspect that you could express this, or something very close to it, in 
>the language CLU.

You mean like this? (Please excuse the style... :-)
Please read carefully - including the notes below, before telling me that I 
haven't solved the problem.


min = PROC [T : TYPE] (x, y : T) RETURNS (T) 
      WHERE T HAS lt : PROCTYPE (T,T) RETURNS (bool)
  
  IF (x < y) 
  THEN 
    RETURN (x) 
  ELSE 
    RETURN (y) 
  ENDIF
END min

Note that both arguments must be the same type; but int & real aren't the same 
so you'd have to explicitly convert the int into a real first (*). Also, < is 
just syntactic sugar for an invocation of the lt function, so (x < y) is read 
by the compiler as type_of(x)$lt(x,y), in other words I could have put 
T$lt(x,y) instead of x < y. CLU doesn't distinguish between built-in & 
user-defined types - it treats them all the same. If the instantiating 
type for T doesn't support a lt operation there'll be a compile-time error.

Calls would then be things like:

   a : int  := min[int](5,6)
   b : list := min[list](c,d)   % where list is a user-defined cluster 
                                % (type) supporting an lt operation and 
				% c & d are of type list
			 
   e : real := min[real](real$i2r(6), 2.0)    % convert an int to a real first

(the type declaration would, obviously, be omitted if the variables were 
previously declared).

Many other languages can be used in EXACTLY the same way. If it has constrained
genericity you can do this. All of the CLU family (CLU, CCLU, Argus, Troy etc)
for example. Sadly Eiffel has inheritance & unconstrained genericity but the 
constrained genericity was left out (I don't like Bertrand Meyer's 
justification for this I'm afraid - but accept that he had his reasons). 
Doesn't Ada have some form of generics too? 

Note that CLU is strongly typed. There is the possibility of over-riding the
static typing by use of the ANY type, however the only way you can apply an
operation to an ANY is by FORCEing it to a type (otherwise all you can do
is assign the ANY value to a variable of type ANY). And the only type that an
object can be forced to is the one it started as (otherwise there's a run-time
exception). Note also that because of the signal mechanism (and the fact that 
the CCLU compiler (& maybe others) warns you if you fail to catch all possible 
signals) you have no-one to blame but yourself if there is a run-time type 
failure which can't be handled by your code. The FORCE operation is defined as:

    FORCE = PROC [T: TYPE] (x : ANY) RETURNS (T) SIGNALS (wrong_type)
    
This solves the resource-manager problem that's being discussed in the 
"Run-time Type Errors in Smalltalk" thread.

----------------

(*) By the way - int and real AREN'T the same. I certainly don't want a 
compiler 'helping' me when I use 2 instead of 2.0 (or, worse still, 
'number_readings : int' instead of 'latest_reading : real'). 
It helps to keep the lid on bugs to be explicit about what you are doing - and 
helps the compiler to optimise things too.

Because of this lack of sub-typing the problem as originally posed cannot be
answered in CLU. Finding the min of a real and an int would be faulted.
What's the problem with an explicit coercion though? Is it merely a matter of
taste? Or down to the "minimal thought vs maximal confidence" religious war?

Those who believe this problem should be solvable as originally posed, please
read & reflect on the following:

Assume that A is of type M, B is of type N and both M & N are subtypes of
type P, which defines a < operation; it doesn't necessarily make sense to
assume automatically that A & B can be compared with <, since either M or
N may have redefined <. In particular, if <P is the P < operator and <M
is a reimplemented < operator for M. We could have A,C of type M and 
B of type N with A <P B, B <P C and C <M A; but, one hopes, A <P C in 
order to maintain transitivity of <P. So how would this hoped-for 
super-min function cope? Any one invocation might be reasonable but
a mutually inconsistent set of invocations could easily result.

The only way I can see to handle this is to say that the reimplemented <M 
must be consistent with the original <P function - I don't believe anyone 
knows how to ensure this sort of thing, let alone has actually built 
it into a real language. Besides, in this case such a constraint renders
<M redundant (unless it has side-effects :-).

-- Peter