Jump to...
-
Off-line partial evaluator...
- Benchamark list
Example 9: a simple interpreter
[ Original program ] [ Annotated program ] [ Specialized program ] [ Runtimes ]
import Benchmark (runBenchmark)
data Nat = Z | S Nat | E
data Token = Cst Nat | Var Nat | Plus Token Token | Minus Token Token
| Mult Token Token
main x =int (Mult (genPlus (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z)))))))))))))))) (Cst x)) [] []
int :: Token -> [Nat] -> [Nat] -> Nat
int (Cst x ) _ _ = x
int (Var x ) vars vals = lookup x vars vals
int (Plus x y) vars vals = add (int x vars vals ) (int y vars vals )
int (Minus x y) vars vals = minus (int x vars vals ) (int y vars vals )
int (Mult x y) vars vals = mult (int x vars vals ) (int y vars vals )
lookup _ [] ( _:_) = E
lookup _ ( _:_ ) [] = E
lookup x (nv:nvs) (v:vs) = ifte (eq x nv) v (lookup x nvs vs )
eq Z Z = True
eq Z (S _)= False
eq (S _) Z = False
eq (S x) (S y)= eq x y
ifte True x _ = x
ifte False _ y = y
add Z y = y
add (S x) y = S(add x y)
minus x Z = x
minus (S x) (S y)= minus x y
mult Z _ = Z
mult (S x) y = add y (mult x y)
--tools
genMult (S Z) = (Cst (S(S Z)))
genMult (S (S n))= (Mult (genMult (S n)) (genMult (S n)))
genPlus (S Z) = (Cst (S Z))
genPlus (S (S n))= (Plus (genPlus (S n)) (genPlus (S n)) )
GEN x = x
bench = runBenchmark 10 (\_ -> print (x =:= main (n2s 20) ))
where x free
n2s n = if n==0 then Z else S (n2s (n-1))
s2n Z =0
s2n (S n)= 1+ s2n n
import Benchmark (runBenchmark)
data Nat = Z | S Nat | E
data Token = Cst Nat | Var Nat | Plus Token Token | Minus Token Token
| Mult Token Token
main x =int (Mult (genPlus (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z)))))))))))))))) (Cst x)) [] []
int :: Token -> [Nat] -> [Nat] -> Nat
int (Cst x ) _ _ = x
int (Var x ) vars vals = lookup x vars vals
int (Plus x y) vars vals = add (GEN (int x vars vals )) (GEN (int y vars vals ))
int (Minus x y) vars vals = minus (GEN (int x vars vals )) (GEN (int y vars vals ))
int (Mult x y) vars vals = mult (GEN (int x vars vals )) (GEN (int y vars vals ))
lookup _ [] ( _:_) = E
lookup _ ( _:_ ) [] = E
lookup x (nv:nvs) (v:vs) = ifte (GEN (eq x nv)) v (GEN (lookup x nvs vs ))
eq Z Z = True
eq Z (S _)= False
eq (S _) Z = False
eq (S x) (S y)= eq x y
ifte True x _ = x
ifte False _ y = y
add Z y = y
add (S x) y = S(add x y)
minus x Z = x
minus (S x) (S y)= minus x y
mult Z _ = Z
mult (S x) y = add y (GEN (mult x y))
-- tools
genMult (S Z) = (Cst (S(S Z)))
genMult (S (S n))= (Mult (genMult (S n)) (genMult (S (GEN n))))
genPlus (S Z) = (Cst (S Z))
genPlus (S (S n))= (Plus (genPlus (S n)) (genPlus (S (GEN n))) )
GEN x = x
bench = runBenchmark 10 (\_ -> print (x =:= main (n2s 20) ))
where x free
n2s n = if n==0 then Z else S (n2s (n-1))
s2n Z =0
s2n (S n)= 1+ s2n n
Specialized program
[ go top ]
prelude> :l intSimpleAnn_pe
Compiled Curry program 'intSimpleAnn_pe.pl' is up-to-date.
-- Program file: intSimpleAnn_pe
module intSimpleAnn(Nat(Z,S,E),Token(Cst,Var,Plus,Minus,Mult),int,lookup,eq,ifte,add,minus,
mult,genMult,genPlus,GEN,bench,n2s,s2n,main,mult_pe1,add_pe2,int_pe3,int_pe4,int_pe5,
int_pe6,int_pe7,int_pe8,int_pe9,int_pe10,int_pe11,int_pe12,int_pe13,int_pe14,int_pe15,
int_pe16,int_pe18,int_pe19) where
import Benchmark
data Nat = Z | S Nat | E
data Token = Cst Nat | Var Nat | Plus Token Token | Minus Token Token | Mult Token Token
int :: Token -> [Nat] -> [Nat] -> Nat
int eval flex
int (Cst v3) v1 v2 = v3
int (Var v4) v1 v2 = lookup v4 v1 v2
int (Plus v5 v6) v1 v2 = add (GEN (int v5 v1 v2)) (GEN (int v6 v1 v2))
int (Minus v7 v8) v1 v2 = minus (GEN (int v7 v1 v2)) (GEN (int v8 v1 v2))
int (Mult v9 v10) v1 v2 = mult (GEN (int v9 v1 v2)) (GEN (int v10 v1 v2))
lookup :: Nat -> [Nat] -> [Nat] -> Nat
lookup eval flex
lookup v0 [] (v3 : v4) = E
lookup v0 (v5 : v6) [] = E
lookup v0 (v5 : v6) (v7 : v8) = ifte (GEN (eq v0 v5)) v7 (GEN (lookup v0 v6 v8))
eq :: Nat -> Nat -> Bool
eq eval flex
eq Z Z = True
eq Z (S v2) = False
eq (S v3) Z = False
eq (S v3) (S v4) = eq v3 v4
ifte :: Bool -> a -> a -> a
ifte eval flex
ifte True v1 v2 = v1
ifte False v1 v2 = v2
add :: Nat -> Nat -> Nat
add eval flex
add Z v1 = v1
add (S v2) v1 = S (add v2 v1)
minus :: Nat -> Nat -> Nat
minus eval flex
minus v0 Z = v0
minus (S v3) (S v2) = minus v3 v2
mult :: Nat -> Nat -> Nat
mult eval flex
mult Z v1 = Z
mult (S v2) v1 = add v1 (GEN (mult v2 v1))
genMult :: Nat -> Token
genMult eval flex
genMult (S Z) = Cst (S (S Z))
genMult (S (S v2)) = Mult (genMult (S v2)) (genMult (S (GEN v2)))
genPlus :: Nat -> Token
genPlus eval flex
genPlus (S Z) = Cst (S Z)
genPlus (S (S v2)) = Plus (genPlus (S v2)) (genPlus (S (GEN v2)))
GEN :: a -> a
GEN v0 = v0
bench :: IO ()
bench = Benchmark.runBenchmark 10 (intSimpleAnn_lambda0_0 v0) where v0 free
n2s :: Int -> Nat
n2s v0 =
if v0 == 0
then Z
else S (n2s (v0 - 1))
s2n :: Nat -> Int
s2n eval flex
s2n Z = 0
s2n (S v1) = 1 + (s2n v1)
intSimpleAnn_lambda0_0 :: Nat -> Int -> IO ()
intSimpleAnn_lambda0_0 v0 v1 = print (v0 =:= (main (n2s 20)))
main :: b -> a
main v0 = mult_pe1 int_pe3 (int_pe19 v0)
mult_pe1 :: c -> b -> a
mult_pe1 eval flex
mult_pe1 Z v5 = Z
mult_pe1 (S v304) v5 = add_pe2 v5 (mult_pe1 v304 v5)
add_pe2 :: c -> b -> a
add_pe2 eval flex
add_pe2 Z v309 = v309
add_pe2 (S v404) v309 = S (add_pe2 v404 v309)
int_pe3 :: a
int_pe3 = add_pe2 int_pe4 int_pe4
int_pe4 :: a
int_pe4 = add_pe2 int_pe5 int_pe5
int_pe5 :: a
int_pe5 = add_pe2 int_pe6 int_pe6
int_pe6 :: a
int_pe6 = add_pe2 int_pe7 int_pe7
int_pe7 :: a
int_pe7 = add_pe2 int_pe8 int_pe8
int_pe8 :: a
int_pe8 = add_pe2 int_pe9 int_pe9
int_pe9 :: a
int_pe9 = add_pe2 int_pe10 int_pe10
int_pe10 :: a
int_pe10 = add_pe2 int_pe11 int_pe11
int_pe11 :: a
int_pe11 = add_pe2 int_pe12 int_pe12
int_pe12 :: a
int_pe12 = add_pe2 int_pe13 int_pe13
int_pe13 :: a
int_pe13 = add_pe2 int_pe14 int_pe14
int_pe14 :: a
int_pe14 = add_pe2 int_pe15 int_pe15
int_pe15 :: a
int_pe15 = add_pe2 int_pe16 int_pe16
int_pe16 :: a
int_pe16 = add_pe2 (S Z) (S Z)
int_pe18 :: b -> a
int_pe18 eval flex
int_pe18 Z = S Z
int_pe18 (S v7404) = add_pe2 (int_pe18 v7404) (int_pe18 v7404)
int_pe19 :: b -> a
int_pe19 v0 = v0
-- end of module intSimpleAnn_pe
intSimpleAnn_pe(module: intSimpleAnn)>
| program | original runtime average | specialized runtime average | speed up |
|
interpreter |
[ go to top ]