equal
deleted
inserted
replaced
54 "traverse (Node x r) = do tl \<leftarrow> Ref.lookup r; |
54 "traverse (Node x r) = do tl \<leftarrow> Ref.lookup r; |
55 xs \<leftarrow> traverse tl; |
55 xs \<leftarrow> traverse tl; |
56 return (x#xs) |
56 return (x#xs) |
57 done" |
57 done" |
58 unfolding traverse_def |
58 unfolding traverse_def |
59 by (auto simp: traverse_def monad_simp MREC_rule) |
59 by (auto simp: traverse_def MREC_rule) |
60 |
60 |
61 |
61 |
62 section {* Proving correctness with relational abstraction *} |
62 section {* Proving correctness with relational abstraction *} |
63 |
63 |
64 subsection {* Definition of list_of, list_of', refs_of and refs_of' *} |
64 subsection {* Definition of list_of, list_of', refs_of and refs_of' *} |
529 rev' (p, next) |
529 rev' (p, next) |
530 done) |
530 done) |
531 done" |
531 done" |
532 unfolding rev'_def MREC_rule[of _ _ "(q, p)"] unfolding rev'_def[symmetric] |
532 unfolding rev'_def MREC_rule[of _ _ "(q, p)"] unfolding rev'_def[symmetric] |
533 thm arg_cong2 |
533 thm arg_cong2 |
534 by (auto simp add: monad_simp expand_fun_eq intro: arg_cong2[where f = "op \<guillemotright>="] split: node.split) |
534 by (auto simp add: expand_fun_eq intro: arg_cong2[where f = "op \<guillemotright>="] split: node.split) |
535 |
535 |
536 fun rev :: "('a:: heap) node \<Rightarrow> 'a node Heap" |
536 fun rev :: "('a:: heap) node \<Rightarrow> 'a node Heap" |
537 where |
537 where |
538 "rev Empty = return Empty" |
538 "rev Empty = return Empty" |
539 | "rev (Node x n) = (do q \<leftarrow> Ref.new Empty; p \<leftarrow> Ref.new (Node x n); v \<leftarrow> rev' (q, p); !v done)" |
539 | "rev (Node x n) = (do q \<leftarrow> Ref.new Empty; p \<leftarrow> Ref.new (Node x n); v \<leftarrow> rev' (q, p); !v done)" |