History log of /seL4-l4v-10.1.1/HOL4/examples/balanced_bst/balanced_mapScript.sml
Revision Date Author Comments
# 624882d6 18-Jul-2017 Michael Norrish <Michael.Norrish@nicta.com.au>

Fixed to build balanced_bst given changes in 93036c73b4

Achieve this by making comparisonTheory a bit more backwards
compatible. Changes to balanced_bstScript.sml are just to add a bunch
of

val _ = print "Proved lemma\n";

messages after Q.prove calls. This makes it
easier to see that the script is making progress as it executes.


# f3e77975 08-Jun-2017 Ramana Kumar <ramana@member.fsf.org>

Add some theorems about toAscList


# 3beef644 07-Jun-2017 Ramana Kumar <ramana@member.fsf.org>

Add lookup_insert theorem to balanced_map


# 927020b1 02-May-2017 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix examples/balanced_bst for new by


# 843ed665 31-Oct-2016 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix proof broken by 9a822fc3 (DROP/TAKE change)


# 12e27f62 07-May-2016 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix balanced_bst theory given changes from 1f63d5f


# 67d4de13 26-Jan-2016 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix balanced_map theory to build with new lc simp


# 0f24f234 21-Dec-2014 Ramana Kumar <ramana@member.fsf.org>

Move comparisonTheory to src/enumfset

(from examples/balanced_bst)

Prove a theorem relating most of the definitions in comparisonTheory to
something in totoTheory.

Also, add a new definition for inverting cpns.

Make the overloads on the constructors of cpn permanent in
comparisonTheory.

Turn on totoTheory's "BigSig" to get more useful exports.

This is work towards integration, but the approach has been towards
plurality, i.e. keeping multiple definitions around and proving
relationships between them. More integration could be possible. Also,
the dependency between toto and comparison could be flipped (I wanted to
write new proofs in the nicer environment of comparison so did not do
that.) It has become apparent that totoTheory is in various minor ways
not self-consistent (esp. with regard to its naming schemes).


# fef315ca 21-Dec-2014 Ramana Kumar <ramana@member.fsf.org>

delete trailing whitespace in examples/balanced_bst


# 284ce52d 20-Dec-2014 Ramana Kumar <ramana@member.fsf.org>

reuse cpn datatype from totoTheory in comparisonTheory

rather than creating an isomorphic new type.

balanced_mapScript.sml has apparently (but not actually) significant
changes because the proofs depend heavily on the order in which the
comparison datatype constructors are defined (inasmuch as it affects the
order of subgoals from cases/induction).


# 1456dbdd 12-Dec-2014 Scott Owens <S.A.Owens@kent.ac.uk>

Add a verified balanced binary tree example

This is based on the implementation of weight balanced binary search
trees in the ghc Haskell compiler's standard library.

comparisonScript.sml has a basic theory of comparisons that return
either Less, Greater, or Equal. This is not compatible with the existing
totoScript.sml, because I don't require cmp x y = Equal ==> x = y, but
it does.

osetScript.sml uses the balanced trees to implement sets.

Functional correctenss of the operations is verified, along with the
balancing properties.