effekt-lang / effekt-lang/effekt

Consider relooping recursive LetDefs on JS CPS

Open
#1,341 0 comments 0 reactions 0 assignees View on GitHub
area:js experiment
Dominant language
Scala
Stars
469
Forks
41
Avg merge
1d 16h
Merged PRs (30d)
23

Description

If we remember which `LetDef`s are recursive, we can also reloop recursive functions (most often workers discovered by previous opt phases):

Image

Source program:
```scala
def myeach[A](list: List[A]) { f: A => Unit }: Unit = list match {
case Cons(x, xs) => f(x); myeach(xs) {f}
case Nil() => ()
}

def main() = {
[(0, 'a'), (1, 'b'), (2, 'c')].myeach {
case Tuple2(i, x) => println(show(i) ++ ": " ++ show(x))
}
}
```

So it'd mean turning the `myeach_worker_...` below
```scala
def main_7486 = { | ks_10277, k_10278 =>
def myeach_worker_10204 = { (list_10205) | ks_10279, k_10280 =>
list_10205 match {
case Cons_2895 (x_10213, xs_10214) => {
x_10213 match {
case Tuple2_424 (i_10249, x_10250) => {
let! ret_10251 = showBuiltin_45(i_10249)
let! ret_10253 = showBuiltin_49(x_10250)
let! v_r_10257 = println_32(infixPlusPlus_62(infixPlusPlus_62(ret_10251, ": "), ret_10253))
myeach_worker_10204(xs_10214) @ ks_10279, k_10280
}
}
}
case Nil_2894 () => {
jump k_10280(()) @ ks_10279
}
}
}
myeach_worker_10204(make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(0, 97), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(1, 98), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(2, 99), make List_2564 Nil_2894())))) @ ks_10277, k_10278
}
```

into a `letrec`:

```scala
def main_7486 = { | ks_10399, k_10400 =>
letrec myeach_worker_10326 = { (list_10327) | ks_10401 =>
list_10327 match {
case Cons_2895 (x_10335, xs_10336) => {
x_10335 match {
case Tuple2_424 (i_10371, x_10372) => {
let! ret_10373 = showBuiltin_45(i_10371)
let! ret_10375 = showBuiltin_49(x_10372)
let! v_r_10379 = println_32(infixPlusPlus_62(infixPlusPlus_62(ret_10373, ": "), ret_10375))
jump myeach_worker_10326(xs_10336) @ ks_10401
}
}
}
case Nil_2894 () => {
jump k_10400(()) @ ks_10401
}
}
}
jump myeach_worker_10326(make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(0, 97), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(1, 98), make List_2564 Cons_2895(make Tuple2_292 Tuple2_424(2, 99), make List_2564 Nil_2894())))) @ ks_10399
}
```

and then teaching the CPS IR -> JS transformer how to deal with these self loops.
Though note that in this example, it seems to have helped only by eliminating a single function call by replacing it with mutable state...

I do have a prototype of this locally, but the code is very low quality.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.