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

[Greg Stein]

I tried to "bounce" this to the SIG, but it looks like it got
held/discarded for admin approval since it didn't have types-sig in the
To: header. Forwarding this time...

---------- Forwarded message ----------
Date: Wed, 22 Dec 1999 03:36:36 -0500
From: scott <scott@chronis.pobox.com>
To: Greg Stein <gstein@lyra.org>
Subject: Re: [Types-sig] recursive types, type safety, and flow analysis

On Tue, Dec 21, 1999 at 10:02:08PM -0800, Greg Stein wrote:
> 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).

[...]

> > 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. So you either issues warnings for all global usage, or
> you issue none. You can make a few guesses based on what happens in the
> global code body, but I don't think the guesses will really improve the
> quality of warnings.

I personally can't imagine that it would be an issue to treat globals
in functions as anything other than a simple flat-rule: for type
checking purposes, globals must be defined at compile time in the
global namespace, that's just me, but I'd probably fire any of the
python programmers that work for me if they did what you describe
above with globals in a large project :)

> 
> Examples? No, I don't really have any handy. Any example would be a short
> code snippet and people would say, "yah. that's bad. it should fail." But
> the issue is with larger bodies of code... that's what we're trying to
> fix! So... No, I don't have a non-trivial example.

I can't even imagine one, so if there's any way to describe this
global issue a little further without putting too much effort into it,
I'd appreciate it.

[...]

> 
> The origination of this discussion was based on the recursive type issue.
> If we have runtime objects, then I doubt we could support the recursive
> type thing without some additional work. Or, as I'm suggesting, you do not
> allow an undefined name (as specified by runtime/execution order) to be
> used in a typedecl.

you could even allow typedecl to import modules for the sake of
gaining access to the names, where those imports would only occur when
the optional type checking is turned on.  I'd agree that the use of an
undefined name should be disallowed.  With the presence of
type-check-only import, following the same
no-mutually-recursive-imports rule of the regular import, but only
importing typedecl statements, you could achieve all this at compile
time. 

I've run into this issue on large projects, importing a classname,
just to run 
    assert isinstance(foo, thatclass), "complain meaningfully"

But it hasn't come up with recursive types in any code I've seen, just
deeply-complex types in terms of container and class hierarchy
relationships.

> 
> The design of how to handle recursive types depends on the decision to
> include/exclude runtime objects that define function, class, or module
> typedecl information. Even if we defer the runtime creation of those
> objects, it will affect the design today.
> 

indeed.

[...]
> 
> I do believe the information goes into the bytecode, but I don't think
> that is the basis for needing to plan now. Instead, we have to define the
> semantics of when/where those typedecl objects exist. Do we have them at
> runtime? 

in the above, no, though we do have the ability to find a name
anywhere at compile time.

>Does a name have to exist (in terms of runtime execution) for it
> to be used in a typedecl, or does it just have to exist *somewhere*? 

in the above, it has to exist in the typedecl 'execution' model, which
is during compile time.

>If
> names must exist before usage, then how is the recursive type thing
> handled? With unspecified typedecls? (like an unspecified struct)

How about an iterative model which continues until all typedecl names
are filled in?

I understand your concern about 2 distinct namespace models being
unsettling.  It raises issues of what exactly we want out of static
typing, and what sets of existing and future python code may benefit
from static typing, and these are indeed big issues.  

For me, it is sufficient to proceed from the premiss that you can't
have static typing work on code that redefines types at run time, and
to limit runtime checking (for the time being) to optionally have the
interpreter take some action (warn or abort) when that happens. That
requirement alone implies that typedecl'd names and their typedecl
bodies need to be available at run time, which is sufficient to
support just about any future developments in a static-typeing
interface in pure python.

As an aside, I'm glad to learn it wouldn't be difficult to have python
put static type information in it's byte code.  That seems like a good
place for it.

As weird as it is to have a separate type-decl name model, it seems
infintely  to depict dynamic typing in a static typing model.

scott