Improving offline narrowing-driven partial evaluation using size-change graphs

Jump to...

- schg page

Example: fibonacci's function

[ Original program ]  [ Annotated program ]

Original program

This is the known function: Fibonacci, which is computed over natural numbers.

 
         
data Nat = Z | S Nat

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)

        

Annotated program [ go top ]

Below, the annotated program. The annotation corresponding to function fib, is added in order to enforce right linearity. No annotations caused by size-change graphs are introduced..

 
module fiboS where

data Nat
     = Z
     | S Nat

GEN :: a -> a
GEN x
     | success
     = x

fib :: Nat -> Nat
fib Z = S Z
fib (S Z) = S Z
fib (S (S n)) = sum (fib (S n)) (fib (GEN n))

sum :: Nat -> Nat -> Nat
sum Z y = y
sum (S n) y = S (sum n y)

[ go top ]