Algebraic types and subclassing

[Nick Kallen]

(>There is a system type called OSType, which is a structure of exactly 4
>bytes, often interpreted as a string of 4 characters.
>The semantics almost match String. The exceptions are that the length is
>always 4, and the characters can have any numeric value of 0 to 255. In
>particular, it is convenient to use the String semantics to build, compare,
>etc.)

>I'm wondering if I am being dense and just not thinking in the "Clean" way.
>My other messages keep using this example. Does anyone have a suggestion on
>the natural way to solve this problem in Clean?

I'm by no means an expert programmer, but I'll offer some of the thoughts
running through my head:

    You could define OSType as a record and define an instance of toString
and fromString. This might very well be the best way to go, although I have
to admit, the excessive usage of toString with all the standard string
manipulation tools might be a pain.
    Second, (you essentially suggested this in an earlier posting..) is just
to make OSType an ADT. Clean has no language level support for ADTs that I'm
aware of, although existential types have some similarities.

Now, I'll list a more elegant solution that requires a significant extension
to the Clean language below. I don't know how practical it is to add this to
Clean, so take this suggestion with a grain of salt.
    I propose an extension to Clean's existing type class system, such that
constraints and invariants and the like can be defined in classes. Imagine,
if you will, a class String. Now, imagine:

instance String OSType
asserts
    ForAll o :: OSType
        len o = 4
    ForAll i in [1..4]
        o.[i] <- [0..255]

This bears an obvious similarity to the "traits" of Larch, and the
facilities provided by most specification languages.
    (Now, please digest all that because I'm about to digress.)
Unfortunately, this example is not great, for several reasons. Since classes
only define the types of functions, a Clean extended with the above feature
would still need to re-implement all the String functions. The possible
solutions to this problem are:
    1. to expand classes so that they can actually implement functions, not
just define the them, (this is similar to classes that are neither abstract
nor concrete in OO languages);
    2. allow instances or classes to inherit from other *instances*, (this
resembles the ability to inherit from concrete classes in OO languages);
    3. allow not just multiple parameter classes (coming in Clean 2.0?), but
parameterLESS classes. Yes, this essentially identical to an instance, but
you can *inherit* from them. This would eliminate the need for the instance
construct altogether. This requires (1) and eliminates the need for (2).

Now, as to the practicality of constraints and invariants and such in
Clean... I believe that many possible constraints are undecidable, and thus
this introduces a huge problem into the language. This is only a big deal,
because atleast in theory, a theorem proving system could prove at compile
time that all the constraints were upheld. Barring that, just aborting
during runtime would be a nice way to go too.


As if this message weren't enough, I'll propose a few more extensions to the
Clean language, not related to the above topic.

- Language level support for pre and post conditions.

- The ability to define functions of arity exceeding 1 in more convenient
ways:
    You can define:
        Add :: Int Int -> Int
        Add x = \y -> x + y
    But it would be nice to be able to define
        Add = (+)
    Sure, you can do this by defining Add :: (Int Int -> Int), but that's
not the same. This is convenient when one wants to define (>>=) = (`bind`),
or even:
        myParser :: Parser foo bar
        myParser x = ...
    Instead of
        myParser = p
            where p x = ...
    This may cause some problems, but it solves some too.

- The use of more classes in the standard library

- Language level support for ADTs. Data hiding is pretty tricky without
this. And you *can't* hide types without this.

- Make the language more orthogonal. Clean is already beautifully small, but
I think it could be a bit smaller. An example is the case construct. Perhaps
I'm missing something, but couldn't case be defined like:
    case` :: a [(a, b)] -> b | Eq a
    case` x l = snd (hd (filter (((==) x) o fst) l))

- OK, this is a pipe dream, but I'd like to see first class types (i.e.,
type can be passed as arguments to functions). This eliminates the need for
a special construct for dynamic types, special constructs for parametered
types (e.g., :: Parser s r :== [s] -> [([s],r)]), etc.

- Another pipe dream: reflection. I think reflection might be a useful
feature in some contexts.

- Support for all major platforms (Unix too!)

- Standard libraries with access to environment variables and the like.