language.v 2.49 KB
Newer Older
1
From iris.algebra Require Export ofe.
2
Set Default Proof Using "Type".
Ralf Jung's avatar
Ralf Jung committed
3

4 5 6 7 8 9
Structure language := Language {
  expr : Type;
  val : Type;
  state : Type;
  of_val : val  expr;
  to_val : expr  option val;
10
  prim_step : expr  state  expr  state  list expr  Prop;
Robbert Krebbers's avatar
Robbert Krebbers committed
11 12
  to_of_val v : to_val (of_val v) = Some v;
  of_to_val e v : to_val e = Some v  of_val v = e;
13
  val_stuck e σ e' σ' efs : prim_step e σ e' σ' efs  to_val e = None
Ralf Jung's avatar
Ralf Jung committed
14
}.
Janno's avatar
Janno committed
15 16 17
Delimit Scope expr_scope with E.
Delimit Scope val_scope with V.
Bind Scope expr_scope with expr.
18
Bind Scope val_scope with val.
19 20 21 22 23
Arguments of_val {_} _.
Arguments to_val {_} _.
Arguments prim_step {_} _ _ _ _ _.
Arguments to_of_val {_} _.
Arguments of_to_val {_} _ _ _.
24
Arguments val_stuck {_} _ _ _ _ _ _.
25

26 27 28
Canonical Structure stateC Λ := leibnizC (state Λ).
Canonical Structure valC Λ := leibnizC (val Λ).
Canonical Structure exprC Λ := leibnizC (expr Λ).
29 30

Definition cfg (Λ : language) := (list (expr Λ) * state Λ)%type.
Ralf Jung's avatar
Ralf Jung committed
31

32
Section language.
33 34
  Context {Λ : language}.
  Implicit Types v : val Λ.
Ralf Jung's avatar
Ralf Jung committed
35

36
  Definition reducible (e : expr Λ) (σ : state Λ) :=
37
     e' σ' efs, prim_step e σ e' σ' efs.
38
  Definition irreducible (e : expr Λ) (σ : state Λ) :=
Robbert Krebbers's avatar
Robbert Krebbers committed
39
    e' σ' efs, ¬prim_step e σ e' σ' efs. 
40
  Definition atomic (e : expr Λ) : Prop :=
41
     σ e' σ' efs, prim_step e σ e' σ' efs  irreducible e' σ'.
42
  Inductive step (ρ1 ρ2 : cfg Λ) : Prop :=
43
    | step_atomic e1 σ1 e2 σ2 efs t1 t2 :
44
       ρ1 = (t1 ++ e1 :: t2, σ1) 
45 46
       ρ2 = (t1 ++ e2 :: t2 ++ efs, σ2) 
       prim_step e1 σ1 e2 σ2 efs 
47 48
       step ρ1 ρ2.

Robbert Krebbers's avatar
Robbert Krebbers committed
49 50
  Lemma of_to_val_flip v e : of_val v = e  to_val e = Some v.
  Proof. intros <-. by rewrite to_of_val. Qed.
51
  Lemma reducible_not_val e σ : reducible e σ  to_val e = None.
52
  Proof. intros (?&?&?&?); eauto using val_stuck. Qed.
53 54
  Lemma val_irreducible e σ : is_Some (to_val e)  irreducible e σ.
  Proof. intros [??] ??? ?%val_stuck. by destruct (to_val e). Qed.
55
  Global Instance of_val_inj : Inj (=) (=) (@of_val Λ).
56
  Proof. by intros v v' Hv; apply (inj Some); rewrite -!to_of_val Hv. Qed.
57
End language.
Ralf Jung's avatar
Ralf Jung committed
58

59 60 61
Class LanguageCtx (Λ : language) (K : expr Λ  expr Λ) := {
  fill_not_val e :
    to_val e = None  to_val (K e) = None;
62 63 64 65 66 67
  fill_step e1 σ1 e2 σ2 efs :
    prim_step e1 σ1 e2 σ2 efs 
    prim_step (K e1) σ1 (K e2) σ2 efs;
  fill_step_inv e1' σ1 e2 σ2 efs :
    to_val e1' = None  prim_step (K e1') σ1 e2 σ2 efs 
     e2', e2 = K e2'  prim_step e1' σ1 e2' σ2 efs
68
}.