src/HOL/IMP/Denotation.thy

proved termination for fun-based AI

(* Authors: Heiko Loetzbeyer, Robert Sandner, Tobias Nipkow *)

header "Denotational Semantics of Commands"

theory Denotation imports Big_Step begin

type_synonym com_den = "(state \<times> state) set"

definition
  Gamma :: "bexp \<Rightarrow> com_den \<Rightarrow> (com_den \<Rightarrow> com_den)" where
  "Gamma b cd = (\<lambda>phi. {(s,t). (s,t) \<in> (cd O phi) \<and> bval b s} \<union>
                       {(s,t). s=t \<and> \<not>bval b s})"

fun C :: "com \<Rightarrow> com_den" where
"C SKIP   = Id" |
"C (x ::= a) = {(s,t). t = s(x := aval a s)}" |
"C (c0;c1)   = C(c0) O C(c1)" |
"C (IF b THEN c1 ELSE c2) = {(s,t). (s,t) \<in> C c1 \<and> bval b s} \<union>
                            {(s,t). (s,t) \<in> C c2 \<and> \<not>bval b s}" |
"C(WHILE b DO c) = lfp (Gamma b (C c))"


lemma Gamma_mono: "mono (Gamma b c)"
by (unfold Gamma_def mono_def) fast

lemma C_While_If: "C(WHILE b DO c) = C(IF b THEN c;WHILE b DO c ELSE SKIP)"
apply simp
apply (subst lfp_unfold [OF Gamma_mono])  --{*lhs only*}
apply (simp add: Gamma_def)
done

text{* Equivalence of denotational and big-step semantics: *}

lemma com1: "(c,s) \<Rightarrow> t \<Longrightarrow> (s,t) \<in> C(c)"
apply (induction rule: big_step_induct)
apply auto
(* while *)
apply (unfold Gamma_def)
apply (subst lfp_unfold[OF Gamma_mono, simplified Gamma_def])
apply fast
apply (subst lfp_unfold[OF Gamma_mono, simplified Gamma_def])
apply auto 
done

lemma com2: "(s,t) \<in> C(c) \<Longrightarrow> (c,s) \<Rightarrow> t"
apply (induction c arbitrary: s t)
apply auto 
apply blast
(* while *)
apply (erule lfp_induct2 [OF _ Gamma_mono])
apply (unfold Gamma_def)
apply auto
done

lemma denotational_is_big_step: "(s,t) \<in> C(c)  =  ((c,s) \<Rightarrow> t)"
by (fast elim: com2 dest: com1)

end