In this notebook, we'll look into modelling implied trading within an exchange. Implied trading refers to ability to connect liquidity on strategy and outright order books (e.g. Euronext).

1 Type definitions and printers

1.1 Model type definitions

Our first goal is to setup the various type definitions that we'll use later on.

In [1]:
type side = BUY | SELL

type outright_id = OUT1 | OUT2 | OUT3
type strategy_id = STRAT1 | STRAT2
type month = Mar | Jun | Sep | Dec

(* Map an outright with an expiry *)
let contract_expiry = function
  | OUT1 -> Mar
  | OUT2 -> Jun
  | OUT3 -> Sep

(* Convert month to an integer *)
let month_to_int = function
  | Mar -> 3
  | Jun -> 6
  | Sep -> 9
  | Dec -> 12
;;

(* Return true of m1 is nearer (or equal) to m2 *)
let month_comp (m1 : month) (m2 : month) =
  (month_to_int m1) < (month_to_int  m2)
;;

type instrument =
  | Strategy of strategy_id
  | Outright of outright_id

(* Level information *)
type level_info = {
  li_qty : int
  ; li_price : int
}

(* best bid and ask information *)
type best_bid_ask = {
  bid_info : level_info option
  ; ask_info : level_info option
}

(* Best bid/ask for all of the books *)
type books_info = {
  book1 : best_bid_ask
  ; book2 : best_bid_ask
  ; book3 : best_bid_ask
}

(* Order type *)
type order = {
  o_qty : int
  ; o_price : int
  ; o_time : int
  ; o_id : int
  ; o_side : side
  ; o_client_id : int
  ; o_inst : instrument
  ; o_is_implied : bool
}

(* Helper function to make order creation simpler *)
let make si qty price id inst clientid isimp time =
  {o_qty = qty ; o_price = price; o_id = id; o_side = si;
   o_client_id = clientid; o_inst = inst; o_is_implied = isimp;
   o_time = time }


(* outright order book *)
type book = {
  b_buys : order list
  ; b_sells : order list
}

let empty_book = { b_buys = []; b_sells = [] }

(* Individual leg *)
type leg = {
  leg_sec_idx : outright_id
  ; leg_mult : int
}

(* Strategy is composed of legs *)
type strategy = {
  time_created : int
  ; leg1 : leg
  ; leg2 : leg
  ; leg3 : leg
}

(* Helper function to make strategy creation smaller *)
let make_strat tcreated m1 m2 m3 = {
  time_created = tcreated
  ; leg1 = { leg_sec_idx = OUT1; leg_mult = m1 }
  ; leg2 = { leg_sec_idx = OUT2; leg_mult = m2 }
  ; leg3 = { leg_sec_idx = OUT3; leg_mult = m3 }
}

type implied_strat_ord = {
  max_strat : int option
  ; strat_price : int option
}

(* New order message *)
type new_ord_msg = {
  no_client_id : int
  ; no_inst_type : instrument
  ; no_qty : int
  ; no_side : side
  ; no_price : int
}

(* cancel order ID *)
type cancel_ord_msg = {
  co_client_id : int
  ; co_order_id : int
  ; co_instrument : instrument
  ; co_side : side
}

(* Inbound messages type *)
type inbound_msg =
  | NewOrder of new_ord_msg
  | CancelOrder of cancel_ord_msg
  | ImpliedUncross

(* Helper function for creating new order messages *)
let make_no_msg cid inst qty sd p =
 NewOrder {
  no_client_id = cid
  ; no_inst_type = inst
  ; no_qty = qty
  ; no_side = sd
  ; no_price = p
 }

(* ack message *)
type ack_msg = {
  ack_client_id : int
  ; ack_order_id : int
  ; ack_inst_type : instrument
  ; ack_qty : int
  ; ack_side : side
  ; ack_price : int
}

(* fill information *)
type fill = {
  fill_client_id : int
  ; fill_qty : int
  ; fill_price : int
  ; fill_order_id : int
  ; fill_order_done : bool
}

(* uncross result *)
type uncross_res = {
  uncrossed_book : book
  ; uncrossed_fills : fill list
  ; uncrossed_qty : int
}

(* outbound message type *)
type outbound_msg =
  | Ack of ack_msg
  | Fill of fill
  | UncrossResult of uncross_res
;;

(* The entire market - strategy definitions, order books, messages, etc. s*)
type market = {

  (* current time*)
  curr_time : int

  (* used for order ID counter *)
  ; last_ord_id : int

  (* two strategy definitions *)
  ; strat1    : strategy
  ; strat2    : strategy

  (* outright books *)
  ; out_book1 : book
  ; out_book2 : book
  ; out_book3 : book

  (* strategy books *)
  ; s_book1   : book
  ; s_book2   : book

  (* inbound and outbound message queues *)
  ; inbound_msgs  : inbound_msg list
  ; outbound_msgs : outbound_msg list

}
Out[1]:
type side = BUY | SELL
type outright_id = OUT1 | OUT2 | OUT3
type strategy_id = STRAT1 | STRAT2
type month = Mar | Jun | Sep | Dec
val contract_expiry : outright_id -> month = <fun>
val month_to_int : month -> Z.t = <fun>
val month_comp : month -> month -> bool = <fun>
type instrument = Strategy of strategy_id | Outright of outright_id
type level_info = { li_qty : Z.t; li_price : Z.t; }
type best_bid_ask = {
  bid_info : level_info option;
  ask_info : level_info option;
}
type books_info = {
  book1 : best_bid_ask;
  book2 : best_bid_ask;
  book3 : best_bid_ask;
}
type order = {
  o_qty : Z.t;
  o_price : Z.t;
  o_time : Z.t;
  o_id : Z.t;
  o_side : side;
  o_client_id : Z.t;
  o_inst : instrument;
  o_is_implied : bool;
}
val make :
  side -> Z.t -> Z.t -> Z.t -> instrument -> Z.t -> bool -> Z.t -> order =
  <fun>
type book = { b_buys : order list; b_sells : order list; }
val empty_book : book = {b_buys = []; b_sells = []}
type leg = { leg_sec_idx : outright_id; leg_mult : Z.t; }
type strategy = { time_created : Z.t; leg1 : leg; leg2 : leg; leg3 : leg; }
val make_strat : Z.t -> Z.t -> Z.t -> Z.t -> strategy = <fun>
type implied_strat_ord = {
  max_strat : Z.t option;
  strat_price : Z.t option;
}
type new_ord_msg = {
  no_client_id : Z.t;
  no_inst_type : instrument;
  no_qty : Z.t;
  no_side : side;
  no_price : Z.t;
}
type cancel_ord_msg = {
  co_client_id : Z.t;
  co_order_id : Z.t;
  co_instrument : instrument;
  co_side : side;
}
type inbound_msg =
    NewOrder of new_ord_msg
  | CancelOrder of cancel_ord_msg
  | ImpliedUncross
val make_no_msg : Z.t -> instrument -> Z.t -> side -> Z.t -> inbound_msg =
  <fun>
type ack_msg = {
  ack_client_id : Z.t;
  ack_order_id : Z.t;
  ack_inst_type : instrument;
  ack_qty : Z.t;
  ack_side : side;
  ack_price : Z.t;
}
type fill = {
  fill_client_id : Z.t;
  fill_qty : Z.t;
  fill_price : Z.t;
  fill_order_id : Z.t;
  fill_order_done : bool;
}
type uncross_res = {
  uncrossed_book : book;
  uncrossed_fills : fill list;
  uncrossed_qty : Z.t;
}
type outbound_msg =
    Ack of ack_msg
  | Fill of fill
  | UncrossResult of uncross_res
type market = {
  curr_time : Z.t;
  last_ord_id : Z.t;
  strat1 : strategy;
  strat2 : strategy;
  out_book1 : book;
  out_book2 : book;
  out_book3 : book;
  s_book1 : book;
  s_book2 : book;
  inbound_msgs : inbound_msg list;
  outbound_msgs : outbound_msg list;
}

1.2 Custom type printers

One of Imandra's powerful features is the ability to combine logic (pure subset of OCaml) and program (all of OCaml) modes. In the following cell, we will create and install a custom type printer (HTML) for an order book. So that next time a value of this type is computed within a cell, this printer would be used instead of the generic one.

In [2]:
(* Here's an example of a custom printer that we can install for arbitrary data types. *)

#program;;
(* #require "tyxml";; *)
let html_of_order (o : order) =
  let module H = Tyxml.Html in
  H.div
  ~a:(if o.o_is_implied then [H.a_style "color: red"] else [])
  [ H.div
    ~a:[H.a_style "font-size: 1.4em"]
    [H.txt (Format.asprintf "%s (%s)" (Z.to_string o.o_price) (Z.to_string o.o_qty))]
  ; H.div (if o.o_is_implied then [H.txt "Implied"] else [])
  ]

let html elt =
  let module H = Tyxml.Html in
  Document.html (Document.Unsafe_.html_of_string @@ CCFormat.sprintf "%a" (H.pp_elt ()) elt);;

let doc_of_order (o:order) =
  let module H = Tyxml.Html in
  html (H.div [html_of_order o]);;

#install_doc doc_of_order;;

let html_of_book ?(title="") (b: book) =
  let module H = Tyxml.Html in
  let rec build_rows acc buys sells =
      match buys, sells with
      | b :: bs, s :: ss -> build_rows (acc @ [H.tr [H.td [html_of_order b]; H.td [html_of_order s]]]) bs ss
      | b :: bs, [] -> build_rows (acc @ [H.tr [H.td [html_of_order b]; H.td [H.txt "-"]]]) bs []
      | [], s :: ss -> build_rows (acc @ [H.tr [H.td [H.txt "-"]; H.td [html_of_order s]]]) [] ss
      | [], [] -> acc
  in
  H.div
  ~a:[H.a_style "margin-right:1em; display: flex; flex-direction: column; align-items: center; justify-content: flex-start"]
  [ H.div ~a:[H.a_style "font-weight: bold"] [H.txt title]
  ; H.table
    ~thead:(H.thead [H.tr [H.th [H.txt "Buys"]; H.th [H.txt "Sells"]]])
    (build_rows [] b.b_buys b.b_sells)]

let doc_of_book (b:book) =
  let module H = Tyxml.Html in
  html (H.div [html_of_book ~title:"M1 Mar21" b]);;

#install_doc doc_of_book;;

let html_of_market (m: market) =
  let module H = Tyxml.Html in
  H.div
  [ H.div ~a:[H.a_style "display: flex"]
    [ html_of_book ~title:"Strategy 1" m.s_book1
    ; html_of_book ~title:"Strategy 2" m.s_book2
    ]
  ; H.div ~a:[H.a_style "margin-top: 1em; display: flex"]
    [ html_of_book ~title:"Book 1" m.out_book1
    ; html_of_book ~title:"Book 2" m.out_book2
    ; html_of_book ~title:"Book 3" m.out_book3
    ]]

let doc_of_market (m : market) =
  html (html_of_market m);;

#install_doc doc_of_market;;

#logic;;
Out[2]:
val html_of_order : order -> [> Html_types.div ] Tyxml_html.elt = <fun>
val html : 'a Tyxml_html.elt -> Document.t = <fun>
val doc_of_order : order -> Document.t = <fun>
val html_of_book :
  ?title:string -> book -> [> Html_types.div ] Tyxml_html.elt = <fun>
val doc_of_book : book -> Document.t = <fun>
val html_of_market : market -> [> Html_types.div ] Tyxml_html.elt = <fun>
val doc_of_market : market -> Document.t = <fun>

1.3 Custom type printer example

In [3]:
let leg = { leg_sec_idx = OUT1; leg_mult = 1 } in

let strat = { time_created = 0; leg1 = leg; leg2 = leg; leg3 = leg } in

let b1 = {
  b_buys = [
    (make BUY 100 54 1 (Outright OUT1) 1 true 1)
    ;(make BUY 100 54 2 (Outright OUT1) 1 false 1)
  ]
  ; b_sells = [
    (make SELL 100 54 3 (Outright OUT1) 1 false 1)
    ;(make SELL 100 54 4 (Outright OUT1) 1 false 1)
  ] } in

  { curr_time = 1
  ; last_ord_id = 1
  ; strat1 = strat
  ; strat2 = strat
  ; out_book1 = b1
  ; out_book2 = b1
  ; out_book3 = b1
  ; s_book1 = b1
  ; s_book2 = b1
  ; inbound_msgs = []
  ; outbound_msgs = []
  }
Out[3]:
- : market = <document>
Strategy 1
BuysSells
54 (100)
Implied
54 (100)
54 (100)
54 (100)
Strategy 2
BuysSells
54 (100)
Implied
54 (100)
54 (100)
54 (100)
Book 1
BuysSells
54 (100)
Implied
54 (100)
54 (100)
54 (100)
Book 2
BuysSells
54 (100)
Implied
54 (100)
54 (100)
54 (100)
Book 3
BuysSells
54 (100)
Implied
54 (100)
54 (100)
54 (100)

2. Outright uncrossing logic

2.1 Order book operatons (inserting, cancelling orders)

In [4]:
(* Convert fills into outbound messages *)
let rec create_fill_msgs (f : fill list) =
  match f with
  | [] -> []
  | x::xs -> (Fill x) :: create_fill_msgs xs

(* TODO: recode this with higher-order functions *)
let rec cancel_ord_side (orders : order list) (c : cancel_ord_msg) =
  match orders with
  | [] -> []
  | x::xs ->
    begin
      if (x.o_client_id = c.co_client_id) && (x.o_id = c.co_order_id) then xs
      else x :: (cancel_ord_side xs c)
    end

(* Helper to cancel orders *)
let cancel_ord_book (co : cancel_ord_msg) (b : book) =
  match co.co_side with
  | BUY -> { b with b_buys = (cancel_ord_side b.b_buys co) }
  | SELL -> { b with b_sells = (cancel_ord_side b.b_sells co) }

(* function used insert individual orders *)
let rec insert_order_side (orders : order list) (o : order) =
  match orders with
  | [] -> [ o ]
  | x::xs ->
    begin
      if o.o_side = BUY then
        (if o.o_price > x.o_price then o :: orders else x :: (insert_order_side xs o))
      else
        (if o.o_price < x.o_price then o :: orders else x :: (insert_order_side xs o))
    end

(* insert order into the book *)
let insert_order (o : order) (b : book) =
  if o.o_side = BUY then
    { b with b_buys = (insert_order_side b.b_buys o) }
  else
    { b with b_sells = (insert_order_side b.b_sells o) }

(* The fills are adjusted to a single fill price during the uncross *)
let rec adjust_fill_prices (fills : fill list) ( f_price : int ) =
  match fills with
  | [] -> []
  | x::xs -> { x with fill_price = f_price } :: ( adjust_fill_prices xs f_price )
;;
Out[4]:
val create_fill_msgs : fill list -> outbound_msg list = <fun>
val cancel_ord_side : order list -> cancel_ord_msg -> order list = <fun>
val cancel_ord_book : cancel_ord_msg -> book -> book = <fun>
val insert_order_side : order list -> order -> order list = <fun>
val insert_order : order -> book -> book = <fun>
val adjust_fill_prices : fill list -> Z.t -> fill list = <fun>
termination proof

Termination proof

call `create_fill_msgs (List.tl f)` from `create_fill_msgs f`
original:create_fill_msgs f
sub:create_fill_msgs (List.tl f)
original ordinal:Ordinal.Int (_cnt f)
sub ordinal:Ordinal.Int (_cnt (List.tl f))
path:[f <> []]
proof:
detailed proof
ground_instances:3
definitions:0
inductions:0
search_time:
0.015s
details:
Expand
smt_stats:
num checks:8
arith assert lower:21
arith tableau max rows:11
arith tableau max columns:36
arith pivots:15
rlimit count:3433
mk clause:49
datatype occurs check:22
mk bool var:119
arith assert upper:16
datatype splits:3
decisions:27
arith row summations:25
propagations:37
conflicts:10
arith fixed eqs:9
datatype accessor ax:10
arith conflicts:2
arith num rows:11
datatype constructor ax:11
num allocs:9371486
final checks:6
added eqs:80
del clause:19
arith eq adapter:14
memory:20.100000
max memory:20.100000
Expand
  • start[0.015s]
      let (_x_0 : int) = count.list count.fill f in
      let (_x_1 : fill list) = List.tl f in
      let (_x_2 : int) = count.list count.fill _x_1 in
      f <> [] && ((_x_0 >= 0) && (_x_2 >= 0))
      ==> not (_x_1 <> [])
          || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
  • simplify
    into:
    let (_x_0 : fill list) = List.tl f in
    let (_x_1 : int) = count.list count.fill _x_0 in
    let (_x_2 : int) = count.list count.fill f in
    not (_x_0 <> []) || Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
    || not (f <> [] && (_x_2 >= 0) && (_x_1 >= 0))
    expansions:
    []
    rewrite_steps:
      forward_chaining:
      • unroll
        expr:
        (|Ordinal.<<| (|Ordinal.Int_79/boot|
                        (|count.list_547/server| (|get.::.1_520/server|…
        expansions:
        • unroll
          expr:
          (|count.list_547/server| (|get.::.1_520/server| f_536/server))
          expansions:
          • unroll
            expr:
            (|count.list_547/server| f_536/server)
            expansions:
            • Unsat
            termination proof

            Termination proof

            call `cancel_ord_side (List.tl orders) c` from `cancel_ord_side orders c`
            original:cancel_ord_side orders c
            sub:cancel_ord_side (List.tl orders) c
            original ordinal:Ordinal.Int (_cnt orders)
            sub ordinal:Ordinal.Int (_cnt (List.tl orders))
            path:[let (_x_0 : order) = List.hd orders in not ((_x_0.o_client_id = c.co_client_id) && (_x_0.o_id = c.co_order_id)) && orders <> []]
            proof:
            detailed proof
            ground_instances:3
            definitions:0
            inductions:0
            search_time:
            0.018s
            details:
            Expand
            smt_stats:
            num checks:8
            arith assert lower:26
            arith tableau max rows:13
            arith tableau max columns:41
            arith pivots:22
            rlimit count:5463
            mk clause:60
            datatype occurs check:28
            mk bool var:285
            arith assert upper:16
            datatype splits:51
            decisions:66
            arith row summations:31
            propagations:40
            interface eqs:1
            conflicts:10
            arith fixed eqs:13
            arith assume eqs:1
            datatype accessor ax:36
            arith conflicts:2
            arith num rows:13
            datatype constructor ax:86
            num allocs:15175048
            final checks:7
            added eqs:353
            del clause:24
            arith eq adapter:16
            memory:20.500000
            max memory:20.500000
            Expand
            • start[0.018s]
                let (_x_0 : order) = List.hd orders in
                let (_x_1 : int) = c.co_client_id in
                let (_x_2 : int) = c.co_order_id in
                let (_x_3 : int) = count.list count.order orders in
                let (_x_4 : order list) = List.tl orders in
                let (_x_5 : int) = count.list count.order _x_4 in
                let (_x_6 : order) = List.hd _x_4 in
                not ((_x_0.o_client_id = _x_1) && (_x_0.o_id = _x_2))
                && (orders <> [] && ((_x_3 >= 0) && (_x_5 >= 0)))
                ==> not
                    (not ((_x_6.o_client_id = _x_1) && (_x_6.o_id = _x_2)) && _x_4 <> [])
                    || Ordinal.( << ) (Ordinal.Int _x_5) (Ordinal.Int _x_3)
            • simplify
              into:
              let (_x_0 : order list) = List.tl orders in
              let (_x_1 : order) = List.hd _x_0 in
              let (_x_2 : int) = c.co_client_id in
              let (_x_3 : int) = c.co_order_id in
              let (_x_4 : int) = count.list count.order _x_0 in
              let (_x_5 : int) = count.list count.order orders in
              let (_x_6 : order) = List.hd orders in
              not (not ((_x_1.o_client_id = _x_2) && (_x_1.o_id = _x_3)) && _x_0 <> [])
              || Ordinal.( << ) (Ordinal.Int _x_4) (Ordinal.Int _x_5)
              || not
                 (not ((_x_6.o_client_id = _x_2) && (_x_6.o_id = _x_3)) && orders <> []
                  && (_x_5 >= 0) && (_x_4 >= 0))
              expansions:
              []
              rewrite_steps:
                forward_chaining:
                • unroll
                  expr:
                  (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                  (|count.list_597/server|
                                    (|ge…
                  expansions:
                  • unroll
                    expr:
                    (|count.list_597/server| (|get.::.1_582/server| orders_584/server))
                    expansions:
                    • unroll
                      expr:
                      (|count.list_597/server| orders_584/server)
                      expansions:
                      • Unsat
                      termination proof

                      Termination proof

                      call `insert_order_side (List.tl orders) o` from `insert_order_side orders o`
                      original:insert_order_side orders o
                      sub:insert_order_side (List.tl orders) o
                      original ordinal:Ordinal.Int (_cnt orders)
                      sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                      path:[not (o.o_price > (List.hd orders).o_price) && o.o_side = BUY && orders <> []]
                      proof:
                      detailed proof
                      ground_instances:3
                      definitions:0
                      inductions:0
                      search_time:
                      0.012s
                      details:
                      Expand
                      smt_stats:
                      num checks:8
                      arith assert lower:20
                      arith tableau max rows:12
                      arith tableau max columns:43
                      arith pivots:17
                      rlimit count:10494
                      mk clause:58
                      datatype occurs check:28
                      mk bool var:293
                      arith assert upper:17
                      datatype splits:59
                      decisions:57
                      arith row summations:25
                      propagations:42
                      interface eqs:1
                      conflicts:10
                      arith fixed eqs:9
                      arith assume eqs:1
                      datatype accessor ax:37
                      arith conflicts:2
                      arith num rows:12
                      datatype constructor ax:82
                      num allocs:30957609
                      final checks:7
                      added eqs:373
                      del clause:22
                      arith eq adapter:14
                      memory:21.020000
                      max memory:21.020000
                      Expand
                      • start[0.012s]
                          let (_x_0 : int) = o.o_price in
                          let (_x_1 : bool) = o.o_side = BUY in
                          let (_x_2 : int) = count.list count.order orders in
                          let (_x_3 : order list) = List.tl orders in
                          let (_x_4 : int) = count.list count.order _x_3 in
                          let (_x_5 : int) = (List.hd _x_3).o_price in
                          let (_x_6 : bool) = _x_3 <> [] in
                          not (_x_0 > (List.hd orders).o_price)
                          && (_x_1 && (orders <> [] && ((_x_2 >= 0) && (_x_4 >= 0))))
                          ==> (not (not (_x_0 > _x_5) && (_x_1 && _x_6))
                               && not (not (_x_0 < _x_5) && (not _x_1 && _x_6)))
                              || Ordinal.( << ) (Ordinal.Int _x_4) (Ordinal.Int _x_2)
                      • simplify
                        into:
                        let (_x_0 : order list) = List.tl orders in
                        let (_x_1 : int) = count.list count.order _x_0 in
                        let (_x_2 : int) = count.list count.order orders in
                        let (_x_3 : int) = o.o_price in
                        let (_x_4 : bool) = o.o_side = BUY in
                        let (_x_5 : int) = (List.hd _x_0).o_price in
                        let (_x_6 : bool) = _x_0 <> [] in
                        Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                        || not
                           ((_x_3 <= (List.hd orders).o_price) && _x_4 && orders <> [] && (_x_2 >= 0)
                            && (_x_1 >= 0))
                        || (not ((_x_3 <= _x_5) && _x_4 && _x_6)
                            && not ((_x_5 <= _x_3) && not _x_4 && _x_6))
                        expansions:
                        []
                        rewrite_steps:
                          forward_chaining:
                          • unroll
                            expr:
                            (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                            (|count.list_683/server|
                                              (|ge…
                            expansions:
                            • unroll
                              expr:
                              (|count.list_683/server| (|get.::.1_667/server| orders_668/server))
                              expansions:
                              • unroll
                                expr:
                                (|count.list_683/server| orders_668/server)
                                expansions:
                                • Unsat
                                call `insert_order_side (List.tl orders) o` from `insert_order_side orders o`
                                original:insert_order_side orders o
                                sub:insert_order_side (List.tl orders) o
                                original ordinal:Ordinal.Int (_cnt orders)
                                sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                                path:[not (o.o_price < (List.hd orders).o_price) && not (o.o_side = BUY) && orders <> []]
                                proof:
                                detailed proof
                                ground_instances:3
                                definitions:0
                                inductions:0
                                search_time:
                                0.012s
                                details:
                                Expand
                                smt_stats:
                                num checks:8
                                arith assert lower:26
                                arith tableau max rows:13
                                arith tableau max columns:44
                                arith pivots:19
                                rlimit count:5362
                                mk clause:60
                                datatype occurs check:28
                                mk bool var:314
                                arith assert upper:17
                                datatype splits:63
                                decisions:63
                                arith row summations:28
                                propagations:45
                                interface eqs:1
                                conflicts:11
                                arith fixed eqs:12
                                arith assume eqs:1
                                datatype accessor ax:40
                                arith conflicts:2
                                arith num rows:13
                                datatype constructor ax:93
                                num allocs:22744701
                                final checks:7
                                added eqs:402
                                del clause:24
                                arith eq adapter:16
                                memory:21.010000
                                max memory:21.010000
                                Expand
                                • start[0.012s]
                                    let (_x_0 : int) = o.o_price in
                                    let (_x_1 : bool) = o.o_side = BUY in
                                    let (_x_2 : bool) = not _x_1 in
                                    let (_x_3 : int) = count.list count.order orders in
                                    let (_x_4 : order list) = List.tl orders in
                                    let (_x_5 : int) = count.list count.order _x_4 in
                                    let (_x_6 : int) = (List.hd _x_4).o_price in
                                    let (_x_7 : bool) = _x_4 <> [] in
                                    not (_x_0 < (List.hd orders).o_price)
                                    && (_x_2 && (orders <> [] && ((_x_3 >= 0) && (_x_5 >= 0))))
                                    ==> (not (not (_x_0 > _x_6) && (_x_1 && _x_7))
                                         && not (not (_x_0 < _x_6) && (_x_2 && _x_7)))
                                        || Ordinal.( << ) (Ordinal.Int _x_5) (Ordinal.Int _x_3)
                                • simplify
                                  into:
                                  let (_x_0 : order list) = List.tl orders in
                                  let (_x_1 : int) = count.list count.order _x_0 in
                                  let (_x_2 : int) = count.list count.order orders in
                                  let (_x_3 : int) = o.o_price in
                                  let (_x_4 : int) = (List.hd _x_0).o_price in
                                  let (_x_5 : bool) = o.o_side = BUY in
                                  let (_x_6 : bool) = _x_0 <> [] in
                                  let (_x_7 : bool) = not _x_5 in
                                  Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                  || (not ((_x_3 <= _x_4) && _x_5 && _x_6)
                                      && not ((_x_4 <= _x_3) && _x_7 && _x_6))
                                  || not
                                     (((List.hd orders).o_price <= _x_3) && _x_7 && orders <> [] && (_x_2 >= 0)
                                      && (_x_1 >= 0))
                                  expansions:
                                  []
                                  rewrite_steps:
                                    forward_chaining:
                                    • unroll
                                      expr:
                                      (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                      (|count.list_683/server|
                                                        (|ge…
                                      expansions:
                                      • unroll
                                        expr:
                                        (|count.list_683/server| (|get.::.1_667/server| orders_668/server))
                                        expansions:
                                        • unroll
                                          expr:
                                          (|count.list_683/server| orders_668/server)
                                          expansions:
                                          • Unsat
                                          termination proof

                                          Termination proof

                                          call `adjust_fill_prices (List.tl fills) f_price` from `adjust_fill_prices fills f_price`
                                          original:adjust_fill_prices fills f_price
                                          sub:adjust_fill_prices (List.tl fills) f_price
                                          original ordinal:Ordinal.Int (_cnt fills)
                                          sub ordinal:Ordinal.Int (_cnt (List.tl fills))
                                          path:[fills <> []]
                                          proof:
                                          detailed proof
                                          ground_instances:3
                                          definitions:0
                                          inductions:0
                                          search_time:
                                          0.012s
                                          details:
                                          Expand
                                          smt_stats:
                                          num checks:8
                                          arith assert lower:20
                                          arith tableau max rows:10
                                          arith tableau max columns:35
                                          arith pivots:17
                                          rlimit count:4025
                                          mk clause:53
                                          datatype occurs check:22
                                          mk bool var:122
                                          arith assert upper:19
                                          datatype splits:3
                                          decisions:29
                                          arith row summations:42
                                          propagations:38
                                          interface eqs:1
                                          conflicts:10
                                          arith fixed eqs:8
                                          arith assume eqs:1
                                          datatype accessor ax:10
                                          arith conflicts:2
                                          arith num rows:10
                                          datatype constructor ax:11
                                          num allocs:41155829
                                          final checks:7
                                          added eqs:81
                                          del clause:23
                                          arith eq adapter:15
                                          memory:21.410000
                                          max memory:21.410000
                                          Expand
                                          • start[0.012s]
                                              let (_x_0 : int) = count.list count.fill fills in
                                              let (_x_1 : fill list) = List.tl fills in
                                              let (_x_2 : int) = count.list count.fill _x_1 in
                                              fills <> [] && ((_x_0 >= 0) && (_x_2 >= 0))
                                              ==> not (_x_1 <> [])
                                                  || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                          • simplify
                                            into:
                                            let (_x_0 : fill list) = List.tl fills in
                                            let (_x_1 : int) = count.list count.fill _x_0 in
                                            let (_x_2 : int) = count.list count.fill fills in
                                            not (_x_0 <> []) || Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                            || not (fills <> [] && (_x_2 >= 0) && (_x_1 >= 0))
                                            expansions:
                                            []
                                            rewrite_steps:
                                              forward_chaining:
                                              • unroll
                                                expr:
                                                (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                (|count.list_820/server|
                                                                  (|ge…
                                                expansions:
                                                • unroll
                                                  expr:
                                                  (|count.list_820/server| (|get.::.1_806/server| fills_807/server))
                                                  expansions:
                                                  • unroll
                                                    expr:
                                                    (|count.list_820/server| fills_807/server)
                                                    expansions:
                                                    • Unsat

                                                    2.2 Book uncross

                                                    In [5]:
                                                    (* Measure for proving termination of `uncross_book` below *)
                                                    let book_measure b =
                                                      Ordinal.of_int (List.length b.b_buys + List.length b.b_sells)
                                                    
                                                    let rec uncross_book (b : book) (fills : fill list) (filled_qty : int) =
                                                      match b.b_buys, b.b_sells with
                                                      | [], [] | _, [] | [], _ ->
                                                        (* we need to check whether there have been fills before,
                                                          if so we need to adjust fill prices before getting out *)
                                                        begin
                                                          match fills with
                                                          | [] -> { uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty }
                                                          | x::xs ->
                                                            let fills' = x :: (adjust_fill_prices xs x.fill_price) in
                                                          { uncrossed_book = b; uncrossed_fills = fills'; uncrossed_qty = filled_qty }
                                                        end
                                                      | buy::bs, sell::ss ->
                                                        if buy.o_price >= sell.o_price then
                                                          begin
                                                            (* compute the fill qty and price *)
                                                            let fill_qty = if buy.o_qty < sell.o_qty then buy.o_qty else sell.o_qty in
                                                            let fill_price = (buy.o_price + sell.o_price) / 2 in
                                                    
                                                            (* update the orders that traded *)
                                                            let buy' = { buy with o_qty = buy.o_qty - fill_qty } in
                                                            let sell' = { sell with o_qty = sell.o_qty - fill_qty } in
                                                    
                                                            (* create the fills *)
                                                            let fill1 = {
                                                              fill_client_id = buy.o_client_id
                                                              ; fill_qty = fill_qty
                                                              ; fill_price = fill_price
                                                              ; fill_order_id = buy.o_id
                                                              ; fill_order_done = true } in
                                                    
                                                            let fill2 = {
                                                              fill_client_id = sell.o_client_id
                                                              ; fill_qty = fill_qty
                                                              ; fill_price = fill_price
                                                              ; fill_order_id = sell.o_id
                                                              ; fill_order_done = true } in
                                                    
                                                            (* now update the books and fills *)
                                                            let new_buys = if buy'.o_qty = 0 then bs else buy'::bs in
                                                            let new_sells = if sell'.o_qty = 0 then ss else sell'::ss in
                                                            let b' = {
                                                              b_buys = new_buys
                                                              ; b_sells = new_sells } in
                                                    
                                                            (* We should not be generating fills for implied orders - there's
                                                              a different mechanism for that *)
                                                            let fills' = if not buy.o_is_implied then
                                                              fill1 :: fills else fills in
                                                            let fills' = if not sell.o_is_implied then
                                                              fill2 :: fills' else fills' in
                                                    
                                                            (* recursively go to the next level *)
                                                            uncross_book b' fills' (filled_qty + fill_qty)
                                                          end
                                                    
                                                        else
                                                          (* nothing to do here *)
                                                          { uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty }
                                                    [@@measure book_measure b]
                                                    ;;
                                                    
                                                    Out[5]:
                                                    val book_measure : book -> Ordinal.t = <fun>
                                                    val uncross_book : book -> fill list -> Z.t -> uncross_res = <fun>
                                                    
                                                    termination proof

                                                    Termination proof

                                                    call `let (_x_0 : order list) = b.b_buys in let (_x_1 : order) = List.hd _x_0 in let (_x_2 : int) = _x_1.o_qty in let (_x_3 : order list) = b.b_sells in let (_x_4 : order) = List.hd _x_3 in let (_x_5 : int) = _x_4.o_qty in let (_x_6 : int) = if _x_2 < _x_5 then _x_2 else _x_5 in let (_x_7 : int) = _x_2 - _x_6 in let (_x_8 : order list) = List.tl _x_0 in let (_x_9 : int) = _x_5 - _x_6 in let (_x_10 : order list) = List.tl _x_3 in let (_x_11 : int) = (_x_1.o_price + _x_4.o_price) / 2 in let (_x_12 : fill list) = if not _x_1.o_is_implied then {fill_client_id = _x_1.o_client_id; fill_qty = _x_6; fill_price = _x_11; fill_order_id = _x_1.o_id; fill_order_done = true} :: fills else fills in uncross_book {b_buys = if _x_7 = 0 then _x_8 else {_x_1 with o_qty = _x_7} :: _x_8; b_sells = if _x_9 = 0 then _x_10 else {_x_4 with o_qty = _x_9} :: _x_10} (if not _x_4.o_is_implied then {fill_client_id = _x_4.o_client_id; fill_qty = _x_6; fill_price = _x_11; fill_order_id = _x_4.o_id; fill_order_done = true} :: _x_12 else _x_12) (filled_qty + _x_6)` from `uncross_book b fills filled_qty`
                                                    original:uncross_book b fills filled_qty
                                                    sub:let (_x_0 : order list) = b.b_buys in let (_x_1 : order) = List.hd _x_0 in let (_x_2 : int) = _x_1.o_qty in let (_x_3 : order list) = b.b_sells in let (_x_4 : order) = List.hd _x_3 in let (_x_5 : int) = _x_4.o_qty in let (_x_6 : int) = if _x_2 < _x_5 then _x_2 else _x_5 in let (_x_7 : int) = _x_2 - _x_6 in let (_x_8 : order list) = List.tl _x_0 in let (_x_9 : int) = _x_5 - _x_6 in let (_x_10 : order list) = List.tl _x_3 in let (_x_11 : int) = (_x_1.o_price + _x_4.o_price) / 2 in let (_x_12 : fill list) = if not _x_1.o_is_implied then {fill_client_id = _x_1.o_client_id; fill_qty = _x_6; fill_price = _x_11; fill_order_id = _x_1.o_id; fill_order_done = true} :: fills else fills in uncross_book {b_buys = if _x_7 = 0 then _x_8 else {_x_1 with o_qty = _x_7} :: _x_8; b_sells = if _x_9 = 0 then _x_10 else {_x_4 with o_qty = _x_9} :: _x_10} (if not _x_4.o_is_implied then {fill_client_id = _x_4.o_client_id; fill_qty = _x_6; fill_price = _x_11; fill_order_id = _x_4.o_id; fill_order_done = true} :: _x_12 else _x_12) (filled_qty + _x_6)
                                                    original ordinal:book_measure b
                                                    sub ordinal:let (_x_0 : order list) = b.b_buys in let (_x_1 : order) = List.hd _x_0 in let (_x_2 : int) = _x_1.o_qty in let (_x_3 : order list) = b.b_sells in let (_x_4 : order) = List.hd _x_3 in let (_x_5 : int) = _x_4.o_qty in let (_x_6 : int) = if _x_2 < _x_5 then _x_2 else _x_5 in let (_x_7 : int) = _x_2 - _x_6 in let (_x_8 : order list) = List.tl _x_0 in let (_x_9 : int) = _x_5 - _x_6 in let (_x_10 : order list) = List.tl _x_3 in book_measure {b_buys = if _x_7 = 0 then _x_8 else {_x_1 with o_qty = _x_7} :: _x_8; b_sells = if _x_9 = 0 then _x_10 else {_x_4 with o_qty = _x_9} :: _x_10}
                                                    path:[(List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price && b.b_buys <> [] && b.b_sells <> []]
                                                    proof:
                                                    detailed proof
                                                    ground_instances:5
                                                    definitions:0
                                                    inductions:0
                                                    search_time:
                                                    0.016s
                                                    details:
                                                    Expand
                                                    smt_stats:
                                                    arith offset eqs:29
                                                    num checks:12
                                                    arith assert lower:73
                                                    arith tableau max rows:21
                                                    arith tableau max columns:41
                                                    arith pivots:38
                                                    rlimit count:13261
                                                    mk clause:112
                                                    datatype occurs check:83
                                                    mk bool var:678
                                                    arith assert upper:42
                                                    datatype splits:154
                                                    decisions:162
                                                    arith row summations:132
                                                    arith bound prop:13
                                                    propagations:196
                                                    interface eqs:2
                                                    conflicts:24
                                                    arith fixed eqs:22
                                                    arith assume eqs:2
                                                    datatype accessor ax:95
                                                    arith conflicts:4
                                                    arith num rows:21
                                                    arith assert diseq:11
                                                    datatype constructor ax:243
                                                    num allocs:52974000
                                                    final checks:12
                                                    added eqs:1260
                                                    del clause:74
                                                    arith eq adapter:48
                                                    memory:22.100000
                                                    max memory:22.100000
                                                    Expand
                                                    • start[0.016s]
                                                        let (_x_0 : order list) = b.b_buys in
                                                        let (_x_1 : order) = List.hd _x_0 in
                                                        let (_x_2 : order list) = b.b_sells in
                                                        let (_x_3 : order) = List.hd _x_2 in
                                                        let (_x_4 : int) = List.length _x_0 + List.length _x_2 in
                                                        let (_x_5 : int) = if _x_4 >= 0 then _x_4 else 0 in
                                                        let (_x_6 : int) = List.length ….b_buys + List.length ….b_sells in
                                                        let (_x_7 : int) = if _x_6 >= 0 then _x_6 else 0 in
                                                        let (_x_8 : int) = _x_1.o_qty in
                                                        let (_x_9 : int) = _x_3.o_qty in
                                                        let (_x_10 : int) = if _x_8 < _x_9 then _x_8 else _x_9 in
                                                        let (_x_11 : int) = _x_8 - _x_10 in
                                                        let (_x_12 : order list) = List.tl _x_0 in
                                                        let (_x_13 : order list)
                                                            = if _x_11 = 0 then _x_12
                                                              else
                                                                {o_qty = _x_11; o_price = …; o_time = …; o_id = …;
                                                                 o_side = …; o_client_id = …; o_inst = …; o_is_implied = …}
                                                                :: _x_12
                                                        in
                                                        let (_x_14 : int) = _x_9 - _x_10 in
                                                        let (_x_15 : order list) = List.tl _x_2 in
                                                        let (_x_16 : order list)
                                                            = if _x_14 = 0 then _x_15
                                                              else
                                                                {o_qty = _x_14; o_price = …; o_time = …; o_id = …;
                                                                 o_side = …; o_client_id = …; o_inst = …; o_is_implied = …}
                                                                :: _x_15
                                                        in
                                                        (_x_1.o_price >= _x_3.o_price)
                                                        && (_x_0 <> [] && (_x_2 <> [] && ((_x_5 >= 0) && (_x_7 >= 0))))
                                                        ==> not
                                                            (((List.hd _x_13).o_price >= (List.hd _x_16).o_price)
                                                             && (_x_13 <> [] && _x_16 <> []))
                                                            || Ordinal.( << ) (Ordinal.Int _x_7) (Ordinal.Int _x_5)
                                                    • simplify
                                                      into:
                                                      let (_x_0 : order list) = b.b_buys in
                                                      let (_x_1 : int) = (List.hd _x_0).o_qty in
                                                      let (_x_2 : order list) = b.b_sells in
                                                      let (_x_3 : int) = (List.hd _x_2).o_qty in
                                                      let (_x_4 : int) = (-1) * (if _x_3 <= _x_1 then _x_3 else _x_1) in
                                                      let (_x_5 : int) = _x_1 + _x_4 in
                                                      let (_x_6 : order list) = List.tl _x_0 in
                                                      let (_x_7 : order list)
                                                          = if _x_5 = 0 then _x_6
                                                            else
                                                              {o_qty = _x_5; o_price = …; o_time = …; o_id = …; o_side = …;
                                                               o_client_id = …; o_inst = …; o_is_implied = …}
                                                              :: _x_6
                                                      in
                                                      let (_x_8 : int) = _x_3 + _x_4 in
                                                      let (_x_9 : order list) = List.tl _x_2 in
                                                      let (_x_10 : order list)
                                                          = if _x_8 = 0 then _x_9
                                                            else
                                                              {o_qty = _x_8; o_price = …; o_time = …; o_id = …; o_side = …;
                                                               o_client_id = …; o_inst = …; o_is_implied = …}
                                                              :: _x_9
                                                      in
                                                      let (_x_11 : int) = List.length _x_7 + List.length _x_10 in
                                                      let (_x_12 : int) = List.length _x_0 + List.length _x_2 in
                                                      not
                                                      (((List.hd _x_7).o_price >= (List.hd _x_10).o_price) && _x_7 <> []
                                                       && _x_10 <> [])
                                                      || Ordinal.( << ) (Ordinal.Int (if _x_11 >= 0 then _x_11 else 0))
                                                         (Ordinal.Int (if _x_12 >= 0 then _x_12 else 0))
                                                      || not ((… >= …) && _x_0 <> [] && _x_2 <> [])
                                                      expansions:
                                                      []
                                                      rewrite_steps:
                                                        forward_chaining:
                                                        • unroll
                                                          expr:
                                                          (let ((a!1 (<= (o_qty_1305/client
                                                                           (|get.::.0_870/server| (b_sells_1326/client b_888…
                                                          expansions:
                                                          • unroll
                                                            expr:
                                                            (let ((a!1 (<= (o_qty_1305/client
                                                                             (|get.::.0_870/server| (b_sells_1326/client b_888…
                                                            expansions:
                                                            • unroll
                                                              expr:
                                                              (let ((a!1 (<= (o_qty_1305/client
                                                                               (|get.::.0_870/server| (b_sells_1326/client b_888…
                                                              expansions:
                                                              • unroll
                                                                expr:
                                                                (|List.length_876/server| (b_sells_1326/client b_888/server))
                                                                expansions:
                                                                • unroll
                                                                  expr:
                                                                  (|List.length_876/server| (b_buys_1325/client b_888/server))
                                                                  expansions:
                                                                  • Unsat

                                                                  We now have a function that does something real - uncross_book (b : book) (fills : fill list) (filled_qty : int). Let's experiment how it works with some concrete values.

                                                                  In [6]:
                                                                  let book1 = {
                                                                    b_buys = [
                                                                      (make BUY 100 55 1 (Outright OUT1) 1 false 1)
                                                                      ; (make BUY 100 50 2 (Outright OUT1) 1 false 1)
                                                                      ]
                                                                   ; b_sells = [
                                                                      (make BUY 100 54 3 (Outright OUT1) 1 false 1)
                                                                      ; (make BUY 100 54 4 (Outright OUT1) 1 false 1)
                                                                    ]
                                                                  } in
                                                                  
                                                                  uncross_book book1 [] 0
                                                                  
                                                                  Out[6]:
                                                                  - : uncross_res =
                                                                  {uncrossed_book = <document>;
                                                                   uncrossed_fills =
                                                                    [{fill_client_id = 1; fill_qty = 100; fill_price = 54; fill_order_id = 3;
                                                                      fill_order_done = true};
                                                                     {fill_client_id = 1; fill_qty = 100; fill_price = 54; fill_order_id = 1;
                                                                      fill_order_done = true}];
                                                                   uncrossed_qty = 100}
                                                                  
                                                                  M1 Mar21
                                                                  BuysSells
                                                                  50 (100)
                                                                  54 (100)

                                                                  2.3 A few verification goals

                                                                  Let's try to verify some verification goals.

                                                                  The first one will make sure that for an order book that is sorted (so the best bid/ask orders will be the first ones in their respective lists. Note: this is not based on the 'imbalance' of the order book, this is simply taking the midpointt of the most aggressive orders.

                                                                  In [7]:
                                                                  (* Returns true if the orders are sorted with respect to price *)
                                                                  let rec side_price_sorted (si : side) (orders : order list) =
                                                                    match orders with
                                                                    | [] -> true
                                                                    | x::[] -> true
                                                                    | x::y::xs ->
                                                                      if si = BUY then
                                                                        begin
                                                                          if y.o_price > x.o_price && x.o_price > 0 then false else (side_price_sorted si (y::xs))
                                                                        end
                                                                      else
                                                                        begin
                                                                          if y.o_price < x.o_price && y.o_price > 0 then false else (side_price_sorted si (y::xs))
                                                                        end
                                                                  ;;
                                                                  
                                                                  (* Let's make sure all the fills have this price *)
                                                                  let rec fills_good_price (fills : fill list) (p : int) =
                                                                    match fills with
                                                                    | [] -> true
                                                                    | x::xs -> (x.fill_price = p) && (fills_good_price xs p)
                                                                  ;;
                                                                  
                                                                  (** Let's to verify some properties *)
                                                                  let fill_price_midpoint (b : book) =
                                                                  
                                                                    let buys_sorted = side_price_sorted BUY b.b_buys in
                                                                    let sells_sorted = side_price_sorted SELL b.b_sells in
                                                                  
                                                                    let result_good =
                                                                      begin
                                                                        match b.b_buys, b.b_sells with
                                                                        | [], _ -> true
                                                                        | _, [] -> true
                                                                        | x::xs, y::ys ->
                                                                          let unc_res = uncross_book b [] 0 in
                                                                          if x.o_price >= y.o_price then
                                                                            let midprice = (x.o_price + y.o_price) / 2 in
                                                                            (List.length unc_res.uncrossed_fills) > 0 && (fills_good_price unc_res.uncrossed_fills midprice)
                                                                          else
                                                                            true
                                                                      end in
                                                                  
                                                                    (* This is the 'punchline'... if the sides are price-sorted, then the fills will be the first midpoint *)
                                                                    (buys_sorted && sells_sorted) ==> result_good
                                                                  ;;
                                                                  
                                                                  
                                                                  verify fill_price_midpoint
                                                                  
                                                                  Out[7]:
                                                                  val side_price_sorted : side -> order list -> bool = <fun>
                                                                  val fills_good_price : fill list -> Z.t -> bool = <fun>
                                                                  val fill_price_midpoint : book -> bool = <fun>
                                                                  - : book -> bool = <fun>
                                                                  module CX : sig val b : book end
                                                                  
                                                                  termination proof

                                                                  Termination proof

                                                                  call `let (_x_0 : order list) = List.tl orders in side_price_sorted si ((List.hd _x_0) :: (List.tl _x_0))` from `side_price_sorted si orders`
                                                                  original:side_price_sorted si orders
                                                                  sub:let (_x_0 : order list) = List.tl orders in side_price_sorted si ((List.hd _x_0) :: (List.tl _x_0))
                                                                  original ordinal:Ordinal.Int (_cnt orders)
                                                                  sub ordinal:let (_x_0 : order list) = List.tl orders in Ordinal.Int (_cnt ((List.hd _x_0) :: (List.tl _x_0)))
                                                                  path:[let (_x_0 : int) = (List.hd orders).o_price in not (((List.hd (List.tl orders)).o_price > _x_0) && (_x_0 > 0)) && si = BUY && (List.tl orders) <> [] && orders <> []]
                                                                  proof:
                                                                  detailed proof
                                                                  ground_instances:3
                                                                  definitions:0
                                                                  inductions:0
                                                                  search_time:
                                                                  0.015s
                                                                  details:
                                                                  Expand
                                                                  smt_stats:
                                                                  num checks:8
                                                                  arith assert lower:41
                                                                  arith tableau max rows:15
                                                                  arith tableau max columns:48
                                                                  arith pivots:23
                                                                  rlimit count:14804
                                                                  mk clause:72
                                                                  datatype occurs check:21
                                                                  mk bool var:302
                                                                  arith assert upper:28
                                                                  datatype splits:52
                                                                  decisions:79
                                                                  arith row summations:34
                                                                  arith bound prop:1
                                                                  propagations:65
                                                                  interface eqs:1
                                                                  conflicts:9
                                                                  arith fixed eqs:20
                                                                  arith assume eqs:1
                                                                  datatype accessor ax:35
                                                                  minimized lits:2
                                                                  arith conflicts:2
                                                                  arith num rows:15
                                                                  datatype constructor ax:83
                                                                  num allocs:81762424
                                                                  final checks:7
                                                                  added eqs:373
                                                                  del clause:29
                                                                  arith eq adapter:21
                                                                  memory:22.560000
                                                                  max memory:22.580000
                                                                  Expand
                                                                  • start[0.015s]
                                                                      let (_x_0 : order list) = List.tl orders in
                                                                      let (_x_1 : order) = List.hd _x_0 in
                                                                      let (_x_2 : int) = _x_1.o_price in
                                                                      let (_x_3 : int) = (List.hd orders).o_price in
                                                                      let (_x_4 : bool) = si = BUY in
                                                                      let (_x_5 : int) = count.list count.order orders in
                                                                      let (_x_6 : int) = count.list count.order (_x_1 :: …) in
                                                                      let (_x_7 : int) = (List.hd …).o_price in
                                                                      let (_x_8 : bool) = … <> [] in
                                                                      not ((_x_2 > _x_3) && (_x_3 > 0))
                                                                      && (_x_4 && (_x_0 <> [] && (orders <> [] && ((_x_5 >= 0) && (_x_6 >= 0)))))
                                                                      ==> (not (not ((_x_7 > _x_2) && (_x_2 > 0)) && (_x_4 && _x_8))
                                                                           && not (not ((_x_7 < _x_2) && (_x_7 > 0)) && (not _x_4 && _x_8)))
                                                                          || Ordinal.( << ) (Ordinal.Int _x_6) (Ordinal.Int _x_5)
                                                                  • simplify
                                                                    into:
                                                                    let (_x_0 : order list) = List.tl orders in
                                                                    let (_x_1 : order) = List.hd _x_0 in
                                                                    let (_x_2 : int) = count.list count.order orders in
                                                                    let (_x_3 : int) = (List.hd …).o_price in
                                                                    let (_x_4 : int) = _x_1.o_price in
                                                                    let (_x_5 : bool) = si = BUY in
                                                                    let (_x_6 : order list) = List.tl _x_0 in
                                                                    let (_x_7 : int) = (List.hd orders).o_price in
                                                                    Ordinal.( << ) (Ordinal.Int (count.list count.order (_x_1 :: …)))
                                                                    (Ordinal.Int _x_2)
                                                                    || (not (not (not (_x_3 <= _x_4) && not (_x_4 <= 0)) && _x_5 && … <> [])
                                                                        && not
                                                                           (not (not (_x_4 <= _x_3) && not ((List.hd _x_6).o_price <= 0))
                                                                            && not _x_5 && _x_6 <> []))
                                                                    || not
                                                                       (not (not (_x_4 <= _x_7) && not (_x_7 <= 0)) && _x_5 && _x_0 <> []
                                                                        && orders <> [] && (_x_2 >= 0)
                                                                        && (count.list count.order (_x_1 :: _x_6) >= 0))
                                                                    expansions:
                                                                    []
                                                                    rewrite_steps:
                                                                      forward_chaining:
                                                                      • unroll
                                                                        expr:
                                                                        (let ((a!1 (|count.list_1055/server|
                                                                                     (|::| (|get.::.0_1038/server|
                                                                                            …
                                                                        expansions:
                                                                        • unroll
                                                                          expr:
                                                                          (|count.list_1055/server|
                                                                            (|::| (|get.::.0_1038/server| (|get.::.1_1039/server| orders_1041/server…
                                                                          expansions:
                                                                          • unroll
                                                                            expr:
                                                                            (|count.list_1055/server| orders_1041/server)
                                                                            expansions:
                                                                            • Unsat
                                                                            call `let (_x_0 : order list) = List.tl orders in side_price_sorted si ((List.hd _x_0) :: (List.tl _x_0))` from `side_price_sorted si orders`
                                                                            original:side_price_sorted si orders
                                                                            sub:let (_x_0 : order list) = List.tl orders in side_price_sorted si ((List.hd _x_0) :: (List.tl _x_0))
                                                                            original ordinal:Ordinal.Int (_cnt orders)
                                                                            sub ordinal:let (_x_0 : order list) = List.tl orders in Ordinal.Int (_cnt ((List.hd _x_0) :: (List.tl _x_0)))
                                                                            path:[let (_x_0 : int) = (List.hd (List.tl orders)).o_price in not ((_x_0 < (List.hd orders).o_price) && (_x_0 > 0)) && not (si = BUY) && (List.tl orders) <> [] && orders <> []]
                                                                            proof:
                                                                            detailed proof
                                                                            ground_instances:3
                                                                            definitions:0
                                                                            inductions:0
                                                                            search_time:
                                                                            0.019s
                                                                            details:
                                                                            Expand
                                                                            smt_stats:
                                                                            arith offset eqs:1
                                                                            num checks:8
                                                                            arith assert lower:89
                                                                            arith tableau max rows:17
                                                                            arith tableau max columns:50
                                                                            arith pivots:56
                                                                            rlimit count:8436
                                                                            mk clause:114
                                                                            datatype occurs check:27
                                                                            mk bool var:413
                                                                            arith assert upper:90
                                                                            datatype splits:64
                                                                            decisions:111
                                                                            arith row summations:80
                                                                            arith bound prop:2
                                                                            propagations:108
                                                                            interface eqs:1
                                                                            conflicts:24
                                                                            arith fixed eqs:33
                                                                            arith assume eqs:1
                                                                            datatype accessor ax:42
                                                                            minimized lits:16
                                                                            arith conflicts:12
                                                                            arith num rows:17
                                                                            arith assert diseq:4
                                                                            datatype constructor ax:91
                                                                            num allocs:67383302
                                                                            final checks:7
                                                                            added eqs:457
                                                                            del clause:77
                                                                            arith eq adapter:65
                                                                            time:0.001000
                                                                            memory:22.580000
                                                                            max memory:22.580000
                                                                            Expand
                                                                            • start[0.019s]
                                                                                let (_x_0 : order list) = List.tl orders in
                                                                                let (_x_1 : order) = List.hd _x_0 in
                                                                                let (_x_2 : int) = _x_1.o_price in
                                                                                let (_x_3 : bool) = _x_2 > 0 in
                                                                                let (_x_4 : bool) = si = BUY in
                                                                                let (_x_5 : bool) = not _x_4 in
                                                                                let (_x_6 : int) = count.list count.order orders in
                                                                                let (_x_7 : order list) = List.tl _x_0 in
                                                                                let (_x_8 : int) = count.list count.order (_x_1 :: _x_7) in
                                                                                let (_x_9 : int) = (List.hd _x_7).o_price in
                                                                                let (_x_10 : bool) = _x_7 <> [] in
                                                                                not ((_x_2 < (List.hd orders).o_price) && _x_3)
                                                                                && (_x_5 && (_x_0 <> [] && (orders <> [] && ((_x_6 >= 0) && (_x_8 >= 0)))))
                                                                                ==> (not (not ((_x_9 > _x_2) && _x_3) && (_x_4 && _x_10))
                                                                                     && not (not ((_x_9 < _x_2) && (_x_9 > 0)) && (_x_5 && _x_10)))
                                                                                    || Ordinal.( << ) (Ordinal.Int _x_8) (Ordinal.Int _x_6)
                                                                            • simplify
                                                                              into:
                                                                              let (_x_0 : order list) = List.tl orders in
                                                                              let (_x_1 : order) = List.hd _x_0 in
                                                                              let (_x_2 : order list) = List.tl _x_0 in
                                                                              let (_x_3 : int) = count.list count.order (_x_1 :: _x_2) in
                                                                              let (_x_4 : int) = count.list count.order orders in
                                                                              let (_x_5 : int) = (List.hd …).o_price in
                                                                              let (_x_6 : int) = _x_1.o_price in
                                                                              let (_x_7 : bool) = not (_x_6 <= 0) in
                                                                              let (_x_8 : bool) = si = BUY in
                                                                              let (_x_9 : bool) = not _x_8 in
                                                                              Ordinal.( << ) (Ordinal.Int _x_3) (Ordinal.Int _x_4)
                                                                              || (not (not (not (_x_5 <= _x_6) && _x_7) && _x_8 && … <> [])
                                                                                  && not
                                                                                     (not (not (_x_6 <= _x_5) && not ((List.hd _x_2).o_price <= 0)) && _x_9
                                                                                      && _x_2 <> []))
                                                                              || not
                                                                                 (not (not ((List.hd orders).o_price <= _x_6) && _x_7) && _x_9
                                                                                  && _x_0 <> [] && orders <> [] && (_x_4 >= 0) && (_x_3 >= 0))
                                                                              expansions:
                                                                              []
                                                                              rewrite_steps:
                                                                                forward_chaining:
                                                                                • unroll
                                                                                  expr:
                                                                                  (let ((a!1 (|count.list_1055/server|
                                                                                               (|::| (|get.::.0_1038/server|
                                                                                                      …
                                                                                  expansions:
                                                                                  • unroll
                                                                                    expr:
                                                                                    (|count.list_1055/server|
                                                                                      (|::| (|get.::.0_1038/server| (|get.::.1_1039/server| orders_1041/server…
                                                                                    expansions:
                                                                                    • unroll
                                                                                      expr:
                                                                                      (|count.list_1055/server| orders_1041/server)
                                                                                      expansions:
                                                                                      • Unsat
                                                                                      termination proof

                                                                                      Termination proof

                                                                                      call `fills_good_price (List.tl fills) p` from `fills_good_price fills p`
                                                                                      original:fills_good_price fills p
                                                                                      sub:fills_good_price (List.tl fills) p
                                                                                      original ordinal:Ordinal.Int (_cnt fills)
                                                                                      sub ordinal:Ordinal.Int (_cnt (List.tl fills))
                                                                                      path:[(List.hd fills).fill_price = p && fills <> []]
                                                                                      proof:
                                                                                      detailed proof
                                                                                      ground_instances:3
                                                                                      definitions:0
                                                                                      inductions:0
                                                                                      search_time:
                                                                                      0.011s
                                                                                      details:
                                                                                      Expand
                                                                                      smt_stats:
                                                                                      num checks:8
                                                                                      arith assert lower:20
                                                                                      arith tableau max rows:10
                                                                                      arith tableau max columns:33
                                                                                      arith pivots:17
                                                                                      rlimit count:4221
                                                                                      mk clause:51
                                                                                      datatype occurs check:19
                                                                                      mk bool var:121
                                                                                      arith assert upper:19
                                                                                      datatype splits:3
                                                                                      decisions:29
                                                                                      arith row summations:44
                                                                                      propagations:39
                                                                                      interface eqs:1
                                                                                      conflicts:10
                                                                                      arith fixed eqs:8
                                                                                      arith assume eqs:1
                                                                                      datatype accessor ax:10
                                                                                      arith conflicts:2
                                                                                      arith num rows:10
                                                                                      datatype constructor ax:11
                                                                                      num allocs:97765122
                                                                                      final checks:7
                                                                                      added eqs:81
                                                                                      del clause:23
                                                                                      arith eq adapter:15
                                                                                      memory:22.810000
                                                                                      max memory:22.810000
                                                                                      Expand
                                                                                      • start[0.011s]
                                                                                          let (_x_0 : int) = count.list count.fill fills in
                                                                                          let (_x_1 : fill list) = List.tl fills in
                                                                                          let (_x_2 : int) = count.list count.fill _x_1 in
                                                                                          ((List.hd fills).fill_price = p)
                                                                                          && (fills <> [] && ((_x_0 >= 0) && (_x_2 >= 0)))
                                                                                          ==> not (((List.hd _x_1).fill_price = p) && _x_1 <> [])
                                                                                              || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                      • simplify
                                                                                        into:
                                                                                        let (_x_0 : fill list) = List.tl fills in
                                                                                        let (_x_1 : int) = count.list count.fill _x_0 in
                                                                                        let (_x_2 : int) = count.list count.fill fills in
                                                                                        not (((List.hd _x_0).fill_price = p) && _x_0 <> [])
                                                                                        || Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                        || not
                                                                                           (((List.hd fills).fill_price = p) && fills <> [] && (_x_2 >= 0)
                                                                                            && (_x_1 >= 0))
                                                                                        expansions:
                                                                                        []
                                                                                        rewrite_steps:
                                                                                          forward_chaining:
                                                                                          • unroll
                                                                                            expr:
                                                                                            (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                            (|count.list_1216/server|
                                                                                                              (|g…
                                                                                            expansions:
                                                                                            • unroll
                                                                                              expr:
                                                                                              (|count.list_1216/server| (|get.::.1_1202/server| fills_1203/server))
                                                                                              expansions:
                                                                                              • unroll
                                                                                                expr:
                                                                                                (|count.list_1216/server| fills_1203/server)
                                                                                                expansions:
                                                                                                • Unsat
                                                                                                Counterexample (after 7 steps, 0.022s):
                                                                                                let b : book =
                                                                                                  let (_x_0 : instrument) = Strategy STRAT1 in
                                                                                                  {b_buys =
                                                                                                   [{o_qty = 1142; o_price = 1236; o_time = 3; o_id = 4; o_side = BUY;
                                                                                                     o_client_id = 5; o_inst = _x_0; o_is_implied = true}];
                                                                                                   b_sells =
                                                                                                   [{o_qty = 1142; o_price = 56; o_time = 6; o_id = 7; o_side = BUY;
                                                                                                     o_client_id = 8; o_inst = _x_0; o_is_implied = true}]}
                                                                                                
                                                                                                Refuted
                                                                                                proof attempt
                                                                                                ground_instances:7
                                                                                                definitions:0
                                                                                                inductions:0
                                                                                                search_time:
                                                                                                0.022s
                                                                                                details:
                                                                                                Expand
                                                                                                smt_stats:
                                                                                                arith offset eqs:39
                                                                                                arith assert lower:86
                                                                                                arith patches_succ:2
                                                                                                datatype occurs check:323
                                                                                                datatype splits:370
                                                                                                arith bound prop:10
                                                                                                propagations:389
                                                                                                arith patches:2
                                                                                                interface eqs:6
                                                                                                conflicts:21
                                                                                                arith fixed eqs:39
                                                                                                datatype constructor ax:624
                                                                                                num allocs:118132630
                                                                                                final checks:25
                                                                                                added eqs:3191
                                                                                                del clause:86
                                                                                                num checks:15
                                                                                                arith tableau max rows:26
                                                                                                arith tableau max columns:50
                                                                                                arith pivots:57
                                                                                                rlimit count:22463
                                                                                                mk clause:250
                                                                                                mk bool var:1606
                                                                                                arith gcd tests:2
                                                                                                arith assert upper:84
                                                                                                decisions:444
                                                                                                arith row summations:151
                                                                                                arith assume eqs:6
                                                                                                datatype accessor ax:218
                                                                                                minimized lits:2
                                                                                                arith conflicts:4
                                                                                                arith num rows:26
                                                                                                arith assert diseq:1
                                                                                                arith eq adapter:50
                                                                                                time:0.002000
                                                                                                memory:24.000000
                                                                                                max memory:24.000000
                                                                                                Expand
                                                                                                • start[0.022s]
                                                                                                    let (_x_0 : order list) = ( :var_0: ).b_buys in
                                                                                                    let (_x_1 : order list) = ( :var_0: ).b_sells in
                                                                                                    side_price_sorted BUY _x_0 && side_price_sorted SELL _x_1
                                                                                                    ==> (if _x_0 <> []
                                                                                                         then
                                                                                                           if _x_1 <> []
                                                                                                           then
                                                                                                             if (List.hd _x_0).o_price >= (List.hd _x_1).o_price
                                                                                                             then (List.length … > 0) && fills_good_price … … else true
                                                                                                           else true
                                                                                                         else true)
                                                                                                • simplify

                                                                                                  into:
                                                                                                  let (_x_0 : order list) = ( :var_0: ).b_buys in
                                                                                                  let (_x_1 : order list) = ( :var_0: ).b_sells in
                                                                                                  (not (List.length … <= 0) && fills_good_price … …)
                                                                                                  || not ((List.hd _x_0).o_price >= (List.hd _x_1).o_price) || not (_x_1 <> [])
                                                                                                  || not (_x_0 <> [])
                                                                                                  || not (side_price_sorted BUY _x_0 && side_price_sorted SELL _x_1)
                                                                                                  expansions:
                                                                                                  []
                                                                                                  rewrite_steps:
                                                                                                    forward_chaining:
                                                                                                    • unroll
                                                                                                      expr:
                                                                                                      (side_price_sorted_1485/client
                                                                                                        SELL_1253/client
                                                                                                        (b_sells_1326/client b_1516/client))
                                                                                                      expansions:
                                                                                                      • unroll
                                                                                                        expr:
                                                                                                        (side_price_sorted_1485/client
                                                                                                          BUY_1252/client
                                                                                                          (b_buys_1325/client b_1516/client))
                                                                                                        expansions:
                                                                                                        • unroll
                                                                                                          expr:
                                                                                                          (|List.length_1274/server|
                                                                                                            (uncrossed_fills_1400/client (uncross_book_1454/client b_1516/client |[…
                                                                                                          expansions:
                                                                                                          • unroll
                                                                                                            expr:
                                                                                                            (uncross_book_1454/client b_1516/client |[]| 0)
                                                                                                            expansions:
                                                                                                            • unroll
                                                                                                              expr:
                                                                                                              (let ((a!1 (+ (o_price_1306/client
                                                                                                                              (|get.::.0_1267/server| (b_buys_1325/client b_151…
                                                                                                              expansions:
                                                                                                              • unroll
                                                                                                                expr:
                                                                                                                (let ((a!1 (<= (o_qty_1305/client
                                                                                                                                 (|get.::.0_1267/server| (b_sells_1326/client b_15…
                                                                                                                expansions:
                                                                                                                • unroll
                                                                                                                  expr:
                                                                                                                  (let ((a!1 (|::| (|get.::.0_1267/server|
                                                                                                                                     (|get.::.1_1268/server| (b_sells_1326/cl…
                                                                                                                  expansions:
                                                                                                                  • Sat (Some let b : book = let (_x_0 : instrument) = Strategy STRAT1 in {b_buys = [{o_qty = (Z.of_nativeint (1142n)); o_price = (Z.of_nativeint (1236n)); o_time = (Z.of_nativeint (3n)); o_id = (Z.of_nativeint (4n)); o_side = BUY; o_client_id = (Z.of_nativeint (5n)); o_inst = _x_0; o_is_implied = true}]; b_sells = [{o_qty = (Z.of_nativeint (1142n)); o_price = (Z.of_nativeint (56n)); o_time = (Z.of_nativeint (6n)); o_id = (Z.of_nativeint (7n)); o_side = BUY; o_client_id = (Z.of_nativeint (8n)); o_inst = _x_0; o_is_implied = true}]} )

                                                                                                                  Our second verification goal will look to make sure that no quantities are lost during uncrossing. Note that no fills are generated for implied orders (there's a different mechanism for that), so when we look at the book we will only consider outright orders. Note that o_qty represents the residual order quantity - for this demo, we do not differentiate between original, filled and residual order quantity. When order is created, the qty is set to that number and is decreased when filled.

                                                                                                                  In [8]:
                                                                                                                  (* All no quantities get lost during uncross *)
                                                                                                                  let no_lost_qtys (b : book) =
                                                                                                                  
                                                                                                                    let rec qtys_pos_nonimp = function
                                                                                                                      | [] -> true
                                                                                                                      | x::xs -> x.o_qty >= 0 && not x.o_is_implied && (qtys_pos_nonimp xs) in
                                                                                                                  
                                                                                                                    let rec sum_qtys = function
                                                                                                                      | [] -> 0
                                                                                                                      | x::xs -> x.o_qty + (sum_qtys xs) in
                                                                                                                  
                                                                                                                    let rec sum_fill_qtys = function
                                                                                                                      | [] -> 0
                                                                                                                      | x::xs -> x.fill_qty + (sum_fill_qtys xs) in
                                                                                                                  
                                                                                                                    let unc_res = uncross_book b [] 0 in
                                                                                                                  
                                                                                                                    (* We need to make sure the book is non-negative *)
                                                                                                                    let book_nonneg_nonimp = (qtys_pos_nonimp b.b_buys) && (qtys_pos_nonimp b.b_sells) in
                                                                                                                  
                                                                                                                    (* Let's sum up all of the quantities of orders before the uncross *)
                                                                                                                    let count_before = (sum_qtys b.b_buys) + (sum_qtys b.b_sells) in
                                                                                                                  
                                                                                                                    (* And after *)
                                                                                                                    let count_after = (sum_qtys unc_res.uncrossed_book.b_buys) +
                                                                                                                                      (sum_qtys unc_res.uncrossed_book.b_sells) +
                                                                                                                                      (sum_fill_qtys unc_res.uncrossed_fills) in
                                                                                                                  
                                                                                                                    book_nonneg_nonimp ==> (count_before = count_after)
                                                                                                                  ;;
                                                                                                                  
                                                                                                                  verify ~upto:15 no_lost_qtys
                                                                                                                  
                                                                                                                  Out[8]:
                                                                                                                  val no_lost_qtys : book -> bool = <fun>
                                                                                                                  - : book -> bool = <fun>
                                                                                                                  
                                                                                                                  termination proof

                                                                                                                  Termination proof

                                                                                                                  call `rec_fun.no_lost_qtys.sum_fill_qtys.2 (List.tl _z)` from `rec_fun.no_lost_qtys.sum_fill_qtys.2 _z`
                                                                                                                  original:rec_fun.no_lost_qtys.sum_fill_qtys.2 _z
                                                                                                                  sub:rec_fun.no_lost_qtys.sum_fill_qtys.2 (List.tl _z)
                                                                                                                  original ordinal:Ordinal.Int (_cnt _z)
                                                                                                                  sub ordinal:Ordinal.Int (_cnt (List.tl _z))
                                                                                                                  path:[_z <> []]
                                                                                                                  proof:
                                                                                                                  detailed proof
                                                                                                                  ground_instances:3
                                                                                                                  definitions:0
                                                                                                                  inductions:0
                                                                                                                  search_time:
                                                                                                                  0.011s
                                                                                                                  details:
                                                                                                                  Expand
                                                                                                                  smt_stats:
                                                                                                                  num checks:8
                                                                                                                  arith assert lower:20
                                                                                                                  arith tableau max rows:10
                                                                                                                  arith tableau max columns:35
                                                                                                                  arith pivots:17
                                                                                                                  rlimit count:4025
                                                                                                                  mk clause:53
                                                                                                                  datatype occurs check:22
                                                                                                                  mk bool var:122
                                                                                                                  arith assert upper:19
                                                                                                                  datatype splits:3
                                                                                                                  decisions:29
                                                                                                                  arith row summations:42
                                                                                                                  propagations:38
                                                                                                                  interface eqs:1
                                                                                                                  conflicts:10
                                                                                                                  arith fixed eqs:8
                                                                                                                  arith assume eqs:1
                                                                                                                  datatype accessor ax:10
                                                                                                                  arith conflicts:2
                                                                                                                  arith num rows:10
                                                                                                                  datatype constructor ax:11
                                                                                                                  num allocs:139427991
                                                                                                                  final checks:7
                                                                                                                  added eqs:81
                                                                                                                  del clause:23
                                                                                                                  arith eq adapter:15
                                                                                                                  memory:23.970000
                                                                                                                  max memory:24.000000
                                                                                                                  Expand
                                                                                                                  • start[0.011s]
                                                                                                                      let (_x_0 : int) = count.list count.fill _z in
                                                                                                                      let (_x_1 : fill list) = List.tl _z in
                                                                                                                      let (_x_2 : int) = count.list count.fill _x_1 in
                                                                                                                      _z <> [] && ((_x_0 >= 0) && (_x_2 >= 0))
                                                                                                                      ==> not (_x_1 <> [])
                                                                                                                          || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                                                  • simplify
                                                                                                                    into:
                                                                                                                    let (_x_0 : fill list) = List.tl _z in
                                                                                                                    let (_x_1 : int) = count.list count.fill _x_0 in
                                                                                                                    let (_x_2 : int) = count.list count.fill _z in
                                                                                                                    not (_x_0 <> []) || Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                                                    || not (_z <> [] && (_x_2 >= 0) && (_x_1 >= 0))
                                                                                                                    expansions:
                                                                                                                    []
                                                                                                                    rewrite_steps:
                                                                                                                      forward_chaining:
                                                                                                                      • unroll
                                                                                                                        expr:
                                                                                                                        (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                        (|count.list_1392/server|
                                                                                                                                          (|g…
                                                                                                                        expansions:
                                                                                                                        • unroll
                                                                                                                          expr:
                                                                                                                          (|count.list_1392/server| (|get.::.1_1378/server| _z_1381/server))
                                                                                                                          expansions:
                                                                                                                          • unroll
                                                                                                                            expr:
                                                                                                                            (|count.list_1392/server| _z_1381/server)
                                                                                                                            expansions:
                                                                                                                            • Unsat
                                                                                                                            termination proof

                                                                                                                            Termination proof

                                                                                                                            call `rec_fun.no_lost_qtys.sum_qtys.1 (List.tl _y)` from `rec_fun.no_lost_qtys.sum_qtys.1 _y`
                                                                                                                            original:rec_fun.no_lost_qtys.sum_qtys.1 _y
                                                                                                                            sub:rec_fun.no_lost_qtys.sum_qtys.1 (List.tl _y)
                                                                                                                            original ordinal:Ordinal.Int (_cnt _y)
                                                                                                                            sub ordinal:Ordinal.Int (_cnt (List.tl _y))
                                                                                                                            path:[_y <> []]
                                                                                                                            proof:
                                                                                                                            detailed proof
                                                                                                                            ground_instances:3
                                                                                                                            definitions:0
                                                                                                                            inductions:0
                                                                                                                            search_time:
                                                                                                                            0.013s
                                                                                                                            details:
                                                                                                                            Expand
                                                                                                                            smt_stats:
                                                                                                                            arith offset eqs:8
                                                                                                                            num checks:8
                                                                                                                            arith assert lower:108
                                                                                                                            arith tableau max rows:17
                                                                                                                            arith tableau max columns:47
                                                                                                                            arith pivots:48
                                                                                                                            rlimit count:12898
                                                                                                                            mk clause:128
                                                                                                                            datatype occurs check:23
                                                                                                                            mk bool var:486
                                                                                                                            arith assert upper:121
                                                                                                                            datatype splits:79
                                                                                                                            decisions:194
                                                                                                                            arith row summations:97
                                                                                                                            arith bound prop:5
                                                                                                                            propagations:184
                                                                                                                            conflicts:28
                                                                                                                            arith fixed eqs:42
                                                                                                                            datatype accessor ax:54
                                                                                                                            minimized lits:15
                                                                                                                            arith conflicts:12
                                                                                                                            arith num rows:17
                                                                                                                            arith assert diseq:5
                                                                                                                            datatype constructor ax:94
                                                                                                                            num allocs:159893563
                                                                                                                            final checks:6
                                                                                                                            added eqs:558
                                                                                                                            del clause:92
                                                                                                                            arith eq adapter:104
                                                                                                                            memory:24.150000
                                                                                                                            max memory:24.150000
                                                                                                                            Expand
                                                                                                                            • start[0.013s]
                                                                                                                                let (_x_0 : int) = count.list count.order _y in
                                                                                                                                let (_x_1 : order list) = List.tl _y in
                                                                                                                                let (_x_2 : int) = count.list count.order _x_1 in
                                                                                                                                _y <> [] && ((_x_0 >= 0) && (_x_2 >= 0))
                                                                                                                                ==> not (_x_1 <> [])
                                                                                                                                    || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                                                            • simplify
                                                                                                                              into:
                                                                                                                              let (_x_0 : order list) = List.tl _y in
                                                                                                                              let (_x_1 : int) = count.list count.order _x_0 in
                                                                                                                              let (_x_2 : int) = count.list count.order _y in
                                                                                                                              Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                                                              || not (_y <> [] && (_x_2 >= 0) && (_x_1 >= 0)) || not (_x_0 <> [])
                                                                                                                              expansions:
                                                                                                                              []
                                                                                                                              rewrite_steps:
                                                                                                                                forward_chaining:
                                                                                                                                • unroll
                                                                                                                                  expr:
                                                                                                                                  (|count.list_1428/server| (|get.::.1_1374/server| _y_1421/server))
                                                                                                                                  expansions:
                                                                                                                                  • unroll
                                                                                                                                    expr:
                                                                                                                                    (|count.list_1428/server| _y_1421/server)
                                                                                                                                    expansions:
                                                                                                                                    • unroll
                                                                                                                                      expr:
                                                                                                                                      (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                      (|count.list_1428/server|
                                                                                                                                                        (|g…
                                                                                                                                      expansions:
                                                                                                                                      • Unsat
                                                                                                                                      termination proof

                                                                                                                                      Termination proof

                                                                                                                                      call `rec_fun.no_lost_qtys.qtys_pos_nonimp.0 (List.tl _x)` from `rec_fun.no_lost_qtys.qtys_pos_nonimp.0 _x`
                                                                                                                                      original:rec_fun.no_lost_qtys.qtys_pos_nonimp.0 _x
                                                                                                                                      sub:rec_fun.no_lost_qtys.qtys_pos_nonimp.0 (List.tl _x)
                                                                                                                                      original ordinal:Ordinal.Int (_cnt _x)
                                                                                                                                      sub ordinal:Ordinal.Int (_cnt (List.tl _x))
                                                                                                                                      path:[not (List.hd _x).o_is_implied && (List.hd _x).o_qty >= 0 && _x <> []]
                                                                                                                                      proof:
                                                                                                                                      detailed proof
                                                                                                                                      ground_instances:3
                                                                                                                                      definitions:0
                                                                                                                                      inductions:0
                                                                                                                                      search_time:
                                                                                                                                      0.013s
                                                                                                                                      details:
                                                                                                                                      Expand
                                                                                                                                      smt_stats:
                                                                                                                                      num checks:8
                                                                                                                                      arith assert lower:71
                                                                                                                                      arith tableau max rows:23
                                                                                                                                      arith tableau max columns:51
                                                                                                                                      arith pivots:60
                                                                                                                                      rlimit count:34251
                                                                                                                                      mk clause:87
                                                                                                                                      datatype occurs check:29
                                                                                                                                      mk bool var:311
                                                                                                                                      arith assert upper:40
                                                                                                                                      datatype splits:51
                                                                                                                                      decisions:93
                                                                                                                                      arith row summations:240
                                                                                                                                      propagations:83
                                                                                                                                      interface eqs:4
                                                                                                                                      conflicts:10
                                                                                                                                      arith fixed eqs:37
                                                                                                                                      arith assume eqs:4
                                                                                                                                      datatype accessor ax:36
                                                                                                                                      arith conflicts:2
                                                                                                                                      arith num rows:23
                                                                                                                                      datatype constructor ax:70
                                                                                                                                      num allocs:182181043
                                                                                                                                      final checks:10
                                                                                                                                      added eqs:356
                                                                                                                                      del clause:60
                                                                                                                                      arith eq adapter:40
                                                                                                                                      memory:24.220000
                                                                                                                                      max memory:24.220000
                                                                                                                                      Expand
                                                                                                                                      • start[0.013s]
                                                                                                                                          let (_x_0 : order) = List.hd _x in
                                                                                                                                          let (_x_1 : int) = count.list count.order _x in
                                                                                                                                          let (_x_2 : order list) = List.tl _x in
                                                                                                                                          let (_x_3 : int) = count.list count.order _x_2 in
                                                                                                                                          let (_x_4 : order) = List.hd _x_2 in
                                                                                                                                          not _x_0.o_is_implied
                                                                                                                                          && ((_x_0.o_qty >= 0) && (_x <> [] && ((_x_1 >= 0) && (_x_3 >= 0))))
                                                                                                                                          ==> not (not _x_4.o_is_implied && ((_x_4.o_qty >= 0) && _x_2 <> []))
                                                                                                                                              || Ordinal.( << ) (Ordinal.Int _x_3) (Ordinal.Int _x_1)
                                                                                                                                      • simplify
                                                                                                                                        into:
                                                                                                                                        let (_x_0 : order list) = List.tl _x in
                                                                                                                                        let (_x_1 : int) = count.list count.order _x_0 in
                                                                                                                                        let (_x_2 : int) = count.list count.order _x in
                                                                                                                                        let (_x_3 : order) = List.hd _x in
                                                                                                                                        let (_x_4 : order) = List.hd _x_0 in
                                                                                                                                        Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                                                                        || not
                                                                                                                                           (not _x_3.o_is_implied && (_x_3.o_qty >= 0) && _x <> [] && (_x_2 >= 0)
                                                                                                                                            && (_x_1 >= 0))
                                                                                                                                        || not (not _x_4.o_is_implied && (_x_4.o_qty >= 0) && _x_0 <> [])
                                                                                                                                        expansions:
                                                                                                                                        []
                                                                                                                                        rewrite_steps:
                                                                                                                                          forward_chaining:
                                                                                                                                          • unroll
                                                                                                                                            expr:
                                                                                                                                            (|count.list_1428/server| (|get.::.1_1374/server| _x_1457/server))
                                                                                                                                            expansions:
                                                                                                                                            • unroll
                                                                                                                                              expr:
                                                                                                                                              (|count.list_1428/server| _x_1457/server)
                                                                                                                                              expansions:
                                                                                                                                              • unroll
                                                                                                                                                expr:
                                                                                                                                                (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                                (|count.list_1428/server|
                                                                                                                                                                  (|g…
                                                                                                                                                expansions:
                                                                                                                                                • Unsat
                                                                                                                                                Proved up to 15 steps

                                                                                                                                                2.4 Test generation

                                                                                                                                                First, we will decompose the function and then generate test cases for it.

                                                                                                                                                In [9]:
                                                                                                                                                (* This is a 'side_condition' function that tells decomposition that we're only interested in cases where the
                                                                                                                                                initial fills are empty *)
                                                                                                                                                let cond (b : book) (fills : fill list) (filled_qty : int) =
                                                                                                                                                 fills = [] && filled_qty = 0
                                                                                                                                                ;;
                                                                                                                                                
                                                                                                                                                let d = Modular_decomp.top ~assuming:"cond" "uncross_book" ~prune:true [@@program];;
                                                                                                                                                
                                                                                                                                                Out[9]:
                                                                                                                                                val cond : book -> fill list -> Z.t -> bool = <fun>
                                                                                                                                                val d : Modular_decomp_intf.decomp_ref = <abstr>
                                                                                                                                                
                                                                                                                                                Regions details

                                                                                                                                                No group selected.

                                                                                                                                                • Concrete regions are numbered
                                                                                                                                                • Unnumbered regions are groups whose children share a particular constraint
                                                                                                                                                • Click on a region to view its details
                                                                                                                                                • Double click on a region to zoom in on it
                                                                                                                                                • Shift+double click to zoom out
                                                                                                                                                • Hit escape to reset back to the top
                                                                                                                                                decomp of (uncross_book b, fills, filled_qty
                                                                                                                                                Reg_idConstraintsInvariant
                                                                                                                                                19
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (fills <> [])
                                                                                                                                                • not Is_a([], b.b_buys)
                                                                                                                                                • not (b.b_sells <> [])
                                                                                                                                                {uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty}
                                                                                                                                                18
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (fills <> [])
                                                                                                                                                • Is_a([], b.b_buys)
                                                                                                                                                • not (b.b_sells <> [])
                                                                                                                                                {uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty}
                                                                                                                                                17
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (fills <> [])
                                                                                                                                                • not (b.b_buys <> [])
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                {uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty}
                                                                                                                                                16
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not ((List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price)
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                {uncrossed_book = b; uncrossed_fills = fills; uncrossed_qty = filled_qty}
                                                                                                                                                15
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0)
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_2 : order list) = b.b_sells in
                                                                                                                                                let (_x_3 : int) = (List.hd _x_2).o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = {_x_1 with o_qty = _x_1.o_qty - _x_3} :: (List.tl _x_0);
                                                                                                                                                 b_sells = List.tl _x_2}
                                                                                                                                                fills (filled_qty + _x_3)
                                                                                                                                                14
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0)
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_2 : order list) = b.b_sells in
                                                                                                                                                let (_x_3 : order) = List.hd _x_2 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = {_x_1 with o_qty = _x_1.o_qty - _x_4} :: (List.tl _x_0);
                                                                                                                                                 b_sells = List.tl _x_2}
                                                                                                                                                ({fill_client_id = _x_1.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_1.o_price + _x_3.o_price) / 2; fill_order_id = _x_1.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                13
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0)
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_2 : order list) = b.b_sells in
                                                                                                                                                let (_x_3 : order) = List.hd _x_2 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = {_x_1 with o_qty = _x_1.o_qty - _x_4} :: (List.tl _x_0);
                                                                                                                                                 b_sells = List.tl _x_2}
                                                                                                                                                ({fill_client_id = _x_3.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_1.o_price + _x_3.o_price) / 2; fill_order_id = _x_3.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                12
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0)
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_2 : order list) = b.b_sells in
                                                                                                                                                let (_x_3 : order) = List.hd _x_2 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                let (_x_5 : int) = (_x_1.o_price + _x_3.o_price) / 2 in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = {_x_1 with o_qty = _x_1.o_qty - _x_4} :: (List.tl _x_0);
                                                                                                                                                 b_sells = List.tl _x_2}
                                                                                                                                                ({fill_client_id = _x_3.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                  fill_order_id = _x_3.o_id; fill_order_done = true}
                                                                                                                                                 ::
                                                                                                                                                 ({fill_client_id = _x_1.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                   fill_order_id = _x_1.o_id; fill_order_done = true}
                                                                                                                                                  :: fills))
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                11
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_sells in
                                                                                                                                                uncross_book {b_buys = List.tl b.b_buys; b_sells = List.tl _x_0} fills
                                                                                                                                                (filled_qty + (List.hd _x_0).o_qty)
                                                                                                                                                10
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_2.o_price + _x_3.o_price) / 2; fill_order_id = _x_2.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                9
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : int) = _x_2.o_qty in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_3;
                                                                                                                                                  fill_price = ((List.hd _x_0).o_price + _x_2.o_price) / 2;
                                                                                                                                                  fill_order_id = _x_2.o_id; fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_3)
                                                                                                                                                8
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_buys).o_qty - (List.hd b.b_sells).o_qty = 0
                                                                                                                                                • not ((List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty)
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : int) = _x_2.o_qty in
                                                                                                                                                let (_x_4 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_5 : int) = (_x_4.o_price + _x_2.o_price) / 2 in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_3; fill_price = _x_5;
                                                                                                                                                  fill_order_id = _x_2.o_id; fill_order_done = true}
                                                                                                                                                 ::
                                                                                                                                                 ({fill_client_id = _x_4.o_client_id; fill_qty = _x_3; fill_price = _x_5;
                                                                                                                                                   fill_order_id = _x_4.o_id; fill_order_done = true}
                                                                                                                                                  :: fills))
                                                                                                                                                (filled_qty + _x_3)
                                                                                                                                                7
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0)
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : int) = (List.hd _x_0).o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = List.tl _x_0;
                                                                                                                                                 b_sells = {_x_2 with o_qty = _x_2.o_qty - _x_3} :: (List.tl _x_1)}
                                                                                                                                                fills (filled_qty + _x_3)
                                                                                                                                                6
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0)
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = List.tl _x_0;
                                                                                                                                                 b_sells = {_x_2 with o_qty = _x_2.o_qty - _x_4} :: (List.tl _x_1)}
                                                                                                                                                ({fill_client_id = _x_3.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_3.o_price + _x_2.o_price) / 2; fill_order_id = _x_3.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                5
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0)
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = List.tl _x_0;
                                                                                                                                                 b_sells = {_x_2 with o_qty = _x_2.o_qty - _x_4} :: (List.tl _x_1)}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_3.o_price + _x_2.o_price) / 2; fill_order_id = _x_2.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                4
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • not ((List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0)
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                let (_x_5 : int) = (_x_3.o_price + _x_2.o_price) / 2 in
                                                                                                                                                uncross_book
                                                                                                                                                {b_buys = List.tl _x_0;
                                                                                                                                                 b_sells = {_x_2 with o_qty = _x_2.o_qty - _x_4} :: (List.tl _x_1)}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                  fill_order_id = _x_2.o_id; fill_order_done = true}
                                                                                                                                                 ::
                                                                                                                                                 ({fill_client_id = _x_3.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                   fill_order_id = _x_3.o_id; fill_order_done = true}
                                                                                                                                                  :: fills))
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                3
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl b.b_sells} fills
                                                                                                                                                (filled_qty + (List.hd _x_0).o_qty)
                                                                                                                                                2
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_3 : int) = _x_2.o_qty in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_3;
                                                                                                                                                  fill_price = (_x_2.o_price + (List.hd _x_1).o_price) / 2;
                                                                                                                                                  fill_order_id = _x_2.o_id; fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_3)
                                                                                                                                                1
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_4;
                                                                                                                                                  fill_price = (_x_3.o_price + _x_2.o_price) / 2; fill_order_id = _x_2.o_id;
                                                                                                                                                  fill_order_done = true}
                                                                                                                                                 :: fills)
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                0
                                                                                                                                                • fills = []
                                                                                                                                                • filled_qty = 0
                                                                                                                                                • not (List.hd b.b_buys).o_is_implied
                                                                                                                                                • not (List.hd b.b_sells).o_is_implied
                                                                                                                                                • (List.hd b.b_sells).o_qty - (List.hd b.b_buys).o_qty = 0
                                                                                                                                                • (List.hd b.b_buys).o_qty < (List.hd b.b_sells).o_qty
                                                                                                                                                • (List.hd b.b_buys).o_price >= (List.hd b.b_sells).o_price
                                                                                                                                                • b.b_buys <> []
                                                                                                                                                • b.b_sells <> []
                                                                                                                                                let (_x_0 : order list) = b.b_buys in
                                                                                                                                                let (_x_1 : order list) = b.b_sells in
                                                                                                                                                let (_x_2 : order) = List.hd _x_1 in
                                                                                                                                                let (_x_3 : order) = List.hd _x_0 in
                                                                                                                                                let (_x_4 : int) = _x_3.o_qty in
                                                                                                                                                let (_x_5 : int) = (_x_3.o_price + _x_2.o_price) / 2 in
                                                                                                                                                uncross_book {b_buys = List.tl _x_0; b_sells = List.tl _x_1}
                                                                                                                                                ({fill_client_id = _x_2.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                  fill_order_id = _x_2.o_id; fill_order_done = true}
                                                                                                                                                 ::
                                                                                                                                                 ({fill_client_id = _x_3.o_client_id; fill_qty = _x_4; fill_price = _x_5;
                                                                                                                                                   fill_order_id = _x_3.o_id; fill_order_done = true}
                                                                                                                                                  :: fills))
                                                                                                                                                (filled_qty + _x_4)
                                                                                                                                                In [10]:
                                                                                                                                                (* Now let's try to generate some test cases *)
                                                                                                                                                
                                                                                                                                                (* This will auto-generate model extractor *)
                                                                                                                                                Extract.eval ~quiet:true ~signature:(Event.DB.fun_id_of_str (db()) "uncross_book") ();;
                                                                                                                                                
                                                                                                                                                #remove_doc doc_of_book;;
                                                                                                                                                #remove_doc doc_of_order;;
                                                                                                                                                Modular_decomp.get_regions d |> CCList.map (fun r -> r |> Modular_decomp.get_model |> Mex.of_model);;
                                                                                                                                                #install_doc doc_of_order;;
                                                                                                                                                #install_doc doc_of_book;;
                                                                                                                                                
                                                                                                                                                Out[10]:
                                                                                                                                                                                                  - : unit
                                                                                                                                                            =
                                                                                                                                                            ()
                                                                                                                                                - : Mex.extract_type list =
                                                                                                                                                [{Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 1; o_price = 6483; o_time = 5; o_id = 6; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = true}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 1; o_price = 6483; o_time = 5; o_id = 6; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 1; o_price = 6483; o_time = 5; o_id = 6; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = true}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = true}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 1; o_price = 6483; o_time = 5; o_id = 6; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = true}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 38; o_time = 2; o_id = 1; o_side = BUY;
                                                                                                                                                       o_client_id = 3; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 0; o_price = -7681; o_time = 4; o_id = 5; o_side = BUY;
                                                                                                                                                       o_client_id = 6; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 38; o_time = 1; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 2; o_inst = Strategy STRAT1; o_is_implied = true}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 0; o_price = -7681; o_time = 6; o_id = 4; o_side = BUY;
                                                                                                                                                       o_client_id = 5; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 38; o_time = 1; o_id = 2; o_side = BUY;
                                                                                                                                                       o_client_id = 3; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 0; o_price = -7681; o_time = 5; o_id = 4; o_side = BUY;
                                                                                                                                                       o_client_id = 6; o_inst = Strategy STRAT1; o_is_implied = true}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 38; o_time = 1; o_id = 2; o_side = BUY;
                                                                                                                                                       o_client_id = 3; o_inst = Strategy STRAT1; o_is_implied = true}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = 0; o_price = -7681; o_time = 4; o_id = 5; o_side = BUY;
                                                                                                                                                       o_client_id = 6; o_inst = Strategy STRAT1; o_is_implied = true}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 3; o_id = 4; o_side = BUY;
                                                                                                                                                       o_client_id = 2; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = -1; o_price = 6483; o_time = 5; o_id = 6; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = true}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = -1; o_price = 6483; o_time = 6; o_id = 5; o_side = BUY;
                                                                                                                                                       o_client_id = 7; o_inst = Strategy STRAT1; o_is_implied = false}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 2; o_id = 3; o_side = BUY;
                                                                                                                                                       o_client_id = 4; o_inst = Strategy STRAT1; o_is_implied = false}];
                                                                                                                                                    b_sells =
                                                                                                                                                     [{o_qty = -1; o_price = 6483; o_time = 5; o_id = 7; o_side = BUY;
                                                                                                                                                       o_client_id = 6; o_inst = Strategy STRAT1; o_is_implied = true}]};
                                                                                                                                                  fills = []; filled_qty = 0};
                                                                                                                                                 {Mex.b =
                                                                                                                                                   {b_buys =
                                                                                                                                                     [{o_qty = 0; o_price = 7719; o_time = 4; o_id = 2; o_side = BUY;
                                                                                                                                                       o_client_id = 3; o_inst = ...; o_is_implied = ...}];
                                                                                                                                                    b_sells = [...]};
                                                                                                                                                  fills = []; filled_qty = 0};...;...;...;...]
                                                                                                                                                

                                                                                                                                                3 Implied trading

                                                                                                                                                3.1 Strategy ranking

                                                                                                                                                When generating implied orders for strategies, there's a criteria used to rank strategies - this section encodes the comparison function.

                                                                                                                                                In [11]:
                                                                                                                                                (* Calculate somehow how big the ratio is *)
                                                                                                                                                let leg_ratio (s : strategy) =
                                                                                                                                                  let abs x = if x < 0 then -x else x in
                                                                                                                                                  (abs s.leg1.leg_mult) + (abs s.leg2.leg_mult) + (abs s.leg3.leg_mult)
                                                                                                                                                ;;
                                                                                                                                                
                                                                                                                                                (* Nearest time to expiry *)
                                                                                                                                                let nearest_time_to_exp (s : strategy) =
                                                                                                                                                  let exp =
                                                                                                                                                    if (month_to_int (contract_expiry s.leg1.leg_sec_idx)) < (month_to_int (contract_expiry s.leg2.leg_sec_idx)) then
                                                                                                                                                      contract_expiry s.leg1.leg_sec_idx
                                                                                                                                                    else
                                                                                                                                                      contract_expiry s.leg2.leg_sec_idx in
                                                                                                                                                
                                                                                                                                                  if (month_to_int exp) < (month_to_int (contract_expiry s.leg2.leg_sec_idx)) then
                                                                                                                                                    exp
                                                                                                                                                  else
                                                                                                                                                    contract_expiry s.leg2.leg_sec_idx
                                                                                                                                                ;;
                                                                                                                                                
                                                                                                                                                (* Return true if s1 should implied uncross before s2 *)
                                                                                                                                                let priority_strat (s1 : strategy) (s2 : strategy) =
                                                                                                                                                  (*
                                                                                                                                                    1. time to expiry of the nearest leg
                                                                                                                                                    2. strategy types (strategies with the greater leg ratio executed first)
                                                                                                                                                    3. strategy creation times *)
                                                                                                                                                  if (month_to_int (nearest_time_to_exp s1)) < (month_to_int (nearest_time_to_exp s2)) then
                                                                                                                                                    true
                                                                                                                                                  else
                                                                                                                                                    if (leg_ratio s1) > (leg_ratio s2) then
                                                                                                                                                      true
                                                                                                                                                    else
                                                                                                                                                      s1.time_created <= s2.time_created
                                                                                                                                                
                                                                                                                                                Out[11]:
                                                                                                                                                val leg_ratio : strategy -> Z.t = <fun>
                                                                                                                                                val nearest_time_to_exp : strategy -> month = <fun>
                                                                                                                                                val priority_strat : strategy -> strategy -> bool = <fun>
                                                                                                                                                
                                                                                                                                                In [12]:
                                                                                                                                                let transitivity s1 s2 s3 =
                                                                                                                                                 ((priority_strat s1 s2) && (priority_strat s2 s3)) ==> (priority_strat s1 s3)
                                                                                                                                                
                                                                                                                                                verify transitivity
                                                                                                                                                
                                                                                                                                                Out[12]:
                                                                                                                                                val transitivity : strategy -> strategy -> strategy -> bool = <fun>
                                                                                                                                                - : strategy -> strategy -> strategy -> bool = <fun>
                                                                                                                                                module CX : sig val s1 : strategy val s2 : strategy val s3 : strategy end
                                                                                                                                                
                                                                                                                                                Counterexample (after 0 steps, 0.028s):
                                                                                                                                                let s1 : strategy =
                                                                                                                                                  {time_created = 0; leg1 = {leg_sec_idx = OUT3; leg_mult = 1602};
                                                                                                                                                   leg2 = {leg_sec_idx = OUT3; leg_mult = 590};
                                                                                                                                                   leg3 = {leg_sec_idx = OUT1; leg_mult = 2324}}
                                                                                                                                                let s2 : strategy =
                                                                                                                                                  {time_created = 3609; leg1 = {leg_sec_idx = OUT2; leg_mult = 3045};
                                                                                                                                                   leg2 = {leg_sec_idx = OUT3; leg_mult = 49};
                                                                                                                                                   leg3 = {leg_sec_idx = OUT1; leg_mult = 1421}}
                                                                                                                                                let s3 : strategy =
                                                                                                                                                  {time_created = (-1); leg1 = {leg_sec_idx = OUT3; leg_mult = 2240};
                                                                                                                                                   leg2 = {leg_sec_idx = OUT3; leg_mult = 1};
                                                                                                                                                   leg3 = {leg_sec_idx = OUT1; leg_mult = 2275}}
                                                                                                                                                
                                                                                                                                                Refuted
                                                                                                                                                proof attempt
                                                                                                                                                ground_instances:0
                                                                                                                                                definitions:0
                                                                                                                                                inductions:0
                                                                                                                                                search_time:
                                                                                                                                                0.028s
                                                                                                                                                details:
                                                                                                                                                Expand
                                                                                                                                                smt_stats:
                                                                                                                                                arith offset eqs:36
                                                                                                                                                num checks:1
                                                                                                                                                arith assert lower:642
                                                                                                                                                arith tableau max rows:30
                                                                                                                                                arith tableau max columns:65
                                                                                                                                                arith pivots:67
                                                                                                                                                rlimit count:28708
                                                                                                                                                mk clause:585
                                                                                                                                                datatype occurs check:3
                                                                                                                                                mk bool var:1300
                                                                                                                                                arith assert upper:314
                                                                                                                                                datatype splits:126
                                                                                                                                                decisions:746
                                                                                                                                                arith row summations:188
                                                                                                                                                arith bound prop:9
                                                                                                                                                propagations:1413
                                                                                                                                                conflicts:55
                                                                                                                                                arith fixed eqs:126
                                                                                                                                                datatype accessor ax:15
                                                                                                                                                minimized lits:3
                                                                                                                                                arith conflicts:9
                                                                                                                                                arith num rows:30
                                                                                                                                                arith assert diseq:163
                                                                                                                                                datatype constructor ax:163
                                                                                                                                                num allocs:1310006378
                                                                                                                                                final checks:1
                                                                                                                                                added eqs:1880
                                                                                                                                                del clause:315
                                                                                                                                                arith eq adapter:395
                                                                                                                                                time:0.017000
                                                                                                                                                memory:26.410000
                                                                                                                                                max memory:27.130000
                                                                                                                                                Expand
                                                                                                                                                • start[0.028s]
                                                                                                                                                    let (_x_0 : int) = ( :var_0: ).time_created in
                                                                                                                                                    let (_x_1 : int) = ( :var_1: ).time_created in
                                                                                                                                                    let (_x_2 : leg) = ( :var_0: ).leg1 in
                                                                                                                                                    let (_x_3 : int) = _x_2.leg_mult in
                                                                                                                                                    let (_x_4 : leg) = ( :var_0: ).leg2 in
                                                                                                                                                    let (_x_5 : int) = _x_4.leg_mult in
                                                                                                                                                    let (_x_6 : int) = ( :var_0: ).leg3.leg_mult in
                                                                                                                                                    let (_x_7 : int)
                                                                                                                                                        = (if _x_3 < 0 then ~- _x_3 else _x_3)
                                                                                                                                                          + (if _x_5 < 0 then ~- _x_5 else _x_5)
                                                                                                                                                          + (if _x_6 < 0 then ~- _x_6 else _x_6)
                                                                                                                                                    in
                                                                                                                                                    let (_x_8 : leg) = ( :var_1: ).leg1 in
                                                                                                                                                    let (_x_9 : int) = _x_8.leg_mult in
                                                                                                                                                    let (_x_10 : leg) = ( :var_1: ).leg2 in
                                                                                                                                                    let (_x_11 : int) = _x_10.leg_mult in
                                                                                                                                                    let (_x_12 : int) = ( :var_1: ).leg3.leg_mult in
                                                                                                                                                    let (_x_13 : int)
                                                                                                                                                        = (if _x_9 < 0 then ~- _x_9 else _x_9)
                                                                                                                                                          + (if _x_11 < 0 then ~- _x_11 else _x_11)
                                                                                                                                                          + (if _x_12 < 0 then ~- _x_12 else _x_12)
                                                                                                                                                    in
                                                                                                                                                    let (_x_14 : outright_id) = _x_4.leg_sec_idx in
                                                                                                                                                    let (_x_15 : bool) = _x_14 = OUT1 in
                                                                                                                                                    let (_x_16 : month) = if _x_15 then Mar else … in
                                                                                                                                                    let (_x_17 : outright_id) = _x_2.leg_sec_idx in
                                                                                                                                                    let (_x_18 : bool) = _x_17 = OUT1 in
                                                                                                                                                    let (_x_19 : month)
                                                                                                                                                        = if _x_18 then Mar else if _x_17 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_20 : month)
                                                                                                                                                        = if _x_15 then Mar else if _x_14 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_21 : int)
                                                                                                                                                        = if _x_20 = Mar then 3
                                                                                                                                                          else if _x_20 = Jun then 6 else if _x_20 = Sep then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    let (_x_22 : bool)
                                                                                                                                                        = (if _x_19 = Mar then 3
                                                                                                                                                           else if _x_19 = Jun then 6 else if _x_19 = Sep then 9 else 12)
                                                                                                                                                          < _x_21
                                                                                                                                                    in
                                                                                                                                                    let (_x_23 : month) = if _x_22 then if _x_18 then Mar else … else _x_16
                                                                                                                                                    in
                                                                                                                                                    let (_x_24 : month) = if _x_22 then _x_19 else _x_20 in
                                                                                                                                                    let (_x_25 : bool)
                                                                                                                                                        = (if _x_24 = Mar then 3
                                                                                                                                                           else if _x_24 = Jun then 6 else if _x_23 = Sep then 9 else 12)
                                                                                                                                                          < _x_21
                                                                                                                                                    in
                                                                                                                                                    let (_x_26 : int)
                                                                                                                                                        = if (if _x_25 then _x_24 else _x_20) = Mar then 3
                                                                                                                                                          else
                                                                                                                                                          if (if _x_25 then _x_23 else _x_20) = Jun then 6
                                                                                                                                                          else
                                                                                                                                                          if (if _x_25 then if _x_22 then … else … else _x_16) = Sep 
                                                                                                                                                          then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    let (_x_27 : outright_id) = _x_10.leg_sec_idx in
                                                                                                                                                    let (_x_28 : bool) = _x_27 = OUT1 in
                                                                                                                                                    let (_x_29 : month) = if _x_28 then Mar else … in
                                                                                                                                                    let (_x_30 : outright_id) = _x_8.leg_sec_idx in
                                                                                                                                                    let (_x_31 : bool) = _x_30 = OUT1 in
                                                                                                                                                    let (_x_32 : month)
                                                                                                                                                        = if _x_31 then Mar else if _x_30 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_33 : month)
                                                                                                                                                        = if _x_28 then Mar else if _x_27 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_34 : int)
                                                                                                                                                        = if _x_33 = Mar then 3
                                                                                                                                                          else if _x_33 = Jun then 6 else if _x_33 = Sep then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    let (_x_35 : bool)
                                                                                                                                                        = (if _x_32 = Mar then 3
                                                                                                                                                           else if _x_32 = Jun then 6 else if _x_32 = Sep then 9 else 12)
                                                                                                                                                          < _x_34
                                                                                                                                                    in
                                                                                                                                                    let (_x_36 : month) = if _x_35 then if _x_31 then Mar else … else _x_29
                                                                                                                                                    in
                                                                                                                                                    let (_x_37 : month) = if _x_35 then _x_32 else _x_33 in
                                                                                                                                                    let (_x_38 : bool)
                                                                                                                                                        = (if _x_37 = Mar then 3
                                                                                                                                                           else if _x_37 = Jun then 6 else if _x_36 = Sep then 9 else 12)
                                                                                                                                                          < _x_34
                                                                                                                                                    in
                                                                                                                                                    let (_x_39 : int)
                                                                                                                                                        = if (if _x_38 then _x_37 else _x_33) = Mar then 3
                                                                                                                                                          else
                                                                                                                                                          if (if _x_38 then _x_36 else _x_33) = Jun then 6
                                                                                                                                                          else
                                                                                                                                                          if (if _x_38 then if _x_35 then … else … else _x_29) = Sep 
                                                                                                                                                          then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    let (_x_40 : int) = ( :var_2: ).time_created in
                                                                                                                                                    let (_x_41 : leg) = ( :var_2: ).leg1 in
                                                                                                                                                    let (_x_42 : int) = _x_41.leg_mult in
                                                                                                                                                    let (_x_43 : leg) = ( :var_2: ).leg2 in
                                                                                                                                                    let (_x_44 : int) = _x_43.leg_mult in
                                                                                                                                                    let (_x_45 : int) = ( :var_2: ).leg3.leg_mult in
                                                                                                                                                    let (_x_46 : int)
                                                                                                                                                        = (if _x_42 < 0 then ~- _x_42 else _x_42)
                                                                                                                                                          + (if _x_44 < 0 then ~- _x_44 else _x_44)
                                                                                                                                                          + (if _x_45 < 0 then ~- _x_45 else _x_45)
                                                                                                                                                    in
                                                                                                                                                    let (_x_47 : outright_id) = _x_43.leg_sec_idx in
                                                                                                                                                    let (_x_48 : bool) = _x_47 = OUT1 in
                                                                                                                                                    let (_x_49 : month) = if _x_48 then Mar else … in
                                                                                                                                                    let (_x_50 : outright_id) = _x_41.leg_sec_idx in
                                                                                                                                                    let (_x_51 : bool) = _x_50 = OUT1 in
                                                                                                                                                    let (_x_52 : month)
                                                                                                                                                        = if _x_51 then Mar else if _x_50 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_53 : month)
                                                                                                                                                        = if _x_48 then Mar else if _x_47 = OUT2 then Jun else Sep
                                                                                                                                                    in
                                                                                                                                                    let (_x_54 : int)
                                                                                                                                                        = if _x_53 = Mar then 3
                                                                                                                                                          else if _x_53 = Jun then 6 else if _x_53 = Sep then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    let (_x_55 : bool)
                                                                                                                                                        = (if _x_52 = Mar then 3
                                                                                                                                                           else if _x_52 = Jun then 6 else if _x_52 = Sep then 9 else 12)
                                                                                                                                                          < _x_54
                                                                                                                                                    in
                                                                                                                                                    let (_x_56 : month) = if _x_55 then if _x_51 then Mar else … else _x_49
                                                                                                                                                    in
                                                                                                                                                    let (_x_57 : month) = if _x_55 then _x_52 else _x_53 in
                                                                                                                                                    let (_x_58 : bool)
                                                                                                                                                        = (if _x_57 = Mar then 3
                                                                                                                                                           else if _x_57 = Jun then 6 else if _x_56 = Sep then 9 else 12)
                                                                                                                                                          < _x_54
                                                                                                                                                    in
                                                                                                                                                    let (_x_59 : int)
                                                                                                                                                        = if (if _x_58 then _x_57 else _x_53) = Mar then 3
                                                                                                                                                          else
                                                                                                                                                          if (if _x_58 then _x_56 else _x_53) = Jun then 6
                                                                                                                                                          else
                                                                                                                                                          if (if _x_58 then if _x_55 then … else … else _x_49) = Sep 
                                                                                                                                                          then 9 else 12
                                                                                                                                                    in
                                                                                                                                                    (if _x_26 < _x_39 then true
                                                                                                                                                     else if _x_7 > _x_13 then true else _x_0 <= _x_1)
                                                                                                                                                    && (if _x_39 < _x_59 then true
                                                                                                                                                        else if _x_13 > _x_46 then true else _x_1 <= _x_40)
                                                                                                                                                    ==> (if _x_26 < _x_59 then true
                                                                                                                                                         else if _x_7 > _x_46 then true else _x_0 <= _x_40)
                                                                                                                                                • simplify

                                                                                                                                                  into:
                                                                                                                                                  let (_x_0 : int) = ( :var_0: ).time_created in
                                                                                                                                                  let (_x_1 : int) = ( :var_2: ).time_created in
                                                                                                                                                  let (_x_2 : leg) = ( :var_2: ).leg1 in
                                                                                                                                                  let (_x_3 : outright_id) = _x_2.leg_sec_idx in
                                                                                                                                                  let (_x_4 : bool) = _x_3 = OUT1 in
                                                                                                                                                  let (_x_5 : month) = if _x_4 then Mar else … in
                                                                                                                                                  let (_x_6 : leg) = ( :var_2: ).leg2 in
                                                                                                                                                  let (_x_7 : outright_id) = _x_6.leg_sec_idx in
                                                                                                                                                  let (_x_8 : bool) = _x_7 = OUT1 in
                                                                                                                                                  let (_x_9 : month) = if _x_8 then Mar else … in
                                                                                                                                                  let (_x_10 : month) = if _x_8 then Mar else if _x_7 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_11 : int)
                                                                                                                                                      = if _x_10 = Mar then 3
                                                                                                                                                        else if _x_10 = Jun then 6 else if _x_10 = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_12 : month) = if _x_4 then Mar else if _x_3 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_13 : bool)
                                                                                                                                                      = _x_11
                                                                                                                                                        <= (if _x_12 = Mar then 3
                                                                                                                                                            else if _x_12 = Jun then 6 else if _x_12 = Sep then 9 else 12)
                                                                                                                                                  in
                                                                                                                                                  let (_x_14 : month) = if _x_13 then _x_10 else _x_12 in
                                                                                                                                                  let (_x_15 : bool)
                                                                                                                                                      = _x_13
                                                                                                                                                        || (_x_11
                                                                                                                                                            <= (if _x_14 = Mar then 3
                                                                                                                                                                else
                                                                                                                                                                if _x_14 = Jun then 6
                                                                                                                                                                else if (if _x_13 then _x_9 else _x_5) = Sep then 9 else 12))
                                                                                                                                                  in
                                                                                                                                                  let (_x_16 : month) = if _x_15 then _x_10 else _x_12 in
                                                                                                                                                  let (_x_17 : int)
                                                                                                                                                      = if _x_16 = Mar then 3
                                                                                                                                                        else
                                                                                                                                                        if _x_16 = Jun then 6
                                                                                                                                                        else if (if _x_15 then _x_9 else _x_5) = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_18 : leg) = ( :var_0: ).leg1 in
                                                                                                                                                  let (_x_19 : outright_id) = _x_18.leg_sec_idx in
                                                                                                                                                  let (_x_20 : bool) = _x_19 = OUT1 in
                                                                                                                                                  let (_x_21 : month) = if _x_20 then Mar else … in
                                                                                                                                                  let (_x_22 : leg) = ( :var_0: ).leg2 in
                                                                                                                                                  let (_x_23 : outright_id) = _x_22.leg_sec_idx in
                                                                                                                                                  let (_x_24 : bool) = _x_23 = OUT1 in
                                                                                                                                                  let (_x_25 : month) = if _x_24 then Mar else … in
                                                                                                                                                  let (_x_26 : month)
                                                                                                                                                      = if _x_24 then Mar else if _x_23 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_27 : bool) = _x_26 = Jun in
                                                                                                                                                  let (_x_28 : bool) = _x_26 = Mar in
                                                                                                                                                  let (_x_29 : int)
                                                                                                                                                      = if _x_28 then 3 else if _x_27 then 6 else if _x_25 = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_30 : month)
                                                                                                                                                      = if _x_20 then Mar else if _x_19 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_31 : bool) = _x_30 = Jun in
                                                                                                                                                  let (_x_32 : bool) = _x_30 = Mar in
                                                                                                                                                  let (_x_33 : bool)
                                                                                                                                                      = _x_29
                                                                                                                                                        <= (if _x_32 then 3
                                                                                                                                                            else if _x_31 then 6 else if _x_21 = Sep then 9 else 12)
                                                                                                                                                  in
                                                                                                                                                  let (_x_34 : bool)
                                                                                                                                                      = _x_33
                                                                                                                                                        || (_x_29
                                                                                                                                                            <= (if (if _x_33 then _x_26 else _x_30) = Mar then 3
                                                                                                                                                                else
                                                                                                                                                                if (if _x_33 then _x_25 else _x_21) = Jun then 6
                                                                                                                                                                else if (if _x_33 then … else …) = Sep then 9 else 12))
                                                                                                                                                  in
                                                                                                                                                  let (_x_35 : int)
                                                                                                                                                      = if _x_28 then 3 else if _x_27 then 6 else if _x_26 = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_36 : bool)
                                                                                                                                                      = _x_35
                                                                                                                                                        <= (if _x_32 then 3
                                                                                                                                                            else if _x_31 then 6 else if _x_30 = Sep then 9 else 12)
                                                                                                                                                  in
                                                                                                                                                  let (_x_37 : month) = if _x_36 then _x_26 else _x_30 in
                                                                                                                                                  let (_x_38 : int)
                                                                                                                                                      = if (if _x_36
                                                                                                                                                               || (_x_35
                                                                                                                                                                   <= (if _x_37 = Mar then 3
                                                                                                                                                                       else
                                                                                                                                                                       if _x_37 = Jun then 6
                                                                                                                                                                       else
                                                                                                                                                                       if (if _x_36 then _x_25 else _x_21) = Sep then 9 else 12))
                                                                                                                                                            then _x_26 else _x_30)
                                                                                                                                                           = Mar
                                                                                                                                                        then 3
                                                                                                                                                        else
                                                                                                                                                        if (if _x_34 then _x_26 else _x_30) = Jun then 6
                                                                                                                                                        else if (if _x_34 then _x_25 else _x_21) = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_39 : int) = _x_18.leg_mult in
                                                                                                                                                  let (_x_40 : int) = _x_22.leg_mult in
                                                                                                                                                  let (_x_41 : int) = ( :var_0: ).leg3.leg_mult in
                                                                                                                                                  let (_x_42 : int)
                                                                                                                                                      = (if 0 <= _x_39 then _x_39 else (-1) * _x_39)
                                                                                                                                                        + (if 0 <= _x_40 then _x_40 else (-1) * _x_40)
                                                                                                                                                        + (if 0 <= _x_41 then _x_41 else (-1) * _x_41)
                                                                                                                                                  in
                                                                                                                                                  let (_x_43 : int) = _x_2.leg_mult in
                                                                                                                                                  let (_x_44 : int) = _x_6.leg_mult in
                                                                                                                                                  let (_x_45 : int) = ( :var_2: ).leg3.leg_mult in
                                                                                                                                                  let (_x_46 : int)
                                                                                                                                                      = (if 0 <= _x_43 then _x_43 else (-1) * _x_43)
                                                                                                                                                        + (if 0 <= _x_44 then _x_44 else (-1) * _x_44)
                                                                                                                                                        + (if 0 <= _x_45 then _x_45 else (-1) * _x_45)
                                                                                                                                                  in
                                                                                                                                                  let (_x_47 : int) = ( :var_1: ).time_created in
                                                                                                                                                  let (_x_48 : leg) = ( :var_1: ).leg1 in
                                                                                                                                                  let (_x_49 : outright_id) = _x_48.leg_sec_idx in
                                                                                                                                                  let (_x_50 : bool) = _x_49 = OUT1 in
                                                                                                                                                  let (_x_51 : month) = if _x_50 then Mar else … in
                                                                                                                                                  let (_x_52 : leg) = ( :var_1: ).leg2 in
                                                                                                                                                  let (_x_53 : outright_id) = _x_52.leg_sec_idx in
                                                                                                                                                  let (_x_54 : bool) = _x_53 = OUT1 in
                                                                                                                                                  let (_x_55 : month) = if _x_54 then Mar else … in
                                                                                                                                                  let (_x_56 : month)
                                                                                                                                                      = if _x_54 then Mar else if _x_53 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_57 : int)
                                                                                                                                                      = if _x_56 = Mar then 3
                                                                                                                                                        else if _x_56 = Jun then 6 else if _x_56 = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_58 : month)
                                                                                                                                                      = if _x_50 then Mar else if _x_49 = OUT2 then Jun else Sep
                                                                                                                                                  in
                                                                                                                                                  let (_x_59 : bool)
                                                                                                                                                      = _x_57
                                                                                                                                                        <= (if _x_58 = Mar then 3
                                                                                                                                                            else if _x_58 = Jun then 6 else if _x_58 = Sep then 9 else 12)
                                                                                                                                                  in
                                                                                                                                                  let (_x_60 : month) = if _x_59 then _x_56 else _x_58 in
                                                                                                                                                  let (_x_61 : bool)
                                                                                                                                                      = _x_59
                                                                                                                                                        || (_x_57
                                                                                                                                                            <= (if _x_60 = Mar then 3
                                                                                                                                                                else
                                                                                                                                                                if _x_60 = Jun then 6
                                                                                                                                                                else if (if _x_59 then _x_55 else _x_51) = Sep then 9 else 12))
                                                                                                                                                  in
                                                                                                                                                  let (_x_62 : month) = if _x_61 then _x_56 else _x_58 in
                                                                                                                                                  let (_x_63 : int)
                                                                                                                                                      = if _x_62 = Mar then 3
                                                                                                                                                        else
                                                                                                                                                        if _x_62 = Jun then 6
                                                                                                                                                        else if (if _x_61 then _x_55 else _x_51) = Sep then 9 else 12
                                                                                                                                                  in
                                                                                                                                                  let (_x_64 : int) = _x_48.leg_mult in
                                                                                                                                                  let (_x_65 : int) = _x_52.leg_mult in
                                                                                                                                                  let (_x_66 : int) = ( :var_1: ).leg3.leg_mult in
                                                                                                                                                  let (_x_67 : int)
                                                                                                                                                      = (if 0 <= _x_64 then _x_64 else (-1) * _x_64)
                                                                                                                                                        + (if 0 <= _x_65 then _x_65 else (-1) * _x_65)
                                                                                                                                                        + (if 0 <= _x_66 then _x_66 else (-1) * _x_66)
                                                                                                                                                  in
                                                                                                                                                  (_x_0 <= _x_1) || not (_x_17 <= _x_38) || not (_x_42 <= _x_46)
                                                                                                                                                  || not
                                                                                                                                                     (((_x_0 <= _x_47) || not (_x_63 <= _x_38) || not (_x_42 <= _x_67))
                                                                                                                                                      && ((_x_47 <= _x_1) || not (_x_17 <= _x_63) || not (_x_67 <= _x_46)))
                                                                                                                                                  expansions:
                                                                                                                                                  []
                                                                                                                                                  rewrite_steps:
                                                                                                                                                    forward_chaining:
                                                                                                                                                    • Sat (Some let s1 : strategy = {time_created = (Z.of_nativeint (0n)); leg1 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (1602n))}; leg2 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (590n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (2324n))}} let s2 : strategy = {time_created = (Z.of_nativeint (3609n)); leg1 = {leg_sec_idx = OUT2; leg_mult = (Z.of_nativeint (3045n))}; leg2 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (49n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (1421n))}} let s3 : strategy = {time_created = (Z.of_nativeint (-1n)); leg1 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (2240n))}; leg2 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (1n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (2275n))}} )

                                                                                                                                                    Ooops! It seems that our ranking criteria is not transitive. Let's check the results (note that the counter examples are now reflected into the run time in the CX module)

                                                                                                                                                    In [13]:
                                                                                                                                                    priority_strat CX.s1 CX.s2
                                                                                                                                                    
                                                                                                                                                    Out[13]:
                                                                                                                                                    - : bool = true
                                                                                                                                                    
                                                                                                                                                    In [14]:
                                                                                                                                                    priority_strat CX.s2 CX.s3
                                                                                                                                                    
                                                                                                                                                    Out[14]:
                                                                                                                                                    - : bool = true
                                                                                                                                                    
                                                                                                                                                    In [15]:
                                                                                                                                                    priority_strat CX.s1 CX.s3
                                                                                                                                                    
                                                                                                                                                    Out[15]:
                                                                                                                                                    - : bool = false
                                                                                                                                                    

                                                                                                                                                    3.2 Implied strategy price calculation

                                                                                                                                                    In [16]:
                                                                                                                                                    (* return the sum of volume at the highest level *)
                                                                                                                                                    let rec get_level_sums (orders : order list) (li : level_info option) =
                                                                                                                                                      match orders with
                                                                                                                                                      | [] -> li
                                                                                                                                                      | x::xs ->
                                                                                                                                                        begin
                                                                                                                                                          match li with
                                                                                                                                                          | None -> get_level_sums xs (Some {li_qty = x.o_qty; li_price = x.o_price})
                                                                                                                                                          | Some l ->
                                                                                                                                                            if (l.li_price = x.o_price) then
                                                                                                                                                              get_level_sums xs (Some {l with li_qty = l.li_qty + x.o_qty})
                                                                                                                                                            else
                                                                                                                                                              li
                                                                                                                                                        end
                                                                                                                                                    
                                                                                                                                                    (* Return best bid/ask levels *)
                                                                                                                                                    let get_book_tops (b : book) =
                                                                                                                                                      let bid_info = get_level_sums b.b_buys None in
                                                                                                                                                      let ask_info = get_level_sums b.b_sells None in
                                                                                                                                                      { bid_info; ask_info }
                                                                                                                                                    ;;
                                                                                                                                                    
                                                                                                                                                    (* Get the maximum number of strategy units here *)
                                                                                                                                                    (* Note that the units may have different signs, so we
                                                                                                                                                     need to make sure that we have enough *)
                                                                                                                                                    let calc_implied_strat_order (sid : strategy_id) (s : strategy) (books : books_info) (si : side) (time : int) =
                                                                                                                                                      let abs x = if x < 0 then -x else x in
                                                                                                                                                    
                                                                                                                                                      let adjust (mult : int) =
                                                                                                                                                        if si = BUY then mult else -mult in
                                                                                                                                                    
                                                                                                                                                      (* *)
                                                                                                                                                      let calc_max_out_mult (mult : int) (book : best_bid_ask)  =
                                                                                                                                                        if mult = 0 then
                                                                                                                                                          None
                                                                                                                                                        else
                                                                                                                                                          begin
                                                                                                                                                           if (adjust mult) > 0 then
                                                                                                                                                            match books.book1.bid_info with
                                                                                                                                                               | Some x -> Some (x.li_qty / (abs mult))
                                                                                                                                                               | None -> None
                                                                                                                                                           else
                                                                                                                                                               match book.ask_info with
                                                                                                                                                               | Some x -> Some (x.li_qty / (abs mult))
                                                                                                                                                               | None -> None
                                                                                                                                                          end in
                                                                                                                                                    
                                                                                                                                                      let mult1 = calc_max_out_mult s.leg1.leg_mult books.book1 in
                                                                                                                                                      let mult2 = calc_max_out_mult s.leg2.leg_mult books.book2 in
                                                                                                                                                      let mult3 = calc_max_out_mult s.leg3.leg_mult books.book3 in
                                                                                                                                                    
                                                                                                                                                      (* Compute the quantity *)
                                                                                                                                                      let max_strat =
                                                                                                                                                        begin
                                                                                                                                                           match mult1 with
                                                                                                                                                           | None -> 0
                                                                                                                                                           | Some x -> x
                                                                                                                                                        end in
                                                                                                                                                      let max_strat =
                                                                                                                                                        begin
                                                                                                                                                           match mult2 with
                                                                                                                                                           | None -> max_strat
                                                                                                                                                           | Some x -> if x < max_strat then x else max_strat
                                                                                                                                                        end in
                                                                                                                                                      let max_strat =
                                                                                                                                                        begin
                                                                                                                                                         match mult3 with
                                                                                                                                                         | None -> max_strat
                                                                                                                                                         | Some x -> if x < max_strat then x else max_strat
                                                                                                                                                        end in
                                                                                                                                                    
                                                                                                                                                      (* Now compute the price *)
                                                                                                                                                      let strat_price =
                                                                                                                                                        begin
                                                                                                                                                           match mult1 with
                                                                                                                                                           | None -> 0
                                                                                                                                                           | Some x ->
                                                                                                                                                             begin
                                                                                                                                                                if (adjust s.leg1.leg_mult) > 0 then
                                                                                                                                                                    match books.book1.bid_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg1.leg_mult)
                                                                                                                                                                    | None -> 0
                                                                                                                                                                else
                                                                                                                                                                    match books.book1.ask_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg1.leg_mult)
                                                                                                                                                                    | None -> 0
                                                                                                                                                             end
                                                                                                                                                        end in
                                                                                                                                                      let strat_price =
                                                                                                                                                        begin
                                                                                                                                                           match mult2 with
                                                                                                                                                           | None -> strat_price
                                                                                                                                                           | Some x ->
                                                                                                                                                             begin
                                                                                                                                                                if (adjust s.leg2.leg_mult) > 0 then
                                                                                                                                                                    match books.book2.bid_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg2.leg_mult) + strat_price
                                                                                                                                                                    | None -> strat_price
                                                                                                                                                                else
                                                                                                                                                                    match books.book2.ask_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg2.leg_mult) + strat_price
                                                                                                                                                                    | None -> strat_price
                                                                                                                                                             end
                                                                                                                                                        end in
                                                                                                                                                      let strat_price =
                                                                                                                                                        begin
                                                                                                                                                           match mult3 with
                                                                                                                                                           | None -> strat_price
                                                                                                                                                           | Some x ->
                                                                                                                                                             begin
                                                                                                                                                                if (adjust s.leg3.leg_mult) > 0 then
                                                                                                                                                                    match books.book3.bid_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg3.leg_mult) + strat_price
                                                                                                                                                                    | None -> strat_price
                                                                                                                                                                else
                                                                                                                                                                    match books.book3.ask_info with
                                                                                                                                                                    | Some x -> x.li_price * (adjust s.leg3.leg_mult) + strat_price
                                                                                                                                                                    | None -> strat_price
                                                                                                                                                             end
                                                                                                                                                        end in
                                                                                                                                                    
                                                                                                                                                      (* Now form the new implied order here... *)
                                                                                                                                                      {
                                                                                                                                                       o_qty = max_strat
                                                                                                                                                       ; o_price = strat_price
                                                                                                                                                       ; o_id = -1
                                                                                                                                                       ; o_time = time
                                                                                                                                                       ; o_side = si
                                                                                                                                                       ; o_client_id = -1
                                                                                                                                                       ; o_inst = Strategy sid
                                                                                                                                                       ; o_is_implied = true }
                                                                                                                                                    ;;
                                                                                                                                                    
                                                                                                                                                    Out[16]:
                                                                                                                                                    val get_level_sums : order list -> level_info option -> level_info option =
                                                                                                                                                      <fun>
                                                                                                                                                    val get_book_tops : book -> best_bid_ask = <fun>
                                                                                                                                                    val calc_implied_strat_order :
                                                                                                                                                      strategy_id -> strategy -> books_info -> side -> Z.t -> order = <fun>
                                                                                                                                                    
                                                                                                                                                    termination proof

                                                                                                                                                    Termination proof

                                                                                                                                                    call `let (_x_0 : order) = List.hd orders in get_level_sums (List.tl orders) (Some {li_qty = _x_0.o_qty; li_price = _x_0.o_price})` from `get_level_sums orders li`
                                                                                                                                                    original:get_level_sums orders li
                                                                                                                                                    sub:let (_x_0 : order) = List.hd orders in get_level_sums (List.tl orders) (Some {li_qty = _x_0.o_qty; li_price = _x_0.o_price})
                                                                                                                                                    original ordinal:Ordinal.Int (_cnt orders)
                                                                                                                                                    sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                                                                                                                                                    path:[Is_a(None, li) && orders <> []]
                                                                                                                                                    proof:
                                                                                                                                                    detailed proof
                                                                                                                                                    ground_instances:3
                                                                                                                                                    definitions:0
                                                                                                                                                    inductions:0
                                                                                                                                                    search_time:
                                                                                                                                                    0.012s
                                                                                                                                                    details:
                                                                                                                                                    Expand
                                                                                                                                                    smt_stats:
                                                                                                                                                    arith offset eqs:7
                                                                                                                                                    num checks:8
                                                                                                                                                    arith assert lower:80
                                                                                                                                                    arith tableau max rows:16
                                                                                                                                                    arith tableau max columns:44
                                                                                                                                                    arith pivots:34
                                                                                                                                                    rlimit count:14306
                                                                                                                                                    mk clause:109
                                                                                                                                                    datatype occurs check:28
                                                                                                                                                    mk bool var:411
                                                                                                                                                    arith assert upper:94
                                                                                                                                                    datatype splits:63
                                                                                                                                                    decisions:139
                                                                                                                                                    arith row summations:61
                                                                                                                                                    arith bound prop:6
                                                                                                                                                    propagations:146
                                                                                                                                                    conflicts:26
                                                                                                                                                    arith fixed eqs:30
                                                                                                                                                    datatype accessor ax:47
                                                                                                                                                    minimized lits:15
                                                                                                                                                    arith conflicts:12
                                                                                                                                                    arith num rows:16
                                                                                                                                                    arith assert diseq:6
                                                                                                                                                    datatype constructor ax:85
                                                                                                                                                    num allocs:1457317901
                                                                                                                                                    final checks:6
                                                                                                                                                    added eqs:456
                                                                                                                                                    del clause:75
                                                                                                                                                    arith eq adapter:79
                                                                                                                                                    memory:26.970000
                                                                                                                                                    max memory:27.130000
                                                                                                                                                    Expand
                                                                                                                                                    • start[0.012s]
                                                                                                                                                        let (_x_0 : int) = count.list count.order orders in
                                                                                                                                                        let (_x_1 : order list) = List.tl orders in
                                                                                                                                                        let (_x_2 : int) = count.list count.order _x_1 in
                                                                                                                                                        Is_a(None, li) && (orders <> [] && ((_x_0 >= 0) && (_x_2 >= 0)))
                                                                                                                                                        ==> not (((List.hd orders).o_price = (List.hd _x_1).o_price) && _x_1 <> [])
                                                                                                                                                            || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                                                                                    • simplify
                                                                                                                                                      into:
                                                                                                                                                      let (_x_0 : order list) = List.tl orders in
                                                                                                                                                      let (_x_1 : int) = count.list count.order _x_0 in
                                                                                                                                                      let (_x_2 : int) = count.list count.order orders in
                                                                                                                                                      Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                                                                                      || not (((List.hd orders).o_price = (List.hd _x_0).o_price) && _x_0 <> [])
                                                                                                                                                      || not (Is_a(None, li) && orders <> [] && (_x_2 >= 0) && (_x_1 >= 0))
                                                                                                                                                      expansions:
                                                                                                                                                      []
                                                                                                                                                      rewrite_steps:
                                                                                                                                                        forward_chaining:
                                                                                                                                                        • unroll
                                                                                                                                                          expr:
                                                                                                                                                          (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                                          (|count.list_2146/server|
                                                                                                                                                                            (|g…
                                                                                                                                                          expansions:
                                                                                                                                                          • unroll
                                                                                                                                                            expr:
                                                                                                                                                            (|count.list_2146/server| (|get.::.1_2127/server| orders_2131/server))
                                                                                                                                                            expansions:
                                                                                                                                                            • unroll
                                                                                                                                                              expr:
                                                                                                                                                              (|count.list_2146/server| orders_2131/server)
                                                                                                                                                              expansions:
                                                                                                                                                              • Unsat
                                                                                                                                                              call `let (_x_0 : level_info) = Option.get li in get_level_sums (List.tl orders) (Some {_x_0 with li_qty = _x_0.li_qty + (List.hd orders).o_qty})` from `get_level_sums orders li`
                                                                                                                                                              original:get_level_sums orders li
                                                                                                                                                              sub:let (_x_0 : level_info) = Option.get li in get_level_sums (List.tl orders) (Some {_x_0 with li_qty = _x_0.li_qty + (List.hd orders).o_qty})
                                                                                                                                                              original ordinal:Ordinal.Int (_cnt orders)
                                                                                                                                                              sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                                                                                                                                                              path:[(Option.get li).li_price = (List.hd orders).o_price && not Is_a(None, li) && orders <> []]
                                                                                                                                                              proof:
                                                                                                                                                              detailed proof
                                                                                                                                                              ground_instances:3
                                                                                                                                                              definitions:0
                                                                                                                                                              inductions:0
                                                                                                                                                              search_time:
                                                                                                                                                              0.015s
                                                                                                                                                              details:
                                                                                                                                                              Expand
                                                                                                                                                              smt_stats:
                                                                                                                                                              arith offset eqs:7
                                                                                                                                                              num checks:8
                                                                                                                                                              arith assert lower:80
                                                                                                                                                              arith tableau max rows:15
                                                                                                                                                              arith tableau max columns:43
                                                                                                                                                              arith pivots:33
                                                                                                                                                              rlimit count:7275
                                                                                                                                                              mk clause:107
                                                                                                                                                              datatype occurs check:28
                                                                                                                                                              mk bool var:408
                                                                                                                                                              arith assert upper:95
                                                                                                                                                              datatype splits:63
                                                                                                                                                              decisions:136
                                                                                                                                                              arith row summations:61
                                                                                                                                                              arith bound prop:5
                                                                                                                                                              propagations:144
                                                                                                                                                              conflicts:25
                                                                                                                                                              arith fixed eqs:29
                                                                                                                                                              datatype accessor ax:47
                                                                                                                                                              minimized lits:15
                                                                                                                                                              arith conflicts:12
                                                                                                                                                              arith num rows:15
                                                                                                                                                              arith assert diseq:5
                                                                                                                                                              datatype constructor ax:82
                                                                                                                                                              num allocs:1383647440
                                                                                                                                                              final checks:6
                                                                                                                                                              added eqs:454
                                                                                                                                                              del clause:74
                                                                                                                                                              arith eq adapter:77
                                                                                                                                                              memory:27.020000
                                                                                                                                                              max memory:27.130000
                                                                                                                                                              Expand
                                                                                                                                                              • start[0.015s]
                                                                                                                                                                  let (_x_0 : int) = (Option.get li).li_price in
                                                                                                                                                                  let (_x_1 : int) = count.list count.order orders in
                                                                                                                                                                  let (_x_2 : order list) = List.tl orders in
                                                                                                                                                                  let (_x_3 : int) = count.list count.order _x_2 in
                                                                                                                                                                  (_x_0 = (List.hd orders).o_price)
                                                                                                                                                                  && (not Is_a(None, li) && (orders <> [] && ((_x_1 >= 0) && (_x_3 >= 0))))
                                                                                                                                                                  ==> not ((_x_0 = (List.hd _x_2).o_price) && _x_2 <> [])
                                                                                                                                                                      || Ordinal.( << ) (Ordinal.Int _x_3) (Ordinal.Int _x_1)
                                                                                                                                                              • simplify
                                                                                                                                                                into:
                                                                                                                                                                let (_x_0 : int) = (Option.get li).li_price in
                                                                                                                                                                let (_x_1 : order list) = List.tl orders in
                                                                                                                                                                let (_x_2 : int) = count.list count.order _x_1 in
                                                                                                                                                                let (_x_3 : int) = count.list count.order orders in
                                                                                                                                                                not ((_x_0 = (List.hd _x_1).o_price) && _x_1 <> [])
                                                                                                                                                                || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_3)
                                                                                                                                                                || not
                                                                                                                                                                   ((_x_0 = (List.hd orders).o_price) && not Is_a(None, li) && orders <> []
                                                                                                                                                                    && (_x_3 >= 0) && (_x_2 >= 0))
                                                                                                                                                                expansions:
                                                                                                                                                                []
                                                                                                                                                                rewrite_steps:
                                                                                                                                                                  forward_chaining:
                                                                                                                                                                  • unroll
                                                                                                                                                                    expr:
                                                                                                                                                                    (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                                                    (|count.list_2146/server|
                                                                                                                                                                                      (|g…
                                                                                                                                                                    expansions:
                                                                                                                                                                    • unroll
                                                                                                                                                                      expr:
                                                                                                                                                                      (|count.list_2146/server| (|get.::.1_2127/server| orders_2131/server))
                                                                                                                                                                      expansions:
                                                                                                                                                                      • unroll
                                                                                                                                                                        expr:
                                                                                                                                                                        (|count.list_2146/server| orders_2131/server)
                                                                                                                                                                        expansions:
                                                                                                                                                                        • Unsat

                                                                                                                                                                        Let's now try to experiment with this.

                                                                                                                                                                        In [17]:
                                                                                                                                                                        let strat1 = {
                                                                                                                                                                          time_created = 1;
                                                                                                                                                                          leg1    = { leg_sec_idx = OUT1; leg_mult = 1 }
                                                                                                                                                                          ; leg2  = { leg_sec_idx = OUT2; leg_mult = 0 }
                                                                                                                                                                          ; leg3  = { leg_sec_idx = OUT3; leg_mult = 0 }
                                                                                                                                                                        };;
                                                                                                                                                                        
                                                                                                                                                                        let books = {
                                                                                                                                                                            book1 = { bid_info = None ; ask_info = Some { li_qty = 100 ; li_price = 450 }}
                                                                                                                                                                          ; book2 = { bid_info = Some { li_qty = 125 ; li_price = 100 }; ask_info = Some { li_qty = 100 ; li_price = 350 }}
                                                                                                                                                                          ; book3 = { bid_info = None ; ask_info = Some { li_qty = 100 ; li_price = 425 }}
                                                                                                                                                                        };;
                                                                                                                                                                        
                                                                                                                                                                        (* This should just replicate the OUT1 security on the SELL side *)
                                                                                                                                                                        calc_implied_strat_order STRAT1 strat1 books SELL 1
                                                                                                                                                                        
                                                                                                                                                                        Out[17]:
                                                                                                                                                                        val strat1 : strategy =
                                                                                                                                                                          {time_created = 1; leg1 = {leg_sec_idx = OUT1; leg_mult = 1};
                                                                                                                                                                           leg2 = {leg_sec_idx = OUT2; leg_mult = 0};
                                                                                                                                                                           leg3 = {leg_sec_idx = OUT3; leg_mult = 0}}
                                                                                                                                                                        val books : books_info =
                                                                                                                                                                          {book1 = {bid_info = None; ask_info = Some {li_qty = 100; li_price = 450}};
                                                                                                                                                                           book2 =
                                                                                                                                                                            {bid_info = Some {li_qty = 125; li_price = 100};
                                                                                                                                                                             ask_info = Some {li_qty = 100; li_price = 350}};
                                                                                                                                                                           book3 = {bid_info = None; ask_info = Some {li_qty = 100; li_price = 425}}}
                                                                                                                                                                        - : order = <document>
                                                                                                                                                                        
                                                                                                                                                                        -450 (100)
                                                                                                                                                                        Implied
                                                                                                                                                                        In [18]:
                                                                                                                                                                        (* Now let's try the same on the BUY side - there should not be any available orders as the bid is empty *)
                                                                                                                                                                        calc_implied_strat_order STRAT1 strat1 books BUY 1
                                                                                                                                                                        
                                                                                                                                                                        Out[18]:
                                                                                                                                                                        - : order = <document>
                                                                                                                                                                        
                                                                                                                                                                        0 (0)
                                                                                                                                                                        Implied
                                                                                                                                                                        In [19]:
                                                                                                                                                                        (* let's try to mix up the legs now *)
                                                                                                                                                                        
                                                                                                                                                                        let strat2 = {
                                                                                                                                                                         strat1 with
                                                                                                                                                                         leg2 = {leg_sec_idx = OUT2; leg_mult = -1}
                                                                                                                                                                        };;
                                                                                                                                                                        
                                                                                                                                                                        (* This will not result in any orders because there's no BUY *)
                                                                                                                                                                        calc_implied_strat_order STRAT1 strat2 books BUY 1
                                                                                                                                                                        
                                                                                                                                                                        Out[19]:
                                                                                                                                                                        val strat2 : strategy =
                                                                                                                                                                          {time_created = 1; leg1 = {leg_sec_idx = OUT1; leg_mult = 1};
                                                                                                                                                                           leg2 = {leg_sec_idx = OUT2; leg_mult = -1};
                                                                                                                                                                           leg3 = {leg_sec_idx = OUT3; leg_mult = 0}}
                                                                                                                                                                        - : order = <document>
                                                                                                                                                                        
                                                                                                                                                                        -350 (0)
                                                                                                                                                                        Implied
                                                                                                                                                                        In [20]:
                                                                                                                                                                        calc_implied_strat_order STRAT2 strat2 books SELL 1
                                                                                                                                                                        
                                                                                                                                                                        Out[20]:
                                                                                                                                                                        - : order = <document>
                                                                                                                                                                        
                                                                                                                                                                        -450 (100)
                                                                                                                                                                        Implied
                                                                                                                                                                        In [21]:
                                                                                                                                                                        let strat = {
                                                                                                                                                                          time_created = 1;
                                                                                                                                                                          leg1    = { leg_sec_idx = OUT1; leg_mult = 1 }
                                                                                                                                                                          ; leg2  = { leg_sec_idx = OUT2; leg_mult = -2 }
                                                                                                                                                                          ; leg3  = { leg_sec_idx = OUT3; leg_mult = 0 }
                                                                                                                                                                        };;
                                                                                                                                                                        
                                                                                                                                                                        let books = {
                                                                                                                                                                            book1 = { bid_info = Some { li_qty = 500; li_price = 50 } ; ask_info = Some { li_qty = 750 ; li_price = 50 }}
                                                                                                                                                                          ; book2 = { bid_info = Some { li_qty = 200 ; li_price = 60 }; ask_info = Some { li_qty = 500 ; li_price = 70 }}
                                                                                                                                                                          ; book3 = { bid_info = None ; ask_info = None }
                                                                                                                                                                        };;
                                                                                                                                                                        
                                                                                                                                                                        calc_implied_strat_order STRAT1 strat books BUY 1
                                                                                                                                                                        
                                                                                                                                                                        Out[21]:
                                                                                                                                                                        val strat : strategy =
                                                                                                                                                                          {time_created = 1; leg1 = {leg_sec_idx = OUT1; leg_mult = 1};
                                                                                                                                                                           leg2 = {leg_sec_idx = OUT2; leg_mult = -2};
                                                                                                                                                                           leg3 = {leg_sec_idx = OUT3; leg_mult = 0}}
                                                                                                                                                                        val books : books_info =
                                                                                                                                                                          {book1 =
                                                                                                                                                                            {bid_info = Some {li_qty = 500; li_price = 50};
                                                                                                                                                                             ask_info = Some {li_qty = 750; li_price = 50}};
                                                                                                                                                                           book2 =
                                                                                                                                                                            {bid_info = Some {li_qty = 200; li_price = 60};
                                                                                                                                                                             ask_info = Some {li_qty = 500; li_price = 70}};
                                                                                                                                                                           book3 = {bid_info = None; ask_info = None}}
                                                                                                                                                                        - : order = <document>
                                                                                                                                                                        
                                                                                                                                                                        -90 (250)
                                                                                                                                                                        Implied

                                                                                                                                                                        3.3 Implied uncrossing operations

                                                                                                                                                                        In [22]:
                                                                                                                                                                        (* removes implied orders from a book *)
                                                                                                                                                                        let remove_imp_orders (b : book) =
                                                                                                                                                                          let rec remove_imp_orders_side (orders : order list) =
                                                                                                                                                                            match orders with
                                                                                                                                                                            | [] -> []
                                                                                                                                                                            | x::xs ->
                                                                                                                                                                                if x.o_is_implied then
                                                                                                                                                                                  (remove_imp_orders_side xs)
                                                                                                                                                                                else
                                                                                                                                                                                  x::(remove_imp_orders_side xs) in
                                                                                                                                                                        
                                                                                                                                                                          { b_buys = (remove_imp_orders_side b.b_buys)
                                                                                                                                                                          ; b_sells = (remove_imp_orders_side b.b_sells)
                                                                                                                                                                          }
                                                                                                                                                                        
                                                                                                                                                                        (* Allocate implied fills to the book and return fills *)
                                                                                                                                                                        let allocate_implied_fills (b : book) (qty : int) (price : int) (time : int) =
                                                                                                                                                                          if qty = 0 then {
                                                                                                                                                                            uncrossed_book = b
                                                                                                                                                                            ; uncrossed_fills = []
                                                                                                                                                                            ; uncrossed_qty = 0
                                                                                                                                                                          } else
                                                                                                                                                                          begin
                                                                                                                                                                            (* Insert new order into the book and uncross it *)
                                                                                                                                                                            let new_order = {
                                                                                                                                                                              o_qty = if qty < 0 then (-qty) else qty
                                                                                                                                                                              ; o_price = price
                                                                                                                                                                              ; o_id = -1
                                                                                                                                                                              ; o_time = time
                                                                                                                                                                              ; o_side = if qty < 0 then SELL else BUY
                                                                                                                                                                              ; o_client_id = -1
                                                                                                                                                                              ; o_inst = Outright OUT1
                                                                                                                                                                              ; o_is_implied = true
                                                                                                                                                                            } in
                                                                                                                                                                        
                                                                                                                                                                            (* create new order that we will trade *)
                                                                                                                                                                            let b' = insert_order new_order b in
                                                                                                                                                                        
                                                                                                                                                                            (* finally we will uncross the book and return results *)
                                                                                                                                                                            (uncross_book b' [] 0)
                                                                                                                                                                          end
                                                                                                                                                                        
                                                                                                                                                                        (* Calculate the price at which implied orders should trade in the outright books *)
                                                                                                                                                                        let calc_implied_trade_price (mult : int) (bidask : best_bid_ask) =
                                                                                                                                                                          if mult > 0 then
                                                                                                                                                                           begin
                                                                                                                                                                            match bidask.ask_info with
                                                                                                                                                                              | None -> 0
                                                                                                                                                                              | Some x -> x.li_price
                                                                                                                                                                            end
                                                                                                                                                                          else
                                                                                                                                                                            begin
                                                                                                                                                                                match bidask.bid_info with
                                                                                                                                                                                  | None -> 0
                                                                                                                                                                                  | Some x -> x.li_price
                                                                                                                                                                            end
                                                                                                                                                                        ;;
                                                                                                                                                                        
                                                                                                                                                                        Out[22]:
                                                                                                                                                                        val remove_imp_orders : book -> book = <fun>
                                                                                                                                                                        val allocate_implied_fills : book -> Z.t -> Z.t -> Z.t -> uncross_res = <fun>
                                                                                                                                                                        val calc_implied_trade_price : Z.t -> best_bid_ask -> Z.t = <fun>
                                                                                                                                                                        
                                                                                                                                                                        termination proof

                                                                                                                                                                        Termination proof

                                                                                                                                                                        call `rec_fun.remove_imp_orders.remove_imp_orders_side.0 (List.tl orders)` from `rec_fun.remove_imp_orders.remove_imp_orders_side.0 orders`
                                                                                                                                                                        original:rec_fun.remove_imp_orders.remove_imp_orders_side.0 orders
                                                                                                                                                                        sub:rec_fun.remove_imp_orders.remove_imp_orders_side.0 (List.tl orders)
                                                                                                                                                                        original ordinal:Ordinal.Int (_cnt orders)
                                                                                                                                                                        sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                                                                                                                                                                        path:[(List.hd orders).o_is_implied && orders <> []]
                                                                                                                                                                        proof:
                                                                                                                                                                        detailed proof
                                                                                                                                                                        ground_instances:3
                                                                                                                                                                        definitions:0
                                                                                                                                                                        inductions:0
                                                                                                                                                                        search_time:
                                                                                                                                                                        0.013s
                                                                                                                                                                        details:
                                                                                                                                                                        Expand
                                                                                                                                                                        smt_stats:
                                                                                                                                                                        num checks:8
                                                                                                                                                                        arith assert lower:37
                                                                                                                                                                        arith tableau max rows:14
                                                                                                                                                                        arith tableau max columns:44
                                                                                                                                                                        arith pivots:27
                                                                                                                                                                        rlimit count:13430
                                                                                                                                                                        mk clause:74
                                                                                                                                                                        datatype occurs check:22
                                                                                                                                                                        mk bool var:265
                                                                                                                                                                        arith assert upper:24
                                                                                                                                                                        datatype splits:39
                                                                                                                                                                        decisions:69
                                                                                                                                                                        arith row summations:68
                                                                                                                                                                        propagations:101
                                                                                                                                                                        conflicts:12
                                                                                                                                                                        arith fixed eqs:18
                                                                                                                                                                        datatype accessor ax:34
                                                                                                                                                                        minimized lits:1
                                                                                                                                                                        arith conflicts:2
                                                                                                                                                                        arith num rows:14
                                                                                                                                                                        arith assert diseq:1
                                                                                                                                                                        datatype constructor ax:65
                                                                                                                                                                        num allocs:1631800409
                                                                                                                                                                        final checks:6
                                                                                                                                                                        added eqs:299
                                                                                                                                                                        del clause:29
                                                                                                                                                                        arith eq adapter:23
                                                                                                                                                                        memory:28.500000
                                                                                                                                                                        max memory:28.500000
                                                                                                                                                                        Expand
                                                                                                                                                                        • start[0.013s]
                                                                                                                                                                            let (_x_0 : int) = count.list count.order orders in
                                                                                                                                                                            let (_x_1 : order list) = List.tl orders in
                                                                                                                                                                            let (_x_2 : int) = count.list count.order _x_1 in
                                                                                                                                                                            let (_x_3 : bool) = (List.hd _x_1).o_is_implied in
                                                                                                                                                                            let (_x_4 : bool) = _x_1 <> [] in
                                                                                                                                                                            (List.hd orders).o_is_implied
                                                                                                                                                                            && (orders <> [] && ((_x_0 >= 0) && (_x_2 >= 0)))
                                                                                                                                                                            ==> (not (_x_3 && _x_4) && not (not _x_3 && _x_4))
                                                                                                                                                                                || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                                                                                                        • simplify
                                                                                                                                                                          into:
                                                                                                                                                                          let (_x_0 : order list) = List.tl orders in
                                                                                                                                                                          let (_x_1 : bool) = (List.hd _x_0).o_is_implied in
                                                                                                                                                                          let (_x_2 : bool) = _x_0 <> [] in
                                                                                                                                                                          let (_x_3 : int) = count.list count.order _x_0 in
                                                                                                                                                                          let (_x_4 : int) = count.list count.order orders in
                                                                                                                                                                          (not (_x_1 && _x_2) && not (not _x_1 && _x_2))
                                                                                                                                                                          || Ordinal.( << ) (Ordinal.Int _x_3) (Ordinal.Int _x_4)
                                                                                                                                                                          || not
                                                                                                                                                                             ((List.hd orders).o_is_implied && orders <> [] && (_x_4 >= 0)
                                                                                                                                                                              && (_x_3 >= 0))
                                                                                                                                                                          expansions:
                                                                                                                                                                          []
                                                                                                                                                                          rewrite_steps:
                                                                                                                                                                            forward_chaining:
                                                                                                                                                                            • unroll
                                                                                                                                                                              expr:
                                                                                                                                                                              (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                                                              (|count.list_2284/server|
                                                                                                                                                                                                (|g…
                                                                                                                                                                              expansions:
                                                                                                                                                                              • unroll
                                                                                                                                                                                expr:
                                                                                                                                                                                (|count.list_2284/server| (|get.::.1_2269/server| orders_2271/server))
                                                                                                                                                                                expansions:
                                                                                                                                                                                • unroll
                                                                                                                                                                                  expr:
                                                                                                                                                                                  (|count.list_2284/server| orders_2271/server)
                                                                                                                                                                                  expansions:
                                                                                                                                                                                  • Unsat
                                                                                                                                                                                  call `rec_fun.remove_imp_orders.remove_imp_orders_side.0 (List.tl orders)` from `rec_fun.remove_imp_orders.remove_imp_orders_side.0 orders`
                                                                                                                                                                                  original:rec_fun.remove_imp_orders.remove_imp_orders_side.0 orders
                                                                                                                                                                                  sub:rec_fun.remove_imp_orders.remove_imp_orders_side.0 (List.tl orders)
                                                                                                                                                                                  original ordinal:Ordinal.Int (_cnt orders)
                                                                                                                                                                                  sub ordinal:Ordinal.Int (_cnt (List.tl orders))
                                                                                                                                                                                  path:[not (List.hd orders).o_is_implied && orders <> []]
                                                                                                                                                                                  proof:
                                                                                                                                                                                  detailed proof
                                                                                                                                                                                  ground_instances:3
                                                                                                                                                                                  definitions:0
                                                                                                                                                                                  inductions:0
                                                                                                                                                                                  search_time:
                                                                                                                                                                                  0.018s
                                                                                                                                                                                  details:
                                                                                                                                                                                  Expand
                                                                                                                                                                                  smt_stats:
                                                                                                                                                                                  num checks:8
                                                                                                                                                                                  arith assert lower:37
                                                                                                                                                                                  arith tableau max rows:14
                                                                                                                                                                                  arith tableau max columns:44
                                                                                                                                                                                  arith pivots:27
                                                                                                                                                                                  rlimit count:6703
                                                                                                                                                                                  mk clause:74
                                                                                                                                                                                  datatype occurs check:22
                                                                                                                                                                                  mk bool var:265
                                                                                                                                                                                  arith assert upper:24
                                                                                                                                                                                  datatype splits:39
                                                                                                                                                                                  decisions:69
                                                                                                                                                                                  arith row summations:68
                                                                                                                                                                                  propagations:101
                                                                                                                                                                                  conflicts:12
                                                                                                                                                                                  arith fixed eqs:18
                                                                                                                                                                                  datatype accessor ax:34
                                                                                                                                                                                  minimized lits:1
                                                                                                                                                                                  arith conflicts:2
                                                                                                                                                                                  arith num rows:14
                                                                                                                                                                                  arith assert diseq:1
                                                                                                                                                                                  datatype constructor ax:65
                                                                                                                                                                                  num allocs:1555188104
                                                                                                                                                                                  final checks:6
                                                                                                                                                                                  added eqs:299
                                                                                                                                                                                  del clause:29
                                                                                                                                                                                  arith eq adapter:23
                                                                                                                                                                                  memory:28.490000
                                                                                                                                                                                  max memory:28.490000
                                                                                                                                                                                  Expand
                                                                                                                                                                                  • start[0.018s]
                                                                                                                                                                                      let (_x_0 : int) = count.list count.order orders in
                                                                                                                                                                                      let (_x_1 : order list) = List.tl orders in
                                                                                                                                                                                      let (_x_2 : int) = count.list count.order _x_1 in
                                                                                                                                                                                      let (_x_3 : bool) = (List.hd _x_1).o_is_implied in
                                                                                                                                                                                      let (_x_4 : bool) = _x_1 <> [] in
                                                                                                                                                                                      not (List.hd orders).o_is_implied
                                                                                                                                                                                      && (orders <> [] && ((_x_0 >= 0) && (_x_2 >= 0)))
                                                                                                                                                                                      ==> (not (_x_3 && _x_4) && not (not _x_3 && _x_4))
                                                                                                                                                                                          || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                                                                                                                                                                  • simplify
                                                                                                                                                                                    into:
                                                                                                                                                                                    let (_x_0 : order list) = List.tl orders in
                                                                                                                                                                                    let (_x_1 : bool) = (List.hd _x_0).o_is_implied in
                                                                                                                                                                                    let (_x_2 : bool) = _x_0 <> [] in
                                                                                                                                                                                    let (_x_3 : int) = count.list count.order _x_0 in
                                                                                                                                                                                    let (_x_4 : int) = count.list count.order orders in
                                                                                                                                                                                    (not (_x_1 && _x_2) && not (not _x_1 && _x_2))
                                                                                                                                                                                    || Ordinal.( << ) (Ordinal.Int _x_3) (Ordinal.Int _x_4)
                                                                                                                                                                                    || not
                                                                                                                                                                                       (not (List.hd orders).o_is_implied && orders <> [] && (_x_4 >= 0)
                                                                                                                                                                                        && (_x_3 >= 0))
                                                                                                                                                                                    expansions:
                                                                                                                                                                                    []
                                                                                                                                                                                    rewrite_steps:
                                                                                                                                                                                      forward_chaining:
                                                                                                                                                                                      • unroll
                                                                                                                                                                                        expr:
                                                                                                                                                                                        (|Ordinal.<<| (|Ordinal.Int_79/boot|
                                                                                                                                                                                                        (|count.list_2284/server|
                                                                                                                                                                                                          (|g…
                                                                                                                                                                                        expansions:
                                                                                                                                                                                        • unroll
                                                                                                                                                                                          expr:
                                                                                                                                                                                          (|count.list_2284/server| (|get.::.1_2269/server| orders_2271/server))
                                                                                                                                                                                          expansions:
                                                                                                                                                                                          • unroll
                                                                                                                                                                                            expr:
                                                                                                                                                                                            (|count.list_2284/server| orders_2271/server)
                                                                                                                                                                                            expansions:
                                                                                                                                                                                            • Unsat

                                                                                                                                                                                            3.4 Implied uncrossing (for single side)

                                                                                                                                                                                            In [23]:
                                                                                                                                                                                            (* The actual cycle *)
                                                                                                                                                                                            let implied_uncross_side (sd : side) (s_id : strategy_id) (s : strategy) (m : market) =
                                                                                                                                                                                            
                                                                                                                                                                                              (* 0. get the top of the book s*)
                                                                                                                                                                                              let book1 = get_book_tops m.out_book1 in
                                                                                                                                                                                              let book2 = get_book_tops m.out_book2 in
                                                                                                                                                                                              let book3 = get_book_tops m.out_book3 in
                                                                                                                                                                                            
                                                                                                                                                                                              let books_tops = { book1; book2; book3 } in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 1. calculate the implied orders that are available right now... *)
                                                                                                                                                                                              let imp_order = calc_implied_strat_order s_id s books_tops sd m.curr_time in
                                                                                                                                                                                            
                                                                                                                                                                                              (* Need to increase the order ID first *)
                                                                                                                                                                                              let new_ord_id = m.last_ord_id + 1 in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 2. insert them into the order book *)
                                                                                                                                                                                              let strat_book =
                                                                                                                                                                                                begin
                                                                                                                                                                                                  match s_id with
                                                                                                                                                                                                  | STRAT1 -> insert_order { imp_order with o_id = new_ord_id } m.s_book1
                                                                                                                                                                                                  | STRAT2 -> insert_order { imp_order with o_id = new_ord_id } m.s_book2
                                                                                                                                                                                                end in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 3. perform the uncross - get the fills, etc... *)
                                                                                                                                                                                              let unc_result = uncross_book strat_book [] 0 in
                                                                                                                                                                                            
                                                                                                                                                                                              let fq = unc_result.uncrossed_qty in
                                                                                                                                                                                            
                                                                                                                                                                                              if fq = 0 then
                                                                                                                                                                                                (* Since we didn't trade anything, let's just return the original market state *)
                                                                                                                                                                                                m
                                                                                                                                                                                              else
                                                                                                                                                                                            
                                                                                                                                                                                              let adjust (mult : int) =
                                                                                                                                                                                                let mult = -mult in
                                                                                                                                                                                                if sd = BUY then mult else -mult in
                                                                                                                                                                                            
                                                                                                                                                                                              let adj_mul1 = adjust s.leg1.leg_mult in
                                                                                                                                                                                              let adj_mul2 = adjust s.leg2.leg_mult in
                                                                                                                                                                                              let adj_mul3 = adjust s.leg3.leg_mult in
                                                                                                                                                                                            
                                                                                                                                                                                              (* calculate the prices at which outright orders will trade *)
                                                                                                                                                                                              let price1 = calc_implied_trade_price adj_mul1 book1 in
                                                                                                                                                                                              let price2 = calc_implied_trade_price adj_mul2 book2 in
                                                                                                                                                                                              let price3 = calc_implied_trade_price adj_mul3 book3 in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 4. allocate fills to the outright orders *)
                                                                                                                                                                                              let out_book1_res = allocate_implied_fills m.out_book1 (fq * adj_mul1) price1 m.curr_time in
                                                                                                                                                                                              let out_book2_res = allocate_implied_fills m.out_book2 (fq * adj_mul2) price2 m.curr_time in
                                                                                                                                                                                              let out_book3_res = allocate_implied_fills m.out_book3 (fq * adj_mul3) price3 m.curr_time in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 5. remove the implied orders - notice that the uncrossed result contains a new book
                                                                                                                                                                                                with partial fills *)
                                                                                                                                                                                              let m = match s_id with
                                                                                                                                                                                              | STRAT1 -> { m with s_book1 = remove_imp_orders unc_result.uncrossed_book }
                                                                                                                                                                                              | STRAT2 -> { m with s_book2 = remove_imp_orders unc_result.uncrossed_book } in
                                                                                                                                                                                            
                                                                                                                                                                                              (* 6. let's now gather all of the fills and turn them into outbound messages *)
                                                                                                                                                                                              let new_fill_msgs = create_fill_msgs (unc_result.uncrossed_fills @ out_book1_res.uncrossed_fills
                                                                                                                                                                                                @ out_book2_res.uncrossed_fills @ out_book3_res.uncrossed_fills) in
                                                                                                                                                                                            
                                                                                                                                                                                              { m with
                                                                                                                                                                                                outbound_msgs = new_fill_msgs @ m.outbound_msgs
                                                                                                                                                                                                ; out_book1 = out_book1_res.uncrossed_book
                                                                                                                                                                                                ; out_book2 = out_book2_res.uncrossed_book
                                                                                                                                                                                                ; out_book3 = out_book3_res.uncrossed_book
                                                                                                                                                                                                ; last_ord_id = new_ord_id }
                                                                                                                                                                                            ;;
                                                                                                                                                                                            
                                                                                                                                                                                            Out[23]:
                                                                                                                                                                                            val implied_uncross_side :
                                                                                                                                                                                              side -> strategy_id -> strategy -> market -> market = <fun>
                                                                                                                                                                                            

                                                                                                                                                                                            Let's now experiment with some concrete examples.

                                                                                                                                                                                            In [24]:
                                                                                                                                                                                            #program;;
                                                                                                                                                                                            (* #remove_doc doc_of_market;; *)
                                                                                                                                                                                            #logic;;
                                                                                                                                                                                            
                                                                                                                                                                                            let strat = {
                                                                                                                                                                                              time_created = 1;
                                                                                                                                                                                              leg1    = { leg_sec_idx = OUT1; leg_mult = 1 }
                                                                                                                                                                                              ; leg2  = { leg_sec_idx = OUT2; leg_mult = -2 }
                                                                                                                                                                                              ; leg3  = { leg_sec_idx = OUT3; leg_mult = 0 }
                                                                                                                                                                                            };;
                                                                                                                                                                                            
                                                                                                                                                                                            let books = {
                                                                                                                                                                                                book1 = { bid_info = Some { li_qty = 500; li_price = 50 } ; ask_info = Some { li_qty = 750 ; li_price = 50 }}
                                                                                                                                                                                              ; book2 = { bid_info = Some { li_qty = 200 ; li_price = 60 }; ask_info = Some { li_qty = 500 ; li_price = 70 }}
                                                                                                                                                                                              ; book3 = { bid_info = None ; ask_info = None }
                                                                                                                                                                                            };;
                                                                                                                                                                                            
                                                                                                                                                                                            let m = {
                                                                                                                                                                                              curr_time = 1
                                                                                                                                                                                            
                                                                                                                                                                                              ; last_ord_id = 0
                                                                                                                                                                                            
                                                                                                                                                                                              (* first strategy is 2*x1 - x2 + x3 *)
                                                                                                                                                                                              ; strat1 = (make_strat 1 2 (-1) 1)
                                                                                                                                                                                              (* second strategy is just the 3rd outright security *)
                                                                                                                                                                                              ; strat2 = (make_strat 2 0 1 0)
                                                                                                                                                                                            
                                                                                                                                                                                              (* outright books *)
                                                                                                                                                                                              ; out_book1 = {
                                                                                                                                                                                                b_buys = [ (make BUY 500 50 1 (Outright OUT1) 1 false 1) ]
                                                                                                                                                                                                ; b_sells = [ (make SELL 750 55 2 (Outright OUT1) 1 false 1) ]
                                                                                                                                                                                              }
                                                                                                                                                                                            
                                                                                                                                                                                              ; out_book2 = {
                                                                                                                                                                                                b_buys = [ (make BUY 200 60 3 (Outright OUT1) 1 false 1) ]
                                                                                                                                                                                                ; b_sells = [ (make SELL 500 70 4 (Outright OUT1) 1 false 1) ]
                                                                                                                                                                                              }
                                                                                                                                                                                            
                                                                                                                                                                                              ; out_book3 = {
                                                                                                                                                                                                b_buys = [ ]
                                                                                                                                                                                                ; b_sells = []
                                                                                                                                                                                              }
                                                                                                                                                                                            
                                                                                                                                                                                              (* Strategy books *)
                                                                                                                                                                                              ; s_book1 = {
                                                                                                                                                                                                b_buys = [
                                                                                                                                                                                                ]
                                                                                                                                                                                                ; b_sells = [
                                                                                                                                                                                                  (make SELL 100 (-100) 5 (Strategy STRAT1) 1 false 1)
                                                                                                                                                                                                ]
                                                                                                                                                                                              }
                                                                                                                                                                                              ; s_book2 = empty_book
                                                                                                                                                                                            
                                                                                                                                                                                              (* Inbound and outbound message queues *)
                                                                                                                                                                                              ; inbound_msgs = []
                                                                                                                                                                                              ; outbound_msgs = []
                                                                                                                                                                                            } in
                                                                                                                                                                                            
                                                                                                                                                                                            let m' = implied_uncross_side BUY STRAT1 strat m in
                                                                                                                                                                                            
                                                                                                                                                                                            (*calc_implied_strat_order STRAT1 m.strat1 books BUY 1 *)
                                                                                                                                                                                            m'.outbound_msgs
                                                                                                                                                                                            
                                                                                                                                                                                            Out[24]:
                                                                                                                                                                                            val strat : strategy =
                                                                                                                                                                                              {time_created = 1; leg1 = {leg_sec_idx = OUT1; leg_mult = 1};
                                                                                                                                                                                               leg2 = {leg_sec_idx = OUT2; leg_mult = -2};
                                                                                                                                                                                               leg3 = {leg_sec_idx = OUT3; leg_mult = 0}}
                                                                                                                                                                                            val books : books_info =
                                                                                                                                                                                              {book1 =
                                                                                                                                                                                                {bid_info = Some {li_qty = 500; li_price = 50};
                                                                                                                                                                                                 ask_info = Some {li_qty = 750; li_price = 50}};
                                                                                                                                                                                               book2 =
                                                                                                                                                                                                {bid_info = Some {li_qty = 200; li_price = 60};
                                                                                                                                                                                                 ask_info = Some {li_qty = 500; li_price = 70}};
                                                                                                                                                                                               book3 = {bid_info = None; ask_info = None}}
                                                                                                                                                                                            - : outbound_msg list =
                                                                                                                                                                                            [Fill
                                                                                                                                                                                              {fill_client_id = 1; fill_qty = 100; fill_price = -95; fill_order_id = 5;
                                                                                                                                                                                               fill_order_done = true};
                                                                                                                                                                                             Fill
                                                                                                                                                                                              {fill_client_id = 1; fill_qty = 100; fill_price = 50; fill_order_id = 1;
                                                                                                                                                                                               fill_order_done = true};
                                                                                                                                                                                             Fill
                                                                                                                                                                                              {fill_client_id = 1; fill_qty = 200; fill_price = 70; fill_order_id = 4;
                                                                                                                                                                                               fill_order_done = true}]
                                                                                                                                                                                            

                                                                                                                                                                                            3.5 Implied uncrossing decomposition

                                                                                                                                                                                            In [25]:
                                                                                                                                                                                            (* Let's try to decompose the logic of 'implied_uncross_side' - we will put
                                                                                                                                                                                               several functions in the basis to focus on the critical aspects of the logic *)
                                                                                                                                                                                            #timeout 1000;;
                                                                                                                                                                                            
                                                                                                                                                                                            let d = Modular_decomp.top "implied_uncross_side"
                                                                                                                                                                                                    ~basis:["get_book_tops"; "allocate_implied_fills"; "insert_order";
                                                                                                                                                                                                    "create_fill_msgs"; "calc_implied_strat_order"] ~prune:true [@@program];;
                                                                                                                                                                                            
                                                                                                                                                                                            Out[25]:
                                                                                                                                                                                            val d : Modular_decomp_intf.decomp_ref = <abstr>