[Types-sig] recursive types, type safety, and flow analysis

[Michael Hudson]

Whew! I go on holiday for a week and 400+ messages turn up on types-sig!
I've scanned them all, but I'm not sure I'm not repeating others here.
Exciting times... 

----------
>From: Greg Stein <gstein@lyra.org>
>To: types-sig@python.org
>Subject: Re: [Types-sig] recursive types, type safety, and flow analysis
>Date: Wed, Dec 22, 1999, 6:02 am
>

>On Tue, 21 Dec 1999, scott wrote:
>> On Tue, Dec 21, 1999 at 08:06:28PM -0800, Greg Stein wrote:
>>...
>> > Basically, I think your request to find and report on
>> > use-before-definition is "intractable" *when* you're talking about
>> > multiple bodies of code (e.g. two functions, or the global space and a
>> > function).
>> > 
>> > [ by "intractable", I mean within the scope of what I believe we want to
>> >   build; the problem is certainly doable but I believe it would involve
>> >   complex, global, control-flow analysis. ]
>> 
>> I'd agree that this has been demonstrated, but only for examples of
>> code which seem like great candidates for compile time warnings.  Are
>> there examples which strike you otherwise?
>
>One of my points was that I do not believe you can issue warnings because
>you can't know whether a problem might exist. Basically, it boils to not
>knowing whether a global used by a function exists at the time the
>function is called. 

Which is because you CAN'T! For the very simple case (i.e. name assigned to
at toplevel of module, never referred to in a "del" statement), you know
everything about the lifetime of the variable, and for other cases you in
general know nothing, because to know more for arbitrary cases involves
solving the halting problem. If people want to typecheck code along the
lines of


a = 0
if some_function():
    del a

then, frankly, sod 'em.

You could make allowances for code along the lines of

if __debug__:
    verbose = 1
else:
    verbose = 0

but I don't think it's worth it. (which leads to an argument for being able
to restrict types assigned to names, thinking about it...)

[snip]

On a separate point, there is only one language that I can think of that is
as dynamic (probably more so, actually) than Python, yet has optional static
typing (mainly for OPT, to be sure, but you get some ERR, too), and that is
ANSI Common Lisp. The more I read of this present discussion, the more I
repsect the way CL is designed.

The things that seem most immediately relavent are: 

1) Just declaring the type for names is enough most of the time (eg.
(declare (type <type> <var>*))), but occasionally you want to type
expressions too (eg. (the <type> expr)).

2) It's worth having distinguished "read" and "compile" phases (and a "macro
expansion" phase would surely be nice...).

3) Type inference need not be demanded in a compiler, but it's nice when
it's there.

If anyone partaking in this discussion doesn't know CL's approach to types
and typing, I'd heartily enjoin them to find out. Dylan might be relavent
too, but I don't know that.