Library models.DCPOSL

Require Import LogicalRelations.
Require Import OptionRel.
Require Import Category.
Require Import ConcreteCategory.
Require Import Functor.
Require Import DCPO.
Require Import EffectSignatures.

Require Import PropExtensionality.
Require Import FunctionalExtensionality.
Require Import Classical.

Free dcpo-semilattice generated by a set

A dcpo-semilattice is a set equipped independently with both the structure of a dcpo and that of a semilattice. Structures of this kind are mentioned for example in §6.2 of Abramsky and Jung's domain theory textbook, which discusses various forms of powerdomains.

For our purposes, the specific structures we combine are:

pointed dcpos and strict Scott-continuous functions between them, representing spaces of potentially non-terminating computations, and
complete (semi)lattices and sup-preserving functions, representing computation spaces featuring undefined behaviors and angelic choices.

Note that both structures involve a partial order, least element and supremum operations. In fact, every complete lattice is a dcpo, and every sup-preserving function is strict Scott-continuous. However, a dcpo-semilattice provides two distinct partial orderings of its carrier set, which may or may not have anything to do with each other.

In this file, we construct the free dcpo-semilattice generated by a given set.

Free dcpo

Before we construct the free dcpo-semilattice, we start with the free dcpo generated by a set, a standard construction which essentially consists of the discrete order extended with a bottom element. For our purposes, we will call the elements of the free dcpo "outcomes", which can either be values from the generating set or bottom element meant to denote divergence.

Variant outcome {A} := val (a : A) | div.
Arguments outcome : clear implicits.

The information ordering on outcomes allows div to be replaced by a terminating outcome.

Variant outcome_le {A} : relation (outcome A) :=
  | val_le a : outcome_le (val a) (val a)
  | div_le x : outcome_le div x.

Global Instance outcome_le_preo A :
  PreOrder (@outcome_le A).

Global Instance outcome_le_antisym A :
  Antisymmetric (outcome A) eq outcome_le.

Classically speaking, the order defined above is also a dcpo: any directed set will contain at most one of the generators, in which case it will be the supremum. If there is no generator in the set then the supremum must be div. However, it is not possible to provide a dsup operator as defined in the DCPO library without the use of classical axioms, as we would need the generator membership condition to be decidable for a set given in outcome A → Prop. Since we only use the construction above as a building block, this is not an issue.

Free semilattice

On the other side of things, the free sup-lattice generated by a set is simply its powerset, ordered under inclusion, where suprema are given by set unions. We may want to refactor the code to make this explicit somewhere, though this construction is a special case of the downset completion mechanized in lattices/Downset.v.

Free dcpo-semilattice

Per Abramsky and Jung, a dcpo-semilattice is a dcpo which provides the join operation of a semilattice. As a dcpo operator, the join must preserve directed sups in each argument. In the infinitary case of the sup-lattices we are considering, this manifests as the distributivity property

⋃i∈I · ⋁j∈Jᵢ · xi,j = ⋁f∈(∏i·Jᵢ) · ⋃i∈I · xi,f(i)

where ⋃ denotes the join operation associated with the sup-lattice and ⋁ is the directed-sup operation (the least element can be seen as the empty sup) associated with the dcpo structure. Maps between dcpo-semilattices must respect both structures and be at the time strict Scott-continuous with regards to the dcpo and sup-preserving with regards the semilattice ordering.

Module FDSL.

Carrier set

The free dcpo-semilattice can be defined using sets of outcomes. The associated sup-lattice structure is induced by the set inclusion ordering, where suprema are given by set union.

Definition omap A :=
outcome A → Prop.

By contrast, the directed-complete structure is more subtle. The least element is the singleton {div}. As the computation progresses, any div outcome in the set can be replaced by a new set of outcomes. This new set of outcomes can be empty, and could itself include div if some of the computation's nondeterministic are still running. However, once div has been dropped from the set, the computation is fully terminated and can no longer be modified by further execution.

Section DCPO.
Context (A : Type).

The order described above can be defined as follows.

    Record le (x y : omap A) :=
      {
        le_fw a : x (val a) → y (val a);
        le_bw σ : y σ → x div ∨ x σ;
      }.

    Lemma le_div (x y : omap A) :
      le x y → y div → x div.

    Global Instance le_preo :
      PreOrder le.

    Global Instance le_antisym :
      Antisymmetric _ eq le.

Under that ordering, fully terminating computations are the maximal elements. Two computations will have an upper bound when it is possible to extend them so that they produce the same set of outcomes. Sups for sets of computations which are compatible in this way can be defined as follows.

    Section DSUP.
      Context (D : omap A → Prop) `{HD : !Directed D}.

      Definition dsup : omap A :=
        fun σ ⇒
          match σ with
            | val a ⇒ ∃ x , D x ∧ x (val a)
            | div ⇒ ∀ x, D x → x div
          end.

      Lemma directed_val x y a :
        D x → D y → x (val a) → y div ∨ y (val a).

      Lemma dsup_has_all σ :
        dsup σ → ∀ x, D x → x div ∨ x σ.

      Global Instance lsup_spec :
        IsSup D dsup.
    End DSUP.

    Global Instance le_dc : DirectedComplete (omap A) :=
      {
        dc_po := {| models.DCPO.le := le |};
        dsup D _ := dsup D;
      }.
  End DCPO.

Monad operations

TODO: we could have a proper definition of the ConcreteCategory of dcpo-semilattice and their homomorphisms and prove the full adjunction property, but for now we can start with the induced monad.

  Variant ret {A} (a : A) : omap A :=
    | ret_intro : ret a (val a).

  Variant bind {A B} (f : A → omap B) (x : omap A) : omap B :=
    | bind_div : x div → bind f x div
    | bind_val a σ : x (val a) → f a σ → bind f x σ.

  Lemma bind_ret_l {A} (x : omap A) :
    bind (@ret A) x = x.

  Lemma bind_ret_r {A B} (f : A → omap B) (a : A) :
    bind f (ret a) = f a.

  Lemma bind_bind {A B C} (g : B → omap C) (f : A → omap B) (x : omap A) :
    bind g (bind f x) = bind (fun a ⇒ bind g (f a)) x.

End FDSL.