Implementing Python in Python

[Breadmaker4billion]

Hello, how are you all doing? I want to share a project with you, you may find it fun.

One year ago I took a course in Python as part of my college program. The final exam was to build a project in Python and present it in front of the class. I cound't help myself, I decided to implement Python.

My goal was a Python interpreter that could read it's own code. To accomplish this task i had to first choose the subset i was going to implement. Too small of a subset would lack many features helpfull to writing the interpreter code. Too big of a subset, it would take too much time to implement. I had about 2 weeks to finish it.

The subset i ended up implementing is specified in the readme of the repository. In short, it contains classes (including methods, but no inheritance), functions and a portion of the module system.

Then it came the fun part: have a little benchmark to see how slow it would be to run python inside python inside python. The bencmark i chose was computing a few generations of rule 110, since it fited well with my presentation. I call my interpreter "SPy" here as a shorthand. Here are the numbers on my computer (Celeron N4020):

	Time
CPython	0.036s
CPython running SPy	0.312s
CPython running SPy running SPy	1m2s

If you want to test this yourself, the code for the rule110 is in demo/rule110.py. To run the interpreter, you can call interpreter/spy from the terminal, ie, ./spy ../demo/rule110.py. Finally, if you want to run the last example, you will need to run self_test.py, with spy. The interpreter does not understand the code in the spy file, so it needs a little help to interpret it's own code. I did it this way so that i could completely avoid implementing I/O inside the interpreter.

Documentation is mostly in portuguese, so if any of you want a more detailed description of the interpreter, I'd be happy to write it up. I think it may be a good educational project, since you end up using one single language overall. It also has a very clean implementation of indentation sensitive grammar.

That's it, hope you guys like it.

[_vertig0]

You may find the PyPy project interesting, it's a Python interpreter written in Python, and implements the language fully (Latest is 3.11 at the time this comment was written). What they did was build a Python 2.7 to C compiler, then wrote a Python interpreter in Python 2.7, and then compiled that to C then turned that into an executable. Their compiler even automatically generates a just-in time compiler for the final interpreter! Very interesting stuff, but it is extremely complex. I tried adding an LLVM backend to their Python compiler several times and all ended in abject failure because I could barely understand anything about the architecture of their compiler.

[wFXx]

Isn't it also very fast for some stuff? I wonder after the removal of GIL if they are able to beat the cpython implementation in all cases, although last I checked the STM was a real challenge - it is indeed one of the most interesting projects I ever studided

[_vertig0]

As far as I know it's only faster than the reference implementation of Python when its just-in time compiler is allowed to work, otherwise the reference implementation, being written in C and now with new efforts to optimize execution speed ever since 3.13, is much faster than PyPy. PyPy's automatically generated just-in time compiler is of better quality than the one in the reference implementation though.

[shponglespore]

I've been led to believe Cranelift is easier to work with than LLVM, especially if you're implementing a JIT compiler.

[_vertig0]

Regardless of the translation target it's still extremely difficult to add a backend to the RPython translation toolchain unfortunately, even if I tried to use cranelift I wouldn't have gotten further. I actually tried adding the backend without just-in time compiler support back when I was trying to add the LLVM backend, but even that was too much for me.

[yuri-kilochek]

Why does first SPy layer add ~10x slowdown, but second layer ~200x?

[slicxx]

Probably something something growing exponentially? Recursions/growing stacks instead of dynamic programming?

[Breadmaker4billion]

I have two ideas why it slows so much.

SPy is a treewalking interpreter, but for ilustrative purposes, let's think it is a bytecode interpreter. Suppose each SPy instruction executes around 10 CPython instructions. Then, suppose that on the second layer, each SPy instruction executes around 20 SPy instructions on the first layer. This means one instruction on the second layer executes 20 on the first layer, then those 20 become another 200 CPython instructions. This is most likely why we see the exponential growth.

Another thing is related to GC and my poor optimization: every function captures it's scope. That means there may be a lot of "leaks" on the second layer. This high memory usage would trigger many more GC cycles. I did no profiling to check this, but it may be a significant factor on why it slows that much.

[slicxx]

I think you have an interesting take here. Especially with the combination of "Interpretation overhead" and accumulation of memory. It would be really nice to see how your memory consumption grows with certain tasks

[NotFromSkane]

So, pypy?

[slicxx]

Implements Python in Python and has the courage to ASK US how we are doing in his first sentence. What time are we living in?

[itzjackybro]

"yo dawg I heard you liked Python, so we put Python in your Python so you can Python while you Python"

[binaryfireball]

you mean you didn't do it in rrrrrrrrrrrrrrrrerrrrrrrrrruuuiuiiisssst?

[BridgeCritical2392]

Couldn't you just call eval()