Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Interpreter written on top of an interpreter? #4

Open
Demonstrandum opened this issue Jun 29, 2019 · 20 comments
Open

Interpreter written on top of an interpreter? #4

Demonstrandum opened this issue Jun 29, 2019 · 20 comments
Labels
enhancement New feature or request feature request

Comments

@Demonstrandum
Copy link

This implementation will end up being quite slow, given that your writing this high level language in another interpreted high level language. Perhaps consider writing a bytecode compiler. You could compile your parse tree to Python bytecode and have it run on the Python VM. This is a good option because you're already writing it in Python so getting it to work should be easy, although Python bytecode is slightly non-standardised, so that's a con.
Alternatively you could rewrite this AST traversing interpreter in a compiled language and give it a speed boost, or even do that and write a virtual machine and compile it to your own bytecode.

@MonliH
Copy link
Collaborator

MonliH commented Jun 29, 2019

Sometime in the future, I may re-write some part (or all of Neutron) in Cython, for speedups. I don't think Neutron will be bytecode interpreted anytime soon though, as I have little knowledge on how to implement one, but if anyone is willing to help, I would appreciate it!

@Demonstrandum
Copy link
Author

I think a stack based VM would be the easiest to implement and easier to compile to. Instead of executing/evaluating code directly as you traverse the AST, compile it down to a set of instructions instead. These instructions can be executed much faster, on say the Python VM (which is stack based).

I think it would be an excellent endeavour.

@MonliH
Copy link
Collaborator

MonliH commented Jun 30, 2019

I just did a bit of research, a I found that a stack-based virtual machine requires a virtual machine, and even if I wrote the VM in python, it would still be tremendously slow. I may use rust to do this as it has lower level support, is faster, etc.. I might actually implement a register-based VM which is much faster. I'll look into it though... Do you have any knowledge in this field? Perhaps you could help.

@MonliH MonliH added the enhancement New feature or request label Jun 30, 2019
@MonliH
Copy link
Collaborator

MonliH commented Jul 1, 2019

Doing more research, I found that Common Intermediate Language (CIL) looks promising. It is the same bytecode used by c#. I could compile into CIL then run it with the .NET runtime or Mono (for multi-platform support, not just windows). This seems like a difficult task, so any help would be appreciated. I will most likely make 2 branches of Neutron, one bytecode interpreted and one traversing AST. This second branch would be much faster, but I think the built-in Numpy support would have to be sacrificed. I will also look into JVM.

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

If I have time I might try and make a Neutron compiler as well. Not sure what it should compile to yet tho. But it would be written in Chirp

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

I have little expertise in the compiler world, although you could compile to LLVM, directly to assembly (extremely ambiguous), or transpile to C++? Looking at Chirp, it looks like its a long way off, cause it doesn't have its core modules written yet, but I think they'll be there soon. You'd also have to write your own parser and lexer, which I could help with... I'm best with python, though.

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

One thing I don't see is, why use Chirp? Why not C++? C++ is probably faster (because of more assembly optimizations) and runs on almost every OS. Most people already have a C++ compiler, and C++ has more support and libraries.

EDIT: C++ also has classes, and structs. It looks like Chrip is just a clone of C++ with a different syntax.

EDIT 2: I just found out that you are one of the authors of Chrip, and that is why you want to use it.

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Transpiling to C++ would be an option, but I would prefer something else tho. I think compiling to Assembly would be a good idea tho, but need to investegate in that more. And yeah. I would prefer Chirp over C++, and I can tell you that Chirp will be stable with core modules within a few weeks. But yeah, C++ is faster than Chirp, I just don't like C++. I like Python the most, but it just Isn't the right language to make a good language

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Altough, I'm up for helping with a compiler written in Python as well. If speed isn't the biggest matter

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

Actually, making a compiler in python is not a bad idea, because compile time may be bad, but runtime would be very fast. I'm +1 for writing a compiler or transpiler in python.

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Nono. It's not bad, just not as fast. Count me in 🙋‍♂️

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Okay that was a wrong emoji

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

Yeah, i could write a compiler in python, although to what language, assembly? I don't think assembly is a good idea because its too hard to scale, and will become spaghetti, also, if I compiled to assembly, I would have to support way too many different cpu architectures... I think I will compile to LLVM IR.

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Nono. Don't use Assembly if making a compiler in Python. I guess LLVM IR would be the best choice, but not sure.

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

I may use python's llvmlite module, although I would have to toy around with it a bit and a stable realese may not come out for a while. Of course I would make 2 branches, one for interpreter, and one for a JIT compiler (with llvmlite). I guess I have alot of learning to do...

Note: if I made this JIT compiled, some features would have to be dropped, like inline python code and Numpy array support. That why I'm making 2 branches.

@Dmunch04
Copy link

Dmunch04 commented Jul 2, 2019

Is the "inline python code" feature like a preprocessor? Or what? And I won't mind if numpy arrays aren't builtin. But that's just my opinion

@MonliH
Copy link
Collaborator

MonliH commented Jul 2, 2019

What do you mean "preprocessor"? If I made neutron JIT compiled, I would have to completely rewrite all the built-in modules (because they use inline python code), which is fine.

@Demonstrandum
Copy link
Author

JIT compilation is a big task, so is a compiler. Learning something like LLVM will indeed take a lot of time. I didn't suggest you write VM in python, I suggested you compile your code down to python bytecode to run on the pre-existing python VM (which is written in C). Registrer based VMs are indeed slightly faster, but both Java with its JVM and Python both use stack based VMs. They offer great speed advantages without being too difficult to compile to nor implement.

@MonliH
Copy link
Collaborator

MonliH commented Jul 5, 2019

Yes, I may actually make Neutron run on JVM (the Java runtime) or CIL (the C# runtime), but I think llvmlite might work as well. It turns out llvmlite is not extremely low-level, so it might work. One pro of using llvmlite is that it will make the code run much faster, because when it compiles the LLVM IR, it does many optimizations.

I will do some tests and tell you what I find and some more research. I don't think I want to use the python VM because there is no real solid and consistent documentation though. I wasn't clear about this before: by JIT compiler I mean a "transpiler" of sorts that transpiles code into a bytecode, like JVM or CLS. It seems that CIL is more modern than JVM, although that is just speculation. I'll look into it though.

@Demonstrandum
Copy link
Author

Oh yeah, the HotSpot JVM and the main CIL VMs will do JIT compilation for you.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request feature request
Projects
None yet
Development

No branches or pull requests

3 participants