What is Expressiveness in a Computer Language

[Marshall]

Joe Marshall wrote:
> Marshall 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.
>
> It would depend on the type system, naturally.

Naturally!


> It isn't clear to me which programs we would have to give up, either.
> I don't have much experience in sophisticated typed languages.  It is
> rather easy to find programs that baffle an unsophisticated typed
> language (C, C++, Java, etc.).

C and Java, certainly, but I'm wary these days about making
any statement about limitations on C++'s type system, for it is
subtle and quick to anger.


> Looking back in comp.lang.lisp, I see these examples:
>
> (defun noisy-apply (f arglist)
>   (format t "I am now about to apply ~s to ~s" f arglist)
>   (apply f arglist))
>
> (defun blackhole (argument)
>   (declare (ignore argument))
>   #'blackhole)
>
> But wait a sec.  It seems that these were examples I invented in
> response to the same question from you!

Ah, how well I remember that thread, and how little I got from it.

My memories of that thread are
1) the troll who claimed that Java was unable to read two numbers from
standard input and add them together.
2) The fact that all the smart people agreed the blackhole
function indicated something profound.
3) The fact that I didn't understand the black hole function.

The noisy-apply function I think I understand; it's generic on the
entire arglist. In fact, if I read it correctly, it's even generic
on the *arity* of the function, which is actually pretty impressive.
True? This is an issue I've been wrestling with in my own type
system investigations: how to address genericity across arity.

Does noisy-apply get invoked the same way as other functions?
That would be cool.

As to the black hole function, could you explain it a bit? I apologize
for my lisp-ignorance. I am sure there is a world of significance
in the # ' on the third line, but I have no idea what it is.


> > > If you allow Turing Complete type systems, then I would say no--every
> > > bug can be reforumlated as a type error.  If you require your type
> > > system to be less powerful, then some bugs must escape it.
> >
> > I don't think so. Even with a Turing complete type system, a program's
> > runtime behavior is still something different from its static behavior.
> > (This is the other side of the "types are not tags" issue--not only
> > is it the case that there are things static types can do that tags
> > can't, it is also the case that there are things tags can do that
> > static types can't.)
>
> I agree.  The point of static checking is to *not* run the program.  If
> the type system gets too complicated, it may be a de-facto interpreter.

Aha! A lightbulb just want off.

Consider that a program is a function parameterized on its input.
Static
analysis is exactly the field of what we can say about a program
without
know the values of its parameters.


Marshall