package bap-std

Expression interpreter.

Expi is a base class for all other interpreters (see bili and biri, that do all the hard work. Expi recognizes a language defined by exp type. It evaluates arbitrary expressions under provided context.

To create new interpreter use operator new:

        let expi = new expi;;
        val expi : _#Expi.context expi = <obj>

Note: The type _#Expi.context is weakly polymorphic subtype of Expi.context1. Basically, this means, that the type is not generalized and will be instantiated when used and fixed afterwards.

        let r = expi#eval_exp Bil.(int Word.b0 lor int Word.b1);;
        val r : _#Expi.context Bil.Result.r = <abstr>

The returned value is a state monad parametrized by a subtype of class Expi.context. The state monad is a chain of computations, where each computation is merely a function from state to a state paired with the result of computation. The state is accessible inside the computation and can be changed.

To run the computation use Monad.State.eval function, that accepts a state monad and an initial value. Here we can provide any subtype of Expi.context as an initial value. Let start with a Expi.context as a first approximation:

        let x = Monad.State.eval r (new Expi.context);;
        val x : Bil.result = [0x3] true

The expression evaluates to true, and the result is tagged with an identifier [0x3]. The Exp.context assigns a unique identifier for each freshly created result. Tag [0x3] means that this was the third value created under provided context.

If the only thing, that you need is just to evaluate an expression, then you can just use Exp.eval function:

        Exp.eval Bil.(int Word.b0 lor int Word.b1);;
        - : Bil.value = true

The main strength of expi is its extensibility. Let's write a expression evaluator that will record a trace of evaluation:

class context = object
  inherit Expi.context
  val events : (exp * Bil.result) list = []
  method add_event exp res = {< events = (exp,res) :: events >}
  method show_events = List.rev events
end

class ['a] exp_tracer = object
  constraint 'a = #context
  inherit ['a] expi as super
  method! eval_exp e =
    let open Monad.State in
    super#eval_exp e >>= fun r ->
    get () >>= fun ctxt ->
    put (ctxt#add_event e r) >>= fun () ->
    return r
end;;

Note : We made our exp_tracer class polymorphic as a courtesy to our fellow programmer, that may want to reuse it. We can define it by inheriting from expi parametrized with our context type, like this: inherit [context] expi

Also, there is no need to write a constraint, as it will be inferred automatically.

Now, let's try to use our tracer. We will use Monad.State.run function, that returns both, the evaluated value and the context. (We can also use Monad.State.exec, if we're not interested in value at all):

        let expi = new exp_tracer;;
        val expi : _#context exp_tracer = <obj>
        # let r = expi#eval_exp Bil.(int Word.b0 lor int Word.b1);;
        val r : _#context Bil.Result.r = <abstr>
        # let r,ctxt = Monad.State.run r (new context) ;;
        val r : Bil.result = [0x3] true
        val ctxt : context = <obj>
        ctxt#events;;
        - : (exp * Bil.result) list =
        [(false, [0x1] false); (true, [0x2] true); (false | true, [0x3] true)]

1: The weakness of the type variable is introduced by a value restriction and can't be relaxed since it is invariant in state monad.

Interaction with environment

Error conditions

Evaluation methods