Python from Wise Guy's Viewpoint

[Fergus Henderson]

Lex Spoon <lex at cc.gatech.edu> writes:
>Fergus Henderson <fjh at cs.mu.oz.au> writes:
>>[someone wrote:]
>>>Why? If the collection happens to contain only elements of a single type 
>>>(or this type at most), you only need to check write accesses if they 
>>>violate this condition. As long as they don't, you don't need to check 
>>>read accesses.
>>
>> So which, if any, implementations of dynamic languages actually perform such
>> optimizations?
>
>I'm sure every implementation does this "optimization", because it is
>simply less code.

You're wrong.  I think you misunderstood what optimization I'm talking about.

>The only time you get a dynamic type error are:
>
>       1. You try to call a method, but the object has no such method.

Calling a method is a read access.  We were discussing optimizations that
ensure that you *don't* need to do a dynamic check for each read access.

>If you are simply doing "x := y" then there is no checking required.

Yes, we covered that already.  But that's not what is happening in
the scenario that I was describing.  The scenario that I'm describing is

	Collection c;

	...
	foreach x in c do
		use(x);

where use(x) might be a method call, a field access, or similar.
For example, perhaps the collection is a set of integers, and you
are computing their sum, so use(x) would be "sum += x".

I think that in these situations, dynamically typed language
implementations will do O(N) dynamic type checks, where N is the number
of elements in "c".  In theory it is possible to optimize these away,
but I don't know of any such implementations that do, and I would be
suprised if there are any (except perhaps in limited cases, e.g. when
the collection is an array or is implemented using an array).

>Regarding your earlier question, though, the great trick in Self was
>to remember the result of a check and thus avoid doing it again
>whenever possible.  If you do "y := x + 1", and you determine that "x"
>is a floating point number, then you know that "y" will also be a
>floating point number immediately afterwards.

Sure.  That helps an implementation avoid checking the type of the collection
"c" at every element access.  But it doesn't help the implementation avoid
checking the type of the element "x" at each iteration of the loop.

>This points to a general observation.  Dealing with the #1 style
>dynamic type errors is a subset of dealing with dynamic dispatch in
>general.  [....] any optimizations that get rid of these dynamic lookups,
>will also get rid of type checks just by their nature.

That's true.  But the difference between dynamically typed languages and
statically typed languages is that in dynamically typed languages, *every*
data access (other than just copying data around) involves a dynamic dispatch.
Sure, implementations can optimize a lot of them away.  But generally you're
still left lots that your implementation can't optimize away, but which
would not be present in a statically typed language, such as the O(N)
dynamic type checks in the example above.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.