What is Expressiveness in a Computer Language

[rossberg at ps.uni-sb.de]

Rob Thorpe write:
> >
> > Take one of these languages. You have a variable that is supposed to
> > store functions from int to int. Can you test that a given function
> > meets this requirement?
>
> The answer is no for python and perl AFAIK.  Also no for lisp _aux
> naturelle_ (you can do it by modifying lisp though of-course, I believe
> you can make it entirely statically typed if you want).
>
> But the analogous criticism could be made of statically typed
> languages.
> Can I make a type in C that can only have values between 1 and 10?
> How about a variable that can only hold odd numbers, or, to make it
> more difficult, say fibonacci numbers?

Fair point. However, there are in fact static type systems powerful
enough to express all of this and more (whether they are convenient
enough in practice is a different matter). On the other hand, AFAICS,
it is principally impossible to express the above property on functions
with tags or any other purely dynamic mechanism.

> The cases can be far from trivial.  In lisp a type specifier can mean
> something like "argument must be a 10x10 matrix with top corner element
> larger than 35"  You can also, for example, easily make predicates that
> tell if a value is odd, or a fibonacci number.

Now, these are yet another beast. They are not tags, they are
user-defined predicates. I would not call them types either, but that's
an equally pointless battle. :-)

- Andreas