What is Expressiveness in a Computer Language

[Neelakantan Krishnaswami]

In article <4fb97sF1if8l6U1 at individual.net>, Pascal Costanza wrote:
> Torben Ægidius Mogensen wrote:
> 
>> On a similar note, is a statically typed langauge more or less
>> expressive than a dynamically typed language?  Some would say less, as
>> you can write programs in a dynamically typed language that you can't
>> compile in a statically typed language (without a lot of encoding),
>> whereas the converse isn't true.
> 
> It's important to get the levels right here: A programming language
> with a rich static type system is more expressive at the type level,
> but less expressive at the base level (for some useful notion of
> expressiveness ;).

This doesn't seem obviously the case to me. If you have static
information about your program, the compiler can use this information
to automate a lot of grunt work away.

Haskell's system of typeclasses work this way. If you tell the
compiler how to print integers, and how to print lists, then when you
call a print function on a list of list of integers, then the compiler
will automatically figure out the right print function using your base
definitions. This yields an increase in Felleisen-expressiveness over
a dynamically typed language, because you would need to globally
restructure your program to achieve a similar effect.

More dramatic are the "polytypic" programming languages, which let you
automate even more by letting you write generic map, fold, and print
functions which work at every type.

> This doesn't seem to capture what I hear from Haskell programmers
> who say that it typically takes quite a while to convince the
> Haskell compiler to accept their programs. (They perceive this to be
> worthwhile because of some benefits wrt correctness they claim to
> get in return.)

This is true, if you are a novice learning the language, or if you are
an expert programming with good style.

If you encode your invariants in the types, then type errors will
signal broken invariants. But: learning how to use the type system to
encode significantly complex invariants (eg, that an abstract syntax
tree representing an HTML document actually satisfies all of the
constraints on valid HTML) takes experience to do well.

-- 
Neel Krishnaswami
neelk at cs.cmu.edu