Difference between revisions of "Exp3 8"
Jump to navigation
Jump to search
(Created page with "= Description = = The code = = Evaluation = == Reductions and Timing == == Garbage Collection ==") |
|||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
= Description = | = Description = | ||
| − | + | Exp3_8 is a program from the nofib benchmark set that calculates 3^8 symbolically, using Church numbers. | |
| + | The source code for Version 1 is available on [https://github.com/fun-isa/fun-bmarks/blob/main/src/exp3_8/exp3_8.fn github]. | ||
| + | |||
| + | = Data Structures = | ||
| + | |||
| + | data Nat = Succ a | Zero; | ||
| + | data Bool = False | True ; | ||
| + | |||
| + | n1 = Succ Zero; | ||
| + | n2 = Succ(n1); | ||
| + | n3 = Succ(n2); | ||
| + | n4 = Succ(n3); | ||
| + | n5 = Succ(n4); | ||
| + | n6 = Succ(n5); | ||
| + | n7 = Succ(n6); | ||
| + | n8 = Succ(n7); | ||
| + | n9 = Succ(n8); | ||
| + | n10 = Succ(n9); | ||
| + | |||
| + | = Auxiliary Functions = | ||
| + | |||
| + | put x = out (extern 0x10a1fafa) x; | ||
| + | |||
| + | |||
| + | = Version 1 : Recursive = | ||
| + | |||
| + | add x y = x y (\a -> Succ (add a y)); | ||
| + | mul x y = y (Zero) (\a -> (add (mul x a) x)); | ||
| + | pow x y = y (Succ Zero) (\a -> mul x (pow x a)); | ||
| + | |||
| + | toInt n = n (0) (\a -> (+ 1 (toInt a))); | ||
| + | |||
| + | main = put (toInt (pow n3 n8)) True; | ||
| + | |||
| + | [[File:Exp38.png |600px|frameless]] | ||
| + | |||
| + | = Version 2 : Explicit Catamorphism = | ||
| + | fmap_nat f n = n Zero (\a -> Succ (f a )); | ||
| + | cata f alg x = alg (f (cata f alg) x); | ||
| + | natC z next = cata fmap_nat (\b -> b z (\a -> next a) ); | ||
| + | |||
| + | pow x y = natC (Succ Zero) (mul x) y; | ||
| + | add x y = natC y Succ x; | ||
| + | mul x y = natC Zero (add y) x; | ||
| + | |||
| + | toInt = cata fmap_nat (\x -> x 0 (+ 1)) ; | ||
| + | |||
| + | main = put (toInt (pows n3 n8)) True; | ||
| + | |||
| + | = Version 3 : Mendler-style Catamorphism = | ||
| + | natC z f = Fix (\s n -> n z (\a -> f (s a))); | ||
| + | |||
| + | pow x y = natC (Succ Zero) (mul x) y; | ||
| + | add x y = natC y Succ x; | ||
| + | mul x y = natC Zero (add y) x; | ||
| + | |||
| + | main = put (toInt (pows n3 n8)) True; | ||
= Evaluation = | = Evaluation = | ||
| Line 8: | Line 64: | ||
== Reductions and Timing == | == Reductions and Timing == | ||
| − | = | + | {| class="wikitable" |
| + | |- | ||
| + | ! | ||
| + | ! Recursive | ||
| + | ! Catamorphism | ||
| + | ! Mendler-style | ||
| + | |- | ||
| + | | Reductions | ||
| + | | 16175369 | ||
| + | | 492059 | ||
| + | | 314921 | ||
| + | |- | ||
| + | | Traversal steps | ||
| + | | 40400688 | ||
| + | | 1053012 | ||
| + | | 692175 | ||
| + | |- | ||
| + | | Node Allocations | ||
| + | | 40367860 | ||
| + | | 925075 | ||
| + | | 524872 | ||
| + | |- | ||
| + | | Total cycles* | ||
| + | | 88900524 | ||
| + | | 2214275 | ||
| + | | 1505722 | ||
| + | |} | ||
| + | \*Total cycle count include operations that take CPU time but are not considered combinators, such as links, i/o and garbage collection. This reference value was obtained with a development version of the [[Implementations | Blackbird]] CPU. | ||
Latest revision as of 09:47, 8 August 2022
Description
Exp3_8 is a program from the nofib benchmark set that calculates 3^8 symbolically, using Church numbers.
The source code for Version 1 is available on github.
Data Structures
data Nat = Succ a | Zero; data Bool = False | True ; n1 = Succ Zero; n2 = Succ(n1); n3 = Succ(n2); n4 = Succ(n3); n5 = Succ(n4); n6 = Succ(n5); n7 = Succ(n6); n8 = Succ(n7); n9 = Succ(n8); n10 = Succ(n9);
Auxiliary Functions
put x = out (extern 0x10a1fafa) x;
Version 1 : Recursive
add x y = x y (\a -> Succ (add a y)); mul x y = y (Zero) (\a -> (add (mul x a) x)); pow x y = y (Succ Zero) (\a -> mul x (pow x a));
toInt n = n (0) (\a -> (+ 1 (toInt a)));
main = put (toInt (pow n3 n8)) True;
Version 2 : Explicit Catamorphism
fmap_nat f n = n Zero (\a -> Succ (f a )); cata f alg x = alg (f (cata f alg) x); natC z next = cata fmap_nat (\b -> b z (\a -> next a) );
pow x y = natC (Succ Zero) (mul x) y; add x y = natC y Succ x; mul x y = natC Zero (add y) x; toInt = cata fmap_nat (\x -> x 0 (+ 1)) ;
main = put (toInt (pows n3 n8)) True;
Version 3 : Mendler-style Catamorphism
natC z f = Fix (\s n -> n z (\a -> f (s a))); pow x y = natC (Succ Zero) (mul x) y; add x y = natC y Succ x; mul x y = natC Zero (add y) x; main = put (toInt (pows n3 n8)) True;
Evaluation
Reductions and Timing
| Recursive | Catamorphism | Mendler-style | |
|---|---|---|---|
| Reductions | 16175369 | 492059 | 314921 |
| Traversal steps | 40400688 | 1053012 | 692175 |
| Node Allocations | 40367860 | 925075 | 524872 |
| Total cycles* | 88900524 | 2214275 | 1505722 |
\*Total cycle count include operations that take CPU time but are not considered combinators, such as links, i/o and garbage collection. This reference value was obtained with a development version of the Blackbird CPU.