What is Expressiveness in a Computer Language

[Chris Smith]

Marshall <marshall.spight at gmail.com> wrote:
> Yes, an important question (IMHO the *more* important question
> than the terminology) is what *programs* do we give up if we
> wish to use static typing? I have never been able to pin this
> one down at all.

You'd need to clarify what you mean by "use static typing".  Clearly, if 
you use forms of static typing that currently exist for Java, there's 
considerable limitation in expressiveness.  If you mean a hypothetical 
"perfect" type system, then there would be no interesting programs you 
couldn't write, but such a system may not be possible to implement, and 
certainly isn't feasible.

So it seems to me that we have this ideal point at which it is possible 
to write all correct or interesting programs, and impossible to write 
buggy programs.  Pure static type systems try to approach that point 
from the conservative side.  Pure dynamic systems (and I actually think 
that design-by-contract languages and such apply here just as well as 
type tagging) try to approach that point via runtime verification from 
the liberal side.  (No, this has nothing to do with George Bush or Noam 
Chomsky... :)  Either side finds that the closer they get, the more 
creative they need to be to avoid creating development work that's no 
longer commensurate with the gains involved (whether in safety or 
expressiveness).

I think I am now convinced that the answer to the question of whether 
there is a class of type errors in dynamically checked languages is the 
same as the answer for static type systems: no.  In both cases, it's 
just a question of what systems may be provided for the purposes of 
verifying (more or less conservatively or selectively) certain program 
properties.  Type tags or other features that "look like" types are only 
relevant in that they encapsulate common kinds of constraints on program 
correctness without requiring the programmer to express those 
constraints in any more general purpose language.

As for what languages to use right now, we are interestingly enough back 
where Xah Lee started this whole thread.  All languages (except a few of 
the more extreme statically typed languages) are Turing complete, so in 
order to compare expressiveness, we'd need some other measure that 
considers some factor or factors beyond which operations are 
expressible.

> There are also what I call "packaging" issues, such as
> being able to run partly-wrong programs on purpose so
> that one would have the opportunity to do runtime analysis
> without having to, say, implement parts of some interface
> that one isn't interested in testing yet. These could also
> be solved in a statically typed language. (Although
> historically it hasn't been done that way.)

I'll note veryh briefly that the built-in compiler for the Eclipse IDE 
has the very nice feature that when a particular method fails to 
compile, it can still produces a result but replace the implementation 
of that method with one that just throws an Error.  I've taken advantage 
of that on occasion, though it doesn't allow the same range of options 
as a language that will just go ahead and try the buggy operations.

> The real question is, are there some programs that we
> can't write *at all* in a statically typed language, because
> they'll *never* be typable? I think there might be, but I've
> never been able to find a solid example of one.

This seems to depend on the specific concept of equivalence of programs 
that you have in mind.

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