Created
April 25, 2011 15:29
-
-
Save ilya-klyuchnikov/940672 to your computer and use it in GitHub Desktop.
How to combine supercompilers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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