Jump to...
-
Off-line partial evaluator...
- Benchamark list
Example 3:
pascal's triangle
[ Original program ] [ Annotated program ] [ Specialized program ] [ Runtimes ]
import Benchmark (runBenchmark)
data Nat = Z | S Nat
main x = pascal x (S(S(S(S(S(S(S(S Z))))))))
pascal row col = cond col row
cond Z _ = (S Z)
cond (S c) (S r) =
ite (eq c r) (S Z) (sum (pascal r c) (pascal r (S c)))
ite True x _ = x
ite False _ y = y
eq Z Z = True
eq Z (S _ ) = False
eq (S _) Z = False
eq (S x) (S y) = eq x y
sum Z y = y
sum (S x) y = S(sum x y)
--tools
n2s n = if n==0 then Z else S (n2s (n-1))
s2n Z = 0
s2n (S n)=1+s2n n
--for annotations
GEN x = x
bench = runBenchmark 10 (\_ -> print (x =:= main (n2s 17) ))
where x free
import Benchmark (runBenchmark)
data Nat = Z | S Nat
main x = pascal x (S(S(S(S(S(S(S(S Z))))))))
pascal row col = cond col row
cond Z _ = (S Z)
cond (S c) (S r) =
ite (GEN (eq c r)) (S Z) (GEN ( sum (GEN (pascal r c)) (GEN (pascal r (S c)))))
ite True x _ = x
ite False _ y = y
eq Z Z = True
eq Z (S _ ) = False
eq (S _) Z = False
eq (S x) (S y) = eq x y
sum Z y = y
sum (S x) y = S(sum x y)
n2s n = if n==0 then Z else S (n2s (n-1))
s2n Z = 0
s2n (S n)=1+s2n n
--for annotations
GEN x = x
bench = runBenchmark 10 (\_ -> print (x =:= main (n2s 17) ))
where x free
Specialized program
[ go top ]
prelude> :l pascal_pe
Compiled Curry program 'pascal_pe.pl' is up-to-date.
pascal_pe(module: pascal)> :show
No source program file available, generating source from FlatCurry...
-- Program file: pascal_pe
module pascal(Nat(Z,S),pascal,cond,ite,eq,sum,n2s,s2n,GEN,bench,main,pascal_pe1,
sum_pe11,pascal_pe12,pascal_pe13,pascal_pe14,pascal_pe15,pascal_pe16,pascal_pe17,
pascal_pe18) where
import Benchmark
import System
data Nat = Z | S Nat
pascal :: Nat -> Nat -> Nat
pascal v0 v1 = cond v1 v0
cond :: Nat -> Nat -> Nat
cond eval flex
cond Z v1 = S Z
cond (S v2) (S v3) = ite (GEN (eq v2 v3)) (S Z) (GEN (sum (GEN (pascal v3 v2))
(GEN (pascal v3 (S v2)))))
ite :: Bool -> a -> a -> a
ite eval flex
ite True v1 v2 = v1
ite False v1 v2 = v2
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
sum :: Nat -> Nat -> Nat
sum eval flex
sum Z v1 = v1
sum (S v2) v1 = S (sum v2 v1)
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)
GEN :: a -> a
GEN v0 = v0
bench :: IO ()
bench = Benchmark.runBenchmark 10 (pascal_lambda0_0 v0) where v0 free
pascal_lambda0_0 :: Nat -> Int -> IO ()
pascal_lambda0_0 v0 v1 = print (v0 =:= (main (n2s 17)))
main :: b -> a
main v0 = pascal_pe1 v0
pascal_pe1 :: b -> a
pascal_pe1 eval flex
pascal_pe1 (S v206) = fcase (fcase v206 of
Z -> False
S v408 -> fcase v408 of
Z -> False
S v608 -> fcase v608 of
Z -> False
S v808 -> fcase v808 of
Z -> False
S v1008 -> fcase v1008 of
Z -> False
S v1208 -> fcase v1208 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe12 v206) (pascal_pe1 v206)
sum_pe11 :: c -> b -> a
sum_pe11 eval flex
sum_pe11 Z v214 = v214
sum_pe11 (S v404) v214 = S (sum_pe11 v404 v214)
pascal_pe12 :: b -> a
pascal_pe12 eval flex
pascal_pe12 (S v506) = fcase (fcase v506 of
Z -> False
S v608 -> fcase v608 of
Z -> False
S v808 -> fcase v808 of
Z -> False
S v1008 -> fcase v1008 of
Z -> False
S v1208 -> fcase v1208 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe13 v506) (pascal_pe12 v506)
pascal_pe13 :: b -> a
pascal_pe13 eval flex
pascal_pe13 (S v806) = fcase (fcase v806 of
Z -> False
S v808 -> fcase v808 of
Z -> False
S v1008 -> fcase v1008 of
Z -> False
S v1208 -> fcase v1208 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe14 v806) (pascal_pe13 v806)
pascal_pe14 :: b -> a
pascal_pe14 eval flex
pascal_pe14 (S v1106) = fcase (fcase v1106 of
Z -> False
S v1008 -> fcase v1008 of
Z -> False
S v1208 -> fcase v1208 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe15 v1106) (pascal_pe14 v1106)
pascal_pe15 :: b -> a
pascal_pe15 eval flex
pascal_pe15 (S v1406) = fcase (fcase v1406 of
Z -> False
S v1208 -> fcase v1208 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe16 v1406) (pascal_pe15 v1406)
pascal_pe16 :: b -> a
pascal_pe16 eval flex
pascal_pe16 (S v1706) = fcase (fcase v1706 of
Z -> False
S v1408 -> fcase v1408 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe17 v1706) (pascal_pe16 v1706)
pascal_pe17 :: b -> a
pascal_pe17 eval flex
pascal_pe17 (S v2006) = fcase (fcase v2006 of
Z -> False
S v1608 -> fcase v1608 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (pascal_pe18 v2006) (pascal_pe17 v2006)
pascal_pe18 :: b -> a
pascal_pe18 eval flex
pascal_pe18 (S v2306) = fcase (fcase v2306 of
Z -> True
S v1806 -> False
) of
True -> S Z
False -> sum_pe11 (S Z) (pascal_pe18 v2306)
-- end of module pascal_pe
| program | original runtime average | specialized runtime average | speed up |
|
pascal |
[ go to top ]