Xref: utzoo comp.object:3287 comp.lang.misc:7568 comp.lang.eiffel:1525
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!news.funet.fi!jyu.fi!sakkinen
From: sakkinen@jyu.fi (Markku Sakkinen)
Newsgroups: comp.object,comp.lang.misc,comp.lang.eiffel
Subject: Re: A Hard Problem for Static Type Systems
Message-ID: <1991Apr22.150348.10415@jyu.fi>
Date: 22 Apr 91 15:03:48 GMT
References: <1991Apr20.010347.28984@leland.Stanford.EDU>
Reply-To: sakkinen@jytko.jyu.fi (Markku Sakkinen)
Organization: University of Jyvaskyla, Finland
Lines: 67

In article <1991Apr20.010347.28984@leland.Stanford.EDU> craig@self.stanford.edu writes:
>
>Here's a simple example that cannot be described by a static type
>system in most statically-typed object-oriented languages.  I'm using
>it to help me make sure that the static type system in my new OO
>language is sufficiently powerful, but you could use it as another
>example of a simple, useful program that is handled simply in a
                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
>dynamically-typed system that requires a lot of sophistication in a 
 ^^^^^^^^^^^^^^^^^^^^^^^^
>statically-typed system.
> ...
>Assume that we have two kinds of numbers in our language, integers and
>floats, and that we've defined implementations of "<" for all four
>combinations of integer and float arguments.  We define number as the
>common supertype of both integers and floats; since we've defined all
>possible combinations, "<" is defined over pairs of numbers.
>
>We also have a collection hierarchy.  The "<" message is defined for
>all collections of things that themselves understand "<" to do
>lexicographic ordering of two collections.
>
>Note that we do NOT have a "<" message that can take a number as one
>argument and a collection as the other.
> ...

It appears to me that the given starting point for this problem
(although somewhat fuzzily defined) itself requires additional
work in a purely dynamically-typed system,
but is simple in a statically-typed system with the appropriate
features, i.e. first-class set types.  (I don't know about SETL
except that it's built mainly upon set handling; is it
statically typed?)

It seems that you require homogeneous sets, i.e. sets of numbers,
sets of sets of numbers, etc.  In a statically-typed language that
really supports sets of any order, you can get that homogeneity
automatically with the correct type definition.  If you then try
to add a NUMBER to a SET OF SET OF NUMBER you get a compile-time error.
In a dynamically-typed language, you have to program yourself
the run-time tests to check:

(1) when you try to add a new element to a non-empty set,
    that it is of the same "degree" as the previous elements

(2) when applying the '<' operator to two objects,
    that they are of the same "degree"

On the other hand, I don't know if any current statically-typed
language allows a convenient single recursive definition of '<'
for all such set types (some functional language perhaps?).
In a dynamically-typed object-oriented language, it would obviously
suffice to define a class StratifiedOrderedCollection,
which would have the "degree" as one instance variable.

P.S. The word 'degree' is in quotes above because I am uncertain
about the established term.  Is it 'order' (what an overloaded
word: no wonder that the misnomer 'sorting' is so commonly used
for 'ordering')?

Markku Sakkinen
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
          SAKKINEN@FINJYU.bitnet (alternative network address)