Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!agate!stanford.edu!leland.Stanford.EDU!leland.Stanford.EDU!craig
From: craig@leland.Stanford.EDU (Craig Chambers)
Newsgroups: comp.object
Subject: Re: A Hard Problem for Static Type Systems
Message-ID: <1991Apr25.011607.25536@leland.Stanford.EDU>
Date: 25 Apr 91 01:16:07 GMT
References: <1991Apr20.010347.28984@leland.Stanford.EDU> <DUCHIER.91Apr23205041@albania.cs.yale.edu> <1991Apr24.032543.11704@leland.Stanford.EDU> <boehm.672515148@siria>
Sender: news@leland.Stanford.EDU (Mr News)
Reply-To: craig@self.stanford.edu
Organization: Stanford University
Lines: 59

In article <boehm.672515148@siria>, boehm@parc.xerox.com (Hans Boehm) writes:
|> It seems to me that this problem fundamentally has very little to do with object
|> oriented programming.  Expressing things in terms of a subtype hierarchy
|> confuses the issue and contributes nothing.  In Russell, the min function
|> has signature:
|> 
|> func [x,y: val T; T: type { < }] val T
|> 
|> It's a function of two values of type T, and of the type T itself.  T is
|> expected to include a < operation.  (I get to cheat slightly, in that
|> operations like < have the "right" type by default.)  The third (type)
|> parameter will be inferred for each call, and is not explicitly needed,
|> except in the declaration of min.

Part of the subtype interaction is that I'd like to instantiate the type T
above to "Number", and then allow subtypes of Number as the actuals passed
to x and y.  So I don't think that subtyping is completely spurious.

But I believe that subtyping might be able to be "grafted on" to an
existing non-object-oriented language that handles these sorts of
things.  For example, I think that you could take CLU's form of the
parameterized min function with where clauses:

min = proc[T:type](x:T, y:T) returns(T)
	where T has <:proctype(T, T) returns bool
    ...
end min

...and then allow subtyping of arguments.  Then I could write:

min[number](3,4.5)

I could also write:

min[collection[number]]({3,4.5}, {2,6.2,-5})

The where clause above is similar to the type pattern idea I talked
about earlier and to properties in the Haskell type class system.  But
I'd like to find a solution that didn't have both a notion of type
that has subtypes and a notion of type property that has instances;
having both seems non-orthogonal in some way.

It seems to me that languages based (at least in spirit) on some form
of polymorphic lambda calculus, e.g. Russell, ML, and Haskell, can do
the part of the problem that involves type variables (i.e. handling
Num * Num and Collection * Collection), but none of them really handle
the part dealing with subtyping of various kinds of numbers.  And most
existing statically-typed object-oriented languages handle the
subtyping of numbers fine but fall down when faced with a need for
some form of type variables.

-- Craig Chambers

P.S. People might find it interesting that A. K. Wright sent me e-mail
saying that he felt that the min problem and similar problems cannot
be solved to my satisfaction, and references his SIGPLAN PLDI'90 paper
with G. V. Cormack on "Type-Dependent Parameter Inference" as
containing a number of linear algebra examples that pose similar
problems for static type checkers.