Skip to content

Instantly share code, notes, and snippets.

@ilya-klyuchnikov
Created April 25, 2011 15:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ilya-klyuchnikov/940672 to your computer and use it in GitHub Desktop.
Save ilya-klyuchnikov/940672 to your computer and use it in GitHub Desktop.
How to combine supercompilers
import Control.Monad
import Data.Maybe
data DriveStep e = DriveStep e
type Driver e = e -> DriveStep e
type Whistle e = [e] -> e -> Maybe e
type Rebuilder e = e -> e -> e
type MRebuilder e = e -> e -> [e]
data SC e = SC {drive :: Driver e, whistle :: Whistle e,
rebuild :: Rebuilder e}
data MSC e = MSC {mdrive :: Driver e, mwhistle :: Whistle e,
mrebuild :: MRebuilder e}
data SCGraph e = SCGraph e
runSC :: SC e -> e -> e
runSC = undefined
runMSC :: MSC e -> e -> [e]
runMSC = undefined
---------
type Subst e = e -> e
(//) :: e -> Subst e -> e
(//) = undefined
test :: e -> e -> Maybe (Subst e)
test = undefined
-- makes a two-level single-result supercompiler
-- from a single-result supercompiler
l2 :: SC e -> SC e
l2 sc@(SC d w rb) = SC d w rb' where
rb' e1 e2 =
maybe (rb e1 e2) (e1 //) (test (runSC sc e1) (runSC sc e2))
-- makes a two-level single-result supercompiler by combining
-- two different single-result supercompilers
l2' :: SC e -> SC e -> SC e
l2' (SC d w rb) sc = SC d w rb' where
rb' e1 e2 =
maybe (rb e1 e2) (e1 //) (test (runSC sc e1) (runSC sc e2))
-- makes a two-level single-result supercompiler by combining
-- a single-result supercompiler and multi-result supercompiler
l2'' :: SC e -> MSC e -> SC e
l2'' (SC d w rb) msc = SC d w rb' where
rb' e1 e2 = maybe (rb e1 e2) (e1 //) res where
res = msum [test x y | x <- es1, y <- es2]
(es1, es2) = (runMSC msc e1, runMSC msc e1)
--------
type MGeneralizer e = e -> [e]
-- makes a multi-result one-level supercompiler by combining
-- a single-result supercompiler and multi-generalization
multi :: SC e -> MGeneralizer e -> MSC e
multi (SC d w _) g = MSC d w rb where
rb _ e2 = g e2
-- makes a multi-result two-level supercompiler by combining
-- an upper multi-result supercompiler and
-- a lower single-result supercompiler
multi' :: MSC e -> SC e -> MSC e
multi' (MSC d w rb) sc = (MSC d w rb') where
rb' e1 e2 = ex ++ (rb e1 e2) where
ex = map (e1 //) $ maybeToList (test (runSC sc e1) (runSC sc e2))
-- makes a multi-result two-level supercompiler by combining
-- two multi-result supercompiler
multi'' :: MSC e -> MSC e -> MSC e
multi'' (MSC d w rb) msc = (MSC d w rb') where
rb' e1 e2 = extra ++ (rb e1 e2) where
extra = map (e1 //) $ catMaybes $ [test x y | x <- es1, y <- es2]
(es1, es2) = (runMSC msc e1, runMSC msc e1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment