Python compiler?

[Hannah Schroeter]

Hello!

In article <mailman.987615806.20733.python-list at python.org>,
Ken Seehof <kens at sightreader.com> wrote:

>[...]

>> Isn't really needed. Data flow analysis, renaming of separate lifeness
>> spans, then type inference often gains much without changing a
>> source language. And where no unique type can be deduced, you must compile
>> some dynamic dispatch.

>I keep hearing that kind of thing.  Maybe I'm missing something but it seems
>like a compiler would need -reliable- type information to make any
>meaningful
>use of type inference.  Because python is not a functional language (and I'm
>definitely not suggesting that it should be) reliable type inference would
>seem
>to be impossible.

>A good type inference engine would probably get the right answer 98% of
>the time, but would be -certain- of the correct answer maybe 2% of the time.

Of course, the type inference must be defensive. Current Lisp
implementations usually use a combination between optional
explicit type declarations (these are just assertions that the compiler
*may* use for any purpose; in "safe" mode, it must check them either
compile time or run time), and inferred type information. The
inference starts at points where types are known either through
explicit type declarations or through previous knowledge of the
compiler (known types for standard library values and functions and
for constants, already inferred types).

The Lisp standard type model is quite flexible, but OTOH less strong
as e.g. a Hindley Milner type system, insofar as it has almost no
parametric polymorphism, and thus you can't declare e.g. the type of
all lists with only integers as elements. However, you *can* declare
unions, intersections, complements, the "all" type (t) and the
"none" type (nil). In any "place", "t" is a safe assumption.
"t" leads to not so fast code, but will never make an error.

>from zaphod import Z
>z = Z()
>x = 5
>print z
>x = x+1

>Ok, so what is the type of x now?  We simply don't know since that would
>require deep path analysys of the zaphod module in order to confirm that
>Z.__str__ doesn't modify 'x' in the local namespace.  Of course this is an
>absurd example, but the point is there probably is no way for a compiler to
>know algorithmically that this is an absurd example.  Almost every line of
>code in python involves an arbitrary function call that may have unknown
>side effects.

Okay. The Lisp equivalent does as well:

(defpackage ...)
(in-package "SOMEWHERE")

(defvar *z*)	; equivalent of your "z"
(setf *z* (zaphod:make-z))
(defvar *x*)
(setf *x* 5)
(print *z*)	; may invoke some CLOS print method
		; packages and package symbol tables are manipulable!
(incf *x*)

Now, incf must do a check, except perhaps there's an inferred attribute
on (zaphod:make-z) that it yields an object of class "zaphod:z",
and on the cl:print-object generic function, that there's a method
for class zaphod:z and that can't be changed any more at run time,
and that that method does definitely not write to global variables
(i.e. symbol value cells).

That still doesn't hinder the existence of Common Lisp compilers
that don't make mistakes even in those cases, and are efficient in
*usual* code, and still at least as fast as an interpreter in
pathological cases.

>[...]

>One could attempt to make use of unreliable type inference by adding type
>checking to conditionally execute optimized code when the object happens
>to have the correct type, but I think you would end up with a type check
>on almost every line.  Hardly what I'd call optimization.

Dunno. If in 98% the type predictions are right, and in 2% they're
wrong, you can call the number "+1" function with just a conditional
trap "if arg isn't a number, do [more expensive] redispatching" in
the beginning, rather than do a completely dynamical dispatch in
every case. That's one of the strategies often used in JITs: If they
notice at a method dispatch point that most often, one single implementation
is used, they dispatch to that method with just such a small conditional
trap in the beginning of that method. And if the implementation can
prove that only one method can ever be called, it can statically
dispatch a few instructions later in the same method (after the conditional
trap).

>[...]

Kind regards,

Hannah.

PS: You might like to have a look e.g. at the free Lisp compiler contained
in CMUCL and SBCL, which is called Python too, but isn't related to
the Python language and implementations usually discussed here.