Effect handlers (tracking issue)

[LPTK]

Here are some problems left in the original PR (#257) that still need to be addressed.

Code documentation

• Function instrumentation and effect handlers transformation #257 (review)

Interactions with initialization

• handle statements should not be followed by object initialization code: Function instrumentation and effect handlers transformation #257 (review)
• [low-priority] Once we have optional bindings, we could add special treatment to let bindings that may never run due to lack of resumption Function instrumentation and effect handlers transformation #257 (review)

Bug fixes

• Fix bug that was introduced or uncovered after the big refactoring (f764eb9)

  Details

  mlscript/hkmc2/shared/src/test/mlscript/handlers/EffectsInClasses.mls

  Lines 9 to 55 in f764eb9

  	// FIXME: the `return Lol1` is wrong here
  	:sjs
  	class Lol(h) with
  	print(h.perform("k"))
  	//│ JS (unsanitized):
  	//│ let Lol1;
  	//│ Lol1 = function Lol(h1) { return new Lol.class(h1); };
  	//│ Lol1.class = class Lol {
  	//│ constructor(h) {
  	//│ this.h = h;
  	//│ let tmp, res, Cont$168;
  	//│ Cont$168 = function Cont$168(pc1) { return new Cont$168.class(pc1); };
  	//│ Cont$168.class = class Cont$168 extends globalThis.Predef.__Cont.class {
  	//│ constructor(pc) {
  	//│ let tmp1;
  	//│ tmp1 = super(null, null);
  	//│ this.pc = pc;
  	//│ }
  	//│ resume(value$) {
  	//│ if (this.pc === 0) {
  	//│ res = value$;
  	//│ }
  	//│ contLoop: while (true) {
  	//│ if (this.pc === 1) {
  	//│ return Lol1;
  	//│ } else if (this.pc === 0) {
  	//│ tmp = res;
  	//│ this.pc = 1;
  	//│ continue contLoop;
  	//│ }
  	//│ break;
  	//│ }
  	//│ }
  	//│ toString() { return "Cont$168(" + this.pc + ")"; }
  	//│ };
  	//│ res = this.h.perform("k") ?? null;
  	//│ if (res instanceof globalThis.Predef.__EffectSig.class) {
  	//│ res.tail.next = new Cont$168.class(0);
  	//│ res.tail = res.tail.next;
  	//│ return res;
  	//│ }
  	//│ tmp = res;
  	//│ Predef.print(tmp)
  	//│ }
  	//│ toString() { return "Lol(" + this.h + ")"; }
  	//│ };
  	//│ null

• Instrumentation seems to break with the following test: https://github.com/CAG2Mark/mlscript/blob/handler-fixes/hkmc2/shared/src/test/mlscript/handlers/ZCombinatorHandler.mls (edit: it's due to stuff after tail-calls not being resumed as a result of the handler tail-call optimization, it's being fixed right now)

• This fails to print "b"

  class Lol(h) with
    print(h.perform("k"))
  
  let oops = 
    handle h = Effect with
      fun perform(arg)(k) =
        print(arg)
        k("b")
    Lol(h)
  //│ > k
  //│ oops = Lol { h: Effect$h$ {} }

• Fix bug related to nested handlers and non-tail resumptive handlers (ea34066)

• Verify assertion added in (ea34066) always hold or fix those cases. Rewrote from scratch.

• Fix bug related to super call being effectful or disallow effectful constructor.

• modules and object constructors needs to be treated specially, they are called immediately.

Missing implementations

• Add ability to handle parameterized effects
• Add code to correctly interact with JS-native throw/catch

Optimizations

• Use switch statements instead of nested if (this.pc === ...) statements
• When stack safety is on, never unwind the stack for tail-resumptive effects – just treat them like normal virtual calls without a resume continuation. Unless annotated with some @nonTailResumptive annotation, which the stack effect's handler method itself would have.
• Generate continuation classes of the form class Cont with {constructor(pc) ...} rather than class Cont(pc) with {...}, as the latter generates an additional function, which here is superfluous. However, the constructor syntax is not yet (fully?) supported in the new compiler.
• Coalesce useless states (EDIT: it's already pretty optimized, further optimization might be very hard)
• Maybe don't instrument the calls to small functions? (As long as they are known not to use much stack space.)
• Lambdas cause a lot of code duplication. The example

  fun foo() = 2
  :sjs
  fun mkrec(g) =
    let x = foo()
    selfApp of self =>
      let y = foo()
      g of y => 
        let z = foo()
        self(self)(y)

  generates about 300 lines of code. A possible fix would be to move the lambda body into another function definition.

Space-saving optimizations to try:

• Instrument stack safety after effect handlers (EDIT: Stack safety overhaul and effect handlers debloating MK1 #307)
  • No need for the virtual stack manipulations
  • Don't do the stack checking stuff in continuation classes

Benchmarking

• Compare to a JS program where everything is async
  • when no suspension is actually performed (the program is effectively sync)
  • when various numbers of suspensions are made
• Compare to a JS program where everything is sync and no suspension is performed (example of non-tailrec map function and how it scales in both cases)
• Try the transformation on ported nofib programs and benchmark them

Future possible features to add

• Add a sync function modifier to compile a function without instrumentation
• Add a sync expression modifier to compile a function call without instrumentation
• Add logic to call methods onSuspend, onResume, onUnwind, if they exist, when appropriate to handle resources