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]:
/usr/local/var/imandra/_opam/lib/uutf: added to search path
/usr/local/var/imandra/_opam/lib/uutf/uutf.cma: loaded
/usr/local/var/imandra/_opam/lib/tyxml/functor: added to search path
/usr/local/var/imandra/_opam/lib/tyxml/functor/tyxml_f.cma: loaded
/usr/local/var/imandra/_opam/lib/tyxml: added to search path
/usr/local/var/imandra/_opam/lib/tyxml/tyxml.cma: loaded
- : unit = ()
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.013s
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:3427
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:690676
final checks:6
added eqs:80
del clause:19
arith eq adapter:14
memory:5.240000
max memory:5.240000
Expand
  • start[0.013s]
      let (_x_0 : fill list) = List.tl … in
      let (_x_1 : int) = count.list count.fill _x_0 in
      f <> [] && count.list count.fill f >= 0 && _x_1 >= 0
      ==> not (_x_0 <> [])
          || Ordinal.( << ) (Ordinal.Int _x_1)
             (Ordinal.Int (count.list count.fill …))
  • simplify
    into:
    let (_x_0 : fill list) = List.tl … in
    let (_x_1 : int) = count.list count.fill _x_0 in
    let (_x_2 : int) = count.list count.fill … in
    (not (_x_0 <> []) || Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2))
    || not ((… <> [] && _x_2 >= 0) && _x_1 >= 0)
    expansions:
    []
    rewrite_steps:
      forward_chaining:
      • unroll
        expr:
        (|Ordinal.<<_129/client|
          (|Ordinal.Int_114/client|
            (|count.list_1698/server| (|get.::.1_1672/s…
        expansions:
        • unroll
          expr:
          (|count.list_1698/server| (|get.::.1_1672/server| f_1687/server))
          expansions:
          • unroll
            expr:
            (|count.list_1698/server| f_1687/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:2
            definitions:0
            inductions:0
            search_time:
            0.012s
            details:
            Expand
            smt_stats:
            arith offset eqs:7
            num checks:6
            arith assert lower:82
            arith tableau max rows:10
            arith tableau max columns:27
            arith pivots:64
            rlimit count:11002
            mk clause:86
            datatype occurs check:19
            mk bool var:353
            arith assert upper:80
            datatype splits:66
            decisions:100
            arith row summations:83
            arith bound prop:3
            propagations:102
            conflicts:24
            arith fixed eqs:30
            datatype accessor ax:41
            minimized lits:10
            arith conflicts:12
            arith num rows:10
            arith assert diseq:4
            datatype constructor ax:75
            num allocs:2694275
            final checks:4
            added eqs:410
            del clause:64
            arith eq adapter:64
            memory:5.430000
            max memory:5.430000
            Expand
            • start[0.012s]
                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 : order) = List.hd orders in
              let (_x_5 : int) = count.list count.order orders in
              let (_x_6 : int) = count.list count.order _x_0 in
              (not (not (_x_1.o_client_id = _x_2 && _x_1.o_id = _x_3) && _x_0 <> [])
               || not
                  (((not (_x_4.o_client_id = _x_2 && _x_4.o_id = _x_3) && orders <> [])
                    && _x_5 >= 0)
                   && _x_6 >= 0))
              || Ordinal.( << ) (Ordinal.Int _x_6) (Ordinal.Int _x_5)
              expansions:
              []
              rewrite_steps:
                forward_chaining:
                • unroll
                  expr:
                  (|count.list_1735/server| orders_1726/server)
                  expansions:
                  • unroll
                    expr:
                    (|Ordinal.<<_129/client|
                      (|Ordinal.Int_114/client|
                        (|count.list_1735/server| (|get.::.1_1646/s…
                    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:59
                    arith tableau max rows:21
                    arith tableau max columns:52
                    arith pivots:45
                    rlimit count:24830
                    mk clause:78
                    datatype occurs check:41
                    mk bool var:337
                    arith assert upper:41
                    datatype splits:59
                    decisions:90
                    arith row summations:58
                    propagations:75
                    conflicts:9
                    arith fixed eqs:28
                    datatype accessor ax:36
                    arith conflicts:2
                    arith num rows:21
                    datatype constructor ax:82
                    num allocs:10721404
                    final checks:6
                    added eqs:421
                    del clause:42
                    arith eq adapter:35
                    memory:5.560000
                    max memory:5.580000
                    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 : int) = (List.hd _x_0).o_price in
                      let (_x_5 : bool) = o.o_side = BUY in
                      let (_x_6 : bool) = _x_0 <> [] in
                      (Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                       || not ((_x_3 <= _x_4 && _x_5) && _x_6)
                          && not ((_x_4 <= _x_3 && not _x_5) && _x_6))
                      || not
                         ((((_x_3 <= (List.hd orders).o_price && _x_5) && orders <> [])
                           && _x_2 >= 0)
                          && _x_1 >= 0)
                      expansions:
                      []
                      rewrite_steps:
                        forward_chaining:
                        • unroll
                          expr:
                          (|count.list_1735/server| (|get.::.1_1646/server| orders_1792/server))
                          expansions:
                          • unroll
                            expr:
                            (|count.list_1735/server| orders_1792/server)
                            expansions:
                            • unroll
                              expr:
                              (|Ordinal.<<_129/client|
                                (|Ordinal.Int_114/client|
                                  (|count.list_1735/server| (|get.::.1_1646/s…
                              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.016s
                              details:
                              Expand
                              smt_stats:
                              num checks:8
                              arith assert lower:55
                              arith tableau max rows:23
                              arith tableau max columns:54
                              arith pivots:52
                              rlimit count:17844
                              mk clause:77
                              datatype occurs check:31
                              mk bool var:362
                              arith assert upper:32
                              datatype splits:71
                              decisions:86
                              arith row summations:49
                              propagations:74
                              interface eqs:2
                              conflicts:10
                              arith fixed eqs:29
                              arith assume eqs:2
                              datatype accessor ax:43
                              arith conflicts:2
                              arith num rows:23
                              datatype constructor ax:95
                              num allocs:6058620
                              final checks:8
                              added eqs:462
                              del clause:41
                              arith eq adapter:32
                              memory:5.580000
                              max memory:5.580000
                              Expand
                              • start[0.016s]
                                  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 : 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
                                 (((((List.hd orders).o_price <= _x_0 && _x_2) && orders <> []) && _x_3 >= 0)
                                  && _x_5 >= 0)
                                 || Ordinal.( << ) (Ordinal.Int _x_5) (Ordinal.Int _x_3))
                                || not ((_x_0 <= _x_6 && _x_1) && _x_7)
                                   && not ((_x_6 <= _x_0 && _x_2) && _x_7)
                                expansions:
                                []
                                rewrite_steps:
                                  forward_chaining:
                                  • unroll
                                    expr:
                                    (|count.list_1735/server| (|get.::.1_1646/server| orders_1792/server))
                                    expansions:
                                    • unroll
                                      expr:
                                      (|count.list_1735/server| orders_1792/server)
                                      expansions:
                                      • unroll
                                        expr:
                                        (|Ordinal.<<_129/client|
                                          (|Ordinal.Int_114/client|
                                            (|count.list_1735/server| (|get.::.1_1646/s…
                                        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.011s
                                        details:
                                        Expand
                                        smt_stats:
                                        num checks:8
                                        arith assert lower:42
                                        arith tableau max rows:17
                                        arith tableau max columns:42
                                        arith pivots:33
                                        rlimit count:30002
                                        mk clause:62
                                        datatype occurs check:29
                                        mk bool var:143
                                        arith assert upper:31
                                        datatype splits:3
                                        decisions:49
                                        arith row summations:72
                                        propagations:54
                                        conflicts:12
                                        arith fixed eqs:19
                                        datatype accessor ax:9
                                        arith conflicts:2
                                        arith num rows:17
                                        datatype constructor ax:11
                                        num allocs:16567961
                                        final checks:6
                                        added eqs:100
                                        del clause:35
                                        arith eq adapter:27
                                        memory:5.460000
                                        max memory:5.580000
                                        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
                                            fills <> [] && _x_0 >= 0 && _x_2 >= 0
                                            ==> not (_x_1 <> [])
                                                || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0)
                                        • simplify
                                          into:
                                          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
                                          (not ((fills <> [] && _x_0 >= 0) && _x_2 >= 0)
                                           || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0))
                                          || not (_x_1 <> [])
                                          expansions:
                                          []
                                          rewrite_steps:
                                            forward_chaining:
                                            • unroll
                                              expr:
                                              (|count.list_1698/server| (|get.::.1_1672/server| fills_1912/server))
                                              expansions:
                                              • unroll
                                                expr:
                                                (|count.list_1698/server| fills_1912/server)
                                                expansions:
                                                • unroll
                                                  expr:
                                                  (|Ordinal.<<_129/client|
                                                    (|Ordinal.Int_114/client|
                                                      (|count.list_1698/server| (|get.::.1_1672/s…
                                                  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.017s
                                                  details:
                                                  Expand
                                                  smt_stats:
                                                  arith offset eqs:15
                                                  num checks:12
                                                  arith assert lower:65
                                                  arith tableau max rows:23
                                                  arith tableau max columns:43
                                                  arith pivots:42
                                                  rlimit count:43105
                                                  mk clause:110
                                                  datatype occurs check:66
                                                  mk bool var:652
                                                  arith assert upper:70
                                                  datatype splits:136
                                                  decisions:149
                                                  arith row summations:144
                                                  arith bound prop:8
                                                  propagations:163
                                                  interface eqs:3
                                                  conflicts:16
                                                  arith fixed eqs:39
                                                  arith assume eqs:3
                                                  datatype accessor ax:84
                                                  arith conflicts:2
                                                  arith num rows:23
                                                  arith assert diseq:17
                                                  datatype constructor ax:228
                                                  num allocs:23891503
                                                  final checks:13
                                                  added eqs:1291
                                                  del clause:69
                                                  arith eq adapter:55
                                                  memory:5.560000
                                                  max memory:5.580000
                                                  Expand
                                                  • start[0.017s]
                                                      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_price 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_price in
                                                      let (_x_6 : int) = List.length _x_0 + List.length _x_3 in
                                                      let (_x_7 : int) = if _x_6 >= 0 then _x_6 else 0 in
                                                      let (_x_8 : int) = List.length ….b_buys + List.length ….b_sells in
                                                      let (_x_9 : int) = if _x_8 >= 0 then _x_8 else 0 in
                                                      let (_x_10 : int) = _x_1.o_qty in
                                                      let (_x_11 : int) = _x_4.o_qty in
                                                      let (_x_12 : int) = if _x_10 < _x_11 then _x_10 else _x_11 in
                                                      let (_x_13 : int) = _x_10 - _x_12 in
                                                      let (_x_14 : order list) = List.tl _x_0 in
                                                      let (_x_15 : order list)
                                                          = if _x_13 = 0 then _x_14
                                                            else
                                                              {o_qty = _x_13; o_price = _x_2; o_time = …; o_id = …;
                                                               o_side = …; o_client_id = …; o_inst = …; o_is_implied = …}
                                                              :: _x_14
                                                      in
                                                      let (_x_16 : int) = _x_11 - _x_12 in
                                                      let (_x_17 : order list) = List.tl _x_3 in
                                                      let (_x_18 : order list)
                                                          = if _x_16 = 0 then _x_17
                                                            else
                                                              {o_qty = _x_16; o_price = _x_5; o_time = …; o_id = …;
                                                               o_side = …; o_client_id = …; o_inst = …; o_is_implied = …}
                                                              :: _x_17
                                                      in
                                                      _x_2 >= _x_5 && _x_0 <> [] && _x_3 <> [] && _x_7 >= 0 && _x_9 >= 0
                                                      ==> not
                                                          ((List.hd _x_15).o_price >= (List.hd _x_18).o_price
                                                           && _x_15 <> [] && _x_18 <> [])
                                                          || Ordinal.( << ) (Ordinal.Int _x_9) (Ordinal.Int _x_7)
                                                  • simplify
                                                    into:
                                                    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_1.o_qty in
                                                    let (_x_5 : int) = _x_3.o_qty in
                                                    let (_x_6 : int) = (-1) * (if _x_5 <= _x_4 then _x_5 else _x_4) in
                                                    let (_x_7 : order list) = if _x_4 + _x_6 = 0 then List.tl _x_0 else … in
                                                    let (_x_8 : order list) = if _x_5 + _x_6 = 0 then List.tl _x_2 else … in
                                                    let (_x_9 : int) = List.length _x_7 + List.length _x_8 in
                                                    let (_x_10 : int) = List.length _x_0 + List.length _x_2 in
                                                    (not ((_x_1.o_price >= _x_3.o_price && _x_0 <> []) && _x_2 <> [])
                                                     || Ordinal.( << ) (Ordinal.Int (if _x_9 >= 0 then _x_9 else 0))
                                                        (Ordinal.Int (if _x_10 >= 0 then _x_10 else 0)))
                                                    || not
                                                       (((List.hd _x_7).o_price >= (List.hd _x_8).o_price && _x_7 <> [])
                                                        && _x_8 <> [])
                                                    expansions:
                                                    []
                                                    rewrite_steps:
                                                      forward_chaining:
                                                      • unroll
                                                        expr:
                                                        (let ((a!1 (<= (o_qty_1399/client
                                                                         (|get.::.0_1645/server| (b_sells_1420/client b_19…
                                                        expansions:
                                                        • unroll
                                                          expr:
                                                          (let ((a!1 (<= (o_qty_1399/client
                                                                           (|get.::.0_1645/server| (b_sells_1420/client b_19…
                                                          expansions:
                                                          • unroll
                                                            expr:
                                                            (let ((a!1 (<= (o_qty_1399/client
                                                                             (|get.::.0_1645/server| (b_sells_1420/client b_19…
                                                            expansions:
                                                            • unroll
                                                              expr:
                                                              (|List.length_1946/server| (b_buys_1419/client b_1954/server))
                                                              expansions:
                                                              • unroll
                                                                expr:
                                                                (|List.length_1946/server| (b_sells_1420/client b_1954/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.012s
                                                                details:
                                                                Expand
                                                                smt_stats:
                                                                num checks:8
                                                                arith assert lower:79
                                                                arith tableau max rows:24
                                                                arith tableau max columns:57
                                                                arith pivots:51
                                                                rlimit count:62573
                                                                mk clause:93
                                                                datatype occurs check:22
                                                                mk bool var:346
                                                                arith assert upper:45
                                                                datatype splits:56
                                                                decisions:107
                                                                arith row summations:124
                                                                arith bound prop:2
                                                                propagations:94
                                                                interface eqs:2
                                                                conflicts:9
                                                                arith fixed eqs:39
                                                                arith assume eqs:2
                                                                datatype accessor ax:36
                                                                minimized lits:2
                                                                arith conflicts:2
                                                                arith num rows:24
                                                                datatype constructor ax:85
                                                                num allocs:43837723
                                                                final checks:8
                                                                added eqs:428
                                                                del clause:54
                                                                arith eq adapter:40
                                                                memory:5.670000
                                                                max memory:5.670000
                                                                Expand
                                                                • start[0.012s]
                                                                    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) = _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 : order list) = List.tl _x_0 in
                                                                  let (_x_7 : int) = count.list count.order (_x_1 :: _x_6) in
                                                                  let (_x_8 : int) = (List.hd _x_6).o_price in
                                                                  let (_x_9 : bool) = _x_6 <> [] in
                                                                  (not
                                                                   (((((not (not (_x_2 <= _x_3) && not (_x_3 <= 0)) && _x_4) && _x_0 <> [])
                                                                      && orders <> [])
                                                                     && _x_5 >= 0)
                                                                    && _x_7 >= 0)
                                                                   || not ((not (not (_x_8 <= _x_2) && not (_x_2 <= 0)) && _x_4) && _x_9)
                                                                      && not
                                                                         ((not (not (_x_2 <= _x_8) && not (_x_8 <= 0)) && not _x_4) && _x_9))
                                                                  || Ordinal.( << ) (Ordinal.Int _x_7) (Ordinal.Int _x_5)
                                                                  expansions:
                                                                  []
                                                                  rewrite_steps:
                                                                    forward_chaining:
                                                                    • unroll
                                                                      expr:
                                                                      (|count.list_1735/server|
                                                                        (|::| (|get.::.0_1645/server| (|get.::.1_1646/server| orders_2146/server…
                                                                      expansions:
                                                                      • unroll
                                                                        expr:
                                                                        (|count.list_1735/server| orders_2146/server)
                                                                        expansions:
                                                                        • unroll
                                                                          expr:
                                                                          (let ((a!1 (|count.list_1735/server|
                                                                                       (|::| (|get.::.0_1645/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.018s
                                                                          details:
                                                                          Expand
                                                                          smt_stats:
                                                                          num checks:8
                                                                          arith assert lower:70
                                                                          arith tableau max rows:24
                                                                          arith tableau max columns:57
                                                                          arith pivots:50
                                                                          rlimit count:52390
                                                                          mk clause:86
                                                                          datatype occurs check:28
                                                                          mk bool var:340
                                                                          arith assert upper:42
                                                                          datatype splits:56
                                                                          decisions:102
                                                                          arith row summations:109
                                                                          arith bound prop:2
                                                                          propagations:91
                                                                          interface eqs:1
                                                                          conflicts:11
                                                                          arith fixed eqs:34
                                                                          arith assume eqs:1
                                                                          datatype accessor ax:37
                                                                          minimized lits:2
                                                                          arith conflicts:2
                                                                          arith num rows:24
                                                                          datatype constructor ax:88
                                                                          num allocs:33225725
                                                                          final checks:7
                                                                          added eqs:418
                                                                          del clause:48
                                                                          arith eq adapter:35
                                                                          memory:5.670000
                                                                          max memory:5.670000
                                                                          Expand
                                                                          • start[0.018s]
                                                                              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) = List.tl _x_0 in
                                                                            let (_x_2 : int) = (List.hd _x_1).o_price in
                                                                            let (_x_3 : order) = List.hd _x_0 in
                                                                            let (_x_4 : int) = _x_3.o_price in
                                                                            let (_x_5 : bool) = not (_x_4 <= 0) in
                                                                            let (_x_6 : bool) = si = BUY in
                                                                            let (_x_7 : bool) = _x_1 <> [] in
                                                                            let (_x_8 : bool) = not _x_6 in
                                                                            let (_x_9 : int) = count.list count.order (_x_3 :: _x_1) in
                                                                            let (_x_10 : int) = count.list count.order orders in
                                                                            (not ((not (not (_x_2 <= _x_4) && _x_5) && _x_6) && _x_7)
                                                                             && not ((not (not (_x_4 <= _x_2) && not (_x_2 <= 0)) && _x_8) && _x_7)
                                                                             || Ordinal.( << ) (Ordinal.Int _x_9) (Ordinal.Int _x_10))
                                                                            || not
                                                                               (((((not (not ((List.hd orders).o_price <= _x_4) && _x_5) && _x_8)
                                                                                   && _x_0 <> [])
                                                                                  && orders <> [])
                                                                                 && _x_10 >= 0)
                                                                                && _x_9 >= 0)
                                                                            expansions:
                                                                            []
                                                                            rewrite_steps:
                                                                              forward_chaining:
                                                                              • unroll
                                                                                expr:
                                                                                (|count.list_1735/server|
                                                                                  (|::| (|get.::.0_1645/server| (|get.::.1_1646/server| orders_2146/server…
                                                                                expansions:
                                                                                • unroll
                                                                                  expr:
                                                                                  (|count.list_1735/server| orders_2146/server)
                                                                                  expansions:
                                                                                  • unroll
                                                                                    expr:
                                                                                    (let ((a!1 (|count.list_1735/server|
                                                                                                 (|::| (|get.::.0_1645/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.013s
                                                                                    details:
                                                                                    Expand
                                                                                    smt_stats:
                                                                                    num checks:8
                                                                                    arith assert lower:41
                                                                                    arith tableau max rows:16
                                                                                    arith tableau max columns:39
                                                                                    arith pivots:31
                                                                                    rlimit count:67997
                                                                                    mk clause:58
                                                                                    datatype occurs check:35
                                                                                    mk bool var:138
                                                                                    arith assert upper:29
                                                                                    datatype splits:3
                                                                                    decisions:48
                                                                                    arith row summations:80
                                                                                    propagations:53
                                                                                    conflicts:10
                                                                                    arith fixed eqs:18
                                                                                    datatype accessor ax:9
                                                                                    arith conflicts:2
                                                                                    arith num rows:16
                                                                                    datatype constructor ax:11
                                                                                    num allocs:56039487
                                                                                    final checks:6
                                                                                    added eqs:100
                                                                                    del clause:33
                                                                                    arith eq adapter:25
                                                                                    memory:5.590000
                                                                                    max memory:5.670000
                                                                                    Expand
                                                                                    • start[0.013s]
                                                                                        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 : 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
                                                                                      (not
                                                                                       ((((List.hd fills).fill_price = p && fills <> []) && _x_0 >= 0) && _x_2 >= 0)
                                                                                       || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0))
                                                                                      || not ((List.hd _x_1).fill_price = p && _x_1 <> [])
                                                                                      expansions:
                                                                                      []
                                                                                      rewrite_steps:
                                                                                        forward_chaining:
                                                                                        • unroll
                                                                                          expr:
                                                                                          (|count.list_1698/server| (|get.::.1_1672/server| fills_2309/server))
                                                                                          expansions:
                                                                                          • unroll
                                                                                            expr:
                                                                                            (|count.list_1698/server| fills_2309/server)
                                                                                            expansions:
                                                                                            • unroll
                                                                                              expr:
                                                                                              (|Ordinal.<<_129/client|
                                                                                                (|Ordinal.Int_114/client|
                                                                                                  (|count.list_1698/server| (|get.::.1_1672/s…
                                                                                              expansions:
                                                                                              • Unsat
                                                                                              Counterexample (after 7 steps, 0.021s):
                                                                                              let b : book =
                                                                                                let (_x_0 : instrument) = Strategy STRAT1 in
                                                                                                {b_buys =
                                                                                                 [{o_qty = 1142; o_price = 583; 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 = 583; 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.021s
                                                                                              details:
                                                                                              Expand
                                                                                              smt_stats:
                                                                                              arith offset eqs:35
                                                                                              arith assert lower:85
                                                                                              arith patches_succ:2
                                                                                              datatype occurs check:395
                                                                                              datatype splits:373
                                                                                              arith bound prop:9
                                                                                              propagations:383
                                                                                              arith patches:2
                                                                                              interface eqs:10
                                                                                              conflicts:21
                                                                                              arith fixed eqs:37
                                                                                              datatype constructor ax:692
                                                                                              num allocs:71682754
                                                                                              final checks:32
                                                                                              added eqs:3342
                                                                                              del clause:97
                                                                                              num checks:15
                                                                                              arith tableau max rows:25
                                                                                              arith tableau max columns:49
                                                                                              arith pivots:54
                                                                                              rlimit count:23074
                                                                                              mk clause:270
                                                                                              mk bool var:1705
                                                                                              arith gcd tests:2
                                                                                              arith assert upper:80
                                                                                              decisions:450
                                                                                              arith row summations:152
                                                                                              arith assume eqs:10
                                                                                              datatype accessor ax:225
                                                                                              minimized lits:1
                                                                                              arith conflicts:3
                                                                                              arith num rows:25
                                                                                              arith assert diseq:2
                                                                                              arith eq adapter:51
                                                                                              time:0.001000
                                                                                              memory:6.540000
                                                                                              max memory:6.540000
                                                                                              Expand
                                                                                              • start[0.021s]
                                                                                                  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_1579/client
                                                                                                      SELL_1347/client
                                                                                                      (b_sells_1420/client b_1610/client))
                                                                                                    expansions:
                                                                                                    • unroll
                                                                                                      expr:
                                                                                                      (side_price_sorted_1579/client
                                                                                                        BUY_1346/client
                                                                                                        (b_buys_1419/client b_1610/client))
                                                                                                      expansions:
                                                                                                      • unroll
                                                                                                        expr:
                                                                                                        (|List.length_2360/server|
                                                                                                          (uncrossed_fills_1494/client (uncross_book_1548/client b_1610/client |[…
                                                                                                        expansions:
                                                                                                        • unroll
                                                                                                          expr:
                                                                                                          (uncross_book_1548/client b_1610/client |[]| 0)
                                                                                                          expansions:
                                                                                                          • unroll
                                                                                                            expr:
                                                                                                            (let ((a!1 (+ (o_price_1400/client
                                                                                                                            (|get.::.0_2353/server| (b_buys_1419/client b_161…
                                                                                                            expansions:
                                                                                                            • unroll
                                                                                                              expr:
                                                                                                              (let ((a!1 (<= (o_qty_1399/client
                                                                                                                               (|get.::.0_2353/server| (b_sells_1420/client b_16…
                                                                                                              expansions:
                                                                                                              • unroll
                                                                                                                expr:
                                                                                                                (let ((a!1 (|::| (|get.::.0_2353/server|
                                                                                                                                   (|get.::.1_2354/server| (b_sells_1420/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 (583n)); 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 (583n)); 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:2
                                                                                                                definitions:0
                                                                                                                inductions:0
                                                                                                                search_time:
                                                                                                                0.011s
                                                                                                                details:
                                                                                                                Expand
                                                                                                                smt_stats:
                                                                                                                num checks:6
                                                                                                                arith assert lower:20
                                                                                                                arith tableau max rows:7
                                                                                                                arith tableau max columns:21
                                                                                                                arith pivots:12
                                                                                                                rlimit count:26251
                                                                                                                mk clause:34
                                                                                                                datatype occurs check:19
                                                                                                                mk bool var:88
                                                                                                                arith assert upper:18
                                                                                                                datatype splits:2
                                                                                                                decisions:26
                                                                                                                arith row summations:39
                                                                                                                propagations:27
                                                                                                                conflicts:9
                                                                                                                arith fixed eqs:7
                                                                                                                datatype accessor ax:9
                                                                                                                arith conflicts:2
                                                                                                                arith num rows:7
                                                                                                                datatype constructor ax:8
                                                                                                                num allocs:87944179
                                                                                                                final checks:4
                                                                                                                added eqs:62
                                                                                                                del clause:19
                                                                                                                arith eq adapter:14
                                                                                                                memory:6.290000
                                                                                                                max memory:6.540000
                                                                                                                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 : 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
                                                                                                                  (not ((_z <> [] && _x_0 >= 0) && _x_2 >= 0)
                                                                                                                   || Ordinal.( << ) (Ordinal.Int _x_2) (Ordinal.Int _x_0))
                                                                                                                  || not (_x_1 <> [])
                                                                                                                  expansions:
                                                                                                                  []
                                                                                                                  rewrite_steps:
                                                                                                                    forward_chaining:
                                                                                                                    • unroll
                                                                                                                      expr:
                                                                                                                      (|count.list_2525/server| _z_2514/server)
                                                                                                                      expansions:
                                                                                                                      • unroll
                                                                                                                        expr:
                                                                                                                        (|Ordinal.<<_129/client|
                                                                                                                          (|Ordinal.Int_114/client|
                                                                                                                            (|count.list_2525/server| (|get.::.1_2358/s…
                                                                                                                        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.012s
                                                                                                                        details:
                                                                                                                        Expand
                                                                                                                        smt_stats:
                                                                                                                        num checks:8
                                                                                                                        arith assert lower:49
                                                                                                                        arith tableau max rows:14
                                                                                                                        arith tableau max columns:44
                                                                                                                        arith pivots:39
                                                                                                                        rlimit count:32658
                                                                                                                        mk clause:81
                                                                                                                        datatype occurs check:29
                                                                                                                        mk bool var:290
                                                                                                                        arith assert upper:37
                                                                                                                        datatype splits:47
                                                                                                                        decisions:65
                                                                                                                        arith row summations:83
                                                                                                                        propagations:71
                                                                                                                        interface eqs:2
                                                                                                                        conflicts:10
                                                                                                                        arith fixed eqs:24
                                                                                                                        arith assume eqs:2
                                                                                                                        datatype accessor ax:33
                                                                                                                        minimized lits:1
                                                                                                                        arith conflicts:2
                                                                                                                        arith num rows:14
                                                                                                                        arith assert diseq:1
                                                                                                                        datatype constructor ax:65
                                                                                                                        num allocs:103965807
                                                                                                                        final checks:8
                                                                                                                        added eqs:320
                                                                                                                        del clause:39
                                                                                                                        arith eq adapter:33
                                                                                                                        memory:6.290000
                                                                                                                        max memory:6.540000
                                                                                                                        Expand
                                                                                                                        • start[0.012s]
                                                                                                                            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_2561/server| (|get.::.1_2354/server| _y_2554/server))
                                                                                                                              expansions:
                                                                                                                              • unroll
                                                                                                                                expr:
                                                                                                                                (|Ordinal.<<_129/client|
                                                                                                                                  (|Ordinal.Int_114/client|
                                                                                                                                    (|count.list_2561/server| (|get.::.1_2354/s…
                                                                                                                                expansions:
                                                                                                                                • unroll
                                                                                                                                  expr:
                                                                                                                                  (|count.list_2561/server| _y_2554/server)
                                                                                                                                  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:2
                                                                                                                                  definitions:0
                                                                                                                                  inductions:0
                                                                                                                                  search_time:
                                                                                                                                  0.010s
                                                                                                                                  details:
                                                                                                                                  Expand
                                                                                                                                  smt_stats:
                                                                                                                                  num checks:6
                                                                                                                                  arith assert lower:10
                                                                                                                                  arith tableau max rows:6
                                                                                                                                  arith tableau max columns:23
                                                                                                                                  arith pivots:4
                                                                                                                                  rlimit count:36017
                                                                                                                                  mk clause:25
                                                                                                                                  datatype occurs check:14
                                                                                                                                  mk bool var:170
                                                                                                                                  arith assert upper:6
                                                                                                                                  datatype splits:38
                                                                                                                                  decisions:27
                                                                                                                                  arith row summations:12
                                                                                                                                  propagations:20
                                                                                                                                  conflicts:7
                                                                                                                                  arith fixed eqs:2
                                                                                                                                  datatype accessor ax:30
                                                                                                                                  arith conflicts:2
                                                                                                                                  arith num rows:6
                                                                                                                                  datatype constructor ax:50
                                                                                                                                  num allocs:121510638
                                                                                                                                  final checks:4
                                                                                                                                  added eqs:206
                                                                                                                                  del clause:14
                                                                                                                                  arith eq adapter:5
                                                                                                                                  memory:6.300000
                                                                                                                                  max memory:6.540000
                                                                                                                                  Expand
                                                                                                                                  • start[0.010s]
                                                                                                                                      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.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
                                                                                                                                     ((((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)
                                                                                                                                    expansions:
                                                                                                                                    []
                                                                                                                                    rewrite_steps:
                                                                                                                                      forward_chaining:
                                                                                                                                      • unroll
                                                                                                                                        expr:
                                                                                                                                        (|Ordinal.<<_129/client|
                                                                                                                                          (|Ordinal.Int_114/client|
                                                                                                                                            (|count.list_2561/server| (|get.::.1_2354/s…
                                                                                                                                        expansions:
                                                                                                                                        • unroll
                                                                                                                                          expr:
                                                                                                                                          (|count.list_2561/server| _x_2590/server)
                                                                                                                                          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 = 3; o_id = 1; o_side = BUY;
                                                                                                                                                 o_client_id = 2; 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 = 2; o_id = 3; o_side = BUY;
                                                                                                                                                 o_client_id = 1; 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 = 3; o_id = 1; o_side = BUY;
                                                                                                                                                 o_client_id = 2; 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 = 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 = 6; o_id = 4; o_side = BUY;
                                                                                                                                                 o_client_id = 5; 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 = 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 = 4; o_id = 2; o_side = BUY;
                                                                                                                                                 o_client_id = 3; 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 = ...; 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.025s):
                                                                                                                                          let s1 : strategy =
                                                                                                                                            {time_created = 0; leg1 = {leg_sec_idx = OUT3; leg_mult = 0};
                                                                                                                                             leg2 = {leg_sec_idx = OUT2; leg_mult = 0};
                                                                                                                                             leg3 = {leg_sec_idx = OUT1; leg_mult = 18989}}
                                                                                                                                          let s2 : strategy =
                                                                                                                                            {time_created = 974; leg1 = {leg_sec_idx = OUT1; leg_mult = 1653};
                                                                                                                                             leg2 = {leg_sec_idx = OUT3; leg_mult = 8456};
                                                                                                                                             leg3 = {leg_sec_idx = OUT1; leg_mult = 8879}}
                                                                                                                                          let s3 : strategy =
                                                                                                                                            {time_created = (-1); leg1 = {leg_sec_idx = OUT2; leg_mult = 0};
                                                                                                                                             leg2 = {leg_sec_idx = OUT3; leg_mult = 18988};
                                                                                                                                             leg3 = {leg_sec_idx = OUT1; leg_mult = 1}}
                                                                                                                                          
                                                                                                                                          Refuted
                                                                                                                                          proof attempt
                                                                                                                                          ground_instances:0
                                                                                                                                          definitions:0
                                                                                                                                          inductions:0
                                                                                                                                          search_time:
                                                                                                                                          0.025s
                                                                                                                                          details:
                                                                                                                                          Expand
                                                                                                                                          smt_stats:
                                                                                                                                          arith offset eqs:7
                                                                                                                                          num checks:1
                                                                                                                                          arith assert lower:403
                                                                                                                                          arith tableau max rows:33
                                                                                                                                          arith tableau max columns:68
                                                                                                                                          arith pivots:56
                                                                                                                                          rlimit count:25735
                                                                                                                                          mk clause:499
                                                                                                                                          datatype occurs check:9
                                                                                                                                          mk bool var:956
                                                                                                                                          arith assert upper:294
                                                                                                                                          datatype splits:86
                                                                                                                                          decisions:652
                                                                                                                                          arith row summations:163
                                                                                                                                          arith bound prop:4
                                                                                                                                          propagations:1194
                                                                                                                                          interface eqs:3
                                                                                                                                          conflicts:40
                                                                                                                                          arith fixed eqs:102
                                                                                                                                          arith assume eqs:3
                                                                                                                                          datatype accessor ax:15
                                                                                                                                          minimized lits:3
                                                                                                                                          arith conflicts:9
                                                                                                                                          arith num rows:33
                                                                                                                                          arith assert diseq:65
                                                                                                                                          datatype constructor ax:112
                                                                                                                                          num allocs:1131828115
                                                                                                                                          final checks:4
                                                                                                                                          added eqs:1400
                                                                                                                                          del clause:247
                                                                                                                                          arith eq adapter:265
                                                                                                                                          time:0.013000
                                                                                                                                          memory:7.510000
                                                                                                                                          max memory:8.270000
                                                                                                                                          Expand
                                                                                                                                          • start[0.025s]
                                                                                                                                              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 : outright_id) = _x_2.leg_sec_idx in
                                                                                                                                              let (_x_17 : bool) = _x_16 = OUT1 in
                                                                                                                                              let (_x_18 : month)
                                                                                                                                                  = if _x_17 then Mar else if _x_16 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_19 : month)
                                                                                                                                                  = if _x_15 then Mar else if _x_14 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_20 : int)
                                                                                                                                                  = if _x_19 = Mar then 3
                                                                                                                                                    else if _x_19 = Jun then 6 else if _x_19 = Sep then 9 else 12
                                                                                                                                              in
                                                                                                                                              let (_x_21 : bool)
                                                                                                                                                  = (if _x_18 = Mar then 3
                                                                                                                                                     else if _x_18 = Jun then 6 else if _x_18 = Sep then 9 else 12)
                                                                                                                                                    < _x_20
                                                                                                                                              in
                                                                                                                                              let (_x_22 : month) = if _x_21 then _x_18 else _x_19 in
                                                                                                                                              let (_x_23 : bool)
                                                                                                                                                  = (if _x_22 = Mar then 3
                                                                                                                                                     else
                                                                                                                                                     if _x_22 = Jun then 6
                                                                                                                                                     else
                                                                                                                                                     if (if _x_21 then if _x_17 then Mar else …
                                                                                                                                                         else if _x_15 then Mar else …)
                                                                                                                                                        = Sep
                                                                                                                                                     then 9 else 12)
                                                                                                                                                    < _x_20
                                                                                                                                              in
                                                                                                                                              let (_x_24 : int)
                                                                                                                                                  = if (if _x_23 then _x_22 else _x_19) = Mar then 3
                                                                                                                                                    else
                                                                                                                                                    if (if _x_23
                                                                                                                                                        then
                                                                                                                                                          if _x_21 then if _x_17 then Mar else …
                                                                                                                                                          else if _x_15 then Mar else …
                                                                                                                                                        else _x_19)
                                                                                                                                                       = Jun
                                                                                                                                                    then 6
                                                                                                                                                    else
                                                                                                                                                    if (if _x_23 then if _x_21 then … else …
                                                                                                                                                        else if _x_15 then Mar else …)
                                                                                                                                                       = Sep
                                                                                                                                                    then 9 else 12
                                                                                                                                              in
                                                                                                                                              let (_x_25 : outright_id) = _x_10.leg_sec_idx in
                                                                                                                                              let (_x_26 : bool) = _x_25 = OUT1 in
                                                                                                                                              let (_x_27 : outright_id) = _x_8.leg_sec_idx in
                                                                                                                                              let (_x_28 : bool) = _x_27 = OUT1 in
                                                                                                                                              let (_x_29 : month)
                                                                                                                                                  = if _x_28 then Mar else if _x_27 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_30 : month)
                                                                                                                                                  = if _x_26 then Mar else if _x_25 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_31 : int)
                                                                                                                                                  = if _x_30 = Mar then 3
                                                                                                                                                    else if _x_30 = Jun then 6 else if _x_30 = Sep then 9 else 12
                                                                                                                                              in
                                                                                                                                              let (_x_32 : bool)
                                                                                                                                                  = (if _x_29 = Mar then 3
                                                                                                                                                     else if _x_29 = Jun then 6 else if _x_29 = Sep then 9 else 12)
                                                                                                                                                    < _x_31
                                                                                                                                              in
                                                                                                                                              let (_x_33 : month) = if _x_32 then _x_29 else _x_30 in
                                                                                                                                              let (_x_34 : bool)
                                                                                                                                                  = (if _x_33 = Mar then 3
                                                                                                                                                     else
                                                                                                                                                     if _x_33 = Jun then 6
                                                                                                                                                     else
                                                                                                                                                     if (if _x_32 then if _x_28 then Mar else …
                                                                                                                                                         else if _x_26 then Mar else …)
                                                                                                                                                        = Sep
                                                                                                                                                     then 9 else 12)
                                                                                                                                                    < _x_31
                                                                                                                                              in
                                                                                                                                              let (_x_35 : int)
                                                                                                                                                  = if (if _x_34 then _x_33 else _x_30) = Mar then 3
                                                                                                                                                    else
                                                                                                                                                    if (if _x_34
                                                                                                                                                        then
                                                                                                                                                          if _x_32 then if _x_28 then Mar else …
                                                                                                                                                          else if _x_26 then Mar else …
                                                                                                                                                        else _x_30)
                                                                                                                                                       = Jun
                                                                                                                                                    then 6
                                                                                                                                                    else
                                                                                                                                                    if (if _x_34 then if _x_32 then … else …
                                                                                                                                                        else if _x_26 then Mar else …)
                                                                                                                                                       = Sep
                                                                                                                                                    then 9 else 12
                                                                                                                                              in
                                                                                                                                              let (_x_36 : int) = ( :var_2: ).time_created in
                                                                                                                                              let (_x_37 : leg) = ( :var_2: ).leg1 in
                                                                                                                                              let (_x_38 : int) = _x_37.leg_mult in
                                                                                                                                              let (_x_39 : leg) = ( :var_2: ).leg2 in
                                                                                                                                              let (_x_40 : int) = _x_39.leg_mult in
                                                                                                                                              let (_x_41 : int) = ( :var_2: ).leg3.leg_mult in
                                                                                                                                              let (_x_42 : int)
                                                                                                                                                  = (if _x_38 < 0 then ~- _x_38 else _x_38)
                                                                                                                                                    + (if _x_40 < 0 then ~- _x_40 else _x_40)
                                                                                                                                                    + (if _x_41 < 0 then ~- _x_41 else _x_41)
                                                                                                                                              in
                                                                                                                                              let (_x_43 : outright_id) = _x_39.leg_sec_idx in
                                                                                                                                              let (_x_44 : bool) = _x_43 = OUT1 in
                                                                                                                                              let (_x_45 : outright_id) = _x_37.leg_sec_idx in
                                                                                                                                              let (_x_46 : bool) = _x_45 = OUT1 in
                                                                                                                                              let (_x_47 : month)
                                                                                                                                                  = if _x_46 then Mar else if _x_45 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_48 : month)
                                                                                                                                                  = if _x_44 then Mar else if _x_43 = OUT2 then Jun else Sep
                                                                                                                                              in
                                                                                                                                              let (_x_49 : int)
                                                                                                                                                  = if _x_48 = Mar then 3
                                                                                                                                                    else if _x_48 = Jun then 6 else if _x_48 = Sep then 9 else 12
                                                                                                                                              in
                                                                                                                                              let (_x_50 : bool)
                                                                                                                                                  = (if _x_47 = Mar then 3
                                                                                                                                                     else if _x_47 = Jun then 6 else if _x_47 = Sep then 9 else 12)
                                                                                                                                                    < _x_49
                                                                                                                                              in
                                                                                                                                              let (_x_51 : month) = if _x_50 then _x_47 else _x_48 in
                                                                                                                                              let (_x_52 : bool)
                                                                                                                                                  = (if _x_51 = Mar then 3
                                                                                                                                                     else
                                                                                                                                                     if _x_51 = Jun then 6
                                                                                                                                                     else
                                                                                                                                                     if (if _x_50 then if _x_46 then Mar else …
                                                                                                                                                         else if _x_44 then Mar else …)
                                                                                                                                                        = Sep
                                                                                                                                                     then 9 else 12)
                                                                                                                                                    < _x_49
                                                                                                                                              in
                                                                                                                                              let (_x_53 : int)
                                                                                                                                                  = if (if _x_52 then _x_51 else _x_48) = Mar then 3
                                                                                                                                                    else
                                                                                                                                                    if (if _x_52
                                                                                                                                                        then
                                                                                                                                                          if _x_50 then if _x_46 then Mar else …
                                                                                                                                                          else if _x_44 then Mar else …
                                                                                                                                                        else _x_48)
                                                                                                                                                       = Jun
                                                                                                                                                    then 6
                                                                                                                                                    else
                                                                                                                                                    if (if _x_52 then if _x_50 then … else …
                                                                                                                                                        else if _x_44 then Mar else …)
                                                                                                                                                       = Sep
                                                                                                                                                    then 9 else 12
                                                                                                                                              in
                                                                                                                                              (if _x_24 < _x_35 then true
                                                                                                                                               else if _x_7 > _x_13 then true else _x_0 <= _x_1)
                                                                                                                                              && (if _x_35 < _x_53 then true
                                                                                                                                                  else if _x_13 > _x_42 then true else _x_1 <= _x_36)
                                                                                                                                              ==> (if _x_24 < _x_53 then true
                                                                                                                                                   else if _x_7 > _x_42 then true else _x_0 <= _x_36)
                                                                                                                                          • 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 : leg) = ( :var_2: ).leg2 in
                                                                                                                                            let (_x_6 : outright_id) = _x_5.leg_sec_idx in
                                                                                                                                            let (_x_7 : bool) = _x_6 = OUT1 in
                                                                                                                                            let (_x_8 : month) = if _x_7 then Mar else if _x_6 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_9 : int)
                                                                                                                                                = if _x_8 = Mar then 3
                                                                                                                                                  else if _x_8 = Jun then 6 else if _x_8 = Sep then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_10 : month) = if _x_4 then Mar else if _x_3 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_11 : bool)
                                                                                                                                                = _x_9 <=
                                                                                                                                                  (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_11 then _x_8 else _x_10 in
                                                                                                                                            let (_x_13 : bool)
                                                                                                                                                = _x_11
                                                                                                                                                  || _x_9 <=
                                                                                                                                                     (if _x_12 = Mar then 3
                                                                                                                                                      else
                                                                                                                                                      if _x_12 = Jun then 6
                                                                                                                                                      else
                                                                                                                                                      if (if _x_11 then if _x_7 then Mar else …
                                                                                                                                                          else if _x_4 then Mar else …)
                                                                                                                                                         = Sep
                                                                                                                                                      then 9 else 12)
                                                                                                                                            in
                                                                                                                                            let (_x_14 : month) = if _x_13 then _x_8 else _x_10 in
                                                                                                                                            let (_x_15 : int)
                                                                                                                                                = if _x_14 = Mar then 3
                                                                                                                                                  else
                                                                                                                                                  if _x_14 = Jun then 6
                                                                                                                                                  else
                                                                                                                                                  if (if _x_13 then if _x_7 then Mar else …
                                                                                                                                                      else if _x_4 then Mar else …)
                                                                                                                                                     = Sep
                                                                                                                                                  then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_16 : leg) = ( :var_0: ).leg1 in
                                                                                                                                            let (_x_17 : outright_id) = _x_16.leg_sec_idx in
                                                                                                                                            let (_x_18 : bool) = _x_17 = OUT1 in
                                                                                                                                            let (_x_19 : leg) = ( :var_0: ).leg2 in
                                                                                                                                            let (_x_20 : outright_id) = _x_19.leg_sec_idx in
                                                                                                                                            let (_x_21 : bool) = _x_20 = OUT1 in
                                                                                                                                            let (_x_22 : month)
                                                                                                                                                = if _x_21 then Mar else if _x_20 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_23 : int)
                                                                                                                                                = if _x_22 = Mar then 3
                                                                                                                                                  else if _x_22 = Jun then 6 else if _x_22 = Sep then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_24 : month)
                                                                                                                                                = if _x_18 then Mar else if _x_17 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_25 : bool)
                                                                                                                                                = _x_23 <=
                                                                                                                                                  (if _x_24 = Mar then 3
                                                                                                                                                   else if _x_24 = Jun then 6 else if _x_24 = Sep then 9 else 12)
                                                                                                                                            in
                                                                                                                                            let (_x_26 : month) = if _x_25 then _x_22 else _x_24 in
                                                                                                                                            let (_x_27 : bool)
                                                                                                                                                = _x_25
                                                                                                                                                  || _x_23 <=
                                                                                                                                                     (if _x_26 = Mar then 3
                                                                                                                                                      else
                                                                                                                                                      if _x_26 = Jun then 6
                                                                                                                                                      else
                                                                                                                                                      if (if _x_25 then if _x_21 then Mar else …
                                                                                                                                                          else if _x_18 then Mar else …)
                                                                                                                                                         = Sep
                                                                                                                                                      then 9 else 12)
                                                                                                                                            in
                                                                                                                                            let (_x_28 : month) = if _x_27 then _x_22 else _x_24 in
                                                                                                                                            let (_x_29 : int)
                                                                                                                                                = if _x_28 = Mar then 3
                                                                                                                                                  else
                                                                                                                                                  if _x_28 = Jun then 6
                                                                                                                                                  else
                                                                                                                                                  if (if _x_27 then if _x_21 then Mar else …
                                                                                                                                                      else if _x_18 then Mar else …)
                                                                                                                                                     = Sep
                                                                                                                                                  then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_30 : int) = _x_16.leg_mult in
                                                                                                                                            let (_x_31 : int) = _x_19.leg_mult in
                                                                                                                                            let (_x_32 : int) = ( :var_0: ).leg3.leg_mult in
                                                                                                                                            let (_x_33 : int)
                                                                                                                                                = (if 0 <= _x_30 then _x_30 else (-1) * _x_30)
                                                                                                                                                  + (if 0 <= _x_31 then _x_31 else (-1) * _x_31)
                                                                                                                                                  + (if 0 <= _x_32 then _x_32 else (-1) * _x_32)
                                                                                                                                            in
                                                                                                                                            let (_x_34 : int) = _x_2.leg_mult in
                                                                                                                                            let (_x_35 : int) = _x_5.leg_mult in
                                                                                                                                            let (_x_36 : int) = ( :var_2: ).leg3.leg_mult in
                                                                                                                                            let (_x_37 : int)
                                                                                                                                                = (if 0 <= _x_34 then _x_34 else (-1) * _x_34)
                                                                                                                                                  + (if 0 <= _x_35 then _x_35 else (-1) * _x_35)
                                                                                                                                                  + (if 0 <= _x_36 then _x_36 else (-1) * _x_36)
                                                                                                                                            in
                                                                                                                                            let (_x_38 : int) = ( :var_1: ).time_created in
                                                                                                                                            let (_x_39 : leg) = ( :var_1: ).leg1 in
                                                                                                                                            let (_x_40 : outright_id) = _x_39.leg_sec_idx in
                                                                                                                                            let (_x_41 : bool) = _x_40 = OUT1 in
                                                                                                                                            let (_x_42 : leg) = ( :var_1: ).leg2 in
                                                                                                                                            let (_x_43 : outright_id) = _x_42.leg_sec_idx in
                                                                                                                                            let (_x_44 : bool) = _x_43 = OUT1 in
                                                                                                                                            let (_x_45 : month)
                                                                                                                                                = if _x_44 then Mar else if _x_43 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_46 : int)
                                                                                                                                                = if _x_45 = Mar then 3
                                                                                                                                                  else if _x_45 = Jun then 6 else if _x_45 = Sep then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_47 : month)
                                                                                                                                                = if _x_41 then Mar else if _x_40 = OUT2 then Jun else Sep
                                                                                                                                            in
                                                                                                                                            let (_x_48 : bool)
                                                                                                                                                = _x_46 <=
                                                                                                                                                  (if _x_47 = Mar then 3
                                                                                                                                                   else if _x_47 = Jun then 6 else if _x_47 = Sep then 9 else 12)
                                                                                                                                            in
                                                                                                                                            let (_x_49 : month) = if _x_48 then _x_45 else _x_47 in
                                                                                                                                            let (_x_50 : bool)
                                                                                                                                                = _x_48
                                                                                                                                                  || _x_46 <=
                                                                                                                                                     (if _x_49 = Mar then 3
                                                                                                                                                      else
                                                                                                                                                      if _x_49 = Jun then 6
                                                                                                                                                      else
                                                                                                                                                      if (if _x_48 then if _x_44 then Mar else …
                                                                                                                                                          else if _x_41 then Mar else …)
                                                                                                                                                         = Sep
                                                                                                                                                      then 9 else 12)
                                                                                                                                            in
                                                                                                                                            let (_x_51 : month) = if _x_50 then _x_45 else _x_47 in
                                                                                                                                            let (_x_52 : int)
                                                                                                                                                = if _x_51 = Mar then 3
                                                                                                                                                  else
                                                                                                                                                  if _x_51 = Jun then 6
                                                                                                                                                  else
                                                                                                                                                  if (if _x_50 then if _x_44 then Mar else …
                                                                                                                                                      else if _x_41 then Mar else …)
                                                                                                                                                     = Sep
                                                                                                                                                  then 9 else 12
                                                                                                                                            in
                                                                                                                                            let (_x_53 : int) = _x_39.leg_mult in
                                                                                                                                            let (_x_54 : int) = _x_42.leg_mult in
                                                                                                                                            let (_x_55 : int) = ( :var_1: ).leg3.leg_mult in
                                                                                                                                            let (_x_56 : int)
                                                                                                                                                = (if 0 <= _x_53 then _x_53 else (-1) * _x_53)
                                                                                                                                                  + (if 0 <= _x_54 then _x_54 else (-1) * _x_54)
                                                                                                                                                  + (if 0 <= _x_55 then _x_55 else (-1) * _x_55)
                                                                                                                                            in
                                                                                                                                            ((_x_0 <= _x_1 || not (_x_15 <= _x_29)) || not (_x_33 <= _x_37))
                                                                                                                                            || not
                                                                                                                                               (((_x_0 <= _x_38 || not (_x_52 <= _x_29)) || not (_x_33 <= _x_56))
                                                                                                                                                && ((_x_38 <= _x_1 || not (_x_15 <= _x_52)) || not (_x_56 <= _x_37)))
                                                                                                                                            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 (0n))}; leg2 = {leg_sec_idx = OUT2; leg_mult = (Z.of_nativeint (0n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (18989n))}} let s2 : strategy = {time_created = (Z.of_nativeint (974n)); leg1 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (1653n))}; leg2 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (8456n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (8879n))}} let s3 : strategy = {time_created = (Z.of_nativeint (-1n)); leg1 = {leg_sec_idx = OUT2; leg_mult = (Z.of_nativeint (0n))}; leg2 = {leg_sec_idx = OUT3; leg_mult = (Z.of_nativeint (18988n))}; leg3 = {leg_sec_idx = OUT1; leg_mult = (Z.of_nativeint (1n))}} )

                                                                                                                                              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:
                                                                                                                                              num checks:8
                                                                                                                                              arith assert lower:52
                                                                                                                                              arith tableau max rows:20
                                                                                                                                              arith tableau max columns:48
                                                                                                                                              arith pivots:43
                                                                                                                                              rlimit count:37008
                                                                                                                                              mk clause:65
                                                                                                                                              datatype occurs check:29
                                                                                                                                              mk bool var:251
                                                                                                                                              arith assert upper:27
                                                                                                                                              datatype splits:35
                                                                                                                                              decisions:65
                                                                                                                                              arith row summations:37
                                                                                                                                              propagations:59
                                                                                                                                              conflicts:10
                                                                                                                                              arith fixed eqs:25
                                                                                                                                              datatype accessor ax:29
                                                                                                                                              arith conflicts:2
                                                                                                                                              arith num rows:20
                                                                                                                                              datatype constructor ax:62
                                                                                                                                              num allocs:1265220739
                                                                                                                                              final checks:6
                                                                                                                                              added eqs:289
                                                                                                                                              del clause:36
                                                                                                                                              arith eq adapter:28
                                                                                                                                              memory:7.770000
                                                                                                                                              max memory:8.270000
                                                                                                                                              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 (((Is_a(None, li) && orders <> []) && _x_2 >= 0) && _x_1 >= 0))
                                                                                                                                                || not ((List.hd orders).o_price = (List.hd _x_0).o_price && _x_0 <> [])
                                                                                                                                                expansions:
                                                                                                                                                []
                                                                                                                                                rewrite_steps:
                                                                                                                                                  forward_chaining:
                                                                                                                                                  • unroll
                                                                                                                                                    expr:
                                                                                                                                                    (|count.list_3309/server| orders_3294/server)
                                                                                                                                                    expansions:
                                                                                                                                                    • unroll
                                                                                                                                                      expr:
                                                                                                                                                      (|count.list_3309/server| (|get.::.1_3290/server| orders_3294/server))
                                                                                                                                                      expansions:
                                                                                                                                                      • unroll
                                                                                                                                                        expr:
                                                                                                                                                        (|Ordinal.<<_129/client|
                                                                                                                                                          (|Ordinal.Int_114/client|
                                                                                                                                                            (|count.list_3309/server| (|get.::.1_3290/s…
                                                                                                                                                        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.013s
                                                                                                                                                        details:
                                                                                                                                                        Expand
                                                                                                                                                        smt_stats:
                                                                                                                                                        num checks:8
                                                                                                                                                        arith assert lower:52
                                                                                                                                                        arith tableau max rows:20
                                                                                                                                                        arith tableau max columns:48
                                                                                                                                                        arith pivots:43
                                                                                                                                                        rlimit count:31392
                                                                                                                                                        mk clause:65
                                                                                                                                                        datatype occurs check:56
                                                                                                                                                        mk bool var:257
                                                                                                                                                        arith assert upper:27
                                                                                                                                                        datatype splits:35
                                                                                                                                                        decisions:65
                                                                                                                                                        arith row summations:37
                                                                                                                                                        propagations:59
                                                                                                                                                        conflicts:10
                                                                                                                                                        arith fixed eqs:25
                                                                                                                                                        datatype accessor ax:30
                                                                                                                                                        arith conflicts:2
                                                                                                                                                        arith num rows:20
                                                                                                                                                        datatype constructor ax:63
                                                                                                                                                        num allocs:1196620948
                                                                                                                                                        final checks:6
                                                                                                                                                        added eqs:295
                                                                                                                                                        del clause:36
                                                                                                                                                        arith eq adapter:28
                                                                                                                                                        memory:7.850000
                                                                                                                                                        max memory:8.270000
                                                                                                                                                        Expand
                                                                                                                                                        • start[0.013s]
                                                                                                                                                            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 : 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) = (Option.get li).li_price in
                                                                                                                                                          (Ordinal.( << ) (Ordinal.Int _x_1) (Ordinal.Int _x_2)
                                                                                                                                                           || not (_x_3 = (List.hd _x_0).o_price && _x_0 <> []))
                                                                                                                                                          || not
                                                                                                                                                             ((((_x_3 = (List.hd orders).o_price && not Is_a(None, li)) && orders <> [])
                                                                                                                                                               && _x_2 >= 0)
                                                                                                                                                              && _x_1 >= 0)
                                                                                                                                                          expansions:
                                                                                                                                                          []
                                                                                                                                                          rewrite_steps:
                                                                                                                                                            forward_chaining:
                                                                                                                                                            • unroll
                                                                                                                                                              expr:
                                                                                                                                                              (|count.list_3309/server| orders_3294/server)
                                                                                                                                                              expansions:
                                                                                                                                                              • unroll
                                                                                                                                                                expr:
                                                                                                                                                                (|count.list_3309/server| (|get.::.1_3290/server| orders_3294/server))
                                                                                                                                                                expansions:
                                                                                                                                                                • unroll
                                                                                                                                                                  expr:
                                                                                                                                                                  (|Ordinal.<<_129/client|
                                                                                                                                                                    (|Ordinal.Int_114/client|
                                                                                                                                                                      (|count.list_3309/server| (|get.::.1_3290/s…
                                                                                                                                                                  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:2
                                                                                                                                                                  definitions:0
                                                                                                                                                                  inductions:0
                                                                                                                                                                  search_time:
                                                                                                                                                                  0.010s
                                                                                                                                                                  details:
                                                                                                                                                                  Expand
                                                                                                                                                                  smt_stats:
                                                                                                                                                                  num checks:6
                                                                                                                                                                  arith assert lower:20
                                                                                                                                                                  arith tableau max rows:9
                                                                                                                                                                  arith tableau max columns:26
                                                                                                                                                                  arith pivots:18
                                                                                                                                                                  rlimit count:45771
                                                                                                                                                                  mk clause:44
                                                                                                                                                                  datatype occurs check:24
                                                                                                                                                                  mk bool var:186
                                                                                                                                                                  arith assert upper:18
                                                                                                                                                                  datatype splits:34
                                                                                                                                                                  decisions:32
                                                                                                                                                                  arith row summations:40
                                                                                                                                                                  arith bound prop:1
                                                                                                                                                                  propagations:34
                                                                                                                                                                  conflicts:9
                                                                                                                                                                  arith fixed eqs:6
                                                                                                                                                                  datatype accessor ax:27
                                                                                                                                                                  arith conflicts:2
                                                                                                                                                                  arith num rows:9
                                                                                                                                                                  arith assert diseq:1
                                                                                                                                                                  datatype constructor ax:45
                                                                                                                                                                  num allocs:1404701484
                                                                                                                                                                  final checks:4
                                                                                                                                                                  added eqs:205
                                                                                                                                                                  del clause:18
                                                                                                                                                                  arith eq adapter:15
                                                                                                                                                                  memory:7.790000
                                                                                                                                                                  max memory:8.270000
                                                                                                                                                                  Expand
                                                                                                                                                                  • start[0.010s]
                                                                                                                                                                      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 : 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)
                                                                                                                                                                    expansions:
                                                                                                                                                                    []
                                                                                                                                                                    rewrite_steps:
                                                                                                                                                                      forward_chaining:
                                                                                                                                                                      • unroll
                                                                                                                                                                        expr:
                                                                                                                                                                        (|Ordinal.<<_129/client|
                                                                                                                                                                          (|Ordinal.Int_114/client|
                                                                                                                                                                            (|count.list_3309/server| (|get.::.1_3290/s…
                                                                                                                                                                        expansions:
                                                                                                                                                                        • unroll
                                                                                                                                                                          expr:
                                                                                                                                                                          (|count.list_3309/server| orders_3393/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:2
                                                                                                                                                                          definitions:0
                                                                                                                                                                          inductions:0
                                                                                                                                                                          search_time:
                                                                                                                                                                          0.012s
                                                                                                                                                                          details:
                                                                                                                                                                          Expand
                                                                                                                                                                          smt_stats:
                                                                                                                                                                          num checks:6
                                                                                                                                                                          arith assert lower:22
                                                                                                                                                                          arith tableau max rows:10
                                                                                                                                                                          arith tableau max columns:27
                                                                                                                                                                          arith pivots:19
                                                                                                                                                                          rlimit count:41428
                                                                                                                                                                          mk clause:44
                                                                                                                                                                          datatype occurs check:22
                                                                                                                                                                          mk bool var:193
                                                                                                                                                                          arith assert upper:17
                                                                                                                                                                          datatype splits:34
                                                                                                                                                                          decisions:36
                                                                                                                                                                          arith row summations:42
                                                                                                                                                                          arith bound prop:1
                                                                                                                                                                          propagations:37
                                                                                                                                                                          conflicts:9
                                                                                                                                                                          arith fixed eqs:7
                                                                                                                                                                          datatype accessor ax:29
                                                                                                                                                                          arith conflicts:2
                                                                                                                                                                          arith num rows:10
                                                                                                                                                                          arith assert diseq:2
                                                                                                                                                                          datatype constructor ax:48
                                                                                                                                                                          num allocs:1333718077
                                                                                                                                                                          final checks:4
                                                                                                                                                                          added eqs:218
                                                                                                                                                                          del clause:18
                                                                                                                                                                          arith eq adapter:16
                                                                                                                                                                          memory:7.700000
                                                                                                                                                                          max memory:8.270000
                                                                                                                                                                          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
                                                                                                                                                                              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.<<_129/client|
                                                                                                                                                                                  (|Ordinal.Int_114/client|
                                                                                                                                                                                    (|count.list_3309/server| (|get.::.1_3290/s…
                                                                                                                                                                                expansions:
                                                                                                                                                                                • unroll
                                                                                                                                                                                  expr:
                                                                                                                                                                                  (|count.list_3309/server| orders_3393/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>