effekt-lang / effekt-lang/effekt
Further optimising stream fusion
- Dominant language
- Scala
- Stars
- 469
- Forks
- 41
- Avg merge
- 1d 16h
- Merged PRs (30d)
- 23
Description
I was trying out "stream fusion" (example from https://gitlab.haskell.org/ghc/ghc/-/wikis/sequent-core#cases-where-we-win), can we do better here somehow?
At the very least, I'd like this program to not be worse with a new optimiser, cc @dvdvgt.
[Playground link](https://effekt-lang.org/playground.html?playground=hZFfa4MwFMXf%2FRTnMYHQtd1%2FRze6vY697amUIRppmEYxcXOI331JjGlxhT0Uiveec373hOc5TzV4KfRuuydfSdHyGFsa410KHUUZz5GLQvPGjoWsWx3jVSi7TdHjk%2FP6yQiwecRzVRUYwhgb9BFgHZRueFKecRhjcDEBGI3bQJno9OD0QJoojjdREGpTCD1%2BfKmkIh1Dp9woq5wP6eiDjyRmYtaHyIO0MqAY%2BPF%2FbKUzjNMrXJxufoKAGPsRZ8C30Ieg6tEZL7ePwNZw1ZacEEpH8MCiQq9ne%2FyP709xgXOinMN5MNdch0Rm6BYud97dEflU8mHXZiN3zFSqfy5%2Fl28jZJiDvJvncw892difMbO9lImQ9qlRN0LqQpLdimHNcMlwxXDNcMNwy3DHcM%2BwWu4X87yyysjaGGywxEB%2FAQ%3D%3D&repl=bWFpbigp)
```scala
effect emit[A](value: A): Unit
def filter[A](input: List[A]) { keep?: A => Bool }: List[A] = {
def stream[A](input: List[A]): Unit / emit[A] = input match {
case Nil() => ()
case Cons(x, xs) => do emit(x); stream(xs)
}
def unstream[A] { stream: => Unit / emit[A] }: List[A] =
try { stream(); Nil() } with emit[A] { x =>
Cons(x, resume(()))
}
def sfilter[A] { keep?: A => Bool } { stream: => Unit / emit[A] }: Unit / emit[A] =
try stream() with emit[A] {
case x and x.keep? => do emit(x); resume(())
case _ => resume(())
}
unstream {
sfilter { x => x.keep? } {
stream(input)
}
}
}
def main() = println([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].filter { x => x.mod(2) == 0 })
```
Core IR:
```scala
interface emit_3589[A_3588] {}
def main_3594() = {
val v_r_4078: List_928[Int_409] = reset { {p_5070} => // Is the `reset-shift` even needed here anymore?
def stream_worker_5105(input_5102: List_928[Int_409]) = input_5102 match {
case Nil_1165 { () =>
return ()
}
case Cons_1166 { (x_5101: Int_409, xs_5100: List_928[Int_409]) =>
if (infixEq_73(mod_109(x_5101, 2), 0)) {
val __5210: Unit_405 = shift(p_5070) { {k_5150} =>
val v_r_5152: List_928[Int_409] = resume(k_5150) {
return ()
};
return make List_928[Int_409] Cons_1166(x_5101, v_r_5152)
};
stream_worker_5105(xs_5100) // I think we could lift these tail calls out of the if
} else {
stream_worker_5105(xs_5100) // see ^
}
}
}
val __5212: Unit_405 = stream_worker_5105(make List_928[Int_409] Cons_1166(1, make List_928[Int_409] Cons_1166(2, make List_928[Int_409] Cons_1166(3, make List_928[Int_409] Cons_1166(4, make List_928[Int_409] Cons_1166(5, make List_928[Int_409] Cons_1166(6, make List_928[Int_409] Cons_1166(7, make List_928[Int_409] Cons_1166(8, make List_928[Int_409] Cons_1166(9, make List_928[Int_409] Cons_1166(10, make List_928[Int_409] Nil_1165())))))))))));
return make List_928[Int_409] Nil_1165()
};
def go_5244(l_5242: List_928[Int_409]) = l_5242 match {
case Nil_1165 { () =>
return "Nil()"
}
case Cons_1166 { (x_5251: Int_409, xs_5249: List_928[Int_409]) =>
val v_r_5259: String_404 = go_5244(xs_5249);
return infixConcat_36(infixConcat_36(infixConcat_36(infixConcat_36("Cons(", show_15(x_5251)), ", "), v_r_5259), ")")
}
}
val v_r_5253: String_404 = go_5244(v_r_4078);
let tmp_5308 = println_1(v_r_5253)
return tmp_5308
}
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Use the linked playground example and its generated Core IR as the baseline. Read the optimizer behavior around the shown reset-shift and duplicated tail calls, then verify whether the optimized program is no worse and whether the unnecessary structure can be removed without changing the result.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- scala
- Domain
- compilers, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100