What is Expressiveness in a Computer Language

[Chris Smith]

Chris F Clark <cfc at shell01.TheWorld.com> wrote:
> Ok, we'll get there.  First, we need to step back in time, to when there
> was roughly algol, cobol, fortran, and lisp.  Back then, at least as I
> understood things, there were only a few types that generally people
> understood integer, real, and (perhaps) pointer.

In order to continue my tradition of trying to be as precise as 
possible, let me point out that of course there were more "candidate 
types", as it were, and that people understood them just fine.  They 
just didn't have a type system in place to make them into real types, so 
they didn't think to call them types.

> The important thing is the dynamicism of lisp allowed one to write
> polymorphic programs, before most of us knew the term.

Sure.  In exchange for giving up the proofs of the type checker, you 
could write all kinds of programs.  To this day, we continue to write 
programs in languages with dynamic checking features because we don't 
have powerful enough type systems to express the corresponding type 
system.

> Thus, as we traverse a list, the first element might be an integer,
> the second a floating point value, the third a sub-list, the fourth
> and fifth, two more integers, and so on.  If you look statically at
> the head of the list, we have a very wide union of types going by.
> However, perhaps there is a mapping going on that can be discerned.
> For example, perhaps the list has 3 distinct types of elements
> (integers, floating points, and sub-lists) and it circles through the
> types in the order, first having one of each type, then two of each
> type, then four of each type, then eight, and so on.  The world is now
> patterned.  
> 
> However, I don't know how to write a static type annotation that
> describes exactly that type.

I believe that, in fact, it would be trivial to imagine a type system 
which is capable of expressing that type.  Okay, not trivial, since it 
appears to be necessary to conceive of an infinite family of integer 
types with only one value each, along with range types, and 
relationships between them; but it's probably not completely beyond the 
ability of a very bright 12-year-old who has someone to describe the 
problem thoroughly and help her with the notation.

The more interesting problem is whether this type system could be made: 
(a) unobstrusive enough, probably via type inference or something along 
those lines, that it would be usable in practice; and (b) general enough 
that you could define a basic type operator that applies to a wide range 
of problems rather than revising your type operator the first time you 
need a complete 3-tree of similar form.

> That may just be my lack of experience
> in writing annotations.

You would, of course, need a suitable type system first.  For example, 
it appears to me that there is simply no possible way of expressing what 
you've described in Java, even with the new generics features.  Perhaps 
it's possible in ML or Haskell (I don't know).  My point is that if you 
were allowed to design a type system to meet your needs, I bet you could 
do it.

> And, this brings us to the point, if the data that my program
> encounters doesn't match the model I have formulated, then something
> is of the wrong "type".  Equally importantly, the dynamic tags, have
> helped me discover that type error.

Sure.  The important question, then, is whether there exists any program 
bug that can't be formulated as a type error.  And if so, what good does 
it do us to talk about type errors when we already have the perfectly 
good word "bug" to describe the same concept?

> Now, the example may have seemed arbitrary to you, and it was in some
> sense arbitrary.

Arbitrary is good.  One of the pesky things that keeps getting in the 
way here is the intuition attached to the word "type" that makes 
everyone think "string or integer".

-- 
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation