What is Expressiveness in a Computer Language [correction]

[David Hopwood]

David Hopwood wrote:
> Marshall wrote:
>>David Hopwood wrote:
>>>Marshall wrote:
>>>
>>>>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?
>>>
>>>In a statically typed language that has a "dynamic" type, all
>>>dynamically typed programs are straightforwardly expressible.

Correction: as the paper on gradual typing referenced below points
out in section 5, something like the "typerec" construct of
<http://citeseer.ist.psu.edu/harper95compiling.html> would be
needed, in order for a system with a "dynamic" type to be equivalent
in expressiveness to dynamic typing or gradual typing.

("typerec" can be used to implement "dynamic"; it is more general.)

>>So, how does this "dynamic" type work?
> 
> <http://citeseer.ist.psu.edu/abadi89dynamic.html>
> 
>>It can't simply be the "any" type, because that type has no/few
>>functions defined on it.
> 
> It isn't. From the abstract of the above paper:
> 
>   [...] even in statically typed languages, there is often the need to
>   deal with data whose type cannot be determined at compile time. To handle
>   such situations safely, we propose to add a type Dynamic whose values are
>   pairs of a value v and a type tag T where v has the type denoted by T.
>   Instances of Dynamic are built with an explicit tagging construct and
>   inspected with a type safe typecase construct.
> 
> "Gradual typing" as described in
> <http://www.cs.rice.edu/~jgs3847/pubs/pubs/2006/siek06:_gradual.pdf> is
> another alternative. The difference between gradual typing and a
> "dynamic" type

This should be: the difference between gradual typing and a system with
"typerec"...

> is one of convenience rather than expressiveness --
> gradual typing does not require explicit tagging and typecase constructs.

-- 
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>