bosatsu icon indicating copy to clipboard operation
bosatsu copied to clipboard

change matchless LoopFn node

Open johnynek opened this issue 2 years ago • 2 comments

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:

  1. we prove that recur always jumps back to the nearest enclosing loop by construction.
  2. we have labels on recur so that we update the correct values (I think this is easier since functions already have names).

johnynek avatar Jul 30 '21 19:07 johnynek

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.

johnynek avatar Jul 31 '21 02:07 johnynek

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.

johnynek avatar Sep 26 '21 20:09 johnynek