blog-static/code/dawn/DawnEval.v

Require Import Coq.Lists.List.
Require Import DawnV2.
Require Import Coq.Program.Equality.
From Ltac2 Require Import Ltac2.

Inductive step_result :=
  | err
  | middle (e : expr) (s : value_stack)
  | final (s : value_stack).

Fixpoint eval_step (s : value_stack) (e : expr) : step_result :=
  match e, s with
  | e_int swap, v' :: v :: vs => final (v :: v' :: vs)
  | e_int clone, v :: vs => final (v :: v :: vs)
  | e_int drop, v :: vs => final vs
  | e_int quote, v :: vs => final (v_quote (value_to_expr v) :: vs)
  | e_int compose, (v_quote v2) :: (v_quote v1) :: vs => final (v_quote (e_comp v1 v2) :: vs)
  | e_int apply, (v_quote v1) :: vs => middle v1 vs
  | e_quote e', vs => final (v_quote e' :: vs)
  | e_comp e1 e2, vs =>
      match eval_step vs e1 with
      | final vs' => middle e2 vs'
      | middle e1' vs' => middle (e_comp e1' e2) vs'
      | err => err
      end
  | _, _ => err
  end.

Theorem eval_step_correct : forall (e : expr) (vs vs' : value_stack), Sem_expr vs e vs' ->
  (eval_step vs e = final vs') \/
  (exists (ei : expr) (vsi : value_stack),
    eval_step vs e = middle ei vsi /\
    Sem_expr vsi ei vs').
Proof.
  intros e vs vs' Hsem.
  (* Proceed by induction on the semantics. *)
  induction Hsem.
  - inversion H; (* The expression is just an intrnsic. *)
    (* Dismiss all the straightforward "final" cases,
       of which most intrinsics are. *)
    try (left; reflexivity).
    (* Only apply remains; We are in an intermediate / middle case. *)
    right.
    (* The semantics guarantee that the expression in the
       quote evaluates to the final state. *)
    exists e, vs0. auto.
  - (* The expression is a quote. This is yet another final case. *)
    left; reflexivity.
  - (* The composition is never a final step, since we have to evaluate both
       branches to "finish up". *)
    destruct IHHsem1; right.
    + (* If the left branch finihed, only the right branch needs to be evaluted. *)
      simpl. rewrite H. exists e2, vs2. auto.
    + (* Otherwise, the left branch has an intermediate evaluation, guaranteed
         by induction to be consitent. *)
      destruct H as [ei [vsi [Heval Hsem']]].
      (* We compose the remaining part of the left branch with the right branch. *)
      exists (e_comp ei e2), vsi. simpl.
      (* The evaluation is trivially to a "middle" state. *)
      rewrite Heval. split. auto.
      eapply Sem_e_comp. apply Hsem'. apply Hsem2.
Qed.

Inductive eval_chain (vs : value_stack) (e : expr) (vs' : value_stack) : Prop :=
  | chain_final (P : eval_step vs e = final vs')
  | chain_middle (ei : expr) (vsi : value_stack)
      (P : eval_step vs e = middle ei vsi) (rest : eval_chain vsi ei vs').

Lemma eval_chain_merge : forall (e1 e2 : expr) (vs vs' vs'' : value_stack),
  eval_chain vs e1 vs' -> eval_chain vs' e2 vs'' -> eval_chain vs (e_comp e1 e2) vs''.
Proof.
  intros e1 e2 vs vs' vs'' ch1 ch2.
  induction ch1;
  eapply chain_middle; simpl; try (rewrite P); auto.
Qed.

Lemma eval_chain_split : forall (e1 e2 : expr) (vs vs'' : value_stack),
  eval_chain vs (e_comp e1 e2) vs'' -> exists vs', (eval_chain vs e1 vs') /\ (eval_chain vs' e2 vs'').
Proof.
  intros e1 e2 vs vss'' ch.
  ltac1:(dependent induction ch).
  - simpl in P. destruct (eval_step vs e1); inversion P.
  - simpl in P. destruct (eval_step vs e1) eqn:Hval; try (inversion P).
    + injection P as Hinj; subst. specialize (IHch e e2 H0) as [s'0 [ch1 ch2]].
      eexists. split.
      * eapply chain_middle. apply Hval. apply ch1.
      * apply ch2.
    + subst. eexists. split.
      * eapply chain_final. apply Hval.
      * apply ch.
Qed.

Theorem val_step_sem : forall (e : expr) (vs vs' : value_stack),
  Sem_expr vs e vs' -> eval_chain vs e vs'
with eval_step_int : forall (i : intrinsic) (vs vs' : value_stack),
  Sem_int vs i vs' -> eval_chain vs (e_int i) vs'.
Proof.
  - intros e vs vs' Hsem.
    induction Hsem.
    + (* This is an intrinsic, which is handled by the second
         theorem, eval_step_int. This lemma is used here. *)
      auto.
    + (* A quote doesn't have a next step, and so is final. *)
      apply chain_final. auto.
    + (* In composition, by induction, we know that the two sub-expressions produce
         proper evaluation chains. Chains can be composed (via eval_chain_merge). *)
      eapply eval_chain_merge; eauto.
  - intros i vs vs' Hsem.
    (* The evaluation chain depends on the specific intrinsic in use. *)
    inversion Hsem; subst;
    (* Most intrinsics produce a final value, and the evaluation chain is trivial. *)
    try (apply chain_final; auto; fail).
    (* Only apply is non-final. The first step is popping the quote from the stack,
       and the rest of the steps are given by the evaluation of the code in the quote. *)
    apply chain_middle with e vs0; auto.
Qed.

Ltac2 Type exn ::= [ | Not_intrinsic ].

Ltac2 rec destruct_n (n : int) (vs : constr) : unit :=
  if Int.le n 0 then () else
    let v := Fresh.in_goal @v in
    let vs' := Fresh.in_goal @vs in
    destruct $vs as [|$v $vs']; Control.enter (fun () =>
      try (destruct_n (Int.sub n 1) (Control.hyp vs'))
    ).

Ltac2 int_arity (int : constr) : int :=
  match! int with
  | swap => 2
  | clone => 1
  | drop => 1
  | quote => 1
  | compose => 2
  | apply => 1
  | _ => Control.throw Not_intrinsic
  end.

Ltac2 destruct_int_stack (int : constr) (va: constr) := destruct_n (int_arity int) va.

Ltac2 ensure_valid_stack () := Control.enter (fun () =>
  match! goal with
  | [h : eval_step ?a (e_int ?b) = ?c |- _] =>
      let h := Control.hyp h in
      destruct_int_stack b a;
      try (inversion $h; fail)
  | [|- _ ] => ()
  end).

Theorem test : forall (vs vs': value_stack), eval_step vs (e_int swap) = final vs' ->
  exists v1 v2 vs'', vs = v1 :: v2 :: vs'' /\ vs' = v2 :: v1 :: vs''.
Proof.
  intros s s' Heq.
  ensure_valid_stack ().
  simpl in Heq. injection Heq as Hinj. subst. eauto.
Qed.

Theorem eval_step_final_sem : forall (e : expr) (vs vs' : value_stack),
  eval_step vs e = final vs' -> Sem_expr vs e vs'.
Proof.
  intros e vs vs' Hev. destruct e.
  - destruct i; ensure_valid_stack ();
    (* Get rid of trivial cases that match one-to-one. *)
    simpl in Hev; try (injection Hev as Hinj; subst; solve_basic ()).
    + (* compose with one quoted value is not final, but an error. *)
      destruct v. inversion Hev.
    + (* compose with two quoted values. *)
      destruct v; destruct v0.
      injection Hev as Hinj; subst; solve_basic ().
    + (* Apply is not final. *) destruct v. inversion Hev.
  - (* Quote is always final, trivially, and the semantics match easily. *)
    simpl in Hev. injection Hev as Hinj; subst. solve_basic ().
  - (* Compose is never final, so we don't need to handle it here. *)
    simpl in Hev. destruct (eval_step vs e1); inversion Hev.
Qed.

Theorem eval_step_middle_sem : forall (e ei: expr) (vs vsi vs' : value_stack),
  eval_step vs e = middle ei vsi ->
  Sem_expr vsi ei vs' ->
  Sem_expr vs e vs'.
Proof.
  intros e. induction e; intros ei vs vsi vs' Hev Hsem.
  - destruct i; ensure_valid_stack ().
    + (* compose with one quoted value; invalid. *)
      destruct v. inversion Hev.
    + (* compose with two quoted values; not a middle step. *)
      destruct v; destruct v0. inversion Hev.
    + (* Apply *)
      destruct v. injection Hev as Hinj; subst.
      solve_basic (). auto.
  - (* quoting an expression is not middle. *)
    inversion Hev.
  - simpl in Hev.
    destruct (eval_step vs e1) eqn:Hev1.
    + (* Step led to an error, which can't happen in a chain. *)
      inversion Hev.
    + (* Left expression makes a non-final step. Milk this for equalities first. *)
      injection Hev as Hinj; subst.
      (* The rest of the program (e_comp e e2) evaluates using our semantics,
         which means that both e and e2 evaluate using our semantics. *)
      inversion Hsem; subst.
      (* By induction, e1 evaluates using our semantics if e does, which we just confirmed. *)
      specialize (IHe1 e vs vsi vs2 Hev1 H2).
      (* The composition rule can now be applied. *)
      eapply Sem_e_comp; eauto.
    + (* Left expression makes a final step. Milk this for equalities first. *)
      injection Hev as Hinj; subst.
      (* Using eval_step_final, we know that e1 evaluates to the intermediate
         state given our semantics. *)
      specialize (eval_step_final_sem e1 vs vsi Hev1) as Hsem1.
      (* The composition rule can now be applied. *)
      eapply Sem_e_comp; eauto.
Qed.

Theorem eval_step_sem_back : forall (e : expr) (vs vs' : value_stack),
  eval_chain vs e vs' -> Sem_expr vs e vs'.
Proof.
  intros e vs vs' ch.
  ltac1:(dependent induction ch).
  - apply eval_step_final_sem. auto.
  - specialize (eval_step_middle_sem e ei vs vsi vs' P IHch). auto.
Qed.

Corollary eval_step_no_sem : forall (e : expr) (vs vs' : value_stack),
  ~(Sem_expr vs e vs') -> ~(eval_chain vs e vs').
Proof.
  intros e vs vs' Hnsem Hch.
  specialize (eval_step_sem_back _ _ _ Hch). auto.
Qed.

Require Extraction.
Require Import ExtrHaskellBasic.
Extraction Language Haskell.
Set Extraction KeepSingleton.
Extraction "UccGen.hs" expr eval_step true false or.

Remark eval_swap_two_values : forall (vs vs' : value_stack),
  eval_step vs (e_int swap) = final vs' -> exists v1 v2 vst, vs = v1 :: v2 :: vst /\ vs' = v2 :: v1 :: vst.
Proof.
  intros vs vs' Hev.
  (* Can't proceed until we know more about the stack. *)
  destruct vs as [|v1 [|v2 vs]].
  - (* Invalid case; empty stack. *) inversion Hev.
  - (* Invalid case; stack only has one value. *) inversion Hev.
  - (* Valid case: the stack has two values. *) injection Hev. eauto.
Qed.

Remark eval_swap_two_values' : forall (vs vs' : value_stack),
  eval_step vs (e_int swap) = final vs' -> exists v1 v2 vst, vs = v1 :: v2 :: vst /\ vs' = v2 :: v1 :: vst.
Proof.
  intros vs vs' Hev.
  ensure_valid_stack ().
  injection Hev. eauto.
Qed.