search

johnynek / bosatsu

A python-ish pure and total functional programming language
Apache License 2.0
225 stars 11 forks source link

Implement deforestation optimizations #966

Open johnynek opened 1 year ago

johnynek commented 1 year ago

See the foldr/build optimization here:

https://users.cs.northwestern.edu/~robby/courses/395-495-2017-winter/deforestation-short-cut.pdf

And Wadler's paper:

https://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps

johnynek commented 1 year ago

The tactic here, I guess would be to have a few stages:

  1. inline all predef functions if they involve build_List or foldr_List (e.g. map_List, filter_List, concat_List, etc...)
  2. apply the foldr_List(build_List(g), a, b) == g(a, b) optimization
  3. if we don't introduce thunks (see #978) we would finally rewrite foldr_List into fold-left and reverse.