Ocaml

Each component in a reference architecture can be mapped to a OCaml program unit (called module) and interfaces among them can be specified as signatures. Signatures show the types of all components:

module type CHECKER =
sig
   module T : TERM
   val check : T.term -> T.term
end

module type OPTIMIZER =
sig
   module T : TERM
   val opt : T.term -> T.term
end

module type EVAL =
sig
   module T : TERM
   val eval : T.term -> int
end

The signature CHECKER specifies a structure that must provide a function check, which has a type of Term.term -> int. However, our product line analysis already identifies that Term itself would be extended to support new terms such as If0, which implies the type of check has to be of ETerm.term -> int where ETerm is a extension of Term. We can postpone writing down any concrete type in a signature definition by using a type specification and referring to it by name.

Then, by using conceptual components (eval, checker, optimizer), we can specify functors which generate interpreters as in the following code.

module InterpFun (C:CHECKER) 
                 (E:EVALUATOR with type T.term = C.T.term) =
struct
    let interp = fun e -> E.eval (C.check e)
end

module InterpOptFun (C:CHECKER) 
                    (O:OPTIMIZER with type T.term = C.T.term)
                    (E:EVALUATOR with type T.term = O.T.term) =
struct
    let interp = fun e -> E.eval (O.opt (C.check e))
end

For example, the functor InterpFun takes two components checker and evaluator with additional constraints defining that the types of term in both components should coincide and then returns their composition.

While there would be only one implementation for each static component, generic components can have multiple implementations. For example, since the component evaluator is generic, it has multiple implementations each of which should match with its signature EVALUATOR. The following code shows an implementation for the Evaluation semantics feature.

module BigStep =
struct  
    module T = Term

    let base eval env e = match e with
             T.NUM n -> n
           | T.VAR x -> env x 
           | T.PLUS (e1, e2) -> eval env e1 + eval env e2
           | T.LET (x, e1, e2) -> eval (Env.bind (eval env e1, x, env)) e2

    let eval e = 
	let rec run env e = base run env e
	in run Env.empty e
end

As the language grows, so does the evaluation semantics. The structure EBigStep, for example, extends the structure BigStep to support a conditional term. Since the data type in OCaml is not extensible (NOTE: OCaml supports such extension through objects and polymorphic variants, which will be discussed here), there may appear some code duplication between the structure BigStep and EBigStep as illustrated in the following code:

module EBigStep =
struct  
    module T = ETerm

    let base eval env e = match e with
             T.NUM n -> n
           | T.VAR x -> env x 
           | T.PLUS (e1, e2) -> eval env e1 + eval env e2
           | T.LET (x, e1, e2) -> eval (Env.bind (eval env e1, x, env)) e2
	   | T.IF0 (c, t, f) ->
	     if (eval env c) = 0 then eval env t else eval env f

    let eval e = 
	let rec run env e = base run env e
	in run Env.empty e
end

Then we can instantiate all four interpreters by functor applications. For example, an optimized base interpreter Iopt can be instantiated by applying the functor InterpOptFun to the components Checker, Optimizer and BigStep.

module I = InterpFun (Checker) (BigStep)

module Im = InterpFun (Checker) (Machine)

module Iopt = InterpOptFun (Checker) (Optimizer) (BigStep)

module I’opt = InterpOptFun (EChecker) (EOptimizer) (EBigStep)

Reference

[1] Wonseok Chae and Matthias Blume, “Building a Family of Compilers”, SPLC 2008.

Go to home