Module Core.BlangSource

Boolean expressions.

A blang is a boolean expression built up by applying the usual boolean operations to properties that evaluate to true or false in some context.

Usage

For example, imagine writing a config file for an application that filters a stream of integers. Your goal is to keep only those integers that are multiples of either -3 or 5. Using Blang for this task, the code might look like:

  module Property = struct
    type t =
      | Multiple_of of int
      | Positive
      | Negative
    [@@deriving sexp]

    let eval t num =
      match t with
      | Multiple_of n -> num % n = 0
      | Positive      -> num > 0
      | Negative      -> num < 0
  end

  type config = {
    keep : Property.t Blang.t;
  } [@@deriving sexp]

  let config = {
    keep =
      Blang.t_of_sexp
        Property.t_of_sexp
        (Sexp.of_string
           "(or (and negative (multiple_of 3)) (and positive (multiple_of 5)))";
  }

  let keep config num : bool =
    Blang.eval config.keep (fun p -> Property.eval p num)

Note how positive and negative and multiple_of become operators in a small, newly-defined boolean expression language that allows you to write statements like (and negative (multiple_of 3)).

Blang sexp syntax

The blang sexp syntax is almost exactly the derived one, except that:

1. Base properties are not marked explicitly. Thus, if your base property type has elements FOO, BAR, etc., then you could write the following Blang s-expressions:

    FOO
    (and FOO BAR)
    (if FOO BAR BAZ)

and so on. Note that this gets in the way of using the blang "keywords" in your value language.

2. And and Or take a variable number of arguments, so that one can (and probably should) write

(and FOO BAR BAZ QUX)

instead of

(and FOO (and BAR (and BAZ QUX)))

If you want to see the derived sexp, use Raw.sexp_of_t.

Sourcetype +'a t = private
  1. | True
  2. | False
  3. | And of 'a t * 'a t
  4. | Or of 'a t * 'a t
  5. | Not of 'a t
  6. | If of 'a t * 'a t * 'a t
  7. | Base of 'a

Note that the sexps are not directly inferred from the type below -- there are lots of fancy shortcuts. Also, the sexps for 'a must not look anything like blang sexps. Otherwise t_of_sexp will fail. The directly inferred sexps are available via Raw.sexp_of_t.

include Bin_prot.Binable.S_local1 with type +'a t := 'a t
include Bin_prot.Binable.S1 with type +'a t := 'a t
Sourceval bin_size_t : ('a, 'a t) Bin_prot.Size.sizer1
Sourceval bin_write_t : ('a, 'a t) Bin_prot.Write.writer1
Sourceval bin_read_t : ('a, 'a t) Bin_prot.Read.reader1
Sourceval __bin_read_t__ : ('a, int -> 'a t) Bin_prot.Read.reader1
Sourceval bin_writer_t : ('a, 'a t) Bin_prot.Type_class.S1.writer
Sourceval bin_reader_t : ('a, 'a t) Bin_prot.Type_class.S1.reader
Sourceval bin_t : ('a, 'a t) Bin_prot.Type_class.S1.t
Sourceval bin_size_t__local : ('a, 'a t) Bin_prot.Size.sizer_local1
Sourceval bin_write_t__local : ('a, 'a t) Bin_prot.Write.writer_local1
include Ppx_compare_lib.Comparable.S1 with type +'a t := 'a t
Sourceval compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
include Ppx_compare_lib.Equal.S1 with type +'a t := 'a t
Sourceval equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
include Ppx_hash_lib.Hashable.S1 with type +'a t := 'a t
Sourceval hash_fold_t : (Base.Hash.state -> 'a -> Base.Hash.state) -> Base.Hash.state -> 'a t -> Base.Hash.state
include Sexplib0.Sexpable.S1 with type +'a t := 'a t
Sourceval t_of_sexp : (Sexplib0.Sexp.t -> 'a) -> Sexplib0.Sexp.t -> 'a t
Sourceval sexp_of_t : ('a -> Sexplib0.Sexp.t) -> 'a t -> Sexplib0.Sexp.t
include Typerep_lib.Typerepable.S1 with type +'a t := 'a t
Sourcemodule Raw : sig ... end

Raw provides the automatically derived sexp_of_t, useful in debugging the actual structure of the blang.

Smart constructors that simplify away constants whenever possible

Sourcemodule type Constructors = sig ... end
include Constructors
Sourceval base : 'a -> 'a t
Sourceval true_ : _ t
Sourceval false_ : _ t
Sourceval constant : Base.Bool.t -> _ t

function true -> true_ | false -> false_

Sourceval not_ : 'a t -> 'a t
Sourceval and_ : 'a t Base.List.t -> 'a t

n-ary And

Sourceval or_ : 'a t Base.List.t -> 'a t

n-ary Or

Sourceval if_ : 'a t -> 'a t -> 'a t -> 'a t

if_ if then else

Sourcemodule O : sig ... end
Sourceval constant_value : 'a t -> Base.Bool.t Base.Option.t

constant_value t = Some b iff t = constant b

The following two functions are useful when one wants to pretend that 'a t has constructors And and Or of type 'a t list -> 'a t. The pattern of use is

  match t with
  | And (_, _) as t -> let ts = gather_conjuncts t in ...
  | Or (_, _) as t -> let ts = gather_disjuncts t in ...
  | ...

or, in case you also want to handle True (resp. False) as a special case of conjunction (disjunction)

  match t with
  | True | And (_, _) as t -> let ts = gather_conjuncts t in ...
  | False | Or (_, _) as t -> let ts = gather_disjuncts t in ...
  | ...
Sourceval gather_conjuncts : 'a t -> 'a t Base.List.t

gather_conjuncts t gathers up all toplevel conjuncts in t. For example,

  • gather_conjuncts (and_ ts) = ts
  • gather_conjuncts (And (t1, t2)) = gather_conjuncts t1 @ gather_conjuncts t2
  • gather_conjuncts True = []
  • gather_conjuncts t = [t] when t matches neither And (_, _) nor True
Sourceval gather_disjuncts : 'a t -> 'a t Base.List.t

gather_disjuncts t gathers up all toplevel disjuncts in t. For example,

  • gather_disjuncts (or_ ts) = ts
  • gather_disjuncts (Or (t1, t2)) = gather_disjuncts t1 @ gather_disjuncts t2
  • gather_disjuncts False = []
  • gather_disjuncts t = [t] when t matches neither Or (_, _) nor False
include Container.S1 with type 'a t := 'a t
Sourceval mem : 'a t -> 'a -> equal:('a -> 'a -> bool) -> bool

Checks whether the provided element is there, using equal.

Sourceval length : 'a t -> int
Sourceval is_empty : 'a t -> bool
Sourceval iter : 'a t -> f:('a -> unit) -> unit
Sourceval fold : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc

fold t ~init ~f returns f (... f (f (f init e1) e2) e3 ...) en, where e1..en are the elements of t

Sourceval fold_result : 'a t -> init:'acc -> f:('acc -> 'a -> ('acc, 'e) Base.Result.t) -> ('acc, 'e) Base.Result.t

fold_result t ~init ~f is a short-circuiting version of fold that runs in the Result monad. If f returns an Error _, that value is returned without any additional invocations of f.

Sourceval fold_until : 'a t -> init:'acc -> f:('acc -> 'a -> ('acc, 'final) Base.Container.Continue_or_stop.t) -> finish:('acc -> 'final) -> 'final

fold_until t ~init ~f ~finish is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed. If f never returns Stop _, the final result is computed by finish.

Example:

  type maybe_negative =
    | Found_negative of int
    | All_nonnegative of { sum : int }

  (** [first_neg_or_sum list] returns the first negative number in [list], if any,
      otherwise returns the sum of the list. *)
  let first_neg_or_sum =
    List.fold_until ~init:0
      ~f:(fun sum x ->
        if x < 0
        then Stop (Found_negative x)
        else Continue (sum + x))
      ~finish:(fun sum -> All_nonnegative { sum })
  ;;

  let x = first_neg_or_sum [1; 2; 3; 4; 5]
  val x : maybe_negative = All_nonnegative {sum = 15}

  let y = first_neg_or_sum [1; 2; -3; 4; 5]
  val y : maybe_negative = Found_negative -3
Sourceval exists : 'a t -> f:('a -> bool) -> bool

Returns true if and only if there exists an element for which the provided function evaluates to true. This is a short-circuiting operation.

Sourceval for_all : 'a t -> f:('a -> bool) -> bool

Returns true if and only if the provided function evaluates to true for all elements. This is a short-circuiting operation.

Sourceval count : 'a t -> f:('a -> bool) -> int

Returns the number of elements for which the provided function evaluates to true.

Returns the sum of f i for all i in the container.

Sourceval sum : (module Base.Container.Summable with type t = 'sum) -> 'a t -> f:('a -> 'sum) -> 'sum
Sourceval find : 'a t -> f:('a -> bool) -> 'a option

Returns as an option the first element for which f evaluates to true.

Sourceval find_map : 'a t -> f:('a -> 'b option) -> 'b option

Returns the first evaluation of f that returns Some, and returns None if there is no such element.

Sourceval to_list : 'a t -> 'a list
Sourceval to_array : 'a t -> 'a array
Sourceval min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option

Returns a minimum (resp maximum) element from the collection using the provided compare function, or None if the collection is empty. In case of a tie, the first element encountered while traversing the collection is returned. The implementation uses fold so it has the same complexity as fold.

Sourceval max_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
include Quickcheckable.S1 with type 'a t := 'a t

Blang.t sports a substitution monad:

  • return v is Base v (think of v as a variable)
  • bind t f replaces every Base v in t with f v (think of v as a variable and f as specifying the term to substitute for each variable)

Note: bind t f does short-circuiting, so f may not be called on every variable in t.

include Interfaces.Monad with type 'a t := 'a t
Sourceval (>>=) : 'a t -> ('a -> 'b t) -> 'b t

t >>= f returns a computation that sequences the computations represented by two monad elements. The resulting computation first does t to yield a value v, and then runs the computation returned by f v.

Sourceval (>>|) : 'a t -> ('a -> 'b) -> 'b t

t >>| f is t >>= (fun a -> return (f a)).

Sourcemodule Monad_infix : sig ... end
Sourceval bind : 'a t -> f:('a -> 'b t) -> 'b t

bind t ~f = t >>= f

Sourceval return : 'a -> 'a t

return v returns the (trivial) computation that returns v.

Sourceval map : 'a t -> f:('a -> 'b) -> 'b t

map t ~f is t >>| f.

Sourceval join : 'a t t -> 'a t

join t is t >>= (fun t' -> t').

Sourceval ignore_m : 'a t -> unit t

ignore_m t is map t ~f:(fun _ -> ()). ignore_m used to be called ignore, but we decided that was a bad name, because it shadowed the widely used Stdlib.ignore. Some monads still do let ignore = ignore_m for historical reasons.

Sourceval all : 'a t list -> 'a list t
Sourceval all_unit : unit t list -> unit t

Like all, but ensures that every monadic value in the list produces a unit value, all of which are discarded rather than being collected into a list.

Sourcemodule Let_syntax : sig ... end

These are convenient to have in scope when programming with a monad:

Sourceval values : 'a t -> 'a Base.List.t

values t forms the list containing every v for which Base v is a subexpression of t

Sourceval eval : 'a t -> ('a -> Base.Bool.t) -> Base.Bool.t

eval t f evaluates the proposition t relative to an environment f that assigns truth values to base propositions.

Sourceval eval_set : universe:('elt, 'comparator) Set.t Lazy.t -> ('a -> ('elt, 'comparator) Set.t) -> 'a t -> ('elt, 'comparator) Set.t

eval_set ~universe set_of_base expression returns the subset of elements e in universe that satisfy eval expression (fun base -> Set.mem (set_of_base base) e).

eval_set assumes, but does not verify, that set_of_base always returns a subset of universe. If this doesn't hold, then eval_set's result may contain elements not in universe.

And set1 set2 represents the elements that are both in set1 and set2, thus in the intersection of the two sets. Symmetrically, Or set1 set2 represents the union of set1 and set2.

Sourceval specialize : 'a t -> ('a -> [ `Known of Base.Bool.t | `Unknown ]) -> 'a t

specialize t f partially evaluates t according to a perhaps-incomplete assignment f of the values of base propositions. The following laws (at least partially) characterize its behavior.

  • specialize t (fun _ -> `Unknown) = t
  • specialize t (fun x -> `Known (f x)) = constant (eval t f)
  • List.for_all (values (specialize t g)) ~f:(fun x -> g x = `Unknown)
  • if
  List.for_all (values t) ~f:(fun x ->
    match g x with
    | `Known b -> b = f x
    | `Unknown -> true)
then
  eval t f = eval (specialize t g) f
Sourcemodule type Monadic = sig ... end
Sourcemodule For_monad (M : Base.Monad.S) : Monadic with module M := M

Generalizes some of the blang operations above to work in a monad.

Sourceval invariant : 'a t -> Base.Unit.t
Sourcemodule Stable : sig ... end