bosatsu
bosatsu copied to clipboard
change matchless LoopFn node
We currently in matchless have a LoopFn node:
https://github.com/johnynek/bosatsu/blob/f9ef6767321c682ed392bf2425f13e976b7e4db8/core/src/main/scala/org/bykn/bosatsu/Matchless.scala#L41
this is a tail recursive function. One problem here is that it harms inlining somewhat: it is not solved how to inline tail recursive functions.
Instead we could follow clojure and have Loop/Recur
which isn't a function but evaluates to a value which is the result of a loop. Here, LoopFn would be a normal function that has a Loop/Recur body. In this way, we could inline such functions normally because Loop/Recur just compiles to a normal while loop, not a function + while loop.
There is some subtlety about nested inlines, but I think that can be solved in one of two ways:
- we prove that recur always jumps back to the nearest enclosing loop by construction.
- we have labels on recur so that we update the correct values (I think this is easier since functions already have names).
actually, maybe the better design is to introduce a new node at the TypedExpr
level that matches the Loop/Recur
pairing. That way, TypedExpr normalization can leverage it. Something like:
case class Loop[A](name: Bindable, binds: NonEmptyList[(Bindable, TypedExpr[A])], body: TypedExpr[A]) extends TypedExpr[A]
// This jumps back out to the nearest enclosing Loop with the matching name
case class Recur[A](name: Bindable, rebind: NonEmptyList[TypedExpr[A]], tpe: Type, tag: A) extends TypedExpr[A]
We can actually do this as the first phase of normalization. In this way, we can inline lambdas whose bodies are loops by just inlining the loops.
This may only work with monomorphic recursion. A loop with polymorphic recursion kind of implies boxing or type-erasure at the underlying level.
We are currently cavalier with the types when we do this transformation because Matchless
is type-erased.