continued Specialization of Interpreters.

Implementation of interpreters

First we introduce some details about the implementation of interpreters, so we present information regarding the meta-programming facilities of Curry (Hanus, 2011).

 

Meta-programming in Curry. The implementation of our partial evaluator and our Curry interpreter relies on the meta-programming facilities of the language Curry. In particular, we consider the intermediate language FlatCurry for representing functional logic programs. In FlatCurry, all functions are defined at the top level (i.e., local function declarations in source programs are globalized by lambda lifting) and the pattern matching strategy is made explicit by the use of case expressions. In this setting, a FlatCurry program is represented by means of the following data type:

 

data Prog = Prog String --name of module

                 [String] --imported modules

                 [TypeDecl] --type declarations

                 [FuncDecl] --function declarations

                 [OpDecl] --operator declarations

 

For simplicity, here we only show the data types for representing function declarations[FuncDecl]:

 

data FuncDecl = Func QName --qualified name

                     Int --arity

                     Visibility --public/private

                     TypeExpr --type

                     Rule --rule

                     data Rule = Rule [VarIndex] Expr

 

Therefore, each function is represented by a single Rule whose left-hand side contains different variables ([VarIndex]) and whose right-hand side is an expression (Expr) containing variables, literals, function and constructor calls, disjunctions, and case expressions:

 

data Expr = Var VarIndex

                 | Lit Literal

                 | Comb CombType QName [Expr]

                 | Or Expr Expr

                 | Case CaseType Expr [BranchExpr]

data CombType = FuncCall | ConsCall

data CaseType = Rigid | Flex

data BranchExpr = Branch Pattern Expr

data Pattern = Pattern QName [VarIndex]

                     | LPattern Literal

 

 

Description of interpreter’s implementation. Reasoning that an interpreter is a kind of operational semantics of low-level, and therefore may serve as a definition of a programming language (Jones et al., 1993), so in Figure 7 we show the simple operational semantics which should follow our interpreters on an informal basis. However, it is really based on the basic RLNT calculus of (Albert et al., 2002) and on the syntax subset of flatCurry language (Hanus et al., 1999) shown in Section 2 of this working draft. We believe this is enough to implement our interpreters to be specialized. It is necessary to say that we do not consider some features of Curry like: higher-order neither concurrent programming for these implementations but some built-ins and constraints are.

Figure 3. Simple operational semantics for interpreters

As it can seen in the Fibonacci example, it has a main function definition,  mixpo looks for the default function main to start the specialization, so if we want to specialize an interpreter w.r.t. a program it must be included into the same interpreter; we put in the right hand side of main the function call to the interpreter with the following arguments: a boolean flag, the program (to be interpreted)and the expression to be evaluated. Previously we must translate the program to FlatCurry this to include just its list of functions in flat format. Let us explain this, below, there is an example of a Curry simple interpreter; there, we have the function:

{-
int p e = do (Prog _ _ _ funs _ ) <- readFlatCurry p
             print (ieval True funs e)
-}

which is enclosed by {- -}. It is only used to test the interpreter, that is the reason why it is commented. int does two actions; reads the program and prints the evaluation of expression e. The data type to represent a Curry program in the intermediate form, i.e., in FlatCurry has the constructor (Prog) and five arguments where (funs) is the set of functions. So we give just this structure (funs) into the interpreter as the program to be interpreted, ieval is the main function of the interpreter. If you see the right hand side of main function, one of ieval arguments is:

 

[Func ("rev2","main") 0 Public (TCons ("Prelude","Int") [ ]) (Rule [ ] (Comb FuncCall ("Prelude","+") [Comb FuncCall ("Prelude","-") [Comb FuncCall ("Prelude","*") [Lit (Intc 3), Lit (Intc 4)],Lit (Intc 1)],Lit (Intc 2)]))]

 

which represents the functions list in FlatCurry of the following Curry program: main = 3*4-1+2 commented also by {- -} in the example (see below). You may specialize this simple program with mixpo, able to specialize built-ins, as we hope you get the following program:

 

-- Program file: metaintf/examples/rev2_ann_pe

module rev2_ann(main) where

main :: a

main = 13

-- end of module metaintf/examples/rev2_ann_pe

 

Now, if you specialize the simple interpreter shown below, i.e., first to annotate and then specialize, you get the following program:

 

module int_arith_ann(main,ieval_pe1) where

import FlatCurry

 

main :: a

main = ieval_pe1

 

ieval_pe1 :: a ieval_pe1 =

      FlatCurry.Comb FlatCurry.FuncCall ("Prelude","+")

                     [FlatCurry.Comb FlatCurry.FuncCall ("Prelude","-")

                           [FlatCurry.Lit (FlatCurry.Intc 12),FlatCurry.Lit (FlatCurry.Intc 1)],

                          FlatCurry.Lit (FlatCurry.Intc 2)]

 

Striking that all the code of the interpreter has been removed, but we have as a result of this partial evaluation just two function definitions: the main function and the ieval function partially evaluated.

 

Continuing with the implementation description of interpreters structure (which refers to the below example), we have two rules to evaluate a constructor-rooted terms, only one of them unfolds, the rule with True argument, and stops until HNF is reached. ievalList evaluates the function/constructor expression list. See the following rules:

 

ieval True v2 (Comb ConsCall v8 v9) = (Comb ConsCall v8 (ievalList True v2 v9) )

ieval False _ (Comb ConsCall c es) = Comb ConsCall c es

 

While ieval False _ (Comb ConsCall c es) is used to have some control over the evaluation of the case expression argument, i.e., to restrict the unfolding of the possible ConsCall expressions. Let us check the following segment of Curry code:

 

ieval top funs (Case ctype e ces) =

        case (ieval False funs e) of

                Comb ConsCall f es -> ieval top funs (matchBranch ces f es)

                Lit l -> ieval top funs (matchBranchLit ces l)

 

For the sake of simplicity, we take into account only two possible cases of the resulting Case expression, both results make a call to the evaluation of the respective branch of the Case, depending on the resulting Case expression the branch is selected by the functions matchBranch or matchBranchLit.

To know the rest of description about the implementation of interpreters you may see this working draft

Continue with the specialization of interpreters

Go back




 

Example of a Curry simple interpreter

module int_arith where

import FlatCurry --metaprogramming facilities (e.g., data structure for flat progs)

--these are just a test examples for the partial evaluator in order to
--avoid using I/O facilities which are not allowed

{-

main = 3*4-1+2                           
  
-}

main = ieval True [Func ("rev2","main") 0 Public (TCons ("Prelude","Int") []) (Rule [] (Comb FuncCall ("Prelude","+") [Comb FuncCall ("Prelude","-") [Comb FuncCall ("Prelude","*") [Lit (Intc 3),Lit (Intc 4)],Lit (Intc 1)],Lit (Intc 2)]))] (Comb FuncCall ("rev2","main") [])

--these functiond are only used by the partial evaluator to annotate some expressions:

UNF x = x
MEM x = x

--function int is only used to test the interpreter (the partial evaluator calls
--directly to ieval to avoid having I/O function calls
{-
int p e = do (Prog _ _ _ funs _ ) <- readFlatCurry p
             print (ieval True funs e)
-}

--ieval: this is the main function of the interpreter
--arguments: a boolean flag, true for the top expression and false otherwise
--           the program
--           the expression to be evaluated
--returns a pair (value,current value of n)

--vars (we use no environment!)
ieval _ _ (Var v) = Var v

--literals
ieval _ _ (Lit l) = Lit l

--constructor calls (observe the use of the Boolean flag)
ieval True v2  (Comb ConsCall v8 v9) = (Comb ConsCall v8 (ievalList True v2 v9) )

ievalList _  _ [] = []

ievalList top funs (e:es) = ievalListaux top funs (ieval top funs e) es

ievalListaux top funs ne es = ne : (ievalList top funs es)

ieval False _   (Comb ConsCall c es) = Comb ConsCall c es

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
   else ieval top funs (matchiRHS  funs (mn,f) es)

ieval top funs (Case ctype e ces) =
  case (ieval False funs e) of
    Comb ConsCall f es -> ieval top funs (matchBranch ces f es)
    Lit l -> ieval top funs (matchBranchLit ces l)
  --problema con el renaming!

ieval_ARITH :: Bool -> [FuncDecl] -> QName -> [Expr] -> Expr
ieval_ARITH    top       fns         (mn,fn)  [e1,e2] =
  if (isLitInt e1) && (isLitInt e2)
     then (ieval_ARITH_aux (mn,fn) [e1,e2])
     else
        Comb FuncCall (mn,fn) (ievalList top fns [e1,e2])

--evaluation of simple arithmetic functions
ieval_ARITH_aux (_,f) [(Lit (Intc e1)),(Lit (Intc e2))] =
             case f of
                  ("*") -> Lit (Intc (e1*e2))
                  ("+") -> Lit (Intc (e1+e2))
                  ("-") -> Lit (Intc (e1-e2))

ieval_ARITH_auxb top fns (mn,fn) ne = ieval top fns  (Comb FuncCall (mn,fn) ne)

isLitInt :: Expr -> Bool
isLitInt e = case e of
                 (Lit (Intc _)) -> True
                 _              -> False

ieval_EQ :: Bool -> [FuncDecl] -> QName -> [Expr] -> Expr
ieval_EQ    top       fns         (mn,fn)  [e1,e2] =
  if (isLitInt e1) && (isLitInt e2)
     then (ieval_EQ_aux [e1,e2])
     else
        if (isLitInt e1) && (isVar e2)
           then Comb ConsCall ("Prelude","False") []
           else ieval top fns (Comb FuncCall (mn,fn) (ievalList top fns [e1,e2]))


ieval_EQ_aux [(Lit (Intc e1)),(Lit (Intc e2))] =
             case (e1==e2) of
                  True -> Comb ConsCall ("Prelude","True") []
                  _    -> Comb ConsCall ("Prelude","False") []

--ieval_args is only used to evaluate sequentially the arguments of
--a constructor call or an arithmetic operation

ieval_args _ [] = []
ieval_args funs (e:es) = (ieval True funs e) : (ieval_args funs es)

--matchBranch and matchBranchLit are used to select the matching branch
--of a case expression:

matchBranch cbranches c es =
     case cbranches of
         []     -> (Comb FuncCall ("Prelude","failed") [])
         (Branch (Pattern p vars) e):ces ->
                 if p==c then substitute vars es e
                         else matchBranch ces c es

matchBranchLit cbranches c =
     case cbranches of
         []     -> (Comb FuncCall ("Prelude","failed") [])
         (Branch (LPattern p) e):ces ->
                 if p==c then e
                         else matchBranchLit ces c

---------------------------------------------------------------------------
-- CALL UNFOLDING:

-- match a right-hand side of a given function:
matchiRHS [] (_,_) _ = Comb FuncCall ("Prelude","failed") []
matchiRHS (Func (_,fname) _ _ _ funrule : fds) (mn,name) es =
   if fname==name then matchRHS_aux funrule es
                  else matchiRHS fds (mn,name) es

matchRHS_aux (Rule vars rhs) es = substitute vars es rhs

substitute :: [Int] -> [Expr] -> Expr -> Expr
substitute vars exps expr = substituteAll vars exps expr

-- substitute all occurrences of variables by corresponding expressions:
-- * substitute all occurrences of var_i by exp_i in expr
--   (if vars=[var_1,...,var_n] and exps=[exp_1,...,exp_n])
-- * leave all other variables unchanged (i.e., variables in case patterns)
--
-- here we assume that the new variables in case patterns
-- do not occur in the list "vars" of replaced variables!

substituteAll :: [Int] -> [Expr] -> Expr -> Expr
substituteAll vs es x =
    case x of
        (Var i)  -> replaceVar vs es i
        (Lit (Intc l))  -> Lit (Intc l)
        (Lit (Charc l))  -> Lit (Charc l)
        (Comb ConsCall c exps) -> Comb ConsCall c (mapsAll vs es exps)
--        (Comb FuncCall ("Prelude","failed") [])
        (Comb FuncCall c exps) -> Comb FuncCall c (mapsAll vs es exps)
--        (Comb (FuncPartCall ma) c exps) ->
--                       Comb (FuncPartCall ma) c (mapsAll vs es exps)
--        (Comb ctyp (c,o) exps) -> Comb ctyp (c,o) (mapsAll vs es exps)
        (Case ctype e cases) -> Case ctype (substituteAll vs es e)
                                           (substituteAllCases vs es cases)
        (Or e1 e2) ->  (Or (substituteAll vs es e1) (substituteAll vs es e2))
        (Let [(lhs,rhs)] e) ->
             Let (mapsAllLet vs es [(lhs,rhs)]) (substituteAll vs es e)
        (Free vars e) -> Free vars (substituteAll vs es e)

replaceVar [] [] var = Var var
replaceVar (v:vs) (e:es) var  = if v==var then e
                                          else replaceVar vs es var

substituteAllArgs _   _ []         = []
substituteAllArgs vs es (exp:exps) =
  (substituteAll vs es exp) : (substituteAllArgs vs es exps)

substituteAllCases _  _ []              = []
substituteAllCases vs es (tbranch:cases) =
   (substituteAllCase vs es tbranch) : (substituteAllCases vs es cases)


substituteAllCase vs es x =
             case x of
                  (Branch (Pattern (l,o) pvs) e) ->
                          Branch (Pattern (l,o) pvs) (substituteAll vs es e)
                  (Branch (LPattern l) e) -> 
                          Branch (LPattern l) (substituteAll vs es e)

mapsAll vs es []         = []
mapsAll vs es (exp:exps) = (substituteAll vs es exp): (mapsAll vs es exps)

mapsAllLet vs es [] = []
mapsAllLet vs es ((lhs,rhs):bindings) =
              (substituteAllLet vs es (lhs,rhs)):(mapsAllLet vs es bindings)

substituteAllLet :: [Int] -> [Expr] -> (VarIndex,Expr) -> (VarIndex,Expr)
substituteAllLet vs es (var,e)= (var,(substituteAll vs es e))


isVar :: Expr -> Bool
isVar e = case e of
               (Var _) -> True
               _        -> False

 
 

 Please report any bug or comment to garroyo (at) dsic.upv.es. 

MiST ELP GPLIS DSIC UPV

Last update / Gustavo Arroyo