Optimizations to avoid python recursion limit

[purescript-python]

Optimizations to avoid python recursion limit

[mikesol]

I think the VM idea is really good. One thing that may be worth exploring is using the C++ backend for this, which already has a mature community and FFI ecosystem. Another nice thing about that project is that the codegen is human readable, so you can debug pretty easily.

[gabejohnson]

creating functions that take multiple arguments to get rid of currying when possible

This is basically impossible because we only get ASTs of curried functions from purescript corefn.

The erlang backend does arity optimizations:

https://github.com/purerl/purerl/blob/master/src/Language/PureScript/Erl/CodeGen.hs#L217

but it "cheats" by using the externs files:

https://github.com/purerl/purerl/blob/1cb8f0412da684dcc1720a0e46907ea04a6bfa55/app/Build.hs#L119

These aren't part of the official compiler API and can break compatibility at any time.

[thautwarm]

First, purescript compiler is already able to transform tail call into loops.

However, it does not work for deeply stacked do-notations.

I'm not sure if purescript-tailrec helps, but if you haven't checked it, please have a look.

As we can only access corefn of purescript, we just cannot do much for this.

creating functions that take multiple arguments to get rid of currying when possible

This is basically impossible because we only get ASTs of curried functions from purescript corefn.

In order to support functions with arbitrary stack depth, there're 2 approaches:

Transforming Generating Python Code via the Trampoline Method

Supporting tail call eliminations for generated Python code is very easy, however, the problem is, this extremely breaks our straightforward FFI.

We can simply translate following generated code

def f(x):
    a = g(x)
    return f(a)

to

def f(x):
  a = compute_tail_call(g(x))
  return tail_call(f, a)

However then writing Python FFI becomes painful as we have to explicitly annotating every function objects to be tail_call functions:

@tailrec
def ffi_func(...):
    ...

And calling purescript functions from python becomes

from xxx import compute_tail_call
from Mod.pure import f

result =compute_tail_call(compute_tail_call(f(1))(2)) # equivalent to 'f 1 2' in purescript

Other than above annoying calling conventions, the performance got greatly decreased.

I feel like to reject this idea.

Stack-less Execution for Generated Code

I don't have a concrete design, but I think this is feasible and MAY avoid the performance pitfall when providing a stackless execution model.

In fact, so far we're not generating real Python code, instead, we generate something called PySExpr, which is particularly designed for purescript-python as a program representation to support large-scale codegen. You can see some of my explanations about PySExpr at here.

This just suggests that even though we want to run code in CPython runtime, with very straightforward FFI interoperability, it's unnecessary to generate Python code directly.

In fact, directly generating Python code can be impossible in some cases, due to the size of generated code is not scalable. The parser of Python is also so weak that it crashes when the source code is large(e.g., > 5MB). If you'd know more, we could talk in this weekend.

Hence, it'll be okay for us to design a virtual machine, written in C extensions(or things like Cython), which could avoid the endless growth of stacks, instead, migrating it to the space complexity of a heap stack.