ACL2 >; In this session log, I have already loaded my patch to ACL2 V42 to
; support the dtx stuff. In the talk, I will interactively execute
; each of the following commands. Following this LD command is the
; result of that interaction.
(LD '((defun bit32p (x)
(and (integerp x)
(<= 0 x)
(< x (expt 2 32))))
(defun bit64p (x)
(and (integerp x)
(<= 0 x)
(< x (expt 2 64))))
(defdtx bit32p)
(defdtx bit64p)
(defdtx (:REC action (:OR 'READ 'WRITE 'BLOCK)))
(defdtx (:REC line (action bit32p booleanp)))
(defdtx (:REC lines (:OR nil (line . lines))))
(thm
(implies (and (type? action a)
(type? bit32p b))
(type? line (list a b t))))
(pe 'dtx0)
(pe 'dtx9)
(thm
(implies (and (type? lines lst)
(consp lst))
(type? bit64p (cadr (car lst)))))
(pe 'dtx10)
(pe 'dtx19)
(thm
(implies (type? line x)
(true-listp x)))
(thm
(implies (and (type? lines x)
(type? lines y))
(type? lines (append x y))))
(thm (implies (type? action x)
(not (type? line x))))
(thm (implies (type? action x)
(symbolp x)))
(defdtx (:REC (:OR nil (bit64p . *))))
(defdtx (:REC (:OR nil (bit32p . *))))
(thm (implies (type? (:REC (:OR (bit32p . *) nil)) x)
(type? (:REC (:OR nil (bit64p . *))) x)))
(defunt add-to-each (n lst)
((integerp (:REC (:OR nil (integerp . *))))
=>
(:REC (:OR nil (integerp . *))))
(cond ((endp lst) nil)
(t (cons (+ n (car lst))
(add-to-each n (cdr lst))))))
(pcb :x)
(pe 'DTX62)
(pe 'DTX60)
(defdtx integer-listp)
(pcb! :x))
:ld-pre-eval-print t)
ACL2 Version 4.2. Level 2. Cbd "/Users/moore/work/typer/".
Distributed books directory
"/Users/moore/work/v4-2/acl2-sources/books/".
Type :help for help.
Type (good-bye) to quit completely out of ACL2.
ACL2 >>(DEFUN BIT32P (X)
(AND (INTEGERP X)
(<= 0 X)
(< X (EXPT 2 32))))
Since BIT32P is non-recursive, its admission is trivial.
We observe that the type of BIT32P is described by the
theorem (OR (EQUAL (BIT32P X) T) (EQUAL (BIT32P X) NIL)).
Summary
Form: ( DEFUN BIT32P ...)
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
BIT32P
ACL2 >>(DEFUN BIT64P (X)
(AND (INTEGERP X)
(<= 0 X)
(< X (EXPT 2 64))))
Since BIT64P is non-recursive, its admission is trivial.
We observe that the type of BIT64P is described by the
theorem (OR (EQUAL (BIT64P X) T) (EQUAL (BIT64P X) NIL)).
Summary
Form: ( DEFUN BIT64P ...)
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
BIT64P
ACL2 >>(DEFDTX BIT32P)
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(DEFDTX BIT64P)
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(DEFDTX (:REC ACTION (:OR 'READ 'WRITE 'BLOCK)))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(DEFDTX (:REC LINE (ACTION BIT32P BOOLEANP)))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(DEFDTX (:REC LINES (:OR NIL (LINE . LINES))))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(THM (IMPLIES (AND (TYPE? ACTION A) (TYPE? BIT32P B))
(TYPE? LINE (LIST A B T))))
By the simple :definition BIT32P and the :executable-
counterpart of EXPT we reduce the conjecture to
Goal'
(IMPLIES (AND (TYPE? (:REC ACTION (:OR 'BLOCK 'READ 'WRITE))
A)
(INTEGERP B)
(<= 0 B)
(< B 4294967296))
(TYPE? (:REC LINE (ACTION BIT32P BOOLEANP))
(LIST* A B '(T)))).
But simplification reduces this to T, using the :executable-
counterparts of BOOLEANP, CAR, CDR, CONSP, EQUAL and
EXPT, linear arithmetic, primitive type reasoning, the
:rewrite rules CAR-CONS, CDR-CONS, DTX0 and DTX9 and
the :type-prescription rule ACTION.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:DEFINITION BIT32P)
(:EXECUTABLE-COUNTERPART BOOLEANP)
(:EXECUTABLE-COUNTERPART CAR)
(:EXECUTABLE-COUNTERPART CDR)
(:EXECUTABLE-COUNTERPART CONSP)
(:EXECUTABLE-COUNTERPART EQUAL)
(:EXECUTABLE-COUNTERPART EXPT)
(:FAKE-RUNE-FOR-LINEAR NIL)
(:FAKE-RUNE-FOR-TYPE-SET NIL)
(:REWRITE CAR-CONS)
(:REWRITE CDR-CONS)
(:REWRITE DTX0)
(:REWRITE DTX9)
(:TYPE-PRESCRIPTION ACTION))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(PE 'DTX0)
3 (DEFDTX BIT32P)
\
> (DEFTHM
DTX0
(IMPLIES (AND (INTEGERP X)
(NOT (< X '0))
(< X (EXPT '2 '32)))
(BIT32P X))
:RULE-CLASSES ((:REWRITE))
:HINTS (("Goal" :IN-THEORY (ENABLE BIT32P))))
ACL2 >>(PE 'DTX9)
d 6 (DEFDTX (:REC LINE #))
\
> (DEFTHM
DTX9
(IMPLIES
(AND (CONSP E)
(ACTION (CAR E))
(CONSP (CDR E))
(BIT32P (CAR (CDR E)))
(CONSP (CDR (CDR E)))
(BOOLEANP (CAR (CDR (CDR E))))
(EQUAL (CDR (CDR (CDR E))) 'NIL))
(LINE E))
:RULE-CLASSES ((:REWRITE))
:HINTS (("Goal" :IN-THEORY (ENABLE LINE))))
ACL2 >>(THM (IMPLIES (AND (TYPE? LINES LST) (CONSP LST))
(TYPE? BIT64P (CADR (CAR LST)))))
By case analysis we reduce the conjecture to
Goal'
(IMPLIES (AND (TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
LST)
(CONSP LST))
(BIT64P (CADAR LST))).
But simplification reduces this to T, using primitive
type reasoning, the :forward-chaining rules DTX10 and
DTX19, the :rewrite rule DTX4 and the :type-prescription
rules BIT32P, LINE and LINES.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)
(:FORWARD-CHAINING DTX10)
(:FORWARD-CHAINING DTX19)
(:REWRITE DTX4)
(:TYPE-PRESCRIPTION BIT32P)
(:TYPE-PRESCRIPTION LINE)
(:TYPE-PRESCRIPTION LINES))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(PE 'DTX10)
d 6 (DEFDTX (:REC LINE #))
\
> (DEFTHM
DTX10
(IMPLIES
(LINE E)
(IF
(CONSP E)
(IF
(ACTION (CAR E))
(IF
(CONSP (CDR E))
(IF
(BIT32P (CAR (CDR E)))
(IF (CONSP (CDR (CDR E)))
(IF (BOOLEANP (CAR (CDR (CDR E))))
(EQUAL (CDR (CDR (CDR E))) 'NIL)
'NIL)
'NIL)
'NIL)
'NIL)
'NIL)
'NIL))
:RULE-CLASSES ((:FORWARD-CHAINING))
:HINTS (("Goal" :IN-THEORY (ENABLE LINE))))
ACL2 >>(PE 'DTX19)
7:x(DEFDTX (:REC LINES #))
\
> (DEFTHM
DTX19
(IMPLIES
(LINES E)
(IF
(EQUAL E 'NIL)
'T
(IF
(CONSP E)
(IF (LINE (CAR E)) (LINES (CDR E)) 'NIL)
'NIL)))
:RULE-CLASSES ((:FORWARD-CHAINING))
:HINTS (("Goal" :IN-THEORY (ENABLE LINES))))
ACL2 >>(THM (IMPLIES (TYPE? LINE X) (TRUE-LISTP X)))
But we reduce the conjecture to T, by primitive type
reasoning, the :forward-chaining rule DTX10 and the
:type-prescription rule LINE.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)
(:FORWARD-CHAINING DTX10)
(:TYPE-PRESCRIPTION LINE))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(THM (IMPLIES (AND (TYPE? LINES X) (TYPE? LINES Y))
(TYPE? LINES (APPEND X Y))))
By case analysis we reduce the conjecture to
Goal'
(IMPLIES (AND (TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
Name the formula above *1.
Perhaps we can prove *1 by induction. Three induction
schemes are suggested by this conjecture. These merge
into two derived induction schemes. However, one of
these is flawed and so we are left with one viable candidate.
We will induct according to a scheme suggested by
(BINARY-APPEND X Y). This suggestion was produced using
the :induction rules BINARY-APPEND and LINES. If we
let (:P X Y) denote *1 above then the induction scheme
we'll use is
(AND (IMPLIES (AND (NOT (ENDP X)) (:P (CDR X) Y))
(:P X Y))
(IMPLIES (ENDP X) (:P X Y))).
This induction is justified by the same argument used
to admit BINARY-APPEND. When applied to the goal at
hand the above induction scheme produces three nontautologica\
l subgoals.
Subgoal *1/3
(IMPLIES (AND (NOT (ENDP X))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND (CDR X) Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
By the simple :definition ENDP we reduce the conjecture
to
Subgoal *1/3'
(IMPLIES (AND (CONSP X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND (CDR X) Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
But simplification reduces this to T, using the :definitions
BINARY-APPEND and LINES, primitive type reasoning, the
:rewrite rules CAR-CONS, CDR-CONS and DTX18 and the
:type-prescription rules LINE and LINES.
Subgoal *1/2
(IMPLIES
(AND (NOT (ENDP X))
(NOT (TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(CDR X)))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
But we reduce the conjecture to T, by primitive type
reasoning, the :forward-chaining rule DTX19 and the
:type-prescription rule LINES.
Subgoal *1/1
(IMPLIES (AND (ENDP X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
By the simple :definition ENDP we reduce the conjecture
to
Subgoal *1/1'
(IMPLIES (AND (NOT (CONSP X))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
X)
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
Y))
(TYPE? (:REC LINES (:OR NIL (LINE . LINES)))
(APPEND X Y))).
But simplification reduces this to T, using the :definitions
BINARY-APPEND and LINES, the :executable-counterpart
of CONSP, primitive type reasoning and the :type-prescription
rule LINES.
That completes the proof of *1.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:DEFINITION BINARY-APPEND)
(:DEFINITION ENDP)
(:DEFINITION LINES)
(:DEFINITION NOT)
(:EXECUTABLE-COUNTERPART CONSP)
(:FAKE-RUNE-FOR-TYPE-SET NIL)
(:FORWARD-CHAINING DTX19)
(:INDUCTION BINARY-APPEND)
(:INDUCTION LINES)
(:REWRITE CAR-CONS)
(:REWRITE CDR-CONS)
(:REWRITE DTX18)
(:TYPE-PRESCRIPTION LINE)
(:TYPE-PRESCRIPTION LINES))
Time: 0.02 seconds (prove: 0.01, print: 0.01, other: 0.00)
Proof succeeded.
ACL2 >>(THM (IMPLIES (TYPE? ACTION X)
(NOT (TYPE? LINE X))))
But we reduce the conjecture to T, by primitive type
reasoning, the :forward-chaining rules DTX10 and DTX5
and the :type-prescription rules ACTION and LINE.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)
(:FORWARD-CHAINING DTX10)
(:FORWARD-CHAINING DTX5)
(:TYPE-PRESCRIPTION ACTION)
(:TYPE-PRESCRIPTION LINE))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(THM (IMPLIES (TYPE? ACTION X) (SYMBOLP X)))
But we reduce the conjecture to T, by primitive type
reasoning, the :forward-chaining rule DTX5 and the :type-
prescription rule ACTION.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)
(:FORWARD-CHAINING DTX5)
(:TYPE-PRESCRIPTION ACTION))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(DEFDTX (:REC (:OR NIL (BIT64P . *))))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(DEFDTX (:REC (:OR NIL (BIT32P . *))))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(THM (IMPLIES (TYPE? (:REC (:OR (BIT32P . *) NIL)) X)
(TYPE? (:REC (:OR NIL (BIT64P . *)))
X)))
By case analysis we reduce the conjecture to
Goal'
(IMPLIES (TYPE? (:REC (:OR NIL (BIT32P . *))) X)
(TYPE? (:REC (:OR NIL (BIT64P . *)))
X)).
But simplification reduces this to T, using the :rewrite
rule DTX41 and the :type-prescription rule
|(:REC (:OR NIL (BIT32P . *)))|.
Q.E.D.
Summary
Form: ( THM ...)
Rules: ((:REWRITE DTX41)
(:TYPE-PRESCRIPTION
|(:REC (:OR NIL (BIT32P . *)))|))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Proof succeeded.
ACL2 >>(DEFUNT ADD-TO-EACH (N LST)
((INTEGERP (:REC (:OR NIL (INTEGERP . *))))
=> (:REC (:OR NIL (INTEGERP . *))))
(COND ((ENDP LST) NIL)
(T (CONS (+ N (CAR LST))
(ADD-TO-EACH N (CDR LST))))))
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
The admission of ADD-TO-EACH is trivial, using the relation
O< (which is known to be well-founded on the domain
recognized by O-P) and the measure (ACL2-COUNT LST).
We observe that the type of ADD-TO-EACH is described
by the theorem (TRUE-LISTP (ADD-TO-EACH N LST)). We
used primitive type reasoning.
Summary
Form: ( DEFUN ADD-TO-EACH ...)
Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL))
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(PCB :X)
10:x(DEFUNT ADD-TO-EACH (N LST) ...)
(DEFTHM DTX44 ...)
(DEFTHM DTX45 ...)
(DEFDXT INTEGERP)
L (DEFUN |(:REC (:OR NIL (INTEGERP . *)))| (E)
...)
(IN-THEORY (DISABLE))
(DEFTHM DTX51 ...)
(DEFTHM DTX52 ...)
(DEFTHM DTX60 ...)
(DEFTHM DTX61 ...)
(DEFDXT (:REC #))
L (DEFUN ADD-TO-EACH (N LST) ...)
(DEFTHM DTX62 ...)
ACL2 >>(PE 'DTX62)
10:x(DEFUNT ADD-TO-EACH (N LST) ...)
\
> (DEFTHM
DTX62
(IMPLIES
(AND (TYPE? INTEGERP N)
(TYPE? (:REC (:OR NIL (INTEGERP . *)))
LST))
(TYPE? (:REC (:OR NIL (INTEGERP . *)))
(ADD-TO-EACH N LST)))
:RULE-CLASSES
((:REWRITE)
(:FORWARD-CHAINING
:TRIGGER-TERMS ((ADD-TO-EACH N LST)))))
ACL2 >>(PE 'DTX60)
10:x(DEFUNT ADD-TO-EACH (N LST) ...)
\
> (DEFTHM
DTX60
(IMPLIES
(|(:REC (:OR NIL (BIT64P . *)))| X)
(|(:REC (:OR NIL (INTEGERP . *)))| X))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal"
:IN-THEORY
(ENABLE |(:REC (:OR NIL (INTEGERP . *)))|
|(:REC (:OR NIL (BIT64P . *)))|))))
ACL2 >>(DEFDTX INTEGER-LISTP)
Summary
Form: DEFDTX
Rules: NIL
Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00)
DTX-DATABASE
ACL2 >>(PCB! :X)
d 11:x(DEFDTX INTEGER-LISTP)
(DEFTHM
DTX63
(IMPLIES (AND (CONSP L)
(INTEGERP (CAR L))
(INTEGER-LISTP (CDR L)))
(INTEGER-LISTP L))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal" :IN-THEORY (ENABLE INTEGER-LISTP))))
(DEFTHM
DTX64
(IMPLIES (INTEGER-LISTP L)
(IF (CONSP L)
(IF (INTEGERP (CAR L))
(INTEGER-LISTP (CDR L))
'NIL)
(EQUAL L 'NIL)))
:RULE-CLASSES ((:FORWARD-CHAINING))
:HINTS
(("Goal" :IN-THEORY (ENABLE INTEGER-LISTP))))
(DEFTHM
DTX72
(IMPLIES (|(:REC (:OR NIL (BIT64P . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal"
:IN-THEORY
(ENABLE INTEGER-LISTP
|(:REC (:OR NIL (BIT64P . *)))|))))
(DEFTHM
DTX73
(IMPLIES (|(:REC (:OR NIL (BIT32P . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal"
:IN-THEORY
(ENABLE INTEGER-LISTP
|(:REC (:OR NIL (BIT32P . *)))|))))
D (DEFTHM
DTX74
(IMPLIES
(INTEGER-LISTP X)
(|(:REC (:OR NIL (INTEGERP . *)))| X))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal"
:IN-THEORY
(ENABLE
INTEGER-LISTP
|(:REC (:OR NIL (INTEGERP . *)))|))))
D (DEFTHM
DTX75
(IMPLIES
(|(:REC (:OR NIL (INTEGERP . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS
(("Goal"
:IN-THEORY
(ENABLE
INTEGER-LISTP
|(:REC (:OR NIL (INTEGERP . *)))|))))
(DEFTHM
DTX76
(IFF (|(:REC (:OR NIL (INTEGERP . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS (("Goal" :IN-THEORY '(DTX74 DTX75))))
(IN-THEORY (DISABLE DTX74 DTX75))
(DEFTHM
DTX77
(IMPLIES (|(:REC (:OR NIL (BIT32P . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS (("Goal" :USE DTX61
:IN-THEORY '(DTX76))))
(DEFTHM
DTX78
(IMPLIES (|(:REC (:OR NIL (BIT64P . *)))| X)
(INTEGER-LISTP X))
:RULE-CLASSES ((:REWRITE))
:HINTS (("Goal" :USE DTX60
:IN-THEORY '(DTX76))))
ACL2 >>Bye.
:EOF
ACL2 >