~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(trace$ (rewrite :entry (break$))) ((REWRITE :ENTRY (BREAK$))) ACL2 !>:mini-proveall ; then :b in CCL, backtrace in SBCL Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>>:LOGIC The event ( TABLE ACL2-DEFAULTS-TABLE ...) is redundant. See :DOC redundant-events. ACL2 !>>(THM (IMPLIES (AND (TRUE-LISTP X) (TRUE-LISTP Y)) (EQUAL (REVAPPEND (APPEND X Y) Z) (REVAPPEND Y (REVAPPEND X Z))))) > Break: Break > While executing: BREAK$-RAW, in process listener(1). > Type :GO to continue, :POP to abort, :R for a list of available restarts. > If continued: Return from BREAK. > Type :? for other options. 1 > :b (1739DDE90) : 0 (BREAK$-RAW) 160 (1739DDEB0) : 1 (BREAK$) 284 (1739DDED0) : 2 (REWRITE (TRUE-LISTP X) NIL 1 1000 1152921504606846921 ((# 128) (Y 1152)) ? ((NIL IFF :FAKE-RUNE-FOR-ANONYMOUS-ENABLED-RULE NIL)) NIL ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) ACL2_INVISIBLE::|The Live State Itself| NIL NIL NIL NIL ((# # NIL) (# #) (# NIL # # #) (T # # #) :ATOM . T) NIL NIL) 564 (1739DDF10) : 3 (REWRITE-ATM (TRUE-LISTP X) T 1 NIL ((# 128) (Y 1152)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL ((# # NIL) (# #) (# NIL # # #) (T # # #) :ATOM . T) ((NOT #) (EQUAL # #)) ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922 NIL) 1948 (1739DDF50) : 4 (REWRITE-CLAUSE ((NOT #) (NOT #) (EQUAL # #)) (0 1 2) 1 NIL NIL NIL ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL ((# # NIL) (# #) (# NIL # # #) (T # # #) :ATOM . T) NIL 1 NIL NIL ((LEMMA #)) NIL ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 2816 (1739DDF90) : 5 (SIMPLIFY-CLAUSE1 ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# # NIL) (# #) (# NIL) (T) :ATOM . T) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 7104 (1739DDFD0) : 6 (SIMPLIFY-CLAUSE ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 168 (1739DE010) : 7 (WATERFALL-STEP1 SIMPLIFY-CLAUSE ((0) NIL . 0) ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 912 (1739DE050) : 8 (WATERFALL-STEP SIMPLIFY-CLAUSE ((0) NIL . 0) ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 532 (1739DE0B0) : 9 (WATERFALL0 (SIMPLIFY-CLAUSE SETTLED-DOWN-CLAUSE ELIMINATE-DESTRUCTORS-CLAUSE FERTILIZE-CLAUSE GENERALIZE-CLAUSE ...) ((0) NIL . 0) ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846922) 1648 (1739DE0F0) : 10 (WATERFALL1 (APPLY-TOP-HINTS-CLAUSE PREPROCESS-CLAUSE SIMPLIFY-CLAUSE SETTLED-DOWN-CLAUSE ELIMINATE-DESTRUCTORS-CLAUSE ...) ((0) NIL . 0) ((NOT #) (NOT #) (EQUAL # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846953) 404 (1739DE130) : 11 (WATERFALL1-LST NIL ((0) NIL . 0) ((# # #)) ((PREPROCESS-CLAUSE # # HIT # ...)) ((# NIL) (# NIL # # #) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL NIL NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846953) 792 (1739DE170) : 12 (WATERFALL1 (APPLY-TOP-HINTS-CLAUSE PREPROCESS-CLAUSE SIMPLIFY-CLAUSE SETTLED-DOWN-CLAUSE ELIMINATE-DESTRUCTORS-CLAUSE ...) ((0) NIL . 0) ((IMPLIES # #)) NIL ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL T ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846975) 404 (1739DE1B0) : 13 (WATERFALL1-LST SETTLED-DOWN-CLAUSE ((0) NIL . 0) ((#)) NIL ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL NIL T ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846975) 792 (1739DE1F0) : 14 (WATERFALL 0 NIL ((#)) ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846975) 760 (1739DE230) : 15 (PROVE-LOOP2 0 NIL ((#)) ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself| 1152921504606846975) 932 (1739DE270) : 16 (PROVE-LOOP1 0 NIL ((#)) ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself|) 384 (1739DE2D0) : 17 (PROVE-LOOP0 ((#)) ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself|) 1340 (1739DE310) : 18 (PROVE-LOOP ((#)) ((# NIL) (NIL NIL) (NIL # # NIL) (IMPLIES # #) (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself|) 1288 (1739DE350) : 19 (PROVE (IMPLIES (IF # # #) (EQUAL # #)) ((# NIL) (NIL NIL) (NIL # # NIL) 'T (IMPLIES # #) ...) NIL ((5670 # # # # ...) (ENABLED-ARRAY-0 . 8000) (#\E #\N #\A #\B #\L ...) . 0) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) "( THM ...)" ACL2_INVISIBLE::|The Live State Itself|) 1372 (1739DE390) : 20 (THM-FN (IMPLIES (AND # #) (EQUAL # #)) ACL2_INVISIBLE::|The Live State Itself| NIL NIL NIL (THM (IMPLIES # #))) 9228 (1739DE3D0) : 21 (RAW-EV-FNCALL THM-FN ((IMPLIES # #) ACL2_INVISIBLE::|The Live State Itself| NIL NIL NIL ...) ('# STATE 'NIL 'NIL 'NIL ...) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL NIL T) 1208 (1739DE430) : 22 (EV-REC-ACL2-UNWIND-PROTECT ((LAMBDA # #) (# #) STATE-GLOBAL-LET*-CLEANUP-LST) ((STATE-GLOBAL-LET*-CLEANUP-LST # # #) (STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL (NIL) NIL NIL ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 720 (1739DE470) : 23 (EV-REC-LST ((IF # # #)) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL (NIL) NIL NIL ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 452 (1739DE4B0) : 24 (EV-REC ((LAMBDA # #) (IF # # #)) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL (NIL) NIL NIL ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 4140 (1739DE4F0) : 25 (EV ((LAMBDA # #) (IF # # #)) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ACL2_INVISIBLE::|The Live State Itself| ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 356 (1739DE530) : 26 (EV-FOR-TRANS-EVAL ((LAMBDA # #) (IF # # #)) (NIL NIL STATE) ("( MAKE-EVENT ~@0~@1)" (#\0 "(~x0 ...)" #) (#\1 . " ...")) ACL2_INVISIBLE::|The Live State Itself| T NIL) 440 (1739DE570) : 27 (PROTECTED-EVAL (ER-PROGN (WITH-OUTPUT :STACK :POP #) (VALUE #)) :QUIET! ("( MAKE-EVENT ~@0~@1)" (#\0 "(~x0 ...)" #) (#\1 . " ...")) ACL2_INVISIBLE::|The Live State Itself| T) 20636 (1739DE5B0) : 28 (MAKE-EVENT-FN (ER-PROGN (WITH-OUTPUT :STACK :POP #) (VALUE #)) (VALUE-TRIPLE :INVISIBLE) NIL :QUIET! T (MAKE-EVENT (ER-PROGN # #) :EXPANSION? (VALUE-TRIPLE :INVISIBLE) :ON-BEHALF-OF ...) ACL2_INVISIBLE::|The Live State Itself|) 11448 (1739DE5F0) : 29 (RAW-EV-FNCALL MAKE-EVENT-FN ((ER-PROGN # #) (VALUE-TRIPLE :INVISIBLE) NIL :QUIET! T ...) ('# '# 'NIL ':QUIET! 'T ...) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL NIL T) 1208 (1739DE650) : 30 (EV-REC-ACL2-UNWIND-PROTECT ((LAMBDA # #) (# #) STATE-GLOBAL-LET*-CLEANUP-LST) ((STATE-GLOBAL-LET*-CLEANUP-LST # #) (STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL (NIL) NIL NIL ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 720 (1739DE690) : 31 (EV (IF (EQ # #) (MAKE-EVENT-FN # # # # ...) (# # STATE)) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ACL2_INVISIBLE::|The Live State Itself| ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 356 (1739DE6D0) : 32 (EV-FOR-TRANS-EVAL (IF (EQ # #) (MAKE-EVENT-FN # # # # ...) (# # STATE)) (NIL NIL STATE) TOP-LEVEL ACL2_INVISIBLE::|The Live State Itself| T NIL) 440 (1739DE710) : 33 (LD-READ-EVAL-PRINT ACL2_INVISIBLE::|The Live State Itself|) 3880 (1739DE750) : 34 (LD-LOOP ACL2_INVISIBLE::|The Live State Itself|) 204 (1739DE790) : 35 (LD-FN-BODY (:LOGIC (THM #) (DEFUN APP # #) (DEFTHM ASSOC-OF-APP #) (DEFUN REV # #) ...) ((LD-ERROR-ACTION . :RETURN!) (LD-PRE-EVAL-PRINT . T) (LD-REDEFINITION-ACTION) (LD-SKIP-PROOFSP) (STANDARD-OI :LOGIC # # # ...) ...) ACL2_INVISIBLE::|The Live State Itself|) 4036 (1739DE7D0) : 36 (LD-FN0 ((STANDARD-OI :LOGIC # # # ...) (LD-SKIP-PROOFSP) (LD-REDEFINITION-ACTION) (LD-PRE-EVAL-PRINT . T) (LD-ERROR-ACTION . :RETURN!)) ACL2_INVISIBLE::|The Live State Itself| T) 4840 (1739DE850) : 37 (RAW-EV-FNCALL LD-FN ((# # # # #) ACL2_INVISIBLE::|The Live State Itself| T) ((CONS # #) STATE 'T) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ((COMMAND-LANDMARK GLOBAL-VALUE 8732 # NIL) (EVENT-LANDMARK GLOBAL-VALUE 11172 # EXIT-BOOT-STRAP-MODE) (CURRENT-THEORY GLOBAL-VALUE # # # ...) (CURRENT-THEORY-AUGMENTED GLOBAL-VALUE # # # ...) (CURRENT-THEORY-INDEX GLOBAL-VALUE . 5670) ...) NIL NIL T) 1208 (1739DE8B0) : 38 (EV (LD-FN (CONS # #) STATE 'T) ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) ACL2_INVISIBLE::|The Live State Itself| ((STATE . ACL2_INVISIBLE::|The Live State Itself|)) NIL T) 356 (1739DE8F0) : 39 (EV-FOR-TRANS-EVAL (LD-FN (CONS # #) STATE 'T) (NIL NIL STATE) TOP-LEVEL ACL2_INVISIBLE::|The Live State Itself| T NIL) 440 (1739DE930) : 40 (LD-READ-EVAL-PRINT ACL2_INVISIBLE::|The Live State Itself|) 3880 (1739DE970) : 41 (LD-LOOP ACL2_INVISIBLE::|The Live State Itself|) 204 (1739DE9B0) : 42 (LD-FN-BODY ACL2-INPUT-CHANNEL::STANDARD-OBJECT-INPUT-0 ((LD-USER-STOBJS-MODIFIED-WARNING) (LD-VERBOSE . "Project-dir-alist:~|~xb.~|Type :help for help.~%Type ~ (quit) to quit completely out of ACL2.~|~%") (LD-QUERY-CONTROL-ALIST) (LD-ERROR-ACTION . :CONTINUE) (LD-ERROR-TRIPLES . T) ...) ACL2_INVISIBLE::|The Live State Itself|) 4036 (1739DE9F0) : 43 (LD-FN0 ((STANDARD-OI . ACL2-INPUT-CHANNEL::STANDARD-OBJECT-INPUT-0) (STANDARD-CO . ACL2-OUTPUT-CHANNEL::STANDARD-CHARACTER-OUTPUT-0) (PROOFS-CO . ACL2-OUTPUT-CHANNEL::STANDARD-CHARACTER-OUTPUT-0) (CURRENT-PACKAGE . "ACL2") (USELESS-RUNES) ...) ACL2_INVISIBLE::|The Live State Itself| NIL) 4840 (1739DEA70) : 44 (LD-FN ((STANDARD-OI . ACL2-INPUT-CHANNEL::STANDARD-OBJECT-INPUT-0) (STANDARD-CO . ACL2-OUTPUT-CHANNEL::STANDARD-CHARACTER-OUTPUT-0) (PROOFS-CO . ACL2-OUTPUT-CHANNEL::STANDARD-CHARACTER-OUTPUT-0) (CURRENT-PACKAGE . "ACL2") (USELESS-RUNES) ...) ACL2_INVISIBLE::|The Live State Itself| NIL) 1148 (1739DEAB0) : 45 (LP) 6188 (1739DEB10) : 46 (CALL-CHECK-REGS LP) 164 (1739DEB50) : 47 (CHEAP-EVAL (LP)) 96 (1739DEB70) : 48 (ACL2-DEFAULT-RESTART NIL) 1256 (1739DEBB0) : 49 (CALL-CHECK-REGS ACL2-DEFAULT-RESTART) 164 (1739DEBF0) : 50 (CHEAP-EVAL (ACL2-DEFAULT-RESTART)) 96 (1739DEC30) : 51 (FUNCALL #'#<(:INTERNAL CCL::EVAL-STRING CCL::STARTUP-CCL)> "(acl2::acl2-default-restart)") 360 (1739DEC70) : 52 (STARTUP-CCL ("home:ccl-init" "home:\\.ccl-init")) 1252 (1739DECD0) : 53 (FUNCALL #'#<(:INTERNAL (CCL:TOPLEVEL-FUNCTION (CCL::LISP-DEVELOPMENT-SYSTEM T)))>) 100 (1739DED10) : 54 (FUNCALL #'#<(:INTERNAL CCL::MAKE-MCL-LISTENER-PROCESS)>) 564 (1739DED70) : 55 (RUN-PROCESS-INITIAL-FORM # (#)) 596 (1739DEDF0) : 56 (FUNCALL #'#<(:INTERNAL (CCL::%PROCESS-PRESET-INTERNAL (CCL:PROCESS)))> # (#)) 468 (1739DEE50) : 57 (FUNCALL #'#<(:INTERNAL CCL::THREAD-MAKE-STARTUP-FUNCTION)>) 264 1 > Summary Form: ( THM ...) Rules: NIL Time: 0.02 seconds (prove: 0.00, print: 0.00, other: 0.02) Prover steps counted: 53 *** Note: No checkpoints to print. *** ACL2 Error [Failure] in ( THM ...): See :DOC failure. ******** FAILED ******** ACL2 !> ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(cw "~x0, ~x1~%" 'hello 'world) ; see :DOC fmt HELLO, WORLD NIL ACL2 !>(fmx-cw "~x0, ~x1~%" 'hello 'world) ; no change from cw HELLO, WORLD NIL ACL2 !>(fmx "~x0, ~x1~%" 'hello 'world) ; returns state HELLO, WORLD (0 ) ACL2 !>"But what if fmt arguments are missing?" "But what if fmt arguments are missing?" ACL2 !>(cw "~x0, ~x1~%" 'hello) ; runtime error HELLO, HARD ACL2 ERROR in FMT-VAR: Illegal Fmt Syntax. Unbound Fmt Variable. The tilde directive at location 5 in the fmt string below uses the variable #\1. But this variable is not bound in the association list, ((#\0 . HELLO)), supplied with the fmt string. "~x0, ~x1~%" ACL2 Error [Evaluation] in TOP-LEVEL: Evaluation aborted. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>(fmx-cw "~x0, ~x1~%" 'hello) ; guard violation ACL2 Error [Evaluation] in TOP-LEVEL: Guard violation for FMX-CW-FN: Illegal Fmt Syntax. Unbound Fmt Variable. The tilde directive at location 5 in the fmt string below uses the variable #\1. But this variable is not bound in the association list, ((#\0 . HELLO)), supplied with the fmt string. "~x0, ~x1~%" ACL2 !>(fmx "~x0, ~x1~%" 'hello) ; runtime error HELLO, HARD ACL2 ERROR in FMT-VAR: Illegal Fmt Syntax. Unbound Fmt Variable. The tilde directive at location 5 in the fmt string below uses the variable #\1. But this variable is not bound in the association list, ((#\0 . HELLO)), supplied with the fmt string. "~x0, ~x1~%" ACL2 Error [Evaluation] in TOP-LEVEL: Evaluation aborted. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>"Execute meta-x tags-search on: (set-guard-msg fmx-cw" "Execute meta-x tags-search on: (set-guard-msg fmx-cw" ACL2 !>(trace$ fmx-cw-msg) ((FMX-CW-MSG)) ACL2 !>(fmx-cw "~x0, ~x1~%" 'hello) ; guard violation 1> (FMX-CW-MSG "~x0, ~x1~%" ((#\0 . HELLO))) <1 (FMX-CW-MSG ("Illegal Fmt Syntax. ~@0" (#\0 "Unbound Fmt Variable. The tilde directive at location ~x0 in the fmt ~ string below uses the variable ~x1. But this variable is not bound in ~ the association list, ~x2, supplied with the fmt string.~|~%~x3" (#\0 . 5) (#\1 . #\1) (#\2 (#\0 . HELLO)) (#\3 . "~x0, ~x1~%")))) 1> (ACL2_*1*_ACL2::FMX-CW-MSG "~x0, ~x1~%" ((#\0 . HELLO))) 2> (FMX-CW-MSG "~x0, ~x1~%" ((#\0 . HELLO))) <2 (FMX-CW-MSG ("Illegal Fmt Syntax. ~@0" (#\0 "Unbound Fmt Variable. The tilde directive at location ~x0 in the fmt ~ string below uses the variable ~x1. But this variable is not bound in ~ the association list, ~x2, supplied with the fmt string.~|~%~x3" (#\0 . 5) (#\1 . #\1) (#\2 (#\0 . HELLO)) (#\3 . "~x0, ~x1~%")))) <1 (ACL2_*1*_ACL2::FMX-CW-MSG ("Illegal Fmt Syntax. ~@0" (#\0 "Unbound Fmt Variable. The tilde directive at location ~x0 in the fmt ~ string below uses the variable ~x1. But this variable is not bound in ~ the association list, ~x2, supplied with the fmt string.~|~%~x3" (#\0 . 5) (#\1 . #\1) (#\2 (#\0 . HELLO)) (#\3 . "~x0, ~x1~%")))) ACL2 Error [Evaluation] in TOP-LEVEL: Guard violation for FMX-CW-FN: Illegal Fmt Syntax. Unbound Fmt Variable. The tilde directive at location 5 in the fmt string below uses the variable #\1. But this variable is not bound in the association list, ((#\0 . HELLO)), supplied with the fmt string. "~x0, ~x1~%" ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun f1 (x) (declare (xargs :guard (consp x))) (car x)) Since F1 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F1. Computing the guard conjecture for F1.... The guard conjecture for F1 is trivial to prove. F1 is compliant with Common Lisp. Summary Form: ( DEFUN F1 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F1 ACL2 !>(f1 3) ; guard violation ACL2 Error [Evaluation] in TOP-LEVEL: The guard for the function call (F1 X), which is (CONSP X), is violated by the arguments in the call (F1 3). See :DOC set-guard-checking for information about suppressing this check with (set-guard-checking :none), as recommended for new users. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>(defun f2 (x) ; guard verification fails: (declare (xargs :guard t)) (f1 x)) Since F2 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F2. Computing the guard conjecture for F2.... The non-trivial part of the guard conjecture for F2 is Goal (CONSP X). *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. No induction schemes are suggested by *1. Consequently, the proof attempt has failed. ACL2 Error in ( DEFUN F2 ...): The proof of the guard conjecture for F2 has failed. You may wish to avoid specifying a guard, or to supply option :VERIFY-GUARDS NIL with the :GUARD. Otherwise, you may wish to specify :GUARD-DEBUG T; see :DOC verify-guards. Summary Form: ( DEFUN F2 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 8 --- The key checkpoint goal, below, may help you to debug this failure. See :DOC failure and see :DOC set-checkpoint-summary-limit. --- *** Key checkpoint at the top level: *** Goal (CONSP X) ACL2 Error [Failure] in ( DEFUN F2 ...): The proof of the guard conjecture for F2 has failed; see the discussion above about :VERIFY-GUARDS and :GUARD-DEBUG. See :DOC failure. ******** FAILED ******** ACL2 !>(defun f2 (x) ; succeeds; see :DOC evaluation (declare (xargs :guard t)) (ec-call (f1 x))) ; See :DOC evaluation Since F2 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F2. Computing the guard conjecture for F2.... The guard conjecture for F2 is trivial to prove. F2 is compliant with Common Lisp. Summary Form: ( DEFUN F2 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F2 ACL2 !>(trace$ f1 f2) ((F1) (F2)) ACL2 !>(f2 3) ; guard violation 1> (ACL2_*1*_ACL2::F2 3) 2> (F2 3) 3> (ACL2_*1*_ACL2::F1 3) ACL2 Error [Evaluation] in TOP-LEVEL: The guard for the function call (F1 X), which is (CONSP X), is violated by the arguments in the call (F1 3). See :DOC set-guard-checking for information about suppressing this check with (set-guard-checking :none), as recommended for new users. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>(defun f3 (x) (declare (xargs :guard t)) (with-guard-checking nil (f2 x))) Since F3 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F3. Computing the guard conjecture for F3.... The guard conjecture for F3 is trivial to prove. F3 is compliant with Common Lisp. Summary Form: ( DEFUN F3 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F3 ACL2 !>(f3 3) ; logical value (car 3) = nil 1> (F2 3) 2> (ACL2_*1*_ACL2::F1 3) <2 (ACL2_*1*_ACL2::F1 NIL) <1 (F2 NIL) NIL ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun foo (x y) (declare (xargs :measure-debug t)) (if (or (consp x) (consp y)) (1+ (foo (cdr x) (cdr y))) 0)) For the admission of FOO we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (ACL2-COUNT X). The non-trivial part of the measure conjecture is Goal (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y))) (OR (CONSP X) (CONSP Y))) (O< (ACL2-COUNT (CDR X)) (ACL2-COUNT X))). Goal' Subgoal 2 Subgoal 1 Subgoal 1.2 Subgoal 1.2' Subgoal 1.2'' ([ A key checkpoint: Subgoal 1 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y))) (CONSP Y)) (< (ACL2-COUNT (CDR X)) (ACL2-COUNT X))) *1 (Subgoal 1.2'') is pushed for proof by induction: (IMPLIES (AND (EQUAL (ACL2-COUNT X) 0) (NOT (CONSP X)) (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))) (NOT (CONSP Y))). Subgoal 1.1 Subgoal 1.1' ]) Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (ACL2-COUNT X). This suggestion was produced using the :induction rule ACL2-COUNT. If we let (:P X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (NOT (STRINGP X))) (:P X Y)) (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (STRINGP X)) (:P X Y)) (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (COMPLEX-RATIONALP X) (:P (REALPART X) Y) (:P (IMAGPART X) Y)) (:P X Y)) (IMPLIES (AND (NOT (CONSP X)) (RATIONALP X) (NOT (INTEGERP X))) (:P X Y)) (IMPLIES (AND (NOT (CONSP X)) (RATIONALP X) (INTEGERP X)) (:P X Y)) (IMPLIES (AND (CONSP X) (:P (CAR X) Y) (:P (CDR X) Y)) (:P X Y))). This induction is justified by the same argument used to admit ACL2-COUNT. When applied to the goal at hand the above induction scheme produces eight nontautological subgoals. Subgoal *1/8 Subgoal *1/8' Subgoal *1/8'' ([ A key checkpoint while proving *1 (descended from Subgoal 1): Subgoal *1/8' (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (NOT (STRINGP X)) (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))) (NOT (CONSP Y))) *1.1 (Subgoal *1/8'') is pushed for proof by induction. ]) Subgoal *1/7 Subgoal *1/7' Subgoal *1/7'' ([ A key checkpoint while proving *1 (descended from Subgoal 1): Subgoal *1/7' (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (STRINGP X) (EQUAL (LEN (COERCE X 'LIST)) 0) (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))) (NOT (CONSP Y))) *1.2 (Subgoal *1/7'') is pushed for proof by induction. ]) Subgoal *1/6 Subgoal *1/5 Subgoal *1/4 Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' ([ A key checkpoint while proving *1 (descended from Subgoal 1): Subgoal *1/1'' (IMPLIES (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y))) (NOT (CONSP Y))) *1.3 (Subgoal *1/1''') is pushed for proof by induction. ]) So we now return to *1.3, which is (NOT (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))). But the formula above is subsumed by *1.1, which we'll try to prove later. We therefore regard *1.3 as proved (pending the proof of the more general *1.1). Subgoal *1/1'' COMPLETED! We next consider *1.2, which is (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (STRINGP X) (EQUAL (LEN (COERCE X 'LIST)) 0)) (NOT (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y))))). But the formula above is subsumed by *1.1, which we'll try to prove later. We therefore regard *1.2 as proved (pending the proof of the more general *1.1). Subgoal *1/7' COMPLETED! We next consider *1.1, which is (NOT (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))). No induction schemes are suggested by *1.1. Consequently, the proof attempt has failed. ACL2 Error in ( DEFUN FOO ...): The proof of the measure conjecture for FOO has failed. Summary Form: ( DEFUN FOO ...) Rules: ((:DEFINITION ACL2-COUNT) (:DEFINITION INTEGER-ABS) (:DEFINITION LENGTH) (:DEFINITION NOT) (:DEFINITION O-FINP) (:DEFINITION O<) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART <) (:EXECUTABLE-COUNTERPART ACL2-COUNT) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART INTEGERP) (:EXECUTABLE-COUNTERPART NOT) (:FAKE-RUNE-FOR-LINEAR NIL) (:FAKE-RUNE-FOR-LINEAR-EQUALITIES NIL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ACL2-COUNT) (:LINEAR ACL2-COUNT-CAR-CDR-LINEAR) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE COMMUTATIVITY-OF-+) (:REWRITE DEFAULT-CDR) (:TYPE-PRESCRIPTION ACL2-COUNT)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 2645 --- The key checkpoint goals, below, may help you to debug this failure. See :DOC failure and see :DOC set-checkpoint-summary-limit. --- *** Key checkpoint at the top level: *** Subgoal 1 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y))) (CONSP Y)) (< (ACL2-COUNT (CDR X)) (ACL2-COUNT X))) *** Key checkpoint under a top-level induction: *** Subgoal *1/8' (IMPLIES (AND (NOT (CONSP X)) (NOT (RATIONALP X)) (NOT (COMPLEX-RATIONALP X)) (NOT (STRINGP X)) (EXTRA-INFO '(:MEASURE (:RELATION FOO)) '(FOO (CDR X) (CDR Y)))) (NOT (CONSP Y))) ACL2 Error [Failure] in ( DEFUN FOO ...): The proof of the measure conjecture for FOO has failed. See :DOC failure. ******** FAILED ******** ACL2 !>(defun foo (x y) (declare (xargs :measure (+ (acl2-count x) (acl2-count y)))) (if (or (consp x) (consp y)) (1+ (foo (cdr x) (cdr y))) 0)) For the admission of FOO we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (+ (ACL2-COUNT X) (ACL2-COUNT Y)). The non-trivial part of the measure conjecture is Goal (AND (O-P (+ (ACL2-COUNT X) (ACL2-COUNT Y))) (IMPLIES (OR (CONSP X) (CONSP Y)) (O< (+ (ACL2-COUNT (CDR X)) (ACL2-COUNT (CDR Y))) (+ (ACL2-COUNT X) (ACL2-COUNT Y))))). Subgoal 2 Subgoal 1 Subgoal 1.2 Subgoal 1.2.2 Subgoal 1.2.2' Subgoal 1.2.1 Subgoal 1.2.1' Subgoal 1.1 Subgoal 1.1' Subgoal 1.1'' Subgoal 1.1.2 Subgoal 1.1.2' Subgoal 1.1.1 Subgoal 1.1.1' Q.E.D. That completes the proof of the measure theorem for FOO. Thus, we admit this function under the principle of definition. We observe that the type of FOO is described by the theorem (AND (INTEGERP (FOO X Y)) (<= 0 (FOO X Y))). We used primitive type reasoning. Summary Form: ( DEFUN FOO ...) Rules: ((:COMPOUND-RECOGNIZER NATP-COMPOUND-RECOGNIZER) (:DEFINITION ACL2-COUNT) (:DEFINITION FIX) (:DEFINITION NOT) (:DEFINITION O-FINP) (:DEFINITION O-P) (:DEFINITION O<) (:DEFINITION SYNP) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART ACL2-COUNT) (:EXECUTABLE-COUNTERPART BINARY-+) (:FAKE-RUNE-FOR-LINEAR NIL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:LINEAR ACL2-COUNT-CAR-CDR-LINEAR) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE COMMUTATIVITY-2-OF-+) (:REWRITE COMMUTATIVITY-OF-+) (:REWRITE DEFAULT-CDR) (:REWRITE FOLD-CONSTS-IN-+) (:REWRITE UNICITY-OF-0) (:TYPE-PRESCRIPTION ACL2-COUNT)) Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 6439 FOO ACL2 !>(defun f (x) (declare (xargs :measure (f x) :measure-debug t)) (if (and (posp x) (< (f (1- x)) x)) (f (f (1- x))) 0)) For the admission of F we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (F X). The non-trivial part of the measure conjecture is Goal (AND (IMPLIES (EXTRA-INFO '(:MEASURE (:DOMAIN F)) '(O-P (F X))) (O-P (F X))) (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (F (+ -1 X)))) (AND (POSP X) (< (F (+ -1 X)) X))) (O< (F (F (+ -1 X))) (F X))) (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (AND (POSP X) (< (F (+ -1 X)) X))) (O< (F (+ -1 X)) (F X))) (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (POSP X)) (O< (F (+ -1 X)) (F X)))). Subgoal 4 ([ A key checkpoint: Subgoal 4 (IMPLIES (EXTRA-INFO '(:MEASURE (:DOMAIN F)) '(O-P (F X))) (O-P (F X))) *1 (Subgoal 4) is pushed for proof by induction. ]) Subgoal 3 ([ A key checkpoint: Subgoal 3 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (F (+ -1 X)))) (INTEGERP X) (< 0 X) (< (F (+ -1 X)) X)) (O< (F (F (+ -1 X))) (F X))) *2 (Subgoal 3) is pushed for proof by induction. ]) Subgoal 2 ([ A key checkpoint: Subgoal 2 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (INTEGERP X) (< 0 X) (< (F (+ -1 X)) X)) (O< (F (+ -1 X)) (F X))) *3 (Subgoal 2) is pushed for proof by induction. ]) Subgoal 1 ([ A key checkpoint: Subgoal 1 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (INTEGERP X) (< 0 X)) (O< (F (+ -1 X)) (F X))) *4 (Subgoal 1) is pushed for proof by induction. ]) No induction schemes are suggested by *4. Consequently, the proof attempt has failed. ACL2 Error in ( DEFUN F ...): The proof of the measure conjecture for F has failed. Summary Form: ( DEFUN F ...) Rules: ((:DEFINITION NOT) (:DEFINITION POSP)) Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 2266 --- The key checkpoint goals, below, may help you to debug this failure. See :DOC failure and see :DOC set-checkpoint-summary-limit. --- *** Key checkpoints at the top level: *** Subgoal 4 (IMPLIES (EXTRA-INFO '(:MEASURE (:DOMAIN F)) '(O-P (F X))) (O-P (F X))) Subgoal 3 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (F (+ -1 X)))) (INTEGERP X) (< 0 X) (< (F (+ -1 X)) X)) (O< (F (F (+ -1 X))) (F X))) Subgoal 2 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (INTEGERP X) (< 0 X) (< (F (+ -1 X)) X)) (O< (F (+ -1 X)) (F X))) Subgoal 1 (IMPLIES (AND (EXTRA-INFO '(:MEASURE (:RELATION F)) '(F (+ -1 X))) (INTEGERP X) (< 0 X)) (O< (F (+ -1 X)) (F X))) ACL2 Error [Failure] in ( DEFUN F ...): The proof of the measure conjecture for F has failed. See :DOC failure. ******** FAILED ******** ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun f1 (x) x) Since F1 is non-recursive, its admission is trivial. We observe that the type of F1 is described by the theorem (EQUAL (F1 X) X). Summary Form: ( DEFUN F1 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F1 ACL2 !>(defun f2 (x) x) Since F2 is non-recursive, its admission is trivial. We observe that the type of F2 is described by the theorem (EQUAL (F2 X) X). Summary Form: ( DEFUN F2 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F2 ACL2 !>(defun f3 (x) x) Since F3 is non-recursive, its admission is trivial. We observe that the type of F3 is described by the theorem (EQUAL (F3 X) X). Summary Form: ( DEFUN F3 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F3 ACL2 !>(defun f4 (x) x) Since F4 is non-recursive, its admission is trivial. We observe that the type of F4 is described by the theorem (EQUAL (F4 X) X). Summary Form: ( DEFUN F4 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F4 ACL2 !>:pbt 0 0 (EXIT-BOOT-STRAP-MODE) L 1 (DEFUN F1 (X) ...) L 2 (DEFUN F2 (X) ...) L 3 (DEFUN F3 (X) ...) L 4:x(DEFUN F4 (X) ...) ACL2 !>:ubt f2 L 1:x(DEFUN F1 (X) ...) ACL2 !>:pbt 0 0 (EXIT-BOOT-STRAP-MODE) L 1:x(DEFUN F1 (X) ...) ACL2 !>:oops ACL2 Observation in OOPS-WARNING: Installing the requested world. L 4:x(DEFUN F4 (X) ...) ACL2 !>:pbt 0 0 (EXIT-BOOT-STRAP-MODE) L 1 (DEFUN F1 (X) ...) L 2 (DEFUN F2 (X) ...) L 3 (DEFUN F3 (X) ...) L 4:x(DEFUN F4 (X) ...) ACL2 !>:ubu f2 L 2:x(DEFUN F2 (X) ...) ACL2 !>:pbt 0 0 (EXIT-BOOT-STRAP-MODE) L 1 (DEFUN F1 (X) ...) L 2:x(DEFUN F2 (X) ...) ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun foo (x) (declare (xargs :guard (and (integerp x) (posp (+ -2 x)) (posp (+ 3 x)) (posp (+ -4 x))))) x) Since FOO is non-recursive, its admission is trivial. We observe that the type of FOO is described by the theorem (EQUAL (FOO X) X). Computing the guard conjecture for FOO.... The guard conjecture for FOO is trivial to prove. FOO is compliant with Common Lisp. Summary Form: ( DEFUN FOO ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) FOO ACL2 !>(foo -1) ACL2 Error [Evaluation] in TOP-LEVEL: The guard for the function call (FOO X), which is (AND (INTEGERP X) (POSP (+ -2 X)) (POSP (+ 3 X)) (POSP (+ -4 X))), is violated by the arguments in the call (FOO -1). See :DOC set-guard-checking for information about suppressing this check with (set-guard-checking :none), as recommended for new users. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>:print-gv (FLET ((FOO{GUARD} (X) (DECLARE (IGNORABLE X)) (AND (INTEGERP X) (POSP (+ -2 X)) (POSP (+ 3 X)) (POSP (+ -4 X))))) (FOO{GUARD} -1)) ACL2 !>"Evaluate the resulting FLET form, as is and with LIST replacing AND." "Evaluate the resulting FLET form, as is and with LIST replacing AND." ACL2 !>(FLET ((FOO{GUARD} (X) (DECLARE (IGNORABLE X)) (AND (INTEGERP X) (POSP (+ -2 X)) (POSP (+ 3 X)) (POSP (+ -4 X))))) (FOO{GUARD} -1)) NIL ACL2 !>(FLET ((FOO{GUARD} (X) (DECLARE (IGNORABLE X)) (list (INTEGERP X) (POSP (+ -2 X)) (POSP (+ 3 X)) (POSP (+ -4 X))))) (FOO{GUARD} -1)) (T NIL T NIL) ACL2 !>(print-gv :conjunct t) Showing guard conjunct (#2 of 4) that evaluates to nil: (FLET ((FOO{GUARD} (X) (POSP (+ -2 X)))) (FOO{GUARD} -1)). ACL2 !>(FLET ((FOO{GUARD} (X) (POSP (+ -2 X)))) (FOO{GUARD} -1)) NIL ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(fmt-to-string "Big list: ~x0" (list (cons #\0 (make-list 30)))) (0 " Big list: (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) ") ACL2 !>(fmt-to-string "Big list: ~x0" (list (cons #\0 (make-list 30))) :fmt-control-alist '((fmt-soft-right-margin . 10000) (fmt-hard-right-margin . 10000))) (131 " Big list: (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)") ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(include-book "centaur/memoize/old/profile" :dir :system) TTAG NOTE (for included book): Adding ttag :PROFILE from book /Users/kaufmann/acl2/acl2/books/centaur/memoize/old/profile. ACL2 Warning [Ttags] in ( INCLUDE-BOOK "centaur/memoize/old/profile" ...): The ttag note just printed to the terminal indicates a modification to ACL2. To avoid this warning, supply an explicit :TTAGS argument when including the book "/Users/kaufmann/acl2/acl2/books/centaur/memoize/old/profile". Summary Form: ( INCLUDE-BOOK "centaur/memoize/old/profile" ...) Rules: NIL Warnings: Ttags Time: 0.10 seconds (prove: 0.00, print: 0.00, other: 0.10) "/Users/kaufmann/acl2/acl2/books/centaur/memoize/old/profile.lisp" ACL2 !>(time$ (profile-acl2)) Profiling 6,271 functions. ACL2 Observation in MEMOIZE-CALL-ARRAY-GROW: Now reinitializing memoization structures. This will erase saved values and statistics. (clear-memoize-statistics) invoked. 6271 functions newly profiled. ; (EV-REC *RETURN-LAST-ARG3* ...) took ; 10.02 seconds realtime, 10.03 seconds runtime ; (4,287,344,960 bytes allocated). NIL ACL2 !>:mini-proveall Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>>:LOGIC The event ( TABLE ACL2-DEFAULTS-TABLE ...) is redundant. See :DOC redundant-events. ACL2 !>>(THM (IMPLIES (AND (TRUE-LISTP X) (TRUE-LISTP Y)) (EQUAL (REVAPPEND (APPEND X Y) Z) (REVAPPEND Y (REVAPPEND X Z))))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Five 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 (REVAPPEND X Z), while accommodating (APPEND X Y) and (TRUE-LISTP X). These suggestions were produced using the :induction rules BINARY-APPEND, REVAPPEND and TRUE-LISTP. If we let (:P X Y Z) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ENDP X)) (:P (CDR X) Y (CONS (CAR X) Z))) (:P X Y Z)) (IMPLIES (ENDP X) (:P X Y Z))). This induction is justified by the same argument used to admit REVAPPEND. Note, however, that the unmeasured variable Z is being instantiated. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( THM ...) Rules: ((:DEFINITION BINARY-APPEND) (:DEFINITION ENDP) (:DEFINITION NOT) (:DEFINITION REVAPPEND) (:DEFINITION TRUE-LISTP) (:EXECUTABLE-COUNTERPART CONSP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION BINARY-APPEND) (:INDUCTION REVAPPEND) (:INDUCTION TRUE-LISTP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION TRUE-LISTP-APPEND)) Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 668 Proof succeeded. ACL2 !>>(DEFUN APP (X Y) (IF (CONSP X) (CONS (CAR X) (APP (CDR X) Y)) Y)) The admission of APP 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 X). We observe that the type of APP is described by the theorem (OR (CONSP (APP X Y)) (EQUAL (APP X Y) Y)). We used primitive type reasoning. Summary Form: ( DEFUN APP ...) Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) APP ACL2 !>>(DEFTHM ASSOC-OF-APP (EQUAL (APP (APP A B) C) (APP A (APP B C)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. Subsumption reduces that number to two. However, one of these is flawed and so we are left with one viable candidate. We will induct according to a scheme suggested by (APP A B), while accommodating (APP A (APP B C)). These suggestions were produced using the :induction rule APP. If we let (:P A B C) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP A)) (:P A B C)) (IMPLIES (AND (CONSP A) (:P (CDR A) B C)) (:P A B C))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM ASSOC-OF-APP ...) Rules: ((:DEFINITION APP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 357 ASSOC-OF-APP ACL2 !>>(DEFUN REV (X) (IF (CONSP X) (APP (REV (CDR X)) (CONS (CAR X) NIL)) NIL)) The admission of REV 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 X). We observe that the type of REV is described by the theorem (OR (CONSP (REV X)) (EQUAL (REV X) NIL)). We used primitive type reasoning and the :type-prescription rule APP. Summary Form: ( DEFUN REV ...) Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL) (:TYPE-PRESCRIPTION APP)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) REV ACL2 !>>(DEFTHM TRUE-LISTP-REV (TRUE-LISTP (REV X)) :RULE-CLASSES (:REWRITE :GENERALIZE)) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (REV X). This suggestion was produced using the :induction rule REV. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X)) (IMPLIES (AND (CONSP X) (:P (CDR X))) (:P X))). This induction is justified by the same argument used to admit REV. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' Subgoal *1/1'4' ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/1' (IMPLIES (AND (CONSP X) (TRUE-LISTP (REV (CDR X)))) (TRUE-LISTP (APP (REV (CDR X)) (LIST (CAR X))))) *1.1 (Subgoal *1/1'4') is pushed for proof by induction. ]) So we now return to *1.1, which is (IMPLIES (TRUE-LISTP RV) (TRUE-LISTP (APP RV (LIST X1)))). Subgoal *1.1/3 Subgoal *1.1/2 Subgoal *1.1/1 *1.1 and *1 are COMPLETED! Thus key checkpoints Subgoal *1/1' and Goal are COMPLETED! Q.E.D. The storage of TRUE-LISTP-REV depends upon the :type-prescription rule TRUE-LISTP. Summary Form: ( DEFTHM TRUE-LISTP-REV ...) Rules: ((:DEFINITION APP) (:DEFINITION REV) (:DEFINITION TRUE-LISTP) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART TRUE-LISTP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:INDUCTION REV) (:INDUCTION TRUE-LISTP) (:TYPE-PRESCRIPTION APP) (:TYPE-PRESCRIPTION TRUE-LISTP)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 786 TRUE-LISTP-REV ACL2 !>>(DEFTHM REV-APP-PROOF-BUILDER (EQUAL (REV (APP A B)) (APP (REV B) (REV A))) :RULE-CLASSES NIL :INSTRUCTIONS (:INDUCT :BASH :INDUCT :BASH :SPLIT (:DV 1) :X :NX (:DV 1) :X :TOP :S :BASH (:DIVE 1 1) := (:DROP 2) :TOP :BASH)) Entering the proof-builder.... ->: :INDUCT ***** Now entering the theorem prover ***** *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. We have been told to use induction. Three induction schemes are suggested by this conjecture. Subsumption reduces that number to two. However, one of these is flawed and so we are left with one viable candidate. We will induct according to a scheme suggested by (APP A B), while accommodating (REV A). These suggestions were produced using the :induction rules APP and REV. If we let (:P A B) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP A)) (:P A B)) (IMPLIES (AND (CONSP A) (:P (CDR A) B)) (:P A B))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/2 (IMPLIES (NOT (CONSP A)) (EQUAL (REV (APP A B)) (APP (REV B) (REV A)))) Subgoal *1/2 is subsumed by a goal yet to be proved. ]) Subgoal *1/1 ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/1 (IMPLIES (AND (CONSP A) (EQUAL (REV (APP (CDR A) B)) (APP (REV B) (REV (CDR A))))) (EQUAL (REV (APP A B)) (APP (REV B) (REV A)))) Subgoal *1/1 is subsumed by a goal yet to be proved. ]) *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Creating two new goals: (MAIN . 1) and (MAIN . 2). The proof of the current goal, MAIN, has been completed. However, the following subgoals remain to be proved: (MAIN . 1) and (MAIN . 2). Now proving (MAIN . 1). ->: :BASH ***** Now entering the theorem prover ***** Goal' ([ A key checkpoint: Goal' (IMPLIES (NOT (CONSP A)) (EQUAL (REV B) (APP (REV B) NIL))) Goal' is subsumed by a goal yet to be proved. ]) Q.E.D. Creating one new goal: ((MAIN . 1) . 1). The proof of the current goal, (MAIN . 1), has been completed. However, the following subgoals remain to be proved: ((MAIN . 1) . 1). Now proving ((MAIN . 1) . 1). ->: :INDUCT ***** Now entering the theorem prover ***** *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. We have been told to use induction. Two induction schemes are suggested by this conjecture. Subsumption reduces that number to one. We will induct according to a scheme suggested by (REV B), while ac- commodating (REV B). These suggestions were produced using the :induction rule REV. If we let (:P A B) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP B)) (:P A B)) (IMPLIES (AND (CONSP B) (:P A (CDR B))) (:P A B))). This induction is justified by the same argument used to admit REV. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/2 (IMPLIES (NOT (CONSP B)) (IMPLIES (NOT (CONSP A)) (EQUAL (REV B) (APP (REV B) NIL)))) Subgoal *1/2 is subsumed by a goal yet to be proved. ]) Subgoal *1/1 ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/1 (IMPLIES (AND (CONSP B) (IMPLIES (NOT (CONSP A)) (EQUAL (REV (CDR B)) (APP (REV (CDR B)) NIL)))) (IMPLIES (NOT (CONSP A)) (EQUAL (REV B) (APP (REV B) NIL)))) Subgoal *1/1 is subsumed by a goal yet to be proved. ]) *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Creating two new goals: (((MAIN . 1) . 1) . 1) and (((MAIN . 1) . 1) . 2). The proof of the current goal, ((MAIN . 1) . 1), has been completed. However, the following subgoals remain to be proved: (((MAIN . 1) . 1) . 1) and (((MAIN . 1) . 1) . 2). Now proving (((MAIN . 1) . 1) . 1). ->: :BASH ***** Now entering the theorem prover ***** Goal' Q.E.D. The proof of the current goal, (((MAIN . 1) . 1) . 1), has been completed, as have all of its subgoals. Now proving (((MAIN . 1) . 1) . 2). ->: :SPLIT ***** Now entering the theorem prover ***** Goal' Goal'' ([ A key checkpoint: Goal'' (IMPLIES (AND (CONSP B) (EQUAL (REV (CDR B)) (APP (REV (CDR B)) NIL)) (NOT (CONSP A))) (EQUAL (REV B) (APP (REV B) NIL))) Goal'' is subsumed by a goal yet to be proved. ]) Q.E.D. Creating one new goal: ((((MAIN . 1) . 1) . 2) . 1). The proof of the current goal, (((MAIN . 1) . 1) . 2), has been completed. However, the following subgoals remain to be proved: ((((MAIN . 1) . 1) . 2) . 1). Now proving ((((MAIN . 1) . 1) . 2) . 1). ->: (:DV 1) ->: :X #->: (EXPAND T) #->: (SUCCEED (S)) ##->: (S) ->: :NX #->: UP #->: 2 ->: (:DV 1) ->: :X #->: (EXPAND T) #->: (SUCCEED (S)) ##->: (S) ->: :TOP ->: :S The proof of the current goal, ((((MAIN . 1) . 1) . 2) . 1), has been completed, as have all of its subgoals. Now proving (MAIN . 2). ->: :BASH ***** Now entering the theorem prover ***** Goal' ([ A key checkpoint: Goal' (IMPLIES (AND (CONSP A) (EQUAL (REV (APP (CDR A) B)) (APP (REV B) (REV (CDR A))))) (EQUAL (APP (REV (APP (CDR A) B)) (LIST (CAR A))) (APP (REV B) (APP (REV (CDR A)) (LIST (CAR A)))))) Goal' is subsumed by a goal yet to be proved. ]) Q.E.D. Creating one new goal: ((MAIN . 2) . 1). The proof of the current goal, (MAIN . 2), has been completed. However, the following subgoals remain to be proved: ((MAIN . 2) . 1). Now proving ((MAIN . 2) . 1). ->: (:DIVE 1 1) ->: := Using hypothesis #2. ->: (:DROP 2) ->: :TOP ->: :BASH ***** Now entering the theorem prover ***** Q.E.D. *!*!*!*!*!*!* All goals have been proved! *!*!*!*!*!*!* Summary Form: ( DEFTHM REV-APP-PROOF-BUILDER ...) Rules: ((:DEFINITION APP) (:DEFINITION NOT) (:DEFINITION REV) (:EXECUTABLE-COUNTERPART APP) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART IF) (:EXECUTABLE-COUNTERPART NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:INDUCTION REV) (:REWRITE ASSOC-OF-APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.05 seconds (prove: 0.02, print: 0.01, other: 0.02) Prover steps counted: 1857 REV-APP-PROOF-BUILDER ACL2 !>>(DEFTHM REV-APP (EQUAL (REV (APP A B)) (APP (REV B) (REV A)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. Subsumption reduces that number to two. However, one of these is flawed and so we are left with one viable candidate. We will induct according to a scheme suggested by (APP A B), while accommodating (REV A). These suggestions were produced using the :induction rules APP and REV. If we let (:P A B) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP A)) (:P A B)) (IMPLIES (AND (CONSP A) (:P (CDR A) B)) (:P A B))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/2' Subgoal *1/2'' Subgoal *1/2''' ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/2' (IMPLIES (NOT (CONSP A)) (EQUAL (REV B) (APP (REV B) NIL))) *1.1 (Subgoal *1/2''') is pushed for proof by induction. ]) Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' Subgoal *1/1'4' So we now return to *1.1, which is (IMPLIES (TRUE-LISTP RV) (EQUAL RV (APP RV NIL))). Subgoal *1.1/3 Subgoal *1.1/2 Subgoal *1.1/1 *1.1 and *1 are COMPLETED! Thus key checkpoints Subgoal *1/2' and Goal are COMPLETED! Q.E.D. Summary Form: ( DEFTHM REV-APP ...) Rules: ((:DEFINITION APP) (:DEFINITION REV) (:DEFINITION TRUE-LISTP) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART APP) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART EQUAL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:GENERALIZE TRUE-LISTP-REV) (:INDUCTION APP) (:INDUCTION REV) (:INDUCTION TRUE-LISTP) (:REWRITE ASSOC-OF-APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE CONS-CAR-CDR)) Time: 0.02 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 2149 REV-APP ACL2 !>>(DEFTHM REV-REV (IMPLIES (TRUE-LISTP X) (EQUAL (REV (REV X)) X))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. Subsumption reduces that number to one. We will induct according to a scheme suggested by (REV X), while ac- commodating (TRUE-LISTP X). These suggestions were produced using the :induction rules REV and TRUE-LISTP. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X)) (IMPLIES (AND (CONSP X) (:P (CDR X))) (:P X))). This induction is justified by the same argument used to admit REV. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM REV-REV ...) Rules: ((:DEFINITION APP) (:DEFINITION REV) (:DEFINITION TRUE-LISTP) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART REV) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION REV) (:INDUCTION TRUE-LISTP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE CONS-CAR-CDR) (:REWRITE REV-APP)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 373 REV-REV ACL2 !>>(ENCAPSULATE (((LT * *) => *)) (LOCAL (DEFUN LT (X Y) (DECLARE (IGNORE X Y)) NIL)) (DEFTHM LT-NON-SYMMETRIC (IMPLIES (LT X Y) (NOT (LT Y X))))) To verify that the two encapsulated events correctly extend the current theory we will evaluate them. The theory thus constructed is only ephemeral. Encapsulated Events: ACL2 !>>>(LOCAL (DEFUN LT (X Y) (DECLARE (IGNORE X Y)) NIL)) Since LT is non-recursive, its admission is trivial. We observe that the type of LT is described by the theorem (EQUAL (LT X Y) NIL). Summary Form: ( DEFUN LT ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) LT ACL2 !>>>(DEFTHM LT-NON-SYMMETRIC (IMPLIES (LT X Y) (NOT (LT Y X)))) ACL2 Warning [Non-rec] in ( DEFTHM LT-NON-SYMMETRIC ...): A :REWRITE rule generated from LT-NON-SYMMETRIC will be triggered only by terms containing the function symbol LT, which has a non-recursive definition. Unless this definition is disabled, this rule is unlikely ever to be used. ACL2 Warning [Subsume] in ( DEFTHM LT-NON-SYMMETRIC ...): The previously added rule LT subsumes a newly proposed :REWRITE rule generated from LT-NON-SYMMETRIC, in the sense that the old rule rewrites a more general target. Because the new rule will be tried first, it may nonetheless find application. Q.E.D. Summary Form: ( DEFTHM LT-NON-SYMMETRIC ...) Rules: ((:TYPE-PRESCRIPTION LT)) Warnings: Subsume and Non-rec Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) LT-NON-SYMMETRIC End of Encapsulated Events. Having verified that the encapsulated events validate the signatures of the ENCAPSULATE event, we discard the ephemeral theory and extend the original theory as directed by the signatures and the non-LOCAL events. The following constraint is associated with the function LT: (IMPLIES (LT X Y) (NOT (LT Y X))) Summary Form: ( ENCAPSULATE (((LT * ...) ...) ...) ...) Rules: NIL Warnings: Subsume and Non-rec Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.01) LT ACL2 !>>(DEFUN INSERT (X LST) (COND ((ATOM LST) (LIST X)) ((LT X (CAR LST)) (CONS X LST)) (T (CONS (CAR LST) (INSERT X (CDR LST)))))) The admission of INSERT 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 INSERT is described by the theorem (CONSP (INSERT X LST)). We used primitive type reasoning. Summary Form: ( DEFUN INSERT ...) Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) INSERT ACL2 !>>(DEFUN INSERT-SORT (LST) (COND ((ATOM LST) NIL) (T (INSERT (CAR LST) (INSERT-SORT (CDR LST)))))) The admission of INSERT-SORT 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 INSERT-SORT is described by the theorem (OR (CONSP (INSERT-SORT LST)) (EQUAL (INSERT-SORT LST) NIL)). We used the :type-prescription rule INSERT. Summary Form: ( DEFUN INSERT-SORT ...) Rules: ((:TYPE-PRESCRIPTION INSERT)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) INSERT-SORT ACL2 !>>(DEFUN DEL (X LST) (COND ((ATOM LST) NIL) ((EQUAL X (CAR LST)) (CDR LST)) (T (CONS (CAR LST) (DEL X (CDR LST)))))) The admission of DEL 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 could deduce no constraints on the type of DEL. Summary Form: ( DEFUN DEL ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) DEL ACL2 !>>(DEFUN MEM (X LST) (COND ((ATOM LST) NIL) ((EQUAL X (CAR LST)) T) (T (MEM X (CDR LST))))) The admission of MEM 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 MEM is described by the theorem (OR (EQUAL (MEM X LST) T) (EQUAL (MEM X LST) NIL)). Summary Form: ( DEFUN MEM ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) MEM ACL2 !>>(DEFUN PERM (LST1 LST2) (COND ((ATOM LST1) (ATOM LST2)) ((MEM (CAR LST1) LST2) (PERM (CDR LST1) (DEL (CAR LST1) LST2))) (T NIL))) The admission of PERM 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 LST1). We observe that the type of PERM is described by the theorem (OR (EQUAL (PERM LST1 LST2) T) (EQUAL (PERM LST1 LST2) NIL)). Summary Form: ( DEFUN PERM ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) PERM ACL2 !>>(DEFTHM PERM-REFLEXIVE (PERM X X)) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (PERM X X). This suggestion was produced using the :induction rule PERM. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (MEM (CAR X) X))) (:P X)) (IMPLIES (AND (NOT (ATOM X)) (MEM (CAR X) X) (:P (CDR X))) (:P X)) (IMPLIES (ATOM X) (:P X))). This induction is justified by the same argument used to admit PERM. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of PERM-REFLEXIVE depends upon the :type-prescription rule PERM. Summary Form: ( DEFTHM PERM-REFLEXIVE ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION MEM) (:DEFINITION NOT) (:DEFINITION PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION PERM) (:TYPE-PRESCRIPTION PERM)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 315 PERM-REFLEXIVE ACL2 !>>(DEFTHM PERM-CONS (IMPLIES (MEM A X) (EQUAL (PERM X (CONS A Y)) (PERM (DEL A X) Y))) :HINTS (("Goal" :INDUCT (PERM X Y)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. We have been told to use induction. One induction scheme is suggested by the induction hint. We will induct according to a scheme suggested by (PERM X Y). This suggestion was produced using the :induction rule PERM. If we let (:P A X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (MEM (CAR X) Y))) (:P A X Y)) (IMPLIES (AND (NOT (ATOM X)) (MEM (CAR X) Y) (:P A (CDR X) (DEL (CAR X) Y))) (:P A X Y)) (IMPLIES (ATOM X) (:P A X Y))). This induction is justified by the same argument used to admit PERM. Note, however, that the unmeasured variable Y is being instantiated. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Subgoal *1/3'' Subgoal *1/3''' Subgoal *1/2 Subgoal *1/2' Splitter note (see :DOC splitter) for Subgoal *1/2' (2 subgoals). if-intro: ((:DEFINITION DEL) (:DEFINITION MEM)) Subgoal *1/2.2 Subgoal *1/2.1 Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM PERM-CONS ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION MEM) (:DEFINITION NOT) (:DEFINITION PERM) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART EQUAL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION PERM) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION MEM)) Splitter rules (see :DOC splitter): if-intro: ((:DEFINITION DEL) (:DEFINITION MEM)) Time: 0.03 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 3880 PERM-CONS ACL2 !>>(DEFTHM PERM-SYMMETRIC (IMPLIES (PERM X Y) (PERM Y X))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. We will choose arbitrarily among these. We will induct according to a scheme suggested by (PERM X Y). This suggestion was produced using the :induction rule PERM. If we let (:P X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (MEM (CAR X) Y))) (:P X Y)) (IMPLIES (AND (NOT (ATOM X)) (MEM (CAR X) Y) (:P (CDR X) (DEL (CAR X) Y))) (:P X Y)) (IMPLIES (ATOM X) (:P X Y))). This induction is justified by the same argument used to admit PERM. Note, however, that the unmeasured variable Y is being instantiated. When applied to the goal at hand the above induction scheme produces four nontautological subgoals. Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/3'' Subgoal *1/3''' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of PERM-SYMMETRIC depends upon the :type-prescription rule PERM. Summary Form: ( DEFTHM PERM-SYMMETRIC ...) Rules: ((:DEFINITION ATOM) (:DEFINITION NOT) (:DEFINITION PERM) (:ELIM CAR-CDR-ELIM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION PERM) (:REWRITE PERM-CONS) (:TYPE-PRESCRIPTION MEM) (:TYPE-PRESCRIPTION PERM)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1789 PERM-SYMMETRIC ACL2 !>>(DEFTHM MEM-DEL (IMPLIES (MEM A (DEL B X)) (MEM A X)) :RULE-CLASSES ((:REWRITE :MATCH-FREE :ONCE))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (MEM A X), while accommodating (DEL B X). These suggestions were produced using the :induction rules DEL and MEM. If we let (:P A B X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (EQUAL A (CAR X))) (:P A B (CDR X))) (:P A B X)) (IMPLIES (AND (NOT (ATOM X)) (EQUAL A (CAR X))) (:P A B X)) (IMPLIES (ATOM X) (:P A B X))). This induction is justified by the same argument used to admit MEM. When applied to the goal at hand the above induction scheme produces four nontautological subgoals. Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/3'' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of MEM-DEL depends upon the :type-prescription rule MEM. Summary Form: ( DEFTHM MEM-DEL ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION MEM) (:DEFINITION NOT) (:EXECUTABLE-COUNTERPART CONSP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION DEL) (:INDUCTION MEM) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION MEM)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 865 MEM-DEL ACL2 !>>(DEFTHM PERM-MEM (IMPLIES (AND (PERM X Y) (MEM A X)) (MEM A Y)) :RULE-CLASSES ((:REWRITE :MATCH-FREE :ONCE))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. 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 (MEM A X), while accommodating (PERM X Y). These suggestions were produced using the :induction rules MEM and PERM. If we let (:P A X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (EQUAL A (CAR X))) (:P A (CDR X) (DEL (CAR X) Y))) (:P A X Y)) (IMPLIES (AND (NOT (ATOM X)) (EQUAL A (CAR X))) (:P A X Y)) (IMPLIES (ATOM X) (:P A X Y))). This induction is justified by the same argument used to admit MEM. Note, however, that the unmeasured variable Y is being instantiated. When applied to the goal at hand the above induction scheme produces five nontautological subgoals. Subgoal *1/5 Subgoal *1/5' Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of PERM-MEM depends upon the :type-prescription rule MEM. Summary Form: ( DEFTHM PERM-MEM ...) Rules: ((:DEFINITION ATOM) (:DEFINITION MEM) (:DEFINITION NOT) (:DEFINITION PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION MEM) (:INDUCTION PERM) (:REWRITE MEM-DEL) (:TYPE-PRESCRIPTION MEM)) Time: 0.02 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 1367 PERM-MEM ACL2 !>>(DEFTHM MEM-DEL2 (IMPLIES (AND (MEM A X) (NOT (EQUAL A B))) (MEM A (DEL B X)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (DEL B X), while accommodating (MEM A X). These suggestions were produced using the :induction rules DEL and MEM. If we let (:P A B X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (EQUAL B (CAR X))) (:P A B (CDR X))) (:P A B X)) (IMPLIES (AND (NOT (ATOM X)) (EQUAL B (CAR X))) (:P A B X)) (IMPLIES (ATOM X) (:P A B X))). This induction is justified by the same argument used to admit DEL. When applied to the goal at hand the above induction scheme produces four nontautological subgoals. Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of MEM-DEL2 depends upon the :type-prescription rule MEM. Summary Form: ( DEFTHM MEM-DEL2 ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION MEM) (:DEFINITION NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION DEL) (:INDUCTION MEM) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION MEM)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 752 MEM-DEL2 ACL2 !>>(DEFTHM COMM-DEL (EQUAL (DEL A (DEL B X)) (DEL B (DEL A X)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (DEL A X), while accommodating (DEL B X). These suggestions were produced using the :induction rule DEL. If we let (:P A B X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (EQUAL A (CAR X))) (:P A B (CDR X))) (:P A B X)) (IMPLIES (AND (NOT (ATOM X)) (EQUAL A (CAR X))) (:P A B X)) (IMPLIES (ATOM X) (:P A B X))). This induction is justified by the same argument used to admit DEL. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Subgoal *1/3'' Subgoal *1/2 Subgoal *1/2' Splitter note (see :DOC splitter) for Subgoal *1/2' (2 subgoals). if-intro: ((:DEFINITION DEL)) Subgoal *1/2.2 Subgoal *1/2.1 Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM COMM-DEL ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION NOT) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART EQUAL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION DEL) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Splitter rules (see :DOC splitter): if-intro: ((:DEFINITION DEL)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1148 COMM-DEL ACL2 !>>(DEFTHM PERM-DEL (IMPLIES (PERM X Y) (PERM (DEL A X) (DEL A Y)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. 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 (DEL A X), while accommodating (PERM X Y). These suggestions were produced using the :induction rules DEL and PERM. If we let (:P A X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (EQUAL A (CAR X))) (:P A (CDR X) (DEL (CAR X) Y))) (:P A X Y)) (IMPLIES (AND (NOT (ATOM X)) (EQUAL A (CAR X))) (:P A X Y)) (IMPLIES (ATOM X) (:P A X Y))). This induction is justified by the same argument used to admit DEL. Note, however, that the unmeasured variable Y is being instantiated. When applied to the goal at hand the above induction scheme produces four nontautological subgoals. Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of PERM-DEL depends upon the :type-prescription rule PERM. Summary Form: ( DEFTHM PERM-DEL ...) Rules: ((:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION NOT) (:DEFINITION PERM) (:EXECUTABLE-COUNTERPART PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION DEL) (:INDUCTION PERM) (:REWRITE COMM-DEL) (:REWRITE MEM-DEL2) (:REWRITE PERM-CONS) (:REWRITE PERM-SYMMETRIC) (:TYPE-PRESCRIPTION MEM) (:TYPE-PRESCRIPTION PERM)) Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1894 PERM-DEL ACL2 !>>(DEFTHM PERM-TRANSITIVE (IMPLIES (AND (PERM X Y) (PERM Y Z)) (PERM X Z)) :RULE-CLASSES ((:REWRITE :MATCH-FREE :ONCE))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. 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 (PERM X Z), while accommodating (PERM X Y). These suggestions were produced using the :induction rule PERM. If we let (:P X Y Z) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (MEM (CAR X) Z))) (:P X Y Z)) (IMPLIES (AND (NOT (ATOM X)) (MEM (CAR X) Z) (:P (CDR X) (DEL (CAR X) Y) (DEL (CAR X) Z))) (:P X Y Z)) (IMPLIES (ATOM X) (:P X Y Z))). This induction is justified by the same argument used to admit PERM. Note, however, that the unmeasured variables Y and Z are being instantiated. When applied to the goal at hand the above induction scheme produces five nontautological subgoals. Subgoal *1/5 Subgoal *1/5' Subgoal *1/5'' Subgoal *1/4 Subgoal *1/4' Subgoal *1/3 Subgoal *1/3' Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of PERM-TRANSITIVE depends upon the :type-prescription rule PERM. Summary Form: ( DEFTHM PERM-TRANSITIVE ...) Rules: ((:DEFINITION ATOM) (:DEFINITION NOT) (:DEFINITION PERM) (:INDUCTION PERM) (:REWRITE PERM-DEL) (:REWRITE PERM-MEM) (:REWRITE PERM-SYMMETRIC) (:TYPE-PRESCRIPTION MEM) (:TYPE-PRESCRIPTION PERM)) Time: 0.02 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 2379 PERM-TRANSITIVE ACL2 !>>(DEFEQUIV PERM) ACL2 Warning [Equiv] in ( DEFTHM PERM-IS-AN-EQUIVALENCE ...): Any lemma about (PERM X Y), proved before PERM is marked as an equivalence relation, is stored so as to rewrite (PERM X Y) to T. After PERM is known to be an equivalence relation, such a rule would rewrite the left-hand side to the right-hand side, preserving PERM. You have previously proved one possibly problematic rule about PERM, namely PERM-DEL. After PERM is marked as an equivalence relation you should reconsider this problematic rule. If the rule is merely in support of establishing that PERM is an equivalence relation, it may be appropriate to disable it permanently hereafter. If the rule is now intended to rewrite left to right, you must prove the lemma again after PERM is known to be an equivalence relation. Subgoal 2 Subgoal 1 Q.E.D. Summary Form: ( DEFTHM PERM-IS-AN-EQUIVALENCE ...) Rules: ((:EXECUTABLE-COUNTERPART TAU-SYSTEM) (:REWRITE PERM-REFLEXIVE) (:REWRITE PERM-SYMMETRIC) (:REWRITE PERM-TRANSITIVE) (:TYPE-PRESCRIPTION PERM)) Warnings: Equiv Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 453 Summary Form: ( MAKE-EVENT (DEFEQUIV-FORM ...)) Rules: NIL Warnings: Equiv Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 453 PERM-IS-AN-EQUIVALENCE ACL2 !>>(IN-THEORY (DISABLE PERM PERM-REFLEXIVE PERM-SYMMETRIC PERM-TRANSITIVE)) Summary Form: ( IN-THEORY (DISABLE ...)) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) (:NUMBER-OF-ENABLED-RUNES 5592) ACL2 !>>(DEFCONG PERM PERM (CONS X Y) 2) Q.E.D. Summary Form: ( DEFTHM PERM-IMPLIES-PERM-CONS-2 ...) Rules: ((:DEFINITION DEL) (:DEFINITION MEM) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE PERM-CONS)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 74 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 74 PERM-IMPLIES-PERM-CONS-2 ACL2 !>>(DEFCONG PERM IFF (MEM X Y) 2) ACL2 Warning [Equiv] in ( DEFTHM PERM-IMPLIES-IFF-MEM-2 ...): The :CONGRUENCE rule PERM-IMPLIES-IFF-MEM-2 can be strengthened by replacing the outer equivalence relation, IFF, by EQUAL. See :DOC congruence, in particular (near the end) the Remark on Replacing IFF by EQUAL. Goal' Goal'' Q.E.D. Summary Form: ( DEFTHM PERM-IMPLIES-IFF-MEM-2 ...) Rules: ((:DEFINITION IFF) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:REWRITE PERM-MEM) (:TYPE-PRESCRIPTION MEM)) Warnings: Equiv Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 146 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Warnings: Equiv Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 146 PERM-IMPLIES-IFF-MEM-2 ACL2 !>>(DEFTHM ATOM-PERM (IMPLIES (NOT (CONSP X)) (PERM X NIL)) :RULE-CLASSES :FORWARD-CHAINING :HINTS (("Goal" :IN-THEORY (ENABLE PERM)))) ACL2 Observation in ( DEFTHM ATOM-PERM ...): The :TRIGGER-TERMS for the :FORWARD-CHAINING rule ATOM-PERM will consist of the list containing (CONSP X). Q.E.D. Summary Form: ( DEFTHM ATOM-PERM ...) Rules: ((:DEFINITION NOT) (:DEFINITION PERM) (:EXECUTABLE-COUNTERPART CONSP)) Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 35 ATOM-PERM ACL2 !>>(DEFTHM INSERT-IS-CONS (PERM (INSERT A X) (CONS A X))) ACL2 Warning [Double-rewrite] in ( DEFTHM INSERT-IS-CONS ...): In a :REWRITE rule generated from INSERT-IS-CONS, equivalence relation PERM is maintained at one problematic occurrence of variable X in the right-hand side, but not at any binding occurrence of X. Consider replacing that occurrence of X in the right-hand side with (DOUBLE-REWRITE X). See :doc double-rewrite for more information on this issue. *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (INSERT A X). This suggestion was produced using the :induction rule INSERT. If we let (:P A X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (NOT (LT A (CAR X))) (:P A (CDR X))) (:P A X)) (IMPLIES (AND (NOT (ATOM X)) (LT A (CAR X))) (:P A X)) (IMPLIES (ATOM X) (:P A X))). This induction is justified by the same argument used to admit INSERT. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Splitter note (see :DOC splitter) for Subgoal *1/3' (2 subgoals). if-intro: ((:DEFINITION DEL)) Subgoal *1/3.2 Subgoal *1/3.1 Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM INSERT-IS-CONS ...) Rules: ((:CONGRUENCE PERM-IMPLIES-IFF-MEM-2) (:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION ATOM) (:DEFINITION DEL) (:DEFINITION INSERT) (:DEFINITION MEM) (:DEFINITION NOT) (:EXECUTABLE-COUNTERPART PERM) (:EXECUTABLE-COUNTERPART TAU-SYSTEM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING ATOM-PERM) (:INDUCTION INSERT) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE CONS-CAR-CDR) (:REWRITE PERM-CONS) (:REWRITE PERM-MEM)) Splitter rules (see :DOC splitter): if-intro: ((:DEFINITION DEL)) Warnings: Double-rewrite Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 733 INSERT-IS-CONS ACL2 !>>(DEFTHM INSERT-SORT-IS-ID (PERM (INSERT-SORT X) X)) ACL2 Warning [Double-rewrite] in ( DEFTHM INSERT-SORT-IS-ID ...): In a :REWRITE rule generated from INSERT-SORT-IS-ID, equivalence relation PERM is maintained at one problematic occurrence of variable X in the right-hand side, but not at any binding occurrence of X. Consider replacing that occurrence of X in the right-hand side with (DOUBLE-REWRITE X). See :doc double-rewrite for more information on this issue. *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (INSERT-SORT X). This suggestion was produced using the :induction rule INSERT-SORT. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ATOM X)) (:P (CDR X))) (:P X)) (IMPLIES (ATOM X) (:P X))). This induction is justified by the same argument used to admit INSERT-SORT. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM INSERT-SORT-IS-ID ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION ATOM) (:DEFINITION INSERT-SORT) (:DEFINITION NOT) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:EXECUTABLE-COUNTERPART PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING ATOM-PERM) (:INDUCTION INSERT-SORT) (:REWRITE CONS-CAR-CDR) (:REWRITE INSERT-IS-CONS)) Warnings: Double-rewrite Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 166 INSERT-SORT-IS-ID ACL2 !>>(DEFCONG PERM PERM (APP X Y) 2) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (APP X Y-EQUIV), while accommodating (APP X Y). These suggestions were produced using the :induction rule APP. If we let (:P X Y Y-EQUIV) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X Y Y-EQUIV)) (IMPLIES (AND (CONSP X) (:P (CDR X) Y Y-EQUIV)) (:P X Y Y-EQUIV))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM PERM-IMPLIES-PERM-APP-2 ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION APP) (:DEFINITION DEL) (:DEFINITION MEM) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE PERM-CONS)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 272 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 272 PERM-IMPLIES-PERM-APP-2 ACL2 !>>(DEFTHM APP-CONS (PERM (APP A (CONS B C)) (CONS B (APP A C)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. Subsumption reduces that number to one. We will induct according to a scheme suggested by (APP A C), while accommodating (APP A (CONS B C)). These suggestions were produced using the :induction rule APP. If we let (:P A B C) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP A)) (:P A B C)) (IMPLIES (AND (CONSP A) (:P (CDR A) B C)) (:P A B C))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' Subgoal *1/1'4' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM APP-CONS ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION APP) (:DEFINITION DEL) (:DEFINITION MEM) (:ELIM CAR-CDR-ELIM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE PERM-CONS)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1439 APP-CONS ACL2 !>>(DEFTHM APP-COMMUTES (PERM (APP A B) (APP B A))) ACL2 Warning [Double-rewrite] in ( DEFTHM APP-COMMUTES ...): In a :REWRITE rule generated from APP-COMMUTES, equivalence relation PERM is maintained at one problematic occurrence of variable A in the right- hand side, but not at any binding occurrence of A. Consider replacing that occurrence of A in the right-hand side with (DOUBLE-REWRITE A). See :doc double-rewrite for more information on this issue. ACL2 Warning [Subsume] in ( DEFTHM APP-COMMUTES ...): A newly proposed :REWRITE rule generated from APP-COMMUTES probably subsumes the previously added :REWRITE rule APP-CONS, in the sense that the new rule will now probably be applied whenever the old rule would have been. *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. We will choose arbitrarily among these. We will induct according to a scheme suggested by (APP A B). This suggestion was produced using the :induction rule APP. If we let (:P A B) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP A)) (:P A B)) (IMPLIES (AND (CONSP A) (:P (CDR A) B)) (:P A B))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/2' Subgoal *1/2'' ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/2' (IMPLIES (NOT (CONSP A)) (PERM B (APP B NIL))) *1.1 (Subgoal *1/2'') is pushed for proof by induction. ]) Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' So we now return to *1.1, which is (PERM B (APP B NIL)). Subgoal *1.1/2 Subgoal *1.1/1 *1.1 and *1 are COMPLETED! Thus key checkpoints Subgoal *1/2' and Goal are COMPLETED! Q.E.D. Summary Form: ( DEFTHM APP-COMMUTES ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-APP-2) (:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION APP) (:DEFINITION NOT) (:ELIM CAR-CDR-ELIM) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:EXECUTABLE-COUNTERPART PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING ATOM-PERM) (:INDUCTION APP) (:REWRITE APP-CONS) (:REWRITE CONS-CAR-CDR)) Warnings: Subsume and Double-rewrite Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 634 APP-COMMUTES ACL2 !>>(DEFCONG PERM PERM (APP X Y) 1 :HINTS (("Goal" :INDUCT (APP Y X)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. We have been told to use induction. One induction scheme is suggested by the induction hint. We will induct according to a scheme suggested by (APP Y X). This suggestion was produced using the :induction rule APP. If we let (:P X X-EQUIV Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP Y)) (:P X X-EQUIV Y)) (IMPLIES (AND (CONSP Y) (:P X X-EQUIV (CDR Y))) (:P X X-EQUIV Y))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/2' Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' Subgoal *1/1''' Subgoal *1/1'4' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM PERM-IMPLIES-PERM-APP-1 ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-APP-2) (:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION APP) (:DEFINITION DEL) (:DEFINITION MEM) (:DEFINITION NOT) (:ELIM CAR-CDR-ELIM) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:EXECUTABLE-COUNTERPART CONSP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING ATOM-PERM) (:INDUCTION APP) (:REWRITE APP-COMMUTES) (:REWRITE APP-CONS) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE PERM-CONS)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 714 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 714 PERM-IMPLIES-PERM-APP-1 ACL2 !>>(DEFTHM REV-IS-ID (PERM (REV X) X)) ACL2 Warning [Double-rewrite] in ( DEFTHM REV-IS-ID ...): In a :REWRITE rule generated from REV-IS-ID, equivalence relation PERM is maintained at one problematic occurrence of variable X in the right-hand side, but not at any binding occurrence of X. Consider replacing that occurrence of X in the right-hand side with (DOUBLE-REWRITE X). See :doc double- rewrite for more information on this issue. *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (REV X). This suggestion was produced using the :induction rule REV. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X)) (IMPLIES (AND (CONSP X) (:P (CDR X))) (:P X))). This induction is justified by the same argument used to admit REV. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM REV-IS-ID ...) Rules: ((:CONGRUENCE PERM-IMPLIES-PERM-APP-1) (:CONGRUENCE PERM-IMPLIES-PERM-CONS-2) (:DEFINITION APP) (:DEFINITION REV) (:EQUIVALENCE PERM-IS-AN-EQUIVALENCE) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART PERM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING ATOM-PERM) (:INDUCTION REV) (:REWRITE APP-COMMUTES) (:REWRITE APP-CONS) (:REWRITE CONS-CAR-CDR)) Warnings: Double-rewrite Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 149 REV-IS-ID ACL2 !>>(DEFUN == (X Y) (IF (CONSP X) (IF (CONSP Y) (AND (EQUAL (CAR X) (CAR Y)) (== (CDR X) (CDR Y))) NIL) (NOT (CONSP Y)))) The admission of == 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 X). We observe that the type of == is described by the theorem (OR (EQUAL (== X Y) T) (EQUAL (== X Y) NIL)). Summary Form: ( DEFUN == ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) == ACL2 !>>(DEFTHM ==-SYMMETRIC (== X X)) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (== X X). This suggestion was produced using the :induction rule ==. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X)) (IMPLIES (AND (CONSP X) (CONSP X) (NOT (EQUAL (CAR X) (CAR X)))) (:P X)) (IMPLIES (AND (CONSP X) (CONSP X) (EQUAL (CAR X) (CAR X)) (:P (CDR X))) (:P X))). This induction is justified by the same argument used to admit ==. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 Subgoal *1/1' *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of ==-SYMMETRIC depends upon the :type-prescription rule ==. Summary Form: ( DEFTHM ==-SYMMETRIC ...) Rules: ((:DEFINITION ==) (:DEFINITION NOT) (:EXECUTABLE-COUNTERPART NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ==) (:TYPE-PRESCRIPTION ==)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 168 ==-SYMMETRIC ACL2 !>>(DEFTHM ==-REFLEXIVE (IMPLIES (== X Y) (== Y X))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (== Y X), while ac- commodating (== X Y). These suggestions were produced using the :induction rule ==. If we let (:P X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP Y)) (:P X Y)) (IMPLIES (AND (CONSP Y) (NOT (CONSP X))) (:P X Y)) (IMPLIES (AND (CONSP Y) (CONSP X) (NOT (EQUAL (CAR Y) (CAR X)))) (:P X Y)) (IMPLIES (AND (CONSP Y) (CONSP X) (EQUAL (CAR Y) (CAR X)) (:P (CDR X) (CDR Y))) (:P X Y))). This induction is justified by the same argument used to admit ==. Note, however, that the unmeasured variable X is being instantiated. When applied to the goal at hand the above induction scheme produces five nontautological subgoals. Subgoal *1/5 Subgoal *1/4 Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. The storage of ==-REFLEXIVE depends upon the :type-prescription rule ==. Summary Form: ( DEFTHM ==-REFLEXIVE ...) Rules: ((:DEFINITION ==) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ==) (:TYPE-PRESCRIPTION ==)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 497 ==-REFLEXIVE ACL2 !>>(DEFEQUIV ==) Subgoal 2 Subgoal 1 ([ A key checkpoint: Subgoal 1 (IMPLIES (AND (== X Y) (== Y Z)) (== X Z)) *1 (Subgoal 1) is pushed for proof by induction. ]) Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (== X Z), while ac- commodating (== Y Z) and (== X Y). These suggestions were produced using the :induction rule ==. If we let (:P X Y Z) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X Y Z)) (IMPLIES (AND (CONSP X) (NOT (CONSP Z))) (:P X Y Z)) (IMPLIES (AND (CONSP X) (CONSP Z) (NOT (EQUAL (CAR X) (CAR Z)))) (:P X Y Z)) (IMPLIES (AND (CONSP X) (CONSP Z) (EQUAL (CAR X) (CAR Z)) (:P (CDR X) (CDR Y) (CDR Z))) (:P X Y Z))). This induction is justified by the same argument used to admit ==. Note, however, that the unmeasured variables Y and Z are being instantiated. When applied to the goal at hand the above induction scheme produces six nontautological subgoals. Subgoal *1/6 Subgoal *1/5 Subgoal *1/4 Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Subgoal 1 is COMPLETED! Q.E.D. Summary Form: ( DEFTHM ==-IS-AN-EQUIVALENCE ...) Rules: ((:DEFINITION ==) (:EXECUTABLE-COUNTERPART TAU-SYSTEM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ==) (:REWRITE ==-REFLEXIVE) (:REWRITE ==-SYMMETRIC) (:TYPE-PRESCRIPTION ==)) Time: 0.02 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 1446 Summary Form: ( MAKE-EVENT (DEFEQUIV-FORM ...)) Rules: NIL Time: 0.02 seconds (prove: 0.02, print: 0.00, other: 0.00) Prover steps counted: 1446 ==-IS-AN-EQUIVALENCE ACL2 !>>(IN-THEORY (DISABLE ==-SYMMETRIC ==-REFLEXIVE)) Summary Form: ( IN-THEORY (DISABLE ...)) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) (:NUMBER-OF-ENABLED-RUNES 5607) ACL2 !>>(DEFCONG == == (CONS X Y) 2) Q.E.D. Summary Form: ( DEFTHM ==-IMPLIES-==-CONS-2 ...) Rules: ((:DEFINITION ==) (:EQUIVALENCE ==-IS-AN-EQUIVALENCE) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 89 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 89 ==-IMPLIES-==-CONS-2 ACL2 !>>(DEFCONG == IFF (CONSP X) 1) ACL2 Warning [Equiv] in ( DEFTHM ==-IMPLIES-IFF-CONSP-1 ...): The :CONGRUENCE rule ==-IMPLIES-IFF-CONSP-1 can be strengthened by replacing the outer equivalence relation, IFF, by EQUAL. See :DOC congruence, in particular (near the end) the Remark on Replacing IFF by EQUAL. Goal' Subgoal 2 Subgoal 1 Q.E.D. Summary Form: ( DEFTHM ==-IMPLIES-IFF-CONSP-1 ...) Rules: ((:DEFINITION ==) (:DEFINITION IFF)) Warnings: Equiv Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 150 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Warnings: Equiv Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 150 ==-IMPLIES-IFF-CONSP-1 ACL2 !>>(DEFCONG == == (APP X Y) 2) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. 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 (APP X Y-EQUIV), while accommodating (APP X Y). These suggestions were produced using the :induction rule APP. If we let (:P X Y Y-EQUIV) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X Y Y-EQUIV)) (IMPLIES (AND (CONSP X) (:P (CDR X) Y Y-EQUIV)) (:P X Y Y-EQUIV))). This induction is justified by the same argument used to admit APP. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM ==-IMPLIES-==-APP-2 ...) Rules: ((:CONGRUENCE ==-IMPLIES-==-CONS-2) (:DEFINITION ==) (:DEFINITION APP) (:EQUIVALENCE ==-IS-AN-EQUIVALENCE) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 452 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 452 ==-IMPLIES-==-APP-2 ACL2 !>>(DEFCONG == == (APP X Y) 1) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (APP X-EQUIV Y), while accommodating (APP X Y) and (== X X-EQUIV). These suggestions were produced using the :induction rules == and APP. If we let (:P X X-EQUIV Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X-EQUIV)) (:P X X-EQUIV Y)) (IMPLIES (AND (CONSP X-EQUIV) (:P (CDR X) (CDR X-EQUIV) Y)) (:P X X-EQUIV Y))). This induction is justified by the same argument used to admit APP. Note, however, that the unmeasured variable X is being instantiated. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM ==-IMPLIES-==-APP-1 ...) Rules: ((:CONGRUENCE ==-IMPLIES-==-CONS-2) (:CONGRUENCE ==-IMPLIES-IFF-CONSP-1) (:DEFINITION ==) (:DEFINITION APP) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ==) (:INDUCTION APP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 492 Summary Form: ( MAKE-EVENT (DEFCONG-FORM ...)) Rules: NIL Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 492 ==-IMPLIES-==-APP-1 ACL2 !>>(DEFTHM REV-REV-AGAIN (== (REV (REV X)) X)) ACL2 Warning [Double-rewrite] in ( DEFTHM REV-REV-AGAIN ...): In a :REWRITE rule generated from REV-REV-AGAIN, equivalence relation == is maintained at one problematic occurrence of variable X in the right- hand side, but not at any binding occurrence of X. Consider replacing that occurrence of X in the right-hand side with (DOUBLE-REWRITE X). See :doc double-rewrite for more information on this issue. *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. One induction scheme is suggested by this conjecture. We will induct according to a scheme suggested by (REV X). This suggestion was produced using the :induction rule REV. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (CONSP X)) (:P X)) (IMPLIES (AND (CONSP X) (:P (CDR X))) (:P X))). This induction is justified by the same argument used to admit REV. When applied to the goal at hand the above induction scheme produces two nontautological subgoals. Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal is COMPLETED! Q.E.D. Summary Form: ( DEFTHM REV-REV-AGAIN ...) Rules: ((:CONGRUENCE ==-IMPLIES-==-APP-2) (:DEFINITION ==) (:DEFINITION APP) (:DEFINITION REV) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART REV) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION REV) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE CONS-CAR-CDR) (:REWRITE REV-APP)) Warnings: Double-rewrite Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 434 REV-REV-AGAIN ACL2 !>>(DEFUN ENDS-IN-A-0 (X) (DECLARE (XARGS :GUARD T)) (IF (CONSP X) (ENDS-IN-A-0 (CDR X)) (EQUAL X 0))) The admission of ENDS-IN-A-0 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 X). We observe that the type of ENDS-IN-A-0 is described by the theorem (OR (EQUAL (ENDS-IN-A-0 X) T) (EQUAL (ENDS-IN-A-0 X) NIL)). We used primitive type reasoning. Computing the guard conjecture for ENDS-IN-A-0.... The guard conjecture for ENDS-IN-A-0 is trivial to prove. ENDS-IN-A-0 is compliant with Common Lisp. Summary Form: ( DEFUN ENDS-IN-A-0 ...) Rules: ((:FAKE-RUNE-FOR-TYPE-SET NIL)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ENDS-IN-A-0 ACL2 !>>(DEFUN APP0 (X Y) (DECLARE (XARGS :GUARD (ENDS-IN-A-0 X))) (IF (ENDS-IN-A-0 X) (IF (EQUAL X 0) Y (CONS (CAR X) (APP0 (CDR X) Y))) 'DEFAULT)) For the admission of APP0 we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (ACL2-COUNT X). The non-trivial part of the measure conjecture is Goal (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0))) (O< (ACL2-COUNT (CDR X)) (ACL2-COUNT X))). Goal' Goal'' Q.E.D. That completes the proof of the measure theorem for APP0. Thus, we admit this function under the principle of definition. We observe that the type of APP0 is described by the theorem (OR (OR (CONSP (APP0 X Y)) (AND (SYMBOLP (APP0 X Y)) (NOT (EQUAL (APP0 X Y) T)) (NOT (EQUAL (APP0 X Y) NIL)))) (EQUAL (APP0 X Y) Y)). We used primitive type reasoning. Computing the guard conjecture for APP0.... The non-trivial part of the guard conjecture for APP0 is Goal (AND (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0))) (ENDS-IN-A-0 (CDR X))) (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0)) (NOT (CONSP X))) (EQUAL X NIL))). Subgoal 2 Subgoal 1 Q.E.D. That completes the proof of the guard theorem for APP0. APP0 is compliant with Common Lisp. Summary Form: ( DEFUN APP0 ...) Rules: ((:DEFINITION ENDS-IN-A-0) (:DEFINITION NOT) (:DEFINITION O-FINP) (:DEFINITION O<) (:FAKE-RUNE-FOR-LINEAR NIL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:LINEAR ACL2-COUNT-CAR-CDR-LINEAR) (:TYPE-PRESCRIPTION ACL2-COUNT)) Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.01) Prover steps counted: 517 APP0 ACL2 !>>(DEFUN REV0 (X) (DECLARE (XARGS :GUARD (ENDS-IN-A-0 X))) (IF (ENDS-IN-A-0 X) (IF (EQUAL X 0) 0 (APP0 (REV0 (CDR X)) (CONS (CAR X) 0))) 'DEFAULT)) For the admission of REV0 we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (ACL2-COUNT X). The non-trivial part of the measure conjecture is Goal (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0))) (O< (ACL2-COUNT (CDR X)) (ACL2-COUNT X))). Goal' Goal'' Q.E.D. That completes the proof of the measure theorem for REV0. Thus, we admit this function under the principle of definition. We observe that the type of REV0 is described by the theorem (OR (EQUAL (REV0 X) 0) (CONSP (REV0 X)) (AND (SYMBOLP (REV0 X)) (NOT (EQUAL (REV0 X) T)) (NOT (EQUAL (REV0 X) NIL)))). We used primitive type reasoning and the :type-prescription rule APP0. Computing the guard conjecture for REV0.... The non-trivial part of the guard conjecture for REV0 is Goal (AND (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0))) (ENDS-IN-A-0 (CDR X))) (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0))) (ENDS-IN-A-0 (REV0 (CDR X)))) (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0)) (NOT (CONSP X))) (EQUAL X NIL))). Subgoal 3 Subgoal 2 Subgoal 2' Subgoal 2'' Subgoal 2''' ([ A key checkpoint: Subgoal 2' (IMPLIES (AND (CONSP X) (ENDS-IN-A-0 (CDR X))) (ENDS-IN-A-0 (REV0 (CDR X)))) *1 (Subgoal 2''') is pushed for proof by induction: (IMPLIES (ENDS-IN-A-0 X2) (ENDS-IN-A-0 (REV0 X2))). ]) Subgoal 1 Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (REV0 X2), while accommodating (ENDS-IN-A-0 X2). These suggestions were produced using the :induction rules ENDS-IN-A-0 and REV0. If we let (:P X2) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (ENDS-IN-A-0 X2)) (:P X2)) (IMPLIES (AND (ENDS-IN-A-0 X2) (NOT (EQUAL X2 0)) (:P (CDR X2))) (:P X2)) (IMPLIES (AND (ENDS-IN-A-0 X2) (EQUAL X2 0)) (:P X2))). This induction is justified by the same argument used to admit REV0. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/3' Subgoal *1/3'' Subgoal *1/3''' Subgoal *1/3'4' Subgoal *1/3'5' ([ A key checkpoint while proving *1 (descended from Subgoal 2'): Subgoal *1/3' (IMPLIES (AND (CONSP X2) (ENDS-IN-A-0 (CDR X2)) (ENDS-IN-A-0 (REV0 (CDR X2)))) (ENDS-IN-A-0 (APP0 (REV0 (CDR X2)) (CONS (CAR X2) 0)))) *1.1 (Subgoal *1/3'5') is pushed for proof by induction. ]) Subgoal *1/2 Subgoal *1/1 So we now return to *1.1, which is (IMPLIES (ENDS-IN-A-0 R0) (ENDS-IN-A-0 (APP0 R0 (CONS X3 0)))). Subgoal *1.1/3 Subgoal *1.1/2 Subgoal *1.1/1 *1.1 and *1 are COMPLETED! Thus key checkpoints Subgoal *1/3' and Subgoal 2' are COMPLETED! Q.E.D. That completes the proof of the guard theorem for REV0. REV0 is compliant with Common Lisp. Summary Form: ( DEFUN REV0 ...) Rules: ((:DEFINITION APP0) (:DEFINITION ENDS-IN-A-0) (:DEFINITION NOT) (:DEFINITION O-FINP) (:DEFINITION O<) (:DEFINITION REV0) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART ENDS-IN-A-0) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART NOT) (:EXECUTABLE-COUNTERPART REV0) (:FAKE-RUNE-FOR-LINEAR NIL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP0) (:INDUCTION ENDS-IN-A-0) (:INDUCTION REV0) (:LINEAR ACL2-COUNT-CAR-CDR-LINEAR) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION ACL2-COUNT) (:TYPE-PRESCRIPTION APP0) (:TYPE-PRESCRIPTION ENDS-IN-A-0)) Time: 0.03 seconds (prove: 0.03, print: 0.00, other: 0.00) Prover steps counted: 2502 REV0 ACL2 !>>(DEFTHM APP0-RIGHT-ID (IMPLIES (FORCE (ENDS-IN-A-0 X)) (EQUAL (APP0 X 0) X))) Goal' ([ A key checkpoint: Goal' (IMPLIES (ENDS-IN-A-0 X) (EQUAL (APP0 X 0) X)) *1 (Goal') is pushed for proof by induction. ]) Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (APP0 X 0), while accommodating (ENDS-IN-A-0 X). These suggestions were produced using the :induction rules APP0 and ENDS-IN-A-0. If we let (:P X) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (ENDS-IN-A-0 X)) (:P X)) (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0)) (:P (CDR X))) (:P X)) (IMPLIES (AND (ENDS-IN-A-0 X) (EQUAL X 0)) (:P X))). This induction is justified by the same argument used to admit APP0. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal' is COMPLETED! Q.E.D. Summary Form: ( DEFTHM APP0-RIGHT-ID ...) Rules: ((:DEFINITION APP0) (:DEFINITION ENDS-IN-A-0) (:DEFINITION FORCE) (:EXECUTABLE-COUNTERPART APP0) (:EXECUTABLE-COUNTERPART ENDS-IN-A-0) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP0) (:INDUCTION ENDS-IN-A-0) (:REWRITE CONS-CAR-CDR) (:TYPE-PRESCRIPTION ENDS-IN-A-0)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 273 APP0-RIGHT-ID ACL2 !>>(DEFUN ENDS-IN-A-ZERO (X) (ENDS-IN-A-0 X)) Since ENDS-IN-A-ZERO is non-recursive, its admission is trivial. We observe that the type of ENDS-IN-A-ZERO is described by the theorem (OR (EQUAL (ENDS-IN-A-ZERO X) T) (EQUAL (ENDS-IN-A-ZERO X) NIL)). We used the :type-prescription rule ENDS-IN-A-0. Summary Form: ( DEFUN ENDS-IN-A-ZERO ...) Rules: ((:TYPE-PRESCRIPTION ENDS-IN-A-0)) Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ENDS-IN-A-ZERO ACL2 !>>(DEFTHM ENDS-IN-A-ZERO-APP0 (IMPLIES (FORCE (ENDS-IN-A-ZERO X)) (ENDS-IN-A-0 (APP0 X (CONS Y 0))))) Goal' ([ A key checkpoint: Goal' (IMPLIES (ENDS-IN-A-0 X) (ENDS-IN-A-0 (APP0 X (CONS Y 0)))) *1 (Goal') is pushed for proof by induction. ]) Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (APP0 X (CONS Y 0)), while accommodating (ENDS-IN-A-0 X). These suggestions were produced using the :induction rules APP0 and ENDS-IN-A-0. If we let (:P X Y) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (ENDS-IN-A-0 X)) (:P X Y)) (IMPLIES (AND (ENDS-IN-A-0 X) (NOT (EQUAL X 0)) (:P (CDR X) Y)) (:P X Y)) (IMPLIES (AND (ENDS-IN-A-0 X) (EQUAL X 0)) (:P X Y))). This induction is justified by the same argument used to admit APP0. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. Subgoal *1/3 Subgoal *1/2 Subgoal *1/1 *1 is COMPLETED! Thus key checkpoint Goal' is COMPLETED! Q.E.D. The storage of ENDS-IN-A-ZERO-APP0 depends upon the :type-prescription rule ENDS-IN-A-0. Summary Form: ( DEFTHM ENDS-IN-A-ZERO-APP0 ...) Rules: ((:DEFINITION APP0) (:DEFINITION ENDS-IN-A-0) (:DEFINITION ENDS-IN-A-ZERO) (:DEFINITION FORCE) (:EXECUTABLE-COUNTERPART ENDS-IN-A-0) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION APP0) (:INDUCTION ENDS-IN-A-0) (:REWRITE CDR-CONS) (:TYPE-PRESCRIPTION ENDS-IN-A-0)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 333 ENDS-IN-A-ZERO-APP0 ACL2 !>>(IN-THEORY (DISABLE ENDS-IN-A-ZERO)) Summary Form: ( IN-THEORY (DISABLE ...)) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) (:NUMBER-OF-ENABLED-RUNES 5628) ACL2 !>>(DEFTHM FORCE-TEST (AND (IMPLIES (ENDS-IN-A-0 X) (EQUAL (APP0 (REV0 X) 0) (REV0 X))) (IMPLIES (ENDS-IN-A-0 Y) (EQUAL (APP0 (REV0 Y) 0) (REV0 Y))) (IMPLIES (ENDS-IN-A-0 Z) (EQUAL (APP0 (REV0 Z) 0) (REV0 Z)))) :HINTS (("[2]Goal" :IN-THEORY (ENABLE ENDS-IN-A-ZERO)))) Subgoal 3 Forcing Round 1 is pending (caused first by applying APP0-RIGHT-ID to Subgoal 3). Subgoal 2 Subgoal 1 q.e.d. (given three forced hypotheses) Modulo three forced goals, that completes the proof of the input Goal. See :DOC forcing-round. [1]Subgoal 3 was forced in Subgoal 1 by applying (:REWRITE APP0-RIGHT-ID). [1]Subgoal 2 was forced in Subgoal 2 by applying (:REWRITE APP0-RIGHT-ID). [1]Subgoal 1 was forced in Subgoal 3 by applying (:REWRITE APP0-RIGHT-ID). We now undertake Forcing Round 1. [1]Subgoal 3 ([ A key checkpoint: [1]Subgoal 3 (IMPLIES (ENDS-IN-A-0 Z) (ENDS-IN-A-0 (REV0 Z))) [1]*1 ([1]Subgoal 3) is pushed for proof by induction. ]) [1]Subgoal 2 ([ A key checkpoint: [1]Subgoal 2 (IMPLIES (ENDS-IN-A-0 Y) (ENDS-IN-A-0 (REV0 Y))) [1]*2 ([1]Subgoal 2) is pushed for proof by induction. ]) [1]Subgoal 1 ([ A key checkpoint: [1]Subgoal 1 (IMPLIES (ENDS-IN-A-0 X) (ENDS-IN-A-0 (REV0 X))) [1]*3 ([1]Subgoal 1) is pushed for proof by induction. ]) But the formula above is subsumed by [1]*2, which we'll try to prove later. We therefore regard [1]*3 as proved (pending the proof of the more general [1]*2). [1]Subgoal 1 COMPLETED! But the formula above is subsumed by [1]*1, which we'll try to prove later. We therefore regard [1]*2 as proved (pending the proof of the more general [1]*1). [1]Subgoal 2 COMPLETED! Perhaps we can prove [1]*1 by induction. Two induction schemes are suggested by this conjecture. These merge into one derived induction scheme. We will induct according to a scheme suggested by (REV0 Z), while ac- commodating (ENDS-IN-A-0 Z). These suggestions were produced using the :induction rules ENDS-IN-A-0 and REV0. If we let (:P Z) denote [1]*1 above then the induction scheme we'll use is (AND (IMPLIES (NOT (ENDS-IN-A-0 Z)) (:P Z)) (IMPLIES (AND (ENDS-IN-A-0 Z) (NOT (EQUAL Z 0)) (:P (CDR Z))) (:P Z)) (IMPLIES (AND (ENDS-IN-A-0 Z) (EQUAL Z 0)) (:P Z))). This induction is justified by the same argument used to admit REV0. When applied to the goal at hand the above induction scheme produces three nontautological subgoals. [1]Subgoal *1/3 Forcing Round 2 is pending (caused first by applying ENDS-IN-A-ZERO-APP0 to [1]Subgoal *1/3). [1]Subgoal *1/2 [1]Subgoal *1/1 [1]*1 is COMPLETED! Thus key checkpoint [1]Subgoal 3 is COMPLETED! q.e.d. (given one forced hypothesis) Modulo one newly forced goal, that completes Forcing Round 1. See :DOC forcing-round. [2]Goal was forced in [1]Subgoal *1/3 by applying (:REWRITE ENDS-IN-A-ZERO-APP0). We now undertake Forcing Round 2. [2]Goal Q.E.D. Summary Form: ( DEFTHM FORCE-TEST ...) Rules: ((:DEFINITION ENDS-IN-A-0) (:DEFINITION ENDS-IN-A-ZERO) (:DEFINITION NOT) (:DEFINITION REV0) (:EXECUTABLE-COUNTERPART ENDS-IN-A-0) (:EXECUTABLE-COUNTERPART FORCE) (:EXECUTABLE-COUNTERPART NOT) (:EXECUTABLE-COUNTERPART REV0) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION ENDS-IN-A-0) (:INDUCTION REV0) (:REWRITE APP0-RIGHT-ID) (:REWRITE ENDS-IN-A-ZERO-APP0) (:TYPE-PRESCRIPTION ENDS-IN-A-0)) Time: 0.02 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1304 FORCE-TEST ACL2 !>>(DEFUN PROPER-CONS-NEST-P (X) (DECLARE (XARGS :GUARD (PSEUDO-TERMP X))) (COND ((SYMBOLP X) NIL) ((FQUOTEP X) (TRUE-LISTP (CADR X))) ((EQ (FFN-SYMB X) 'CONS) (PROPER-CONS-NEST-P (FARGN X 2))) (T NIL))) For the admission of PROPER-CONS-NEST-P we will use the relation O< (which is known to be well-founded on the domain recognized by O-P) and the measure (ACL2-COUNT X). The non-trivial part of the measure conjecture is Goal (IMPLIES (AND (NOT (SYMBOLP X)) (EQ (CAR X) 'CONS)) (O< (ACL2-COUNT (CADDR X)) (ACL2-COUNT X))). Goal' Goal'' Subgoal 4 Subgoal 3 Subgoal 3' Subgoal 3'' Subgoal 2 Subgoal 2' Subgoal 2'' Subgoal 1 Subgoal 1' Subgoal 1'' Q.E.D. That completes the proof of the measure theorem for PROPER-CONS-NEST-P. Thus, we admit this function under the principle of definition. We observe that the type of PROPER-CONS-NEST-P is described by the theorem (OR (EQUAL (PROPER-CONS-NEST-P X) T) (EQUAL (PROPER-CONS-NEST-P X) NIL)). Computing the guard conjecture for PROPER-CONS-NEST-P.... The non-trivial part of the guard conjecture for PROPER-CONS-NEST-P is Goal (AND (IMPLIES (AND (PSEUDO-TERMP X) (NOT (SYMBOLP X)) (NOT (CONSP X))) (EQUAL X NIL)) (IMPLIES (AND (PSEUDO-TERMP X) (NOT (SYMBOLP X)) (EQ (CAR X) 'CONS)) (PSEUDO-TERMP (CADDR X))) (IMPLIES (AND (PSEUDO-TERMP X) (NOT (SYMBOLP X)) (EQ (CAR X) 'CONS) (NOT (CONSP (CDDR X)))) (EQUAL (CDDR X) NIL)) (IMPLIES (AND (PSEUDO-TERMP X) (NOT (SYMBOLP X)) (EQ (CAR X) 'CONS) (NOT (CONSP (CDR X)))) (EQUAL (CDR X) NIL)) (IMPLIES (AND (PSEUDO-TERMP X) (NOT (SYMBOLP X)) (EQ 'QUOTE (CAR X)) (NOT (CONSP (CDR X)))) (EQUAL (CDR X) NIL))). Subgoal 5 Subgoal 4 Subgoal 4' Subgoal 4.3 Subgoal 4.3' Subgoal 4.2 Subgoal 4.2' Subgoal 4.1 Subgoal 4.1' Subgoal 3 Subgoal 3' Subgoal 2 Subgoal 1 Q.E.D. That completes the proof of the guard theorem for PROPER-CONS-NEST-P. PROPER-CONS-NEST-P is compliant with Common Lisp. Summary Form: ( DEFUN PROPER-CONS-NEST-P ...) Rules: ((:DEFINITION ACL2-COUNT) (:DEFINITION EQ) (:DEFINITION FIX) (:DEFINITION NOT) (:DEFINITION O-FINP) (:DEFINITION O<) (:DEFINITION PSEUDO-TERM-LISTP) (:DEFINITION PSEUDO-TERMP) (:DEFINITION SYNP) (:ELIM CAR-CDR-ELIM) (:EXECUTABLE-COUNTERPART ACL2-COUNT) (:EXECUTABLE-COUNTERPART BINARY-+) (:EXECUTABLE-COUNTERPART CAR) (:EXECUTABLE-COUNTERPART CDR) (:EXECUTABLE-COUNTERPART CONS) (:EXECUTABLE-COUNTERPART CONSP) (:EXECUTABLE-COUNTERPART EQUAL) (:EXECUTABLE-COUNTERPART NOT) (:EXECUTABLE-COUNTERPART PSEUDO-TERMP) (:EXECUTABLE-COUNTERPART SYMBOLP) (:FAKE-RUNE-FOR-LINEAR NIL) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:FORWARD-CHAINING PSEUDO-TERM-LISTP-FORWARD-TO-TRUE-LISTP) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS) (:REWRITE COMMUTATIVITY-2-OF-+) (:REWRITE DEFAULT-CAR) (:REWRITE DEFAULT-CDR) (:REWRITE FOLD-CONSTS-IN-+) (:REWRITE UNICITY-OF-0) (:TYPE-PRESCRIPTION ACL2-COUNT) (:TYPE-PRESCRIPTION PSEUDO-TERM-LISTP)) Time: 0.04 seconds (prove: 0.03, print: 0.00, other: 0.00) Prover steps counted: 4267 PROPER-CONS-NEST-P ACL2 !>>(DEFTHM ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST (IMPLIES (AND (ORDERED-SYMBOL-ALISTP L) (SYMBOLP KEY) (ASSOC-EQ KEY L)) (ORDERED-SYMBOL-ALISTP (REMOVE1-ASSOC-EQ KEY L))) :HINTS (("Goal" :IN-THEORY (DISABLE ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ)))) ACL2 Warning [Subsume] in ( DEFTHM ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST ...): The previously added rule ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ subsumes a newly proposed :REWRITE rule generated from ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST, in the sense that the old rule rewrites a more general target. Because the new rule will be tried first, it may nonetheless find application. Q.E.D. The storage of ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST depends upon the :type-prescription rule ORDERED-SYMBOL-ALISTP. Summary Form: ( DEFTHM ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST ...) Rules: ((:DEFINITION ASSOC-EQ-EXEC$GUARD-CHECK) (:DEFINITION REMOVE1-ASSOC-EQ-EXEC$GUARD-CHECK) (:DEFINITION RETURN-LAST) (:EXECUTABLE-COUNTERPART TAU-SYSTEM) (:TYPE-PRESCRIPTION ORDERED-SYMBOL-ALISTP)) Warnings: Subsume Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 48 ORDERED-SYMBOL-ALISTP-REMOVE1-ASSOC-EQ-TEST ACL2 !>>(VALUE-TRIPLE "Mini-proveall completed successfully.") "Mini-proveall completed successfully." ACL2 !>>Bye. :EOF ACL2 !>(memsum) Sorted by *memoize-summary-order-list* = (TOTAL-TIME NUMBER-OF-CALLS). Reporting on 100 of 2,424 functions because *memoize-summary-limit* = 100. (LD-READ-COMMAND Calls 60 Time of all outermost calls 10.76 Time per call 0.18 Heap bytes allocated 672; 0.0% Heap bytes allocated per call 11.20 To READ-STANDARD-OI 6.00E+1 calls took 1.08E+1; 100.0% To self/unprofiled functions 1.44E-4; <0.01% To other functions 1.25E+2 calls took 1.20E-4; <0.01% From LD-READ-EVAL-PRINT 2.00E+0 calls took 1.08E+1; 100.0% From other functions 5.80E+1 calls took 1.62E-4; ?%) (READ-STANDARD-OI Calls 60 Time of all outermost calls 10.76 Time per call 0.18 Heap bytes allocated 352; 0.0% Heap bytes allocated per call 5.87 To READ-OBJECT 2.00E+0 calls took 1.08E+1; 100.0% To self/unprofiled functions 2.66E-5; <0.01% To other functions 6.00E+1 calls took 2.00E-6; <0.01% From LD-READ-COMMAND 6.00E+1 calls took 1.08E+1; 100.0%) (READ-OBJECT Calls 2 Time of all outermost calls 10.76 Time per call 5.38 Heap bytes allocated 352; 0.0% Heap bytes allocated per call 176 To self/unprofiled functions 1.08E+1; 100.0% To other functions 3.10E+1 calls took 3.50E-5; <0.01% From READ-STANDARD-OI 2.00E+0 calls took 1.08E+1; 100.0%) (LD-READ-EVAL-PRINT Calls (running) 60 Time of all outermost calls 9.10 Time per call 0.15 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 4.17E+5 To LD-READ-COMMAND 2.00E+0 calls took 1.08E+1; 118.3% To TRANS-EVAL-DEFAULT-WARNING 2.00E+0 calls took 2.32E+0; 25.5% To other functions 2.90E+1 calls took 8.20E-5; <0.01% From other functions 6.00E+1 calls took 9.10E+0; 100.0%) (TRANS-EVAL-DEFAULT-WARNING Calls (running) 109 Time of all outermost calls 2.32 Time per call 0.02 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.30E+5 To TRANS-EVAL0 2.00E+0 calls took 2.32E+0; 100.0% To self/unprofiled functions 6.20E-6; <0.01% From LD-READ-EVAL-PRINT 2.00E+0 calls took 2.32E+0; 100.0%) (TRANS-EVAL0 Calls (running) 112 Time of all outermost calls 2.32 Time per call 0.02 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.24E+5 To TRANS-EVAL1 2.00E+0 calls took 2.32E+0; 100.0% To other functions 8.00E+0 calls took 4.55E-4; 0.0% From TRANS-EVAL-DEFAULT-WARNING 2.00E+0 calls took 2.32E+0; 100.0%) (EV-REC Calls (running) 6.55E+3 Time of all outermost calls 2.32 Time per call 3.54E-4 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 3.82E+3 To EV-FNCALL-REC 3.00E+0 calls took 2.32E+0; 100.0% To other functions 6.00E+0 calls took 1.09E-4; <0.01% To self/unprofiled functions 4.05E-6; <0.01% From EV 2.00E+0 calls took 2.32E+0; 100.0% From other functions 6.55E+3 calls took 8.90E-5; ?%) (TRANS-EVAL1 Calls (running) 112 Time of all outermost calls 2.32 Time per call 0.02 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.24E+5 To EV-FOR-TRANS-EVAL 2.00E+0 calls took 2.32E+0; 100.0% To other functions 1.00E+1 calls took 1.30E-5; <0.01% To self/unprofiled functions 4.05E-6; <0.01% From TRANS-EVAL0 2.00E+0 calls took 2.32E+0; 100.0%) (EV-FNCALL-REC Calls (running) 5.33E+4 Time of all outermost calls 2.32 Time per call 4.35E-5 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 469.43 To LD-FN 1.00E+0 calls took 2.32E+0; 100.0% To self/unprofiled functions 4.80E-5; <0.01% To other functions 2.48E+2 calls took 3.90E-5; <0.01% From EV-REC 3.00E+0 calls took 2.32E+0; 100.0% From other functions 5.33E+4 calls took 6.60E-5; ?%) (EV-FOR-TRANS-EVAL Calls (running) 112 Time of all outermost calls 2.32 Time per call 0.02 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.24E+5 To EV 2.00E+0 calls took 2.32E+0; 100.0% To other functions 1.00E+1 calls took 2.10E-5; <0.01% To self/unprofiled functions 3.17E-6; <0.01% From TRANS-EVAL1 2.00E+0 calls took 2.32E+0; 100.0%) (EV Calls (running) 269 Time of all outermost calls 2.32 Time per call 8.62E-3 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 9.31E+4 To EV-REC 2.00E+0 calls took 2.32E+0; 100.0% To self/unprofiled functions 2.15E-6; <0.01% To other functions 6.00E+0 calls took 1.00E-6; <0.01% From EV-FOR-TRANS-EVAL 2.00E+0 calls took 2.32E+0; 100.0%) (LD-FN Calls 1 Time of all outermost calls 2.32 Time per call 2.32 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.50E+7 To LD-FN0 1.00E+0 calls took 2.32E+0; 100.0% To self/unprofiled functions 2.15E-6; <0.01% From EV-FNCALL-REC 1.00E+0 calls took 2.32E+0; 100.0%) (LD-FN0 Calls 1 Time of all outermost calls 2.32 Time per call 2.32 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.50E+7 To LD-FN-BODY 1.00E+0 calls took 2.32E+0; 100.0% To other functions 7.00E+0 calls took 5.90E-5; <0.01% To self/unprofiled functions 1.78E-5; <0.01% From LD-FN 1.00E+0 calls took 2.32E+0; 100.0%) (LD-FN-BODY Calls 1 Time of all outermost calls 2.32 Time per call 2.32 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.50E+7 To LD-LOOP 1.00E+0 calls took 2.32E+0; 100.0% To other functions 1.10E+1 calls took 2.42E-4; 0.0% To self/unprofiled functions 2.60E-5; <0.01% From LD-FN0 1.00E+0 calls took 2.32E+0; 100.0%) (LD-LOOP Calls 1 Time of all outermost calls 2.32 Time per call 2.32 Heap bytes allocated 2.50E+7; 3.5% Heap bytes allocated per call 2.50E+7 To DEFTHM-FN 2.70E+1 calls took 1.30E+0; 56.2% To DEFUN-FN 1.30E+1 calls took 3.98E-1; 17.2% To MAKE-EVENT-FN 1.00E+1 calls took 2.84E-1; 12.3% To LD-PRINT-COMMAND 5.70E+1 calls took 1.77E-1; 7.6% To EV-REC-ACL2-UNWIND-PROTECT 2.00E+0 calls took 4.48E-2; 1.9% To LD-PRINT-RESULTS 5.70E+1 calls took 4.21E-2; 1.8% To ENCAPSULATE-FN 1.00E+0 calls took 3.53E-2; 1.5% To other functions 2.89E+3 calls took 3.11E-2; 1.3% To self/unprofiled functions 1.36E-3; 0.1% From LD-FN-BODY 1.00E+0 calls took 2.32E+0; 100.0%) (PRINC$ Calls 5.23E+4 Time of all outermost calls 1.73 Time per call 3.30E-5 To self/unprofiled functions 1.73E+0; 100.0% To other functions 3.19E+2 calls took 1.00E-5; <0.01% From NEWLINE 2.90E+3 calls took 1.72E+0; 99.4% From other functions 4.94E+4 calls took 1.06E-2; 0.6%) (NEWLINE Calls 2.90E+3 Time of all outermost calls 1.72 Time per call 5.92E-4 To PRINC$ 2.90E+3 calls took 1.72E+0; 100.0% To self/unprofiled functions 3.14E-4; 0.0% From FMT0 1.45E+3 calls took 9.67E-1; 56.4% From PPR2-COLUMN 6.88E+2 calls took 3.42E-1; 19.9% From PRINT-TIME-SUMMARY 6.70E+1 calls took 1.35E-1; 7.9% From PPR2 8.10E+1 calls took 1.08E-1; 6.3% From PRINT-SUMMARY 2.01E+2 calls took 5.54E-2; 3.2% From FMT0* 2.90E+1 calls took 4.21E-2; 2.5% From LD-PRINT-RESULTS 5.70E+1 calls took 4.04E-2; 2.4% From PRINT-STEPS-SUMMARY 5.10E+1 calls took 2.52E-2; 1.5% From other functions 2.69E+2 calls took 1.31E-3; 0.1%) (DEFTHM-FN Calls 39 Time of all outermost calls 1.54 Time per call 0.04 Heap bytes allocated 1.86E+7; 2.6% Heap bytes allocated per call 4.77E+5 To DEFTHM-FN1 3.90E+1 calls took 1.54E+0; 100.0% To self/unprofiled functions 7.61E-5; <0.01% To other functions 3.90E+1 calls took 2.90E-5; <0.01% From LD-LOOP 2.70E+1 calls took 1.30E+0; 84.8% From MAKE-EVENT-FN2 1.00E+1 calls took 2.32E-1; 15.1% From other functions 2.00E+0 calls took 1.10E-3; 0.1%) (DEFTHM-FN1 Calls 39 Time of all outermost calls 1.54 Time per call 0.04 Heap bytes allocated 1.86E+7; 2.6% Heap bytes allocated per call 4.77E+5 To PROVE 3.80E+1 calls took 9.46E-1; 61.6% To PRINT-SUMMARY 3.90E+1 calls took 2.82E-1; 18.4% To PROOF-BUILDER 1.00E+0 calls took 1.82E-1; 11.9% To CHK-ACCEPTABLE-RULES 3.90E+1 calls took 8.69E-2; 5.7% To PRINT-RULE-STORAGE-DEPENDENCIES 3.90E+1 calls took 2.24E-2; 1.5% To other functions 1.75E+3 calls took 1.53E-2; 1.0% To self/unprofiled functions 1.12E-3; 0.1% From DEFTHM-FN 3.90E+1 calls took 1.54E+0; 100.0%) (FMT1 Calls 1.09E+3 Time of all outermost calls 1.52 Time per call 1.40E-3 Heap bytes allocated 2.58E+5; 0.0% Heap bytes allocated per call 237.66 To FMT0 1.09E+3 calls took 1.52E+0; 99.9% To self/unprofiled functions 6.69E-4; 0.0% To other functions 2.17E+3 calls took 1.56E-4; 0.0% From FMS 2.27E+2 calls took 7.16E-1; 47.0% From PRINT-RUNES-SUMMARY 6.70E+1 calls took 2.72E-1; 17.8% From LD-PRINT-COMMAND 5.70E+1 calls took 1.77E-1; 11.6% From FMT-ABBREV1 5.60E+1 calls took 8.40E-2; 5.5% From MAYBE-PRINT-PROVED-GOAL-MESSAGE 1.30E+1 calls took 6.73E-2; 4.4% From WATERFALL-PRINT-CLAUSE 2.56E+2 calls took 5.87E-2; 3.8% From FMT 3.50E+1 calls took 5.41E-2; 3.5% From POP-CLAUSE-MSG1 3.30E+1 calls took 4.69E-2; 3.1% From PRINT-DEFUN-MSG/TYPE-PRESCRIPTIONS1 1.30E+1 calls took 4.29E-2; 2.8% From other functions 3.29E+2 calls took 5.59E-3; 0.4%) (FMT0 Calls 2.35E+3 Time of all outermost calls 1.52 Time per call 6.48E-4 Heap bytes allocated 2.58E+5; 0.0% Heap bytes allocated per call 109.78 To NEWLINE 1.45E+3 calls took 9.67E-1; 63.5% To FMT-PPR 2.23E+2 calls took 4.69E-1; 30.8% To FMT0* 8.46E+2 calls took 4.84E-2; 3.2% To other functions 2.24E+5 calls took 2.85E-2; 1.9% To self/unprofiled functions 1.06E-2; 0.7% From FMT1 1.09E+3 calls took 1.52E+0; 100.0%) (PROVE-LOOP Calls 51 Time of all outermost calls 1.18 Time per call 0.02 Heap bytes allocated 2.04E+7; 2.9% Heap bytes allocated per call 4.01E+5 To PROVE-LOOP0 5.10E+1 calls took 1.18E+0; 100.0% To other functions 1.02E+2 calls took 4.56E-4; 0.0% To self/unprofiled functions 1.27E-4; 0.0% From PROVE 4.40E+1 calls took 1.08E+0; 91.5% From PC-PROVE 7.00E+0 calls took 1.00E-1; 8.5%) (PROVE-LOOP0 Calls 51 Time of all outermost calls 1.18 Time per call 0.02 Heap bytes allocated 2.04E+7; 2.9% Heap bytes allocated per call 4.00E+5 To PROVE-LOOP1 5.10E+1 calls took 1.18E+0; 100.0% To self/unprofiled functions 1.34E-4; 0.0% From PROVE-LOOP 5.10E+1 calls took 1.18E+0; 100.0%) (PROVE-LOOP1 Calls 51 Time of all outermost calls 1.18 Time per call 0.02 Heap bytes allocated 2.04E+7; 2.9% Heap bytes allocated per call 4.00E+5 To PROVE-LOOP2 5.10E+1 calls took 1.18E+0; 100.0% To self/unprofiled functions 1.32E-4; 0.0% To other functions 5.10E+1 calls took 6.00E-6; <0.01% From PROVE-LOOP0 5.10E+1 calls took 1.18E+0; 100.0%) (PROVE-LOOP2 Calls 51 Time of all outermost calls 1.18 Time per call 0.02 Heap bytes allocated 2.04E+7; 2.9% Heap bytes allocated per call 4.00E+5 To WATERFALL 9.00E+1 calls took 5.91E-1; 50.0% To INDUCT 3.70E+1 calls took 4.93E-1; 41.7% To POP-CLAUSE 9.00E+1 calls took 6.19E-2; 5.2% To PROCESS-ASSUMPTIONS 5.30E+1 calls took 3.46E-2; 2.9% To self/unprofiled functions 3.34E-4; 0.0% To other functions 5.30E+1 calls took 1.06E-4; <0.01% From PROVE-LOOP1 5.10E+1 calls took 1.18E+0; 100.0%) (PROVE Calls 45 Time of all outermost calls 1.08 Time per call 0.02 Heap bytes allocated 1.98E+7; 2.8% Heap bytes allocated per call 4.39E+5 To PROVE-LOOP 4.40E+1 calls took 1.08E+0; 100.0% To self/unprofiled functions 3.14E-4; 0.0% To other functions 2.21E+2 calls took 1.68E-4; 0.0% From DEFTHM-FN1 3.80E+1 calls took 9.46E-1; 87.4% From PROVE-GUARD-CLAUSES 3.00E+0 calls took 5.91E-2; 5.5% From THM-FN 1.00E+0 calls took 4.23E-2; 3.9% From PROVE-TERMINATION 3.00E+0 calls took 3.48E-2; 3.2%) (FMS Calls 227 Time of all outermost calls 0.72 Time per call 3.16E-3 Heap bytes allocated 9.66E+4; 0.0% Heap bytes allocated per call 425.44 To FMT1 2.27E+2 calls took 7.16E-1; 99.8% To other functions 2.27E+2 calls took 1.05E-3; 0.1% To self/unprofiled functions 1.25E-4; 0.0% From INDUCT-MSG/CONTINUE 3.30E+1 calls took 4.81E-1; 67.1% From WATERFALL-MSG1 4.80E+1 calls took 1.17E-1; 16.2% From PROVE-GUARD-CLAUSES-MSG 3.00E+0 calls took 4.62E-2; 6.4% From PROCESS-ASSUMPTIONS 5.30E+1 calls took 3.39E-2; 4.7% From PRINT-RULE-STORAGE-DEPENDENCIES 1.20E+1 calls took 2.19E-2; 3.0% From POP-CLAUSE-MSG1 4.10E+1 calls took 1.34E-2; 1.9% From other functions 3.70E+1 calls took 4.11E-3; 0.6%) (WATERFALL Calls 90 Time of all outermost calls 0.59 Time per call 6.57E-3 Heap bytes allocated 1.95E+7; 2.7% Heap bytes allocated per call 2.17E+5 To WATERFALL1-LST 9.00E+1 calls took 5.91E-1; 99.9% To self/unprofiled functions 2.45E-4; 0.0% To other functions 2.72E+2 calls took 7.40E-5; 0.0% From PROVE-LOOP2 9.00E+1 calls took 5.91E-1; 100.0%) (WATERFALL1-LST Calls 464 Time of all outermost calls 0.59 Time per call 1.27E-3 Heap bytes allocated 1.95E+7; 2.7% Heap bytes allocated per call 4.21E+4 To WATERFALL1 1.65E+2 calls took 5.91E-1; 100.0% To self/unprofiled functions 1.59E-4; 0.0% To other functions 5.10E+1 calls took 7.00E-6; <0.01% From WATERFALL 9.00E+1 calls took 5.91E-1; 100.0%) (WATERFALL1 Calls 374 Time of all outermost calls 0.59 Time per call 1.58E-3 Heap bytes allocated 1.95E+7; 2.7% Heap bytes allocated per call 5.22E+4 To WATERFALL0 1.53E+2 calls took 5.27E-1; 89.2% To WATERFALL0-WITH-HINT-SETTINGS 1.20E+1 calls took 3.23E-2; 5.5% To WATERFALL-PRINT-CLAUSE 1.53E+2 calls took 3.08E-2; 5.2% To other functions 4.83E+2 calls took 3.25E-4; 0.1% To self/unprofiled functions 3.09E-4; 0.1% From WATERFALL1-LST 1.65E+2 calls took 5.91E-1; 100.0%) (WATERFALL0 Calls 374 Time of all outermost calls 0.55 Time per call 1.48E-3 Heap bytes allocated 1.85E+7; 2.6% Heap bytes allocated per call 4.95E+4 To WATERFALL-STEP 1.34E+3 calls took 5.20E-1; 94.2% To WATERFALL-PRINT-CLAUSE 2.09E+2 calls took 3.01E-2; 5.5% To other functions 1.95E+3 calls took 1.14E-3; 0.2% To self/unprofiled functions 9.31E-4; 0.2% From WATERFALL1 1.53E+2 calls took 5.27E-1; 95.4% From WATERFALL0-WITH-HINT-SETTINGS 1.20E+1 calls took 2.55E-2; 4.6%) (WATERFALL-STEP Calls 1.34E+3 Time of all outermost calls 0.52 Time per call 3.90E-4 Heap bytes allocated 1.83E+7; 2.6% Heap bytes allocated per call 1.37E+4 To WATERFALL-STEP1 9.59E+2 calls took 3.90E-1; 74.9% To WATERFALL-MSG 3.74E+2 calls took 1.23E-1; 23.6% To other functions 7.38E+3 calls took 6.29E-3; 1.2% To self/unprofiled functions 1.62E-3; 0.3% From WATERFALL0 1.34E+3 calls took 5.20E-1; 100.0%) (PRINT-SUMMARY Calls 70 Time of all outermost calls 0.50 Time per call 7.09E-3 Heap bytes allocated 4.02E+5; 0.1% Heap bytes allocated per call 5.75E+3 To PRINT-RULES-AND-HINT-EVENTS-SUMMARY 6.90E+1 calls took 2.74E-1; 55.1% To PRINT-TIME-SUMMARY 6.90E+1 calls took 1.37E-1; 27.5% To NEWLINE 2.01E+2 calls took 5.54E-2; 11.2% To PRINT-STEPS-SUMMARY 6.90E+1 calls took 2.54E-2; 5.1% To other functions 2.21E+3 calls took 4.24E-3; 0.9% To self/unprofiled functions 8.50E-4; 0.2% From DEFTHM-FN1 3.90E+1 calls took 2.82E-1; 56.9% From DEFUNS-FN 1.40E+1 calls took 1.52E-1; 30.7% From MAKE-EVENT-FN 1.10E+1 calls took 4.95E-2; 10.0% From IN-THEORY-FN 3.00E+0 calls took 1.17E-2; 2.4% From other functions 3.00E+0 calls took 4.79E-4; ?%) (INDUCT Calls 37 Time of all outermost calls 0.49 Time per call 0.01 Heap bytes allocated 6.40E+5; 0.1% Heap bytes allocated per call 1.73E+4 To INDUCT-MSG/CONTINUE 3.70E+1 calls took 4.83E-1; 97.9% To other functions 9.31E+2 calls took 9.91E-3; 2.0% To self/unprofiled functions 6.65E-4; 0.1% From PROVE-LOOP2 3.70E+1 calls took 4.93E-1; 100.0%) (INDUCT-MSG/CONTINUE Calls 37 Time of all outermost calls 0.48 Time per call 0.01 Heap bytes allocated 1.23E+5; 0.0% Heap bytes allocated per call 3.32E+3 To FMS 3.30E+1 calls took 4.81E-1; 99.7% To other functions 4.33E+2 calls took 1.24E-3; 0.3% To self/unprofiled functions 2.91E-4; 0.1% From INDUCT 3.70E+1 calls took 4.83E-1; 100.0%) (FMT-PPR Calls 223 Time of all outermost calls 0.47 Time per call 2.10E-3 Heap bytes allocated 1.06E+5; 0.0% Heap bytes allocated per call 474.69 To PPR2 2.23E+2 calls took 4.60E-1; 98.0% To PPR1 2.23E+2 calls took 8.93E-3; 1.9% To self/unprofiled functions 2.83E-4; 0.1% To other functions 6.69E+2 calls took 1.60E-5; <0.01% From FMT0 2.23E+2 calls took 4.69E-1; 100.0%) (PPR2 Calls 1.31E+3 Time of all outermost calls 0.46 Time per call 3.51E-4 To PPR2-COLUMN 1.64E+2 calls took 3.51E-1; 76.2% To NEWLINE 8.10E+1 calls took 1.08E-1; 23.4% To other functions 9.31E+2 calls took 1.72E-3; 0.4% To self/unprofiled functions 2.49E-4; 0.1% From FMT-PPR 2.23E+2 calls took 4.60E-1; 99.9% From other functions 1.09E+3 calls took 2.35E-4; ?%) (DEFUN-FN Calls 14 Time of all outermost calls 0.43 Time per call 0.03 Heap bytes allocated 5.01E+6; 0.7% Heap bytes allocated per call 3.58E+5 To DEFUNS-FN 1.40E+1 calls took 4.25E-1; 100.0% To self/unprofiled functions 2.00E-5; <0.01% From LD-LOOP 1.30E+1 calls took 3.98E-1; 93.7% From EV-REC-ACL2-UNWIND-PROTECT 1.00E+0 calls took 2.69E-2; 6.3%) (DEFUNS-FN Calls 14 Time of all outermost calls 0.43 Time per call 0.03 Heap bytes allocated 5.01E+6; 0.7% Heap bytes allocated per call 3.58E+5 To DEFUNS-FN0 1.40E+1 calls took 2.49E-1; 58.6% To PRINT-SUMMARY 1.40E+1 calls took 1.52E-1; 35.8% To INSTALL-EVENT-DEFUNS 1.40E+1 calls took 1.90E-2; 4.5% To other functions 3.19E+2 calls took 4.35E-3; 1.0% To self/unprofiled functions 3.07E-4; 0.1% From DEFUN-FN 1.40E+1 calls took 4.25E-1; 100.0%) (WATERFALL-STEP1 Calls 959 Time of all outermost calls 0.39 Time per call 4.07E-4 Heap bytes allocated 1.74E+7; 2.4% Heap bytes allocated per call 1.81E+4 To SIMPLIFY-CLAUSE 2.64E+2 calls took 1.97E-1; 50.4% To PREPROCESS-CLAUSE 3.62E+2 calls took 1.86E-1; 47.8% To ELIMINATE-DESTRUCTORS-CLAUSE 5.40E+1 calls took 5.50E-3; 1.4% To other functions 2.79E+2 calls took 8.43E-4; 0.2% To self/unprofiled functions 7.35E-4; 0.2% From WATERFALL-STEP 9.59E+2 calls took 3.90E-1; 100.0%) (PPR2-COLUMN Calls 360 Time of all outermost calls 0.35 Time per call 9.74E-4 To NEWLINE 6.88E+2 calls took 3.42E-1; 97.6% To PPR2-FLAT 1.05E+3 calls took 7.04E-3; 2.0% To other functions 4.10E+3 calls took 9.53E-4; 0.3% To self/unprofiled functions 4.76E-4; 0.1% From PPR2 1.64E+2 calls took 3.51E-1; 100.0%) (MAKE-EVENT-FN Calls 11 Time of all outermost calls 0.33 Time per call 0.03 Heap bytes allocated 3.95E+6; 0.6% Heap bytes allocated per call 3.59E+5 To MAKE-EVENT-FN1 1.10E+1 calls took 2.33E-1; 70.9% To PRINT-SUMMARY 1.10E+1 calls took 4.95E-2; 15.1% To PROTECTED-EVAL 1.10E+1 calls took 4.52E-2; 13.7% To self/unprofiled functions 4.73E-4; 0.1% To other functions 1.59E+3 calls took 3.70E-4; 0.1% From LD-LOOP 1.00E+1 calls took 2.84E-1; 86.5% From EV-REC-ACL2-UNWIND-PROTECT 1.00E+0 calls took 4.42E-2; 13.5%) (PRINT-RULES-AND-HINT-EVENTS-SUMMARY Calls 69 Time of all outermost calls 0.27 Time per call 3.97E-3 Heap bytes allocated 1.08E+5; 0.0% Heap bytes allocated per call 1.57E+3 To PRINT-RUNES-SUMMARY 6.90E+1 calls took 2.73E-1; 99.7% To other functions 1.38E+2 calls took 7.33E-4; 0.3% To self/unprofiled functions 1.55E-4; 0.1% From PRINT-SUMMARY 6.90E+1 calls took 2.74E-1; 100.0%) (PRINT-RUNES-SUMMARY Calls 69 Time of all outermost calls 0.27 Time per call 3.95E-3 Heap bytes allocated 1.01E+5; 0.0% Heap bytes allocated per call 1.46E+3 To FMT1 6.70E+1 calls took 2.72E-1; 99.8% To other functions 3.84E+2 calls took 5.10E-4; 0.2% To self/unprofiled functions 1.38E-4; 0.1% From PRINT-RULES-AND-HINT-EVENTS-SUMMARY 6.90E+1 calls took 2.73E-1; 100.0%) (DEFUNS-FN0 Calls 14 Time of all outermost calls 0.25 Time per call 0.02 Heap bytes allocated 2.62E+6; 0.4% Heap bytes allocated per call 1.87E+5 To DEFUNS-FN1 1.40E+1 calls took 1.56E-1; 62.7% To PUT-INDUCTION-INFO 1.40E+1 calls took 9.30E-2; 37.3% To self/unprofiled functions 3.80E-5; 0.0% From DEFUNS-FN 1.40E+1 calls took 2.49E-1; 100.0%) (MAKE-EVENT-FN1 Calls 11 Time of all outermost calls 0.23 Time per call 0.02 Heap bytes allocated 3.11E+6; 0.4% Heap bytes allocated per call 2.83E+5 To MAKE-EVENT-FN2 1.10E+1 calls took 2.33E-1; 100.0% To self/unprofiled functions 1.80E-5; <0.01% From MAKE-EVENT-FN 1.10E+1 calls took 2.33E-1; 100.0%) (MAKE-EVENT-FN2 Calls 11 Time of all outermost calls 0.23 Time per call 0.02 Heap bytes allocated 3.11E+6; 0.4% Heap bytes allocated per call 2.83E+5 To DEFTHM-FN 1.00E+1 calls took 2.32E-1; 99.6% To other functions 5.66E+2 calls took 7.87E-4; 0.3% To self/unprofiled functions 1.34E-4; 0.1% From MAKE-EVENT-FN1 1.10E+1 calls took 2.33E-1; 100.0%) (SIMPLIFY-CLAUSE Calls 264 Time of all outermost calls 0.20 Time per call 7.45E-4 Heap bytes allocated 5.82E+6; 0.8% Heap bytes allocated per call 2.20E+4 To SIMPLIFY-CLAUSE1 2.64E+2 calls took 1.95E-1; 99.3% To other functions 2.64E+2 calls took 1.18E-3; 0.6% To self/unprofiled functions 2.49E-4; 0.1% From WATERFALL-STEP1 2.64E+2 calls took 1.97E-1; 100.0%) (SIMPLIFY-CLAUSE1 Calls 264 Time of all outermost calls 0.20 Time per call 7.39E-4 Heap bytes allocated 5.75E+6; 0.8% Heap bytes allocated per call 2.18E+4 To REWRITE-CLAUSE 2.54E+2 calls took 1.69E-1; 86.6% To FORWARD-CHAIN-TOP 2.64E+2 calls took 1.43E-2; 7.3% To SETUP-SIMPLIFY-CLAUSE-POT-LST 2.57E+2 calls took 8.80E-3; 4.5% To other functions 1.67E+3 calls took 2.11E-3; 1.1% To self/unprofiled functions 9.85E-4; 0.5% From SIMPLIFY-CLAUSE 2.64E+2 calls took 1.95E-1; 100.0%) (PREPROCESS-CLAUSE Calls 362 Time of all outermost calls 0.19 Time per call 5.15E-4 Heap bytes allocated 1.12E+7; 1.6% Heap bytes allocated per call 3.09E+4 To TAU-CLAUSEP-LST 3.11E+2 calls took 1.41E-1; 75.8% To BUILT-IN-CLAUSEP 2.77E+2 calls took 2.36E-2; 12.7% To EXPAND-ABBREVIATIONS 3.54E+2 calls took 9.93E-3; 5.3% To CLAUSIFY-INPUT 3.54E+2 calls took 9.31E-3; 5.0% To other functions 1.63E+3 calls took 1.30E-3; 0.7% To self/unprofiled functions 8.61E-4; 0.5% From WATERFALL-STEP1 3.62E+2 calls took 1.86E-1; 100.0%) (PROOF-BUILDER Calls 1 Time of all outermost calls 0.18 Time per call 0.18 Heap bytes allocated 1.06E+6; 0.1% Heap bytes allocated per call 1.06E+6 To STATE-STACK-FROM-INSTRUCTIONS 1.00E+0 calls took 1.82E-1; 100.0% To self/unprofiled functions 2.90E-5; 0.0% To other functions 2.00E+0 calls took 1.00E-6; <0.01% From DEFTHM-FN1 1.00E+0 calls took 1.82E-1; 100.0%) (STATE-STACK-FROM-INSTRUCTIONS Calls 1 Time of all outermost calls 0.18 Time per call 0.18 Heap bytes allocated 1.06E+6; 0.1% Heap bytes allocated per call 1.06E+6 To PC-MAIN 1.00E+0 calls took 1.82E-1; 100.0% To other functions 4.00E+0 calls took 4.40E-5; 0.0% To self/unprofiled functions 8.00E-6; <0.01% From PROOF-BUILDER 1.00E+0 calls took 1.82E-1; 100.0%) (PC-MAIN Calls 1 Time of all outermost calls 0.18 Time per call 0.18 Heap bytes allocated 1.06E+6; 0.1% Heap bytes allocated per call 1.06E+6 To PC-MAIN1 1.00E+0 calls took 1.82E-1; 100.0% To self/unprofiled functions 1.40E-5; <0.01% To other functions 3.00E+0 calls took 2.00E-6; <0.01% From STATE-STACK-FROM-INSTRUCTIONS 1.00E+0 calls took 1.82E-1; 100.0%) (PC-MAIN1 Calls 1 Time of all outermost calls 0.18 Time per call 0.18 Heap bytes allocated 1.06E+6; 0.1% Heap bytes allocated per call 1.06E+6 To PC-MAIN-LOOP 1.00E+0 calls took 1.82E-1; 100.0% To self/unprofiled functions 1.20E-5; <0.01% From PC-MAIN 1.00E+0 calls took 1.82E-1; 100.0%) (PC-MAIN-LOOP Calls 6 Time of all outermost calls 0.18 Time per call 0.03 Heap bytes allocated 1.06E+6; 0.1% Heap bytes allocated per call 1.77E+5 To PC-SINGLE-STEP 1.80E+1 calls took 1.82E-1; 99.6% To other functions 1.44E+2 calls took 6.32E-4; 0.3% To self/unprofiled functions 6.90E-5; 0.0% From PC-MAIN1 1.00E+0 calls took 1.82E-1; 100.0%) (PC-SINGLE-STEP Calls 26 Time of all outermost calls 0.18 Time per call 6.98E-3 Heap bytes allocated 1.05E+6; 0.1% Heap bytes allocated per call 4.05E+4 To PC-SINGLE-STEP-1 1.80E+1 calls took 1.81E-1; 99.8% To other functions 9.90E+1 calls took 2.45E-4; 0.1% To self/unprofiled functions 6.00E-5; 0.0% From PC-MAIN-LOOP 1.80E+1 calls took 1.82E-1; 100.0%) (PC-SINGLE-STEP-1 Calls 26 Time of all outermost calls 0.18 Time per call 6.97E-3 Heap bytes allocated 1.05E+6; 0.1% Heap bytes allocated per call 4.04E+4 To PC-SINGLE-STEP-PRIMITIVE 1.50E+1 calls took 1.74E-1; 96.1% To ACL2-PC::SEQUENCE 3.00E+0 calls took 4.51E-3; 2.5% To PC-MACROEXPAND 1.80E+1 calls took 2.45E-3; 1.4% To other functions 1.83E+2 calls took 9.10E-5; 0.1% To self/unprofiled functions 7.40E-5; 0.0% From PC-SINGLE-STEP 1.80E+1 calls took 1.81E-1; 100.0%) (PC-SINGLE-STEP-PRIMITIVE Calls 21 Time of all outermost calls 0.18 Time per call 8.46E-3 Heap bytes allocated 9.32E+5; 0.1% Heap bytes allocated per call 4.44E+4 To ACL2-PC::PROVE 7.00E+0 calls took 1.04E-1; 58.5% To MAYBE-PRINT-PROVED-GOAL-MESSAGE 2.10E+1 calls took 6.74E-2; 37.9% To ACL2-PC::S 3.00E+0 calls took 4.14E-3; 2.3% To other functions 1.02E+3 calls took 1.50E-3; 0.8% To self/unprofiled functions 6.86E-4; 0.4% From PC-SINGLE-STEP-1 1.50E+1 calls took 1.74E-1; 98.0% From ACL2-PC::SEQUENCE 6.00E+0 calls took 3.56E-3; 2.0%) (LD-PRINT-COMMAND Calls 59 Time of all outermost calls 0.18 Time per call 3.01E-3 Heap bytes allocated 3.44E+4; 0.0% Heap bytes allocated per call 582.24 To FMT1 5.70E+1 calls took 1.77E-1; 99.9% To self/unprofiled functions 9.60E-5; 0.1% To other functions 1.73E+2 calls took 1.70E-5; <0.01% From LD-LOOP 5.70E+1 calls took 1.77E-1; 100.0% From other functions 2.00E+0 calls took 7.00E-6; ?%) (REWRITE-CLAUSE Calls 872 Time of all outermost calls 0.17 Time per call 1.94E-4 Heap bytes allocated 4.85E+6; 0.7% Heap bytes allocated per call 5.56E+3 To REWRITE-CLAUSE-LST 2.54E+2 calls took 1.33E-1; 78.8% To REWRITE-ATM 2.54E+2 calls took 2.62E-2; 15.5% To REWRITE-CLAUSE-TYPE-ALIST 2.54E+2 calls took 5.21E-3; 3.1% To CLAUSIFY 2.54E+2 calls took 2.73E-3; 1.6% To self/unprofiled functions 8.72E-4; 0.5% To other functions 2.21E+3 calls took 8.62E-4; 0.5% From SIMPLIFY-CLAUSE1 2.54E+2 calls took 1.69E-1; 100.0%) (DEFUNS-FN1 Calls 14 Time of all outermost calls 0.16 Time per call 0.01 Heap bytes allocated 1.53E+6; 0.2% Heap bytes allocated per call 1.09E+5 To VERIFY-GUARDS-FN1 4.00E+0 calls took 1.09E-1; 69.6% To PRINT-DEFUN-MSG 1.40E+1 calls took 4.37E-2; 28.0% To other functions 3.82E+2 calls took 3.53E-3; 2.3% To self/unprofiled functions 2.01E-4; 0.1% From DEFUNS-FN0 1.40E+1 calls took 1.56E-1; 100.0%) (REWRITE Calls 2.32E+4 Time of all outermost calls 0.14 Time per call 6.23E-6 Heap bytes allocated 3.31E+6; 0.5% Heap bytes allocated per call 142.29 To REWRITE-ARGS 7.21E+2 calls took 7.56E-2; 52.2% To REWRITE-WITH-LEMMAS 7.11E+2 calls took 6.45E-2; 44.5% To REWRITE-PRIMITIVE 7.11E+2 calls took 2.58E-3; 1.8% To other functions 5.21E+3 calls took 1.10E-3; 0.8% To self/unprofiled functions 1.04E-3; 0.7% From REWRITE-ATM 7.26E+2 calls took 1.38E-1; 95.5% From REWRITE-LINEAR-TERM 4.00E+0 calls took 4.10E-3; 2.8% From PC-REWRITE*-1 3.00E+0 calls took 2.37E-3; 1.6% From other functions 2.25E+4 calls took 3.00E-5; ?%) (REWRITE-ATM Calls 730 Time of all outermost calls 0.14 Time per call 1.95E-4 Heap bytes allocated 3.32E+6; 0.5% Heap bytes allocated per call 4.55E+3 To REWRITE 7.26E+2 calls took 1.38E-1; 97.4% To KNOWN-WHETHER-NIL 7.30E+2 calls took 2.63E-3; 1.8% To self/unprofiled functions 6.44E-4; 0.5% To other functions 3.97E+3 calls took 4.93E-4; 0.3% From REWRITE-CLAUSE-LST 4.76E+2 calls took 1.16E-1; 81.6% From REWRITE-CLAUSE 2.54E+2 calls took 2.62E-2; 18.4%) (TAU-CLAUSEP-LST Calls 311 Time of all outermost calls 0.14 Time per call 4.54E-4 Heap bytes allocated 9.37E+6; 1.3% Heap bytes allocated per call 3.01E+4 To TAU-CLAUSEP-LST-REC 3.11E+2 calls took 1.40E-1; 99.3% To other functions 6.22E+2 calls took 7.37E-4; 0.5% To self/unprofiled functions 2.91E-4; 0.2% From PREPROCESS-CLAUSE 3.11E+2 calls took 1.41E-1; 100.0%) (TAU-CLAUSEP-LST-REC Calls 311 Time of all outermost calls 0.14 Time per call 4.51E-4 Heap bytes allocated 9.37E+6; 1.3% Heap bytes allocated per call 3.01E+4 To TAU-CLAUSEP 3.22E+2 calls took 1.39E-1; 99.4% To other functions 3.22E+2 calls took 6.10E-4; 0.4% To self/unprofiled functions 2.44E-4; 0.2% From TAU-CLAUSEP-LST 3.11E+2 calls took 1.40E-1; 100.0%) (TAU-CLAUSEP Calls 322 Time of all outermost calls 0.14 Time per call 4.33E-4 Heap bytes allocated 9.36E+6; 1.3% Heap bytes allocated per call 2.91E+4 To TAU-CLAUSE1P 3.19E+2 calls took 1.21E-1; 86.6% To CHEAP-TYPE-ALIST-AND-POT-LST 3.22E+2 calls took 1.71E-2; 12.3% To other functions 9.60E+2 calls took 1.13E-3; 0.8% To self/unprofiled functions 3.96E-4; 0.3% From TAU-CLAUSEP-LST-REC 3.22E+2 calls took 1.39E-1; 100.0%) (PRINT-TIME-SUMMARY Calls 69 Time of all outermost calls 0.14 Time per call 1.98E-3 Heap bytes allocated 1.26E+5; 0.0% Heap bytes allocated per call 1.83E+3 To NEWLINE 6.70E+1 calls took 1.35E-1; 98.6% To other functions 1.82E+3 calls took 1.62E-3; 1.2% To self/unprofiled functions 3.45E-4; 0.3% From PRINT-SUMMARY 6.90E+1 calls took 1.37E-1; 100.0%) (REWRITE-WITH-LEMMAS Calls 1.31E+4 Time of all outermost calls 0.14 Time per call 1.04E-5 Heap bytes allocated 3.14E+6; 0.4% Heap bytes allocated per call 239.84 To REWRITE-WITH-LEMMAS1 1.60E+3 calls took 1.32E-1; 96.4% To other functions 6.17E+3 calls took 4.05E-3; 3.0% To self/unprofiled functions 8.15E-4; 0.6% From REWRITE-ARGS 2.99E+3 calls took 7.19E-2; 52.7% From REWRITE 7.11E+2 calls took 6.45E-2; 47.2% From other functions 9.40E+3 calls took 1.18E-4; ?%) (REWRITE-WITH-LEMMAS1 Calls 1.24E+4 Time of all outermost calls 0.13 Time per call 1.08E-5 Heap bytes allocated 3.12E+6; 0.4% Heap bytes allocated per call 252.78 To REWRITE-WITH-LEMMA 2.61E+3 calls took 1.33E-1; 99.5% To self/unprofiled functions 5.53E-4; 0.4% To other functions 2.99E+3 calls took 1.22E-4; 0.1% From REWRITE-WITH-LEMMAS 1.60E+3 calls took 1.32E-1; 98.6% From other functions 1.08E+4 calls took 1.90E-3; 1.4%) (REWRITE-CLAUSE-LST Calls 730 Time of all outermost calls 0.13 Time per call 1.82E-4 Heap bytes allocated 3.84E+6; 0.5% Heap bytes allocated per call 5.26E+3 To REWRITE-ATM 4.76E+2 calls took 1.16E-1; 87.1% To REWRITE-CLAUSE-TYPE-ALIST 4.76E+2 calls took 1.08E-2; 8.1% To CLAUSIFY 4.76E+2 calls took 2.23E-3; 1.7% To CRUNCH-CLAUSE-SEGMENTS 6.18E+2 calls took 2.03E-3; 1.5% To other functions 6.16E+3 calls took 1.10E-3; 0.8% To self/unprofiled functions 1.10E-3; 0.8% From REWRITE-CLAUSE 2.54E+2 calls took 1.33E-1; 100.0%) (REWRITE-WITH-LEMMA Calls 1.75E+4 Time of all outermost calls 0.13 Time per call 7.59E-6 Heap bytes allocated 3.12E+6; 0.4% Heap bytes allocated per call 178.45 To REWRITE-FNCALL 8.05E+2 calls took 1.01E-1; 75.9% To RELIEVE-HYPS 5.03E+2 calls took 2.74E-2; 20.6% To other functions 1.29E+4 calls took 3.16E-3; 2.4% To self/unprofiled functions 1.40E-3; 1.1% From REWRITE-WITH-LEMMAS1 2.61E+3 calls took 1.33E-1; 100.0%) (WATERFALL-MSG Calls 374 Time of all outermost calls 0.12 Time per call 3.28E-4 Heap bytes allocated 7.61E+5; 0.1% Heap bytes allocated per call 2.04E+3 To WATERFALL-MSG1 3.74E+2 calls took 1.17E-1; 95.8% To INCREMENT-TIMER 7.48E+2 calls took 2.95E-3; 2.4% To other functions 1.92E+3 calls took 1.26E-3; 1.0% To self/unprofiled functions 9.91E-4; 0.8% From WATERFALL-STEP 3.74E+2 calls took 1.23E-1; 100.0%) (REWRITE-FNCALL Calls 2.89E+3 Time of all outermost calls 0.12 Time per call 4.24E-5 Heap bytes allocated 2.79E+6; 0.4% Heap bytes allocated per call 966.31 To REWRITE-IF 1.01E+3 calls took 1.08E-1; 87.8% To other functions 3.13E+4 calls took 5.71E-3; 4.7% To REWRITE-FNCALLP 9.81E+2 calls took 2.68E-3; 2.2% To self/unprofiled functions 2.63E-3; 2.1% To REWRITE-PRIMITIVE 1.10E+3 calls took 2.36E-3; 1.9% To REWRITE-ARGS 1.11E+3 calls took 1.55E-3; 1.3% From REWRITE-WITH-LEMMA 8.05E+2 calls took 1.01E-1; 82.4% From RELIEVE-HYP 1.26E+2 calls took 1.90E-2; 15.5% From REWRITE-WITH-LEMMAS 2.00E+0 calls took 1.31E-3; 1.1% From other functions 1.96E+3 calls took 1.27E-3; 1.0%) (TAU-CLAUSE1P Calls 319 Time of all outermost calls 0.12 Time per call 3.78E-4 Heap bytes allocated 8.68E+6; 1.2% Heap bytes allocated per call 2.72E+4 To TAU-ASSUME 1.04E+3 calls took 1.20E-1; 99.8% To self/unprofiled functions 2.52E-4; 0.2% From TAU-CLAUSEP 3.19E+2 calls took 1.21E-1; 100.0%) (TAU-ASSUME Calls 1.06E+3 Time of all outermost calls 0.12 Time per call 1.14E-4 Heap bytes allocated 8.68E+6; 1.2% Heap bytes allocated per call 8.22E+3 To TAU-ASSUME-BASIC 6.13E+2 calls took 9.86E-2; 81.9% To ADD-TO-TAU! 4.19E+2 calls took 1.97E-2; 16.4% To other functions 2.51E+3 calls took 1.43E-3; 1.2% To self/unprofiled functions 6.70E-4; 0.6% From TAU-CLAUSE1P 1.04E+3 calls took 1.20E-1; 100.0%) (WATERFALL-MSG1 Calls 374 Time of all outermost calls 0.12 Time per call 3.14E-4 Heap bytes allocated 3.84E+4; 0.0% Heap bytes allocated per call 102.55 To FMS 4.80E+1 calls took 1.17E-1; 99.2% To other functions 4.22E+2 calls took 6.90E-4; 0.6% To self/unprofiled functions 2.39E-4; 0.2% From WATERFALL-MSG 3.74E+2 calls took 1.17E-1; 100.0%) (ADD-TO-TAU! Calls 1.95E+3 Time of all outermost calls 0.11 Time per call 5.82E-5 Heap bytes allocated 8.62E+6; 1.2% Heap bytes allocated per call 4.43E+3 To APPLY-CONJUNCTIVE-TAU-RULES 1.86E+3 calls took 6.07E-2; 53.6% To ADD-TO-TAU 1.95E+3 calls took 5.21E-2; 46.0% To self/unprofiled functions 4.95E-4; 0.4% From APPLY-SIGNATURE-TAU-RULES1 8.98E+2 calls took 5.30E-2; 46.8% From TAU-ASSUME-BASIC 6.13E+2 calls took 3.99E-2; 35.2% From TAU-ASSUME 4.19E+2 calls took 1.97E-2; 17.4% From other functions 1.60E+1 calls took 5.63E-4; ?%) (REWRITE-IF Calls 2.78E+3 Time of all outermost calls 0.11 Time per call 3.94E-5 Heap bytes allocated 2.62E+6; 0.4% Heap bytes allocated per call 940.48 To REWRITE-IF-FINISH 8.40E+2 calls took 9.66E-2; 88.1% To other functions 2.32E+4 calls took 4.26E-3; 3.9% To ASSUME-TRUE-FALSE 8.40E+2 calls took 3.03E-3; 2.8% To REWRITE-ARGS 6.44E+2 calls took 2.39E-3; 2.2% To RELIEVE-HYPS 3.40E+2 calls took 1.83E-3; 1.7% To self/unprofiled functions 1.60E-3; 1.5% From REWRITE-FNCALL 1.01E+3 calls took 1.08E-1; 98.0% From REWRITE-WITH-LEMMAS 1.50E+1 calls took 1.14E-3; 1.0% From other functions 1.76E+3 calls took 1.00E-3; 0.9%) (VERIFY-GUARDS-FN1 Calls 4 Time of all outermost calls 0.11 Time per call 0.03 Heap bytes allocated 1.41E+6; 0.2% Heap bytes allocated per call 3.52E+5 To PROVE-GUARD-CLAUSES 4.00E+0 calls took 1.08E-1; 99.8% To other functions 4.80E+1 calls took 2.32E-4; 0.2% To self/unprofiled functions 3.70E-5; 0.0% From DEFUNS-FN1 4.00E+0 calls took 1.09E-1; 100.0%) (PROVE-GUARD-CLAUSES Calls 4 Time of all outermost calls 0.11 Time per call 0.03 Heap bytes allocated 1.40E+6; 0.2% Heap bytes allocated per call 3.51E+5 To PROVE 3.00E+0 calls took 5.91E-2; 54.5% To PROVE-GUARD-CLAUSES-MSG 4.00E+0 calls took 4.63E-2; 42.7% To GUARD-OBLIGATION-CLAUSES 4.00E+0 calls took 2.30E-3; 2.1% To other functions 8.80E+1 calls took 6.37E-4; 0.6% To self/unprofiled functions 6.20E-5; 0.1% From VERIFY-GUARDS-FN1 4.00E+0 calls took 1.08E-1; 100.0%) (ACL2-PC::PROVE Calls 7 Time of all outermost calls 0.10 Time per call 0.01 Heap bytes allocated 8.54E+5; 0.1% Heap bytes allocated per call 1.22E+5 To PROVER-CALL 7.00E+0 calls took 1.04E-1; 99.8% To other functions 5.20E+1 calls took 1.11E-4; 0.1% To self/unprofiled functions 7.50E-5; 0.1% From PC-SINGLE-STEP-PRIMITIVE 7.00E+0 calls took 1.04E-1; 100.0%) (PROVER-CALL Calls 7 Time of all outermost calls 0.10 Time per call 0.01 Heap bytes allocated 8.51E+5; 0.1% Heap bytes allocated per call 1.22E+5 To PC-PROVE 7.00E+0 calls took 1.01E-1; 96.9% To TRANSLATE-HINTS+ 7.00E+0 calls took 2.41E-3; 2.3% To other functions 1.12E+2 calls took 7.02E-4; 0.7% To self/unprofiled functions 9.40E-5; 0.1% From ACL2-PC::PROVE 7.00E+0 calls took 1.04E-1; 100.0%) (REWRITE-ARGS Calls 1.11E+4 Time of all outermost calls 0.10 Time per call 9.24E-6 Heap bytes allocated 1.90E+6; 0.3% Heap bytes allocated per call 170.67 To REWRITE-WITH-LEMMAS 2.99E+3 calls took 7.19E-2; 70.0% To other functions 8.61E+4 calls took 7.90E-3; 7.7% To RELIEVE-HYPS 1.51E+3 calls took 6.25E-3; 6.1% To self/unprofiled functions 5.43E-3; 5.3% To REWRITE-SOLIDIFY-PLUS 5.07E+3 calls took 3.81E-3; 3.7% To REWRITE-PRIMITIVE 2.85E+3 calls took 1.57E-3; 1.5% To GENEQV-AND-PEQUIV-INFO-FOR-REWRITE 7.82E+3 calls took 1.34E-3; 1.3% To REWRITE-SOLIDIFY 2.18E+3 calls took 1.27E-3; 1.2% To KNOWN-WHETHER-NIL 4.78E+2 calls took 1.14E-3; 1.1% To ONE-WAY-UNIFY-RESTRICTIONS 3.37E+3 calls took 1.04E-3; 1.0% To REWRITE-WITH-LEMMAS1 2.03E+3 calls took 1.03E-3; 1.0% From REWRITE 7.21E+2 calls took 7.56E-2; 73.6% From REWRITE-IF-FINISH 5.35E+3 calls took 2.08E-2; 20.2% From REWRITE-IF 6.44E+2 calls took 2.39E-3; 2.3% From other functions 3.29E+3 calls took 2.36E-3; 2.3% From REWRITE-FNCALL 1.11E+3 calls took 1.55E-3; 1.5%) (PC-PROVE Calls 7 Time of all outermost calls 0.10 Time per call 0.01 Heap bytes allocated 7.07E+5; 0.1% Heap bytes allocated per call 1.01E+5 To PROVE-LOOP 7.00E+0 calls took 1.00E-1; 99.9% To other functions 2.80E+1 calls took 8.40E-5; 0.1% To self/unprofiled functions 4.00E-5; 0.0% From PROVER-CALL 7.00E+0 calls took 1.01E-1; 100.0%) (TAU-ASSUME-BASIC Calls 621 Time of all outermost calls 0.10 Time per call 1.59E-4 Heap bytes allocated 7.68E+6; 1.1% Heap bytes allocated per call 1.24E+4 To TAU-TERM 6.13E+2 calls took 5.85E-2; 59.3% To ADD-TO-TAU! 6.13E+2 calls took 3.99E-2; 40.5% To self/unprofiled functions 2.28E-4; 0.2% From TAU-ASSUME 6.13E+2 calls took 9.86E-2; 100.0%) (REWRITE-IF-FINISH Calls 2.07E+3 Time of all outermost calls 0.10 Time per call 4.69E-5 Heap bytes allocated 2.31E+6; 0.3% Heap bytes allocated per call 1.12E+3 To REWRITE-ARGS 5.35E+3 calls took 2.08E-2; 21.4% To RELIEVE-HYPS 2.75E+3 calls took 2.05E-2; 21.1% To other functions 1.73E+5 calls took 1.09E-2; 11.2% To self/unprofiled functions 1.07E-2; 11.0% To REWRITE-PRIMITIVE 5.33E+3 calls took 5.94E-3; 6.1% To REWRITE-SOLIDIFY 8.28E+3 calls took 5.59E-3; 5.8% To ASSUME-TRUE-FALSE 1.05E+3 calls took 4.44E-3; 4.6% To ONE-WAY-UNIFY-RESTRICTIONS 7.87E+3 calls took 2.98E-3; 3.1% To RELIEVE-HYPS1-FREE-1 1.97E+2 calls took 2.93E-3; 3.0% To REWRITE-SOLIDIFY-PLUS 3.55E+3 calls took 2.52E-3; 2.6% To RW-CACHE-EXIT-CONTEXT 3.79E+3 calls took 2.15E-3; 2.2% To REWRITE-IF1 1.90E+3 calls took 1.50E-3; 1.5% To DEF-BODY 7.86E+3 calls took 1.35E-3; 1.4% To EXPAND-PERMISSION-RESULT 6.78E+3 calls took 1.28E-3; 1.3% To REWRITE-FNCALLP 3.39E+2 calls took 1.28E-3; 1.3% To PEQUIVS-FOR-REWRITE-ARGS 5.35E+3 calls took 1.16E-3; 1.2% To GENEQV-AND-PEQUIV-INFO-FOR-REWRITE 5.95E+3 calls took 1.04E-3; 1.1% From REWRITE-IF 8.40E+2 calls took 9.66E-2; 99.6% From other functions 1.23E+3 calls took 3.75E-4; ?%) (PUT-INDUCTION-INFO Calls 14 Time of all outermost calls 0.09 Time per call 6.65E-3 Heap bytes allocated 1.09E+6; 0.2% Heap bytes allocated per call 7.81E+4 To PROVE-TERMINATION-RECURSIVE 1.20E+1 calls took 9.11E-2; 97.9% To other functions 8.00E+1 calls took 1.86E-3; 2.0% To self/unprofiled functions 6.50E-5; 0.1% From DEFUNS-FN0 1.40E+1 calls took 9.30E-2; 100.0%) (PROVE-TERMINATION-RECURSIVE Calls 12 Time of all outermost calls 0.09 Time per call 7.59E-3 Heap bytes allocated 1.05E+6; 0.1% Heap bytes allocated per call 8.76E+4 To PROVE-TERMINATION 1.20E+1 calls took 9.10E-2; 99.8% To other functions 3.60E+1 calls took 1.15E-4; 0.1% To self/unprofiled functions 3.70E-5; 0.0% From PUT-INDUCTION-INFO 1.20E+1 calls took 9.11E-2; 100.0%) (PROVE-TERMINATION Calls 14 Time of all outermost calls 0.09 Time per call 6.51E-3 Heap bytes allocated 1.05E+6; 0.1% Heap bytes allocated per call 7.51E+4 To FMT 1.70E+1 calls took 5.38E-2; 59.0% To PROVE 3.00E+0 calls took 3.48E-2; 38.2% To other functions 2.55E+2 calls took 1.22E-3; 1.3% To CLEAN-UP-CLAUSE-SET 1.20E+1 calls took 1.11E-3; 1.2% To self/unprofiled functions 1.72E-4; 0.2% From PROVE-TERMINATION-RECURSIVE 1.20E+1 calls took 9.10E-2; 99.9% From other functions 2.00E+0 calls took 1.28E-4; ?%) (CHK-ACCEPTABLE-RULES Calls 39 Time of all outermost calls 0.09 Time per call 2.23E-3 Heap bytes allocated 4.32E+4; 0.0% Heap bytes allocated per call 1.11E+3 To CHK-ACCEPTABLE-X-RULES 3.70E+1 calls took 8.68E-2; 99.9% To self/unprofiled functions 6.40E-5; 0.1% To other functions 1.15E+2 calls took 1.40E-5; 0.0% From DEFTHM-FN1 3.90E+1 calls took 8.69E-2; 100.0%) (CHK-ACCEPTABLE-X-RULES Calls 37 Time of all outermost calls 0.09 Time per call 2.35E-3 Heap bytes allocated 4.32E+4; 0.0% Heap bytes allocated per call 1.17E+3 To CHK-ACCEPTABLE-X-RULE 3.80E+1 calls took 8.68E-2; 99.9% To self/unprofiled functions 5.30E-5; 0.1% To other functions 3.80E+1 calls took 1.00E-6; <0.01% From CHK-ACCEPTABLE-RULES 3.70E+1 calls took 8.68E-2; 100.0%) (CHK-ACCEPTABLE-X-RULE Calls 38 Time of all outermost calls 0.09 Time per call 2.28E-3 Heap bytes allocated 4.32E+4; 0.0% Heap bytes allocated per call 1.14E+3 To CHK-ACCEPTABLE-REWRITE-RULE 2.60E+1 calls took 8.32E-2; 95.9% To CHK-ACCEPTABLE-EQUIVALENCE-RULE 2.00E+0 calls took 2.93E-3; 3.4% To other functions 1.02E+2 calls took 5.98E-4; 0.7% To self/unprofiled functions 4.70E-5; 0.1% From CHK-ACCEPTABLE-X-RULES 3.80E+1 calls took 8.68E-2; 100.0%) (WARNING1 Calls 12 Time of all outermost calls 0.08 Time per call 7.01E-3 Heap bytes allocated 6.21E+3; 0.0% Heap bytes allocated per call 517.33 To WARNING1-BODY 1.20E+1 calls took 8.40E-2; 99.9% To self/unprofiled functions 2.80E-5; 0.0% To other functions 4.20E+1 calls took 2.30E-5; 0.0% From SHOW-DOUBLE-REWRITE-OPPORTUNITIES1 5.00E+0 calls took 5.45E-2; 64.9% From CHK-REWRITE-RULE-WARNINGS 4.00E+0 calls took 2.63E-2; 31.3% From CHK-ACCEPTABLE-EQUIVALENCE-RULE 1.00E+0 calls took 2.81E-3; 3.3% From other functions 2.00E+0 calls took 3.99E-4; ?%) (FMT-ABBREV1 Calls 28 Time of all outermost calls 0.08 Time per call 3.00E-3 Heap bytes allocated 4.38E+3; 0.0% Heap bytes allocated per call 156.57 To FMT1 5.60E+1 calls took 8.40E-2; 99.9% To self/unprofiled functions 3.20E-5; 0.0% To other functions 2.80E+1 calls took 2.90E-5; 0.0% From FMT-ABBREV 1.30E+1 calls took 8.35E-2; 99.4% From other functions 1.50E+1 calls took 5.08E-4; ?%) (WARNING1-BODY Calls 12 Time of all outermost calls 0.08 Time per call 7.00E-3 Heap bytes allocated 4.29E+3; 0.0% Heap bytes allocated per call 357.33 To FMT-ABBREV 1.20E+1 calls took 8.35E-2; 99.4% To other functions 4.50E+1 calls took 4.89E-4; 0.6% To self/unprofiled functions 4.10E-5; 0.0% From WARNING1 1.20E+1 calls took 8.40E-2; 100.0%) (FMT-ABBREV Calls 13 Time of all outermost calls 0.08 Time per call 6.43E-3 Heap bytes allocated 2.13E+3; 0.0% Heap bytes allocated per call 163.69 To FMT-ABBREV1 1.30E+1 calls took 8.35E-2; 100.0% To self/unprofiled functions 1.10E-5; 0.0% From WARNING1-BODY 1.20E+1 calls took 8.35E-2; 99.9% From other functions 1.00E+0 calls took 6.50E-5; ?%) (CHK-ACCEPTABLE-REWRITE-RULE Calls 26 Time of all outermost calls 0.08 Time per call 3.20E-3 Heap bytes allocated 3.35E+4; 0.0% Heap bytes allocated per call 1.29E+3 To CHK-ACCEPTABLE-REWRITE-RULE1 2.60E+1 calls took 8.29E-2; 99.6% To other functions 1.04E+2 calls took 2.46E-4; 0.3% To self/unprofiled functions 7.30E-5; 0.1% From CHK-ACCEPTABLE-X-RULE 2.60E+1 calls took 8.32E-2; 100.0%) (CHK-ACCEPTABLE-REWRITE-RULE1 Calls 26 Time of all outermost calls 0.08 Time per call 3.19E-3 Heap bytes allocated 2.98E+4; 0.0% Heap bytes allocated per call 1.15E+3 To CHK-ACCEPTABLE-REWRITE-RULE2 2.80E+1 calls took 8.28E-2; 100.0% To self/unprofiled functions 3.50E-5; 0.0% To other functions 2.80E+1 calls took 1.00E-6; <0.01% From CHK-ACCEPTABLE-REWRITE-RULE 2.60E+1 calls took 8.29E-2; 100.0%) (CHK-ACCEPTABLE-REWRITE-RULE2 Calls 28 Time of all outermost calls 0.08 Time per call 2.96E-3 Heap bytes allocated 2.98E+4; 0.0% Heap bytes allocated per call 1.07E+3 To CHK-REWRITE-RULE-WARNINGS 2.80E+1 calls took 8.21E-2; 99.1% To other functions 5.60E+1 calls took 7.00E-4; 0.8% To self/unprofiled functions 6.00E-5; 0.1% From CHK-ACCEPTABLE-REWRITE-RULE1 2.80E+1 calls took 8.28E-2; 100.0%) (CHK-REWRITE-RULE-WARNINGS Calls 28 Time of all outermost calls 0.08 Time per call 2.93E-3 Heap bytes allocated 2.06E+4; 0.0% Heap bytes allocated per call 737.14 To SHOW-DOUBLE-REWRITE-OPPORTUNITIES 5.00E+0 calls took 5.45E-2; 66.5% To WARNING1 4.00E+0 calls took 2.63E-2; 32.1% To other functions 6.80E+2 calls took 8.99E-4; 1.1% To self/unprofiled functions 2.93E-4; 0.4% From CHK-ACCEPTABLE-REWRITE-RULE2 2.80E+1 calls took 8.21E-2; 100.0%) NIL ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(encapsulate () (defun f1 (x) x) (defun f2 (x) x) (defun f3 (x) Y) ; BUG! (defun f4 (x) x)) To verify that the four encapsulated events correctly extend the current theory we will evaluate them. The theory thus constructed is only ephemeral. Encapsulated Events: ACL2 !>>(DEFUN F1 (X) X) Since F1 is non-recursive, its admission is trivial. We observe that the type of F1 is described by the theorem (EQUAL (F1 X) X). Summary Form: ( DEFUN F1 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F1 ACL2 !>>(DEFUN F2 (X) X) Since F2 is non-recursive, its admission is trivial. We observe that the type of F2 is described by the theorem (EQUAL (F2 X) X). Summary Form: ( DEFUN F2 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F2 ACL2 !>>(DEFUN F3 (X) Y) ACL2 Error in ( DEFUN F3 ...): The body of F3 is a free variable occurrence. Summary Form: ( DEFUN F3 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ACL2 Error [Failure] in ( DEFUN F3 ...): See :DOC failure. ******** FAILED ******** ACL2 Warning in ( ENCAPSULATE NIL (DEFUN F1 ...) ...): The attempted ENCAPSULATE has failed while trying to establish the admissibility of one of the (local or non-local) forms in the body of the ENCAPSULATE. Summary Form: ( ENCAPSULATE NIL (DEFUN F1 ...) ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ACL2 Error [Failure] in ( ENCAPSULATE NIL (DEFUN F1 ...) ...): See :DOC failure. ******** FAILED ******** ACL2 !>:pbt 0 0:x(EXIT-BOOT-STRAP-MODE) ACL2 !>:redo-flat Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>> Summary Form: ( DEFLABEL R ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) R ACL2 !>> Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !s>>> F1 ACL2 !s>>> F2 ACL2 !s>>>Bye. :EOF ACL2 !>> Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>>>(DEFUN F3 (X) Y) ACL2 Error in ( DEFUN F3 ...): The body of F3 is a free variable occurrence. Summary Form: ( DEFUN F3 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ACL2 Error [Failure] in ( DEFUN F3 ...): See :DOC failure. ******** FAILED ******** ACL2 !>>>Bye. :EOF ACL2 !>> 1 (DEFLABEL R) L 2 (DEFUN F1 (X) ...) L 3:x(DEFUN F2 (X) ...) ACL2 !>>Bye. :EOF ACL2 !>:pbt 0 0 (EXIT-BOOT-STRAP-MODE) 1 (DEFLABEL R) L 2 (DEFUN F1 (X) ...) L 3:x(DEFUN F2 (X) ...) ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun f () ; error (h t t t t t t t t t t t t)) ACL2 Error [Translate] in ( DEFUN F ...): The symbol H (in package "ACL2") has neither a function nor macro definition in ACL2. Please define it. See :DOC near-misses. Note: this error occurred in the context (H T T T T T T ...). (See :DOC set-iprint to be able to see elided values in this message.) Summary Form: ( DEFUN F ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ACL2 Error [Failure] in ( DEFUN F ...): See :DOC failure. ******** FAILED ******** ACL2 !>(set-iprint t) ACL2 Observation in SET-IPRINT: Iprinting has been enabled. ACL2 !>(defun f () ; error (again) (h t t t t t t t t t t t t)) ACL2 Error [Translate] in ( DEFUN F ...): The symbol H (in package "ACL2") has neither a function nor macro definition in ACL2. Please define it. See :DOC near-misses. Note: this error occurred in the context (H T T T T T T . #@1#). Summary Form: ( DEFUN F ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) ACL2 Error [Failure] in ( DEFUN F ...): See :DOC failure. ******** FAILED ******** ACL2 !>'(H T T T T T T . #@1#) (H T T T T T T T T T T T T) ACL2 !>(set-evisc-tuple ; from :DOC (evisc-tuple 3 ; print-level 4 ; print-length nil ; alist nil ; hiding-cars ) :iprint :same ; better yet, T :sites :all) (:TERM :LD :TRACE :ABBREV . #@2#) ACL2 !>'(H T T T T T T . #@1#) (H T T T . #@3#) ACL2 !>(without-evisc '(H T T T T T T . #@1#)) (H T T T T T T T T T T T T) ACL2 !>(without-evisc '(H T T T T . #@3#)) (H T T T T T T T T T T T T T) ACL2 !>'(H T T T . #@3#) (H T T T . #@4#) ACL2 !>(without-evisc '(H T T T . #@3#)) (H T T T T T T T T T T T T) ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(set-raw-proof-format t) ACL2 !>(set-gag-mode nil) ACL2 !>(thm (equal (append (append x y) z) (append x y z))) Name the formula above *1. Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. Subsumption reduces that number to two. However, one of these is flawed and so we are left with one viable candidate. We will induct according to a scheme suggested by (APPEND X Y), while accommodating (APPEND X Y Z). These suggestions were produced using the :induction rule BINARY-APPEND. If we let (:P X Y Z) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ENDP X)) (:P (CDR X) Y Z)) (:P X Y Z)) (IMPLIES (ENDP X) (:P X Y Z))). 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 two nontautological subgoals. Subgoal *1/2 (IMPLIES (AND (NOT (ENDP X)) (EQUAL (APPEND (APPEND (CDR X) Y) Z) (APPEND (CDR X) Y Z))) (EQUAL (APPEND (APPEND X Y) Z) (APPEND X Y Z))). Preprocess reduces the conjecture to the following, by the list of runes, ((:DEFINITION ENDP)). Subgoal *1/2' (IMPLIES (AND (CONSP X) (EQUAL (APPEND (APPEND (CDR X) Y) Z) (APPEND (CDR X) Y Z))) (EQUAL (APPEND (APPEND X Y) Z) (APPEND X Y Z))). But simplification reduces this to T, using primitive type reasoning and the list of runes, ((:DEFINITION BINARY-APPEND) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)). Subgoal *1/1 (IMPLIES (ENDP X) (EQUAL (APPEND (APPEND X Y) Z) (APPEND X Y Z))). Preprocess reduces the conjecture to the following, by the list of runes, ((:DEFINITION ENDP)). Subgoal *1/1' (IMPLIES (NOT (CONSP X)) (EQUAL (APPEND (APPEND X Y) Z) (APPEND X Y Z))). But simplification reduces this to T, using primitive type reasoning and the list of runes, ((:DEFINITION BINARY-APPEND)). That completes the proof of *1. Q.E.D. Summary Form: ( THM ...) Rules: ((:DEFINITION BINARY-APPEND) (:DEFINITION ENDP) (:DEFINITION NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION BINARY-APPEND) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 435 Proof succeeded. ACL2 !>(set-raw-proof-format :clause) ACL2 !>(thm (equal (append (append x y) z) (append x y z))) Name the formula above *1. Perhaps we can prove *1 by induction. Three induction schemes are suggested by this conjecture. Subsumption reduces that number to two. However, one of these is flawed and so we are left with one viable candidate. We will induct according to a scheme suggested by (APPEND X Y), while accommodating (APPEND X Y Z). These suggestions were produced using the :induction rule BINARY-APPEND. If we let (:P X Y Z) denote *1 above then the induction scheme we'll use is (AND (IMPLIES (AND (NOT (ENDP X)) (:P (CDR X) Y Z)) (:P X Y Z)) (IMPLIES (ENDP X) (:P X Y Z))). 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 two nontautological subgoals. Subgoal *1/2 ((ENDP X) (NOT (EQUAL (BINARY-APPEND (BINARY-APPEND (CDR X) Y) Z) (BINARY-APPEND (CDR X) (BINARY-APPEND Y Z)))) (EQUAL (BINARY-APPEND (BINARY-APPEND X Y) Z) (BINARY-APPEND X (BINARY-APPEND Y Z)))). Preprocess reduces the conjecture to the following, by the list of runes, ((:DEFINITION ENDP)). Subgoal *1/2' ((NOT (CONSP X)) (NOT (EQUAL (BINARY-APPEND (BINARY-APPEND (CDR X) Y) Z) (BINARY-APPEND (CDR X) (BINARY-APPEND Y Z)))) (EQUAL (BINARY-APPEND (BINARY-APPEND X Y) Z) (BINARY-APPEND X (BINARY-APPEND Y Z)))). But simplification reduces this to T, using primitive type reasoning and the list of runes, ((:DEFINITION BINARY-APPEND) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)). Subgoal *1/1 ((NOT (ENDP X)) (EQUAL (BINARY-APPEND (BINARY-APPEND X Y) Z) (BINARY-APPEND X (BINARY-APPEND Y Z)))). Preprocess reduces the conjecture to the following, by the list of runes, ((:DEFINITION ENDP)). Subgoal *1/1' ((CONSP X) (EQUAL (BINARY-APPEND (BINARY-APPEND X Y) Z) (BINARY-APPEND X (BINARY-APPEND Y Z)))). But simplification reduces this to T, using primitive type reasoning and the list of runes, ((:DEFINITION BINARY-APPEND)). That completes the proof of *1. Q.E.D. Summary Form: ( THM ...) Rules: ((:DEFINITION BINARY-APPEND) (:DEFINITION ENDP) (:DEFINITION NOT) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION BINARY-APPEND) (:REWRITE CAR-CONS) (:REWRITE CDR-CONS)) Time: 0.01 seconds (prove: 0.00, print: 0.00, other: 0.00) Prover steps counted: 435 Proof succeeded. ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>(include-book "std/util/define" :dir :system) Summary Form: ( INCLUDE-BOOK "std/util/define" ...) Rules: NIL Time: 0.14 seconds (prove: 0.00, print: 0.00, other: 0.14) "/Users/kaufmann/acl2/acl2/books/std/util/define.lisp" ACL2 !>:trans1 (define f (x) (cons x x)) ; Probably not very helpful (WITH-OUTPUT :STACK :PUSH :OFF (:OTHER-THAN ERROR) (MAKE-EVENT (STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE)))) ACL2 !>:trans (define f (x) (cons x x)) ; DEFINITELY not very helpful (IF (EQ (LD-SKIP-PROOFSP STATE) 'INCLUDE-BOOK) (MAKE-EVENT-FN '(STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE)) 'NIL 'NIL 'NIL 'NIL '(MAKE-EVENT (STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE))) STATE) ((LAMBDA (STATE-GLOBAL-LET*-CLEANUP-LST STATE) ((LAMBDA (MV STATE-GLOBAL-LET*-CLEANUP-LST) ((LAMBDA (ACL2-UNWIND-PROTECT-ERP ACL2-UNWIND-PROTECT-VAL STATE STATE-GLOBAL-LET*-CLEANUP-LST) ((LAMBDA (STATE ACL2-UNWIND-PROTECT-VAL ACL2-UNWIND-PROTECT-ERP) (CONS ACL2-UNWIND-PROTECT-ERP (CONS ACL2-UNWIND-PROTECT-VAL (CONS STATE 'NIL)))) ((LAMBDA (STATE STATE-GLOBAL-LET*-CLEANUP-LST) ((LAMBDA (STATE) STATE) (PUT-GLOBAL 'INHIBIT-OUTPUT-LST-STACK (CAR (NTH '1 STATE-GLOBAL-LET*-CLEANUP-LST)) STATE))) (SET-INHIBIT-OUTPUT-LST-STATE (CAR (NTH '0 STATE-GLOBAL-LET*-CLEANUP-LST)) STATE) STATE-GLOBAL-LET*-CLEANUP-LST) ACL2-UNWIND-PROTECT-VAL ACL2-UNWIND-PROTECT-ERP)) (MV-NTH '0 MV) (MV-NTH '1 MV) (MV-NTH '2 MV) STATE-GLOBAL-LET*-CLEANUP-LST)) ((LAMBDA (MV) ((LAMBDA (ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-VAL STATE) (IF ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP (CONS ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP (CONS ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-VAL (CONS STATE 'NIL))) ((LAMBDA (MV) ((LAMBDA (ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-VAL STATE) (IF ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP (CONS ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-ERP (CONS ER-PROGN-NOT-TO-BE-USED-ELSEWHERE-VAL (CONS STATE 'NIL))) (MAKE-EVENT-FN '(STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE)) 'NIL 'NIL 'NIL 'NIL '(MAKE-EVENT (STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE))) STATE))) (MV-NTH '0 MV) (MV-NTH '1 MV) (MV-NTH '2 MV))) (SET-INHIBIT-OUTPUT-LST-FN ((LAMBDA (X0 X1) (RETURN-LAST 'MBE1-RAW (UNION-EQ-EXEC X0 X1) ((LAMBDA (L1 L2) (RETURN-LAST 'PROGN (UNION-EQ-EXEC$GUARD-CHECK L1 L2) (UNION-EQUAL L1 L2))) X0 X1))) '(PROOF-TREE WARNING! WARNING OBSERVATION PROVE EVENT SUMMARY PROOF-BUILDER COMMENT HISTORY) ((LAMBDA (L1 L2) (RETURN-LAST 'MBE1-RAW (SET-DIFFERENCE-EQ-EXEC L1 L2) (RETURN-LAST 'PROGN (SET-DIFFERENCE-EQ-EXEC$GUARD-CHECK L1 L2) (SET-DIFFERENCE-EQUAL L1 L2)))) (GET-GLOBAL 'INHIBIT-OUTPUT-LST STATE) 'NIL)) STATE)))) (MV-NTH '0 MV) (MV-NTH '1 MV) (MV-NTH '2 MV))) ((LAMBDA (STATE) (CONS 'NIL (CONS 'NIL (CONS STATE 'NIL)))) (PUSH-INHIBIT-OUTPUT-LST-STACK STATE))) STATE-GLOBAL-LET*-CLEANUP-LST)) (CONS (CONS (GET-GLOBAL 'INHIBIT-OUTPUT-LST STATE) 'NIL) (CONS (CONS (GET-GLOBAL 'INHIBIT-OUTPUT-LST-STACK STATE) 'NIL) 'NIL)) STATE)) => (MV * * STATE) ACL2 !>:trans* t (define f (x) (cons x x)) ; Shows the generated defun, etc. Iteration 1 produces (by expansion): (WITH-OUTPUT :STACK :PUSH :OFF (:OTHER-THAN ERROR) (MAKE-EVENT (STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE)))) ---------- Iteration 2 is dropping the WITH-OUTPUT wrapper: (MAKE-EVENT (STD::DEFINE-FN 'F '((X) (CONS X X)) (W STATE))) ---------- Iteration 3 produces (by make-event expansion): (PROGN (DEFSECTION F (WITH-OUTPUT :STACK :POP (DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X)))) (TABLE DEFINE 'STD::GUTS-ALIST (CONS '(F (STD::NAME . F) (STD::NAME-FN . F) (STD::KWD-ALIST) (STD::RETURNSPECS) (STD::T-PROOF) (STD::MAIN-DEF DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X))) (STD::MACRO) (STD::RAW-FORMALS X) (STD::FORMALS (:FORMAL (STD::NAME . X) (GUARD . T) (DOC . "") (STD::OPTS))) (STD::REST-EVENTS) (STD::PE-ENTRY DEFINE F (X) (CONS X X)) (STD::GUARDS-AFTER-RETURNS)) (STD::GET-DEFINE-GUTS-ALIST WORLD))) (STD::SET-DEFINE-CURRENT-FUNCTION F) (LOCAL (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (ENABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) (MAKE-EVENT (LET* ((WORLD (W STATE)) (STD::EVENTS (STD::RETURNSPEC-THMS 'F 'F 'NIL WORLD))) (VALUE (IF STD::EVENTS (CONS 'WITH-OUTPUT (CONS ':STACK (CONS ':POP (CONS (CONS 'PROGN STD::EVENTS) 'NIL)))) '(VALUE-TRIPLE :INVISIBLE))))) (EXTEND-PE-TABLE F (DEFINE F (X) (CONS X X))) (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (DISABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) (MAKE-EVENT (B* ((STD::CURRENT-PKG (F-GET-GLOBAL 'CURRENT-PACKAGE STATE)) (STD::BASE-PKG (PKG-WITNESS STD::CURRENT-PKG)) (STD::NAME 'F) (STD::ALL-TOPICS (XDOC::GET-XDOC-TABLE (W STATE))) (STD::OLD-TOPIC (XDOC::FIND-TOPIC STD::NAME STD::ALL-TOPICS)) ((UNLESS STD::OLD-TOPIC) (VALUE '(VALUE-TRIPLE :INVISIBLE))) ((MV STD::STR STATE) (STD::MAKE-XDOC-TOP STD::NAME 'F '((:FORMAL (STD::NAME . X) (GUARD . T) (DOC . "") (STD::OPTS))) 'NIL STD::BASE-PKG STATE)) (EVENT (LIST 'XDOC::XDOC-PREPEND STD::NAME STD::STR))) (VALUE EVENT))) (MAKE-EVENT (LIST 'VALUE-TRIPLE (IF (EQL 12009 (MAX-ABSOLUTE-EVENT-NUMBER (W STATE))) :REDUNDANT ''F)))) ---------- ACL2 !>"Now use :trans* on the resulting defsection call (pasted in)." "Now use :trans* on the resulting defsection call (pasted in)." ACL2 !>:trans* t (DEFSECTION F (WITH-OUTPUT :STACK :POP (DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X)))) (TABLE DEFINE 'STD::GUTS-ALIST (CONS '(F (STD::NAME . F) (STD::NAME-FN . F) (STD::KWD-ALIST) (STD::RETURNSPECS) (STD::T-PROOF) (STD::MAIN-DEF DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X))) (STD::MACRO) (STD::RAW-FORMALS X) (STD::FORMALS (:FORMAL (STD::NAME . X) (GUARD . T) (DOC . "") (STD::OPTS))) (STD::REST-EVENTS) (STD::PE-ENTRY DEFINE F (X) (CONS X X)) (STD::GUARDS-AFTER-RETURNS)) (STD::GET-DEFINE-GUTS-ALIST WORLD))) (STD::SET-DEFINE-CURRENT-FUNCTION F) (LOCAL (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (ENABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) (MAKE-EVENT (LET* ((WORLD (W STATE)) (STD::EVENTS (STD::RETURNSPEC-THMS 'F 'F 'NIL WORLD))) (VALUE (IF STD::EVENTS (CONS 'WITH-OUTPUT (CONS ':STACK (CONS ':POP (CONS (CONS 'PROGN STD::EVENTS) 'NIL)))) '(VALUE-TRIPLE :INVISIBLE))))) (EXTEND-PE-TABLE F (DEFINE F (X) (CONS X X))) (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (DISABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) Iteration 1 produces (by expansion): (WITH-OUTPUT :STACK :PUSH :OFF :ALL (PROGN (WITH-OUTPUT :STACK :POP (ENCAPSULATE NIL (WITH-OUTPUT :STACK :POP (DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X)))) (TABLE DEFINE 'STD::GUTS-ALIST (CONS '(F (STD::NAME . F) (STD::NAME-FN . F) (STD::KWD-ALIST) (STD::RETURNSPECS) (STD::T-PROOF) (STD::MAIN-DEF DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X))) (STD::MACRO) (STD::RAW-FORMALS X) (STD::FORMALS (:FORMAL (STD::NAME . X) (GUARD . T) (DOC . "") (STD::OPTS))) (STD::REST-EVENTS) (STD::PE-ENTRY DEFINE F (X) (CONS X X)) (STD::GUARDS-AFTER-RETURNS)) (STD::GET-DEFINE-GUTS-ALIST WORLD))) (STD::SET-DEFINE-CURRENT-FUNCTION F) (LOCAL (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (ENABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) (MAKE-EVENT (LET* ((WORLD (W STATE)) (STD::EVENTS (STD::RETURNSPEC-THMS 'F 'F 'NIL WORLD))) (VALUE (IF STD::EVENTS (CONS 'WITH-OUTPUT (CONS ':STACK (CONS ':POP (CONS (CONS 'PROGN STD::EVENTS) 'NIL)))) '(VALUE-TRIPLE :INVISIBLE))))) (EXTEND-PE-TABLE F (DEFINE F (X) (CONS X X))) (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (DISABLE F)) '(VALUE-TRIPLE :INVISIBLE))))))) ---------- Iteration 2 is dropping the WITH-OUTPUT wrapper: (PROGN (WITH-OUTPUT :STACK :POP (ENCAPSULATE NIL (WITH-OUTPUT :STACK :POP (DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X)))) (TABLE DEFINE 'STD::GUTS-ALIST (CONS '(F (STD::NAME . F) (STD::NAME-FN . F) (STD::KWD-ALIST) (STD::RETURNSPECS) (STD::T-PROOF) (STD::MAIN-DEF DEFUN F (X) (DECLARE (XARGS :GUARD T)) (LET ((__FUNCTION__ 'F)) (DECLARE (IGNORABLE __FUNCTION__)) (CONS X X))) (STD::MACRO) (STD::RAW-FORMALS X) (STD::FORMALS (:FORMAL (STD::NAME . X) (GUARD . T) (DOC . "") (STD::OPTS))) (STD::REST-EVENTS) (STD::PE-ENTRY DEFINE F (X) (CONS X X)) (STD::GUARDS-AFTER-RETURNS)) (STD::GET-DEFINE-GUTS-ALIST WORLD))) (STD::SET-DEFINE-CURRENT-FUNCTION F) (LOCAL (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (ENABLE F)) '(VALUE-TRIPLE :INVISIBLE)))) (MAKE-EVENT (LET* ((WORLD (W STATE)) (STD::EVENTS (STD::RETURNSPEC-THMS 'F 'F 'NIL WORLD))) (VALUE (IF STD::EVENTS (CONS 'WITH-OUTPUT (CONS ':STACK (CONS ':POP (CONS (CONS 'PROGN STD::EVENTS) 'NIL)))) '(VALUE-TRIPLE :INVISIBLE))))) (EXTEND-PE-TABLE F (DEFINE F (X) (CONS X X))) (MAKE-EVENT (IF (STD::LOGIC-MODE-P 'F (W STATE)) '(IN-THEORY (DISABLE F)) '(VALUE-TRIPLE :INVISIBLE)))))) ---------- ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(walkabout (w state) state) Commands: 1, 2, ..., up, nx, bk, pp, (pp n), (pp lev len), =, (= symb), (cmds c1 c2 ... cn), and q. ((COMMAND-LANDMARK GLOBAL-VALUE 8732 ...) (EVENT-LANDMARK GLOBAL-VALUE 11172 ...) (CURRENT-THEORY GLOBAL-VALUE # ...) ...) :1 (COMMAND-LANDMARK GLOBAL-VALUE 8732 ...) :pp (COMMAND-LANDMARK GLOBAL-VALUE 8732 (:LOGIC EXIT-BOOT-STRAP-MODE) NIL) :nx (EVENT-LANDMARK GLOBAL-VALUE 11172 ...) :pp (EVENT-LANDMARK GLOBAL-VALUE 11172 ((EXIT-BOOT-STRAP-MODE) 0) EXIT-BOOT-STRAP-MODE) :1 EVENT-LANDMARK :0 (EVENT-LANDMARK GLOBAL-VALUE 11172 ...) :0 ((COMMAND-LANDMARK GLOBAL-VALUE 8732 ...) (EVENT-LANDMARK GLOBAL-VALUE 11172 ...) (CURRENT-THEORY GLOBAL-VALUE # ...) ...) :q ACL2 !>"Now walk about the world...." "Now walk about the world...." ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(defun f1 (x) (car x)) Since F1 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F1. Summary Form: ( DEFUN F1 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F1 ACL2 !>(defun f2 (x) (f1 x)) Since F2 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F2. Summary Form: ( DEFUN F2 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F2 ACL2 !>(defun f3 (x) (f2 x)) Since F3 is non-recursive, its admission is trivial. We could deduce no constraints on the type of F3. Summary Form: ( DEFUN F3 ...) Rules: NIL Time: 0.00 seconds (prove: 0.00, print: 0.00, other: 0.00) F3 ACL2 !>(f3 7) ACL2 Error [Evaluation] in TOP-LEVEL: The guard for the function call (CAR X), which is (OR (CONSP X) (EQUAL X NIL)), is violated by the arguments in the call (CAR 7). See :DOC set-guard-checking for information about suppressing this check with (set-guard-checking :none), as recommended for new users. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. ACL2 !>(wet (f3 7)) TTAG NOTE: Adding ttag :TRACE! from the top level loop. ACL2 Error [Evaluation] in WET: The guard for the function call (CAR X), which is (OR (CONSP X) (EQUAL X NIL)), is violated by the arguments in the call (CAR 7). See :DOC set-guard-checking for information about suppressing this check with (set-guard-checking :none), as recommended for new users. To debug see :DOC print-gv, see :DOC trace, and see :DOC wet. Backtrace stack: ---------------- 1. (ACL2_*1*_ACL2::F1 7) 2. (ACL2_*1*_ACL2::F2 7) 3. (ACL2_*1*_ACL2::F3 7) ACL2 !>"[END OF DEMO]" "[END OF DEMO]" ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$ acl2 Welcome to Clozure Common Lisp Version 1.14 darwinarm64! ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + ACL2 Version 8.7+ (a development snapshot based on ACL2 Version 8.7) + + built November 14, 2026 21:12:31. + + (Git commit hash: dbc6c8be3ec651f6f0162d21158f6e13766ffcc4) + + Copyright (C) 2026, Regents of the University of Texas. + + ACL2 comes with ABSOLUTELY NO WARRANTY. This is free software and + + you are welcome to redistribute it under certain conditions. For + + details, see the LICENSE file distributed with ACL2. + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project-dir-alist: ((:SYSTEM . "/Users/kaufmann/acl2/acl2/books/")). Type :help for help. Type (quit) to quit completely out of ACL2. ACL2 !>(with-brr-data (thm (equal (append x y) (append y x)))) *1 (the initial Goal, a key checkpoint) is pushed for proof by induction. Perhaps we can prove *1 by induction. Two induction schemes are suggested by this conjecture. We will choose arbitrarily among these. We will induct according to a scheme suggested by (APPEND X Y). This suggestion was produced using the :induction rule BINARY-APPEND. 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 two nontautological subgoals. Subgoal *1/2 Subgoal *1/2' Subgoal *1/2'' Subgoal *1/2''' Subgoal *1/2'4' Subgoal *1/2'5' ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/2'' (IMPLIES (AND (CONSP X) (EQUAL (APPEND (CDR X) Y) (APPEND Y (CDR X)))) (EQUAL (CONS (CAR X) (APPEND Y (CDR X))) (APPEND Y X))) *1.1 (Subgoal *1/2'5') is pushed for proof by induction. ]) Subgoal *1/1 Subgoal *1/1' Subgoal *1/1'' ([ A key checkpoint while proving *1 (descended from Goal): Subgoal *1/1'' (IMPLIES (NOT (CONSP X)) (EQUAL Y (APPEND Y X))) *1.2 (Subgoal *1/1'') is pushed for proof by induction. ]) So we now return to *1.2, which is (IMPLIES (NOT (CONSP X)) (EQUAL Y (APPEND Y X))). Subgoal *1.2/2 Subgoal *1.2/2' Subgoal *1.2/1 Subgoal *1.2/1' Subgoal *1.2/1'' Subgoal *1.2/1''' A goal of NIL, Subgoal *1.2/1''', has been generated! Obviously, the proof attempt has failed. Summary Form: ( THM ...) Rules: ((:DEFINITION BINARY-APPEND) (:DEFINITION ENDP) (:DEFINITION NOT) (:ELIM CAR-CDR-ELIM) (:FAKE-RUNE-FOR-TYPE-SET NIL) (:INDUCTION BINARY-APPEND) (:REWRITE CONS-CAR-CDR)) Time: 0.01 seconds (prove: 0.01, print: 0.00, other: 0.00) Prover steps counted: 1044 --- The key checkpoint goals, below, may help you to debug this failure. See :DOC failure and see :DOC set-checkpoint-summary-limit. --- *** Key checkpoint at the top level: *** Goal (EQUAL (APPEND X Y) (APPEND Y X)) *** Key checkpoints under a top-level induction before generating a goal of NIL (see :DOC nil-goal): *** Subgoal *1/2'' (IMPLIES (AND (CONSP X) (EQUAL (APPEND (CDR X) Y) (APPEND Y (CDR X)))) (EQUAL (CONS (CAR X) (APPEND Y (CDR X))) (APPEND Y X))) Subgoal *1/1'' (IMPLIES (NOT (CONSP X)) (EQUAL Y (APPEND Y X))) ACL2 Error [Failure] in ( THM ...): See :DOC failure. ******** FAILED ******** ACL2 Observation: (LENGTH (@ BRR-DATA-LST)) = 16 ACL2 !>(cw-gstack-for-subterm (append y (cdr x))) 1. Simplifying the clause ((NOT (CONSP X)) (NOT (EQUAL (BINARY-APPEND (CDR X) Y) (BINARY-APPEND Y (CDR X)))) (EQUAL (BINARY-APPEND X Y) (BINARY-APPEND Y X))) 2. Rewriting (to simplify) the atom of the third literal, (EQUAL (BINARY-APPEND X Y) (BINARY-APPEND Y X)), Geneqv: (IFF) 3. Rewriting (to simplify) the first argument, (BINARY-APPEND X Y), 4. Attempting to apply (:DEFINITION BINARY-APPEND) to (BINARY-APPEND X Y) The resulting (translated) term is (CONS (CAR X) (BINARY-APPEND Y (CDR X))). ACL2 !>Bye. ~/Dropbox/talks/tutorial-workshop-2026$