Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #40170 > unrolled thread

Why is it impossible to create a compiler than can compile Python to machinecode like C?

Back to article view | Back to comp.lang.python

Contents

  Why is it impossible to create a compiler than can compile Python to machinecode like C? kramer65 <kramerh@gmail.com> - 2013-02-28 12:25 -0800
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Matty Sarro <msarro@gmail.com> - 2013-02-28 15:50 -0500
      Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-01 02:55 +0000
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Stefan Behnel <stefan_ml@behnel.de> - 2013-02-28 22:03 +0100
      Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-01 03:47 +0000
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? alex23 <wuwei23@gmail.com> - 2013-02-28 20:31 -0800
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Stefan Behnel <stefan_ml@behnel.de> - 2013-03-01 08:48 +0100
          Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-02 01:49 +0000
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Chris Angelico <rosuav@gmail.com> - 2013-03-01 08:10 +1100
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Stefan Behnel <stefan_ml@behnel.de> - 2013-02-28 22:17 +0100
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Dave Angel <davea@davea.name> - 2013-02-28 16:18 -0500
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Modulok <modulok@gmail.com> - 2013-02-28 14:19 -0700
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Jonas Geiregat <jonas@geiregat.org> - 2013-02-28 22:33 +0100
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Nobody <nobody@nowhere.com> - 2013-02-28 22:01 +0000
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Terry Reedy <tjreedy@udel.edu> - 2013-02-28 17:06 -0500
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2013-02-28 21:09 -0500
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-01 04:27 +0000
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? alex23 <wuwei23@gmail.com> - 2013-02-28 20:38 -0800
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? 88888 Dihedral <dihedral88888@googlemail.com> - 2013-02-28 22:21 -0800
    Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Grant Edwards <invalid@invalid.invalid> - 2013-03-04 16:36 +0000
      Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? CM <cmpython@gmail.com> - 2013-03-04 14:55 -0800
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-04 15:12 -0800
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Terry Reedy <tjreedy@udel.edu> - 2013-03-04 19:31 -0500
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Chris Angelico <rosuav@gmail.com> - 2013-03-05 11:33 +1100
        Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Benjamin Kaplan <benjamin.kaplan@case.edu> - 2013-03-04 16:27 -0800
      Re: Why is it impossible to create a compiler than can compile Python to machinecode like C? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-05 01:35 +0000

Page 2 of 2 — ← Prev page 1 [2]

#40485

> The main issue is that python has dynamic typing.  The type of object
> that is referenced by a particular name can vary, and there's no way
> (in general) to know at compile time what the type of object "foo" is.
>
> That makes generating object code to manipulate "foo" very difficult.

Could you help me understand this better?  For example, if you
have this line in the Python program:

foo = 'some text'
bar = {'apple':'fruit'}

If the interpreter can determine at runtime that foo is a string
and bar is a dict, why can't the compiler figure that out at
compile time?  Or is the problem that if later in the program
you have this line:

foo = 12

now foo is referring to an integer object, not a string, and
compilers can't have two names referring to two different
types of objects?  Something like that?

I in no way doubt you that this is not possible, I just don't
understand enough about how compiling works to yet "get"
why dynamic typing is a problem for compilers.

Thanks.

[toc] | [prev] | [next] | [standalone]

#40486

On Tuesday, March 5, 2013 6:55:06 AM UTC+8, CM wrote:
> > The main issue is that python has dynamic typing.  The type of object
> 
> > that is referenced by a particular name can vary, and there's no way
> 
> > (in general) to know at compile time what the type of object "foo" is.
> 
> >
> 
> > That makes generating object code to manipulate "foo" very difficult.
> 
> 
> 
> Could you help me understand this better?  For example, if you
> 
> have this line in the Python program:
> 
> 
> 
> foo = 'some text'
> 
> bar = {'apple':'fruit'}
> 
> 
> 
> If the interpreter can determine at runtime that foo is a string
> 
> and bar is a dict, why can't the compiler figure that out at
> 
> compile time?  Or is the problem that if later in the program
> 
> you have this line:
> 
> 
> 
> foo = 12
> 
> 
> 
> now foo is referring to an integer object, not a string, and
> 
> compilers can't have two names referring to two different
> 
> types of objects?  Something like that?
> 
> 
> 
> I in no way doubt you that this is not possible, I just don't
> 
> understand enough about how compiling works to yet "get"
> 
> why dynamic typing is a problem for compilers.
> 
> 
> 
> Thanks.

The dynamic type part is normally in the higher level components of 
objects and functions and generators.

Of course if one can be sure of the types of variables used 
in some functions then that is the cython way to speed up pure OOP python
programs in executions.

[toc] | [prev] | [next] | [standalone]

#40488

On 3/4/2013 5:55 PM, CM wrote:

> Could you help me understand this better?  For example, if you
> have this line in the Python program:
>
> foo = 'some text'
> bar = {'apple':'fruit'}
>
> If the interpreter can determine at runtime that foo is a string
> and bar is a dict, why can't the compiler figure that out at
> compile time?  Or is the problem that if later in the program
> you have this line:
>
> foo = 12
>
> now foo is referring to an integer object, not a string, and
> compilers can't have two names referring to two different
> types of objects?

I believe you mean one name referring to multiple types.

> Something like that?

Something like that. In python, objects are strongly typed, names do not 
have types. Or if you prefer, names are typed according to their current 
binding, which can freely change. As for why this can be an advantage, 
consider this simple function.

def min2(a, b):
   if a <= b:
     return a
   else:
     return b

When the def statement is executed, the names 'a' and 'b' have no 
binding and therefore no type, not even a temporary type.

In a statically typed language, either you or the compiler must rewrite 
that function for every pair of types that are ever input to min2. If 
the compiler does it, it either has to analyze an entire program, or it 
have to compile variations on the fly, as needed. The latter is what the 
psycho module, and, I believe, the pypy jit compiler does.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#40489

On Tue, Mar 5, 2013 at 9:55 AM, CM <cmpython@gmail.com> wrote:
>
>> The main issue is that python has dynamic typing.  The type of object
>> that is referenced by a particular name can vary, and there's no way
>> (in general) to know at compile time what the type of object "foo" is.
>>
>> That makes generating object code to manipulate "foo" very difficult.
>
> Could you help me understand this better?  For example, if you
> have this line in the Python program:
>
> foo = 'some text'
> bar = {'apple':'fruit'}
>
> If the interpreter can determine at runtime that foo is a string
> and bar is a dict, why can't the compiler figure that out at
> compile time?  Or is the problem that if later in the program
> you have this line:
>
> foo = 12
>
> now foo is referring to an integer object, not a string, and
> compilers can't have two names referring to two different
> types of objects?  Something like that?
>
> I in no way doubt you that this is not possible, I just don't
> understand enough about how compiling works to yet "get"
> why dynamic typing is a problem for compilers.

Python doesn't have "variables" with "values"; it has names, which may
(or may not) point to objects. Dynamic typing just means that one name
is allowed to point to multiple different types of object at different
times.

The problem with dynamic typing is more one of polymorphism. Take this
expression as an example:

foo += bar;

In C, the compiler knows the data types of the two variables, and can
compile that to the appropriate code. If they're both integers,
that'll possibly become a single machine instruction that adds two
registers and stores the result back.

In C++, foo could be a custom class with an operator+= function. The
compiler will know, however, what function to call; unless it's a
virtual function, in which case there's a run-time check to figure out
what subclass foo is of, and then the function is called dynamically.

In Python, *everything* is a subclass of PyObject, and every function
call is virtual. That += operation is backed by the __iadd__ function,
defined by PyObject and possibly overridden by whatever type foo is.
So, at run time, the exact function is looked up.

C++ is most definitely a compiled language, at least in most
implementations I've seen. But it has the exact same issue as Python
has: true dynamism requires run-time lookups. That's really what
you're seeing here; it's nothing to do with any sort of "compiled" vs
"interpreted" dichotomy, but with "compile time" vs "run time"
lookups. In C, everything can be done at compile time; in Python, most
things are done at run time.

It's mainly a matter of degree. A more dynamic language needs to do
more work at run time.

ChrisA

[toc] | [prev] | [next] | [standalone]

#40490

[Multipart message — attachments visible in raw view] — view raw

On Mar 4, 2013 3:02 PM, "CM" <cmpython@gmail.com> wrote:
>
>
> > The main issue is that python has dynamic typing.  The type of object
> > that is referenced by a particular name can vary, and there's no way
> > (in general) to know at compile time what the type of object "foo" is.
> >
> > That makes generating object code to manipulate "foo" very difficult.
>
> Could you help me understand this better?  For example, if you
> have this line in the Python program:
>
> foo = 'some text'
> bar = {'apple':'fruit'}
>
> If the interpreter can determine at runtime that foo is a string
> and bar is a dict, why can't the compiler figure that out at
> compile time?  Or is the problem that if later in the program
> you have this line:
>
> foo = 12
>
> now foo is referring to an integer object, not a string, and
> compilers can't have two names referring to two different
> types of objects?  Something like that?
>
> I in no way doubt you that this is not possible, I just don't
> understand enough about how compiling works to yet "get"
> why dynamic typing is a problem for compilers.
>
> Thanks.
> --
> http://mail.python.org/mailman/listinfo/python-list

In the case of literals, the compiler can figure out type information (and
I believe it does do some constant folding). But as soon as you let
something else get in between you and the constant, you lose all guarantees.

import random

if random.random() <0.5 :
    spam = 3
else:
    spam = "hello world"

Then you get into monkey patching and dealing with types that may not be
defined at compile time. The only way a python compiler could convert that
to x86 assembly is if generated code that would look up the type
information at runtime. You'd basically be outputting a python interpreter.

[toc] | [prev] | [next] | [standalone]

#40491

On Mon, 04 Mar 2013 16:36:36 +0000, Grant Edwards wrote:

> On 2013-02-28, kramer65 <kramerh@gmail.com> wrote:
> 
>> I'm using Python for a while now and I love it. There is just one thing
>> I cannot understand. There are compilers for languages like C and C++.
>> why is it impossible to create a compiler that can compile Python code
>> to machinecode?
> 
> The main issue is that python has dynamic typing.  The type of object
> that is referenced by a particular name can vary, and there's no way (in
> general) to know at compile time what the type of object "foo" is.
> 
> That makes generating object code to manipulate "foo" very difficult.

That's only a limitation with a static compiler that tries to generate 
fast machine code at compile time. A JIT compiler can generate fast 
machine code at runtime. The idea is that the time you save by running 
more optimized code is greater than the time it costs to generate that 
code each time you run. If not, then you just run the normal byte-code 
you would have run, and you've lost very little.

This has been a very successful approach. Psyco worked very well, and 
it's successor PyPy seems to work even better. PyPy, on average, runs 
about 5-6 times faster than CPython, and for some tasks about 50 times 
faster. That makes it broadly speaking as fast as Java and approaching C, 
and even in some circumstances even beat static C compilers. (Admittedly 
only under very restrictive circumstances.)

The downside is that JIT compilers need a lot of memory. To oversimplify, 
you might take source code like this:

x = a + b

A static compiler knows what types a and b are, and can turn it into a 
single fairly compact piece of machine code. Using my own crappy invented 
machine code notation:

ADD a, b
STORE x


A JIT compiler has to generate a runtime check and one or more fast 
branches, plus a fallback:


CASE (a and b are both ints):
    ADD a, b
    STORE x
CASE (a and b are both strings):
    COPY a, x
    CONCATENATE b, x
OTHERWISE:
    execute byte code to add two arbitrary objects


The above is probably nothing like the way PyPy actually works. Anyone 
interested in how PyPy really works should spend some time reading their 
website and blog.

http://pypy.org/


I can especially recommend this to give you a flavour for just how 
complicated this sort of thing can become:

http://morepypy.blogspot.com.au/2011/01/loop-invariant-code-motion.html



-- 
Steven

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web