Mailing List Archive

In article <37b075ae.2367293988@news.triode.net.au>
skaller@maxtal.com.au "John (Max" writes:
> This is a request for comments on Viper, Yet Another implementation
> of Python. I'm building Viperi, the interpreter, and I'm interested in
> comments on three issues:
>
> 1) compatability with Python
> 2) Extensions
> 3) Optimisation
>
> Viperi is being built as a prelude to implementation of an optimising
> compiler, Viperc. Unlike previous attempts at a compiler, Viperc will do
> type inference, inlining, and special case analysis,
> in an attempt to optimise generated code.
>
> The interpreter aims to be compatible with 'pure python':
> python not using external C modules, and not fiddling
> implementation details too much. Some of the fiddles
> will work, and some will not.
>
> Compatibility:
> 1) exceptions: both string and class exceptions are supported,
> the class exceptions are client defined in exceptions.py
>
> 2) rebinding module variables after importing is not permitted
> 3) None is a keyword.
> 4) range is a keyword
>
> 5) What restrictions can you live with?
>
> Extensions:
> 1) full slicing semantics
> 2) optional values in dictionaries (Defaults to None)
> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'
> 4) lexically scoped functions (including lambdas)
> 5) optionally typed function parameters
>
> 6) what do you want?

C-style comments

sorted dictionary loops, eg:

for k, v in dict.sortedValues():

where this is sorted by keys.

--
Phil Hunt....philh@vision25.demon.co.uk

John (Max) Skaller <skaller@maxtal.com.au> wrote:
> This is a request for comments on Viper, Yet Another implementation
> of Python. I'm building Viperi, the interpreter, and I'm interested in
> comments on three issues:

> 1) compatability with Python
> 2) Extensions
> 3) Optimisation

> Viperi is being built as a prelude to implementation of an optimising
> compiler, Viperc. Unlike previous attempts at a compiler, Viperc will do
> type inference, inlining, and special case analysis,
> in an attempt to optimise generated code.

It sounds like my (vaporware) Swallow idea. The difference with Viper
is that Viper apparently is going to do type inference, while Swallow
would (at least in the first stages) make do with nonintrusive type
declarations, somewhat like this:

__types__ = {
foo : functionType(args={a: intType, b: intType}, returns=listType(intType)),
bar : functionType(args={}, returns=None)
}

def foo(a, b):
return [a, b]

def bar():
print "hello world"

But I forget the exact details right now. :) I did get a very simple Python
program going that could figure out if two complex types in the declaration
were the same. The idea is to go with a generic type approach somewhat
similar to C++ templates (but easier :). For instance, you'd say:

listType(intType) and Swallow would emit C code for a list of integers.

The idea is also to specify the types of local variables.

In the end, the only types that would need inferring with such a system
would be the type of empty lists and dictionaries:

__types__ = { foo : functionType(..., locals={ bar: listType(intType }) }

a = [] + [1, 2]

The first [] would have no type yet, but it would be fairly straightforward
to figure it out from the expression (I hope!)

> The interpreter aims to be compatible with 'pure python':
> python not using external C modules, and not fiddling
> implementation details too much. Some of the fiddles
> will work, and some will not.

This is a good idea, as pure Python will often still be the development
language (while Swallow/Viper would only be invoked to compile and
optimize things later on, at least in the early stages).

> Compatibility:
> 1) exceptions: both string and class exceptions are supported,
> the class exceptions are client defined in exceptions.py

> 2) rebinding module variables after importing is not permitted
> 3) None is a keyword.
> 4) range is a keyword

Why this? Perhaps instead you could make 'range' and some other builtin
functions 'special functions'. The idea is that like module variables
(and some other set of things perhaps) they cannot be rebinded to something
else, so that the optimizer can do its stuff.

> 5) What restrictions can you live with?

> Extensions:
> 1) full slicing semantics
> 2) optional values in dictionaries (Defaults to None)
> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'
> 4) lexically scoped functions (including lambdas)
> 5) optionally typed function parameters

> 6) what do you want?

I wouldn't aim for *any* extensions to start with. In order for such a
project to succeed you want Viper code to run in Python and vice versa,
unless there's serious messing with internals. At least make it possible
to turn these extensions *off* so they'll be errors.

[snip optimisation discussion]

Hm, I wish you luck, especially with the type inference...

Does viperc compile Python to C code? If so, try to minimize the amount of
C code that's emitted, if at all possible.

> Generally, compiler optimisations
> will go hand in hand with restrictions -- to optimise
> something, information is required, and that will
> require giving up some dynamism.

So you could do with Swallow's "type system" (big word for nothing there),
right?

> It is difficult to optimise individual
> modules. It is a different story to optimise
> a whole program, where _every_ call
> to a function can be traced. Of course,
> this may involve restricting what 'exec' can do,
> and it may involve other restrictions
> (such as not changing any module bindings
> after loading).

Hm, but the possibility to optimise individual modules is what attracts
many people to this idea. This way, people can stay away from writing
C modules and write them in Python instead. The Swallow cycle I had in
mind was something like this:

* Write Python module

* Need to make it faster (at least some functions)

* Supply full type information for any local variables, arguments, etc.
Anything *called* by the functions should also be Swallowable (or already
supported by Swallow).

* Swallow now optimises these functions by translating them to C, and
you can use them in Python (just like C extension modules).

For classes you'd need some extra support (and more restrictions) but that
was phase 2. My advice is to start as small and unambitious as possible
for such an ambitious project. :)

Regards,

Martijn

skaller@maxtal.com.au (John (Max) Skaller) writes:

> Extensions:
>
> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'

At first I thought `hey that's cool!' since I'm kindof sick of typing
has_key() all the time. But then I realized that this is not really
consistent with sequence types.

item in list IMPLIES list[something] == item

but according to your definition,

item in dict IMPLIES list[item] == something

where in each case `something' is undetermined. I suggest you rethink
this `feature'.

Michael

--
Michael Haggerty
mhagger@blizzard.harvard.edu

skaller@maxtal.com.au (John (Max) Skaller) writes:

> This is a request for comments on Viper, Yet Another implementation
> of Python. I'm building Viperi, the interpreter, and I'm interested in
> comments on three issues:
>
> 1) compatability with Python
> 2) Extensions
> 3) Optimisation
>
> Viperi is being built as a prelude to implementation of an optimising
> compiler, Viperc. Unlike previous attempts at a compiler, Viperc will do
> type inference, inlining, and special case analysis,
> in an attempt to optimise generated code.

I think JPython does some global analysis; not heard anything on that
front for a while though.

I'm interested (do you have any code yet?) but I have a few questions:

> The interpreter aims to be compatible with 'pure python':
> python not using external C modules, and not fiddling
> implementation details too much. Some of the fiddles
> will work, and some will not.

I presume fiddling with sys.exc_traceback.f_back.f_locals is out?

> Compatibility:
> 1) exceptions: both string and class exceptions are supported,
> the class exceptions are client defined in exceptions.py
>
> 2) rebinding module variables after importing is not permitted

Does this mean the following is illegal:

import foo
foo.bar = 1

But can foo then have a method set_bar? I guess that would be easier
to cope with for the analyser.

> 3) None is a keyword.
> 4) range is a keyword

What about other builtins? Can't your static analysis find rebindings
of builtin names (including range) rather easily? - particularly as
the don't happen very often.

> 5) What restrictions can you live with?

One thiung I occasionally find very handy is the ability to assign
methods to classes (or more usually within classes).

> Extensions:
> 1) full slicing semantics

Cool.

> 2) optional values in dictionaries (Defaults to None)

Now this one I don't get; do you mean dict[] has dict.get like
semantics?

> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'

Seems unecessary to me. Maybe that's just me.

> 4) lexically scoped functions (including lambdas)

Cool.

> 5) optionally typed function parameters

Out of curiosity, what syntax do use for this? I presume if a
parameter is typed as `Foo' then a value of type `Bar' where Bar
derives from Foo is allowable.

> 6) what do you want?

Can you derive from basic types? That might make some stuff harder.

[snip]
>
> It is difficult to optimise individual
> modules. It is a different story to optimise
> a whole program, where _every_ call
> to a function can be traced. Of course,
> this may involve restricting what 'exec' can do,

Like banning it entirely, I suspect.

> and it may involve other restrictions
> (such as not changing any module bindings
> after loading).

Is that really that much of an issue? I'd have thought that they'd be
fairly easy to spot. Mind you, the whole thing sounds sooo hard, that
anythong that makes it easier is good.

Good luck! (I think you may need it)

Michael

>>>>> "MH" == Michael Hudson <mwh21@cam.ac.uk> writes:

MH> I think JPython does some global analysis; not heard anything
MH> on that front for a while though.

At IPC7, JimH reported on some experiments he'd been doing
<http://www.jpython.org/jpython-talk-1.ppt> with whole program
analysis in the jpythonc tool. He reported some impressive results,
but alas most of that stuff had to be taken out of the released
version of the tool. Due to lack of time, this work will probably be
on the back burner for a long while unless someone else with interest
adopts it.

-Barry

Phil Hunt wrote:
> > 6) what do you want?
>
> C-style comments
>
> sorted dictionary loops, eg:
>
> for k, v in dict.sortedValues():
>
> where this is sorted by keys.

If this last one is what you want, why not use either my B-Tree
container class, or my Trie container class?

Either one gets you reasonably fast mapping/unmapping, as well
as sorted keys.

John S.

On Tue, 10 Aug 99 23:15:18 GMT, philh@vision25.demon.co.uk (Phil Hunt) wrote:

>In article <37b075ae.2367293988@news.triode.net.au>
> skaller@maxtal.com.au "John (Max" writes:
>> This is a request for comments on Viper,
>> Extensions:
>> 6) what do you want?
>
>C-style comments

With what syntax, and why?

1. Syntax:

The C syntax doesn't support nesting; OTOH the PL/1 ML style
(* ... *) syntax does.

New lexicology for strings and comments is easy
enough to add, since it only affects the lexer. However, it is
also easy to create an unreadable mess if _too many_
new lexical forms are introduced.

2. Why?

One obvious reason: annotating things like function parameters
with C++/Python style comments can expand source code too much:

def f( # a function
a, # arg1
b # arg2
):

might be written

def f /* a function */ ( a /* arg1 */, b /* arg2 */ ):

on one line with C style comments.

>sorted dictionary loops, eg:
>for k, v in dict.sortedValues():
>where this is sorted by keys.

Something to support dictionary iteration is
needed. My thought was:

for k in dict: value = dict[k] ...

which is equivalent to

keys = dict.keys()
keys.sort()
for k in keys: value = dict[k]

Unfortunately, you can't write

for k in dict.keys().sort():

because the keys() refers directly to the dictionary
keys, and sort() sorts in place. Both these methods
are the way they are for efficiency. Perhaps a new
method would be a good solution (for Python 1.6 too):

for k in dict.sorted_keys(): ...

however, there is a related idea here, that a dictionary
with all values None is isomorphic to a set. Thus

k in dict

would mean

k in set

which is natural notation, and

k in dict

is an extension to dictionaries in which the
set is the set of keys.

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

On Fri, 13 Aug 1999 11:04:12 -0600, "John W. Stevens" <jstevens@basho.fc.hp.com> wrote:

>Phil Hunt wrote:

>> sorted dictionary loops, eg:

>If this last one is what you want, why not use either my B-Tree
>container class, or my Trie container class?

One of the goals of Viper is too eliminate
the need for C modules There are several reasons
for this. One is that C modules are hard to implement,
another that the C API changes from CPython version
to version, another is that it isn't really as efficient as
whole program analysis, the API dependent on a _particular_
Python implementation (i.e. won't work with JPython),
and finally, it is hard to build a C module, so distributing
Python code including C modules is difficult for
developers.

This last point is the real killer. I have both a Linux and
NT box. I have no problem with building C modules
on Linux, but I don't _have_ a compiler on the NT box that
will build C modules compatible with the Python implementation
I have. [.I have Borland C++, and gcc on the NT box,
but not MSC, which was used to build my NT based Python]

Pure python is easier to distribute. If it could be compiled
to be as fast as C modules, there is no need for the
portability headache.

Having said all that, I think it is worth providing a binding
to existing C modules, but I can't do everything at once,
and the extra work required to do the binding is too much
at the moment.

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

On 11 Aug 1999 08:21:14 GMT, m.faassen@vet.uu.nl (Martijn Faassen) wrote:

>It sounds like my (vaporware) Swallow idea. The difference with Viper
>is that Viper apparently is going to do type inference, while Swallow
>would (at least in the first stages) make do with nonintrusive type
>declarations, somewhat like this:
>
>__types__ = {
> foo : functionType(args={a: intType, b: intType}, returns=listType(intType)),
> bar : functionType(args={}, returns=None)
>}

This is neatly compatible with existing Python code.

>> The interpreter aims to be compatible with 'pure python':
>> python not using external C modules, and not fiddling
>> implementation details too much. Some of the fiddles
>> will work, and some will not.
>
>This is a good idea, as pure Python will often still be the development
>language (while Swallow/Viper would only be invoked to compile and
>optimize things later on, at least in the early stages).

Originally, I planned to recommend development
in Python, and just using Viper for compilation: that is,
I intended to ignore any sophisticated debugging support.
However, I'm beginning to swing the other way now, and
try to provide _better_ debugging than Python.

The reason is pragmatic: without the debugging
support, I can't debug Viper itself.

>> Compatibility:
>> 4) range is a keyword
>
>Why this? Perhaps instead you could make 'range' and some other builtin
>functions 'special functions'.

Yes, that's the idea.

>The idea is that like module variables
>(and some other set of things perhaps) they cannot be rebinded to something
>else, so that the optimizer can do its stuff.

That is what I meant by saying it was a keyword.

>> Extensions:

>I wouldn't aim for *any* extensions to start with. In order for such a
>project to succeed you want Viper code to run in Python and vice versa,
>unless there's serious messing with internals. At least make it possible
>to turn these extensions *off* so they'll be errors.

There are two kinds of extensions: those requiring
extra keywords, and those that 'fit naturally' into python.

Extensions requiring extra keywords can be turned
off with a compiler switch that disables the lookup in the lexer
that maps names to keywords. Then the parser will not
recognize these extensions.

The other kind of extensions include things
like lexical scoping and slicings, where existing or extended syntax is given new
semantics. Sometimes (hopefully rarely) this may lead to an
incompatibility. For example nested functions in Viper
are bound to the activation record of the enclosing
function. As such, variables in the enclosing scope will
hide globals, changing the semantics.

>Hm, I wish you luck, especially with the type inference...

Preliminary tests indicate reasonable results
determining types. In critical cases such as inner loops,
it is usually possible:

s = ""
for i in range(1,10): s = s + str(i)

Obviously i is an integer here, and s a string.

>Does viperc compile Python to C code?

I don't know yet. In the first instance,
a run time is still needed that works like existing Python,
where type inference fails. Therefore, I still need an
interpreter. So Viperi, the interpreter, is the first step.
[.It doesn't support 'global' at the moment, so I cannot
yet run PyStone. I'd like to eliminate 'global']

I will try to optimise it first, before considering
how to build the compiler, and what back ends to implement.
It is possible the first back end will actually general Ocaml
rather than C (since Viper is currently implemented in ocaml).

>> Generally, compiler optimisations
>> will go hand in hand with restrictions -- to optimise
>> something, information is required, and that will
>> require giving up some dynamism.
>
>So you could do with Swallow's "type system" (big word for nothing there),
>right?

Yes. It is useful to have optional typing, to
help make the type inference work. I was considering:

def f(x:int): ...

as the syntax ( because this is fairly conventional,
and a pure extension). However, it isn't
backward compatible, whereas your idea is,
so I will look at it. [The method resembles the
'traits' templates in C++ STL]

>> It is difficult to optimise individual
>> modules.

>Hm, but the possibility to optimise individual modules is what attracts
>many people to this idea.

I know. However, existing attempts to
build a python compiler have not succeeded in
producing code that is much more efficient than
the bytecode interpreter.

Why is this? I suspect it is because
a function in Python is often unintentionally
more polymorphic than actually desired: for example:

def add(i,j): return i + j

Due to the unfortunate overloading of + on
numbers and strings, it is not possible to
determine if 'add' adds numbers or concatenates
strings. However, this can be determined by examining
_calls_ to the function add.

It is possible that both are done: the function is actually
used polymorphically .. but not necessarily in the
same program

Perhaps a _worse_ case is this:

def get_attribute(a,b):
try: return get_attr(a,b)
except: return None

Here, the return type could be anything at all.
If we knew 'a' was an object with only string
attributes, the return type would be either
string or None.

In that case, the function is monomorphic,
but the return type is the sum of string and NoneType.

> * Swallow now optimises these functions by translating them to C, and
> you can use them in Python (just like C extension modules).
>
>For classes you'd need some extra support (and more restrictions) but that
>was phase 2. My advice is to start as small and unambitious as possible
>for such an ambitious project. :)

I agree. However, it turns out adding extensions is often
trivial, whereas providing compatibility is often difficult. Similarly,
it may be more difficult to generate a function than a whole
module, and more difficult to do that than build a whole
program.

In particular, building a whole program is easiest,
since it doesn't require interfacing to python. That interface
is non-trivial: binding to the C API, and then the bytecode
interpreter, and then again, the result is different if you
were using JPython.

So it may be easier to just provide
a binding at a single level, namely
'pure python' source code, than try to build something
that interfaces to existing Python.

In addition, Python 1.6 may have different
internals, and so may Python 2.x. This creates
a maintenance nightmare which may make the project
less useful.

OTOH, many python 'built in C modules'
have corresponding Pure Python sources, for example
the string module. In that case, if the compiler works,
there is no need for the C module.

Another example is Lemburgs mxTools:
I have a 'Pure python' implementation of it,
so I don't need the C version, thus eliminating
a maintenance problem.

Another example (which is now working):
Python has a module 'exceptions'. I have no idea
if Python actually compiles this module and uses it,
however, Viperi currently does. That is, it actually
imports the exceptions module and uses the
classes in it for exceptions.

If Guido adds a new exception,
or changes the semantics, implementation,
or interface, I have a rock solid python compatible
specification to implement, and half the work
will be done by Viper itself. [.Not all, since the
internal exceptions stll have to be mapped to the
python ones]

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

On 11 Aug 1999 10:59:10 -0400, Michael Haggerty <mhagger@blizzard.harvard.edu> wrote:

>skaller@maxtal.com.au (John (Max) Skaller) writes:
>> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'
>
>At first I thought `hey that's cool!' since I'm kindof sick of typing
>has_key() all the time. But then I realized that this is not really
>consistent with sequence types.
>
> item in list IMPLIES list[something] == item
>
>but according to your definition,
>
> item in dict IMPLIES list[item] == something
>
>where in each case `something' is undetermined. I suggest you rethink
>this `feature'.

I agree there are some difficulties here, which is why
I'm appealing to the Python community for ideas.

There is an alternate possible definition:

k,v in dict

which might make more sense:

dict.has_key(k) and dict.get(k)

However the idea is that

x in Y

means 'x is a member of the set of elements of Y'
and for a list the 'set of elements of Y' is the
set of elements of the list, and for a dictionary
it is the set of keys of the dictionary.

In this way, the meaning is consistent for lists
and dictionaries. Furthermore,

for x in Y: S(x)

is also well defined as executing S(i) for
each i in Y: for lists and tuples, in the order
of the list or tuple, for dictionaries either
in a random order, or in order of the sorted
keys.

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

On Sun, 15 Aug 1999 15:36:39 GMT, skaller@maxtal.com.au (John (Max)
Skaller) wrote:

[snip]

>This last point is the real killer. I have both a Linux and
>NT box. I have no problem with building C modules
>on Linux, but I don't _have_ a compiler on the NT box that
>will build C modules compatible with the Python implementation
>I have. [.I have Borland C++, and gcc on the NT box,
>but not MSC, which was used to build my NT based Python]

You can use GCC 2.95 for mingw32
(http://www.xraylith.wisc.edu/~khan/software/gnu-win32/gcc.html)
to compile Python extensions on NT. See my page
http://starship.python.net/crew/kernr/mingw32/Notes.html

Such extensions will work with the distributed Python interpreter for
Win32.

[snip]

>John Max Skaller ph:61-2-96600850
>mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
>http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

Robert Kern |
----------------------|"In the fields of Hell where the grass grows high
This space | Are the graves of dreams allowed to die."
intentionally | - Richard Harter
left blank. |

On 11 Aug 1999 18:23:06 +0100, Michael Hudson <mwh21@cam.ac.uk> wrote:

>skaller@maxtal.com.au (John (Max) Skaller) writes:

>I'm interested (do you have any code yet?

Not for the compiler: I'm implementing
the interpreter first. [.I have done some work on the
type inference algorithm, to make sure it is
feasible]

>) but I have a few questions:
>
>> The interpreter aims to be compatible with 'pure python':
>> python not using external C modules, and not fiddling
>> implementation details too much. Some of the fiddles
>> will work, and some will not.
>
>I presume fiddling with sys.exc_traceback.f_back.f_locals is out?

At present sys.exc_info() will return a tuple in which
the third element is a traceback object. At present, that
traceback object doesn't match the Python one --
it just has a filename and line number in it, to allow the
traceback to be printed.

However, I will try to make everything
as 'python compatible' as possible, at least in the
interpreter. In the compiler, a few things that
work in the interpreter may fail. However,
another possible result is simply to make the
compiled code more inefficient, rather than it
failing. For example, 'exec' must still work.

[Interscript uses exec, so I have to support it ;-]

>> Compatibility:
>> 2) rebinding module variables after importing is not permitted
>
>Does this mean the following is illegal:
>
>import foo
>foo.bar = 1

Technically yes, according to what I said.
But actually, something less stringent will be required.
What will happen is that the compiler will begin
by executing the interpreter on all modules the main
program imports.

During that phase of the compilation
process, assignment to module variables outside
the module will be OK.

AFTER all the modules are imported,
it may not be OK because then I may inline the
value, which means that an assignemt wouldn't
be honoured. However, it isn't clear that I cannot
simply detect such direct assignments and force
the system to honour the current value,
indeed, this may be necessary in some special
cases such as assigning to

sys.stdin

which is a necessary evil for compatibility.

It may end up that the restriction is
that you cannot do:

exec "foo.bar = 1"

because that cannot be detected easily by
static analysis.

>But can foo then have a method set_bar? I guess that would be easier
>to cope with for the analyser.

Yes. It is OK to mutate objects, as opposed
to rebinding variables: mutation has to be supported.
You may think these things are equivalent. Indeed,
they are in interpreted python. However, the restriction
leads to a performance gain; without some restrictions,
compiled python will not execute faster than the bytecode
interpreter.

Indeed, the existing python bytecode compiler
makes such restrictions itself [.on class __getattr_
and __set_attr__ methods, which are cached for
efficiency, as I understand it]

>> 3) None is a keyword.
>> 4) range is a keyword
>
>What about other builtins?

Yes.

>Can't your static analysis find rebindings
>of builtin names (including range) rather easily? - particularly as
>the don't happen very often.

I hadn't considered that, but the answer is probably
'yes', provided they don't occur in 'exec's.

>> 5) What restrictions can you live with?
>
>One thiung I occasionally find very handy is the ability to assign
>methods to classes (or more usually within classes).

OK. I would like to do what Guido has done in the
optimisation of functions [.fast lookup for statically known variables,
plus a dictionary to support others]: provide an optimised structure
where possible, and then provide a dynamic one
for the other cases. That is, the ideal would be to provide
a 'fallback' to the interpreter.

>> Extensions:
>
>> 2) optional values in dictionaries (Defaults to None)
>
>Now this one I don't get; do you mean dict[] has dict.get like
>semantics?

No, you can just write:

d = {1,2,3}

and it is OK and means:

d = {1:None, 2:None, 3:None}

>> 3) 'in' applies to dictionaries 'as if a sequence of keys were used'
>
>Seems unecessary to me. Maybe that's just me.

The idea is that:

x in {1,2,3}

means 'x ==1 or x == 2 or x ==3', that is, the construction

{1,2,3}

can be used like a set (without introducing a new data structure}.

>> 5) optionally typed function parameters
>
>Out of curiosity, what syntax do use for this?

My first idea was the obvious:

def f(a:int): ..

or perhaps

def f(a: IntType): ...

and the interpreter semantics would be

if type(a) is not InType: raise TypeError, "Int expected for arg1 of f"

However, in the compiled version, the semantic might be to generate a compiler
error: that is, the following might not work:

try: f(1.0)
except TypeError: pass # just skip the call


>I presume if a
>parameter is typed as `Foo' then a value of type `Bar' where Bar
>derives from Foo is allowable.

I guess that would make sense (the extension isn't
implemented yet -- not a lot of point appealing for comments
_after_ implementing the extension, only to find someone
has a better idea)

>> 6) what do you want?
>
>Can you derive from basic types? That might make some stuff harder.

Not at present. Can you give an example where
it is useful? [.It can be made to work I think: is it useful?]

>> It is difficult to optimise individual
>> modules. It is a different story to optimise
>> a whole program, where _every_ call
>> to a function can be traced. Of course,
>> this may involve restricting what 'exec' can do,
>
>Like banning it entirely, I suspect.

No. I cannot do that because the program
that I want to compile, interscript, uses exec,
and depends on it to execute client script.
This is the major feature of interscript, so exec
has to work (at least with restrictions).

That means the compiled code has to
contain a full run time system (unless it can be
detected that it isn't required).

>> and it may involve other restrictions
>> (such as not changing any module bindings
>> after loading).
>
>Is that really that much of an issue? I'd have thought that they'd be
>fairly easy to spot.

Several people have said that, and may be right.
I'll examine this issue, since it would provide extra compatibility
to permit it.

As an example of why rebinding should be supported:

_open = open
opened_files = []
def open(f,m):
opened_files.append(f)
_open(f,m)

This code just hooks 'open' to create a list
of all files opened, which could be useful.
So rebindings are a useful trick.

>Mind you, the whole thing sounds sooo hard, that
>anythong that makes it easier is good.

The things that turn out to be hard are
often surprising. For example, right now I having
major problems with something that sounds trivial:
getting the interpreter to set the line number
so that a traceback can print out as it does in Python.

That sounds easy, but the LR grammar I'm
using is not well adapted to it -- NEWLINE tokens
come after statements, instead of before them,
where the line number is needed.

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

On Wed, 11 Aug 1999 15:48:09 -0400 (EDT), "Barry A. Warsaw" <bwarsaw@cnri.reston.va.us> wrote:

>At IPC7, JimH reported on some experiments he'd been doing
><http://www.jpython.org/jpython-talk-1.ppt> with whole program
>analysis in the jpythonc tool. He reported some impressive results,

I'm very encouraged by this.


John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

John (Max) Skaller (skaller@maxtal.com.au) wrote:
: Preliminary tests indicate reasonable results
: determining types. In critical cases such as inner loops,
: it is usually possible:
:
: s = ""
: for i in range(1,10): s = s + str(i)
:
: Obviously i is an integer here, and s a string.

Is it? Surely that depends on what "range" and "+" are bound to at
runtime.

I don't wish to be a spoil-sport but I really do believe that type
inference in Python is a waste of time, and hence your ideas to speed
things up are doomed to fail in all but the simplest of cases. Python
is far too dynamic to be type inferenced (or even type checked). Whether
that's a good thing or not is another matter, but it's certainly a
fact I think.

graham

--

England's not the mythical land of madame george and roses
It's the home of police who kill black boys on mopeds

skaller@maxtal.com.au (John (Max) Skaller) writes:
> On 11 Aug 1999 18:23:06 +0100, Michael Hudson <mwh21@cam.ac.uk> wrote:
> >I'm interested (do you have any code yet?
>
> Not for the compiler: I'm implementing
> the interpreter first. [.I have done some work on the
> type inference algorithm, to make sure it is
> feasible]

Let me rephrase that a little: do you have any code that I can look
at/play with/beat on/improve (maybe)? Actually working/complete code
is not expected or desired, I'm just nosey.

> >I presume fiddling with sys.exc_traceback.f_back.f_locals is out?
>
> At present sys.exc_info() will return a tuple in which
> the third element is a traceback object. At present, that
> traceback object doesn't match the Python one --
> it just has a filename and line number in it, to allow the
> traceback to be printed.

I feel I ought to point out that I'm not particularly desperate to
retain the ability to perform this particular stunt, I was just trying
to get a feel for the limitations you were talking about.

> >But can foo then have a method set_bar? I guess that would be easier
> >to cope with for the analyser.
>
> Yes. It is OK to mutate objects, as opposed
> to rebinding variables: mutation has to be supported.
> You may think these things are equivalent. Indeed,
> they are in interpreted python.

I'd dispute that, but never mind.

> However, the restriction leads to a performance gain; without some
> restrictions, compiled python will not execute faster than the
> bytecode interpreter.

Quite.

> >> 5) What restrictions can you live with?
> >
> >One thiung I occasionally find very handy is the ability to assign
> >methods to classes (or more usually within classes).
>
> OK. I would like to do what Guido has done in the
> optimisation of functions [.fast lookup for statically known variables,
> plus a dictionary to support others]: provide an optimised structure
> where possible, and then provide a dynamic one
> for the other cases. That is, the ideal would be to provide
> a 'fallback' to the interpreter.

vtables might be nice (i.e. attribute accesses don't always go through
a dictionary lookup). Bigger win for compiled code, I suspect.

You could only vtable-ize the methods/data members that static
analysis found were never assigned to in code. This suggests another
restriction for exec.

[.snipped dictionary extensions that I still don't see the need for but
then again if I don't like them I can just ignore them]

> >> 5) optionally typed function parameters
> >
> >Out of curiosity, what syntax do use for this?
>
> My first idea was the obvious:
>
> def f(a:int): ..
>
> or perhaps
>
> def f(a: IntType): ...
>
> and the interpreter semantics would be
>
> if type(a) is not InType: raise TypeError, "Int expected for arg1 of f"

Fair enough; it might be nice (& probably very easy) to hack a CPython
that accepted but ignored type declarations of this sort.

> However, in the compiled version, the semantic might be to generate
> a compiler error: that is, the following might not work:
>
> try: f(1.0)
> except TypeError: pass # just skip the call

I'd say if you coded like that you deserved to lose anyway. Might
become a bigger problem in more complex cases, of course.

> >I presume if a
> >parameter is typed as `Foo' then a value of type `Bar' where Bar
> >derives from Foo is allowable.
>
> I guess that would make sense (the extension isn't
> implemented yet -- not a lot of point appealing for comments
> _after_ implementing the extension, only to find someone
> has a better idea)

I think it would be a hanging offense for anything that called itself
OO to not allow a instance of a derived class to be substituted for
that of a base class.

> >> 6) what do you want?
> >
> >Can you derive from basic types? That might make some stuff harder.
>
> Not at present. Can you give an example where
> it is useful? [.It can be made to work I think: is it useful?]

It's more neat than useful, as far as I can see. But I'll have to
learn more ml, Haskell, smalltalk, Eiffel and lisp/clos before I can
comment properly on type issues, I think (I am actually moderately
serious about learning all the above languages - doing Haskell, Eiffel
and ANSI common lisp at the moment).

> >> It is difficult to optimise individual
> >> modules. It is a different story to optimise
> >> a whole program, where _every_ call
> >> to a function can be traced. Of course,
> >> this may involve restricting what 'exec' can do,
> >
> >Like banning it entirely, I suspect.
>
> No. I cannot do that because the program
> that I want to compile, interscript, uses exec,
> and depends on it to execute client script.
> This is the major feature of interscript, so exec
> has to work (at least with restrictions).

I see; I guess what you're saying is that exec-ed code can't muck with
it's calling environment too much. I'd have thought this would be a
feature for interscript, otherwise malicious documents could seriously
injure the environment.

> That means the compiled code has to
> contain a full run time system (unless it can be
> detected that it isn't required).

Lisp manages to have a very clean interaction between compiled and
interpreted code: you type (compile 'f) and hopefully the only
noticeable difference is that `f' goes quicker. Mind you lisp has had
man-millennia of time from very very clever people poured into it, so
that might be aiming a bit high ;-).

[snip]

> >Mind you, the whole thing sounds sooo hard, that
> >anythong that makes it easier is good.
>
> The things that turn out to be hard are
> often surprising.

That's always the way. I think a large part of programming experience
(of which I don't have a vast amount) is spotting the problems and
being able to come up with top-level designs that are compatible with
further growth. Hard problems.

> For example, right now I having
> major problems with something that sounds trivial:
> getting the interpreter to set the line number
> so that a traceback can print out as it does in Python.
>
> That sounds easy, but the LR grammar I'm
> using is not well adapted to it -- NEWLINE tokens
> come after statements, instead of before them,
> where the line number is needed.

Not something I've done, but it's always struck me that
compilers/parsers that only have to deal with good code must be far
easier to right...

Regards,
Michael

Michael Hudson <mwh21@cam.ac.uk> writes:

> Not something I've done, but it's always struck me that
> compilers/parsers that only have to deal with good code must be far
> easier to right...

I even go and spell check this post, then I go and write (!) such
garbage at the end of it.

no-command-of-the-English-language-here-ly y'rs - michael

John (Max) Skaller <skaller@maxtal.com.au> wrote:
> On 11 Aug 1999 08:21:14 GMT, m.faassen@vet.uu.nl (Martijn Faassen) wrote:

[.type inference, me saying it might be hard, John saying it is doable]

I'm sure type inference can be done (at least in a limited fashion), but
it would be nice to have an intermediate dropoff point; a viperi or
viperc that would work with type annotations. This is useable already,
especially if it could be used to create fast Python extension modules.
(something you aren't aiming for right now, I gather)

Once you have that working, and people bash on it a lot, you will end up
with a system that then is reasonably well tested. Then you tack on
the type inference engine, reusing large parts of what you already
have.

If the project has usuable results at many stages, you have a bigger chance
to get the 'open source' effect going (if you're aiming for that), too.

>>Does viperc compile Python to C code?

> I don't know yet. In the first instance,
> a run time is still needed that works like existing Python,
> where type inference fails. Therefore, I still need an
> interpreter. So Viperi, the interpreter, is the first step.
[snip]
> I will try to optimise it first, before considering
> how to build the compiler, and what back ends to implement.

Ah, so the reason you don't use Python itself as the interpreter is
learning, and also as an intermediate dropoff point.

> It is possible the first back end will actually general Ocaml
> rather than C (since Viper is currently implemented in ocaml).

Hm, why Ocaml? I don't know this language, though I heard some
interesting things about it. But it begs the question why you're
not using Python itself. One reason may be because Python is too
slow to build an interpreter, but as you are aiming for a Python compiler
this can't last. :) And I'd definitely consider at least a C
backend for the compiler, because C is so common. Though Ocaml may be
okay that way too, I don't know.

[snip]
>>So you could do with Swallow's "type system" (big word for nothing there),
>>right?

> Yes. It is useful to have optional typing, to
> help make the type inference work.

Cool. :)

> I was considering:

> def f(x:int): ...

> as the syntax ( because this is fairly conventional,
> and a pure extension). However, it isn't
> backward compatible, whereas your idea is,
> so I will look at it. [The method resembles the
> 'traits' templates in C++ STL]

I did write a bit of Python that could check these Swallow type definitions
and compare if they happened to be of the same (for instance, two
functions may have the same argument types and return value type). It also
supports a kind of typedefs. This sounds too impressive for what it actually
is. :) If anyone wants a look I can dredge it up for them, just ask.

>>> It is difficult to optimise individual
>>> modules.

>>Hm, but the possibility to optimise individual modules is what attracts
>>many people to this idea.

[snip]
> I agree. However, it turns out adding extensions is often
> trivial, whereas providing compatibility is often difficult. Similarly,
> it may be more difficult to generate a function than a whole
> module, and more difficult to do that than build a whole
> program.

But Python's C interface is well known and I believe also quite stable;
or you could use something like Swig too. So if you generated a C
function it wouldn't be that hard to automatically wrap it so it'd
be useable from Python.

> In particular, building a whole program is easiest,
> since it doesn't require interfacing to python. That interface
> is non-trivial: binding to the C API, and then the bytecode
> interpreter, and then again, the result is different if you
> were using JPython.

Okay, I didn't include JPython in my argument.

> So it may be easier to just provide
> a binding at a single level, namely
> 'pure python' source code, than try to build something
> that interfaces to existing Python.

I can see where you're coming from, but I'd still seriously consider
adding at least a CPython interface early on -- the more stages in your
project that are usable, the higher the chance is your project will
bear fruit.

> In addition, Python 1.6 may have different
> internals, and so may Python 2.x. This creates
> a maintenance nightmare which may make the project
> less useful.

Why would you need access to Python internals to build a Python
extension module? You'd just need to wrap up your functions with some C
that does type checking on the arguments -- and Python's C interface
is quite stable.

I can see where full program analysis may help with type inference,
of course. But if you go by the intermediate route of manual adding of
types, it doesn't sound that hard to support some interface with Python.

Of course you need to restrict the modules that can be called by Viper
code to the set of modules supported by Viper; I'm not proposing Viper
code can call random Python modules, if you're thinking about that. That'd
make the whole project far more difficult.

> OTOH, many python 'built in C modules'
> have corresponding Pure Python sources, for example
> the string module. In that case, if the compiler works,
> there is no need for the C module.

Hm, reading this it seems you're talking about the other thing; supporting
C Python modules in Viper? I was talking about allowing people to Viper-compile
their Python modules (as long as they are Viper compliant), and use them
from Python. But as you say, you can use Pure Python modules in Viper
as well; if they restrict themselves to the Viper subset.

Regards,

Martijn

On 15 Aug 1999 23:05:29 GMT, Martijn Faassen wrote:
>John (Max) Skaller <skaller@maxtal.com.au> wrote:

>[.type inference, me saying it might be hard, John saying it is doable]

Type inference and native code compilation might be simultaneously
possible if you write Viper (or Swallow) in Pop-11, which in spite of
being a general-purpose language has manyamenities for language
programmers. Common Lisp, ML, and Prolog are already written in it, and
all compile to native code (and work interactively).

Best of all, Pop-11 is finally free.

>> It is possible the first back end will actually general Ocaml
>> rather than C (since Viper is currently implemented in ocaml).

>Hm, why Ocaml? I don't know this language, though I heard some
>interesting things about it. But it begs the question why you're
>not using Python itself. One reason may be because Python is too
>slow to build an interpreter, but as you are aiming for a Python compiler
>this can't last. :) And I'd definitely consider at least a C
>backend for the compiler, because C is so common. Though Ocaml may be
>okay that way too, I don't know.

ML does type inferance. He's probably using that just so he gets the
inference free.

>Martijn

--
-William "Billy" Tanksley

Robert Kern wrote in message <37b6f43e.1175088@news.erols.com>...
>On Sun, 15 Aug 1999 15:36:39 GMT, skaller@maxtal.com.au (John (Max)
>Skaller) wrote:
>
>[snip]
>
>>This last point is the real killer. I have both a Linux and
>>NT box. I have no problem with building C modules
>>on Linux, but I don't _have_ a compiler on the NT box that
>>will build C modules compatible with the Python implementation
>>I have. [.I have Borland C++, and gcc on the NT box,
>>but not MSC, which was used to build my NT based Python]
>
>You can use GCC 2.95 for mingw32
>(http://www.xraylith.wisc.edu/~khan/software/gnu-win32/gcc.html)
>to compile Python extensions on NT. See my page
>http://starship.python.net/crew/kernr/mingw32/Notes.html
>
>Such extensions will work with the distributed Python interpreter for
>Win32.

There is also LCC-Win32 at http://www.cs.virginia.edu/~lcc-win32/
I haven't played with it recently but I used it to teach a C course
last year and it understood windows.h and .rc files very well.

--
Phil Mayes pmayes AT olivebr DOT com
Olive Branch Software - home of Arranger
http://www.olivebr.com/

graham@sloth.math.uga.edu (Graham Matthews) writes:

> : s = ""
> : for i in range(1,10): s = s + str(i)
> :
> : Obviously i is an integer here, and s a string.
>
> Is it? Surely that depends on what "range" and "+" are bound to at
> runtime.

He said that in Viper, range is a keyword. How could you bind "+" to
something else in the example?

Regards,
Martin

graham@sloth.math.uga.edu (Graham Matthews) writes:
: > : s = ""
: > : for i in range(1,10): s = s + str(i)
: > :
: > : Obviously i is an integer here, and s a string.
: >
: > Is it? Surely that depends on what "range" and "+" are bound to at
: > runtime.
Martin von Loewis (loewis@informatik.hu-berlin.de) wrote:
: He said that in Viper, range is a keyword. How could you bind "+" to
: something else in the example?

You might have bound it in some code previous to this. If you are
planning to compile this code then you have to compile it so that it
will run in all contexts.

What I would like to know here is what is the type of range(1,10)?

graham
--

England's not the mythical land of madame george and roses
It's the home of police who kill black boys on mopeds

John Max Skaller wrote:
>
> On Wed, 11 Aug 1999 15:48:09 -0400 (EDT), "Barry A. Warsaw" <bwarsaw@cnri.reston.va.us> wrote:
>
> >At IPC7, JimH reported on some experiments he'd been doing
> ><http://www.jpython.org/jpython-talk-1.ppt> with whole program
> >analysis in the jpythonc tool. He reported some impressive results,
>
> I'm very encouraged by this.
>
>
> John Max Skaller ph:61-2-96600850
> mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
> http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA

Also, you may want to look at how the SmallEiffel compiler does it's
type inferencing... They did it well enough to get rid of virtual
function tables... There's a few papers that describe what they did and
the essence of how it works and the rather amazing perfomance numbers
(and obviously the souce code is available to give you an implementation
to look at -- written in Eiffel).

http://SmallEiffel.loria.fr/papers/papers.html
--
"Programmers are just machines that convert coffee to executable code"
-Unknown

"Drew Csillag" <drew_csillag@geocities.com>

On Mon, 16 Aug 1999 14:29:06 GMT, Andrew Csillag <andrew@starmedia.net> wrote:
>
>Also, you may want to look at how the SmallEiffel compiler does it's
>type inferencing... They did it well enough to get rid of virtual
>function tables... There's a few papers that describe what they did and
>the essence of how it works and the rather amazing perfomance numbers
>(and obviously the souce code is available to give you an implementation
>to look at -- written in Eiffel).
>
>http://SmallEiffel.loria.fr/papers/papers.html

This is well-worth reading, but the Eiffel folks were able to do their
optimizations because Eiffel is so much more static than Python -- for
example, classes can't be dynamically created in Eiffel. This is not
the case in Python, and I get the impression that John Skaller is
trying to use whole-program analysis to get around that a bit.

In that case, the Cecil papers:

http://www.cs.washington.edu/research/projects/cecil/papers

are the best place to look for ideas. Cecil is a dynamic OO language
that Craig Chambers has been using to work out techniques for wringing
speed out of dynamic languages. The only danger is that it will
inspire John to add predicate methods to Python. :)


Neel

On 16 Aug 1999 14:09:49 GMT, graham@sloth.math.uga.edu (Graham Matthews) wrote:

>graham@sloth.math.uga.edu (Graham Matthews) writes:
>: > : s = ""
>: > : for i in range(1,10): s = s + str(i)
>: > :
>: > : Obviously i is an integer here, and s a string.
>: >
>: > Is it? Surely that depends on what "range" and "+" are bound to at
>: > runtime.
>Martin von Loewis (loewis@informatik.hu-berlin.de) wrote:
>: He said that in Viper, range is a keyword. How could you bind "+" to
>: something else in the example?
>
>You might have bound it in some code previous to this.

It is possible to detect if this might be the case,
provided we exclude rebinding 'range' in an 'exec'.
And, since most people don't rebind range,
assuming it isn't is probably reasonable.

>If you are
>planning to compile this code then you have to compile it so that it
>will run in all contexts.

No, I don't. I plan to compile _whole_ programs.
The result of compiling a function 'f' in some module 'm'
could be different in different programs. In fact,
it could be different for different _calls_: there could be
two or more versions of one function, depending on
usage.

>What I would like to know here is what is the type of range(1,10)?

At present, it has type 'IntRange' which is analogous
to Python 1.5.2's type 'XRange': a dictinct type which is a sequence.

John Max Skaller ph:61-2-96600850
mailto:skaller@maxtal.com.au 10/1 Toxteth Rd
http://www.maxtal.com.au/~skaller Glebe 2037 NSW AUSTRALIA