Inline (bytecode) assembly

In a recent discussion on adding an empty set literal to Python, the conversion went as far off-base as usual, and I offhandedly suggested:

Alternatively, it might be nice if there were a way to do "inline bytecode assembly" in CPython, similar to the way you do inline assembly in many C compilers, so the answer to random's question is just "asm [('BUILD_SET', 0)]" or something similar.

You can follow the rest of the thread from there if you want. I don't really think it's worth pursuing (certainly not for this use case), but it's an interesting idea.

Here's what it would take.

Bytecode assembler

First, you need something that can assemble that inline assembly into actual bytecode. This is the easy part, but I couldn't find any existing projects that worked with Python 3.x, so I wrote one, called cpyasm. There are things that could be improved (see the TODO section in the README), but the basics are there.

If you only want to write entire functions in assembly, cpyasm already gives you everything you need. But that's not what we want, we want to be able to write most of a function in Python, dropping to assembly for a line or two in the middle.

Compiler support

The compiler works in three stages: It tokenizes the data, parses the tokens into an AST, and compiles the AST into bytecode.

The parsing is done according to a GRAMMAR file. Changing CPython's Grammar explains how to edit this file, and then all the other things you have to edit or rebuild after that. The end result is going to be a new kind of AST node, Asm, with appropriate properties.

Fortunately, we're not adding any new bytecodes to the interpreter; the whole point of inline assembly is to provide a different way to generate the existing bytecodes. But compile.c needs to be edited to transform the AST node into a sequence of bytecodes. This is where the actual "assembler" part of the inline assembler goes.

The simplest way to add an asm statement would be to make it a simple statement with one argument, which can be parsed by the existing machinery because it's just a string:

simple_stmt ::= expression_stmt

| ...

| asm_stmt

asm_stmt ::= "asm" stringliteral

However, that would mean the parser can't detect any errors in the inline assembly, or even recognize names. On the opposite end, you could make it a compound statement whose suite consists of lines of assembly code, which have their own grammar:

compound_stmt ::= if_stmt

| ...

| inline_asm_stmt

inline_asm_stmt ::= 'asm' ':' asm_suite

asm_suite ::= asm_statement NEWLINE | NEWLINE INDENT asm_statement+ DEDENT

asm_statement ::= asm_jrel_stmt | asm_jabs_stmt | asm_local_stmt | ...

asm_jrel_stmt ::= ( 'FOR_ITER' | 'JUMP_FORWARD' | ... ) asm_jrel_target

asm_jrel_target ::= asm_label | '+' integer | '-' integer | integer

… and so on

That's a whole lot more work, but it also means the parser does a lot of your work for you (all the cruft I did with regexps in cpyasm).

In between the two, you could use something like a simple statement that takes a list display instead of a string, which would make the parser parse out the list values, which would allow it to recognize identifiers and notice them as names in use, etc.

Import hook

Adding support to the compiler might be fun to do when I have a bit of free time, but it'll be a lot of work.

Also, it's unlikely to get accepted upstream. The best way to get a radically new feature accepted upstream is to package it as a module, put it on PyPI, and see how people are using it, and then go back to the core team and show them how useful it is. But you can't package a compiler modification up as a module. So, what can you do?

Instead of modifying the compiler, you can use an import hook. The core of the normal import process for source files is read the data as bytes, decode the bytes, parse the str into an AST, compile the AST into bytecode. We can write our own version of the function that does those steps and insert our own code to, regexp the source code, or transform the tree. And we can get that installed to handle all source files, or to handle source files with some new extension like .pya, or whatever we want.

The importlib docs show all the details on how to do this, although there's really no good overview there, or anywhere else. You can see an example in a module called emptyset, which I think does a good job with the source and AST modification code, but probably a terrible job with the actually hooking part.

But notice that, while we can do whatever we want to the source before parsing it, and do whatever we want to the tree before compiling it, we can't do much to influence how the parsing itself happens. So, our new syntax has to be valid Python syntax, or at least something we can transform into valid Python syntax. And neither "asm:" followed by a suite full of statements like "CALL_FUNCTION 1,2" nor just "asm" followed by a string are valid syntax.

Fortunately, there's a simple trick that will work here easily: "asm(foo, bar, baz)" is a function call; "CALL_FUNCTION(1,2)" is a function call; etc. So, we either make that our syntax (which kind of sucks; if you wanted your blocks to end with ")" and each like to end in ",", you wouldn't be using Python, you'd be using one of those languages that ends blocks with "}" and lines with ";"…), or we transform our source to convert our chosen syntax into the parseable syntax—which I think is doable with regexps (since there are no recursive asm statements, etc.) even for the complex-statement version, and almost certainly for the simple-statement versions.

So now, we've got a parse tree that has a Call node where the func is a Name node whose id is 'asm', and whose args list is either a list of Call nodes, or a single Str node.

The way to handle this is to write an ast.NodeTransformer that has visit_Call and, if appropriate, visit_Str methods. The example in emptyset is pretty self-explanatory, and the docs in the ast module do a great job on this.

But… what do we transform these nodes into? We could try to work out the appropriate AST node for each bytecode, but this could get pretty tricky. So I think what we'd want to do instead is to assemble the bytecode here, then put some kind of marker into the node that will compile to some known, easily-findable bytecode of the right length—maybe just a sequence of NOPs?—and stash the assembled bytecode. Then, after we've gotten the bytecode back, we'll need to munge it. First, we may need to fixup some references in our code—e.g., the thing we thought was going to be local #1 is actually local #2, we need to change our LOAD_FAST 1 to a LOAD_FAST 2. The easy way to do this is to just re-assemble the source, now that we have all the info we need (the starting offset, the co_varnames, etc.). Then we just replace the sequence of NOPs with the assembled code, update the co_names etc. with any new names we've added, fix up the co_lnotab, and build a new code object out of the result. This isn't completely trivial, but the cpyasm module shows how all of it works.

MacroPy

There's one last option to consider here: Haoyi Lin's amazing MacroPy library helps you build macros that intercept and transform ASTs without having to do all the boilerplate stuff yourself. And it has support for all kinds of cool things that are a pain to build, like making it possible to generate .pyc files that are pre-transformed so you can distribute your project without requiring users to have MacroPy (or the inline asm module).

I don't think MacroPy has hooks for source and bytecode transformations, and, it has only provisional Python 3.x support, but contributing to MacroPy might be better than duplicating all of the work already done. (And of course this would also mean you get support for the earlier versions of import hooks that are needed for each of 2.7, 3.2, and 3.3, instead of just 3.4…)

Conclusion

This post is a lot more pie-in-the-sky than most of my others, mainly because I haven't actually put the work into building the thing I'm discussing. If there's enough interest, and I have enough free time, to make it worth going farther, I'll write a new post.

It's been more than a decade since Typical Programmer Greg Jorgensen taught the word about Abject-Oriented Programming.

Much of what he said still applies, but other things have changed. Languages in the Abject-Oriented space have been borrowing ideas from another paradigm entirely—and then everyone realized that languages like Python, Ruby, and JavaScript had been doing it for years and just hadn't noticed (because these languages do not require you to declare what you're doing, or even to know what you're doing). Meanwhile, new hybrid languages borrow freely from both paradigms.

This other paradigm—which is actually older, but was largely constrained to university basements until recent years—is called Functional Addiction.

A Functional Addict is someone who regularly gets higher-order—sometimes they may even exhibit dependent types—but still manages to retain a job.

Retaining a job is of course the goal of all programming. This is why some of these new hybrid languages, like Rust, check all borrowing, from both paradigms, so extensively that you can make regular progress for months without ever successfully compiling your code, and your managers will appreciate that progress. After all, once it does compile, it will definitely work.

Closures

It's long been known that Closures are dual to Encapsulation.

As Abject-Oriented Programming explained, Encapsulation involves making all of your variables public, and ideally global, to let the rest of the code decide what should and shouldn't be private.

Closures, by contrast, are a way of referring to variables from outer scopes. And there is no scope more outer than global.

Immutability

One of the reasons Functional Addiction has become popular in recent years is that to truly take advantage of multi-core systems, you need immutable data, sometimes also called persistent data.

Instead of mutating a function to fix a bug, you should always make a new copy of that function. For example:

function getCustName(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

When you discover that you actually wanted fields 2 and 3 rather than 1 and 2, it might be tempting to mutate the state of this function. But doing so is dangerous. The right answer is to make a copy, and then try to remember to use the copy instead of the original:

function getCustName(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

function getCustName2(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[2] + ' ' + custRec[3];
    return fullname;
}

This means anyone still using the original function can continue to reference the old code, but as soon as it's no longer needed, it will be automatically garbage collected. (Automatic garbage collection isn't free, but it can be outsourced cheaply.)

Higher-Order Functions

In traditional Abject-Oriented Programming, you are required to give each function a name. But over time, the name of the function may drift away from what it actually does, making it as misleading as comments. Experience has shown that people will only keep once copy of their information up to date, and the CHANGES.TXT file is the right place for that.

Higher-Order Functions can solve this problem:

function []Functions = [
    lambda(custID) {
        custRec = readFromDB("customer", custID);
        fullname = custRec[1] + ' ' + custRec[2];
        return fullname;
    },
    lambda(custID) {
        custRec = readFromDB("customer", custID);
        fullname = custRec[2] + ' ' + custRec[3];
        return fullname;
    },
]

Now you can refer to this functions by order, so there's no need for names.

Parametric Polymorphism

Traditional languages offer Abject-Oriented Polymorphism and Ad-Hoc Polymorphism (also known as Overloading), but better languages also offer Parametric Polymorphism.

The key to Parametric Polymorphism is that the type of the output can be determined from the type of the inputs via Algebra. For example:

function getCustData(custId, x)
{
    if (x == int(x)) {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return int(fullname);
    } else if (x.real == 0) {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return double(fullname);
    } else {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return complex(fullname);
    }
}

Notice that we've called the variable x. This is how you know you're using Algebraic Data Types. The names y, z, and sometimes w are also Algebraic.

Type Inference

Languages that enable Functional Addiction often feature Type Inference. This means that the compiler can infer your typing without you having to be explicit:

function getCustName(custID)
{
    // WARNING: Make sure the DB is locked here or
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

We didn't specify what will happen if the DB is not locked. And that's fine, because the compiler will figure it out and insert code that corrupts the data, without us needing to tell it to!

By contrast, most Abject-Oriented languages are either nominally typed—meaning that you give names to all of your types instead of meanings—or dynamically typed—meaning that your variables are all unique individuals that can accomplish anything if they try.

Memoization

Memoization means caching the results of a function call:

function getCustName(custID)
{
    if (custID == 3) { return "John Smith"; }
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

Non-Strictness

Non-Strictness is often confused with Laziness, but in fact Laziness is just one kind of Non-Strictness. Here's an example that compares two different forms of Non-Strictness:

/****************************************
*
* TO DO:
*
* get tax rate for the customer state
* eventually from some table
*
****************************************/
// function lazyTaxRate(custId) {}

function callByNameTextRate(custId)
{
    /****************************************
    *
    * TO DO:
    *
    * get tax rate for the customer state
    * eventually from some table
    *
    ****************************************/
}

Both are Non-Strict, but the second one forces the compiler to actually compile the function just so we can Call it By Name. This causes code bloat. The Lazy version will be smaller and faster. Plus, Lazy programming allows us to create infinite recursion without making the program hang:

/****************************************
*
* TO DO:
*
* get tax rate for the customer state
* eventually from some table
*
****************************************/
// function lazyTaxRateRecursive(custId) { lazyTaxRateRecursive(custId); }

Laziness is often combined with Memoization:

function getCustName(custID)
{
    // if (custID == 3) { return "John Smith"; }
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

Outside the world of Functional Addicts, this same technique is often called Test-Driven Development. If enough tests can be embedded in the code to achieve 100% coverage, or at least a decent amount, your code is guaranteed to be safe. But because the tests are not compiled and executed in the normal run, or indeed ever, they don't affect performance or correctness.

Conclusion

Many people claim that the days of Abject-Oriented Programming are over. But this is pure hype. Functional Addiction and Abject Orientation are not actually at odds with each other, but instead complement each other.

Bytecode assembler

Compiler support

Import hook

MacroPy

Conclusion

Add a comment

Stupid Python Ideas

Closures

Immutability

Higher-Order Functions

Parametric Polymorphism

Type Inference

Memoization

Non-Strictness

Conclusion

View comments