History log of /seL4-l4v-10.1.1/HOL4/src/simp/src/selftest.sml
Revision Date Author Comments
# 5bb5b631 23-Sep-2018 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix bug in handling of bounded simp (e.g., with Once)

The bug was introduced by d71df467 and was apparent in a CakeML proof:
the commit made it impossible to use the simplifier to rewrite with
the Abbrev definition backwards (i.e., GSYM markerTheory.Abbrev_def)
because the variable on the LHS of that theorem has type bool. This is
a loopy rewrite, but should be permitted if the rewrite is bounded.

Equally, rewriting with the definition of I backwards would exhibit
the same problem, as long as one first instantiated the alpha in that
theorem to bool.


# d71df467 19-Sep-2018 Michael Norrish <Michael.Norrish@nicta.com.au>

Stop simplifier from generating rewrites on boolean variables

Occasionally, an assumption will be generated that the simplifier
reads as a conditional rewrite, but which has the shape

!... x..... preconds x y z ==> x

where x is a variable of type bool. These generate pointless
conditional rewrites for all possible terms of type bool. Now we stop
these from getting in.

Closes #556


# 469c3bb1 10-Jun-2018 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix simp failing to handle rewrites P ==> (b = e) (for b = T or F)

Issue was that code existed for this case but incorrectly manipulated
the input theorem rather than the "undisch" theorem which had moved P
into the theorem assumptions.

Include test.


# a5ac2b87 09-Apr-2017 Thomas Tuerk <thomas@tuerk-brechen.de>

provide first version of BackchainingLib

This lib is used to combine matching preconditions against assumptions
in the goalstack with conditional rewriting. This enables efficient
backwards-chaining with theorems like

``!x y. R x y ==> !x' y'. complicated condition ==> R x' y'``


# e2db1817 21-Apr-2016 Michael Norrish <Michael.Norrish@nicta.com.au>

Make selftest output line up with parallel Holmake's

Also make tests use testutils.OK to report OK


# 7f88b646 17-Sep-2015 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix (somewhat obscure) looping bug in simplifier.

If the terms T = F and F = T both arrive in your assumption list, then
you will go into an infinite loop. Neither should fire as a rewrite at
all. Indeed, anything of the form T = x, or F = x, is better off
flipped, unless it's the bad case above. In the bad case, treat the
rewrite as we treat a bare F.


# e693dc92 02-Mar-2014 Michael Norrish <michael.norrish@nicta.com.au>

Extend simplifier's treatment of abbrevs to handle abstractions better


# 4fd494ce 08-Oct-2012 Thomas Tuerk <tt291@cl.cam.ac.uk>

selftest for SATISFY_ss added


# c546c4ba 17-Mar-2011 Michael Norrish <Michael.Norrish@nicta.com.au>

Simp{L,R} were only working if the argument was a relation.

This meant one could rewrite exclusively on the left/right of /\, =, ==>
etc, but not +. Problem was an unnecessarily specific theorem.

Bug reported by Ramana Kumar.


# d12b0f65 19-Oct-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Add new test of simplifier's congruence technology.


# 98de1da3 10-Mar-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Bug: bounds on rewrites should be shared between all derived rewrites.

In a situation like

th = |- (p = x) /\ (q = y)

as the input rewrite, you might want separate bounds (i.e., both
conjuncts of Once th get to apply once each), but with

|- (s1 = s2) <=> (!x. x IN s1 <=> x IN s2)

you surely do not want the two derived theorems

|- (s1 = s2) <=> (!x. x IN s1 <=> x IN s2)
|- (s2 = s1) <=> (!x. x IN s1 <=> x IN s2)

to both get a chance to apply. Arguably, in the latter case, the
simplifier should be smart enough to see that the two terms are
instances of each other and not generate two theorems, but the test is
not as simple as just "are both sides variables", because one or both
of the variables may be bound in a goal's assumptions, and then both
rewrites are useful.


# 2b3c955b 14-Dec-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

New "portable" subdirs per ML implementations in src/portableML.

Hope to do away with Poly/ML specific code in tools-poly eventually,
moving it into src/portableML/poly. tools/build-sequence now records
that the implementation-specific directories have to be included.


# cc7cb03e 22-Jul-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

src/simp/src/selftest.sml now correctly tests the bug claimed in r6991.
(Yikes^2!)


# 715e9184 22-Jul-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Selftest contained an error in its check for correct behaviour. (Yikes)


# c975f6f6 22-Jul-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Bounded rewrites where the LHS is a single variable (which you might
want if doing something fiddly with |- m = m + 0, say) get their
bounding reference variable decremented prematurely. This bug
manifests with this pattern (and not with more typical ones) because
the pattern matches everything and gets pulled out of the
internal term-net. Other patterns don't get tried on so many terms.

The problem is not the "pulling out of the net", but the decrementing
the reference inappropriately early.


# 446a870f 21-Jul-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Add a test-case for a problem found by Ramana Kumar: the Once
annotation doesn't prevent some rewrites from being rejected as
looping, meaning that they don't get applied at all.


# ddd29f5b 09-Apr-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Modify the standard conditional rewrite behaviour so that if a rewrite
theorem has been bounded (with Once, or Ntimes), then it is allowed to
be applied in circumstances where the simplifier's looping detection
would otherwise reject it. This allows (Once EQ_SYM_EQ) to do
something, as the new self-test demonstrates.


# c76376ed 29-Apr-2008 Konrad Slind <konrad.slind@gmail.com>

Additional functionality for abbreviations.

1. The labels library has been merged into
markerLib and the src/labels directory eliminated.
2. Have added markerSyntax structure.
3. Operations on abbrevs used to all be in
structure Q, even those that didn't deal
with quotations (like UNABBREV_ALL_TAC). Now
markerLib provides all abbrev. operations and
these take terms. Operations that benefit from
quotes, e.g., ABBREV_TAC, MATCH_ABBREV_TAC, etc.
are still to be found in Q.
4. Abbrevs are kept reduced by the simplifiers and
there is a REABBREV_TAC which can be separately called.
This sorts abbrevs topologically, so that they get
restored in a sensible order.
5. For situations where one wants to get rid of all
abbrevs, apply a tactic, and then restore the abbrevs,
there is WITHOUT_ABBREVS: tactic->tactic.
6. Have added a simple topological sort to Lib.
7. Updated proofs in the src directories, and also
in examples/lambda.


# b91d5bc5 10-Mar-2008 Peter Homeier <palantir@trustworthytools.com>

Repaired example in selftest to parse under HOL-Omega.


# c0732b6e 18-Aug-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

A little code reorganisation and a fix for a bug in the implementation
of ASM_SIMP_TAC and FULL_SIMP_TAC: abbreviation references in the
argument list weren't being dealt with early enough. In the case of
ASM_SIMP_TAC this caused the effect of an abbreviation being eliminated
in the assumptions but not in the goal.


# 3935e7f0 05-Aug-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

Add a test to check on bounded simplification.


# af8cbfaf 21-Jan-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

Test that AC really can cope with the associativity and commutativity
theorems the other way round.


# c78caf4a 08-Jan-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

Alright, I admit, this is just being precious.


# 8257be07 08-Jan-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

Handle Interrupt slightly more gracefully.


# 115f2d17 08-Jan-2004 Michael Norrish <Michael.Norrish@nicta.com.au>

Self-test demonstrating the current bug in the AC rewriter.