Get lambda lifting right

[JustusAdam]

Lambda lifting is kind of a mess right now.

I just had to change it so that it doesn't recognize function references as literals, because for unitFn it is important that the reference stays as as a direct argument to the function, due to how code generation works in the backend. The same is actually true for nth, where the two indices have to remain literals. I'd prefer not having to teach the lambda lifting pass which functions need literal inputs and which don't. I don't yet know how this can be improved.

It could also mean that the current representation of the execution graph is insufficient or at least not well suited for nth and the like.

The workaround I am employing for the function references right now might not be available always, but for now its the easiest way.

I'm simply putting this issue out there so that we don't forget that it exists. For now this is low priority.

[sertel]

I think stating it to be a mess without even raising a concern, analyzing the problem properly and suggesting a solution is not really appropriate. You should keep those comments to yourself and rather remain constructive.

That being said, I would like to give the reasoning behind the current implementation:

We find all free variables but also all `lonely´ literals to construct the argument list of the lambda abstaction to be created. That way, no (stateful) function executes before something gets applied to the lambda. This makes sense because this is what a contextified execution is all about.

The problem seems to be now that certain ohua-internal functions exist that would fall into the category of having lonely literals, i.e., the arguments to the call are literals only. In your report you mention the following functions:

• nth :: List a -> Int -> a For an application of this function to appear in the list of lonely literals, the list must be a literal which is not possible to the best of my knowledge.
• unitFn :: FunRefLit a -> UnitLit -> a This function indeed takes always two literals which must remain in the form that it is being called. But I do believe that the unit literal should be a lonely literal to make sure this function never executes outside of its context. Looking at the code generation (for rust), I believe this should work, because the literal would now be input to the control operator.

A solution now could certainly be to just filter out function literals in general. This would work for as long as we do not support stateful functions as first class citizens in the algo language. To support it, we could just always say that the selection should prefer other types of literals first and only take function literals if they are the only type of literal in the argument list.

Looking at the commit history, I can see that Function Literals were introduced into the code without a proper idea of what to do with them in case of lambda lifting: see commit 8a66be136dd67cb21f4fafa77d459b0234f2a95c I can see a TODO comment there and I believe this issue is all about this.