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

Jump to...

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

Example: multiple append

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

Original program

multiple append is a program that presents a composition of functions, is a typical Wadler's deforestation case.

import Benchmark(runBenchmark)

main x = app (app (app ( app x [1,2,3] ) [] ) [] ) []

app [] x = x
app (x:xs) ys = x : app xs ys


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

One argument of innermost app, is known, the list [1,2,3].

Annotated program [ go top ]

Program accomplishes conditions of RSV to direct a finite partial evaluation process. It need not marks.

 
import Benchmark(runBenchmark)


main x = app (app (app ( app  x [1,2,3] ) [] ) [] ) []

app []     x  = x
app (x:xs) ys = x : app xs ys


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

Specialized program [ go top ]

In PAKCS, and once loaded OffPeval, run mix "examples/multapp", now you can load and show the specialized program.

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

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

-- Program file: multapp_pe
module multapp(app,bench,main,app_pe1) where

import Benchmark


app :: [a] -> [a] -> [a]
app eval flex
app [] v1 = v1
app (v2 : v3) v1 = v2 : (app v3 v1)

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

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

main :: b -> a
main v0 = app_pe1 v0

app_pe1 :: b -> a
app_pe1 eval flex
app_pe1 [] = [1,2,3]
app_pe1 (v405 : v406) = v405 : (app_pe1 v406)

-- end of module multapp_pe
      

Now, intermediate structures will not be formed, because deforestation has been applied at specialization time.

Runtimes [ go top ]

[ go to top ]