package dolmen

  1. Overview
  2. Docs

Module Dolmen_std.BuiltinSource

This module defines the builtins that are defined by Dolmen.

Builtins are particularly used in typed expressions see Dolmen.Std.Expr, in order to give more information about constants which have builtin semantics.

Users are encouraged to match builtins rather than specific symbols when inspecting typed expressions, as this basically allows to match on the semantics of an identifier rather than matching on the syntaxic value of an identifier. For instance, equality can take an arbitrary number of arguments, and thus in order to have well-typed terms, each arity of equality gives rise to a different symbol (because the symbol's type depends on the arity desired), but all these symbols have the Equal builtin.

In the following we will use pseudo-code to describe the arity and actual type associated to builtins. These will follow ocaml's notation for types with an additional syntax using dots for arbitrary arity. Some examples:

  • ttype is a type constant
  • ttype -> ttype is a type constructor (e.g. list)
  • int is a constant of type int
  • float -> int is a unary function
  • 'a. 'a -> 'a is a polymorphic unary function
  • 'a. 'a -> ... -> Prop.T describes a family of functions that take a type and then an arbitrary number of arguments of that type, and return a proposition (this is for instance the type of equality).

Additionally, due to some languages having overloaded operators, and in order to not have too verbose names, some of these builtins may have overloaded signtures, such as comparisons on numbers which can operate on integers, rationals, or reals. Note that arbitrary arity operators (well family of operators) can be also be seen as overloaded operators. Overloaded types (particularly for numbers) are written:

  • {a=(Int|Rational|Real)} a -> a -> Prop.T, where the notable difference with polymorphic functions is that functions of this type does not take a type argument.

Type definition

Sourcetype 'a t = 'a Dolmen_intf.Builtin.t = .. constraint 'a = < .. >

Base Builtins

Sourcetype t +=
  1. | Base
    (*

    The base builtin; it is the default builtin for identifiers.

    *)
Sourcetype t +=
  1. | Wildcard : {
    1. ty : 'ty option ref;
    } -> < ty : 'ty.. > t
    (*

    Wildcards, currently used internally to represent implicit type variables during type-checking.

    *)
Sourcetype t +=
  1. | Kind
    (*

    Used for the type of Type. It is an error to try and access the type of kind.

    *)
  2. | Type
    (*

    Builtin used to represent the type of types.

    *)
Sourcetype t +=
  1. | Unit
    (*

    The unit type, which has only one element (named void).

    *)
  2. | Univ
    (*

    Univ: ttype: a builtin type constant used for languages with a default type for elements (such as tptp's `$i`).

    *)
Sourcetype t +=
  1. | Equal
    (*

    Equal: 'a. 'a -> ... -> Prop.T: equality beetween values.

    *)
  2. | Distinct
    (*

    Distinct: 'a. 'a -> ... -> Prop.T: pairwise dis-equality beetween arguments.

    *)
Sourcetype t +=
  1. | Coercion
    (*

    Coercion: 'a 'b. 'a -> 'b: Coercion/cast operator, i.e. allows to cast values of some type to another type. This is a polymorphic operator that takes two type arguments a and b, a value of type a, and returns a value of type b. The interpretation/semantics of this cast can remain up to the user. This operator is currently mainly used to cast numeric types when this transormation is exact (i.e. an integer casted into a rational, which is always possible and exact, or the cast of a rational into an integer, as long as the cast is guarded by a clause verifying the rational is an integer).

    *)
Sourcetype t +=
  1. | Multi_trigger
    (*

    Multi_trigger: 'a1 ... 'an. 'a1 -> ... -> 'an -> Prop.T: Create a multi trigger: it takes an arbitrarily long list of terms of arbitrary types.

    *)
  2. | Maps_to
    (*

    Maps_to: 'term_var -> 'term -> Prop.T: Used in semantic triggers for floating point arithmetic. See alt-ergo/src/preludes/fpa-theory-2017-01-04-16h00.ae.

    warning: It is an Alt-Ergo semantic trigger that should only be allowed inside theories.

    *)
  3. | Semantic_trigger
    (*

    Semantic_trigger: Prop.T -> Prop.T: Denote that its argument is a semantic trigger (used only by Alt-ergo currently).

    *)
Sourcetype t +=
  1. | Pi
    (*

    Pi: 'a. ('a -> Prop.T) -> Prop.T: higher-order encoding of universal quantification.

    *)
  2. | Sigma
    (*

    Sigma: 'a. ('a -> Prop.T) -> Prop.T: higher-order encoding of existencial quantification.

    *)

Boolean Builtins

Sourcemodule Prop : sig ... end
Sourcetype t +=
  1. | Prop of 'a Prop.t
    (*

    Boolean builtins.

    *)

Algebraic datatype Builtins

Sourcemodule Adt : sig ... end
Sourcetype t +=
  1. | Adt of 'a Adt.t
    (*

    Alegbraic datatype builtins.

    *)

HOL encoding Builtins

Sourcemodule Map : sig ... end
Sourcetype t +=
  1. | Map of 'a Map.t
    (*

    Map/Higher-order encoding builtins.

    *)

Arithmetic Builtins

Sourcemodule Arith : sig ... end
Sourcetype t +=
  1. | Arith of 'a Arith.t
    (*

    Arithmetic builtins.

    *)

Arrays Builtins

Sourcemodule Array : sig ... end
Sourcetype t +=
  1. | Array of 'a Array.t
    (*

    Array builtins.

    *)

Bitvectors Builtins

Sourcemodule Bitv : sig ... end
Sourcetype t +=
  1. | Bitv of 'a Bitv.t
    (*

    Bitvectors builtins

    *)

Floats Builtins

Sourcemodule Float : sig ... end
Sourcetype t +=
  1. | Float of 'a Float.t

String and Regexp Builtins

Sourcemodule Str : sig ... end
Sourcetype t +=
  1. | Str of 'a Str.t
    (*

    String builtins

    *)
  2. | Regexp of 'a Str.RegLan.t
    (*

    String Regular language builtins, aka regexps.

    *)