Off-line narrowing-driven partial evaluator for inductively sequential programs

Jump to...

- Off-line partial evaluator...
- Benchamark list

Example: fibonacci

[ Original program ]  [ Annotated program ]  [ Specialized program ] [ Runtimes ]

Original program

This program computes the classical Fibonacci number series.

 
         
import Benchmark (runBenchmark)

data Nat = Z | S Nat

main n = fib (S(S(S(S(S n)))))

fib Z         = S Z
fib (S Z)     = S Z
fib (S (S n)) = sum (fib (S n)) (fib n)

sum Z  y = y
sum (S n) y = S (sum n y)


--for annotations
GEN x = x

bench  = runBenchmark 10 (\_ -> print (x =:= main (n2s 17)))
          where x free


n2s n = if n==0 then Z else S (n2s (n-1))
        

Annotated program [ go top ]

The annotation stage, returns a function fib with its nested function calls marked with identity function GEN.

 
import Benchmark (runBenchmark)

data Nat = Z | S Nat

main n = fib (S(S(S(S(S n)))))

fib Z         = S Z
fib (S Z)     = S Z
fib (S (S n)) = sum (GEN (fib (S n))) (GEN (fib n))

sum Z  y = y
sum (S n) y = S (sum n y)


--for annotations
GEN x = x

bench  = runBenchmark 10 (\_ -> print (x =:= main (n2s 17)))
          where x free


n2s n = if n==0 then Z else S (n2s (n-1))
       

We are going to specialize for numbers greater than or equal to 5 (expressed as Peano natural numbers).

Specialized program [ go top ]

In PAKCS environment and once the specialized version is loaded with :show utility, we can see:

prelude> :l fibo_pe

fibo_pe(module: fibo)> :show
No source program file available, generating source from FlatCurry...

-- Program file: fibo_pe
module fibo(Nat(Z,S),fib,sum,GEN,bench,n2s,main,sum_pe1,fib_pe2,fib_pe3,fib_pe4,
                 fib_pe5,fib_pe6) where

import Benchmark

data Nat = Z | S Nat

fib :: Nat -> Nat
fib eval flex
fib Z = S Z
fib (S Z) = S Z
fib (S (S v2)) = sum (GEN (fib (S v2))) (GEN (fib v2))

sum :: Nat -> Nat -> Nat
sum eval flex
sum Z v1 = v1
sum (S v2) v1 = S (sum v2 v1)

GEN :: a -> a
GEN v0 = v0

bench :: IO ()
bench = Benchmark.runBenchmark 10 (fibo_lambda0_0 v0) where v0 free

n2s :: Int -> Nat
n2s v0 = 
   if v0 == 0
   then Z
   else S (n2s (v0 - 1))

fibo_lambda0_0 :: Nat -> Int -> IO ()
fibo_lambda0_0 v0 v1 = print (v0 =:= (main (n2s 17)))

main :: b -> a
main v0 = sum_pe1 (fib_pe2 v0) (fib_pe3 v0)

sum_pe1 :: c -> b -> a
sum_pe1 eval flex
sum_pe1 Z v6 = v6
sum_pe1 (S v404) v6 = S (sum_pe1 v404 v6)

fib_pe2 :: b -> a
fib_pe2 v0 = sum_pe1 (sum_pe1 (fib_pe4 v0) (fib_pe5 v0)) (fib_pe4 v0)

fib_pe3 :: b -> a
fib_pe3 v0 = sum_pe1 (fib_pe4 v0) (fib_pe5 v0)

fib_pe4 :: b -> a
fib_pe4 v0 = sum_pe1 (fib_pe5 v0) (fib_pe6 v0)

fib_pe5 :: b -> a
fib_pe5 eval flex
fib_pe5 Z = S Z
fib_pe5 (S v1304) = sum_pe1 (fib_pe5 v1304) (fib_pe6 v1304)

fib_pe6 :: b -> a
fib_pe6 eval flex
fib_pe6 Z = S Z
fib_pe6 (S Z) = S Z
fib_pe6 (S (S v1504)) = sum_pe1 (fib_pe5 v1504) (fib_pe6 v1504)


-- end of module fibo_pe

Some unfoldings have been done, e.g. we find a function that calls sum_pe1(sum_pe1 .., while the original program always call recursively to fib. We understand this is an example suitable for tupling, however we obtain a light improvement in performance with our offline partial evaluation method.

Runtimes [ go top ]

[ go to top ]