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

Jump to...

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

Example: kmp

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

Original program

This is an exercise of "KMP test" to our offline partial evaluator. The Knuth-Morris-Pratt string-matching algorithm (KMP) tests whether a pattern string p occurs in a data string s. Indeed, this "KMP-test" has become a popular benchmark for partial evaluators and related systems Here we present a naive algorithm for this.

 
import Benchmark (runBenchmark)

data Letter = A | B
                 
main  ss = match [A,A,B] ss

match p s = loop p s p s

loop []     _      _  _  = True
loop (_:_)  []     _  _  = False
loop (p:ps) (s:ss) op os = ite (eq p s)  (loop ps ss op os) (next op os)

next _  [] = False
next op (_:ss) = loop op ss op ss

ite True  x _ = x
ite False _ y = y

eq A A = True
eq B B = True
eq A B = False
eq B A = False

--for generalizations:
GEN x = x

bench = runBenchmark 10 (\_ -> print (main  (makeList 10000)))

makeList n = if n==0 then [B] else A : makeList (n-1)        

Annotated program [ go top ]

According to our annotation algorithm we should mark those expressions that breaks linearity and also, it does not allow nested  function calls.

In order to get best results, here we make marks at hand. Thus, we can see at third rule of loop, that there is a function that breaks linearity condition.

 
import Benchmark (runBenchmark)

data Letter = A | B
                 
main  ss = match [A,A,B] ss

match p s = loop p s (GEN p) (GEN s)

loop []     _      _  _  = True
loop (_:_)  []     _  _  = False
loop (p:ps) (s:ss) op os = ite (eq p s) (GEN (loop ps ss op os)) (GEN (next op os))

next _  [] = False
next op (_:ss) = loop op ss (GEN op) (GEN ss)

ite True  x _ = x
ite False _ y = y

eq A A = True
eq B B = True
eq A B = False
eq B A = False

--for generalizations:
GEN x = x


bench = runBenchmark 10 (\_ -> print (main  (makeList 10000)))

makeList n = if n==0 then [B] else A : makeList (n-1)

          
        

Specialized program [ go top ]

In PAKCS we load OffPeval and then do "mix examples/kmp", then we load and show the specialized program, as follows:

 
prelude> :l kmp_pe
Compiling './kmp_pe.fcy' into Prolog program 'kmp_pe.pl'...

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

-- Program file: kmp_pe
module kmp(Letter(A,B),match,loop,next,ite,eq,GEN,bench,makeList,main,loop_pe1,
                  next_pe7,loop_pe8) where

import Benchmark

data Letter = A | B

match :: [Letter] -> [Letter] -> Bool
match v0 v1 = loop v0 v1 (GEN v0) (GEN v1)

loop :: [Letter] -> [Letter] -> [Letter] -> [Letter] -> Bool
loop eval flex
loop [] v1 v2 v3 = True
loop (v4 : v5) [] v2 v3 = False
loop (v4 : v5) (v6 : v7) v2 v3 = ite (eq v4 v6) (GEN (loop v5 v7 v2 v3)) (GEN (next v2 v3))

next :: [Letter] -> [Letter] -> Bool
next eval flex
next v0 [] = False
next v0 (v2 : v3) = loop v0 v3 (GEN v0) (GEN v3)

ite :: Bool -> a -> a -> a
ite eval flex
ite True v1 v2 = v1
ite False v1 v2 = v2

eq :: Letter -> Letter -> Bool
eq eval flex
eq A A = True
eq A B = False
eq B B = True
eq B A = False

GEN :: a -> a
GEN v0 = v0

bench :: IO ()
bench = Benchmark.runBenchmark 10 kmp_lambda0_0

makeList :: Int -> [Letter]
makeList v0 = 
   if v0 == 0
   then [B]
   else A : (makeList (v0 - 1))

kmp_lambda0_0 :: Int -> IO ()
kmp_lambda0_0 v0 = print (main (makeList 10000))

main :: b -> a
main v0 = loop_pe1 v0 [A,A,B] v0

loop_pe1 :: d -> c -> b -> a
loop_pe1 eval flex
loop_pe1 [] v3 v4 = False
loop_pe1 (v213 : v214) v3 v4 = fcase (fcase A of
     A -> fcase v213 of
       A -> True
       B -> False
    
     B -> fcase v213 of
       B -> True
       A -> False
    
  ) of
     True -> fcase v214 of
       [] -> False
       v413 : v414 -> fcase (fcase A of
         A -> fcase v413 of
           A -> True
           B -> False
        
         B -> fcase v413 of
           B -> True
           A -> False
        
      ) of
         True -> fcase v414 of
           [] -> False
           v613 : v614 -> fcase (fcase B of
             A -> fcase v613 of
               A -> True
               B -> False
            
             B -> fcase v613 of
               B -> True
               A -> False
            
          ) of
             True -> True
             False -> next_pe7 v3 v4
          
        
         False -> next_pe7 v3 v4
      
    
     False -> next_pe7 v3 v4
  

next_pe7 :: c -> b -> a
next_pe7 eval flex
next_pe7 v3 [] = False
next_pe7 v3 (v805 : v806) = loop_pe8 v3 v806 v3 v806

loop_pe8 :: e -> d -> c -> b -> a
loop_pe8 eval flex
loop_pe8 [] v806 v816 v817 = True
loop_pe8 (v911 : v912) [] v816 v817 = False
loop_pe8 (v911 : v912) (v913 : v914) v816 v817 = fcase (fcase v911 of
     A -> fcase v913 of
       A -> True
       B -> False
    
     B -> fcase v913 of
       B -> True
       A -> False
    
  ) of
     True -> loop_pe8 v912 v914 v816 v817
     False -> next_pe7 v816 v817
  
-- end of module kmp_pe

We obtain improvement however, we do not pass the kmpt test, to overcome this drawback, the information of a traditional binding-time analysis (i.e., specifying which componentes of the initial call are dynamic or static) should be
integrated into the partial evaluator (currently, only termination is taken into account with no assumption on the static data).

Runtimes [ go top ]

[ go to top ]