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

Jump to...

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

Example: allones

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

Original program

The goal of this program is convert an integer list to a list of ones. This is an example to improve Wadler's deforestation. Deforestation algorithms do not recognize that an expression contains two or more functions that consume tha same data structure. This can be improved eliminating unnecessary traversals.

 
import Benchmark(runBenchmark)

data Nat = Z | S Nat

main x = f (1:2:3:4:5:6:7:8:9:1:2:3:4:5:6:7:8:9:0:x)

f l = allones (length2 l)

allones Z = []
allones (S x) = 1 :(allones x)

length2 [] = Z
length2 (_:xs) = S (length2 xs)

--for annotations
GEN x = x

bench = runBenchmark 10 (\_ -> print (x =:= main  [1..50000]    )  )
        where x free
 

The function to specialize is main x. Here we know the first 19 elements of the list.

Annotated program [ go top ]

The annotated version of allones program, does not suffer changes w.r.t. the original code. Reason is, it already accomplishes the characteristics of "non-increasing" program [RSV05].

 
import Benchmark(runBenchmark)

data Nat = Z | S Nat

main x = f (1:2:3:4:5:6:7:8:9:1:2:3:4:5:6:7:8:9:0:x)

f l = allones (length2 l)

allones Z = []
allones (S x) = 1 :(allones x)

length2 [] = Z
length2 (_:xs) = S (length2 xs)

--for annotations
GEN x = x

bench = runBenchmark 10 (\_ -> print (x =:= main  [1..50000]    )  )
        where x free

Specialized program [ go top ]

Inside PAKCS environment, load OffPEval, then compute mix "examples/allones", and finally, load the partially evaluated program , thus:

 
prelude> :l allones_pe
Compiled Curry program 'allones_pe.pl' is up-to-date.

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

-- Program file: allones_pe
module allones(Nat(Z,S),f,allones,length2,GEN,bench,main,allones_pe1) where

import Benchmark

data Nat = Z | S Nat

f :: [a] -> [Int]
f v0 = allones (length2 v0)

allones :: Nat -> [Int]
allones eval flex
allones Z = []
allones (S v1) = 1 : (allones v1)

length2 :: [a] -> Nat
length2 eval flex
length2 [] = Z
length2 (v1 : v2) = S (length2 v2)

GEN :: a -> a
GEN v0 = v0

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

allones_lambda0_0 :: [Int] -> Int -> IO ()
allones_lambda0_0 v0 v1 = print (v0 =:= (main (enumFromTo 1 50000)))

main :: b -> a
main v0 = 1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : (1 : 
         (1 : (1 : (1 : (1 : (1 : (1 : (allones_pe1 v0)))))))))))))))))))

allones_pe1 :: b -> a
allones_pe1 eval flex
allones_pe1 [] = []
allones_pe1 (v7903 : v7904) = 1 : (allones_pe1 v7904)


-- end of module allones_pe      
          
        

Let us observe in specialized program that deforestation has been performed, also, allones_pe1 will traverse only one time the data structure, also, the partially known list has been computed, appearing 19 ones, the static values were processed.

Runtimes [ go top ]

[ go to top ]