/usr/share/acl2-7.2dfsg/books/misc/defp.lisp is in acl2-books-source 7.2dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | ; Copyright (C) 2013, Regents of the University of Texas
; Written by Matt Kaufmann, August, 2007
; License: A 3-clause BSD license. See the LICENSE file distributed with ACL2.
; Enhancement of defpun to allow more than one tail-recursive call.
; Notes:
; The implementation could likely be made more efficient by using if* instead
; of if and having rewrite rules to resolve if* when the test is known true or
; known false. This approach could avoid explosion during clausification
; following the :use hint.
; Example:
#||
(defstub dest (x) t)
(defstobj st fld)
(defp foo (x st)
(let ((y (foo (dest (car x)) st)))
(if (consp (car x))
y
(if (consp x)
(foo (dest x) st)
(cons x (fld st)))))
:rule-classes nil)
||#
(in-package "ACL2")
(include-book "defpun")
(defun defpun-add-test (test tests-and-stuff-lst)
(declare (xargs
:guard
(and (alistp tests-and-stuff-lst)
(true-list-listp (strip-cars tests-and-stuff-lst)))))
(if (endp tests-and-stuff-lst)
nil
(let ((tests (caar tests-and-stuff-lst))
(call (cdar tests-and-stuff-lst)))
(cons (cons (cons test tests)
call)
(defpun-add-test test (cdr tests-and-stuff-lst))))))
(verify-termination dumb-negate-lit)
(defun defpun-calls-tests-and-args-lst (fn term)
(case-match term
((!fn . args)
(list (cons nil args)))
(('if test tbr fbr)
(let ((tbr-tests-and-args-lst
(defpun-calls-tests-and-args-lst fn tbr))
(fbr-tests-and-args-lst
(defpun-calls-tests-and-args-lst fn fbr)))
(append (defpun-add-test
test
tbr-tests-and-args-lst)
(defpun-add-test
(dumb-negate-lit test)
fbr-tests-and-args-lst))))
(& nil)))
(defun defpun-tests-and-base-lst (fn term)
(case-match term
((!fn . &)
nil)
(('if test tbr fbr)
(let ((tbr-base
(defpun-tests-and-base-lst fn tbr))
(fbr-base
(defpun-tests-and-base-lst fn fbr)))
(append (defpun-add-test
test
tbr-base)
(defpun-add-test
(dumb-negate-lit test)
fbr-base))))
(& (list (cons nil term)))))
(defun map-conjoin (lst)
(declare (xargs :guard (true-list-listp lst)))
(if (endp lst)
nil
(cons (conjoin (car lst))
(map-conjoin (cdr lst)))))
(defun defpun-disjoin-tests (tests-and-args-lst)
(declare (xargs :guard (and (alistp tests-and-args-lst)
(true-list-listp
(strip-cars tests-and-args-lst)))))
(let ((tests-lst (strip-cars tests-and-args-lst)))
(disjoin (map-conjoin tests-lst))))
; (verify-termination quote-listp (declare (xargs :verify-guards t)))
; (verify-termination cons-term1 (declare (xargs :verify-guards t))) ; fails
; (verify-termination cons-term (declare (xargs :verify-guards t)))
(program)
(defun defpun-make-nth-arg (tests-and-args-lst n)
(declare (xargs :guard (and (alistp tests-and-args-lst)
(true-list-listp
(strip-cars tests-and-args-lst)))))
(if (endp (cdr tests-and-args-lst))
(nth n (cdar tests-and-args-lst))
(fcons-term* 'if
(conjoin (caar tests-and-args-lst))
(nth n (cdar tests-and-args-lst))
(defpun-make-nth-arg (cdr tests-and-args-lst) n))))
(defun defpun-make-call (fn tests-and-args-lst n acc)
(if (zp n)
(cons-term fn acc)
(let ((n (1- n)))
(defpun-make-call
fn
tests-and-args-lst
n
(cons (defpun-make-nth-arg tests-and-args-lst n)
acc)))))
(defun defpun-make-base (tests-and-base-lst)
(if (endp (cdr tests-and-base-lst))
(cdar tests-and-base-lst)
(fcons-term* 'if
(conjoin (caar tests-and-base-lst))
(cdar tests-and-base-lst)
(defpun-make-base (cdr tests-and-base-lst)))))
(defmacro defp (g vars body &key (rule-classes ':definition))
`(make-event
(er-progn
(if (function-symbolp ',g (w state))
(value nil)
(defstub ,g ,vars t))
(er-let*
((tbody0 (translate ',body t t nil '(defp . ,g) (w state) state)))
(let* ((tbody (remove-lambdas tbody0))
(tests-and-args-lst
(defpun-calls-tests-and-args-lst ',g tbody))
(call (defpun-make-call ',g tests-and-args-lst ,(length vars)
nil))
(tests-and-base-lst
(defpun-tests-and-base-lst ',g tbody))
(base (defpun-make-base tests-and-base-lst))
(test (defpun-disjoin-tests tests-and-base-lst))
(new-body
; It is tempting to call untranslate on the appropriate IF term. But
; untranslate can produce an AND, OR, or NOT term from an IF.
(list 'if
(untranslate test nil (w state))
(untranslate base nil (w state))
(untranslate call nil (w state)))))
(if (ffnnamep ',g base)
(mv (msg "Unable to process the suggested definition as tail ~
recursive. Possible debug info: A problem call has ~
been collected into the base case:~|~% ~x0"
(untranslate base nil (w state)))
nil
state)
(value
(list
'encapsulate
'((,g ,vars t))
(list 'local (list 'defpun ',g ',vars new-body :rule-classes nil))
(list 'defthm
',(packn-pos (list g "$DEF") g)
(list 'equal
(cons ',g ',vars)
',body)
:hints
'(("Goal"
:in-theory (theory 'minimal-theory)
:use ,(packn-pos (list g "-DEF") g)))
:rule-classes ',rule-classes)))))))))
|