Lisp vs Python -- Static Compilation

Question

Why can Lisp with all its dynamic features be statically compiled but Python cannot (without losing all its dynamic features)?

Chewy

.oO(answer in 10 words or less) – Estrous

you can statically compile python code with Cython (cython.org) or shedskin (code.google.com/p/shedskin), which generate C/C++ code from the python, but I think they often lose some of the dynamic features in favour of faster static types – Arabel

Answer 1

There is nothing that prevents static compilation of Python. It's a bit less efficient because Python reveals more mutable local scope, also, to retain some of the dynamic properties (e.g. eval) you need to include the compiler with the compiled program but nothing prevents that too.

That said, research shows that most Python programs, while dynamic under static analysis, are rather static and monomorphic at runtime. This means that runtime JIT compilation approaches work much better on Python programs. See unladen-swallow, PyPy, Psyco for approaches that do compile Python into machine code. But also IronPython and Jython that use a virtual machines originally intended for a static languages to compile Python into machinecode.

Ta

Answer 2

For what its worth, Python scripts are compiled into .pyc files when the are executed, see "Compiled" Python files.

You can also use a tool such as py2exe to compile a Python program into an executable.

Cringle

Not sure it is comparable. You can not run pyc files without a python interpreter. Contrarily, (some) Lisp compile to native machine code. Exes produced by py2exe have bytecode, the python interpreter and dlls embedded, but it is not machine code. – Inexorable

@joaquin: there is no hard line between compilation and interpretation. Nothing prevents one from building a processor that runs Python bytecode directly. Or from the opposite end, you can take compiled x86 machine code and interpret it in an x86 emulator. After all, code is data and data is code. – Ta

@Ants: Thanks. I think I understand your point but still, native machine code would be the more optimized form of code, the faster possible for a given condition and processor. The other possibilities you mention would be at least one step from that, and consecuently would not be as fast. Is it wrong?. Maybe conceptually there is no difference, but is it the same in practical terms? I am not a computer scientist so forgive me if I say something stupid – Inexorable

@joaquin: It's simple to convert a fetch-branch-execute interpreter loop to a compiler by just replacing bytecodes with the execute part. While this removes the fetch-branch overhead (including the expensive indirect branch), it does rather nasty things to code footprint, blowing the code cache. Data shows that for Python the loop overhead isn't that large compared to opcode execution. A good interpreter can easily be faster than a simple approach to compilation. And then there are techniques like subroutine threading, where the "bytecode" is executed directly. – Ta

In the end it doesn't matter how exactly the code is executed, as long as it's executed fast. I place my bets on specializing tracing JITs. They can beat static compilers by adapting to runtime conditions. – Ta

Ants: It's not either-or, of course. HP Labs' Dynamo project was essentially a JIT for machine code, which ran native code faster than the processor normally did, and ran highly-optimized machine code even better (since its optimizations were largely complementary to the compiler's). – Pellagra

It should be noted though that a processor is just an interpreter for machine code. The point is that Python is less 'portable', as in, it's comparatively hard to compile it towards 'any' object code, a specialized python object code had to be designed. In the case of Lisps, any assembly, C, to Java, to Haskell, to C--, to Python, it doesn't matter that much, probably only have to change the back end for that. Also, correct me if I'm wrong, but I don't think Python's grammar is context-free, which also troubles the eval-statements and syntactic analyses needed for runtime python. – Chamois

Answer 3

Actually, there isn't anything that stops you from statically compile a Python program, it's just that no-one wrote such a compiler so far (I personally find Python's runtime to be very easy compared to CL's).

You could say that the difference lies in details like "how much time was spent on actually writing compilers and does the language have a formal specification of how to write one".

Let's address those points:

1. Lisp compilers have been evolving for over 40 years now, with work starting back in 70's if not earlier (I'm not sure of my dates, too lazy too google exact ones). That creates a massive chunk of lore about how to write a compiler. OTOH, Python was nominally designed as "teaching language", and as such compilers weren't that important.
2. Lack of specification - Python doesn't have a single source specifying exact semantics of the language. Sure, you can point to PEP documents, but it still doesn't change the fact that the only real spec is the source of the main implementation, CPython. Which, nota bene, is a simple compiler of sorts (into bytecode).

As for whether it is possible - Python uses quite simple structure to deal with symbols etc., namely its dictionaries. You can treat them as symbol table of a program. You can tag the data types to recognize primitive ones and get the rest based on stored naming and internal structure. rest of the language is also quite simple. The only bit missing is actual work to implement it, and make it run correctly.

Candra

Answer 4

Python can be 'compiled', where compilation is seen as a translation from one Turing Complete language (source code) to another (object code). However in Lisp, the object is assembly, something which is theoretically possible with Python (proven) but not feasible.

The true reason however is less flattening. Lisp is in many ways a revolutionary language that pioneered in its dialects a lot of the features in programming languages we are used to today. In Lisps however they just 'follow' logically from the basics of the language. Language which are inspired by the raw expressive powers of lisps such as JavaScript, Ruby, Perl and Python are necessarily interpreted because getting those features in a language with an 'Algol-like syntax' is just hard.

Lisp gains these features from being 'homo-iconic' there is no essential difference between a lisp program, and a lisp data-structure. Lisp programs are data-structures, they are structural descriptions of a program in such an S-expression if you like, therefore a compiled lisp program effectively 'interprets itself' without the need of a lexer and all that stuff, a lisp program could just be seen as a manual input of parse tree. Which necessitates a syntax which many people find counter-intuitive to work with, therefore there were a lot of attempts to transport the raw expressive power of the paradigm to a more readable syntax, which means that it's infeasible, but not impossible, to compile it towards assembly.

Also, compiling Python to assembly would possibly be slower and larger than 'half-interpreting' it on a virtual machine, a lot of features in python depend upon a syntactic analysis.

The above though is written by a huge lisp fanboy, keep that conflict of interest in mind.

Chamois