Complete chain of ThunkLang optimisations

[myreen]

The following is the proposed sequence of optimisations for ThunkLang. The actual implementation might merge a few of these.

1. pure-to-thunk incorporates let-force (unlike now)
2. pull lam out of delay in letrec/let
3. inline delay var into every force var
4. remove force (delay _) pattern (at the same time as pervious)
5. introduce forced version
6. inline wrapper everywhere
7. remove force (delay _) pattern (at the same time as pervious)
8. push let-delay inwards
9. optionally: split the letrec
10. optionally: remove deadcode

@samsa1 tells me: 2-4 are done as part of thunk_split_Delay_Lam.

Example: count (one forced var, one unforced)

Original PureLang code:

letrec
  count = lam n acc ->
    if n = 0 then acc else count (n - 1) (n : acc)
in ...

After demands:

letrec
  count = lam n acc ->
    seq n $ 
      if n = 0 then acc else count (seq n (n - 1)) (n : acc)
in ...

When entering ThunkLang:

letrec
  count = delay $ lam n acc -> 
    let n' = force n in 
      if n' = 0 then force acc else 
        (force count) (delay (n' - 1)) (delay (n : acc))
in ...

Lift lam out from letrec. This is the first worker-wrapper optimisation:

letrec
  count_lam = lam n acc -> 
    let n' = force n in 
      if n' = 0 then force acc else 
        (force count) (delay (n' - 1)) (delay (n : acc))
  count = delay count_lam
in ...

Inline the wrapper everywhere (including in ...):

letrec
  count_lam = lam n acc -> 
    let n' = force n in 
      if n' = 0 then force acc else 
        (force (delay count_lam)) (delay (n' - 1)) (delay (n : acc))
  count = delay count_lam
in ...

At the same time, remove force-then-delay:

letrec
  count_lam = lam n acc -> 
    let n' = force n in 
      if n' = 0 then force acc else 
        count_lam (delay (n' - 1)) (delay (n : acc))
  count = delay count_lam
in ...

Create a forced version. This is the second worker-wrapper optimisation.

letrec
  count_lam_forced = lam n' acc -> 
    let n = delay n' in 
      if n' = 0 then force acc else 
        count_lam (delay (n' - 1)) (delay (n : acc))
  count_lam = lam n acc -> count_lam_forced (force n) acc
  count = delay count_lam
in ...

Inline the wrapper everywhere (including in ...):

letrec
  count_lam_forced = lam n' acc -> 
    let n = delay n' in 
      if n' = 0 then force acc else 
        count_lam_forced (force (delay (n' - 1))) (delay (n : acc))
  count_lam = lam n acc -> count_lam_forced (force n) acc
  count = delay count_lam
in ...

At the same time, remove force-then-delay:

letrec
  count_lam_forced = lam n' acc -> 
    let n = delay n' in 
      if n' = 0 then force acc else 
        count_lam_forced (n' - 1) (delay (n : acc))
  count_lam = lam n acc -> count_lam_forced (force n) acc
  count = delay count_lam
in ...

Push let delay inwards:

letrec
  count_lam_forced = lam n' acc -> 
    if n' = 0 then force acc else 
      count_lam_forced (n' - 1) (let n = delay n' in delay (n : acc))
  count_lam = lam n acc -> count_lam_forced (force n) acc
  count = delay count_lam
in ...

Finally, we might want to split letrecs:

letrec
  count_lam_forced = lam n' acc -> 
    if n' = 0 then force acc else 
      count_lam_forced (n' - 1) (let n = delay n' in delay (n : acc))
in let
  count_lam = lam n acc -> count_lam_forced (force n) acc
in let
  count = delay count_lam
in ...

And then a bottom-up dead-code elimination pass might be run.

[samsa1]

I've just pushed a relation force_delay_rel that handles pass 7. It is defined as the composition of 2 relations : Force (Delay e) -> Tick e (newly defined relation) and Tick e -> e (special case of clean_rel)