Skip to content

Idea: Automatically stabilise unfoldings before the phase in which a RULE might fire

Here at ZuriHac I'm trying to address a pet peeve of mine: Broken cross-module list fusion.

(The deeper issue is that rewrite RULEs don't work across modules without programmer intervention.)

Here's my call to action: https://github.com/sgraf812/foldr-build/blob/8a42a16e0639afdd2335462f88acb95dc3de259a/README.md

Short version: This two module setup defeats list fusion because of the nature of phase activation of RULEs.

module Producer where

source :: [Int]
source = [0..2022]
module Main where

import Producer

main = print $ sum source

No fusion here without marking source as INLINE. But as I'm trying to convince @Noughtmare of in https://github.com/sgraf812/foldr-build/issues/1, programmers tend to forget to add these, even inside base and GHC.

But while listening to Simon's talk about the Simplifier, I had the following idea: Why couldn't stabilise unfoldings just before the phase where the first rewrite RULE becomes active that might fire in its RHS?

I think in the above example, we'll have RULE "eftInt" trigger on the enumFromTo @Int 0 2022 (which inlines to eftInt 0 2022).

{-# RULES
"eftInt"        [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y)
"eftIntList"    [1] eftIntFB  (:) [] = eftInt
 #-}

I think ~1 means "active before phase 1" (IIRC, doesn't matter much for this example), so we'll have to stabilise eftInt's unfolding after phase 0.

Then we don't need all transitive callers (such as the enumFromTo instance method) to attach INLINEs.

Of course there's the risk of code bloat, but I think it might be worth it.

Edited by Sebastian Graf
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information