Polymorphic Variants

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 EVALUATOR =
sig 
    type term
    val eval : term -> int
end

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

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

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

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 type EVALUATOR0 =
sig 
    type term
    val eval : ((string -> int) * term) -> int
end

module BigStep = struct

    type 'a term0 = [ `Num of int 
                    | `Var of string
                    | `Plus of 'a * 'a
	            | `Let of string * 'a * 'a
	            ]

    module F (X:EVALUATOR0 with type term = private [> 'a term0] as 'a) =
    struct
        type term = X.term term0

        let eval : ((string -> int) * term) -> int = function
             (env, `Num n) -> n
           | (env, `Var x) -> env x
	   | (env, `Plus (e1, e2)) -> X.eval (env, e1) + X.eval (env, e2)
	   | (env, `Let (x, e1, e2)) ->
              X.eval (Env.bind (X.eval (env, e1), x, env), e2)

    end

    module rec L : (EVALUATOR0 with type term = L.term term0) = F (L)
    type term = L.term term0
    let eval e = L.eval (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 OCaml allows polymorphic variants to extend, we can avoid code duplication between the structure BigStep and EBigStep as illustrated in the following code:

module EBigStep = struct

    type 'a term0 = [ 'a BigStep.term0 | `IF0 of 'a * 'a * 'a ]

    module F (X:EVALUATOR0 with type term = private [> 'a term0] as 'a) =
    struct
        type term = X.term term0
        module L = BigStep.F(X)
        let eval : ((string -> int) * term) -> int = function
             (env, (#L.term as e)) -> L.eval (env, e)
	   | (env, `IF0 (c, t, f)) ->
              if (X.eval (env, c) = 0) then X.eval (env, t) 
	      else X.eval (env, f) 
    end

    module rec L : (EVALUATOR0 with type term = L.term term0) = F (L)
    type term = L.term term0
    let eval e = L.eval (Env.empty, e)
end

Then we can instantiate different interpreters by functor applications.

module I = InterpFun (Checker) (BigStep)

module Im = InterpFun (EChecker) (EBigStep)

Reference

[1] Jacques Garrigue, Private rows: abstracting the unnamed. In 4th Asian Symposium on Programming Languages and Systems, Sydney, November 2006. Springer-Verlag LNCS 4279.

Go to home