Specialization of interpreters
You may compile through the specialization of an interpreter that runs just one fixed-source program, producing a target program in the partial evaluator’s output language, besides compiling by partial evaluation always generates correct object code (Jones et al., 1993). So if we have a FlatCurry program pfcy that accepts a function call with static and dynamic data arguments included into the same program, and a program intCy written in Curry language to interpret programs in the intermediate FlatCurry language that produces target programs tgtfcy in FlatCurry also. Thus we may represent a particular interpretation process as:
tgtfcy= [[ intCy]] [pfcy]
Our offline partial evaluator mixpo accepts annotated programs in FlatCurry, thus the first Futamura projection (very similar to the definition of (Jones et al., 1993)) may be represented like:
tgtfcy= [[ mixpo]] [intCy pfcy]fcy
We include the program to be interpreted and a call to this program into the same interpreter as arguments of the interpreter’s call, you can see in the simple interpreter example from previous page, in the right hand side of main function definition, i.e., the ieval function call. In (Andersen, 1992) also use different data (types) structures for programs and data input in order to compile by partial evaluation.
Let us analyze the specialization of an interpreter with the use of the conjunction (sequential); the built-in type &&. The interpreter function main looks like:
{-
main = (3 == 3) && (1 == 1)
-}
main = ieval True [Func ("andexam","main") 0 Public (TCons ("Prelude","Bool") [ ]) (Rule [ ] (Comb FuncCall ("Prelude","&&") [Comb FuncCall ("Prelude","==") [Lit (Intc 3),Lit (Intc 3)], Comb FuncCall ("Prelude","==") [Lit (Intc 1),Lit (Intc 1)]]))] (Comb FuncCall ("andexam","main") [ ])
If we require to PAKCS the evaluation of the expression (3 == 3) && (1 == 1), “True” is the result. In order to interpret this expression we need to make some changes, first the evaluation of functions must be able to process the built-in type &&, so we change this part of interpreter code:
ieval top funs (Comb FuncCall (mn,f) es) =
if mn == "Prelude"
then if f == "failed"
then Comb FuncCall (mn,f) es
else if f == "=="
then (ieval_EQ top funs (mn,f) es)
else case f of
"+" -> ieval_ARITH top funs (mn,f) es
"-" -> ieval_ARITH top funs (mn,f) es
"*" -> ieval_ARITH top funs (mn,f) es
"&&" -> ieval_SAND top funs (mn,f) es
else ieval top funs (matchiRHS funs (mn,f) es)
Notice that we added the call ieval_SAND precisely to assess the referenced built-in. This last function definition is shown below:
ieval_SAND :: Bool -> [FuncDecl] -> QName -> [Expr] -> Expr
ieval_SAND top fns (mn,fn) [e1,e2] =
case (ieval True fns e1) of
(Comb ConsCall (Pre,Tru) [ ])-> (ieval top fns e2)
(Comb ConsCall (Pre,Fal) [ ]) -> (Comb ConsCall (Pre,Fal) [ ])
From experience we have seen a string specializes more easily if we define simple declarations. So we have defined the following declarations:
Pre = "Prelude"
Fal = "False"
Tru = "True"
After specializing the interpreter with the above changes we obtain the following program:
module int_sand_ann(main,ieval_pe1) where
import FlatCurry
main :: a
main = ieval_pe1
ieval_pe1 :: a
ieval_pe1 eval rigid
ieval_pe1 = case (Comb ConsCall ("Prelude","True") [ ]) of
Comb v141 v142 v143 -> case v141 of
ConsCall -> case v142 of
(v144,v145) -> case v143 of
[ ] -> Comb ConsCall ("Prelude","True") [ ]
You may verify the result loading this FlatCurry program to PAKCS then requiring the evaluation of main function that:
Comb ConsCall ("Prelude","True") [ ]
is the result of the requirement.
So far we have seen the partial evaluation of simple programs without dynamic arguments, now see the specialization of the interpreter containing the fibonacci program for natural numbers (shown from previous page). As in the latter interpreter partial evaluation we must change the program to interpret. So the interpreter function main now looks like:
main x = ieval True [Func ("fib7","main") 1 Public (FuncType (TCons ("fib7","Nat") [ ]) (TCons ("fib7","Nat") [ ])) (Rule [1] (Comb FuncCall ("fib7","prod") [Comb FuncCall ("fib7","fib") [Var 1],Comb FuncCall ("fib7","fib") [Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","Z") [ ]]]]]]]])), Func ("fib7","fib") 1 Public (FuncType (TCons ("fib7","Nat") [ ]) (TCons ("fib7","Nat") [ ])) (Rule [1] (Case Rigid (Var 1) [Branch (Pattern ("fib7","Z") [ ]) (Comb ConsCall ("fib7","Z") [ ]),Branch (Pattern ("fib7","S") [2]) (Case Rigid (Var 2) [Branch (Pattern ("fib7","Z") [ ]) (Comb ConsCall ("fib7","S") [Comb ConsCall ("fib7","Z") [ ]]),Branch (Pattern ("fib7","S") [3]) (Comb FuncCall ("fib7","sum") [Comb FuncCall ("fib7","fib") [Comb ConsCall ("fib7","S") [Var 3]],Comb FuncCall ("fib7","fib") [Var 3]])])])), Func ("fib7","prod") 2 Public (FuncType (TCons ("fib7","Nat") [ ]) (FuncType (TCons ("fib7", "Nat") [ ]) (TCons ("fib7","Nat") [ ]))) (Rule [1,2] (Case Rigid (Var 1) [Branch (Pattern ("fib7","Z") [ ]) (Comb ConsCall ("fib7", "Z") [ ]),Branch (Pattern ("fib7","S") [3]) (Comb FuncCall ("fib7" ,"sum") [Var 2,Comb FuncCall ("fib7","prod") [Var 3,Var 2]])])), Func ("fib7","sum") 2 Public (FuncType (TCons ("fib7","Nat") [ ]) (FuncType (TCons ("fib7","Nat") [ ]) (TCons ("fib7","Nat") [ ]))) (Rule [1,2] (Case Rigid (Var 1) [Branch (Pattern ("fib7","Z") [ ]) (Var 2),Branch (Pattern ("fib7","S") [3]) (Comb ConsCall ("fib7", "S") [Comb FuncCall ("fib7","sum") [Var 3,Var 2]])]))] (Comb FuncCall ("fib7","main") [x])
You can see the x of function main this variable represents a dynamic value of the interpreter, i.e, a value probably known at partial evaluation time. This dynamic value spreads through the interpreter when you run the BTA, so our BTA returns the following division:
[("main",1,[D]),("ieval",3,[S,S,D]),("ieval_ARITH",2,[D,D]), ("ieval_EQ",1,[D]), ("ieval_args",2,[S,D]), ("matchBranch",3,[D,D,D]), ("matchBranchLit",2,[D,D]), ("matchiRHS",3,[S,D,D]), ("matchRHS_aux",2,[S,D]),("substituteAll",3,[D,D,D]), ("replaceVar",3,[D,D,D]), ("substituteAllArgs",3,[D,D,D]), ("substituteAllCases",3,[D,D,D]), ("substituteAllCase",3,[D,D,D])]
The size-change analysis (SCA) yields as result thirteen idempotent multigraphs, the following functions: main, ieval_EQ, ieval_ARITH and matchRHS_aux are not involved in the result of SCA, i.e., do not have idempotent multigraphs, so the calls to these functions are annotated with UNF (during the annotation process) because they do not introduce introduce infinite loops. matchiRHS has an idempotent multigraph but it’s first edge, i.e., that corresponds to its first argument, has a label with strict order of reduction (>) and is static. Therefore the matchiRHS function calls are also labeled with UNF. The rest of the function calls are annotated with MEM. Therefore, even without taking into account the vector of generalization, we could deduce that the specialization of this interpreter may not be very good because it has too many functions that cannot be unfolded at the time of the partial evaluation.
However, generally the result of the partial evaluation of our interpreters that accept a call with dynamic arguments; is a mixture of the interpreter and the source program to interpret, containing parts derived from both (Jones et al., 1993). By instance, after the specialization of the interpreter, the rule of the definition main becomes the following:
main :: b -> a
main v0 = ieval_pe1 (Comb FuncCall ("fib7","main") [v0])
Very nice specialization, but matchiRHS now has four substitutions identified in the right hand side; the branches to unfold: main, fib, prod and sum (see below the specialized interpreter). We have also obtained two cases for ieval definition, i.e., that has grown a bit the size of the code obtained. We would expect to be executed faster than the original interpretation at least, but we have reached almost the same runtime average. The interpretation of the program has certainly improved because the unfold process has been transferred directly to the function that is responsible for do it (matchiRHS), i.e., some steps of interpretation have been saved. Although in this case, specialization has not sufficiently reduced the interpreter code because most of the functions cannot be unfold to a value.
To know the rest of explanation about the implementation of interpreters you may see this working draft
Go back
|
Example of a specialized interpreter |
int_fib8_ann_pe(module: int_fib8_ann)> :show No source program file available, generating source from FlatCurry...
% restoring /usr/local/pakcs/tools/genint.state... -- Program file: int_fib8_ann_pe module int_fib8_ann(Nat(Z,S),UNF,MEM,ieval,ieval_ARITH,ieval_EQ,ieval_args,ievalListaux,matchBranch, matchBranchLit,matchiRHS,matchRHS_aux,substituteAll,replaceVar,substituteAllArgs,substituteAllCases, substituteAllCase,getExecTime,runBenchmark,bench,main,ieval_pe1,ieval_args_pe2,ieval_pe4,ieval_EQ_pe8, ieval_args_pe11,ieval_ARITH_pe13,matchiRHS_pe19,substituteAll_pe22,replaceVar_pe23, substituteAllArgs_pe24,substituteAllCases_pe25,matchBranch_pe37,matchBranchLit_pe38) where
import FlatCurry import System
data Nat = Z | S Nat
UNF :: a -> a UNF v1 = v1
MEM :: a -> a MEM v1 = v1
main :: b -> a main v0 = ieval_pe1 (FlatCurry.Comb FlatCurry.FuncCall ("fib7","main") [v0])
ieval_pe1 :: b -> a ieval_pe1 eval rigid&flex -- CONFLICTING!! ieval_pe1 (FlatCurry.Var v42) = FlatCurry.Var v42 ieval_pe1 (FlatCurry.Lit v43) = FlatCurry.Lit v43 ieval_pe1 (FlatCurry.Comb FlatCurry.ConsCall v45 v46) = FlatCurry.Comb FlatCurry.ConsCall v45 (ieval_args_pe2 v46) ieval_pe1 (FlatCurry.Comb FlatCurry.FuncCall (v47,v48) v46) = case (v47 == "Prelude") of True -> case (v48 == "failed") of True -> FlatCurry.Comb FlatCurry.FuncCall (v47,v48) v46 False -> case (v48 == "==") of True -> ieval_EQ_pe8 (ieval_args_pe2 v46) False -> case v48 of v49 : v50 -> case (v49 == '+') of True -> case v50 of [] -> ieval_ARITH_pe13 v47 v48 (ieval_args_pe2 v46)
False -> case (v49 == '-') of True -> case v50 of [] -> ieval_ARITH_pe13 v47 v48 (ieval_args_pe2 v46)
False -> case (v49 == '*') of True -> case v50 of [] -> ieval_ARITH_pe13 v47 v48 (ieval_args_pe2 v46)
False -> ieval_pe1 (matchiRHS_pe19 v47 v48 v46)
ieval_pe1 (FlatCurry.Case v57 v58 v59) = case (ieval_pe4 v58) of FlatCurry.Comb v60 v61 v62 -> case v60 of FlatCurry.ConsCall -> ieval_pe1 (matchBranch_pe37 v59 v61 v62)
FlatCurry.Lit v65 -> ieval_pe1 (matchBranchLit_pe38 v59 v65)
ieval_args_pe2 :: b -> a ieval_args_pe2 [] = [] ieval_args_pe2 (v758 : v759) = (ieval_pe1 v758) : (ieval_args_pe2 v759)
ieval_pe4 :: b -> a ieval_pe4 eval rigid&flex -- CONFLICTING!! ieval_pe4 (FlatCurry.Var v770) = FlatCurry.Var v770 ieval_pe4 (FlatCurry.Lit v771) = FlatCurry.Lit v771 ieval_pe4 (FlatCurry.Comb FlatCurry.ConsCall v773 v774) = FlatCurry.Comb FlatCurry.ConsCall v773 v774 ieval_pe4 (FlatCurry.Comb FlatCurry.FuncCall (v775,v776) v774) = case (v775 == "Prelude") of True -> case (v776 == "failed") of True -> FlatCurry.Comb FlatCurry.FuncCall (v775,v776) v774 False -> case (v776 == "==") of True -> ieval_EQ_pe8 (ieval_args_pe11 v774) False -> case v776 of v777 : v778 -> case (v777 == '+') of True -> case v778 of [] -> ieval_ARITH_pe13 v775 v776 (ieval_args_pe11 v774)
False -> case (v777 == '-') of True -> case v778 of [] -> ieval_ARITH_pe13 v775 v776 (ieval_args_pe11 v774)
False -> case (v777 == '*') of True -> case v778 of [] -> ieval_ARITH_pe13 v775 v776 (ieval_args_pe11 v774)
False -> ieval_pe4 (matchiRHS_pe19 v775 v776 v774)
ieval_pe4 (FlatCurry.Case v785 v786 v787) = case (ieval_pe4 v786) of FlatCurry.Comb v788 v789 v790 -> case v788 of FlatCurry.ConsCall -> ieval_pe4 (matchBranch_pe37 v787 v789 v790)
FlatCurry.Lit v793 -> ieval_pe4 (matchBranchLit_pe38 v787 v793)
ieval_EQ_pe8 :: b -> a ieval_EQ_pe8 eval rigid&flex -- CONFLICTING!! ieval_EQ_pe8 [FlatCurry.Lit (FlatCurry.Intc v9153),FlatCurry.Lit (FlatCurry.Intc v9157)] = case (v9153 == v9157) of True -> FlatCurry.Comb FlatCurry.ConsCall ("Prelude","True") [] False -> FlatCurry.Comb FlatCurry.ConsCall ("Prelude","False") []
ieval_args_pe11 :: b -> a ieval_args_pe11 [] = [] ieval_args_pe11 (v2193 : v2194) = (ieval_pe4 v2193) : (ieval_args_pe11 v2194)
ieval_ARITH_pe13 :: d -> c -> b -> a ieval_ARITH_pe13 eval rigid&flex -- CONFLICTING!! ieval_ARITH_pe13 v775 (v9162 : v9163) [FlatCurry.Lit (FlatCurry.Intc v9157),FlatCurry.Lit (FlatCurry.Intc v9161)] = case (v9162 == '*') of True -> case v9163 of [] -> FlatCurry.Lit (FlatCurry.Intc (v9157 * v9161))
False -> case (v9162 == '+') of True -> case v9163 of [] -> FlatCurry.Lit (FlatCurry.Intc (v9157 + v9161))
False -> case (v9162 == '-') of True -> case v9163 of [] -> FlatCurry.Lit (FlatCurry.Intc (v9157 - v9161))
matchiRHS_pe19 :: d -> c -> b -> a matchiRHS_pe19 eval rigid matchiRHS_pe19 v775 v776 v774 = case ("main" == v776) of True -> substituteAll_pe22 [1] v774 (FlatCurry.Comb FlatCurry.FuncCall ("fib7","mult") [FlatCurry.Comb FlatCurry.FuncCall ("fib7","fib") [FlatCurry.Var 1],FlatCurry.Comb FlatCurry.FuncCall ("fib7","fib") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","Z") []]]]]]]]) False -> case ("fib" == v776) of True -> substituteAll_pe22 [1] v774 (FlatCurry.Case FlatCurry.Rigid (FlatCurry.Var 1) [FlatCurry.Branch (FlatCurry.Pattern ("fib7","Z") []) (FlatCurry.Comb FlatCurry.ConsCall ("fib7","Z") []),FlatCurry.Branch (FlatCurry.Pattern ("fib7","S") [2]) (FlatCurry.Case FlatCurry.Rigid (FlatCurry.Var 2) [FlatCurry.Branch (FlatCurry.Pattern ("fib7","Z") []) (FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","Z") []]),FlatCurry.Branch (FlatCurry.Pattern ("fib7","S") [3]) (FlatCurry.Comb FlatCurry.FuncCall ("fib7","sum") [FlatCurry.Comb FlatCurry.FuncCall ("fib7","fib") [FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Var 3]],FlatCurry.Comb FlatCurry.FuncCall ("fib7","fib") [FlatCurry.Var 3]])])]) False -> case ("mult" == v776) of True -> substituteAll_pe22 [1,2] v774 (FlatCurry.Case FlatCurry.Rigid (FlatCurry.Var 1) [FlatCurry.Branch (FlatCurry.Pattern ("fib7","Z") []) (FlatCurry.Comb FlatCurry.ConsCall ("fib7","Z") []),FlatCurry.Branch (FlatCurry.Pattern ("fib7","S") [3]) (FlatCurry.Comb FlatCurry.FuncCall ("fib7","sum") [FlatCurry.Var 2,FlatCurry.Comb FlatCurry.FuncCall ("fib7","mult") [FlatCurry.Var 3,FlatCurry.Var 2]])]) False -> case ("sum" == v776) of True -> substituteAll_pe22 [1,2] v774 (FlatCurry.Case FlatCurry.Rigid (FlatCurry.Var 1) [FlatCurry.Branch (FlatCurry.Pattern ("fib7","Z") []) (FlatCurry.Var 2),FlatCurry.Branch (FlatCurry.Pattern ("fib7","S") [3]) (FlatCurry.Comb FlatCurry.ConsCall ("fib7","S") [FlatCurry.Comb FlatCurry.FuncCall ("fib7","sum") [FlatCurry.Var 3,FlatCurry.Var 2]])]) False -> FlatCurry.Comb FlatCurry.FuncCall ("Prelude","failed") []
substituteAll_pe22 :: d -> c -> b -> a substituteAll_pe22 eval rigid substituteAll_pe22 v806 v807 (FlatCurry.Var v2212) = replaceVar_pe23 v806 v807 v2212 substituteAll_pe22 v806 v807 (FlatCurry.Lit v2213) = FlatCurry.Lit v2213 substituteAll_pe22 v806 v807 (FlatCurry.Comb v2214 (v2217,v2218) v2216) = FlatCurry.Comb v2214 (v2217,v2218) (substituteAllArgs_pe24 v806 v807 v2216) substituteAll_pe22 v806 v807 (FlatCurry.Case v2219 v2220 v2221) = FlatCurry.Case v2219 (substituteAll_pe22 v806 v807 v2220) (substituteAllCases_pe25 v806 v807 v2221) substituteAll_pe22 v806 v807 (FlatCurry.Or v2222 v2223) = FlatCurry.Or (substituteAll_pe22 v806 v807 v2222) (substituteAll_pe22 v806 v807 v2223)
replaceVar_pe23 :: d -> c -> b -> a replaceVar_pe23 eval rigid&flex -- CONFLICTING!! replaceVar_pe23 [] [] v2229 = FlatCurry.Var v2229 replaceVar_pe23 (v3633 : v3634) (v3635 : v3636) v2229 = case (v3633 == v2229) of True -> v3635 False -> replaceVar_pe23 v3634 v3636 v2229
substituteAllArgs_pe24 :: d -> c -> b -> a substituteAllArgs_pe24 eval rigid substituteAllArgs_pe24 v2231 v2232 [] = [] substituteAllArgs_pe24 v2231 v2232 (v3637 : v3638) = (substituteAll_pe22 v2231 v2232 v3637) : (substituteAllArgs_pe24 v2231 v2232 v3638)
substituteAllCases_pe25 :: d -> c -> b -> a substituteAllCases_pe25 eval rigid substituteAllCases_pe25 v2236 v2237 [] = [] substituteAllCases_pe25 v2236 v2237 (v3642 : v3643) = (case v3642 of FlatCurry.Branch v5063 v5064 -> case v5063 of FlatCurry.Pattern v5065 v5066 -> case v5065 of (v5067,v5068) -> FlatCurry.Branch (FlatCurry.Pattern (v5067,v5068) v5066) (substituteAll_pe22 v2236 v2237 v5064)
FlatCurry.LPattern v5069 -> FlatCurry.Branch (FlatCurry.LPattern v5069) (substituteAll_pe22 v2236 v2237 v5064)
) : (substituteAllCases_pe25 v2236 v2237 v3643)
matchBranch_pe37 :: d -> c -> b -> a matchBranch_pe37 eval rigid matchBranch_pe37 [] v806 v807 = FlatCurry.Comb FlatCurry.FuncCall ("Prelude","failed") [] matchBranch_pe37 ((FlatCurry.Branch (FlatCurry.Pattern v2215 v2216) v2214) : v2212) v806 v807 = case (v2215 == v806) of True -> substituteAll_pe22 v2216 v807 v2214 False -> matchBranch_pe37 v2212 v806 v807
matchBranchLit_pe38 :: c -> b -> a matchBranchLit_pe38 eval rigid matchBranchLit_pe38 [] v809 = FlatCurry.Comb FlatCurry.FuncCall ("Prelude","failed") [] matchBranchLit_pe38 ((FlatCurry.Branch (FlatCurry.LPattern v2216) v2215) : v2213) v809 = case (v2216 == v809) of True -> v2215 False -> matchBranchLit_pe38 v2213 v809
-- end of module int_fib8_ann_pe
int_fib8_ann_pe(module: int_fib8_ann)>
|
Please report any bug or comment to garroyo (at) dsic.upv.es.
| MiST | ELP | GPLIS | DSIC | UPV |
Last update / Gustavo Arroyo