Skip to content

Add simple form of higher-order inlining #267

Open
@myreen

Description

@myreen

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 is relevant, even though we would not aim at anything this comprehensive.

Metadata

Metadata

Assignees

No one assigned

    Labels

    high effortmedium rewardEasy to measure but may not be noticed by itselfstudent projectcan be done as a student project (at various levels)

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions