Sing, goddess, the rage of George and the ImportError,
and its devastation, which put pains thousandfold upon his programs,
hurled in their multitudes to the house of Hades strong ideas
of systems, but gave their code to be the delicate feasting
of dogs, of all birds, and the will of Guido was accomplished
since that time when first there stood in division of conflict
Brett Cannon’s son the lord of modules: the brilliant import keyword. . .
Backstory Before Things Get Weird
This post is about how an ImportError lead me to a very strange place.
I was writing a simple Python program. It was one of my first attempts at Python 3.
I tried to import some code and got an ImportError. Normally I solve ImportError's by shuffling files around until the error goes away. But this time none of my shuffling solved the problem. So I found myself actually reading the official documentation for the Python import system. Somehow I'd spent over five years writing Python code professionally without ever reading more than snippets of those particular docs.
What I learned there changed me.
Yes, I answered my simple question, which had something to do with when I should use .'s in an import:
# most of the time, don't use dots at all: from spam import eggs # If Python has trouble finding spam and spam.py is in the same directory: # (i.e. "package" as the code doing the import): from .spam import eggs # when spam.py is in the *enclosing* package, i.e. one level up: from ..spam import eggs # ImportError! At least in Python 3, you can only use the dots with # the `from a import b` syntax: import .spam
But more importantly I realized that this whole time I had never really understood what the word module means in Python.
According to the official Python tutorial, a "module" is a file containing Python definitions and statements.
In other words, spam.py is a module.
But it's not quite that simple. In my running Python program, if I import requests, then what is type(requests)?
It's module.
That means module is a type of object in a running Python program. And requests in my running program is derived from requests.py, but it's not the same thing.
So what is the module class in Python and how is babby module formed?
Modules and the Python Import System
Modules are created automatically in Python when you import. It turns out that the import keyword in Python is syntactic sugar for a somewhat more complicated process. When you import requests, Python actually does two things:
1) Calls an internal function: __import__('requests') to create, load, and initialize the requests module object
2) Binds the local variable requests to that module
And how exactly does __import__() create, load, and initialize a module?
Well, it's complicated. I'm not going to go into full detail, but there's a great video where Brett Cannon, the main maintainer of the Python import system, painstakingly walks through the whole shebang.
But in a nutshell, importing in Python has 5 steps:
1. See if the module has already been imported
Python maintains a cache of modules that have already been imported. The cache is a dictionary held at sys.modules.
If you try to import requests, __import__ will first check if there's a module in sys.modules named "requests". If there is, Python just gives you the module object in the cache and does not do any more work.
If the module isn't cached (usually because it hasn't been import yet, but also maybe because someone did something nefarious...) then:
2. Find the source code using sys.path
sys.path is a list in every running Python program that tells the interpreter where it should look for modules when it's asked to import them. Here's an excerpt from my current sys.path:
# the directory our code is running in: '', # where my Python executable lives: '/Users/rogueleaderr/miniconda3/lib/python3.5', # the place where `pip install` puts stuff: '/Users/rogueleaderr/miniconda3/lib/python3.5/site-packages'
When I import requests Python goes and looks in those directories for requests.py. If it can't find it, I'm in for an ImportError. I'd estimate that the large majority of real life ImportError's happen because the source code you're trying to import isn't in a directory that's on sys.path. Move your module or add the directory to sys.path and you'll have a better day.
In Python 3, you can do some pretty crazy stuff to tell Python to look in esoteric places for code. But that's a topic for another day!
3. Make a Module object
Python has a builtin type called ModuleType. Once __import__ has found your source code, it'll create a new ModuleType instance and attach your module.py's source code to it.
Then, the exciting part:
4. Execute the module source code!
__import__ will create a new namespace, i.e. scope, i.e. the __dict__ attribute attached to most Python objects. And then it will actually exec your code inside of that namespace.
Any variables or functions that get defined during that execution are captured in that namespace. And the namespace is attached to the newly created module, which is itself then returned into the importing scope.
5. Cache the module inside sys.modules
If we try to import requests again, we'll get the same module object back. Steps 2-5 will not be repeated.
Okay! This is a pretty cool system. It lets us write many pretty Python programs.
But, if we're feeling demented, it also lets us write some pretty dang awful Python programs.
Where it gets weird
I learned how to fix my immediate import problem. That wasn't enough.
With these new import powers in hand, I immediately starting thinking about how I could use them for evil, rather than good. Because, as we know:
(c. Five Finger Tees)
So far, the worst idea I've had for how to misuse the Python import system is to implement a mergesort algorithm using just the import keyword. At first I didn't know if it was possible. But, spoiler alert, it is!
It doesn't actually take much code. It just takes the stubbornness to figure out how to subvert a lot of very well-intentioned, normally helpful machinery in the import system.
We can do this. Here's how:
Remember that when we import a module, Python executes all the source code.
So imagine I start up Python and define a function:
>>> def say_beep(): >>> print("beep!.........beep!") >>> say_beep()
This will print out some beeps.
Now imagine instead I write the same lines of code as above into a file called say_beep.py. Then I open my interpreter and run
>>> import say_beep.py
What happens? The exact same thing: Python prints out some beeps.
If I create a module that contains the same source code as the body of a function then importing the module will produce the same result as calling the function.
Well, what if I need to return something from my function body? Simple:
# make_beeper.py beeper = lambda x: print("say beep") # main.py from make_beeper import beeper beeper()
Anything that gets defined in the module is available in the module's namespace after it's imported. So from a import b is structurally the same as b = f(), if I structure my module correctly.
Okay, what about passing arguments? Well, that gets a bit harder. The trick is that Python source code is just a long string, so we can modify the source of a module before we import it:
# with_args.py a = None b = None result = a + b # main.py src = "" with open("with_args.py") as f: for line in f: src += line a = "10" b = "21" src = src.replace("a = None", f"a = {a}") src = src.replace("b = None", f"b = {b}") with open("with_args.py", "w") as f: f.write(src) from with_args import result print(result) # it's 31!
Now this certainly isn't pretty. But where we're going, nothing is pretty. Buckle up!
How to mergesort
Okay...how can we apply these ideas to implement mergesort?
First, let's quickly review what mergesort is: it's a recursive sorting algorithm with n log n worst-case computational complexity (meaning it's pretty darn good, especially compared to bad sorting algorithms like bubble sort that have n^2 complexity.)
It works by taking a list, splitting it in half, and then splitting the halves in half until we're left with individual elements.
Then we merge adjacent elements by interleaving them in sorted order. Take a look at this diagram:
Or read the Wikipedia article for more details.
Some rules
No built in sorting functionality. Python's built in sort uses a derivative of mergesort so just putting result = sorted(lst) into a module and importing it isn't very sporting.
No user-defined functions at all.
All the source code has to live inside one module file, which we will fittingly call madness.py
The code
Well, here's the code: (Walk-through below, if you don't feel like reading 100 lines of bizarre Python)
""" # This is the algorithm we'll use: import sys import re import inspect import os import importlib import time input_list = [] sublist = input_list is_leaf = len(sublist) < 2 if is_leaf: sorted_sublist = sublist else: split_point = len(sublist) // 2 left_portion = sublist[:split_point] right_portion = sublist[split_point:] # get a reference to the code we're currently running current_module = sys.modules[__name__] # get its source code using stdlib's `inspect` library module_source = inspect.getsource(current_module) # "pass an argument" by modifying the module's source new_list_slug = 'input_list = ' + str(left_portion) adjusted_source = re.sub(r'^input_list = \[.*\]', new_list_slug, module_source, flags=re.MULTILINE) # make a new module from the modified source left_path = "left.py" with open(left_path, "w") as f: f.write(adjusted_source) # invalidate caches; force Python to do the full import again importlib.invalidate_caches() if "left" in sys.modules: del sys.modules['left'] # "call" the function to "return" a sorted sublist from left import sorted_sublist as left_sorted # clean up by deleting the new module if os.path.isfile(left_path): os.remove(left_path) new_list_slug = 'input_list = ' + str(right_portion) adjusted_source = re.sub(r'^input_list = \[.*\]', new_list_slug, module_source, flags=re.MULTILINE) right_path = "right.py" with open(right_path, "w") as f: f.write(adjusted_source) importlib.invalidate_caches() if "right" in sys.modules: del sys.modules['right'] from right import sorted_sublist as right_sorted if os.path.isfile(right_path): os.remove(right_path) # merge merged_list = [] while (left_sorted or right_sorted): if not left_sorted: bigger = right_sorted.pop() elif not right_sorted: bigger = left_sorted.pop() elif left_sorted[-1] >= right_sorted[-1]: bigger = left_sorted.pop() else: bigger = right_sorted.pop() merged_list.append(bigger) # there's probably a better way to do this that doesn't # require .reverse(), but appending to the head of a # list is expensive in Python merged_list.reverse() sorted_sublist = merged_list # not entirely sure why we need this line, but things # don't work without it! sys.modules[__name__].sorted_sublist = sorted_sublist """ import random import os import time random.seed(1001) list_to_sort = [int(1000*random.random()) for i in range(100)] print("unsorted: {}".format(list_to_sort)) mergesort = __doc__ adjusted_source = mergesort.replace('input_list = []', 'input_list = {}'.format(list_to_sort)) with open("merge_sort.py", "w") as f: f.write(adjusted_source) from merge_sort import sorted_sublist as sorted_list os.remove("merge_sort.py") finished_time = time.time() print("original sorted: {}".format(sorted(list_to_sort))) print("import sorted: {}".format(sorted_list)) assert sorted_list == sorted(list_to_sort)
That's all we need.
Breaking it down
Madness itself
The body of madness.py is compact. All it does is generate a random list of numbers, grab our template implementation of merge sort from it's own docstring (how's that for self-documenting code?), jam in our random list, and kick off the algorithm by running
from merge_sort import sorted_sublist as sorted_list
The mergesort implementation
This is the fun part.
First, here is a "normal" implementation of merge_sort as a function:
def merge_sort(input_list): if len(input_list) < 2: # it's a leaf return input_list else: # split split_point = len(input_list) // 2 left_portion, right_portion = input_list[:split_point], input_list[split_point:] # recursion left_sorted = merge_sort(left_portion) right_sorted = merge_sort(right_portion) # merge merged_list = [] while left_sorted or right_sorted: if not left_sorted: bigger = right_sorted.pop() elif not right_sorted: bigger = left_sorted.pop() elif left_sorted[-1] >= right_sorted[-1]: bigger = left_sorted.pop() else: bigger = right_sorted.pop() merged_list.append(bigger) merged_list.reverse() return merged_list
It has three phases:
Split the list in half
Call merge_sort recursively until the list is split down to individual elements
Merge the sublists we're working on at this stage into a single sorted sublist by interleaving the elements in sorted order
But since our rule says that we can't use functions, we need to replace this recursive function with import.
That means replacing this:
left_sorted = merge_sort(left_portion)
With this:
# get a reference to the code we're currently running current_module = sys.modules[__name__] # get it's source code using stdlib's `inspect` library module_source = inspect.getsource(current_module) # "pass an argument" by modifying the module's source new_list_slug = 'input_list = ' + str(left_portion) adjusted_source = re.sub(r'^input_list = \[.*\]', new_list_slug, module_source, flags=re.MULTILINE) # make a new module from the modified source left_path = "left.py" with open(left_path, "w") as f: f.write(adjusted_source) # invalidate caches importlib.invalidate_caches() if "left" in sys.modules: del sys.modules['left'] # "call" the function to "return" a sorted sublist from left import sorted_sublist as left_sorted # clean up by deleting the new module if os.path.isfile(left_path): os.remove(left_path) # not entirely sure why we need this line, but things # don't work without it! Might be to keep the sorted sublist # alive once this import goes out of scope? sys.modules[__name__].sorted_sublist = sorted_sublist
And that's really it.
We just use the tools we learned about to simulate calling functions with arguments and returning values. And we add a few lines to trick Python into not caching modules and instead doing the full import process when we import a module with the same name as one that's already been imported. (If our merge sort execution tree has multiple levels, we're going to have a lot of different left.py's).
And that's how you abuse the Python import system to implement mergesort.
Many paths to the top of the mountain, but the view is a singleton.
It's pretty mindblowing (to me at least) that this approach works at all. But on the other hand, why shouldn't it?
There's a pretty neat idea in computer science is the Church-Turing thesis. It states that any effectively computable function can be computed by a universal Turing machine. The thesis is usually trotted out to explain why there's nothing you can compute with a universal Turing machine that you can't compute using lambda calculus, and therefore there's no program you can write in C that you can't, in principle, write in Lisp.
But here's a corollary: since you can, if you really want to, implement a Turing tape by writing files to the file system one bit at a time and importing the results, you can use the Python import system to simulate a Turing machine. That implies that, in principle, any computation that can be performed by a digital computer can be performed (assuming infinite space, time, and patience) using the Python import system.
The only real question is how annoying a computation will be to implement, and in this case Python's extreme runtime dynamism makes this particular implementation surprisingly easy.
The Python community spends a lot of time advocating for good methodology and "idiomatic" coding styles. They have a good reason: if you're writing software that's intended to be used, some methods are almost always better than their alternatives.
But if you're writing programs to learn, sometimes it's helpful to remember that there are many different models of computation under the sun. And especially in the era when "deep learning" (i.e. graph-structured computations that simulate differentiable functions) is really starting to shine, it's extra important to remember that sometimes taking a completely different (and even wildly "inefficient") approach to a computational problem can lead to startling success.
It's also nice to remember that Python itself started out as (and in a sense still is!) a ridiculously inefficient and roundabout way to execute C code.
Abstractions really matter. In the words of Alfred North Whitehead,
Civilization advances by extending the number of important operations which we can perform without thinking about them
My "import sort" is certainly not a useful abstraction. But I hope that learning about it will lead you to some good ones!
Note Bene
In case it's not obvious, you should never actually use these techniques in any code that you're intending to actually use for anything.
But the general idea of modifying Python source code at import time has at least one useful (if not necessary advisable) use case: macros.
Python has a library called macropy that implements Lisp-style syntactic macros in Python by modifying your source code at import time.
I've never actually used macropy, but it's pretty cool to know that Python makes the simple things easy and the insane things possible.
Finally, as bad as this mergesort implementation is, it allowed me to run a fun little experiment. We know that mergesort has good computation complexity compared to naive sorting algorithms. But how long does a list have to be before a standard implementation of bubble sort runs slower than my awful import-based implementation of mergesort? It turns out that a list only has to be about 50k items long before "import sort" is faster than bubble sort.
Computational complexity is a powerful thing!
All the code for this post is on Github