A Pointless to Js Transpiler

[owaismohsin001]

Hey, I have been following pointless documentation for a day now and it seems extremely interesting. I found pointless through r/ProgrammingLanguages. I visited your website and since I myself like to make programming languages, I was thinking what if we made a Pointless to Js transpiler to increase the performance of Pointless (I read about the performance concern on Pointless's website).

I see ways to simulate many features in Js such as partial application and pipeline operators. Any specific reasons as to why this couldn't be done will be appreciated and if you do decide to make a Js transpiler then I'd surely try to help as much as I can.

[averynortonsmith]

Hey, thanks for the message. I think that a Pointless to JS transpiler could be a cool project - it's one that I've though about before myself. I agree that most of the features in Pointless would translate well to JS - the biggest difficulty I think would be figuring out how to accommodate tail-call optimization, which JS doesn't support natively, but which Pointless requires. I know Elm, which transpiles to JS), handles tail-recursion optimization, but a transpiler for Pointless would have to optimize non-recursive tail-calls as well. I don't have any leads on how this problem might be solved - but I'd be happy to discuss any ideas you have!

[owaismohsin001]

I think tail call optimization is more of you know, an optimization rather than an innate feature of a language that needs implementation once the core is there. I think we can have a transpiler that transpiles without TCO but then we could use some babel plugin like this to transpile the Js that Pointless transpiler compiled. The aforementioned plugin works unless Pointless does tail-call optimization on mutually recursive functions.

I, in general, don't think TCO is something that needs to be prioritized to such a degree because mainstream functional languages like Clojure still do very naive TCO and get away with it. Another way to speed-up could be to re-write this interpreter in something more low-level like Nim. I mean you could re-write it in C but then garbage collection would be a problem. It could be a huge speed-up and I know enough Nim that I might be able to help if you decide to walk towards that route too.

I am saying all of this because one of my languages had major performance concerns(by virtue of being written in Python), it was used by some relatively small local institutes mainly for educational purposes because it was based on my native language. I was able to improve performance by compiling it to Js and I am currently writing an interpreter for it in Nim to have a faster yet equally user-friendly ecosystem.

[owaismohsin001]

Btw, is there a Pointless BNF?

[averynortonsmith]

No BNF yet I'm afraid - the parser code is fairly well commented, but a real grammar spec would certainly be good to have.

With regard to tail-recursion, the one concern is that since Pointless doesn't have normal looping structures, functions end up relying on tail-recursion pretty heavily. Removing tail-recursion optimization would cause many of the list-handling functions in the standard library to stop working for lists with length > 1000 (the call depth limit). Assuming that we have tail-recursion working, though, that might be good enough, even without full tail-call optimization. I'd have to look through the prelude to see if any functions currently use mutual tail-recursion.

You mention the possibility of re-implementing Pointless in a language like Nim or C - as it happens, Pointless was implemented in C up until recently, (see commit history up to c1117c. The C version was much faster than the current Dart implementation, in part because it was written as a bytecode compiler / VM instead of an interpreter, but I found that the time it took to make modifications to the C implementation made it hard to experiment with new language features.

That being said, using Nim for implementation could provide a good balance between performance and ease-of-use. You should take a look at the old C implementation and tell me if you think it would translate well to Nim!

[owaismohsin001]

I would start by commenting on tail-recursion. I understand that pointless itself doesn't have any loop structures and some list functions might be broken without tail-recursion optimization but compiling to Js would require having a standard prelude written in Js anyway so why not have standard prelude and runtime re-written by hand, using loops. The only problem I see is that it may be considered a bit "unethical" or a non-functional approach but remember that the language itself will still be largely functional and I don't theoretically see that as too huge of a concern.

As for the C implementation, just went through seemingly relevant parts of it and it appears that it would be well-translateable and would result in significantly shorter nim code. Like all the structs would become nim types, the stack size can be unlimited with nim sequences, GC wouldn't need to exist since nim does the work for you, most of the tokenizer would remain the same, compiler's translation would be straight forward. I nonetheless think that if you decide to go the VM route, it will still sort of have the same problem of being hard to be experimented with.

I think if keeping the implementation simple enough to experiment is a goal then a translation of the Dart implementation to nim isn't too farfetched either. The dispatch function in the interpreter rather than some weird visitor pattern would translate well to nim, all of the values would translate to nim's version of tagged unions which are very similar to C's version but just way more powerful. Nodes themselves could either translate to another tagged union visited by the aforementioned dispatch function (Way more efficient than the contrary) or to mutually recursive type definitions, visited by nim's multi-methods (Exponentially more elegant and readable than the contrary).

[averynortonsmith]

Yeah the question of how "pure" to keep the implementation if translating to JS isn't something I have a good answer to. I'm more inclined to focus on improving the interpreter / compiler situation than going town the transpiling path, although if that's something you'd like to explore you're welcome to!

If the goal here is to have a faster Pointless implementation, then going from a Dart-based interpreter to a Nim-based interpreter probably won't do much (I tried writing a bytecode compiler / VM in Dart and it wasn't any faster than the interpreter!). So for the work to be fruitful I think that writing a new compiler / VM in Nim would be the way to go. I'm working right now to make examples for Pointless and improve the language itself, so a re-implementation would be a project for the future, but again if that's something you'd like to start looking into I'm happy to provide any help / advice that I can.

[owaismohsin001]

Yes, I happened to be leaning more towards the idea of implementing it in nim. I think I would like to implement this programming language with either an interpreter or a byte-code compiler and VM, I just started working on the tokenizer yesterday and almost got it done. I would share it with you as soon as I am done.

Would an interpreter in C be fast? Because nim more or less is equivalent in speed with C, little differences here and there that may or may not matter. I would like to make an informed and thought out decision on it being a VM based or an interpreter. I think I'll make this decision when I'm done with the parser to make it a have it a bit saner.

Edit: Got the tokenizer fully working.

[averynortonsmith]

Awesome! Can't wait to see it!

I think there would be a substantial slowdown going from a c vm to a c interpreter -- more importantly, I think it might be harder to implement an interpreter in c than a vm. I'd recommend going the vm route.

I'll put together some local test cases that I have for the tokenizer and send them to you if you want to run them against your implementation.

[averynortonsmith]

I've also been working on a Pointless tutorial / example that you might find interesting:
https://ptls.dev/tutorials/factorsVM.html

edit: oops, didn't mean to close the issue

[owaismohsin001]

Definitely send the tests over, they'll be a huge help. Ran it against a bunch of tutorial examples found some bugs and fixed them. Now it runs fine with all the tutorial examples I have tried.
Yeah I think VM route seems more interesting. We'll see when the parser get's completed but it'll most probably be a VM. My PC stopped working for a day but now I got it fixed so, I'll hopefully get to implement the most of the parser tommorow.

[averynortonsmith]

Check out this fork for the tests: https://github.com/averynortonsmith/pointless
^ also contains an updated makefile -- you should be able to run make test to run the tests

The tests inputs are what's important -- the expected outputs are just the current output from the parser / tokenizer. That means, for example, that if you're implementation uses a different string representation for AST nodes, you'll get different outputs.

[owaismohsin001]

Thanks for the tests, worked out really well for me. Finally got all the tests running for the parser and the tokenizer. I was thinking why not implement both the interpreter and the VM/Compiler. I have the front-end done so, I don't think that would be amount to twice the work, and good news would be that we can experiment on one implementation (the interpreter) while keeping the other (VM and compiler) stable. We would test out a feature in the interpreter version and once a feature is completed and final, we can implement it in the VM version.

I think I will get around making the interpreter first and this interpreter would be done in like a day or two (at most, a eek) then I'll upload that implementation, and start working on the VM/Compiler.

edit: Tests really do make life easier, do you have some for the interpreter?

[averynortonsmith]

Sounds good! Take your time too -- I'm sure you've got other things on your plate and you don't want to get burned out!

I have some old interpreter tests lying around. I'll update them and send them to you tomorrow.

Here are some files from a previous attempt at a bytecode VM in Dart https://github.com/averynortonsmith/dartPtlsVM. I abandoned that approach when I did some preliminary performance tests and realized that it wasn't any faster than the interpreter I'd written. I think that Dart is too high-level for the performance benefits of a bytecode VM to really come through. Although I didn't finish the Dart VM, the compiler has some substantial improvements over the C implementation (in particular updates to the instruction set and handling of closures). Could be helpful when working on a new compiler, although I agree that doing the interpreter first makes sense.

You should also know that there are a few features of the current Dart Pointless implementation that I never implemented in the compilers / VMs I prototyped. These include, off the top of my head: try/catch/throw, readling lines from stdin as a lazy list, and the repl; though I have ideas about how all of these could be done.