What is Expressiveness in a Computer Language

[Andreas Rossberg]

Here's what the Scheme Standard has to say:

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-4.html
1.1 Semantics
...
Scheme has latent as opposed to manifest types. Types are assoc-
iated with values (also called objects) rather than with variables.
(Some authors refer to languages with latent types as weakly typed
or dynamically typed languages.) Other languages with latent types
are APL, Snobol, and other dialects of Lisp. Languages with manifest
types (sometimes referred to as strongly typed or statically typed
languages) include Algol 60, Pascal, and C.

Maybe this is the original source of the myth that static typing is all
about assigning types to variables...

With all my respect to the Scheme people, I'm afraid this paragraph is
pretty off, no matter where you stand. Besides the issue just mentioned
it equates "manifest" with static types. I understand "manifest" to mean
"explicit in code", which of course is nonsense - static typing does not
require explicit types. Also, I never heard "weakly typed" used in the
way they suggest - in my book, C is a weakly typed language (= typed,
but grossly unsound).

To me, the word "latent" means that when handed a value of unknown type
at runtime, I can look at it or perform TYPE-OF on it or TYPECASE or
something and thereby discover its actual type at the moment[1], whereas
"manifest" means that types[2] are lexically apparent in the code.

Mh, I'd say typecase is actually a form of reflection, which is yet a
different issue. Moreover, there are statically typed languages with
typecase (e.g. Modula-3, and several more modern ones) or related
constructs (consider instanceof).

- Andreas

 

[Pascal Costanza]

I have trouble understanding your use of the wording "Model of a
program".
If it is a system that behaves according to the rules of your program
then
statements about your program should consider *all* possible models.
If it is a formal system that makes statements about properties of your
program
than the static type system is a simplified model that is suitable for
automatic
analysis and your runtime model is in most cases nonexistent.
Can you give a definition of a "model of a program"? Can you explain
why
Lisp doesn't have two (SBCL does do a lot of typechecking and gives
type errors)?

I wasn't talking about models that the language implementation may or
may not have, but the models that I as a programmer must have in order
to convince the compiler to let me program run.

Consider a simple expression like 'a + b': In a dynamically typed
language, all I need to have in mind is that the program will attempt to
add two numbers. In a statically typed language, I additionally need to
know that there must a guarantee that a and b will always hold numbers.

In a trivial example like this, this doesn't hurt a lot, but can be
problematic as soon as the program size grows.

It is also valuable when you don't know your domain very well and you
want to rely on feedback by your compiler that you haven't made any
mistakes in encoding your limited knowledge

I have more or less used exactly the same words in the paragraph that
followed the one you cited from my previous posting, and I have already
given a reply there.

In the sense that you can start writing code without the compiler
pointing out
all but the most glaring holes in your program, I agree.

I don't know what language environments you are used to, but the Common
Lisp compilers I use always point out the most glaring holes in my
programs. But maybe I just have trouble understanding your use of the
wording "most glaring holes". Can you give a definition of "most glaring
holes"?

Most of your
arguments
aren't very convincing and the thruth is that I have seem lisp
programmers using
the debugger to find out that you can't add a number and a hastable.
The static view
was not there and the dynamic view must have been too complicated so
they had
nothing to think about.

We have all seen less-than-average programmers who would fail in all
kinds of languages. What they do is typically not very illuminating.

My goal is not to convince anyone, my goal is to illustrate for those
who are interested in getting a possibly different perspective.


Pascal

 

[Andreas Rossberg]

Consider a simple expression like 'a + b': In a dynamically typed
language, all I need to have in mind is that the program will attempt to
add two numbers. In a statically typed language, I additionally need to
know that there must a guarantee that a and b will always hold numbers.

I'm confused. Are you telling that you just write a+b in your programs
without trying to ensure that a and b are in fact numbers??

- Andreas

 

[Pascal Costanza]

I'm confused. Are you telling that you just write a+b in your programs
without trying to ensure that a and b are in fact numbers??

Basically, yes.

Note that this is a simplistic example. Consider, instead, sending a
message to an object, or calling a generic function, without ensuring
that there will be applicable methods for all possible cases. When I get
a "message not understood" exception, I can then decide whether that
kind of object shouldn't be a receiver in the first place, or else
whether I should define an appropriate method. I don't want to be forced
to decide this upfront, because either I don't want to be bothered, or
maybe I simply can't because I don't understand the domain well enough
yet, or maybe I want to keep a hook to be able to update the program
appropriately while it is running.


Pascal

 

[Pascal Bourguignon]

I'm confused. Are you telling that you just write a+b in your programs
without trying to ensure that a and b are in fact numbers??

Of course.

(shadow '(+ *))
(defun + (&rest args) `(+ ,@args))
(defun * (&rest args) `(* ,@args))

(let ((var 'x) (init 'b) (slop 'a))
(+ init (* slop var)))
--> (+ B (* A X))

 

[Pascal Bourguignon]

Basically, yes.

Note that this is a simplistic example. Consider, instead, sending a
message to an object, or calling a generic function, without ensuring
that there will be applicable methods for all possible cases. When I
get a "message not understood" exception, I can then decide whether
that kind of object shouldn't be a receiver in the first place, or
else whether I should define an appropriate method. I don't want to be
forced to decide this upfront, because either I don't want to be
bothered, or maybe I simply can't because I don't understand the
domain well enough yet, or maybe I want to keep a hook to be able to
update the program appropriately while it is running.

Moreover, a good proportion of the program and a good number of
algorithms don't even need to know the type of the objects they
manipulate.

For example, sort doesn't need to know what type the objects it sorts
are. It only needs to be given a function that is able to compare the
objects.

Only a few "primitive" functions need specific types.

So basically, you've got a big black box of applicaition code in the
middle that doesn't care what type of value they get, and you've got a
few input values of a specific type, a few processing functions
needing a specific type and returning a specific type, and a few
output values that are expected to be of a specific type. At anytime,
you may change the type of the input values, and ensure that the
needed processing functions will be able to handle this new input
type, and the output gets mapped to the expected type.


Why should adding a few functions or methods, and providing input
values of a new type be rejected from a statically checked point of
view by a compiled program that would be mostly bit-for-bit the same
with or without this new type?

Of course, in the process of so modifying the program, we may get some
dynamically detected type errors that we would correct as Pascal
indicated.

 

[Matthias Blume]

Moreover, a good proportion of the program and a good number of
algorithms don't even need to know the type of the objects they
manipulate.

For example, sort doesn't need to know what type the objects it sorts
are. It only needs to be given a function that is able to compare the
objects.

Of course, some statically typed languages handle this sort of thing
routinely.

Only a few "primitive" functions need specific types.

Your sort function from above also has a specific type -- a type which
represents the fact that the objects to be sorted must be acceptable
input to the comparison function.

So basically, you've got a big black box of applicaition code in the
middle that doesn't care what type of value they get, and you've got a
few input values of a specific type, a few processing functions
needing a specific type and returning a specific type, and a few
output values that are expected to be of a specific type. At anytime,
you may change the type of the input values, and ensure that the
needed processing functions will be able to handle this new input
type, and the output gets mapped to the expected type.

....or you type-check your "black box" and make sure that no matter how
you will ever change the type of the inputs (in accordance with the
interface type of the box) you get a valid program.

 

[Matthias Blume]

What about this: You get a type error when the program attempts to
invoke an operation on values that are not appropriate for this
operation.

Examples: adding numbers to strings; determining the string-length of
a number; applying a function on the wrong number of parameters;
applying a non-function; accessing an array with out-of-bound indexes;
etc.

Yes, the phrase "runtime type error" is actually a misnomer. What one
usually means by that is a situation where the operational semantics
is "stuck", i.e., where the program, while not yet arrived at what's
considered a "result", cannot make any progress because the current
configuration does not match any of the rules of the dynamic
semantics.

The reason why we call this a "type error" is that such situations are
precisely the ones we want to statically rule out using sound static
type systems. So it is a "type error" in the sense that the static
semantics was not strong enough to rule it out.

Sending a message to an object that does not understand that message
is a type error. The "message not understood" machinery can be seen
either as a way to escape from this type error in case it occurs and
allow the program to still do something useful, or to actually remove
(some) potential type errors.

I disagree with this. If the program keeps running in a defined way,
then it is not what I would call a type error. It definitely is not
an error in the sense I described above.

 

[Chris Smith]

What about this: You get a type error when the program attempts to
invoke an operation on values that are not appropriate for this operation.

Examples: adding numbers to strings; determining the string-length of a
number; applying a function on the wrong number of parameters; applying
a non-function; accessing an array with out-of-bound indexes; etc.

Hmm. I'm afraid I'm going to be picky here. I think you need to
clarify what is meant by "appropriate". If you mean "the operation will
not complete successfully" as I suspect you do, then we're closer... but
this little snippet of Java (HORRIBLE, DO NOT USE!) confuses the matter
for me:

int i = 0;

try
{
while (true) process(myArray[i++]);
}
catch (IndexOutOfBoundsException e) { }

That's an array index from out of bounds that not only fails to be a
type error, but also fails to be an error at all! (Don't get confused
by Java's having a static type system for other purposes... we are
looking at array indexing here, which Java checks dynamically. I would
have used a dynamically typed language, if I could have written this as
quickly.)

I'm also unsure how your definition above would apply to languages that
do normal order evaluation, in which (at least in my limited brain) it's
nearly impossible to break down a program into sequences of operations
on actual values. I suppose, though, that they do eventually happen
with primitives at the leaves of the derivation tree, so the definition
would still apply.

 

[Marshall]

Can you be more explicit about what "latent types" means?
I'm sorry to say it's not at all natural or intuitive to me.
Are you referring to the types in the programmers head,
or the ones at runtime, or what?

Here's what the Scheme Standard has to say:

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-4.html
1.1 Semantics
...
Scheme has latent as opposed to manifest types. Types are assoc-
iated with values (also called objects) rather than with variables.
(Some authors refer to languages with latent types as weakly typed
or dynamically typed languages.) Other languages with latent types
are APL, Snobol, and other dialects of Lisp. Languages with manifest
types (sometimes referred to as strongly typed or statically typed
languages) include Algol 60, Pascal, and C.

To me, the word "latent" means that when handed a value of unknown type
at runtime, I can look at it or perform TYPE-OF on it or TYPECASE or
something and thereby discover its actual type at the moment[1], whereas
"manifest" means that types[2] are lexically apparent in the code.

Hmmm. If I read the R5RS text correctly, it is simply doing the
either/or thing that often happens with "static/dynamic" only
using different terms. I don't see any difference between
"latent" and "dynamic." Also, this phrase "types associated with
values instead of variables" that I'm starting to see a lot is
beginning to freak me out: the implication is that other languages
have types associated with variables and not values, which
doesn't describe anything I can think of.

In your followup paragraph, you've contrasted runtime type
introspection, vs. explicit type declarations, which seem
orthorgonal to me. (Not that you said they weren't.)


Marshall

 

[Marshall]

A statically type language requires you to think about two models of
your program at the same time: the static type model and the dynamic
behavioral model. A static type system ensures that these two
_different_ (that's important!) perspectives are always in sync. This is
especially valuable in settings where you know your domain well and want
to rely on feedback by your compiler that you haven't made any mistakes
in encoding your knowledge. (A static type system based on type
inferencing doesn't essentially change the requirement to think in two
models at the same time.)

A dynamically typed language is especially well suited when you don't
(yet) have a good idea about your domain and you want to use programming
especially to explore that domain. Some static typing advocates claim
that static typing is still suitable for exploring domains because of
the compiler's feedback about the preliminary encoding of your
incomplete knowledge, but the disadvantages are a) that you still have
to think about two models at the same time when you don't even have
_one_ model ready and b) that you cannot just run your incomplete
program to see what it does as part of your exploration.

A statically typed language with a dynamic type treats dynamic typing as
the exception, not as the general approach, so this doesn't help a lot
in the second setting (or so it seems to me).

A language like Common Lisp treats static typing as the exception, so
you can write a program without static types / type checks, but later on
add type declarations as soon as you get a better understanding of your
domain. Common Lisp implementations like CMUCL or SBCL even include
static type inference to aid you here, which gives you warnings but
still allows you to run a program even in the presence of static type
errors. I guess the feedback you get from such a system is probably not
"strong" enough to be appreciated by static typing advocates in the
first setting (where you have a good understanding of your domain).

I am sceptical of the idea that when programming in a dynamically
typed language one doesn't have to think about both models as well.
I don't have a good model of the mental process of working
in a dynamically typed language, but how could that be the case?
(I'm not asking rhetorically.) Do you then run your program over
and over, mechanically correcting the code each time you discover
a type error? In other words, if you're not thinking of the type model,
are you using the runtime behavior of the program as an assistant,
the way I use the static analysis of the program as an assistant?

I don't accept the idea about pairing the appropriateness of each
system according to whether one is doing exploratory programming.
I do exploratory programming all the time, and I use the static type
system as an aide in doing so. Rather I think this is just another
manifestation of the differences in the mental processes between
static typed programmers and dynamic type programmers, which
we are beginning to glimpse but which is still mostly unknown.

Oh, and I also want to say that of all the cross-posted mega threads
on static vs. dynamic typing, this is the best one ever. Most info;
least flames. Yay us!


Marshall

 

[Chris Uppal]

Andreas Rossberg wrote:

[me:]

It's worth noting, too, that (in some sense) the type of an object can
change over time[*].

No. Since a type expresses invariants, this is precisely what may *not*
happen. If certain properties of an object may change then the type of
the object has to reflect that possibility. Otherwise you cannot
legitimately call it a type.

Well, it seems to me that you are /assuming/ a notion of what kinds of logic
can be called type (theories), and I don't share your assumptions. No offence
intended.

Actually I would go a little further than that. Granted that whatever logic
one wants to apply in order to prove <whatever> about a program execution is
abstract -- and so timeless -- that does not (to my mind) imply that it must be
/static/. However, even if we grant that additional restriction, that doesn't
imply that the analysis itself must not be cognisant of time. I see no reason,
even in practise, why a static analysis should not be able to see that the set
of acceptable operations (for some definition of acceptable) for some
object/value/variable can be different at different times in the execution. If
the analysis is rich enough to check that the temporal constraints are [not]
satisfied, then I don't see why you should want to use another word than "type"
to describe the results of its analysis.

-- chris

 

[Chris Uppal]

It would be interesting to see what a language designed specifically to
support user-defined, pluggable, and perhaps composable, type systems
would look like.

Since writing that I've come across some thoughts by Gilad Bracha (a Name known
to Java and Smalltalk enthusiasts alike) here:

http://blogs.sun.com/roller/page/gbracha?entry=a_few_ideas_on_type

and a long, and occasionally interesting, related thread on LtU:

http://lambda-the-ultimate.org/node/1311

Not much discussion of concrete language design, though.

-- chris

 

[Marshall]

If you identify an abstract type with the set of underlying values then
it is equivalent to the underlying representation type, i.e. there is no
abstraction.

I don't follow. Are you saying that a set cannot be described
intentionally? How is "the set of all objects that implement the
Foo interface" not sufficiently abstract? Is it possible you are
mixing in implementation concerns?

This is 1973, actually, but most relevant:

James Morris
Types Are Not Sets.
Proc. 1st ACM Symposium on Principles of Programming Languages, 1973

Okay. Since this paper is in the ACM walled garden, I'll have to
wait until next week to get a look at it. But thanks for the reference.

I'm no expert here, but Category Theory is a preferred choice in many
areas of PLT.

Fair enough.


Marshall

 

[Chris Uppal]

Some people here seem to be
saying that there is a universal concept of "type error" in dynamic
typing, but I've still yet to see a good precise definition (nor a good
precise definition of dynamic typing at all).

How about this, at least as a strawman:

I think we're agreed (you and I anyway, if not everyone in this thread) that we
don't want to talk of "the" type system for a given language. We want to allow
a variety of verification logics. So a static type system is a logic which can
be implemented based purely on the program text without making assumptions
about
runtime events (or making maximally pessimistic assumptions -- which comes to
the same thing really). I suggest that a "dynamic type system" is a
verification logic which (in principle) has available as input not only the
program text, but also the entire history of the program execution up to the
moment when the to-be-checked operation is invoked.

I don't mean to imply that an operation /must/ not be checked until it is
invoked (although a particular logic/implementation might not do so). For
instance an out-of-bound array access might be rejected:
When the attempt was made to read that slot.
When, in the surrounding code, it first became
unavoidable that the about read /would/ be reached.
When the array was first passed to a function which
/might/ read that slot.
...and so on...

Note that not all errors that I would want to call type errors are necessarily
caught by the runtime -- it might go happily ahead never realising that it had
just allowed one of the constraints of one of the logics I use to reason about
the program. What's known as an undetected bug -- but just because the runtime
doesn't see it, doesn't mean that I wouldn't say I'd made a type error. (The
same applies to any specific static type system too, of course.)

But the checks the runtime does perform (whatever they are, and whenever they
happen), do between them constitute /a/ logic of correctness. In many highly
dynamic languages that logic is very close to being maximally optimistic, but
it doesn't have to be (e.g. the runtime type checking in the JMV is pretty
pessimistic in many cases).

Anyway, that's more or less what I mean when I talk of dynamically typed
language and their dynamic type systems.

I suspect you'll see the Smalltalk version of the objections raised in
response to my post earlier. In other words, whatever terminology you
think is consistent, you'll probably have a tough time convincing
Smalltalkers to stop saying "type" if they did before. If you exclude
"message not understood" as a type error, then I think you're excluding
type errors from Smalltalk entirely, which contradicts the psychological
understanding again.

Taking Smalltalk /specifically/, there is a definite sense in which it is
typeless -- or trivially typed -- in that in that language there are no[*]
operations which are forbidden[**], and none which might not be invoked
deliberately (e.g. I have code which deliberately reads off the end of a
container object -- just to make sure I raise the "right" error for that
container, rather than raising my own error). But, on the other hand, I do
still want to talk of type, and type system, and type errors even when I
program Smalltalk, and when I do I'm thinking about "type" in something like
the above sense.

-- chris

[*] I can't think of any offhand -- there may be a few.

[**] Although there are operations which are not possible, reading another
object's instvars directly for instance, which I suppose could be taken to
induce a non-trivial (and static) type logic.

 

[Marshall]

Consider a simple expression like 'a + b': In a dynamically typed
language, all I need to have in mind is that the program will attempt to
add two numbers. In a statically typed language, I additionally need to
know that there must a guarantee that a and b will always hold numbers.

I still don't really see the difference.

I would not expect that the dynamic programmer will be
thinking that this code will have two numbers most of the
time but sometimes not, and fail. I would expect that in both
static and dynamic, the thought is that that code is adding
two numbers, with the difference being the static context
gives one a proof that this is so. In this simple example,
the static case is better, but this is not free, and the cost
of the static case is evident elsewhere, but maybe not
illuminated by this example.

This thread's exploration of the mindset of the two kinds
of programmers is difficult. It is actually quite difficult,
(possibly impossible) to reconstruct mental states
though introspection. Nonetheless I don't see any
other way to proceed. Pair programming?

My goal is not to convince anyone, my goal is to illustrate for those
who are interested in getting a possibly different perspective.

Yes, and thank you for doing so.


Marshall

 

[Andreas Rossberg]

For example, sort doesn't need to know what type the objects it sorts
are. It only needs to be given a function that is able to compare the
objects.

Sure. That's why any decent type system supports polymorphism of this
sort. (And some of them can even infer which comparison function to pass
for individual calls, so that the programmer does not have to bother.)

- Andreas

 

[Chris Uppal]

What we need is an FAQ entry for how to talk about types with people
who are technically adept, but non-specialists. Or alternatively, an
FAQ of how to explain the term `dynamic typing' to a type theorist.

You could point people at
"a regular series on object-oriented type theory, aimed
specifically at non-theoreticians."
which was published on/in JoT from:
http://www.jot.fm/issues/issue_2002_05/column5
to
http://www.jot.fm/issues/issue_2005_09/column1

Only 20 episodes ! (But #3 seems to be missing.)

Actually the first one has (in section four) a quick and painless overview of
several kinds of type theory. I haven't read the rest (yet, and maybe never
;-)

-- chris

 

[Andreas Rossberg]

It's worth noting, too, that (in some sense) the type of an object can
change over time[*].

No. Since a type expresses invariants, this is precisely what may *not*
happen. If certain properties of an object may change then the type of
the object has to reflect that possibility. Otherwise you cannot
legitimately call it a type.

Well, it seems to me that you are /assuming/ a notion of what kinds of logic
can be called type (theories), and I don't share your assumptions. No offence
intended.

OK, but can you point me to any literature on type theory that makes a
different assumption?

I see no reason,
even in practise, why a static analysis should not be able to see that the set
of acceptable operations (for some definition of acceptable) for some
object/value/variable can be different at different times in the execution.

Neither do I. But what is wrong with a mutable reference-to-union type,
as I suggested? It expresses this perfectly well.

- Andreas

 

[Rob Thorpe]

Rob Thorpe schreef:

That is your opinion. In the context of this discussion I don't see any
problem to put C's union under "dynamic types".

Lets put it like this:-
1. In C++ and Java it is possible to make a variable that can A)Take on
many different types and B)Where the programmer can test what the type
is.
2. In C it is possible to make a variable that can do 1A but not 1B.

This is a statement of fact, not opinion.

I call languages that do #1 dynamically typed, in line with common
usage.

When such a test is needed for the program with the union, it has it.

What do you mean?
There is no way to test the type of the value inside a union in C.