Code is Data – A Python to Scheme Compiler for a Subset of Python

The night before a 5 minute (!) talk on easily capturing the modern approach to program transformation in Scheme, I spent a half hour or so writing a couple dozen lines of Scheme to compile the subset of Python used in the first few Python programs of the introductory programming course CSC 108 to Scheme.

All the code for the compiler is here, in fact the entire semantic analysis and code generation program (i.e. everything after the syntactic parsing phase) is displayed in The Compiler (and a Compiler Framework) – take a quick look now! The reaction from one student taking the traditional Compilers and Interpreters course was:

“I loved how you took a Python program that converted Python into S-Expressions, then were able to run that same program in Scheme. That kind of stuff is never even considered in [any] course in this school.”

Now for the details read on.

1 The Subset of Python

This was enough for a serious (but still 5 minute) demonstration.

2 Syntactic Analysis – Parsing

Parsing is a necessary but relatively uninteresting step in modern code analysis and transformation, because any reasonable parser produces a good enough representative syntax tree to work with. Modern computers are fast enough, with orders of magnitude more memory than source code size, that if different forms of the tree are useful one simply post-processes the initial tree.

So a simple Python program (py2sexp.py – about a page long) suffices, calling Python’s parser to read python source code text and produce a tree object, then traversing the tree writing it out in Scheme’s literal notation for tree-structured data (S-Expressions). The details of this are not important for the rest of the discussion, nor is diving into Python’s parser to understand the form of the trees it produces – instead it’s simpler to examine the output when run on the sample programs.

3 Python Code Trees

I studied this (and the results for the first and second program) to understand how Python’s native parser represents Python code. For example,

4 Scheme Code to Produce

5 The Compiler Rules

Most of the rules for the other types of Python statements used in the three sample programs are as easy or easier. The two more elaborate ones are not much harder, and the difficulty is in understanding the meaning of compiling the statement from Python to Scheme, not in writing it down. Scheme makes the coding part easy if you know exactly what the application is supposed to do (and if you don’t, then it is hard to code in any language).

Unfortunately, many programmers don’t have a proper specification (were not given one by the application designers, or did not make one if also in charge of design), and instead work backwards writing a program that ends up implicitly (but quite obscurely when read as such) being the only precise specification. And that “specification” contains any unintended behaviour of the code.

Can you write a better specification?

It has to be one that someone who doesn’t know what compiling Python to Scheme means (the computer doesn’t) can be shown to follow blindly (the computer does) and get the correct result.

6 The Compiler (and a Compiler Framework)

Making the rules run is straightforward in Scheme, building on a common pattern matching library and making a function rewrite that captures the idea of “do something everywhere in some structured data until nothing changes”.

The Stratego language was built around variations of this idea (called "Term Rewriting"). Not surprisingly, Stratego is not used much because it has few libraries for the breadth of tasks one wants to accomplish in most modern applications, especially when best programmed in other styles.

One should not make new languages: instead make a language expressive enough that more concepts can be written in the language and put into a library to be used exactly where desired.

7 Do It!