Complete chain of ThunkLang optimisations
- Dominant language
- Standard ML
- Stars
- 44
- Forks
- 5
- PR merge metrics
- No merged PRs in 30d
Description
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.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by examining the existing `thunk_split_Delay_Lam` transformation, which the issue says covers steps 2–4, and identify where the remaining ThunkLang optimisation passes are implemented. The proposed sequence and examples need to be reconciled with the code and validated with compiler tests, but no files or test entry points are named and the final scope is still optional in places.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100