Q: Python 2.0 preliminary features?

[skaller]

Neel Krishnaswami wrote:
> 
> On Mon, 11 Oct 1999 12:16:15 +1000, skaller <skaller at maxtal.com.au> wrote:
> >
> >In the third stage, type inference will attempt to ascribe types to
> >the variables, and use some fixed ad hoc speedups to improve
> >interpreter speed even further.
> 
> How do you plan to mix type inference and extension-type/Python-class
> unification?

	Already done. Here is what happens: every object has a type.
The type in Python is an object of type TypeType. This restriction
does not apply in Viper. The type of an object can be ANY object.
The second thing to know is: when 'ordinary' 

	object.value 

lookup fails in Viper, lookup continues for a method in the type object
of the object. For the standard Python types, including integers,
the type object I'm using is a class. So you can write:

	(1).abs()

right now in Viper, because the type of (1) is PyIntType,
for which Types.IntType is a synonym, and PyIntType
is a class object with a method 'abs'. That is,
the integer type is a class IMPLEMENTED IN PYTHON.
[The native function which computes the result
is not, it has to be compiled into the interpreter.]

The class PyIntType is defined, along with the other
types, in a special file py_types.py.

Please note that this is DIFFERENT to saying that
all objects have class type. This is a BAD idea.
I have implemented the exact opposite: in Viper,
all objects have a type object, which can be any object.
In particular, ONLY class instances have classes,
but ALL objects have a type, including classes
and including instances. The type of a class instance is

	PyInstanceType

and is NOT the class of the instance.

To put all this another way, I have extended the EXISTING
python type system to add a new kind of lookup rule,
and relaxed the restrictions on the Type object,
I have NOT unified the type object with the Class.
I have NOT changed the fact that integers are NOT instances
of classes.

What has this to do with type inference? Easy: the only
types I have to deal with are the builtin ones like integers
and class instances, there are no extension types in Viper.

We don't need them, since the 'type' of all objects is
just another object.

The only way extension types are visible to the interpreter
is if the type is a builtin kind, in which case it is necessary
to modify the inference engine .. and the rest of the interpreter.

For example, there is a File type in Viper. But the client
never sees it, because it is wrapped TWICE with classes!
The first wrapper maps the native file manipulation functions,
and sees the File type. The second wrapper provides the
Python compatible interface.

> As I understand it, type inference in OO languages is generally only a
> win if you can do enough to infer the actual runtime type of the
> object. IOW, it's not enough to know that the object is an instance of
> some subclass of the class Number, but that it's a direct instance of
> the class Integer.  Then you can avoid paying the cost of polymorphic
> dispatch, and can take advantage of knowing the actual method called
> to do additional optimizations (like inlining).

	Yes. In particular, the kinds of things that are worth
optimising are things like:

	x = x + 1

where x is not aliased: this can be replaced by

	x += 1

and avoid an allocation.
 
> But if Python's primitive types are made into real Python classes,
> then any type can be potentially be subclassed, which makes inferring
> the runtime type a much harder prospect.

	Indeed. Luckily, subtyping the basic python types
is entirely useless, for every single python type except
'file'. That is because python types are in fact naturally
algebraic NOT object oriented, again, with the exception
of 'file', which is sensibly an object.

	[Another exception is, exceptions, but they're
already class based]
 
> AFAICT, you need to either add something like Java's "final" keyword,
> do whole-program analysis (does eval defeat this?), or do dynamic
> compilation like Self. Or are there some cool new tricks you can steal
> for Viper from the OCaml compiler..?

	The basic optimisations are functional, that is,
things like making string concatenations go faster in cases like:

	x  = x + "hello"

Here, the deduction starts with the literal "hello"
which
is known to be a string, and, since + accepts a string
RHS only when the LHS is also a string or an int,
and the int case is eliminated since the type of the LHS
of the assignment is also the type of X, and both
operators called + with string RHS return a string,
then x must be a string.

	Now, if strings can be class instances,
we must account for that case too, so there will need
to be a run time test, to check if the x is
a basic string, or some derived type.

	Luckily, because I do whole program analysis,
i know all the classes, including those that
have a + method (__add__). It may be difficult
to decide if the x above is one of those type,
rather than string.

	But somewhere, the programmer had to construct
the x, and it is possible to trace it back to see what
type it is. Sometimes, the result will be it could
be one of several types:

	if t ==0:
		x = "a string"
	elif t == 1:
		x = ClientType("who knows")
	else:
		x = None

but evern here, the set of possible type is enumerable.

	So .. you are right, if all types were
classes and could be subclassed, then determining
which method to call would be harder. However, with
my current system, the extra lookup into the type
object is done, and that type object is itself
compiled, since it is written in Python.
So the dispatch should proceed at reasonable
speed, especially if name binding is already done.

-- 
John Skaller, mailto:skaller at maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller