[Types-sig] Easier?

[skaller]

Paul Prescod wrote:

>>
Jim created an implementation of an excellent, intelligent optimizing
compiler. His work is as, or more, interesting than mine, but it is a
different problem he is trying to solve. (OPT) comes into the picture
because my work makes his much, much easier and more effective in many
cases. 
<<

I think you are wrong, and right: you are wrong that declarations
makes inferencing easier, it makes it harder, because there is
more syntax to analyse, and so more code to add to the inference engine.
But of course, you are right it makes the algorithm more effective,
in particular, if it is only applied locally (say, to a module,
rather than a whole program).

While I'm here, I'd also like to correct a misconception that
type inference is 'hard'. Irrespective of the case for static
languages like C++ or ML, a Python type inferencer is not
harder, but MUCH easier to write.

Here's the explanation: for static systems, the inferencer
needs to be as complete as possible: the client is going to 
be pretty pissed off it it crashes, or if it fails to deduce
a type (both these thing can happen in the ocaml inferencer).
That's because in these languages, it's necessary to deduce
the type for compilation to proceed.

This is not true in Python. It is not necessary for
inferencing to be 'complete' in the sense it is strongly
desired for static languages. In Python, the following
inferencer is acceptable, if not very good:

	def infer_type(expr): return "PyObject"

This inferencer will not help optimise compiled code,
but it is CORRECT. I will call such an inferencer
a _conservative_ inferencer: it will always work
and always give the correct results, even if they
do not help much with optimisation.

The inferencer above is probably the first one I will use
for Viperc: it will be a brain dead code generator that
does nothing more than wrap the equivalent of
bytecode instructions into the equivalent C function calls.
This has to work ANYHOW, as a fallback if the inferencer
cannot infer enough.

Now, you can try for a better inferencer, and, provided
it is conservative, you can probably only get better performance.
The point is that you can build a compiler with a lousy inference
engine, and improve the inferencer -- and the code generator
-- later. All that is required of the inferencer is that
it be correct (conservative).

The issue then arises, that even a good inferencer will yield
poor performing code. That is where 'aggressive' inferencers
come into play -- these are inferencers that make extra
assumptions, in order to get better deductions.

And my 'Type Inference I' post is all about adding extra
constraints to Python, so that more aggressive inferencers
can be considered conservative -- that is, guarranteed correct
according to language specifications.

Apart from the exception handling problem, another 'assumption'
that inferencers can benefit from is 'freezing': assuming
that, after loading, the bindings in a module are immutable.

Indeed, Viperi actually allows freezing modules now
(i.e. even the interpreter can beneift)  but you
have to explicitly call a function to do it -- because otherwise
the interpreter would be breaking the Python language.
I could dispense with that requirement (that the user call the
freezing function) if Guido were to mandate "thou shalt not
change the binding of a module after it is imported".

I'm not asking for that, just trying to explain how
important conformance issues and specifications are
in optimisation, and in particular, how important
it is that certain operations NOT be defined
(even by a requirement that an exception be thrown).

It is, in fact, fairly true to say that it is the
things which are NOT legal, which are the very
things which permit optimisation. Perhaps Tim or Guido
can explain this better.

-- 
John Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
voice: 61-2-9660-0850