Reducing the amount of syntax levels in codegen

I’m writing a lua backend for PureScript and I’ve hit a problem with luajit’s parser which is that it doesn’t support unlimited syntax levels in it’s parser (I think it’s the parser, anyway). Basically large do blocks with lots of binds will generate a huge amount of syntax levels in the generated code.

My question is, what should I do to reduce the amount of nested blocks in the generated code? I could write some optimization pass for Effect, which I tried but that’s a bit trickier than I initially thought. It also won’t work for other types than Effect. I could split the nested expressions into top-level sub-expressions. That seems a bit rough and destroys readability. Do you know of any solutions to this problem?

1 Like

Can you post an example of some output and the code it’s generated from?

One example is in the tests for arrays https://github.com/purescript/purescript-arrays/blob/master/test/Test/Data/Array.purs#L21

This is the generated code for testArray as it stands https://gist.github.com/anttih/779bec3542d8c13c4c54b8479b732821

So basically a lot of discarded binds. I would imagine it’s less likely to happen in code where you’re actually binding variables rather than discarding.

1 Like

There isn’t a difference between discard and bind. The reason discard exists is to incur a constraint on the type being discarded which lets one specify in a type-directed way what can be discarded, and what should warn.

I think you’re correct, that the automated solution is for the backend to syntactically lift these closures in some way. do syntax generates right-associated binds, which is where you get the nesting, so if anything the situation with bind will be worse since it can incur dependencies that prevent lifting. A complete solution would probably require full lambda lifting.

Yeah, this is why I thought that maybe latching on the discards to remove them would solve the problem. But it’s a bad solution anyway, because it’s not complete solution.

Thanks for mentioning lambda lifting! I will need to think if I could still retain some level of readability in the output with full lambda lifting. Maybe adding some cleaverness there to only trigger it where absolutely necessary.

I believe you’re looking for this compiler pass which handles optimizing various functions in Effect including bind and discard. It rewrites nested calls to bind / discard into sequential imperative form that is easy to translate to JS.

Yes, Gary also mentioned this on slack. I totally forgot about MagicDo. I may end up first implementing this even though this only works for Effect.