package bap-std

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

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.

constraint 'a = context

Interaction with environment

method empty : Bil.storage

creates an empty storage. If you want to provide your own implementation of storage, then it is definitely the right place.

method lookup : var -> 'a Bil.Result.r

a variable is looked up in a context

method update : var -> Bil.result -> 'a Bil.Result.u

a variable is bind to a value.

method load : Bil.storage -> addr -> 'a Bil.Result.r

a byte is loaded from a given address

method store : Bil.storage -> addr -> word -> 'a Bil.Result.r

a byte is stored to a a given address

Error conditions

method type_error : type_error -> 'a Bil.Result.r

a given typing error has occured

method division_by_zero : unit -> 'a Bil.Result.r

we can't do this!

method undefined_addr : addr -> 'a Bil.Result.r

called when storage doesn't contain the addr

method undefined_var : var -> 'a Bil.Result.r

called when context doesn't know the variable

Evaluation methods

method eval_exp : exp -> 'a Bil.Result.r
method eval_var : var -> 'a Bil.Result.r
method eval_int : word -> 'a Bil.Result.r
method eval_load : mem:exp -> addr:exp -> endian -> size -> 'a Bil.Result.r
method eval_store : mem:exp -> addr:exp -> exp -> endian -> size -> 'a Bil.Result.r
method eval_binop : binop -> exp -> exp -> 'a Bil.Result.r
method eval_unop : unop -> exp -> 'a Bil.Result.r
method eval_cast : cast -> int -> exp -> 'a Bil.Result.r
method eval_let : var -> exp -> exp -> 'a Bil.Result.r
method eval_ite : cond:exp -> yes:exp -> no:exp -> 'a Bil.Result.r
method eval_concat : exp -> exp -> 'a Bil.Result.r
method eval_extract : int -> int -> exp -> 'a Bil.Result.r
method eval_unknown : string -> typ -> 'a Bil.Result.r
OCaml

Innovation. Community. Security.