CakeML / CakeML/cakeml

Add simple form of higher-order inlining

Open
#267 2 comments 0 reactions 0 assignees View on GitHub
high effort medium reward student project
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

I suspect CakeML would do better on a number of benchmarks and real-world examples if we optimised `tabulate`, `map`, `filter`, `genlist`, `every` etc. for cases where they take a known closure as an argument and pass this closure to recursive calls unchanged.

Example:

fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs = map (fn n => n+1) ys

should become (step 1):

fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
in map end) (fn n => n+1) ys

which becomes (step 2):

fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = ((fn n => n+1) x) :: map f xs
in map end) 0 ys

which becomes (step 3):

fun map f [] = []
| map f (x::xs) = (f x) :: map f xs
...
val xs =
(let
fun map f [] = []
| map f (x::xs) = (let val n = x in n+1 end) :: map f xs
in map end) 0 ys

Such an optimisation would benefit from coming after `clos_known`. In fact, the crucial steps 2-3 would follow by `clos_call` and various `bvl` optimisations, if the last `f x` produced by step 1 was annotated with the closure number of `fn n => n+1`.

@SOwens tells me that [this paper](http://manticore.cs.uchicago.edu/papers/icfp14-reflow.pdf) is relevant, even though we would not aim at anything this comprehensive.

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.