1 ;;; -*- Mode: LISP; Package: (SCREAMER :USE CL :COLON-MODE :EXTERNAL); Base: 10; Syntax: Ansi-common-lisp -*-
3 ;;; LaHaShem HaAretz U'Mloah
6 ;;; A portable efficient implementation of nondeterministic CommonLisp
11 ;;; Jeffrey Mark Siskind (Department of Computer Science, University of Toronto)
12 ;;; David Allen McAllester (MIT Artificial Intelligence Laboratory)
14 ;;; Copyright 1991 Massachusetts Institute of Technology. All rights reserved.
15 ;;; Copyright 1992, 1993 University of Pennsylvania. All rights reserved.
16 ;;; Copyright 1993 University of Toronto. All rights reserved.
18 ;;; Permission is hereby granted, free of charge, to any person obtaining a copy of
19 ;;; this software and associated documentation files (the "Software"), to deal in
20 ;;; the Software without restriction, including without limitation the rights to
21 ;;; use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
22 ;;; the Software, and to permit persons to whom the Software is furnished to do so,
23 ;;; subject to the following conditions:
25 ;;; The above copyright and authorship notice and this permission notice shall be
26 ;;; included in all copies or substantial portions of the Software.
28 ;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
29 ;;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
30 ;;; FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
31 ;;; COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
32 ;;; IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
33 ;;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 ;;; Important notice: In this version of Screamer, if Screamer is already
36 ;;; loaded and you wish to recompile the entire file, the recompilation will
37 ;;; proceed much faster if you first do:
38 ;;; (CLRHASH SCREAMER::*FUNCTION-RECORD-TABLE*)
42 ;;; 2. Should have way of having a stream of values.
43 ;;; 3. Kashket's constraint additions Fall90-158.
44 ;;; 4. Compress trail after repeated LOCAL SETF/SETQ to same variable
45 ;;; 5. LOCAL SETF/SETQ on symbol can use special variable binding stack
46 ;;; instead of unwind-protect.
47 ;;; 6. (F (G (H (EITHER X Y)))) where F, G and H are deterministic can
48 ;;; CPS-CONVERT to (FUNCALL #'(LAMBDA (Z) (F (G (H Z)))) (EITHER X Y)).
49 ;;; 7. Should give warning when it recompiles functions due to changing
50 ;;; determinism status.
51 ;;; 8. =V <V <=V >V and >=V should do congruence/monotone closure.
52 ;;; 9. =V should propagate domains.
54 ;;; 11. Should cache VARIABLE-LOWER-BOUND/VARIABLE-UPPER-BOUND for domain
56 ;;; 12. Faster version of BIND! which doesn't cons.
57 ;;; 13. Get DIAGNOSIS and MONTAGUE to work.
58 ;;; 14. Get GROW-UP and NONLINEAR examples to work.
59 ;;; 15. FUNCALLV and APPLYV need to assert the domains of the variable that
61 ;;; 16. Check that +V, -V, *V, /V, MINV and MAXV work and do the right thing
62 ;;; with type propagation.
63 ;;; 17. Check that PROPAGATE does the right thing with bounds of integers.
64 ;;; 18. MEMBERV and derivatives should support vectors.
65 ;;; 19. Backtracking out of INTEGER-BETWEENV and the like will yield an
66 ;;; unconstrained variable since the constraints are asserted locally.
69 ;;; 1. LOCAL SETF does the wrong thing with GETHASH.
70 ;;; 2. LOCAL (SETF/SETQ X e) will signal an error if X is unbound because it
71 ;;; needs to trail the previous value of X and it has none.
72 ;;; 3. Deterministic/nondeterministic LOCAL SETF/SETQ undone out of order.
73 ;;; 4. Changing determinism status can cause code from a different file to
74 ;;; be included causing wierd behavior.
75 ;;; 5. Will signal an obscure error if FAIL is called in a deterministic
76 ;;; context which is not nested in a choice point.
77 ;;; 6. May loop when expressions contain circular lists.
78 ;;; 7. APPLY-NONDETERMINISTIC conses.
81 ;;; 1. Does not handle SETF methods with multiple values for LOCAL SETF.
82 ;;; 2. If you do a (SETF (SYMBOL-FUNCTION 'FOO) ...) to a nondeterministic
83 ;;; function you will lose when you attempt to evaluate (FOO ...).
84 ;;; 3. If you do a (SETF (SYMBOL-FUNCTION 'FOO) ...) to a deterministic
85 ;;; function when FOO was previously defined as a nondeterministic
86 ;;; function you will lose when you attempt to evaluate (FOO ...).
87 ;;; 4. The function record table will not work if we ever support FLET and
88 ;;; LABELS and in particular, if we ever support FLET and LABELS of
89 ;;; nondeterministic functions.
90 ;;; 5. There is no way to force Screamer into compiling a deterministic
91 ;;; function as a nondeterministic one. A wizard might want to do this to
92 ;;; take advantage of the fact that a LOCAL SETF/SETQ in a nondeterministic
93 ;;; function does not cons up closures.
94 ;;; 6. Doesn't handle most CommonLisp special forms.
102 ;;; MULTIPLE-VALUE-CALL
103 ;;; MULTIPLE-VALUE-PROG1
110 ;;; Probably will never handle:
127 ;;; WITH-ADDED-METHODS
132 ;;; Changed the who calls database code to fix the bug whereby after loading
133 ;;; the definition of a nondeterministic function FOO
134 ;;; (ALL-VALUES (FOO ...)) would not work because FOO would not be recognized
135 ;;; as nondeterministic until at least one DEFUN was expanded. In the process
136 ;;; changed the OLD/NEW-DETERMINISTIC? terminology.
138 ;;; Fixed the bug whereby a function FOO which referenced #'BAR or
139 ;;; #'(LAMBDA (...) ... (BAR ...) ...) would not be recompiled when the
140 ;;; deterministic status of BAR changed. This involved a polarity switch on
141 ;;; NESTED?. This also fixed the bug whereby STATIC-ORDERING and REORDER were
142 ;;; incorrectly classified as nondeterministic.
144 ;;; Made SOLUTION walk its argument.
146 ;;; Separated USE-PACKAGE from IN-PACKAGE.
148 ;;; Added *SCREAMER-VERSION*. Set it to 2.1
150 ;;; Added FLIP. Changed EITHER to a macro which expands into FLIP. Expunged
151 ;;; from the code walker, any notion of EITHER being a special form. Removed
152 ;;; the optimization that inline expanded calls to FAIL. Version 2.2.
154 ;;; Fixed bug in VARIABLES-IN. Version 2.3.
156 ;;; Added COUNT-FAILURES. Version 2.4.
158 ;;; Added :SCREAMER to *FEATURES* at the request of CGDEMARC. Version 2.5.
160 ;;; Fixed bug with FUTURE-COMMON-LISP on Symbolics with SETF, FUNCTION and
161 ;;; LAMBDA. Version 2.6.
163 ;;; Fixed INTEGER-BETWEEN to work correctly with noninteger arguments.
164 ;;; Removed SUBST form of Beta-conversion. Version 2.7.
166 ;;; Changed -NOT- to -NOTV- naming convention to be consistent.
167 ;;; Changed INTEGERV to INTEGERPV, REALV to REALPV, NUMBERV to NUMBERPV and
168 ;;; BOOLEANV to BOOLEANPV to be consistent.
169 ;;; Can now walk EVAL-WHEN, FLET, LABELS, PROGV and THE.
170 ;;; Can now CPS convert THE. Also added types to CPS conversion.
171 ;;; Added WHEN-FAILING and rewrote COUNT-FAILURES.
176 ;;; Fixed PROCESS-SUBFORMS to fix bug whereby it didn't correctly walk
177 ;;; EVAL-WHEN, FLET and LABELS.
178 ;;; Fixed DEFUN FUNCTION-NAME to support RETURN-FROM FUNCTION-NAME in its
179 ;;; body for both deterministic and nondeterministic cases.
180 ;;; Fixed PEAL-OFF-DOCUMENTATION-STRING-AND-DECLARATIONS to not consider a
181 ;;; lone string in the body as a documentation string.
184 ;;; Removed redundant "Improper form" error.
185 ;;; Changed all ''NIL and 'NIL to NIL.
186 ;;; Reorganized FORM-TYPEs.
187 ;;; Changed CONSTANT to QUOTE.
188 ;;; Aesthetic capitalization of ALLOW-OTHER-KEYS.
189 ;;; Renamed BLOCK to SEGMENT to be consistent.
190 ;;; Added SELF-EVALUATING? and QUOTIFY and changed processing of QUOTE and
192 ;;; Enforce non-NIL function names.
193 ;;; Added SCREAMER? argument to WALK.
194 ;;; Allow FLET/LABELS to bind SETF functions.
197 ;;; Built new mechanism to determine when to recompile functions due to
198 ;;; changing determinism status to solve a long standing bug.
199 ;;; PERFORM-SUBSTITUTIONS had a call to itself rather than a FUNCALL to
201 ;;; Removed redundant check for NEEDS-SUBSTITUTION? in CPS-CONVERT since that
202 ;;; was checked by PERFORM-SUBSTITUTION anyway.
203 ;;; Made the check performed by NEEDS-SUBSTITUTION? tighter so that fewer
204 ;;; needless macro expansions take place for deterministic DEFUNs.
206 ;;; M6Apr92, T7Apr92, R9Apr92, M13Apr92 Qobi
207 ;;; Changed DEFUN-COMPILE-TIME to compile functions.
208 ;;; Fixed bug in CPS-CONVERT introduced by QUOTE change.
209 ;;; Fixed polarity bug of FUNCTION-LAMBDA in NEEDS-SUBSTITUTION?
210 ;;; Got rid of POSITIVE/NEGATIVE-INFINITY and (OR RATIONAL FLOAT) bogosity.
211 ;;; Changed rules to use (NOT (VARIABLE? X)) instead of prior bogosity.
212 ;;; Fixed fence-post error in trail unwinding.
213 ;;; Added UNWIND-TRAIL.
214 ;;; Added COST-FUNCTION and PREDICATE parameters to REORDER
215 ;;; Fixed bug in DOMAIN-SIZE.
216 ;;; Added RANGE-SIZE.
217 ;;; Moved consistency checks to ends of rules to fix a bug.
218 ;;; Removed unsound type propagation from rules relating to Gaussian integers.
219 ;;; Changed naming conventions: MIN->LOWER-BOUND, MAX->UPPER-BOUND.
220 ;;; Added fuzzy comparisons to bounds restrictions.
221 ;;; Added *MINIMUM-SHRINK-RATIO*.
222 ;;; Moved type consistency checks in ASSERT!-INTEGERPV etc. to beginning.
223 ;;; Removed all fuzziness except for RANGE-SIZE. Fuzzy noninteger-real
224 ;;; variables no longer dereference. REORDER cost function must now return
225 ;;; non-NIL value for a variable to be forced.
226 ;;; Fixed =-RULE to `support' complex numbers.
227 ;;; Fixed CHECK-MEMBERV-RESTRICTION to check for groundness rather than
229 ;;; Fixed RESTRICT-UPPER/LOWER-BOUND! and ASSERT!-INTEGERPV to have integer
230 ;;; bounds for integer variables fixing (INTEGER-BETWEENV 2.1 2.2) problem.
231 ;;; Added RESTRICT-BOUNDS!
232 ;;; Differentiated up versus down rules.
235 ;;; Added NECESSARILY? and FOR-EFFECTS.
236 ;;; Changed MAP-VALUES to accept multiple forms.
237 ;;; Changed PRINT-VALUES and ALL-VALUES to use new version of MAP-VALUES.
238 ;;; Changed all &BODY BODY to &BODY FORMS.
241 ;;; Changed failure strategy for INTEGER-BETWEEN and MEMBER-OF.
242 ;;; Removed (DECLARE (IGNORE FORM)) from NEEDS-SUBSTITUTION?.
243 ;;; Removed MAP-VALUES and changed all callers to use FOR-EFFECTS.
244 ;;; Added AN-INTEGER, INTEGER-ABOVE, INTEGER-BELOW, A-REALV and AN-INTEGERV.
245 ;;; Changed LINEAR-FORCE to no longer require that an integer variable have
247 ;;; Fixed CPS conversion of TAGBODY so that CPS converted code always
248 ;;; evaluates to NIL.
249 ;;; Redid dependency calculations yet again to fix a latent bug.
250 ;;; Removed error messages so that now can RETURN-FROM or GO to deterministic
251 ;;; code from nondeterministic code wrapped in a FOR-EFFECTS but not in a
255 ;;; Fixed a bug in the redone dependency calculations.
258 ;;; Fixed a bug in CHECK-MEMBERV-RESTRICTION that prevented BIND! to a
259 ;;; variable. Wrapped FORMS in PROGN in ALL-VALUES and PRINT-VALUES to fix a
260 ;;; bug introduced by the elimination of MAP-VALUES.
263 ;;; Redid fix for CHECK-MEMBERV-RESTRICTION. Fixed a bug in dependency
264 ;;; calculations so that mutually recursive nondeterministic functions can
265 ;;; become deterministic. Also fixed bug so that macroexpand without compile
266 ;;; doesn't cache definition. Redid PRINT-VARIABLE. Changed NON- to NON.
267 ;;; Fixed bug in EQUALV. Versions of KNOWN?-TRUE-INTERNAL and
268 ;;; KNOWN?-FALSE-INTERNAL without ASSERT!-BOOLEANPV. Type noticers.
269 ;;; Fixed bug in RESTRICT-BOUNDS!. Fixed +V2 -V2 *V2 /V2 MINV2 MAXV2
270 ;;; ASSERT!-=V2 ASSERT!-<=V2 ASSERT!-<V2 ASSERT!-/=V2 to run rule only after
271 ;;; noticers have been attached.
274 ;;; Completely excised all support for domains containing variables.
275 ;;; EQUAL and EQL don't use = so fixed bug that EQUALV and friends mistakingly
276 ;;; used =V for numbers. As a result it is possible for variables to be bound
277 ;;; to numbers, including complex and real numbers. <=V2 and <V2 asserted
278 ;;; theirs arguments to be numbers which sould be real. Completely redesigned
279 ;;; the constraint package. Must walk body of FOR-EFFECTS.
282 ;;; Implemented CGDEMARC's version of AN-INTEGER, AN-INTEGER-ABOVE,
283 ;;; AN-INTEGER-BELOW, AN-INTEGER-BETWEEN, A-MEMBER-OF-VECTOR and
284 ;;; A-MEMBER-OF-LIST. Added IScream-based Y-OR-N-P. Fixed stupid efficiency
285 ;;; bug in ITH-VALUE.
288 ;;; Fixed bug whereby SUPPLIED-P arguments of deterministic surrogate
289 ;;; functions were not ignored. Added VALUE-OF to all primitives. Made
290 ;;; A-MEMBER-OF be one function. Exported *MAXIMUM-DISCRETIZATION-RANGE*.
291 ;;; FIND-BEST now always returns only variables with non-null cost. FIND-BEST
292 ;;; also will not return a corrupted variable, one where a divide-and-conquer
293 ;;; step will not reduce the RANGE-SIZE. REORDER-INTERNAL no longer conses.
294 ;;; DIVIDE-AND-CONQUER-FORCE will stop recursing if a step fails to tighten
295 ;;; the bound it tried to. Added changes from Volker Haarslev to support
296 ;;; MCL 2.0. Changed reference from LISP package to COMMON-LISP. The functions
297 ;;; PRINT-NONDETERMINISTIC-FUNCTION, FAIL, UNWIND-TRAIL, PURGE and
298 ;;; UNWEDGE-SCREAMER are now defined with DEFUN rather than COMMON-LISP:DEFUN.
299 ;;; MCL supports ENVIRONMENT argument to MACRO-FUNCTION. Workaround MCL
300 ;;; MAPHASH bug in CALLERS. Replaced MAPC with DOLIST everywhere.
301 ;;; DEFSTRUCT-COMPILE-TIME VARIABLE. CHECK-LAMBDA-EXPRESSION integrated into
302 ;;; LAMBDA-EXPRESSION?. Fixed bug in CPS-CONVERT-TAGBODY. Added DYNAMIC-EXTENT
306 ;;; Changed RESTRICT-ENUMERATED-DOMAIN! and RESTRICT-ENUMERATED-ANTIDOMAIN! to
307 ;;; call SET-ENUMERATED-DOMAIN! to fix a bug whereby they didn't restrict
308 ;;; upper and lower bounds. Also fixed many bugs in SHARE!. Fixed bug in MINV2
309 ;;; and MAXV2 where they used INFINITY-MIN and INFINITY-MAX incorrectly.
310 ;;; Fixed bug in CORRUPTED? to allow it to work on nonreal variables. Fixed
311 ;;; bug in FIND-BEST so that it dereferences variables. Removed
312 ;;; DEFSTRUCT-COMPILE-TIME VARIABLE since fixed the real bug which was that
313 ;;; GET-SETF-METHOD needed to take the ENVIRONMENT as its argument. Changed
314 ;;; preamble to conform to new style. Changed many calls to LOOP to TAGBODY
315 ;;; since MCL 2.0 macroexpands LOOP into MACROLET which WALK can't handle.
316 ;;; Changed some WHENs to IFs. GET-SETF-METHOD now takes ENVIRONMENT argument.
317 ;;; Removed extra space in PRINT-VALUES Y-OR-N-P. The functions
318 ;;; PRINT-NONDETERMINISTIC-FUNCTION, FAIL, UNWIND-TRAIL, PURGE and
319 ;;; UNWEDGE-SCREAMER are again defined with COMMON-LISP:DEFUN rather than
320 ;;; DEFUN. Modifications to RESTRICT-LOWER-BOUND!, RESTRICT-UPPER-BOUND! and
321 ;;; RESTRICT-BOUNDS! which improves efficiency slightly. Changed calls to
322 ;;; SEQUENCEP to TYPEP SEQUENCE. I don't know why CLtL2 doesn't have
323 ;;; SEQUENCEP while Lucid does. Lifted generators now take optional NAME
324 ;;; argument like MAKE-VARIABLE. Changed = 0, < 0 and > 0 to ZEROP, MINUSP
325 ;;; and PLUSP. Changed INT-CHAR to CODE-CHAR. Changed /-RULE to not divide by
326 ;;; zero. Also *-RULE-UP/DOWN now just FAIL on divide by zero.
329 ;;; Changed references to COMMON-LISP and COMMON-LISP-USER to CL and CL-USER.
330 ;;; Added DEFINE-SCREAMER-PACKAGE and modified definition of SCREAMER-USER to
331 ;;; use it. All calls to GET-SETF-METHOD and MACRO-FUNCTION now pass
332 ;;; ENVIRONMENT since GENERA 8.1, Lucid 4.0.2 and MCL 2.0 all support this
333 ;;; argument. Added Kludge to support Lucid 4.0.2 without CLIM 1.1 loaded.
334 ;;; Added compile-time switch option whereby variables can be represented
335 ;;; either using DEFSTRUCT or using DEFCLASS. Changed FUTURE-COMMON-LISP to
336 ;;; LISP since now using Ansi-common-lisp syntax for Symbolics.
339 ;;; Implemented the missing cases of BCP from ANDV and ORV. Changed
340 ;;; VALUE-OF as per suggestions of Volker Haarslev. Removed check whether
341 ;;; *QUERY-IO* was same as *TERMINAL-IO* from Y-OR-N-P since *QUERY-IO* is
342 ;;; usually a synonym stream and Lucid doesn't implement
343 ;;; SYNONYM-STREAM-SYMBOL and even if it did, there would be no way to
344 ;;; determine whether or not a steam is a a synonym stream.
347 ;;; ATTACH-NOTICER! now runs it. Load extended LOOP macro for MCL since
348 ;;; regular MCL LOOP expands into a MACROLET which WALK can't handle.
349 ;;; Undid change which turned LOOP into TAGBODY. Don't trail unnested LOCAL
350 ;;; SETF and LOCAL-OUTPUT. Special case BOOLEANS. Fixed bug whereby ANDV
351 ;;; didn't return NIL when one argument was known to be NIL and ORV didn't
352 ;;; return T when one argument was known to be T. Added ASSERT!-ORV and
353 ;;; ASSERT!-NOTV-ANDV optimizations. Fixed a really obscure bug in
354 ;;; PERFORM-SUBSTITUTIONS where it didn't perform substitutions on a
358 ;;; Fixed bug in DETERMINE-WHETHER-CALLERS-ARE-DETERMINISTIC. Fixed the fix
359 ;;; to the obscure bug in PERFORM-SUBSTITUTIONS. Changed the call to
360 ;;; CPS-CONVERT inside CPS-CONVERT-RETURN-FROM to pass (FOURTH TAG) as VALUE?
361 ;;; to fix an obscure bug due to John Eric Fosler.
364 ;;; More efficient ANDV, ORV, ASSERT!-NOTV-ANDV and ASSERT!-ORV. Added
365 ;;; COUNT-TRUES and COUNT-TRUESV. Fixed bug in TRANSFORM-ASSERT!. Added
366 ;;; INTERNAL versions of ANDV, ORV, ASSERT!-NOTV-ANDV, ASSERT!-ORV,
367 ;;; COUNT-TRUES and COUNT-TRUESV. Fixed bug in FUNCALLV and APPLYV. Fixed
368 ;;; efficiency bug in CPS-CONVERT-CALL. Fixed bug in RESTRICT-INTEGER!.
370 ;;; T22Dec92--R25Feb93 Qobi
371 ;;; Exported REAL, REALP, BOOLEAN and BOOLEANP. Added support for partial
372 ;;; evaluator. T is now SELF-EVALUATING. Fixed bug in NEEDS-SUBSTITUTION?
373 ;;; so that NESTED? is T. Fixed CACHE-DEFINITION. Added #||# to IN-PACKAGE.
374 ;;; Added EVAL-WHEN to REQUIRE :LOOP for MCL. Fixed bug in RESTRICT-VALUE!.
377 ;;; Changed meaning of POLARITY? in KNOWN?-CONSTRAINT, PROPAGATE, and
378 ;;; ASSERT!-CONSTRAINT so that non-NIL result of FUNCALLV or APPLYV is
379 ;;; considered to satisfy constraint.
381 ;;; S9May93--S11Jul93 Qobi
382 ;;; Added initial values for LAMBDA-LIST, BODY, ENVIRONMENT, CALLEES, and
383 ;;; OLD-DETERMINISTIC? of FUNCTION-RECORD to allow to run under Genera 8.1.1.
384 ;;; Changed WALK of IF to support Genera 8.3. Conditionalized
385 ;;; SPECIAL-OPERATOR-P and GET-SETF-EXPANSION to support both CLtL2 and dpANS.
386 ;;; CACHE-DEFINITION and friends no longer save ENVIRONMENT. Got rid of code
387 ;;; which saved environments in FUNCTION-RECORD in CACHE-ENVIRONMENT and got
388 ;;; rid of COPY-LIST of environments in DEFUN since that was not portable.
389 ;;; Added #-POPLOG ENVIRONMENT to calls to GET-SETF-METHOD and MACRO-FUNCTION.
390 ;;; Added some other conditionalization to support Poplog. Walker
391 ;;; conditionalization for COND now just used for Explorer and not Allegro.
392 ;;; Added wraps around MACRO-FUNCTION to support Allegro. Added support for
393 ;;; nondeterministic functions that return multiple values. Added support for
394 ;;; AKCL. Fixed efficiency bug in ASSERT!-CONSTRAINT. Fixed error messages
395 ;;; for FUNCALLV/APPLYV. FUNCALLV/APPLYV now return ground value when
396 ;;; manifest. Added arc consistency. DEFUN now returns function name.
397 ;;; Completely obliterated all traces of FUNCTION-RECORD-ENVIRONMENT and
398 ;;; commented all cases where current rather than saved environment is used.
399 ;;; Various machinations to get Screamer to run under Harlequin, Allegro, MCL,
400 ;;; and AKCL. Fixed bugs in ASSERT!-MEMBERV-INTERNAL, ASSERT!-MEMBERV,
401 ;;; ASSERT!-NOTV-MEMBERV-INTERNAL, and ASSERT!-NOTV-MEMBERV. FUNCALLV and
402 ;;; APPLYV now propagate to Z when all arguments become bound.
405 ;;; To consolidate version skew on version 3.11.
408 ;;; Fixed bug in -V2 (i.e. (-V2 0 <variable>)) by removing bogus special case.
411 ;;; Since ATTACH-NOTICER! now runs the noticer after attaching it removed the
412 ;;; cases where the noticers were explicitly run by lifted functions.
415 ;;; Iterate no longer exports FINISH under AKCL since it conflicts with PCL.
416 ;;; TERMINATE is a synonym anyway.
418 ;;; T28Sep93-M4Oct93 Qobi
419 ;;; Ported to CMU CommonLisp 17b. This change necesitated converting the
420 ;;; LOOPs in Y-OR-N-P, UNWIND-TRAIL, VALUE-OF, VARIABLIZE, and
421 ;;; CHOICE-POINT-INTERNAL into TAGBODY/GO combintations since CMU CommonLisp
422 ;;; expands LOOP into MACROLET. Changed POSSIBLY-BETA-REDUCE-FUNCALL to again
423 ;;; do SUBST optimization. Changed CPS-CONVERT-BLOCK, CPS-CONVERT-IF,
424 ;;; CPS-CONVERT-TAGBODY, and CPS-CONVERT-CALL to use
425 ;;; POSSIBLY-BETA-REDUCE-FUNCALL to encapsulate the *DYNAMIC-EXTENT?*
426 ;;; interface and fix some efficiency bugs. Even Symbolics port now uses
427 ;;; MAGIC. Set *DYNAMIC-EXTENT?* to NIL for Symbolics. Added patch files for
428 ;;; Lucid bug-5511. *TRAIL* now has an initial size of 4096 and a growth rate
429 ;;; of 1024 so that we don't spend much time growing it on implementations
430 ;;; where that is inefficient.
433 ;;; PERFORM-SUBSTITUTIONS didn't handle FOR-EFFECTS which caused a bug when
434 ;;; a deterministic DEFUN contained a FOR-EFFECTS which had a nested LOCAL
438 ;;; Fixed bug in CPS-CONVERT-RETURN-FROM that surfaced due to the previous
442 ;;; Fixed bug in WHEN-FAILING so that it now nests.
445 ;;; Fixes to make work under Allegro 4.2 and Genera 8.3.
446 ;;; Future work includes integrating the Allegro\PC and CLISP mods,
447 ;;; fixing the conditionalization on the DEFTYPE BOOLEAN, and checking that
448 ;;; the new official DEFTYPE BOOLEAN corresponds to what Screamer expects.
451 (in-package :cl-user
)
453 (defpackage :screamer
454 (:shadow
:defun
:multiple-value-bind
:y-or-n-p
:variable
)
461 :multiple-value-call-nondeterministic
468 :nondeterministic-function?
469 :funcall-nondeterministic
470 :apply-nondeterministic
530 :divide-and-conquer-force
538 :define-screamer-package
542 :*minimum-shrink-ratio
*
543 :*maximum-discretization-range
*
546 (in-package :screamer
)
548 (declaim (declaration magic
))
550 (defmacro define-screamer-package
(defined-package-name &rest options
)
551 `(defpackage ,defined-package-name
553 (:shadowing-import-from
:screamer
:defun
:multiple-value-bind
:y-or-n-p
)
554 (:use
:cl
:screamer
)))
556 (define-screamer-package :screamer-user
)
558 (defmacro defstruct-compile-time
(options &body items
)
559 `(eval-when (:compile-toplevel
:load-toplevel
:execute
)
560 (defstruct ,options
,@items
)))
562 (defmacro defvar-compile-time
(name &optional initial-value documentation
)
563 `(eval-when (:compile-toplevel
:load-toplevel
:execute
)
564 (defvar ,name
,initial-value
,documentation
)))
566 (defmacro defun-compile-time
(function-name lambda-list
&body body
)
567 `(eval-when (:compile-toplevel
:load-toplevel
:execute
)
568 (cl:defun
,function-name
,lambda-list
,@body
)
569 (eval-when (:compile-toplevel
) (compile ',function-name
))))
571 ;;; Needed because Allegro has some bogosity whereby (MACRO-FUNCTION <m> <e>)
572 ;;; returns NIL during compile time when <m> is a macro being defined for the
573 ;;; first time in the file being compiled.
574 (defmacro defmacro-compile-time
(function-name lambda-list
&body body
)
575 `(eval-when (:compile-toplevel
:load-toplevel
:execute
)
576 (defmacro ,function-name
,lambda-list
,@body
)))
578 (defparameter *screamer-version
* "3.20"
579 "The version of Screamer which is loaded.")
581 (defvar-compile-time *dynamic-extent?
* t
582 "T to enable the dynamic extent optimization.")
584 (defvar *iscream?
* nil
585 "T if Screamer is running under ILisp/GNUEmacs with iscream.el loaded.")
587 (defvar *nondeterministic?
* nil
"This must be globally NIL.")
589 (defvar-compile-time *screamer?
* nil
590 "This must be NIL except when defining internal Screamer functions.")
592 (defvar-compile-time *nondeterministic-context?
* nil
593 "This must be globally NIL.")
595 (defvar-compile-time *local?
* nil
"This must be globally NIL.")
597 (defvar-compile-time *block-tags
* '() "This must be globally NIL.")
599 (defvar-compile-time *tagbody-tags
* '() "This must be globally NIL.")
601 (defvar *trail
* (make-array 4096 :adjustable t
:fill-pointer
0) "The trail.")
603 (defvar-compile-time *function-record-table
* (make-hash-table :test
#'equal
)
604 "The function record table.")
606 (defvar-compile-time *ordered-lambda-list-keywords
*
607 '(&optional
&rest
&key
&allow-other-keys
&aux
)
608 "The allowed lambda list keywords in order.")
610 (defmacro-compile-time choice-point-internal
(form)
611 ;; note: Is it really better to use VECTOR-PUSH-EXTEND than CONS for the
614 (let ((*nondeterministic?
* t
))
615 (unwind-protect ,form
619 (if (= (fill-pointer *trail
*) trail-pointer
) (return))
620 (funcall (vector-pop *trail
*))
621 ;; note: This is to allow the trail closures to be garbage
623 (setf (aref *trail
* (fill-pointer *trail
*)) nil
)
626 (defmacro-compile-time choice-point-external
(&rest forms
)
627 ;; note: Is it really better to use VECTOR-PUSH-EXTEND than CONS for the
629 `(let ((trail-pointer (fill-pointer *trail
*))) ,@forms
))
631 (defmacro-compile-time choice-point
(form)
632 `(choice-point-external (choice-point-internal ,form
)))
634 (defstruct-compile-time function-record
640 (old-deterministic? nil
)
641 (screamer?
*screamer?
*))
643 (defstruct-compile-time (nondeterministic-function
644 (:print-function print-nondeterministic-function
)
645 (:predicate nondeterministic-function?-internal
))
648 (defun-compile-time screamer-error
(header &rest args
)
654 "~%There are eight types of nondeterministic contexts: the body of a~%~
655 function defined with DEFUN, the body of a call to the FOR-EFFECTS~%~
656 macro, the first argument of a call to the ONE-VALUE macro, the body of~%~
657 a call to the POSSIBLY? macro, the body of a call to the NECESSARILY?~%~
658 macro, the body of a call to the ALL-VALUES macro, the second argument~%~
659 of a call to the ITH-VALUE macro and the body of a call to the~%~
660 PRINT-VALUES macro. Note that, the default forms of &OPTIONAL and &KEY~%~
661 arguments and the initialization forms of &AUX variables, are always~%~
662 deterministic contexts even though they may appear inside a DEFUN.")
665 (defun-compile-time get-function-record
(function-name)
666 (let ((function-record (gethash function-name
*function-record-table
*)))
667 (unless function-record
668 (setf function-record
(make-function-record :function-name function-name
))
669 (setf (gethash function-name
*function-record-table
*) function-record
))
672 (defun-compile-time peal-off-documentation-string-and-declarations
673 (body &optional documentation-string?
)
674 ;; note: This will need to be done as well for LOCALLY and MACROLET when we
675 ;; eventually implement them.
676 ;; needs work: This requires that the documentation string preceed all
677 ;; declarations which needs to be fixed.
678 (let (documentation-string declarations
)
679 (when (and documentation-string?
681 (not (null (rest body
)))
682 (stringp (first body
)))
683 (setf documentation-string
(first body
))
684 (setf body
(rest body
)))
685 (loop (unless (and (not (null body
))
687 (eq (first (first body
)) 'declare
))
689 (push (first body
) declarations
)
691 (values body
(reverse declarations
) documentation-string
)))
693 (defun-compile-time self-evaluating?
(thing)
694 (and (not (consp thing
))
695 (or (not (symbolp thing
))
698 (eq (symbol-package thing
) (symbol-package :x
)))))
700 (defun-compile-time quotify
(thing)
701 (if (self-evaluating? thing
) thing
`',thing
))
703 (defun-compile-time lambda-expression?
(form)
705 (eq (first form
) 'lambda
)
706 (or (and (null (rest (last form
)))
708 (listp (second form
)))
709 (error "Invalid syntax for LAMBDA expression: ~S" form
))))
711 (defun-compile-time valid-function-name?
(function-name)
712 (or (and (symbolp function-name
) (not (null function-name
)))
713 (and (consp function-name
)
714 (eq (first function-name
) 'setf
)
715 (null (rest (last function-name
)))
716 (= (length function-name
) 2)
717 (symbolp (second function-name
))
718 (not (null (second function-name
))))))
720 (defun-compile-time check-function-name
(function-name)
721 (unless (valid-function-name? function-name
)
722 (error "Invalid function name: ~S" function-name
)))
724 (defun-compile-time every-other
(list)
725 (cond ((null list
) list
)
726 ((null (rest list
)) list
)
727 (t (cons (first list
) (every-other (rest (rest list
)))))))
729 (defun-compile-time check-lambda-list-internal
(lambda-list &optional mode
)
732 ((member (first lambda-list
) *ordered-lambda-list-keywords
* :test
#'eq
)
733 (check-lambda-list-internal (rest lambda-list
) (first lambda-list
)))
734 (t (let ((parameter (first lambda-list
)))
737 (unless (symbolp parameter
)
738 (error "Invalid parameter: ~S" parameter
)))
740 (unless (or (symbolp parameter
)
741 (and (consp parameter
)
742 (null (rest (last parameter
)))
743 (or (= (length parameter
) 1)
744 (= (length parameter
) 2)
745 (and (= (length parameter
) 3)
746 (symbolp (third parameter
))))
747 (symbolp (first parameter
))))
748 (error "Invalid &OPTIONAL parameter: ~S" parameter
)))
750 (unless (symbolp parameter
)
751 (error "Invalid &REST parameter: ~S" parameter
)))
753 (unless (or (symbolp parameter
)
754 (and (consp parameter
)
755 (null (rest (last parameter
)))
756 (or (= (length parameter
) 1)
757 (= (length parameter
) 2)
758 (and (= (length parameter
) 3)
759 (symbolp (third parameter
))))
760 (or (symbolp (first parameter
))
761 (and (consp (first parameter
))
762 (null (rest (last (first parameter
))))
763 (= (length (first parameter
)) 2)
764 (symbolp (first (first parameter
)))
765 (symbolp (second (first parameter
)))))))
766 (error "Invalid &KEY parameter: ~S" parameter
)))
768 (unless (or (symbolp parameter
)
769 (and (consp parameter
)
770 (null (rest (last parameter
)))
771 (or (= (length parameter
) 1)
772 (= (length parameter
) 2))
773 (symbolp (first parameter
))))
774 (error "Invalid &AUX parameter: ~S" parameter
)))))
775 (check-lambda-list-internal (rest lambda-list
) mode
))))
777 (defun-compile-time check-lambda-list
(lambda-list)
778 (unless (null (rest (last lambda-list
)))
779 (error "Improper lambda-list: ~S" lambda-list
))
780 (let ((rest (member '&rest lambda-list
:test
#'eq
)))
782 (let ((rest (rest rest
)))
783 (unless (not (member '&rest rest
:test
#'eq
))
784 (error "&REST cannot appear more than once: ~S" lambda-list
))
785 (unless (and (not (null rest
))
786 (not (member (first rest
) lambda-list-keywords
:test
#'eq
))
787 (or (null (rest rest
))
788 (member (first (rest rest
)) lambda-list-keywords
790 (error "&REST must be followed by exactly one variable: ~S"
792 (let ((allow-other-keys (member '&allow-other-keys lambda-list
:test
#'eq
)))
794 (unless (or (null (rest allow-other-keys
))
795 (member (first (rest allow-other-keys
)) lambda-list-keywords
797 (error "&ALLOW-OTHER-KEYS must not be followed by a parameter: ~S"
800 (remove-if-not #'(lambda (argument)
801 (member argument lambda-list-keywords
:test
#'eq
))
803 (unless (every #'(lambda (keyword)
804 (member keyword
*ordered-lambda-list-keywords
* :test
#'eq
))
806 (error "Invalid lambda list keyword: ~S" lambda-list
))
807 (unless (every #'(lambda (x y
)
808 (member y
(member x
*ordered-lambda-list-keywords
*
813 (error "Invalid order for lambda list keywords: ~S" lambda-list
)))
814 (check-lambda-list-internal lambda-list
))
816 (defun-compile-time walk-lambda-list-reducing
817 (map-function reduce-function screamer? partial? nested? lambda-list
818 environment
&optional mode
)
820 ((null lambda-list
) (funcall reduce-function
))
821 ((member (first lambda-list
) *ordered-lambda-list-keywords
* :test
#'eq
)
822 (walk-lambda-list-reducing map-function
829 (first lambda-list
)))
831 ((nil &rest
&allow-other-keys
&aux
)
832 (walk-lambda-list-reducing map-function
841 (if (and (consp (first lambda-list
))
842 (consp (rest (first lambda-list
))))
845 (walk map-function reduce-function screamer? partial? nested?
846 (second (first lambda-list
)) environment
)
847 (walk-lambda-list-reducing map-function
855 (walk-lambda-list-reducing map-function
864 (defun-compile-time walk-lambda-list
865 (map-function reduce-function screamer? partial? nested? lambda-list
867 (check-lambda-list lambda-list
)
871 (funcall map-function lambda-list
'lambda-list
)
872 (walk-lambda-list-reducing map-function
879 (funcall map-function lambda-list
'lambda-list
)))
881 (defun-compile-time walk-block
882 (map-function reduce-function screamer? partial? nested? form environment
)
883 (unless (null (rest (last form
))) (error "Improper BLOCK: ~S" form
))
884 (unless (>= (length form
) 2)
885 (error "BLOCK must have at least one argument, a NAME: ~S" form
))
886 (unless (symbolp (second form
)) (error "NAME must be a symbol: ~S" form
))
888 (funcall reduce-function
889 (funcall map-function form
'block
)
890 (reduce reduce-function
891 (mapcar #'(lambda (subform)
899 (rest (rest form
)))))
900 (funcall map-function form
'block
)))
902 (defun-compile-time walk-catch
903 (map-function reduce-function screamer? partial? nested? form environment
)
904 (unless (null (rest (last form
))) (error "Improper PROGN: ~S" form
))
905 (unless (>= (length form
) 2)
906 (error "CATCH must have at least one argument, a TAG: ~S" form
))
908 (funcall reduce-function
909 (funcall map-function form
'catch
)
910 (reduce reduce-function
911 (mapcar #'(lambda (subform)
920 (funcall map-function form
'catch
)))
922 (defun-compile-time walk-eval-when
923 (map-function reduce-function screamer? partial? nested? form environment
)
924 (unless (null (rest (last form
))) (error "Improper EVAL-WHEN: ~S" form
))
925 (unless (>= (length form
) 2)
926 (error "EVAL-WHEN must have at least one argument: ~S" form
))
927 (unless (listp (second form
))
928 (error "First argument of EVAL-WHEN must be a list: ~S" form
))
929 (unless (null (rest (last (second form
))))
930 (error "Improper list of SITUATIONS: ~S" form
))
931 (unless (every #'(lambda (situation)
932 (member situation
'(:compile-top-level
940 (error "Invalid SITUATION: ~S" form
))
941 (if (member :execute
(second form
) :test
#'eq
)
942 (walk-progn map-function
947 `(progn ,@(rest (rest form
)))
949 (funcall map-function nil
'quote
)))
951 (defun-compile-time walk-flet
/labels
952 (map-function reduce-function screamer? partial? nested? form environment
954 (unless (null (rest (last form
))) (error "Improper ~S: ~S" form-type form
))
955 (unless (>= (length form
) 2)
956 (error "~S must have BINDINGS: ~S" form-type form
))
957 (unless (and (listp (second form
))
958 (null (rest (last (second form
))))
959 (every #'(lambda (binding)
961 (null (rest (last binding
)))
962 (>= (length binding
) 2)
963 (valid-function-name?
(first binding
))
964 (listp (second binding
))))
966 (error "Invalid BINDINGS for ~S: ~S" form-type form
))
970 (funcall map-function form form-type
)
978 (funcall reduce-function
979 (walk-lambda-list map-function
995 (peal-off-documentation-string-and-declarations
996 (rest (rest binding
)) t
))))
998 (reduce reduce-function
999 (mapcar #'(lambda (subform)
1007 (rest (rest form
)))))
1008 (reduce reduce-function
1009 (mapcar #'(lambda (subform)
1017 (rest (rest form
))))))
1018 (funcall map-function form form-type
)))
1020 (defun-compile-time walk-function
1021 (map-function reduce-function screamer? partial? nested? form environment
)
1022 (unless (null (rest (last form
))) (error "Improper FUNCTION: ~S" form
))
1023 (unless (= (length form
) 2)
1024 (error "FUNCTION must have one argument: ~S" form
))
1025 (cond ((lambda-expression?
(second form
))
1026 (if (and reduce-function nested?
)
1029 (funcall map-function form
'function-lambda
)
1032 (walk-lambda-list map-function
1037 (second (second form
))
1041 (mapcar #'(lambda (subform)
1049 (peal-off-documentation-string-and-declarations
1050 (rest (rest (second form
))) t
)))))
1051 (funcall map-function form
'function-lambda
)))
1052 ((valid-function-name?
(second form
))
1054 ((symbolp (second form
))
1055 (if (or (special-operator-p (second form
))
1056 (macro-function (second form
) environment
))
1057 (error "You can't reference the FUNCTION of a special form or~%~
1060 (funcall map-function form
'function-symbol
)))
1061 (t (funcall map-function form
'function-setf
))))
1062 (t (error "Invalid argument to FUNCTION: ~S" form
))))
1064 (defun-compile-time walk-go
(map-function form
)
1065 (unless (null (rest (last form
))) (error "Improper GO: ~S" form
))
1066 (unless (= (length form
) 2) (error "GO must have one argument: ~S" form
))
1067 (unless (or (symbolp (second form
)) (integerp (second form
)))
1068 (error "TAG of GO must be a symbol or integer: ~S" form
))
1069 (funcall map-function form
'go
))
1071 (defun-compile-time walk-if
1072 (map-function reduce-function screamer? partial? nested? form environment
)
1073 (unless (null (rest (last form
))) (error "Improper IF: ~S" form
))
1074 (unless (or (= (length form
) 3) (= (length form
) 4))
1075 (error "IF must have two or three arguments: ~S" form
))
1077 (if (= (length form
) 4)
1078 (funcall reduce-function
1079 (funcall map-function form
'if
)
1080 (funcall reduce-function
1088 (funcall reduce-function
1103 (funcall reduce-function
1104 (funcall map-function form
'if
)
1105 (funcall reduce-function
1120 (funcall map-function form
'if
)))
1122 (defun-compile-time walk-let
/let
*
1123 (map-function reduce-function screamer? partial? nested? form environment
1125 (unless (null (rest (last form
))) (error "Improper ~S: ~S" form-type form
))
1126 (unless (>= (length form
) 2)
1127 (error "~S must have BINDINGS: ~S" form-type form
))
1128 (unless (and (listp (second form
))
1129 (null (rest (last (second form
))))
1130 (every #'(lambda (binding)
1131 (or (symbolp binding
)
1132 (and (consp binding
)
1133 (null (rest (last binding
)))
1134 (or (= (length binding
) 1)
1135 (= (length binding
) 2))
1136 (symbolp (first binding
)))))
1138 (error "Invalid BINDINGS for ~S: ~S" form-type form
))
1142 (funcall map-function form form-type
)
1143 (funcall reduce-function
1144 (reduce reduce-function
1145 (mapcar #'(lambda (binding)
1155 (and (consp binding
)
1156 (= (length binding
) 2)))
1158 (reduce reduce-function
1159 (mapcar #'(lambda (subform)
1167 (peal-off-documentation-string-and-declarations
1168 (rest (rest form
)))))))
1169 (funcall map-function form form-type
)))
1171 (defun-compile-time walk-multiple-value-call
1172 (map-function reduce-function screamer? partial? nested? form environment
)
1173 (unless (null (rest (last form
)))
1174 (error "Improper MULTIPLE-VALUE-CALL: ~S" form
))
1175 (unless (>= (length form
) 2)
1176 (error "MULTIPLE-VALUE-CALL must have at least one argument, a FUNCTION: ~S"
1179 (funcall reduce-function
1180 (funcall map-function form
'multiple-value-call
)
1181 (reduce reduce-function
1182 (mapcar #'(lambda (subform)
1191 (funcall map-function form
'multiple-value-call
)))
1193 (defun-compile-time walk-multiple-value-prog1
1194 (map-function reduce-function screamer? partial? nested? form environment
)
1195 (unless (null (rest (last form
)))
1196 (error "Improper MULTIPLE-VALUE-PROG1: ~S" form
))
1197 (unless (>= (length form
) 2)
1198 (error "MULTIPLE-VALUE-PROG1 must have at least one argument, a FORM: ~S"
1201 (funcall reduce-function
1202 (funcall map-function form
'multiple-value-prog1
)
1203 (reduce reduce-function
1204 (mapcar #'(lambda (subform)
1213 (funcall map-function form
'multiple-value-prog1
)))
1215 (defun-compile-time walk-progn
1216 (map-function reduce-function screamer? partial? nested? form environment
)
1217 (unless (null (rest (last form
))) (error "Improper PROGN: ~S" form
))
1219 (funcall reduce-function
1220 (funcall map-function form
'progn
)
1221 (reduce reduce-function
1222 (mapcar #'(lambda (subform)
1231 (funcall map-function form
'progn
)))
1233 (defun-compile-time walk-progv
1234 (map-function reduce-function screamer? partial? nested? form environment
)
1235 (unless (null (rest (last form
))) (error "Improper PROGV: ~S" form
))
1236 (unless (>= (length form
) 3)
1237 (error "PROGV must have at least two arguments: ~S" form
))
1239 (funcall reduce-function
1240 (funcall map-function form
'progv
)
1241 (funcall reduce-function
1242 (funcall reduce-function
1257 (reduce reduce-function
1258 (mapcar #'(lambda (subform)
1266 (rest (rest (rest form
)))))))
1267 (funcall map-function form
'progv
)))
1269 (defun-compile-time walk-quote
(map-function form
)
1270 (unless (null (rest (last form
))) (error "Improper QUOTE: ~S" form
))
1271 (unless (= (length form
) 2)
1272 (error "QUOTE must have one argument: ~S" form
))
1273 (funcall map-function
(second form
) 'quote
))
1275 (defun-compile-time walk-return-from
1276 (map-function reduce-function screamer? partial? nested? form environment
)
1277 (unless (null (rest (last form
))) (error "Improper RETURN-FROM: ~S" form
))
1278 (unless (or (= (length form
) 2) (= (length form
) 3))
1279 (error "RETURN-FROM must have one or two arguments,~%~
1280 a NAME and an optional RESULT: ~S" form
))
1281 (unless (symbolp (second form
)) (error "NAME must be a symbol: ~S" form
))
1283 (funcall reduce-function
1284 (funcall map-function form
'return-from
)
1290 (if (= (length form
) 3) (third form
) nil
)
1292 (funcall map-function form
'return-from
)))
1294 (defun-compile-time walk-setq
1295 (map-function reduce-function screamer? partial? nested? form environment
)
1296 (unless (null (rest (last form
))) (error "Improper SETQ: ~S" form
))
1297 (unless (every #'symbolp
(every-other (rest form
)))
1298 (error "Invalid destination for SETQ: ~S" form
))
1299 (unless (evenp (length (rest form
)))
1300 (error "Odd number of arguments to SETQ: ~S" form
))
1302 (funcall reduce-function
1303 (funcall map-function form
'setq
)
1304 (reduce reduce-function
1305 (mapcar #'(lambda (subform)
1313 (every-other (rest (rest form
))))))
1314 (funcall map-function form
'setq
)))
1316 (defun-compile-time walk-tagbody
1317 (map-function reduce-function screamer? partial? nested? form environment
)
1318 (unless (null (rest (last form
))) (error "Improper TAGBODY: ~S" form
))
1319 (unless (every #'(lambda (subform)
1320 (or (symbolp subform
) (integerp subform
) (listp subform
)))
1322 (error "A subforms of a TAGBODY must be symbols, integers or lists: ~S"
1324 (let ((tags (remove-if #'consp
(rest form
))))
1325 (unless (= (length tags
) (length (remove-duplicates tags
)))
1326 (error "TAGBODY has duplicate TAGs: ~S" form
)))
1328 (funcall reduce-function
1329 (funcall map-function form
'tagbody
)
1330 (reduce reduce-function
1331 (mapcar #'(lambda (subform)
1339 (remove-if-not #'consp
(rest form
)))))
1340 (funcall map-function form
'tagbody
)))
1342 (defun-compile-time walk-the
1343 (map-function reduce-function screamer? partial? nested? form environment
)
1344 (unless (null (rest (last form
))) (error "Improper THE: ~S" form
))
1345 (unless (= (length form
) 3) (error "THE must have two arguments: ~S" form
))
1347 (funcall reduce-function
1355 (funcall map-function form
'the
))
1356 (funcall map-function form
'the
)))
1358 (defun-compile-time walk-throw
1359 (map-function reduce-function screamer? partial? nested? form environment
)
1360 (unless (null (rest (last form
))) (error "Improper THROW: ~S" form
))
1361 (unless (= (length form
) 3)
1362 (error "THROW must have two arguments, a TAG and a RESULT: ~S" form
))
1364 (funcall reduce-function
1365 (funcall map-function form
'throw
)
1366 (funcall reduce-function
1381 (funcall map-function form
'throw
)))
1383 (defun-compile-time walk-unwind-protect
1384 (map-function reduce-function screamer? partial? nested? form environment
)
1385 (unless (null (rest (last form
))) (error "Improper UNWIND-PROTECT: ~S" form
))
1386 (unless (>= (length form
) 2)
1387 (error "UNWIND-PROTECT must have at least one argument, a PROTECTED-FORM: ~S"
1392 (funcall map-function form
'unwind-protect
)
1393 (funcall reduce-function
1401 (reduce reduce-function
1402 (mapcar #'(lambda (subform)
1410 (rest (rest form
))))))
1411 (funcall map-function form
'unwind-protect
)))
1413 (defun-compile-time walk-for-effects
1414 (map-function reduce-function screamer? partial? nested? form environment
)
1415 (unless (null (rest (last form
))) (error "Improper FOR-EFFECTS: ~S" form
))
1416 ;; note: We used to think that we should never walk the body of FOR-EFFECTS
1417 ;; as we thought that the walker would get confused on the code
1418 ;; generated by FOR-EFFECTS and that FOR-EFFECTS called
1419 ;; CPS-CONVERT-PROGN on its body and that CPS-CONVERT-PROGN did the
1420 ;; walk for us. But that was wrong since FORM-CALLEES also walks and
1421 ;; thus would miss functions called in the body of a FOR-EFFECTS. So now
1422 ;; we walk the body of a FOR-EFFECTS without macro-expanding it, but
1423 ;; only when NESTED? is true which is essentially only for FORM-CALLEES
1424 ;; since DETERMINISTIC? must not walk the body of FOR-EFFECTS or else
1425 ;; it will mistakingly report that that a FOR-EFFECTS form is
1426 ;; nondeterministic when its body is nondeterministic.
1427 (if (and reduce-function nested?
)
1428 (funcall reduce-function
1429 (funcall map-function form
'for-effects
)
1430 (reduce reduce-function
1431 (mapcar #'(lambda (subform)
1440 (funcall map-function form
'for-effects
)))
1442 (defun-compile-time walk-setf
1443 (map-function reduce-function screamer? partial? nested? form environment
)
1444 (unless (null (rest (last form
))) (error "Improper SETF: ~S" form
))
1445 (unless (evenp (length (rest form
)))
1446 (error "Odd number of arguments to SETF: ~S" form
))
1449 (funcall reduce-function
1450 (funcall map-function form
'local-setf
)
1451 (reduce reduce-function
1452 (mapcar #'(lambda (subform)
1460 (every-other (rest (rest form
))))))
1461 (funcall map-function form
'local-setf
))
1467 (let ((*macroexpand-hook
* #'funcall
))
1468 (macroexpand-1 form environment
))
1471 (defun-compile-time walk-multiple-value-call-nondeterministic
1472 (map-function reduce-function screamer? partial? nested? form environment
)
1473 (unless (null (rest (last form
)))
1474 (error "Improper MULTIPLE-VALUE-CALL-NONDETERMINISTIC: ~S" form
))
1475 (unless (>= (length form
) 2)
1476 (error "MULTIPLE-VALUE-CALL-NONDETERMINISTIC must have at least one ~
1477 argument, a FUNCTION: ~S"
1480 (funcall reduce-function
1481 (funcall map-function form
'multiple-value-call-nondeterministic
)
1482 (reduce reduce-function
1483 (mapcar #'(lambda (subform)
1492 (funcall map-function form
'multiple-value-call-nondeterministic
)))
1494 (defun-compile-time walk-full
(map-function form
)
1495 (unless (null (rest (last form
))) (error "Improper FULL: ~S" form
))
1496 (unless (= (length form
) 2)
1497 (error "FULL must have exactly one argument, a FORM: ~S" form
))
1498 (funcall map-function form
'full
))
1500 (defun-compile-time walk-macro-call
1501 (map-function reduce-function screamer? partial? nested? form environment
)
1503 (funcall reduce-function
1504 (funcall map-function form
'macro-call
)
1510 (let ((*macroexpand-hook
* #'funcall
))
1511 (macroexpand-1 form environment
))
1518 (let ((*macroexpand-hook
* #'funcall
))
1519 (macroexpand-1 form environment
))
1522 (defun-compile-time walk-function-call
1523 (map-function reduce-function screamer? partial? nested? form environment
)
1524 (unless (null (rest (last form
)))
1525 (error "Improper function call form: ~S" form
))
1527 ((lambda-expression?
(first form
))
1531 (funcall map-function form
'lambda-call
)
1534 (reduce reduce-function
1535 (mapcar #'(lambda (subform)
1546 (walk-lambda-list map-function
1551 (second (first form
))
1553 (reduce reduce-function
1554 (mapcar #'(lambda (subform)
1562 (peal-off-documentation-string-and-declarations
1563 (rest (rest (first form
))) t
))))))
1564 (funcall map-function form
'lambda-call
)))
1565 ((valid-function-name?
(first form
))
1566 (if (symbolp (first form
))
1568 (funcall reduce-function
1569 (funcall map-function form
'symbol-call
)
1570 (reduce reduce-function
1571 (mapcar #'(lambda (subform)
1580 (funcall map-function form
'symbol-call
))
1582 (funcall reduce-function
1583 (funcall map-function form
'setf-call
)
1584 (reduce reduce-function
1585 (mapcar #'(lambda (subform)
1594 (funcall map-function form
'setf-call
))))
1595 (t (error "CAR of form ~S is not a valid function" form
))))
1597 ;;; Possible FORM-TYPEs
1599 ;;; LAMBDA-LIST VARIABLE
1601 ;;; BLOCK CATCH EVAL-WHEN FLET FUNCTION-LAMBDA FUNCTION-SYMBOL FUNCTION-SETF
1602 ;;; GO IF LABELS LET LET* MULTIPLE-VALUE-CALL MULTIPLE-VALUE-PROG1 PROGN
1603 ;;; PROGV QUOTE RETURN-FROM SETQ TAGBODY THE THROW UNWIND-PROTECT
1604 ;;; Symbolics special forms:
1605 ;;; SYS:VARIABLE-LOCATION COMPILER:INVISIBLE-REFERENCES
1606 ;;; Screamer special forms:
1607 ;;; FOR-EFFECTS LOCAL-SETF
1608 ;;; Partial special forms:
1611 ;;; MACRO-CALL LAMBDA-CALL SYMBOL-CALL SETF-CALL
1613 (defun-compile-time walk
1614 (map-function reduce-function screamer? partial? nested? form environment
)
1615 ;; needs work: Cannot walk MACROLET or special forms not in both CLtL1 and
1618 ((self-evaluating? form
) (funcall map-function form
'quote
))
1619 ((symbolp form
) (funcall map-function form
'variable
))
1620 ((eq (first form
) 'block
)
1622 map-function reduce-function screamer? partial? nested? form environment
))
1623 ((eq (first form
) 'catch
)
1625 map-function reduce-function screamer? partial? nested? form environment
))
1626 ((eq (first form
) 'eval-when
)
1628 map-function reduce-function screamer? partial? nested? form environment
))
1629 ((eq (first form
) 'flet
)
1631 map-function reduce-function screamer? partial? nested? form environment
1633 ((eq (first form
) 'function
)
1635 map-function reduce-function screamer? partial? nested? form environment
))
1636 ((eq (first form
) 'go
) (walk-go map-function form
))
1637 ((eq (first form
) 'if
)
1638 (walk-if map-function reduce-function screamer? partial? nested? form
1640 ((eq (first form
) 'labels
)
1642 map-function reduce-function screamer? partial? nested? form environment
1644 ((eq (first form
) 'let
)
1646 map-function reduce-function screamer? partial? nested? form environment
1648 ((eq (first form
) 'let
*)
1650 map-function reduce-function screamer? partial? nested? form environment
1652 ;; needs work: This is a temporary kludge to support MCL.
1653 ((and (eq (first form
) 'locally
) (null (fourth form
)))
1654 (walk map-function reduce-function screamer? partial? nested?
(third form
)
1656 ((eq (first form
) 'multiple-value-call
)
1657 (walk-multiple-value-call
1658 map-function reduce-function screamer? partial? nested? form environment
))
1659 ((eq (first form
) 'multiple-value-prog1
)
1660 (walk-multiple-value-prog1
1661 map-function reduce-function screamer? partial? nested? form environment
))
1662 ((eq (first form
) 'progn
)
1664 map-function reduce-function screamer? partial? nested? form environment
))
1665 ((eq (first form
) 'progv
)
1667 map-function reduce-function screamer? partial? nested? form environment
))
1668 ((eq (first form
) 'quote
) (walk-quote map-function form
))
1669 ((eq (first form
) 'return-from
)
1671 map-function reduce-function screamer? partial? nested? form environment
))
1672 ((eq (first form
) 'setq
)
1674 map-function reduce-function screamer? partial? nested? form environment
))
1675 ((eq (first form
) 'tagbody
)
1677 map-function reduce-function screamer? partial? nested? form environment
))
1678 ((eq (first form
) 'the
)
1680 map-function reduce-function screamer? partial? nested? form environment
))
1681 ((eq (first form
) 'throw
)
1683 map-function reduce-function screamer? partial? nested? form environment
))
1684 ((eq (first form
) 'unwind-protect
)
1685 (walk-unwind-protect
1686 map-function reduce-function screamer? partial? nested? form environment
))
1687 ((and screamer?
(eq (first form
) 'for-effects
))
1689 map-function reduce-function screamer? partial? nested? form environment
))
1690 ((and screamer?
(eq (first form
) 'setf
))
1692 map-function reduce-function screamer? partial? nested? form environment
))
1693 ((and screamer?
(eq (first form
) 'local
))
1696 map-function reduce-function screamer? partial? nested? form
1698 ((and screamer?
(eq (first form
) 'global
))
1699 (let ((*local?
* nil
))
1701 map-function reduce-function screamer? partial? nested? form
1703 ((and screamer?
(eq (first form
) 'multiple-value-call-nondeterministic
))
1704 (walk-multiple-value-call-nondeterministic
1705 map-function reduce-function screamer? partial? nested? form environment
))
1706 ((and partial?
(eq (first form
) 'full
)) (walk-full map-function form
))
1707 ((and (symbolp (first form
))
1708 (macro-function (first form
) environment
))
1710 map-function reduce-function screamer? partial? nested? form environment
))
1711 ((special-operator-p (first form
))
1712 (error "Cannot (currently) handle the special form ~S" (first form
)))
1713 (t (walk-function-call
1714 map-function reduce-function screamer? partial? nested? form
1717 (defun-compile-time process-subforms
(function form form-type environment
)
1719 (lambda-list (error "This shouldn't happen"))
1720 ((variable go
) form
)
1724 (mapcar #'(lambda (subform)
1725 (funcall function subform environment
))
1726 (rest (rest form
))))))
1731 (cl:multiple-value-bind
(body declarations documentation-string
)
1732 (peal-off-documentation-string-and-declarations
1733 (rest (rest binding
)) t
)
1735 ;; needs work: To process subforms of lambda list.
1737 ,@(if documentation-string
(list documentation-string
))
1740 #'(lambda (subform) (funcall function subform environment
))
1744 #'(lambda (subform) (funcall function subform environment
))
1745 (rest (rest form
)))))
1747 (cl:multiple-value-bind
(body declarations
)
1748 (peal-off-documentation-string-and-declarations (rest (rest form
)))
1752 (if (and (consp binding
) (= (length binding
) 2))
1754 ,(funcall function
(second binding
) environment
))
1759 #'(lambda (subform) (funcall function subform environment
)) body
))))
1762 #'(lambda (subform) (funcall function subform environment
))
1764 (quote (quotify form
))
1765 (the `(the ,(second form
) ,(funcall function
(third form
) environment
)))
1766 (macro-call (error "This shouldn't happen"))
1768 (cl:multiple-value-bind
(body declarations documentation-string
)
1769 (peal-off-documentation-string-and-declarations
1770 (rest (rest (first form
))) t
)
1771 ;; needs work: To process subforms of lambda list.
1772 `((lambda ,(second (first form
))
1773 ,@(if documentation-string
(list documentation-string
))
1775 ,@(mapcar #'(lambda (subform) (funcall function subform environment
))
1778 #'(lambda (subform) (funcall function subform environment
))
1782 (mapcar #'(lambda (subform) (funcall function subform environment
))
1785 (defun-compile-time deterministic?
(form environment
)
1787 #'(lambda (form form-type
)
1789 ((symbol-call setf-call
)
1790 (function-record-deterministic?
(get-function-record (first form
))))
1791 (multiple-value-call-nondeterministic nil
)
1792 ;; note: not really sure about CATCH, THROW and UNWIND-PROTECT
1794 ;; note: potentially inefficient because must walk entire form even
1795 ;; after it is known to be nondeterministic
1796 #'(lambda (&optional
(x nil x?
) y
) (if x?
(and x y
) t
))
1803 (defun-compile-time deterministic-lambda-list?
(lambda-list environment
)
1805 #'(lambda (form form-type
)
1807 ((symbol-call setf-call
)
1808 (function-record-deterministic?
(get-function-record (first form
))))
1809 (multiple-value-call-nondeterministic nil
)
1810 ;; note: not really sure about CATCH, THROW and UNWIND-PROTECT
1812 ;; note: potentially inefficient because must walk entire form even
1813 ;; after it is known to be nondeterministic
1814 #'(lambda (&optional
(x nil x?
) y
) (if x?
(and x y
) t
))
1821 (defun-compile-time needs-substitution?
(form environment
)
1823 #'(lambda (form form-type
)
1826 (not (and (every #'(lambda (form) (deterministic? form environment
))
1827 (peal-off-documentation-string-and-declarations
1828 (rest (rest (second form
))) t
))
1829 (deterministic-lambda-list?
1830 (second (second form
)) environment
))))
1831 ((function-symbol function-setf
)
1832 (not (function-record-deterministic?
1833 (get-function-record (second form
)))))
1834 (return-from (let ((tag (assoc (second form
) *block-tags
* :test
#'eq
)))
1835 (and tag
(second tag
))))
1836 (go (let ((tag (assoc (second form
) *tagbody-tags
*)))
1837 (and tag
(second tag
))))
1841 ;; note: potentially inefficient because must walk entire form even
1842 ;; after it is known to need substitution
1843 #'(lambda (&optional
(x nil x?
) y
) (if x?
(or x y
) '()))
1850 (defun-compile-time contains-local-setf
/setq?
(form environment
)
1851 (walk #'(lambda (form form-type
)
1852 (declare (ignore form
))
1853 (or (and *local?
* (eq form-type
'setq
))
1854 (eq form-type
'local-setf
)))
1855 ;; note: potentially inefficient because must walk entire form even
1856 ;; after it is known to contain a LOCAL SETF/SETQ special form
1857 #'(lambda (&optional
(x nil x?
) y
) (if x?
(or x y
) '()))
1864 (defun-compile-time form-callees
(form environment
)
1865 (walk #'(lambda (form form-type
)
1867 ((function-symbol function-setf
) (list (second form
)))
1868 ((symbol-call setf-call
) (list (first form
)))
1870 #'(lambda (&optional
(x nil x?
) y
)
1871 (if x?
(union x y
:test
#'equal
) '()))
1878 (defun-compile-time callees
(function-name)
1879 (function-record-callees (get-function-record function-name
)))
1881 (defun-compile-time indirect-callees-internal
(function-names callees
)
1882 (if (null function-names
)
1884 (let ((function-name (first function-names
)))
1885 (if (member function-name callees
:test
#'equal
)
1886 (indirect-callees-internal (rest function-names
) callees
)
1887 (indirect-callees-internal
1888 (rest function-names
)
1889 (indirect-callees-internal
1890 (callees function-name
) (cons function-name callees
)))))))
1892 (defun-compile-time indirect-callees
(function-name)
1893 (indirect-callees-internal (callees function-name
) '()))
1895 (defun-compile-time callers
(function-name)
1897 (function-names '()))
1898 (maphash #'(lambda (function-name function-record
)
1899 (declare (ignore function-record
))
1900 (push function-name function-names
))
1901 *function-record-table
*)
1902 (dolist (caller function-names
)
1903 (if (member function-name
(callees caller
) :test
#'equal
)
1904 (pushnew caller callers
:test
#'equal
)))
1907 (defun-compile-time indirect-callers-internal
(function-names callers
)
1908 (if (null function-names
)
1910 (let ((function-name (first function-names
)))
1911 (if (member function-name callers
:test
#'equal
)
1912 (indirect-callers-internal (rest function-names
) callers
)
1913 (indirect-callers-internal
1914 (rest function-names
)
1915 (indirect-callers-internal
1916 (callers function-name
) (cons function-name callers
)))))))
1918 (defun-compile-time indirect-callers
(function-name)
1919 (indirect-callers-internal (callers function-name
) '()))
1921 (defun-compile-time expand-local-setf
(pairs environment
)
1924 (let ((d (gensym "DUMMY-"))
1925 (dummy-argument (gensym "DUMMY-")))
1926 (cl:multiple-value-bind
(vars vals stores store-form access-form
)
1927 (get-setf-expansion (first pairs
) environment
)
1928 `(let* (,@(mapcar #'list vars vals
)
1929 (,dummy-argument
,(second pairs
))
1931 (trail #'(lambda () ,(subst d
(first stores
) store-form
)))
1932 ,@(if (null (rest (rest pairs
)))
1933 (list (subst dummy-argument
(first stores
) store-form
))
1934 (list (subst dummy-argument
(first stores
) store-form
)
1935 (expand-local-setf (rest (rest pairs
)) environment
))))))))
1937 (defun-compile-time expand-local-setq
(pairs environment
)
1940 (let ((d (gensym "DUMMY-")))
1941 `(let ((,d
,(first pairs
)))
1942 (trail #'(lambda () (setq ,(first pairs
) ,d
)))
1943 ,@(if (null (rest (rest pairs
)))
1946 ,(perform-substitutions (second pairs
) environment
)))
1949 ,(perform-substitutions (second pairs
) environment
))
1950 (expand-local-setq (rest (rest pairs
)) environment
)))))))
1952 (defun-compile-time perform-substitutions
(form environment
)
1953 (if (needs-substitution? form environment
)
1955 #'(lambda (form form-type
)
1957 (lambda-list (error "This shouldn't happen"))
1958 (variable (error "This shouldn't happen"))
1959 (block (let ((*block-tags
*
1960 (cons (list (second form
) nil
) *block-tags
*)))
1962 #'perform-substitutions form form-type environment
)))
1964 (unless (deterministic-lambda-list?
1965 (second (second form
)) environment
)
1967 "Cannot (currently) handle a LAMDBA expression with~%~
1968 nondeterministic initializations forms for~%~
1969 &OPTIONAL and &AUX parameters: ~S"
1971 (cl:multiple-value-bind
(body declarations documentation-string
)
1972 (peal-off-documentation-string-and-declarations
1973 (rest (rest (second form
))) t
)
1974 (if (every #'(lambda (form) (deterministic? form environment
))
1976 ;; needs work: To process subforms of lambda list.
1977 `#'(lambda ,(second (second form
))
1978 ,@(if documentation-string
(list documentation-string
))
1982 (perform-substitutions subform environment
))
1984 (let ((continuation (gensym "CONTINUATION-")))
1985 ;; note: This conses every time #'(LAMBDA (...) ...) is
1986 ;; accessed when it is nondeterministic. A small
1987 ;; price to pay for a lot of error checking.
1988 `(make-nondeterministic-function
1990 ;; needs work: To process subforms of lambda list.
1991 #'(lambda (,continuation
,@(second (second form
)))
1992 ,@(if documentation-string
(list documentation-string
))
1994 ,continuation
;ignore
1995 ,(cps-convert-progn body
2000 ((function-symbol function-setf
)
2001 (if (function-record-deterministic?
2002 (get-function-record (second form
)))
2004 ;; note: This conses every time #'FOO or #'(SETF FOO) is
2005 ;; accessed when FOO or (SETF FOO) is nondeterministic.
2006 ;; A small price to pay for a lot of error checking.
2007 `(make-nondeterministic-function
2008 :function
#',(cps-convert-function-name (second form
)))))
2009 (go (let ((tag (assoc (second form
) *tagbody-tags
*)))
2010 ;; note: Can't issue an error here if tag not found since it
2011 ;; might be outside the scope of a FOR-EFFECTS.
2012 (if (and tag
(second tag
)) `(,(second tag
)) form
)))
2013 (quote (error "This shouldn't happen"))
2015 (let ((tag (assoc (second form
) *block-tags
* :test
#'eq
))
2016 (value (perform-substitutions
2017 (if (= (length form
) 3) (third form
) nil
)
2019 ;; note: Can't issue an error here if tag not found since it
2020 ;; might be outside the scope of a FOR-EFFECTS.
2021 (if (and tag
(second tag
))
2022 (possibly-beta-reduce-funcall
2023 (second tag
) '() value
(fourth tag
))
2024 `(return-from ,(second form
) ,value
))))
2026 (expand-local-setq (rest form
) environment
)
2028 #'perform-substitutions form form-type environment
)))
2029 (tagbody (let ((*tagbody-tags
*
2030 (append (mapcar #'(lambda (tag) (list tag nil
))
2031 (remove-if #'consp
(rest form
)))
2034 #'perform-substitutions form form-type environment
)))
2035 (for-effects (perform-substitutions
2036 (let ((*macroexpand-hook
* #'funcall
))
2037 (macroexpand-1 form environment
))
2039 (local-setf (perform-substitutions
2040 (expand-local-setf (rest form
) environment
)
2042 (macro-call (error "This shouldn't happen"))
2043 (otherwise (process-subforms
2044 #'perform-substitutions form form-type environment
))))
2053 (defun-compile-time is-magic-declaration?
(form)
2055 (eq (first form
) 'declare
)
2057 (consp (second form
))
2058 (eq (first (second form
)) 'magic
)))
2060 (defun-compile-time is-magic-continuation?
(continuation)
2061 ;; Checks that CONTINUATION is of the form:
2062 ;; #'(lambda (...) (declare (magic) ...) ...)
2063 (and (consp continuation
)
2064 (eq (first continuation
) 'function
)
2065 (null (rest (last continuation
)))
2066 (= (length continuation
) 2)
2067 (lambda-expression?
(second continuation
))
2068 (>= (length (second continuation
)) 3)
2069 (is-magic-declaration?
(third (second continuation
)))))
2071 (defun-compile-time magic-continuation-argument
(continuation)
2072 (if (or (eq (first (second (second continuation
))) '&optional
)
2073 (eq (first (second (second continuation
))) '&rest
))
2074 (second (second (second continuation
)))
2075 (first (second (second continuation
)))))
2077 (defun-compile-time possibly-beta-reduce-funcall
2078 (continuation types form value?
)
2079 (unless (or (and (symbolp continuation
) (not (symbol-package continuation
)))
2080 (and (consp continuation
)
2081 (eq (first continuation
) 'function
)
2082 (null (rest (last continuation
)))
2083 (= (length continuation
) 2)
2084 (symbolp (second continuation
)))
2085 (is-magic-continuation? continuation
))
2086 (error "Please report this bug; This shouldn't happen (A)"))
2088 ((symbolp continuation
)
2092 `(multiple-value-call ,continuation
,form
)
2093 ;; note: This optimization is technically unsound if FORM
2094 ;; is a symbol macro that returns multiple values.
2095 `(funcall ,continuation
,form
))
2096 ;; note: This optimization assumes that there are no VALUES
2098 `(funcall ,continuation
(the (and ,@types
) ,form
)))
2099 `(progn ,form
(funcall ,continuation
))))
2100 ((symbolp (second continuation
))
2104 `(multiple-value-call ,continuation
,form
)
2105 ;; note: This optimization is technically unsound if FORM
2106 ;; is a symbol macro that returns multiple values.
2107 `(,(second continuation
) ,form
))
2108 ;; note: This optimization assumes that there are no VALUES
2110 `(,(second continuation
) (the (and ,@types
) ,form
)))
2111 `(progn ,form
(,(second continuation
)))))
2114 (if (null (second (second continuation
)))
2115 (error "Please report this bug; This shouldn't happen (B)"))
2117 ((eq (first (second (second continuation
))) '&rest
)
2119 `(let ((,(magic-continuation-argument continuation
)
2120 (multiple-value-list ,form
)))
2121 ;; Peal off LAMBDA, arguments, and DECLARE.
2122 ,@(rest (rest (rest (second continuation
)))))
2123 `(let ((,(magic-continuation-argument continuation
)
2124 (list (the (and ,@types
) ,form
))))
2125 ;; Peal off LAMBDA, arguments, and DECLARE.
2126 ,@(rest (rest (rest (second continuation
)))))))
2127 ((or (and (consp form
)
2129 (and (eq (first form
) 'function
)
2130 (null (rest (last form
)))
2132 (symbolp (second form
)))))
2133 (and (symbolp form
) (symbol-package form
))
2134 (symbol-package (magic-continuation-argument continuation
)))
2136 `(let ((,(magic-continuation-argument continuation
) ,form
))
2137 ,@(if (and *dynamic-extent?
* (is-magic-continuation? form
))
2140 ,(magic-continuation-argument continuation
)))))
2141 ;; Peal off LAMBDA, arguments, and DECLARE.
2142 ,@(rest (rest (rest (second continuation
)))))
2143 `(let ((,(magic-continuation-argument continuation
)
2144 (the (and ,@types
) ,form
)))
2147 ,(magic-continuation-argument continuation
)))
2148 ;; Peal off LAMBDA, arguments, and DECLARE.
2149 ,@(rest (rest (rest (second continuation
)))))))
2150 ;; note: This case may be unsoundly taken in the following cases:
2151 ;; a. (MAGIC-CONTINUATION-ARGUMENT CONTINUATION) is a
2152 ;; non-Screamer GENSYM. This can only happen if a
2153 ;; a BINDING-VARIABLE is a GENSYM in CPS-CONVERT-LET*.
2154 ;; b. FORM is a non-Screamer GENSYM
2157 (magic-continuation-argument continuation
)
2158 ;; Peal off LAMBDA, arguments, and DECLARE.
2159 `(progn ,@(rest (rest (rest (second continuation
)))))
2161 (subst `(the (and ,@types
) ,form
)
2162 (magic-continuation-argument continuation
)
2163 ;; Peal off LAMBDA, arguments, and DECLARE.
2164 `(progn ,@(rest (rest (rest (second continuation
)))))
2167 (unless (null (second (second continuation
)))
2168 (error "Please report this bug; This shouldn't happen (C)"))
2169 ;; Peal off LAMBDA, arguments, and DECLARE.
2170 `(progn ,form
,@(rest (rest (rest (second continuation
))))))))))
2172 (defun-compile-time void-continuation
(continuation)
2173 (unless (or (and (symbolp continuation
) (not (symbol-package continuation
)))
2174 (and (consp continuation
)
2175 (eq (first continuation
) 'function
)
2176 (null (rest (last continuation
)))
2177 (= (length continuation
) 2)
2178 (symbolp (second continuation
)))
2179 (is-magic-continuation? continuation
))
2180 (error "Please report this bug; This shouldn't happen (D)"))
2181 (let ((dummy-argument (gensym "DUMMY-")))
2182 ;; note: We could get rid of this bogosity by having two versions of each
2183 ;; nondeterministic function, one which returned a value and one which
2185 `#'(lambda (&rest
,dummy-argument
)
2187 (ignore ,dummy-argument
))
2188 ,@(cond ((symbolp continuation
) `((funcall ,continuation
)))
2189 ((symbolp (second continuation
)) `((,(second continuation
))))
2190 ;; Peal off LAMBDA, arguments, and DECLARE.
2191 (t (rest (rest (rest (second continuation
)))))))))
2193 (defun-compile-time cps-convert-function-name
(function-name)
2194 (if (symbolp function-name
)
2195 (intern (format nil
"~A-NONDETERMINISTIC" (string function-name
))
2196 (symbol-package function-name
))
2197 `(setf ,(intern (format nil
"~A-NONDETERMINISTIC"
2198 (string (second function-name
)))
2199 (symbol-package (second function-name
))))))
2201 (defun-compile-time cps-convert-block
2202 (name body continuation types value? environment
)
2203 (let* ((c (gensym "CONTINUATION-"))
2204 (*block-tags
* (cons (list name c types value?
) *block-tags
*)))
2205 (possibly-beta-reduce-funcall
2208 ,(cps-convert-progn body c types value? environment
))
2213 (defun-compile-time cps-convert-if
(antecedent
2220 (let ((c (gensym "CONTINUATION-"))
2221 (dummy-argument (gensym "DUMMY-"))
2222 (other-arguments (gensym "OTHER-")))
2223 (possibly-beta-reduce-funcall
2228 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2230 (ignore ,other-arguments
))
2232 ,(cps-convert consequent c types value? environment
)
2233 ,(cps-convert alternate c types value? environment
)))
2241 (defun-compile-time cps-convert-let
(bindings
2253 ,(cps-convert-progn body continuation types value? environment
))
2254 (let* ((binding (first bindings
))
2256 (if (symbolp binding
) binding
(first binding
)))
2258 (if (and (consp binding
) (= (length binding
) 2))
2261 (dummy-argument (gensym "DUMMY-"))
2262 (other-arguments (gensym "OTHER-")))
2265 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2267 (ignore ,other-arguments
))
2268 ,(cps-convert-let (rest bindings
)
2275 (cons (list binding-variable dummy-argument
)
2281 (defun-compile-time cps-convert-let
* (bindings
2289 (if (null declarations
)
2290 (cps-convert-progn body continuation types value? environment
)
2293 ,(cps-convert-progn body continuation types value? environment
)))
2294 (let* ((binding (first bindings
))
2296 (if (symbolp binding
) binding
(first binding
)))
2298 (if (and (consp binding
) (= (length binding
) 2))
2301 (other-arguments (gensym "OTHER-")))
2304 `#'(lambda (&optional
,binding-variable
&rest
,other-arguments
)
2306 (ignore ,other-arguments
))
2307 ,(cps-convert-let* (rest bindings
)
2318 (defun-compile-time cps-convert-multiple-value-call-internal
2319 (nondeterministic? function forms continuation types value? environment
2320 &optional arguments
)
2322 (if nondeterministic?
2323 ;; needs work: TYPES is never actually used in this branch.
2324 `(apply-nondeterministic-nondeterministic
2325 ,(if value? continuation
(void-continuation continuation
))
2327 (append ,@(reverse arguments
)))
2328 (possibly-beta-reduce-funcall
2331 `(apply ,function
(append ,@(reverse arguments
)))
2333 (let ((dummy-argument (gensym "DUMMY-")))
2336 `#'(lambda (&rest
,dummy-argument
)
2338 ,(cps-convert-multiple-value-call-internal
2339 nondeterministic? function
(rest forms
) continuation types value?
2340 environment
(cons dummy-argument arguments
)))
2345 (defun-compile-time cps-convert-multiple-value-call
2346 (nondeterministic? function forms continuation types value? environment
)
2347 (let ((dummy-argument (gensym "DUMMY-"))
2348 (other-arguments (gensym "OTHER-")))
2351 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2353 (ignore ,other-arguments
))
2354 ,(cps-convert-multiple-value-call-internal
2355 nondeterministic? dummy-argument forms continuation types value?
2361 (defun-compile-time cps-convert-multiple-value-prog1
2362 (form forms continuation types value? environment
)
2364 (let ((dummy-argument (gensym "DUMMY-")))
2367 `#'(lambda (&rest
,dummy-argument
)
2373 (possibly-beta-reduce-funcall
2374 continuation types
`(values-list ,dummy-argument
) t
))
2381 (cps-convert-progn (cons form forms
) continuation types nil environment
)))
2383 (defun-compile-time cps-convert-progn
2384 (body continuation types value? environment
)
2386 ((null body
) (possibly-beta-reduce-funcall continuation types nil value?
))
2388 (cps-convert (first body
) continuation types value? environment
))
2394 (rest body
) continuation types value? environment
))
2399 (defun-compile-time cps-convert-return-from
(name result environment
)
2400 (let ((tag (assoc name
*block-tags
* :test
#'eq
)))
2401 (if (and tag
(second tag
))
2402 (cps-convert result
(second tag
) (third tag
) (fourth tag
) environment
)
2403 ;; note: Can't issue an error here if tag not found since it might be
2404 ;; outside the scope of a FOR-EFFECTS. Thus we must compile a
2405 ;; RETURN-FROM nondeterministic code to deterministic code.
2406 ;; Likewise, can't issue an error here if tag is found but
2407 ;; (SECOND TAG) is NIL since this arrises when you have a
2408 ;; RETURN-FROM inside a FOR-EFFECTS to a tag outside the
2410 (let ((dummy-argument (gensym "DUMMY-")))
2413 `#'(lambda (&rest
,dummy-argument
)
2415 (return-from ,name
(values-list ,dummy-argument
)))
2420 (defun-compile-time cps-convert-setq
2421 (arguments continuation types value? environment
)
2422 (if (null arguments
)
2423 (possibly-beta-reduce-funcall continuation types nil value?
)
2424 (let ((dummy-argument (gensym "DUMMY-"))
2425 (other-arguments (gensym "OTHER-")))
2428 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2430 (ignore ,other-arguments
)
2431 ,@(if (and (null (rest (rest arguments
)))
2433 `((type (and ,@types
) ,dummy-argument
))))
2434 ,(if (null (rest (rest arguments
)))
2435 (possibly-beta-reduce-funcall
2438 `(setq ,(first arguments
) ,dummy-argument
)
2440 `(progn (setq ,(first arguments
) ,dummy-argument
)
2442 (rest (rest arguments
))
2447 (if (null (rest (rest arguments
))) types
'())
2451 (defun-compile-time cps-convert-tagbody
2452 (body continuation types value? environment
)
2453 (let ((segments (list (list 'header
)))
2454 (*tagbody-tags
* *tagbody-tags
*)) ;cool!
2457 (push form
(rest (first segments
)))
2458 (let ((c (gensym "CONTINUATION-")))
2459 (push (list form c
) *tagbody-tags
*)
2460 (push (list c
) segments
))))
2461 (push nil
(rest (first segments
)))
2462 (let ((segments (reverse segments
))
2463 (dummy-argument (gensym "DUMMY-"))
2464 (other-arguments (gensym "OTHER-")))
2465 ;; needs work: The closures created by LABELS functions aren't declared to
2466 ;; have DYNAMIC-EXTENT since I don't know how to do this in
2470 (let ((next (rest (member segment segments
:test
#'eq
))))
2472 (&optional
,dummy-argument
&rest
,other-arguments
)
2473 (declare (ignore ,dummy-argument
,other-arguments
))
2475 (reverse (rest segment
))
2476 (if next
`#',(first (first next
)) continuation
)
2481 ,(let ((next (rest segments
)))
2483 (reverse (rest (first segments
)))
2484 (if next
`#',(first (first next
)) continuation
)
2489 (defun-compile-time cps-convert-local-setf
/setq
2490 (arguments continuation types value? environment
)
2491 (if (null arguments
)
2492 (possibly-beta-reduce-funcall continuation types nil value?
)
2493 (let ((d (gensym "DUMMY-"))
2494 (dummy-argument (gensym "DUMMY-"))
2495 (other-arguments (gensym "OTHER-")))
2496 (cl:multiple-value-bind
(vars vals stores store-form access-form
)
2497 (get-setf-expansion (first arguments
) environment
)
2500 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2502 (ignore ,other-arguments
)
2503 ,@(if (and (null (rest (rest arguments
)))
2505 `((type (and ,@types
) ,dummy-argument
))))
2506 (let* (,@(mapcar #'list vars vals
) (,d
,access-form
))
2508 ,(if (null (rest (rest arguments
)))
2509 (possibly-beta-reduce-funcall
2512 (subst dummy-argument
(first stores
) store-form
)
2518 ,(cps-convert-local-setf/setq
2519 (rest (rest arguments
))
2524 ,(subst d
(first stores
) store-form
))))
2525 (if (null (rest (rest arguments
))) types
'())
2529 (defun-compile-time cps-convert-call
(function-name
2537 ;; needs work: TYPES is never actually used here.
2538 (if (null arguments
)
2539 (let ((c (gensym "CONTINUATION-")))
2540 (possibly-beta-reduce-funcall
2543 (,(cps-convert-function-name function-name
)
2545 ,@(reverse dummy-arguments
)))
2547 (if value? continuation
(void-continuation continuation
))
2549 (let ((dummy-argument (gensym "DUMMY-"))
2550 (other-arguments (gensym "OTHER-")))
2553 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2555 (ignore ,other-arguments
))
2563 (cons dummy-argument dummy-arguments
)))
2568 (defun-compile-time cps-non-convert-call
(function-name
2576 (if (null arguments
)
2577 (possibly-beta-reduce-funcall
2580 (if (not (null types
))
2581 `(the (and ,@types
) (,function-name
,@(reverse dummy-arguments
)))
2582 `(,function-name
,@(reverse dummy-arguments
)))
2584 (let ((dummy-argument (gensym "DUMMY-"))
2585 (other-arguments (gensym "OTHER-")))
2588 `#'(lambda (&optional
,dummy-argument
&rest
,other-arguments
)
2590 (ignore ,other-arguments
))
2591 ,(cps-non-convert-call
2598 (cons dummy-argument dummy-arguments
)))
2603 (defun-compile-time cps-convert
(form continuation types value? environment
)
2604 (walk #'(lambda (form form-type
)
2605 (if (and (not (eq form-type
'quote
))
2606 (deterministic? form environment
)
2607 (not (contains-local-setf/setq? form environment
)))
2608 (possibly-beta-reduce-funcall
2611 (perform-substitutions form environment
)
2614 (lambda-list (error "This shouldn't happen"))
2615 (variable (possibly-beta-reduce-funcall
2616 continuation types form value?
))
2617 (block (cps-convert-block (second form
)
2623 ((function-lambda function-symbol function-setf
)
2624 (possibly-beta-reduce-funcall
2627 (perform-substitutions form environment
)
2629 (go (error "This shouldn't happen"))
2630 (if (cps-convert-if (second form
)
2632 (if (null (rest (rest (rest form
))))
2639 (let (cl:multiple-value-bind
(body declarations
)
2640 (peal-off-documentation-string-and-declarations
2650 (let* (cl:multiple-value-bind
(body declarations
)
2651 (peal-off-documentation-string-and-declarations
2661 (multiple-value-call
2662 (cps-convert-multiple-value-call
2670 (multiple-value-prog1
2671 (cps-convert-multiple-value-prog1
2678 (progn (cps-convert-progn
2679 (rest form
) continuation types value? environment
))
2680 (quote (possibly-beta-reduce-funcall
2681 continuation types
(quotify form
) value?
))
2682 (return-from (cps-convert-return-from
2684 (if (= (length form
) 2) nil
(third form
))
2687 (cps-convert-local-setf/setq
2688 (rest form
) continuation types value? environment
)
2690 (rest form
) continuation types value? environment
)))
2691 (tagbody (cps-convert-tagbody
2692 (rest form
) continuation types value? environment
))
2693 (the (cps-convert (third form
)
2695 (cons (second form
) types
)
2698 (for-effects (possibly-beta-reduce-funcall
2699 continuation types form value?
))
2701 (cps-convert-local-setf/setq
2702 (rest form
) continuation types value? environment
))
2703 (multiple-value-call-nondeterministic
2704 (cps-convert-multiple-value-call
2712 (macro-call (error "This shouldn't happen"))
2714 (unless (deterministic-lambda-list?
2715 (second (first form
)) environment
)
2717 "Cannot (currently) handle a LAMDBA expression with~%~
2718 nondeterministic initializations forms for~%~
2719 &OPTIONAL and &AUX parameters: ~S"
2722 #'(lambda (argument)
2723 (and (symbolp argument
)
2724 (not (member argument lambda-list-keywords
2726 (second (first form
)))
2727 (error "Cannot (currently) handle a nondeterministic~%~
2728 form whose CAR is a LAMBDA expression with~%~
2729 lambda list keywords or arguments that are not~%~
2732 (unless (= (length (second (first form
)))
2733 (length (rest form
)))
2734 (error "The form ~S has a CAR which is a LAMBDA~%~
2735 expression which takes a different number of~%~
2736 arguments than it is called with"
2738 (cl:multiple-value-bind
(body declarations
)
2739 (peal-off-documentation-string-and-declarations
2740 (rest (rest (first form
))) t
)
2741 ;; note: The documentation string is lost for lambda calls
2742 ;; that are CPS Converted.
2744 (mapcar #'list
(second (first form
)) (rest form
))
2751 ((symbol-call setf-call
)
2752 (if (function-record-deterministic?
2753 (get-function-record (first form
)))
2754 (cps-non-convert-call (first form
)
2760 (cps-convert-call (first form
)
2768 "Cannot (currently) handle the special form ~S inside a~%~
2769 nondeterministic context."
2778 (defun-compile-time declare-deterministic
(function-name)
2779 (setf (function-record-deterministic?
(get-function-record function-name
)) t
))
2781 (defun-compile-time declare-nondeterministic
(function-name)
2782 (setf (function-record-deterministic?
(get-function-record function-name
))
2785 (defun-compile-time compute-callees
(body environment
)
2786 ;; note: What bogosity in CommonLisp! UNION should allow zero arguments and
2787 ;; return NIL as the identity element for use by REDUCE.
2790 (mapcar #'(lambda (form) (form-callees form environment
))
2791 (peal-off-documentation-string-and-declarations body t
))
2792 :initial-value
'()))
2794 (defun-compile-time cache-definition
(function-name lambda-list body callees
)
2795 (let ((function-record (get-function-record function-name
)))
2796 (setf (function-record-lambda-list function-record
) lambda-list
)
2797 (setf (function-record-body function-record
) body
)
2798 (setf (function-record-callees function-record
) callees
)))
2800 (defun-compile-time determine-whether-deterministic
(function-name environment
)
2801 ;; note: This is using the current rather than the saved ENVIRONMENT.
2802 (let* ((function-record (get-function-record function-name
)))
2803 (setf (function-record-deterministic? function-record
)
2804 (and (every #'(lambda (form) (deterministic? form environment
))
2805 (peal-off-documentation-string-and-declarations
2806 (function-record-body function-record
) t
))
2807 (deterministic-lambda-list?
2808 (function-record-lambda-list function-record
) environment
)))))
2810 (defun-compile-time determine-whether-callers-are-deterministic
2811 (function-name function-names environment
)
2812 ;; note: This is using the current rather than the saved ENVIRONMENT.
2813 (dolist (caller (callers function-name
))
2814 (unless (member caller function-names
:test
#'equal
)
2815 (determine-whether-deterministic caller environment
)
2816 (determine-whether-callers-are-deterministic
2817 caller
(cons caller function-names
) environment
))))
2819 (defun-compile-time function-definition
(function-name environment
)
2820 ;; note: This is using the current rather than the saved ENVIRONMENT.
2821 (let* ((function-record (get-function-record function-name
))
2822 (lambda-list (function-record-lambda-list function-record
))
2823 (body (function-record-body function-record
)))
2824 (cl:multiple-value-bind
(body declarations documentation-string
)
2825 (peal-off-documentation-string-and-declarations body t
)
2826 (if (function-record-deterministic? function-record
)
2827 (let ((*block-tags
* (list (list function-name nil
))))
2828 ;; needs work: To process subforms of lambda list.
2829 (list `(cl:defun
,function-name
,lambda-list
2830 ,@(if documentation-string
(list documentation-string
))
2832 ,@(mapcar #'(lambda (form)
2833 (perform-substitutions form environment
))
2835 `(declare-deterministic ',function-name
)))
2836 (let* ((continuation (gensym "CONTINUATION-"))
2837 ;; note: Could provide better TYPES and VALUE? here.
2838 (*block-tags
* (list (list function-name continuation
'() t
))))
2839 (list `(cl:defun
,function-name
,lambda-list
2840 ,@(if documentation-string
(list documentation-string
))
2847 #'(lambda (argument)
2848 (if (consp argument
)
2849 (if (and (consp (rest argument
))
2850 (consp (rest (rest argument
))))
2851 (list (first argument
) (third argument
))
2852 (list (first argument
)))
2856 lambda-list-keywords
2859 "Function ~S is a nondeterministic function. As such, it~%~
2860 must be called only from a nondeterministic context."
2862 `(cl:defun
,(cps-convert-function-name function-name
)
2863 (,continuation
,@lambda-list
)
2864 ,@(if documentation-string
(list documentation-string
))
2866 ,continuation
;ignore
2867 ,(cps-convert-progn body continuation
'() t environment
))
2868 `(declare-nondeterministic ',function-name
)))))))
2870 (defun-compile-time modified-function-definitions
(function-name environment
)
2871 ;; note: This is using the current rather than the saved ENVIRONMENT.
2872 (let ((function-record (get-function-record function-name
))
2873 (callers (indirect-callers function-name
))
2874 (function-records '()))
2875 (setf (function-record-old-deterministic? function-record
)
2876 (function-record-deterministic? function-record
))
2877 (setf (function-record-deterministic? function-record
) t
)
2878 (push function-record function-records
)
2879 (dolist (caller callers
)
2880 (let ((function-record (get-function-record caller
)))
2881 (unless (member function-record function-records
:test
#'eq
)
2882 (setf (function-record-old-deterministic? function-record
)
2883 (function-record-deterministic? function-record
))
2884 (setf (function-record-deterministic? function-record
) t
)
2885 (push function-record function-records
))))
2886 (dolist (caller callers
)
2887 (dolist (callee (callees caller
))
2888 (let ((function-record (get-function-record callee
)))
2889 (unless (member function-record function-records
:test
#'eq
)
2890 (setf (function-record-old-deterministic? function-record
)
2891 (function-record-deterministic? function-record
))
2892 (push function-record function-records
)))))
2893 (determine-whether-deterministic function-name environment
)
2894 (determine-whether-callers-are-deterministic function-name nil environment
)
2895 (let ((definitions (function-definition function-name environment
)))
2896 (unless (eq (not (function-record-deterministic? function-record
))
2897 (not (function-record-old-deterministic? function-record
)))
2898 (dolist (caller callers
)
2899 (if (and (not (equal caller function-name
))
2900 (some #'(lambda (callee)
2901 (let ((function-record (get-function-record callee
)))
2902 (not (eq (not (function-record-deterministic?
2904 (not (function-record-old-deterministic?
2905 function-record
))))))
2908 (append (function-definition caller environment
)
2910 ;; note: This is so that macroexpand without compile doesn't get out of
2912 (dolist (function-record function-records
)
2913 (setf (function-record-deterministic? function-record
)
2914 (function-record-old-deterministic? function-record
)))
2919 (defmacro-compile-time defun
2920 (function-name lambda-list
&body body
&environment environment
)
2921 (let ((*nondeterministic-context?
* t
))
2922 (check-function-name function-name
)
2923 (let* ((callees (compute-callees body environment
))
2924 (function-record (get-function-record function-name
))
2925 (function-record-lambda-list
2926 (function-record-lambda-list function-record
))
2927 (function-record-body (function-record-body function-record
))
2928 (function-record-callees (function-record-callees function-record
))
2929 (function-record-deterministic?
2930 (function-record-deterministic? function-record
))
2931 (function-record-old-deterministic?
2932 (function-record-old-deterministic? function-record
))
2933 (function-record-screamer?
2934 (function-record-screamer? function-record
)))
2935 (cache-definition function-name lambda-list body callees
)
2936 (let ((modified-function-definitions
2937 ;; note: This is using the current rather than the saved ENVIRONMENT.
2938 (modified-function-definitions function-name environment
)))
2939 ;; note: This is so that macroexpand without compile doesn't get out of
2941 (setf (function-record-lambda-list function-record
)
2942 function-record-lambda-list
)
2943 (setf (function-record-body function-record
) function-record-body
)
2944 (setf (function-record-callees function-record
)
2945 function-record-callees
)
2946 (setf (function-record-deterministic? function-record
)
2947 function-record-deterministic?
)
2948 (setf (function-record-old-deterministic? function-record
)
2949 function-record-old-deterministic?
)
2950 (setf (function-record-screamer? function-record
)
2951 function-record-screamer?
)
2952 `(eval-when (:compile-toplevel
:load-toplevel
:execute
)
2953 (cache-definition ',function-name
',lambda-list
',body
',callees
)
2954 ,@modified-function-definitions
2955 ',function-name
)))))
2957 (defmacro-compile-time either
(&body expressions
)
2958 "Nondeterministically evaluates and returns the value of one of its
2959 EXPRESSIONS. It sets up a choice point and evaluates the first
2960 EXPRESSION returning its result. Whenever backtracking proceeds to
2961 this choice point, the next EXPRESSION is evaluated and its result
2962 returned. When no more EXPRESSIONS remain, the current choice point is
2963 removed and backtracking continues to the next most recent choice
2964 point. As an optimization, the choice point created for this
2965 expression is removed before the evaluation of the last EXPRESSION so
2966 that a failure during the evaluation of the last expression will
2967 backtrack directly to the parent choice point of the EITHER
2968 expression. EITHER takes any number of arguments. With no arguments,
2969 \(EITHER) is equivalent to \(FAIL) and is thus deterministic. With one
2970 argument, \(EITHER EXPRESSION) is equivalent to expression itself and
2971 is thus deterministic only when EXPRESSION is deterministic. Either is
2972 a special form, not a function. It is an error for the expression
2973 #'EITHER to appear in a program. Thus \(FUNCALL #'EITHER ...) or
2974 \(APPLY #'EITHER ...) are in error and will yield unpredictable
2975 results. With two or more argument it is nondeterministic and can only
2976 appear in a nondeterministic context."
2977 ;; FIXME: ref to operators providing nondeterministic contexts
2978 (cond ((not expressions
)
2980 ((not (rest expressions
))
2981 (first expressions
))
2984 ,(first expressions
)
2985 (either ,@(rest expressions
))))))
2987 (defmacro-compile-time local
(&body expressions
&environment environment
)
2988 "Evaluates EXPRESSIONS in the same fashion as PROGN except that all
2989 SETF and SETQ expressions lexically nested in its body result in local
2990 side effects which are undone upon backtracking. Note that this
2991 affects only side effects introduced explicitly via SETF and SETQ.
2992 Side effects introduced by Common Lisp builtin in functions such as
2993 RPLACA are always global. Furthermore, it affects only occurrences of
2994 SETF and SETQ which appear textually nested in the body of the LOCAL
2995 expression -- not those appearing in functions called from the body.
2996 LOCAL and GLOBAL expressions may be nested inside one another. The
2997 nearest surrounding declaration determines whether or not a given SETF
2998 or SETQ results in a local or global side effect. Side effects default
2999 to be global when there is no surrounding LOCAL or GLOBAL expression.
3000 Local side effects can appear both in deterministic as well as
3001 nondeterministic contexts though different techniques are used to
3002 implement the trailing of prior values for restoration upon
3003 backtracking. In nondeterministic contexts, LOCAL as well as SETF are
3004 treated as special forms rather than macros. This should be completely
3005 transparent to the user."
3008 #'(lambda (form) (perform-substitutions form environment
))
3011 (defmacro-compile-time global
(&body expressions
&environment environment
)
3012 "Evaluates EXPRESSIONS in the same fashion as PROGN except that all
3013 SETF and SETQ expressions lexically nested in its body result in
3014 global side effects which are not undone upon backtracking. Note that
3015 this affects only side effects introduced explicitly via SETF and
3016 SETQ. Side effects introduced by Common Lisp builtin functions such as
3017 RPLACA are always global anyway. Furthermore, it affects only
3018 occurrences of SETF and SETQ which appear textually nested in the body
3019 of the GLOBAL expression -- not those appearing in functions called
3020 from the body. LOCAL and GLOBAL expressions may be nested inside one
3021 another. The nearest surrounding declaration determines whether or not
3022 a given SETF or SETQ results in a local or global side effect. Side
3023 effects default to be global when there is no surrounding LOCAL or
3024 GLOBAL expression. Global side effects can appear both in
3025 deterministic as well as nondeterministic contexts. In
3026 nondeterministic contexts, GLOBAL as well as SETF are treated as
3027 special forms rather than macros. This should be completely
3028 transparent to the user."
3029 (let ((*local?
* nil
))
3031 #'(lambda (form) (perform-substitutions form environment
))
3034 (defmacro-compile-time for-effects
(&body forms
&environment environment
)
3036 ,(let ((*nondeterministic-context?
* t
))
3037 (cps-convert-progn forms
'#'fail nil nil environment
))))
3039 (defmacro-compile-time one-value
(expression &optional
(default-expression '(fail)))
3040 "Returns the first value of a nondeterministic expression.
3041 EXPRESSION is evaluated, deterministically returning only its first
3042 nondeterministic value, if any. No further execution of EXPRESSION is
3043 attempted after it successfully returns one value. If EXPRESSION does
3044 not return any nondeterministic values \(i.e. it fails) then
3045 DEFAULT-EXPRESSION is evaluated and its value returned instead.
3046 DEFAULT-EXPRESSION defaults to \(FAIL) if not present. Local side
3047 effects performed by EXPRESSION are undone when ONE-VALUE returns. On
3048 the other hand, local side effects performed by DEFAULT-EXPRESSION are
3049 not undone when ONE-VALUE returns. A ONE-VALUE expression can appear
3050 in both deterministic and nondeterministic contexts. Irrespective of
3051 what context the ONE-VALUE expression appears in, EXPRESSION is always
3052 in a nondeterministic context, while DEFAULT-EXPRESSION is in whatever
3053 context the ONE-VALUE expression appears. A ONE-VALUE expression is
3054 nondeterministic if DEFAULT-EXPRESSION is present and is
3055 nondeterministic, otherwise it is deterministic. If DEFAULT-EXPRESSION
3056 is present and nondeterministic, and if EXPRESSION fails, then it is
3057 possible to backtrack into the DEFAULT-EXPRESSION and for the
3058 ONE-VALUE expression to nondeterministically return multiple times.
3059 ONE-VALUE is analogous to the cut primitive \(!) in Prolog."
3061 (for-effects (return-from one-value
,expression
))
3062 ,default-expression
))
3064 (defmacro-compile-time possibly?
(&body forms
)
3065 `(one-value (let ((value (progn ,@forms
))) (unless value
(fail)) value
) nil
))
3067 (defmacro-compile-time necessarily?
(&body forms
)
3070 (let ((value (progn ,@forms
)))
3071 (when value
(setf result value
) (fail))
3075 (defmacro-compile-time all-values
(&body expressions
)
3076 "Evaluates EXPRESSIONS \(wrapped in an implicit PROGN) and returns a
3077 list of all of the nondeterministic values returned by the last
3078 EXPRESSION. These values are produced by repeatedly evaluating the
3079 body and backtracking to produce the next value, until the body fails
3080 and yields no further values. Accordingly, local side effects
3081 performed by the body while producing each value are undone before
3082 attempting to produce subsequent values, and all local side effects
3083 performed by the body are undone upon exit from ALL-VALUES. Returns
3084 the list containing NIL if there are no EXPRESSIONS. An ALL-VALUES
3085 expression can appear in both deterministic and nondeterministic
3086 contexts. Irrespective of what context the ALL-VALUES expression
3087 appears in, the EXPRESSIONS are always in a nondeterministic context.
3088 An ALL-VALUES expression itself is always deterministic. ALL-VALUES is
3089 analogous to the bagof primitive in Prolog."
3090 (let ((values (gensym "VALUES"))
3091 (last-value-cons (gensym "LAST-VALUE-CONS")))
3092 `(let ((,values
'())
3093 (,last-value-cons nil
))
3095 (let ((value (progn ,@expressions
)))
3096 (global (if (null ,values
)
3097 (setf ,last-value-cons
(list value
)
3098 ,values
,last-value-cons
)
3099 (setf (rest ,last-value-cons
) (list value
)
3100 ,last-value-cons
(rest ,last-value-cons
))))))
3103 (defmacro-compile-time ith-value
(i expression
&optional
(default-expression '(fail)))
3104 "Returns the Ith value of a nondeterministic expression. EXPRESSION
3105 is evaluated, deterministically returning only its Ith
3106 nondeterministic value, if any. I must be an integer. The first
3107 nondeterministic value returned by EXPRESSION is numbered zero, the
3108 second one, etc. The Ith value is produced by repeatedly evaluating
3109 EXPRESSION, backtracking through and discarding the first I values and
3110 deterministically returning the next value produced. No further
3111 execution of EXPRESSION is attempted after it successfully returns the
3112 desired value. If EXPRESSION fails before returning both the I values
3113 to be discarded, as well as the desired Ith value, then
3114 DEFAULT-EXPRESSION is evaluated and its value returned instead.
3115 DEFAULT-EXPRESSION defaults to \(FAIL) if not present. Local side
3116 effects performed by EXPRESSION are undone when ITH-VALUE returns. On
3117 the other hand, local side effects performed by DEFAULT-EXPRESSION and
3118 by I are not undone when ITH-VALUE returns. An ITH-VALUE expression
3119 can appear in both deterministic and nondeterministic contexts.
3120 Irrespective of what context the ITH-VALUE expression appears in,
3121 EXPRESSION is always in a nondeterministic context, while
3122 DEFAULT-EXPRESSION and I are in whatever context the ITH-VALUE
3123 expression appears. An ITH-VALUE expression is nondeterministic if
3124 DEFAULT-EXPRESSION is present and is nondeterministic, or if I is
3125 nondeterministic. Otherwise it is deterministic. If DEFAULT-EXPRESSION
3126 is present and nondeterministic, and if EXPRESSION fails, then it is
3127 possible to backtrack into the DEFAULT-EXPRESSION and for the
3128 ITH-VALUE expression to nondeterministically return multiple times. If
3129 I is nondeterministic then the ITH-VALUE expression operates
3130 nondeterministically on each value of I. In this case, backtracking
3131 for each value of EXPRESSION and DEFAULT-EXPRESSION is nested in, and
3132 restarted for, each backtrack of I."
3133 (let ((counter (gensym "I")))
3135 (let ((,counter
(value-of ,i
)))
3136 (for-effects (let ((value ,expression
))
3137 (if (zerop ,counter
)
3138 (return-from ith-value value
)
3140 ,default-expression
))))
3142 (defun trail (function)
3143 ;; note: Is it really better to use VECTOR-PUSH-EXTEND than CONS for the
3145 (if *nondeterministic?
* (vector-push-extend function
*trail
* 1024)))
3148 (&optional
(format-string nil format-string?
) &rest format-args
)
3151 (let ((query (if format-string?
3152 (format nil
"~A (Y or N): "
3153 (apply #'format nil format-string format-args
))
3155 (emacs-eval '(y-or-n-p-begin))
3159 (format *query-io
* "~%~A" query
)
3160 (let ((char (read-char *query-io
*)))
3161 (when (or (char= char
#\y
) (char= char
#\Y
))
3162 (format *query-io
* "Y")
3163 (return-from y-or-n-p t
))
3164 (when (or (char= char
#\n) (char= char
#\N
))
3165 (format *query-io
* "N")
3166 (return-from y-or-n-p nil
)))
3167 (format *query-io
* "Please type a single character, Y or N")
3169 (emacs-eval '(y-or-n-p-end)))))
3170 (format-string?
(apply #'cl
:y-or-n-p format-string format-args
))
3173 (defmacro-compile-time print-values
(&body expressions
)
3174 "Evaluates EXPRESSIONS \(wrapped in an implicit PROGN) and prints
3175 each of the nondeterministic values returned by the last EXPRESSION in
3176 succession \(using PRINT). After each value is printed, the user is
3177 queried as to whether or not further values are desired. These values
3178 are produced by repeatedly evaluating the body and backtracking to
3179 produce the next value, until either the user indicates that no
3180 further values are desired or until the body fails and yields no
3181 further values. Accordingly, local side effects performed by the body
3182 while producing each value are undone after printing each value,
3183 before attempting to produce subsequent values, and all local side
3184 effects performed by the body are undone upon exit from PRINT-VALUES,
3185 either because there are no further values or because the user
3186 declines to produce further values. A PRINT-VALUES expression can
3187 appear in both deterministic and nondeterministic contexts.
3188 Irrespective of what context the PRINT-VALUES expression appears in,
3189 the EXPRESSIONS are always in a nondeterministic context. A
3190 PRINT-VALUES expression itself is always deterministic and always
3191 returns NIL. PRINT-VALUES is analogous to the standard top-level user
3192 interface in Prolog."
3193 ;; FIXME: Documentation lies: does not always return NIL.
3196 (let ((value (progn ,@expressions
)))
3198 (unless (y-or-n-p "Do you want another solution?")
3199 (throw 'succeed value
))))))
3201 ;;; note: Should have way of having a stream of values.
3203 (eval-when (:compile-toplevel
:load-toplevel
:execute
) (setf *screamer?
* t
))
3205 (defun print-nondeterministic-function
3206 (nondeterministic-function stream print-level
)
3207 (declare (ignore print-level
))
3208 (format stream
"#<~A ~S>"
3210 (nondeterministic-function-function nondeterministic-function
)))
3212 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3213 (declare-nondeterministic 'a-boolean
))
3215 (cl:defun
a-boolean ()
3217 "A-BOOLEAN is a nondeterministic function. As such, it must be called only~%~
3218 from a nondeterministic context."))
3220 (cl:defun
a-boolean-nondeterministic (continuation)
3221 (choice-point (funcall continuation t
))
3222 (funcall continuation nil
))
3225 "Backtracks to the most recent choise point. Equivalent to
3226 \(EITHER). Note that FAIL is deterministic function and thus it is
3227 permissible to reference #'FAIL, and write \(FUNCALL #'FAIL) or
3228 \(APPLY #'FAIL). In nondeterministic contexts, the expression \(FAIL)
3229 is optimized to generate inline backtracking code."
3230 ;; FIXME: Since we export FAIL, throwing to it is probably a bad idea.
3231 ;; ...better throw to %FAIL.
3234 (defmacro-compile-time when-failing
((&body failing-forms
) &body forms
)
3235 (let ((old-fail (gensym "FAIL-")))
3236 `(let ((,old-fail
#'fail
))
3238 (progn (setf (symbol-function 'fail
)
3239 #'(lambda () ,@failing-forms
(funcall ,old-fail
)))
3241 (setf (symbol-function 'fail
) ,old-fail
)))))
3243 (defmacro-compile-time count-failures
(&body forms
)
3244 (let ((values (gensym "VALUES-")))
3245 `(let ((failure-count 0))
3246 (when-failing ((incf failure-count
))
3247 (let ((,values
(multiple-value-list (progn ,@forms
))))
3248 (format t
"Failures = ~10<~;~d~>" failure-count
)
3249 (values-list ,values
))))))
3251 (defun nondeterministic-function?
(x)
3252 "Returns T if X is a nondeterministic function object and NIL
3253 otherwise. Nondeterministic function objects can be produced in two
3254 ways. First, the special form \(FUNCTION FOO) \(i.e. #'FOO) will
3255 \(deterministically) evaluate to a nondeterministic function object if
3256 FOO names a nondeterministic function defined by DEFUN. Second, the
3257 special form \(FUNCTION \(LAMBDA \(...) ...)) \(i.e. #'\(lambda \(...)
3258 ...)) will \(deterministically) evaluate to a nondeterministic function
3259 object if the body of the lambda expression contains a
3260 nondeterministic expression."
3261 ;; FIXME: Is the above really true? What about FDEFINITION,
3262 ;; SYMBOL-FUNCTION, or #'X where X is defined by FLET or LABELS?
3263 (nondeterministic-function?-internal
(value-of x
)))
3265 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3266 (declare-nondeterministic 'funcall-nondeterministic
))
3268 (cl:defun
funcall-nondeterministic (function &rest arguments
)
3269 "Analogous to the Common Lisp built-in function FUNCALL except that
3270 it accepts both ordinary Common Lisp \(deterministic) function objects
3271 as well as nondeterministic function objects for function. You must
3272 use FUNCALL-NONDETERMINISTIC to funcall a nondeterministic function
3273 object. A runtime error will be signalled if you attempt to funcall a
3274 nondeterministic function object with FUNCALL. You can use
3275 FUNCALL-NONDETERMINISTIC to funcall either a deterministic or
3276 nondeterministic function object though even if all of the arguments
3277 to FUNCALL-NONDETERMINISTIC are deterministic and FUNCTION is a
3278 deterministic function object, the call expression will still be
3279 nondeterministic \(with presumably a single value), since it is
3280 impossible to determine at compile time that a given call to
3281 FUNCALL-NONDETERMINISTIC will be passed only deterministic function
3282 objects for function."
3283 (declare (ignore function arguments
))
3285 "FUNCALL-NONDETERMINISTIC is a nondeterministic function. As such, it~%~
3286 must be called only from a nondeterministic context."))
3288 (cl:defun
funcall-nondeterministic-nondeterministic
3289 (continuation function
&rest arguments
)
3290 (let ((function (value-of function
)))
3291 (if (nondeterministic-function? function
)
3292 (apply (nondeterministic-function-function function
)
3295 (funcall continuation
(apply function arguments
)))))
3297 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3298 (declare-nondeterministic 'apply-nondeterministic
))
3300 (cl:defun
apply-nondeterministic (function argument
&rest arguments
)
3301 "Analogous to the Common Lisp built-in function APPLY except that it
3302 accepts both ordinary Common Lisp \(deterministic) function objects as
3303 well as nondeterministic function objects for function. You must use
3304 APPLY-NONDETERMINISTIC to apply a nondeterministic function object. A
3305 runtime error will be signalled if you attempt to apply a
3306 nondeterministic function object with APPLY. You can use
3307 APPLY-NONDETERMINISTIC to apply either a deterministic or
3308 nondeterministic function object though even if all of the arguments
3309 to APPLY-NONDETERMINISTIC are deterministic and function is a
3310 deterministic function object, the call expression will still be
3311 nondeterministic \(with presumably a single value), since it is
3312 impossible to determine at compile time that a given call to
3313 APPLY-NONDETERMINISTIC will be passed only deterministic function
3314 objects for function."
3315 (declare (ignore function argument arguments
))
3317 "APPLY-NONDETERMINISTIC is a nondeterministic function. As such, it must~%~
3318 be called only from a nondeterministic context."))
3320 (cl:defun
apply-nondeterministic-nondeterministic
3321 (continuation function argument
&rest arguments
)
3322 (let ((function (value-of function
)))
3323 (if (nondeterministic-function? function
)
3324 ;; note: I don't know how to avoid the consing here.
3325 (apply (nondeterministic-function-function function
)
3327 (apply #'list
* (cons argument arguments
)))
3328 (funcall continuation
(apply function argument arguments
)))))
3330 (defmacro-compile-time multiple-value-bind
3331 (variables form
&body body
&environment environment
)
3332 (if (every #'(lambda (form) (deterministic? form environment
))
3333 (peal-off-documentation-string-and-declarations body
))
3334 `(cl:multiple-value-bind
,variables
,form
,@body
)
3335 (let ((other-arguments (gensym "OTHER-")))
3336 `(multiple-value-call-nondeterministic
3337 #'(lambda (&optional
,@variables
&rest
,other-arguments
)
3338 (declare (ignore ,other-arguments
))
3342 (defun unwind-trail ()
3345 (if (zerop (fill-pointer *trail
*)) (return-from unwind-trail
))
3346 (funcall (vector-pop *trail
*))
3347 ;; note: This is to allow the trail closures to be garbage collected.
3348 (setf (aref *trail
* (fill-pointer *trail
*)) nil
)
3351 (defun purge (function-name)
3352 "Removes any information about FUNCTION-NAME from Screamer's
3353 who-calls database."
3354 (remhash (value-of function-name
) *function-record-table
*)
3357 (defun unwedge-screamer ()
3358 "Removes any information about all user defined functions from
3359 Screamer's who-calls database."
3360 (maphash #'(lambda (function-name function-record
)
3361 (unless (function-record-screamer? function-record
)
3362 (remhash function-name
*function-record-table
*)))
3363 *function-record-table
*)
3366 ;;; note: These optimized versions of AN-INTEGER, AN-INTEGER-ABOVE,
3367 ;;; AN-INTEGER-BELOW, AN-INTEGER-BETWEEN and A-MEMBER-OF have different
3368 ;;; failure behavior as far as WHEN-FAILING is concerned than the
3369 ;;; original purely Screamer versions. This is likely to affect only
3370 ;;; failure counts generated by COUNT-FAILURES. A small price to pay for
3371 ;;; tail recursion optimization.
3373 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3374 (declare-nondeterministic 'an-integer
))
3376 (cl:defun
an-integer ()
3378 "AN-INTEGER is a nondeterministic function. As such, it must be called~%~
3379 only from a nondeterministic context."))
3381 (cl:defun
an-integer-nondeterministic (continuation)
3382 (choice-point-external
3383 (choice-point-internal (funcall continuation
0))
3385 (loop (choice-point-internal (funcall continuation i
))
3386 (choice-point-internal (funcall continuation
(- i
)))
3389 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3390 (declare-nondeterministic 'an-integer-above
))
3392 (cl:defun
an-integer-above (low)
3393 (declare (ignore low
))
3395 "AN-INTEGER-ABOVE is a nondeterministic function. As such, it must be~%~
3396 called only from a nondeterministic context."))
3398 (cl:defun
an-integer-above-nondeterministic (continuation low
)
3399 (let ((low (ceiling (value-of low
))))
3400 (choice-point-external
3402 (loop (choice-point-internal (funcall continuation i
))
3405 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3406 (declare-nondeterministic 'an-integer-below
))
3408 (cl:defun
an-integer-below (high)
3409 (declare (ignore high
))
3411 "AN-INTEGER-BELOW is a nondeterministic function. As such, it must be~%~
3412 called only from a nondeterministic context."))
3414 (cl:defun
an-integer-below-nondeterministic (continuation high
)
3415 (let ((high (floor (value-of high
))))
3416 (choice-point-external
3418 (loop (choice-point-internal (funcall continuation i
))
3421 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3422 (declare-nondeterministic 'an-integer-between
))
3424 (cl:defun
an-integer-between (low high
)
3425 "Nondeterministically returns an integer in the closed interval
3426 [LOW, HIGH]. The results are returned in ascending order. LOW and HIGH
3427 must be integers. Fails if the interval does not contain any
3429 (declare (ignore low high
))
3431 "AN-INTEGER-BETWEEN is a nondeterministic function. As such, it must be~%~
3432 called only from a nondeterministic context."))
3434 (cl:defun
an-integer-between-nondeterministic (continuation low high
)
3435 (let ((low (ceiling (value-of low
)))
3436 (high (floor (value-of high
))))
3437 (unless (> low high
)
3438 (choice-point-external
3439 (do ((i low
(1+ i
))) ((= i high
))
3440 (choice-point-internal (funcall continuation i
))))
3441 (funcall continuation high
))))
3443 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3444 (declare-nondeterministic 'a-member-of
))
3446 (cl:defun
a-member-of (sequence)
3447 "Nondeterministically returns an element of SEQUENCE. The elements
3448 are returned in the order that they appear in SEQUENCE. SEQUENCE must
3449 be either a list or a vector."
3450 (declare (ignore sequence
))
3452 "A-MEMBER-OF is a nondeterministic function. As such, it must be called~%~
3453 only from a nondeterministic context."))
3455 (cl:defun
a-member-of-nondeterministic (continuation sequence
)
3456 (let ((sequence (value-of sequence
)))
3459 (unless (null sequence
)
3460 (choice-point-external
3461 (loop (if (null (rest sequence
)) (return))
3462 (choice-point-internal (funcall continuation
(first sequence
)))
3463 (setf sequence
(value-of (rest sequence
)))))
3464 (funcall continuation
(first sequence
))))
3466 (let ((n (1- (length sequence
))))
3468 (choice-point-external
3470 (choice-point-internal (funcall continuation
(aref sequence i
)))))
3471 (funcall continuation
(aref sequence n
)))))
3472 (t (error "SEQUENCE must be a sequence")))))
3474 ;;; note: The following two functions work only when Screamer is running under
3475 ;;; ILisp/GNUEmacs with iscream.el loaded.
3477 (defun emacs-eval (expression)
3479 (error "Cannot do EMACS-EVAL unless Screamer is running under~%~
3480 ILisp/GNUEmacs with iscream.el loaded."))
3481 (format *terminal-io
* "~A~A~A"
3482 (format nil
"~A" (code-char 27))
3483 (string-downcase (format nil
"~A" expression
))
3484 (format nil
"~A" (code-char 29))))
3486 (defmacro-compile-time local-output
(&body forms
)
3489 (error "Cannot do LOCAL-OUTPUT unless Screamer is running under~%~
3490 ILisp/GNUEmacs with iscream.el loaded."))
3491 (trail #'(lambda () (emacs-eval '(pop-end-marker))))
3492 (emacs-eval '(push-end-marker))
3497 (defvar *name
* 0 "The counter for anonymous names.")
3499 (defvar *minimum-shrink-ratio
* 1e-2
3500 "Ignore propagations which reduce the range of a variable by less than this
3503 (defvar *maximum-discretization-range
* 20
3504 "Discretize integer variables whose range is not greater than this number.
3505 Discretize all integer variables if NIL.
3506 Must be an integer or NIL.")
3508 (defvar *strategy
* :gfc
3509 "Strategy to use for FUNCALLV and APPLYV: either :GFC or :AC")
3511 ;;; note: Enable this to use CLOS instead of DEFSTRUCT for variables.
3513 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
3514 (pushnew :screamer-clos
*features
* :test
#'eq
))
3517 (defstruct-compile-time (variable (:print-function print-variable
)
3518 (:predicate variable?
)
3519 (:constructor make-variable-internal
))
3522 (enumerated-domain t
)
3523 (enumerated-antidomain nil
)
3525 (possibly-integer? t
)
3526 (possibly-noninteger-real? t
)
3527 (possibly-nonreal-number? t
)
3528 (possibly-boolean? t
)
3529 (possibly-nonboolean-nonnumber? t
)
3534 (defclass variable
()
3535 ((name :accessor variable-name
:initarg
:name
)
3536 (noticers :accessor variable-noticers
:initform nil
)
3537 (enumerated-domain :accessor variable-enumerated-domain
:initform t
)
3538 (enumerated-antidomain :accessor variable-enumerated-antidomain
3540 (value :accessor variable-value
)
3541 (possibly-integer?
:accessor variable-possibly-integer?
:initform t
)
3542 (possibly-noninteger-real?
:accessor variable-possibly-noninteger-real?
3544 (possibly-nonreal-number?
:accessor variable-possibly-nonreal-number?
3546 (possibly-boolean?
:accessor variable-possibly-boolean?
:initform t
)
3547 (possibly-nonboolean-nonnumber?
3548 :accessor variable-possibly-nonboolean-nonnumber?
3550 (lower-bound :accessor variable-lower-bound
:initform nil
)
3551 (upper-bound :accessor variable-upper-bound
:initform nil
)))
3554 (defmethod print-object ((variable variable
) stream
)
3555 (print-variable variable stream nil
))
3558 (defun-compile-time variable?
(thing) (typep thing
'variable
))
3560 (defun booleanp (x) (typep x
'boolean
))
3562 (defun infinity-min (x y
) (and x y
(min x y
)))
3564 (defun infinity-max (x y
) (and x y
(max x y
)))
3566 (defun infinity-+ (x y
) (and x y
(+ x y
)))
3568 (defun infinity-- (x y
) (and x y
(- x y
)))
3570 (defun infinity-* (x y
) (and x y
(* x y
)))
3572 (defun contains-variables?
(x)
3574 (cons (or (contains-variables?
(car x
)) (contains-variables?
(cdr x
))))
3578 (defun eliminate-variables (x)
3579 (if (contains-variables? x
)
3581 (cons (eliminate-variables (car x
)) (eliminate-variables (cdr x
)))
3582 (eliminate-variables (variable-value x
)))
3585 (defun print-variable (x stream print-level
)
3586 (declare (ignore print-level
))
3587 (let ((x (value-of x
)))
3590 (if (and (not (eq (variable-enumerated-domain x
) t
))
3591 (not (null (variable-enumerated-antidomain x
))))
3592 (error "This shouldn't happen"))
3593 (format stream
"[~S" (variable-name x
))
3595 (cond ((variable-boolean? x
) " Boolean")
3596 ((variable-integer? x
) " integer")
3598 (if (variable-noninteger? x
) " noninteger-real" " real"))
3599 ((variable-number? x
)
3600 (cond ((variable-nonreal? x
) " nonreal-number")
3601 ((variable-noninteger? x
) " noninteger-number")
3603 ((variable-nonnumber? x
) " nonnumber")
3604 ((variable-nonreal? x
) " nonreal")
3605 ((variable-noninteger? x
) " noninteger")
3607 (if (variable-real? x
)
3608 (if (variable-lower-bound x
)
3609 (if (variable-upper-bound x
)
3610 (format stream
" ~D:~D"
3611 (variable-lower-bound x
) (variable-upper-bound x
))
3612 (format stream
" ~D:" (variable-lower-bound x
)))
3613 (if (variable-upper-bound x
)
3614 (format stream
" :~D" (variable-upper-bound x
)))))
3615 (if (and (not (eq (variable-enumerated-domain x
) t
))
3616 (not (variable-boolean? x
)))
3617 (format stream
" enumerated-domain:~S"
3618 (variable-enumerated-domain x
)))
3619 (if (not (null (variable-enumerated-antidomain x
)))
3620 (format stream
" enumerated-antidomain:~S"
3621 (variable-enumerated-antidomain x
)))
3622 (format stream
"]"))
3623 (t (format stream
"~S" x
)))))
3625 (defun make-variable (&optional
(name nil name?
))
3626 "Creates and returns a new variable. Variables are assigned a name
3627 which is only used to identify the variable when it is printed. If the
3628 parameter NAME is given then it is assigned as the name of the
3629 variable. Otherwise, a unique name is assigned. The parameter NAME can
3630 be any Lisp object."
3633 (make-variable-internal :name
(if name? name
(incf *name
*)))
3635 (make-instance 'variable
:name
(if name? name
(incf *name
*)))))
3636 (setf (variable-value variable
) variable
)
3639 (defun variable-integer?
(x)
3640 (and (not (variable-possibly-boolean? x
))
3641 (not (variable-possibly-nonboolean-nonnumber? x
))
3642 (not (variable-possibly-nonreal-number? x
))
3643 (not (variable-possibly-noninteger-real? x
))
3644 (variable-possibly-integer? x
)))
3646 (defun variable-noninteger?
(x)
3647 (and (or (variable-possibly-boolean? x
)
3648 (variable-possibly-nonboolean-nonnumber? x
)
3649 (variable-possibly-nonreal-number? x
)
3650 (variable-possibly-noninteger-real? x
))
3651 (not (variable-possibly-integer? x
))))
3653 (defun variable-real?
(x)
3654 (and (not (variable-possibly-boolean? x
))
3655 (not (variable-possibly-nonboolean-nonnumber? x
))
3656 (not (variable-possibly-nonreal-number? x
))
3657 (or (variable-possibly-noninteger-real? x
)
3658 (variable-possibly-integer? x
))))
3660 (defun variable-nonreal?
(x)
3661 (and (or (variable-possibly-boolean? x
)
3662 (variable-possibly-nonboolean-nonnumber? x
)
3663 (variable-possibly-nonreal-number? x
))
3664 (not (variable-possibly-noninteger-real? x
))
3665 (not (variable-possibly-integer? x
))))
3667 (defun variable-number?
(x)
3668 (and (not (variable-possibly-boolean? x
))
3669 (not (variable-possibly-nonboolean-nonnumber? x
))
3670 (or (variable-possibly-nonreal-number? x
)
3671 (variable-possibly-noninteger-real? x
)
3672 (variable-possibly-integer? x
))))
3674 (defun variable-nonnumber?
(x)
3675 (and (or (variable-possibly-boolean? x
)
3676 (variable-possibly-nonboolean-nonnumber? x
))
3677 (not (variable-possibly-nonreal-number? x
))
3678 (not (variable-possibly-noninteger-real? x
))
3679 (not (variable-possibly-integer? x
))))
3681 (defun variable-boolean?
(x)
3682 (and (variable-possibly-boolean? x
)
3683 (not (variable-possibly-nonboolean-nonnumber? x
))
3684 (not (variable-possibly-nonreal-number? x
))
3685 (not (variable-possibly-noninteger-real? x
))
3686 (not (variable-possibly-integer? x
))))
3688 (defun variable-nonboolean?
(x)
3689 (and (not (variable-possibly-boolean? x
))
3690 (or (variable-possibly-nonboolean-nonnumber? x
)
3691 (variable-possibly-nonreal-number? x
)
3692 (variable-possibly-noninteger-real? x
)
3693 (variable-possibly-integer? x
))))
3695 (defun variable-true?
(x) (eq (variable-value x
) t
))
3697 (defun variable-false?
(x) (null (variable-value x
)))
3702 (if (or (not (variable? x
))
3703 #+screamer-clos
(not (slot-boundp x
'value
))
3704 (eq (variable-value x
) x
))
3705 (return-from value-of x
))
3706 (setf x
(variable-value x
))
3709 (defun variablize (x)
3713 (if (or (not (variable?
(variable-value x
)))
3714 (eq (variable-value x
) x
))
3715 (return-from variablize x
))
3716 (setf x
(variable-value x
))
3718 (let ((y (make-variable))) (restrict-value! y x
) y
)))
3720 (defun bound?
(x) (not (variable?
(value-of x
))))
3723 (let ((x (value-of x
)))
3724 (and (not (variable? x
))
3725 (or (not (consp x
)) (and (ground?
(car x
)) (ground?
(cdr x
)))))))
3727 (defun apply-substitution (x)
3728 (let ((x (value-of x
)))
3730 (cons (apply-substitution (car x
)) (apply-substitution (cdr x
)))
3733 (defun occurs-in?
(x value
)
3734 ;; note: X must be a variable such that (EQ X (VALUE-OF X)).
3735 ;; note: Will loop if VALUE is circular.
3738 ((and (variable? value
) (not (eq value
(variable-value value
))))
3739 (occurs-in? x
(variable-value value
)))
3740 ((consp value
) (or (occurs-in? x
(car value
)) (occurs-in? x
(cdr value
))))
3743 (defun attach-noticer!-internal
(noticer x
)
3744 ;; note: Will loop if X is circular.
3746 (cons (attach-noticer!-internal noticer
(car x
))
3747 (attach-noticer!-internal noticer
(cdr x
)))
3748 (variable (if (eq x
(variable-value x
))
3749 ;; note: I can't remember why this check for duplication is
3751 (unless (member noticer
(variable-noticers x
) :test
#'eq
)
3752 ;; note: This can't be a PUSH because of the Lucid screw.
3753 (local (setf (variable-noticers x
)
3754 (cons noticer
(variable-noticers x
)))))
3755 (attach-noticer!-internal noticer
(variable-value x
))))))
3757 (defun attach-noticer! (noticer x
)
3758 (attach-noticer!-internal noticer x
)
3761 (defun run-noticers (x)
3762 (dolist (noticer (variable-noticers x
)) (funcall noticer
)))
3766 (defun restrict-integer! (x)
3767 ;; note: X must be a variable.
3768 (unless (variable-possibly-integer? x
) (fail))
3769 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3771 (when (variable-possibly-noninteger-real? x
)
3772 (local (setf (variable-possibly-noninteger-real? x
) nil
))
3774 (when (variable-possibly-nonreal-number? x
)
3775 (local (setf (variable-possibly-nonreal-number? x
) nil
))
3777 (when (variable-possibly-boolean? x
)
3778 (local (setf (variable-possibly-boolean? x
) nil
))
3780 (when (variable-possibly-nonboolean-nonnumber? x
)
3781 (local (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
3783 (when (and (variable-lower-bound x
)
3784 (not (integerp (variable-lower-bound x
))))
3785 (if (and (variable-upper-bound x
)
3786 (< (variable-upper-bound x
)
3787 (ceiling (variable-lower-bound x
))))
3789 (local (setf (variable-lower-bound x
)
3790 (ceiling (variable-lower-bound x
))))
3792 (when (and (variable-upper-bound x
)
3793 (not (integerp (variable-upper-bound x
))))
3794 (if (and (variable-lower-bound x
)
3795 (> (variable-lower-bound x
)
3796 (floor (variable-upper-bound x
))))
3798 (local (setf (variable-upper-bound x
) (floor (variable-upper-bound x
))))
3801 (cond ((eq (variable-enumerated-domain x
) t
)
3802 (if (and (variable-lower-bound x
)
3803 (variable-upper-bound x
)
3804 (or (null *maximum-discretization-range
*)
3805 (<= (- (variable-upper-bound x
)
3806 (variable-lower-bound x
))
3807 *maximum-discretization-range
*)))
3808 (set-enumerated-domain!
3809 x
(all-values (an-integer-between
3810 (variable-lower-bound x
)
3811 (variable-upper-bound x
))))))
3812 ((not (every #'integerp
(variable-enumerated-domain x
)))
3813 ;; note: Could do less consing if had LOCAL DELETE-IF.
3814 ;; This would also allow checking list only once.
3815 (set-enumerated-domain!
3816 x
(remove-if-not #'integerp
(variable-enumerated-domain x
)))))
3817 (run-noticers x
)))))
3819 (defun restrict-noninteger! (x)
3820 ;; note: X must be a variable.
3821 (unless (or (variable-possibly-noninteger-real? x
)
3822 (variable-possibly-nonreal-number? x
)
3823 (variable-possibly-boolean? x
)
3824 (variable-possibly-nonboolean-nonnumber? x
))
3826 (when (and (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3827 (variable-possibly-integer? x
))
3828 (local (setf (variable-possibly-integer? x
) nil
))
3829 (if (and (not (eq (variable-enumerated-domain x
) t
))
3830 (some #'integerp
(variable-enumerated-domain x
)))
3831 ;; note: Could do less consing if had LOCAL DELETE-IF.
3832 ;; This would also allow checking list only once.
3833 (set-enumerated-domain!
3834 x
(remove-if #'integerp
(variable-enumerated-domain x
))))
3837 (defun restrict-real! (x)
3838 ;; note: X must be a variable.
3839 (unless (or (variable-possibly-integer? x
)
3840 (variable-possibly-noninteger-real? x
))
3842 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3844 (when (variable-possibly-nonreal-number? x
)
3845 (local (setf (variable-possibly-nonreal-number? x
) nil
))
3847 (when (variable-possibly-boolean? x
)
3848 (local (setf (variable-possibly-boolean? x
) nil
))
3850 (when (variable-possibly-nonboolean-nonnumber? x
)
3851 (local (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
3854 (if (and (not (eq (variable-enumerated-domain x
) t
))
3855 (not (every #'realp
(variable-enumerated-domain x
))))
3856 ;; note: Could do less consing if had LOCAL DELETE-IF.
3857 ;; This would also allow checking list only once.
3858 (set-enumerated-domain!
3859 x
(remove-if-not #'realp
(variable-enumerated-domain x
))))
3860 (run-noticers x
)))))
3862 (defun restrict-nonreal! (x)
3863 ;; note: X must be a variable.
3864 (unless (or (variable-possibly-nonreal-number? x
)
3865 (variable-possibly-boolean? x
)
3866 (variable-possibly-nonboolean-nonnumber? x
))
3868 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3870 (when (variable-possibly-integer? x
)
3871 (local (setf (variable-possibly-integer? x
) nil
))
3873 (when (variable-possibly-noninteger-real? x
)
3874 (local (setf (variable-possibly-noninteger-real? x
) nil
))
3877 (if (and (not (eq (variable-enumerated-domain x
) t
))
3878 (some #'realp
(variable-enumerated-domain x
)))
3879 ;; note: Could do less consing if had LOCAL DELETE-IF.
3880 ;; This would also allow checking list only once.
3881 (set-enumerated-domain!
3882 x
(remove-if #'realp
(variable-enumerated-domain x
))))
3883 (run-noticers x
)))))
3885 (defun restrict-number! (x)
3886 ;; note: X must be a variable.
3887 (unless (or (variable-possibly-integer? x
)
3888 (variable-possibly-noninteger-real? x
)
3889 (variable-possibly-nonreal-number? x
))
3891 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3893 (when (variable-possibly-boolean? x
)
3894 (local (setf (variable-possibly-boolean? x
) nil
))
3896 (when (variable-possibly-nonboolean-nonnumber? x
)
3897 (local (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
3900 (if (and (not (eq (variable-enumerated-domain x
) t
))
3901 (not (every #'numberp
(variable-enumerated-domain x
))))
3902 ;; note: Could do less consing if had LOCAL DELETE-IF.
3903 ;; This would also allow checking list only once.
3904 (set-enumerated-domain!
3905 x
(remove-if-not #'numberp
(variable-enumerated-domain x
))))
3906 (run-noticers x
)))))
3908 (defun restrict-nonnumber! (x)
3909 ;; note: X must be a variable.
3910 (unless (or (variable-possibly-boolean? x
)
3911 (variable-possibly-nonboolean-nonnumber? x
))
3913 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3915 (when (variable-possibly-integer? x
)
3916 (local (setf (variable-possibly-integer? x
) nil
))
3918 (when (variable-possibly-noninteger-real? x
)
3919 (local (setf (variable-possibly-noninteger-real? x
) nil
))
3921 (when (variable-possibly-nonreal-number? x
)
3922 (local (setf (variable-possibly-nonreal-number? x
) nil
))
3925 (if (and (not (eq (variable-enumerated-domain x
) t
))
3926 (some #'numberp
(variable-enumerated-domain x
)))
3927 ;; note: Could do less consing if had LOCAL DELETE-IF.
3928 ;; This would also allow checking list only once.
3929 (set-enumerated-domain!
3930 x
(remove-if #'numberp
(variable-enumerated-domain x
))))
3931 (run-noticers x
)))))
3933 (defun restrict-boolean! (x)
3934 ;; note: X must be a variable.
3935 (unless (variable-possibly-boolean? x
) (fail))
3936 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3938 (when (variable-possibly-integer? x
)
3939 (local (setf (variable-possibly-integer? x
) nil
))
3941 (when (variable-possibly-noninteger-real? x
)
3942 (local (setf (variable-possibly-noninteger-real? x
) nil
))
3944 (when (variable-possibly-nonreal-number? x
)
3945 (local (setf (variable-possibly-nonreal-number? x
) nil
))
3947 (when (variable-possibly-nonboolean-nonnumber? x
)
3948 (local (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
3952 ((eq (variable-enumerated-domain x
) t
)
3955 ((member t
(variable-enumerated-antidomain x
) :test
#'eq
)
3956 (cond ((member nil
(variable-enumerated-antidomain x
) :test
#'eq
)
3958 (t (setf (variable-enumerated-domain x
) '(nil))
3959 (setf (variable-enumerated-antidomain x
) '())
3960 (setf (variable-value x
) nil
))))
3961 ((member nil
(variable-enumerated-antidomain x
) :test
#'eq
)
3962 (setf (variable-enumerated-domain x
) '(t))
3963 (setf (variable-enumerated-antidomain x
) '())
3964 (setf (variable-value x
) t
))
3965 (t (setf (variable-enumerated-domain x
) '(t nil
))
3966 (unless (null (variable-enumerated-antidomain x
))
3967 (setf (variable-enumerated-antidomain x
) '()))))))
3968 ((not (every #'booleanp
(variable-enumerated-domain x
)))
3969 ;; note: Could do less consing if had LOCAL DELETE-IF.
3970 ;; This would also allow checking list only once.
3971 (set-enumerated-domain!
3972 x
(remove-if-not #'booleanp
(variable-enumerated-domain x
)))))
3973 (run-noticers x
)))))
3975 (defun restrict-nonboolean! (x)
3976 ;; note: X must be a variable.
3977 (unless (or (variable-possibly-integer? x
)
3978 (variable-possibly-noninteger-real? x
)
3979 (variable-possibly-nonreal-number? x
)
3980 (variable-possibly-nonboolean-nonnumber? x
))
3982 (when (and (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
3983 (variable-possibly-boolean? x
))
3984 (local (setf (variable-possibly-boolean? x
) nil
))
3985 (cond ((eq (variable-enumerated-domain x
) t
)
3986 (local (setf (variable-enumerated-antidomain x
)
3988 (adjoin nil
(variable-enumerated-antidomain x
)
3991 ((some #'booleanp
(variable-enumerated-domain x
))
3992 ;; note: Could do less consing if had LOCAL DELETE-IF.
3993 ;; This would also allow checking list only once.
3994 (set-enumerated-domain!
3995 x
(remove-if #'booleanp
(variable-enumerated-domain x
)))))
3998 (defun restrict-lower-bound! (x lower-bound
)
3999 ;; note: X must be a variable.
4000 ;; note: LOWER-BOUND must be a real constant.
4001 (if (variable-integer? x
) (setf lower-bound
(ceiling lower-bound
)))
4002 (when (and (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
4003 (or (not (variable-lower-bound x
))
4004 (> lower-bound
(variable-lower-bound x
))))
4005 (if (and (variable-upper-bound x
) (< (variable-upper-bound x
) lower-bound
))
4007 (when (or (not (variable-lower-bound x
))
4008 (not (variable-upper-bound x
))
4009 (>= (/ (- lower-bound
(variable-lower-bound x
))
4010 (- (variable-upper-bound x
) (variable-lower-bound x
)))
4011 *minimum-shrink-ratio
*))
4012 (local (setf (variable-lower-bound x
) lower-bound
))
4013 (cond ((eq (variable-enumerated-domain x
) t
)
4014 (if (and lower-bound
4015 (variable-upper-bound x
)
4016 (variable-integer? x
)
4017 (or (null *maximum-discretization-range
*)
4018 (<= (- (variable-upper-bound x
) lower-bound
)
4019 *maximum-discretization-range
*)))
4020 (set-enumerated-domain!
4021 x
(all-values (an-integer-between lower-bound
4022 (variable-upper-bound x
))))))
4023 ((some #'(lambda (element) (< element lower-bound
))
4024 (variable-enumerated-domain x
))
4025 ;; note: Could do less consing if had LOCAL DELETE-IF.
4026 ;; This would also allow checking list only once.
4027 (set-enumerated-domain!
4028 x
(remove-if #'(lambda (element) (< element lower-bound
))
4029 (variable-enumerated-domain x
)))))
4032 (defun restrict-upper-bound! (x upper-bound
)
4033 ;; note: X must be a variable.
4034 ;; note: UPPER-BOUND must be a real constant.
4035 (when (variable-integer? x
)
4036 (setf upper-bound
(floor upper-bound
)))
4037 (when (and (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
4038 (or (not (variable-upper-bound x
))
4039 (< upper-bound
(variable-upper-bound x
))))
4040 (when (and (variable-lower-bound x
) (> (variable-lower-bound x
) upper-bound
))
4042 (when (or (not (variable-lower-bound x
))
4043 (not (variable-upper-bound x
))
4044 (>= (/ (- (variable-upper-bound x
) upper-bound
)
4045 (- (variable-upper-bound x
) (variable-lower-bound x
)))
4046 *minimum-shrink-ratio
*))
4047 (local (setf (variable-upper-bound x
) upper-bound
))
4048 (cond ((eq (variable-enumerated-domain x
) t
)
4049 (when (and (variable-lower-bound x
)
4051 (variable-integer? x
)
4052 (or (null *maximum-discretization-range
*)
4053 (<= (- upper-bound
(variable-lower-bound x
))
4054 *maximum-discretization-range
*)))
4055 (set-enumerated-domain!
4056 x
(all-values (an-integer-between (variable-lower-bound x
)
4058 ((some #'(lambda (element) (> element upper-bound
))
4059 (variable-enumerated-domain x
))
4060 ;; note: Could do less consing if had LOCAL DELETE-IF.
4061 ;; This would also allow checking list only once.
4062 (set-enumerated-domain!
4063 x
(remove-if #'(lambda (element) (> element upper-bound
))
4064 (variable-enumerated-domain x
)))))
4067 (defun restrict-bounds! (x lower-bound upper-bound
)
4068 ;; note: X must be a variable.
4069 ;; note: LOWER-BOUND and UPPER-BOUND must be real constants.
4070 (when (variable-integer? x
)
4071 (if lower-bound
(setf lower-bound
(ceiling lower-bound
)))
4072 (if upper-bound
(setf upper-bound
(floor upper-bound
))))
4073 (if (or (eq (variable-value x
) x
) (not (variable?
(variable-value x
))))
4075 (when (and lower-bound
4076 (or (not (variable-lower-bound x
))
4077 (> lower-bound
(variable-lower-bound x
))))
4078 (if (and (variable-upper-bound x
)
4079 (< (variable-upper-bound x
) lower-bound
))
4081 (when (or (not (variable-lower-bound x
))
4082 (not (variable-upper-bound x
))
4083 (>= (/ (- lower-bound
(variable-lower-bound x
))
4084 (- (variable-upper-bound x
) (variable-lower-bound x
)))
4085 *minimum-shrink-ratio
*))
4086 (local (setf (variable-lower-bound x
) lower-bound
))
4088 (when (and upper-bound
4089 (or (not (variable-upper-bound x
))
4090 (< upper-bound
(variable-upper-bound x
))))
4091 (if (and (variable-lower-bound x
)
4092 (> (variable-lower-bound x
) upper-bound
))
4094 (when (or (not (variable-lower-bound x
))
4095 (not (variable-upper-bound x
))
4096 (>= (/ (- (variable-upper-bound x
) upper-bound
)
4097 (- (variable-upper-bound x
) (variable-lower-bound x
)))
4098 *minimum-shrink-ratio
*))
4099 (local (setf (variable-upper-bound x
) upper-bound
))
4102 (cond ((eq (variable-enumerated-domain x
) t
)
4103 (if (and (variable-lower-bound x
)
4104 (variable-upper-bound x
)
4105 (variable-integer? x
)
4106 (or (null *maximum-discretization-range
*)
4107 (<= (- (variable-upper-bound x
)
4108 (variable-lower-bound x
))
4109 *maximum-discretization-range
*)))
4110 (set-enumerated-domain!
4111 x
(all-values (an-integer-between
4112 (variable-lower-bound x
)
4113 (variable-upper-bound x
))))))
4114 ((or (and lower-bound
4115 (some #'(lambda (element) (< element lower-bound
))
4116 (variable-enumerated-domain x
)))
4118 (some #'(lambda (element) (> element upper-bound
))
4119 (variable-enumerated-domain x
))))
4120 ;; note: Could do less consing if had LOCAL DELETE-IF.
4121 ;; This would also allow checking list only once.
4122 (set-enumerated-domain!
4123 x
(remove-if #'(lambda (element)
4124 (or (and lower-bound
(< element lower-bound
))
4125 (and upper-bound
(> element upper-bound
))))
4126 (variable-enumerated-domain x
)))))
4127 (run-noticers x
)))))
4130 ;; note: X and Y must be variables such that (EQ X (VALUE-OF X)) and
4131 ;; (EQ Y (VALUE-OF Y)).
4133 (y-lower-bound? nil
)
4134 (y-upper-bound? nil
)
4135 (x-lower-bound (variable-lower-bound x
))
4136 (x-upper-bound (variable-upper-bound x
))
4137 (y-lower-bound (variable-lower-bound y
))
4138 (y-upper-bound (variable-upper-bound y
)))
4139 (cond ((and (variable-integer? y
) (not (variable-integer? x
)))
4140 (if x-lower-bound
(setf x-lower-bound
(ceiling x-lower-bound
)))
4141 (if x-upper-bound
(setf x-upper-bound
(floor x-upper-bound
))))
4142 ((and (not (variable-integer? y
)) (variable-integer? x
))
4143 (when (and y-lower-bound
(not (integerp y-lower-bound
)))
4144 (setf y-lower-bound
(ceiling y-lower-bound
))
4145 (setf y-lower-bound? t
))
4146 (when (and y-upper-bound
(not (integerp y-upper-bound
)))
4147 (setf y-upper-bound
(floor y-upper-bound
))
4148 (setf y-upper-bound? t
))))
4149 (when (and (not (variable-possibly-integer? x
))
4150 (variable-possibly-integer? y
))
4151 (local (setf (variable-possibly-integer? y
) nil
))
4153 (when (and (not (variable-possibly-noninteger-real? x
))
4154 (variable-possibly-noninteger-real? y
))
4155 (local (setf (variable-possibly-noninteger-real? y
) nil
))
4157 (when (and (not (variable-possibly-nonreal-number? x
))
4158 (variable-possibly-nonreal-number? y
))
4159 (local (setf (variable-possibly-nonreal-number? y
) nil
))
4161 (when (and (not (variable-possibly-boolean? x
))
4162 (variable-possibly-boolean? y
))
4163 (local (setf (variable-possibly-boolean? y
) nil
))
4165 (when (and (not (variable-possibly-nonboolean-nonnumber? x
))
4166 (variable-possibly-nonboolean-nonnumber? y
))
4167 (local (setf (variable-possibly-nonboolean-nonnumber? y
) nil
))
4169 (unless (or (variable-possibly-integer? y
)
4170 (variable-possibly-noninteger-real? y
)
4171 (variable-possibly-nonreal-number? y
)
4172 (variable-possibly-boolean? y
)
4173 (variable-possibly-nonboolean-nonnumber? y
))
4175 (cond ((and x-lower-bound
4176 (or (not y-lower-bound
) (> x-lower-bound y-lower-bound
)))
4177 (local (setf (variable-lower-bound y
) x-lower-bound
))
4180 (local (setf (variable-lower-bound y
) y-lower-bound
))
4182 (cond ((and x-upper-bound
4183 (or (not y-upper-bound
) (< x-upper-bound y-upper-bound
)))
4184 (local (setf (variable-upper-bound y
) x-upper-bound
))
4187 (local (setf (variable-upper-bound y
) y-upper-bound
))
4189 (unless (or (null (variable-lower-bound y
))
4190 (null (variable-upper-bound y
))
4191 (< (variable-lower-bound y
) (variable-upper-bound y
)))
4194 (let ((lower-bound (variable-lower-bound y
))
4195 (upper-bound (variable-upper-bound y
)))
4196 (if (eq (variable-enumerated-domain y
) t
)
4197 (if (and lower-bound
4199 (variable-integer? y
)
4200 (or (null *maximum-discretization-range
*)
4201 (<= (- upper-bound lower-bound
)
4202 *maximum-discretization-range
*)))
4203 (set-enumerated-domain!
4204 y
(all-values (an-integer-between lower-bound upper-bound
))))
4207 (if (some #'(lambda (element)
4208 (or (< element lower-bound
)
4209 (> element upper-bound
)))
4210 (variable-enumerated-domain y
))
4211 ;; note: Could do less consing if had LOCAL DELETE-IF.
4212 ;; This would also allow checking list only once.
4213 (set-enumerated-domain!
4214 y
(remove-if #'(lambda (element)
4215 (or (< element lower-bound
)
4216 (> element upper-bound
)))
4217 (variable-enumerated-domain y
))))
4218 (if (some #'(lambda (element) (< element lower-bound
))
4219 (variable-enumerated-domain y
))
4220 ;; note: Could do less consing if had LOCAL DELETE-IF.
4221 ;; This would also allow checking list only once.
4222 (set-enumerated-domain!
4223 y
(remove-if #'(lambda (element)
4224 (< element lower-bound
))
4225 (variable-enumerated-domain y
)))))
4227 (if (some #'(lambda (element) (> element upper-bound
))
4228 (variable-enumerated-domain y
))
4229 ;; note: Could do less consing if had LOCAL DELETE-IF.
4230 ;; This would also allow checking list only once.
4231 (set-enumerated-domain!
4232 y
(remove-if #'(lambda (element)
4233 (> element upper-bound
))
4234 (variable-enumerated-domain y
)))))))))
4235 (local (let* ((enumerated-domain
4237 ((eq (variable-enumerated-domain x
) t
)
4238 (if (eq (variable-enumerated-domain y
) t
)
4240 (set-difference (variable-enumerated-domain y
)
4241 (variable-enumerated-antidomain x
)
4243 ((eq (variable-enumerated-domain y
) t
)
4244 (set-difference (variable-enumerated-domain x
)
4245 (variable-enumerated-antidomain y
)
4247 (t (intersection (variable-enumerated-domain x
)
4248 (variable-enumerated-domain y
)
4250 (enumerated-antidomain
4251 (if (eq enumerated-domain t
)
4252 (union (variable-enumerated-antidomain x
)
4253 (variable-enumerated-antidomain y
)
4256 (if (null enumerated-domain
) (fail))
4257 (if (and (not (eq enumerated-domain t
))
4258 (or (eq (variable-enumerated-domain y
) t
)
4259 (< (length enumerated-domain
)
4260 (length (variable-enumerated-domain y
)))))
4261 (setf (variable-enumerated-domain y
) enumerated-domain
))
4262 (if (if (eq enumerated-domain t
)
4263 (> (length enumerated-antidomain
)
4264 (length (variable-enumerated-antidomain y
)))
4265 (not (null (variable-enumerated-antidomain y
))))
4266 (setf (variable-enumerated-antidomain y
) enumerated-antidomain
)))
4267 (setf (variable-noticers y
)
4268 (append (variable-noticers y
) (variable-noticers x
)))
4269 (setf (variable-noticers x
) '())
4270 (setf (variable-value x
) y
))
4273 (defun restrict-value! (x value
)
4274 ;; note: X must be a variable such that (EQ X (VALUE-OF X)).
4275 ;; note: VALUE must not be a variable.
4276 (if (occurs-in? x value
) (fail))
4278 (integer (unless (variable-possibly-integer? x
) (fail)))
4279 (real (unless (variable-possibly-noninteger-real? x
) (fail)))
4280 (number (unless (variable-possibly-nonreal-number? x
) (fail)))
4281 (boolean (unless (variable-possibly-boolean? x
) (fail)))
4282 (otherwise (unless (variable-possibly-nonboolean-nonnumber? x
) (fail))))
4283 ;; needs work: This is sound only if VALUE does not contain any variables.
4284 (if (eq (variable-enumerated-domain x
) t
)
4285 (if (member value
(variable-enumerated-antidomain x
) :test
#'equal
)
4287 (unless (member value
(variable-enumerated-domain x
) :test
#'equal
)
4289 (if (and (realp value
)
4290 (or (and (variable-lower-bound x
)
4291 (< value
(variable-lower-bound x
)))
4292 (and (variable-upper-bound x
)
4293 (> value
(variable-upper-bound x
)))))
4295 (local (setf (variable-value x
) value
)
4297 (integer (if (variable-possibly-noninteger-real? x
)
4298 (setf (variable-possibly-noninteger-real? x
) nil
))
4299 (if (variable-possibly-nonreal-number? x
)
4300 (setf (variable-possibly-nonreal-number? x
) nil
))
4301 (if (variable-possibly-boolean? x
)
4302 (setf (variable-possibly-boolean? x
) nil
))
4303 (if (variable-possibly-nonboolean-nonnumber? x
)
4304 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
4305 (if (or (null (variable-lower-bound x
))
4306 (not (integerp (variable-lower-bound x
)))
4307 (> value
(variable-lower-bound x
)))
4308 (setf (variable-lower-bound x
) value
))
4309 (if (or (null (variable-upper-bound x
))
4310 (not (integerp (variable-upper-bound x
)))
4311 (< value
(variable-upper-bound x
)))
4312 (setf (variable-upper-bound x
) value
)))
4313 (real (if (variable-possibly-integer? x
)
4314 (setf (variable-possibly-integer? x
) nil
))
4315 (if (variable-possibly-nonreal-number? x
)
4316 (setf (variable-possibly-nonreal-number? x
) nil
))
4317 (if (variable-possibly-boolean? x
)
4318 (setf (variable-possibly-boolean? x
) nil
))
4319 (if (variable-possibly-nonboolean-nonnumber? x
)
4320 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
4321 (if (or (null (variable-lower-bound x
))
4322 (> value
(variable-lower-bound x
)))
4323 (setf (variable-lower-bound x
) value
))
4324 (if (or (null (variable-upper-bound x
))
4325 (< value
(variable-upper-bound x
)))
4326 (setf (variable-upper-bound x
) value
)))
4327 (number (if (variable-possibly-integer? x
)
4328 (setf (variable-possibly-integer? x
) nil
))
4329 (if (variable-possibly-noninteger-real? x
)
4330 (setf (variable-possibly-noninteger-real? x
) nil
))
4331 (if (variable-possibly-boolean? x
)
4332 (setf (variable-possibly-boolean? x
) nil
))
4333 (if (variable-possibly-nonboolean-nonnumber? x
)
4334 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
)))
4335 (boolean (if (variable-possibly-integer? x
)
4336 (setf (variable-possibly-integer? x
) nil
))
4337 (if (variable-possibly-noninteger-real? x
)
4338 (setf (variable-possibly-noninteger-real? x
) nil
))
4339 (if (variable-possibly-nonreal-number? x
)
4340 (setf (variable-possibly-nonreal-number? x
) nil
))
4341 (if (variable-possibly-nonboolean-nonnumber? x
)
4342 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
)))
4343 (otherwise (if (variable-possibly-integer? x
)
4344 (setf (variable-possibly-integer? x
) nil
))
4345 (if (variable-possibly-noninteger-real? x
)
4346 (setf (variable-possibly-noninteger-real? x
) nil
))
4347 (if (variable-possibly-nonreal-number? x
)
4348 (setf (variable-possibly-nonreal-number? x
) nil
))
4349 (if (variable-possibly-boolean? x
)
4350 (setf (variable-possibly-boolean? x
) nil
))))
4351 (cond ((eq (variable-enumerated-domain x
) t
)
4352 ;; needs work: This is sound only if VALUE does not contain any
4354 (setf (variable-enumerated-domain x
) (list value
))
4355 (setf (variable-enumerated-antidomain x
) '()))
4356 ((not (null (rest (variable-enumerated-domain x
))))
4357 ;; needs work: This is sound only if VALUE does not contain any
4359 (setf (variable-enumerated-domain x
) (list value
)))))
4362 (defun restrict-true! (x)
4363 ;; note: X must be a Boolean variable.
4364 (if (eq (variable-value x
) nil
) (fail))
4365 (when (eq (variable-value x
) x
)
4366 (local (setf (variable-value x
) t
)
4367 (setf (variable-enumerated-domain x
) '(t)))
4370 (defun restrict-false! (x)
4371 ;; note: X must be a Boolean variable.
4372 (if (eq (variable-value x
) t
) (fail))
4373 (when (eq (variable-value x
) x
)
4374 (local (setf (variable-value x
) nil
)
4375 (setf (variable-enumerated-domain x
) '(nil)))
4378 (defun set-enumerated-domain! (x enumerated-domain
)
4379 ;; note: X must be a variable such that (EQ X (VALUE-OF X)).
4380 ;; note: All callers must insure that the new ENUMERATED-DOMAIN is a subset
4382 (if (null enumerated-domain
) (fail))
4385 ((eq (variable-enumerated-domain x
) t
)
4386 (setf (variable-enumerated-domain x
) enumerated-domain
)
4387 (unless (null (variable-enumerated-antidomain x
))
4388 (setf (variable-enumerated-antidomain x
) '()))
4389 (if (and (variable-possibly-boolean? x
)
4390 (not (some #'booleanp enumerated-domain
)))
4391 (setf (variable-possibly-boolean? x
) nil
))
4392 (if (and (variable-possibly-nonboolean-nonnumber? x
)
4393 (not (some #'(lambda (x)
4394 (and (not (booleanp x
)) (not (numberp x
))))
4395 enumerated-domain
)))
4396 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
4397 (if (and (variable-possibly-nonreal-number? x
)
4398 (not (some #'(lambda (x) (and (not (realp x
)) (numberp x
)))
4399 enumerated-domain
)))
4400 (setf (variable-possibly-nonreal-number? x
) nil
))
4401 (if (and (variable-possibly-noninteger-real? x
)
4402 (not (some #'(lambda (x) (and (not (integerp x
)) (realp x
)))
4403 enumerated-domain
)))
4404 (setf (variable-possibly-noninteger-real? x
) nil
))
4405 (if (and (variable-possibly-integer? x
)
4406 (not (some #'integerp enumerated-domain
)))
4407 (setf (variable-possibly-integer? x
) nil
))
4408 (if (variable-real? x
)
4409 (let ((lower-bound (reduce #'min enumerated-domain
))
4410 (upper-bound (reduce #'max enumerated-domain
)))
4411 (if (or (null (variable-lower-bound x
))
4412 (> lower-bound
(variable-lower-bound x
)))
4413 (setf (variable-lower-bound x
) lower-bound
))
4414 (if (or (null (variable-upper-bound x
))
4415 (< upper-bound
(variable-upper-bound x
)))
4416 (setf (variable-upper-bound x
) upper-bound
))))
4417 (if (null (rest enumerated-domain
))
4418 (setf (variable-value x
) (first enumerated-domain
)))
4420 ((< (length enumerated-domain
) (length (variable-enumerated-domain x
)))
4421 (setf (variable-enumerated-domain x
) enumerated-domain
)
4422 (if (and (variable-possibly-boolean? x
)
4423 (not (some #'booleanp enumerated-domain
)))
4424 (setf (variable-possibly-boolean? x
) nil
))
4425 (if (and (variable-possibly-nonboolean-nonnumber? x
)
4426 (not (some #'(lambda (x)
4427 (and (not (booleanp x
)) (not (numberp x
))))
4428 enumerated-domain
)))
4429 (setf (variable-possibly-nonboolean-nonnumber? x
) nil
))
4430 (if (and (variable-possibly-nonreal-number? x
)
4431 (not (some #'(lambda (x) (and (not (realp x
)) (numberp x
)))
4432 enumerated-domain
)))
4433 (setf (variable-possibly-nonreal-number? x
) nil
))
4434 (if (and (variable-possibly-noninteger-real? x
)
4435 (not (some #'(lambda (x) (and (not (integerp x
)) (realp x
)))
4436 enumerated-domain
)))
4437 (setf (variable-possibly-noninteger-real? x
) nil
))
4438 (if (and (variable-possibly-integer? x
)
4439 (not (some #'integerp enumerated-domain
)))
4440 (setf (variable-possibly-integer? x
) nil
))
4441 (if (variable-real? x
)
4442 (let ((lower-bound (reduce #'min enumerated-domain
))
4443 (upper-bound (reduce #'max enumerated-domain
)))
4444 (if (or (null (variable-lower-bound x
))
4445 (> lower-bound
(variable-lower-bound x
)))
4446 (setf (variable-lower-bound x
) lower-bound
))
4447 (if (or (null (variable-upper-bound x
))
4448 (< upper-bound
(variable-upper-bound x
)))
4449 (setf (variable-upper-bound x
) upper-bound
))))
4450 (if (null (rest enumerated-domain
))
4451 (setf (variable-value x
) (first enumerated-domain
)))
4455 (defun restrict-enumerated-domain! (x enumerated-domain
)
4456 ;; note: X must be a variable such that (EQ X (VALUE-OF X)).
4457 ;; note: ENUMERATED-DOMAIN must not be a variable.
4458 (unless (typep enumerated-domain
'sequence
) (fail))
4459 (when (every #'ground? enumerated-domain
)
4460 (setf enumerated-domain
4461 (remove-duplicates (map 'list
#'eliminate-variables enumerated-domain
)
4463 (unless (variable-possibly-boolean? x
)
4464 (setf enumerated-domain
(remove-if #'booleanp enumerated-domain
)))
4465 (unless (variable-possibly-nonboolean-nonnumber? x
)
4466 (setf enumerated-domain
4467 (remove-if #'(lambda (x) (and (not (booleanp x
)) (not (numberp x
))))
4468 enumerated-domain
)))
4469 (unless (variable-possibly-nonreal-number? x
)
4470 (setf enumerated-domain
4471 (remove-if #'(lambda (x) (and (not (realp x
)) (numberp x
)))
4472 enumerated-domain
)))
4473 (unless (variable-possibly-noninteger-real? x
)
4474 (setf enumerated-domain
4475 (remove-if #'(lambda (x) (and (not (integerp x
)) (realp x
)))
4476 enumerated-domain
)))
4477 (unless (variable-possibly-integer? x
)
4478 (setf enumerated-domain
(remove-if #'integerp enumerated-domain
)))
4479 (if (variable-upper-bound x
)
4480 (let ((upper-bound (variable-upper-bound x
)))
4481 (setf enumerated-domain
4482 (remove-if #'(lambda (element) (> element upper-bound
))
4483 enumerated-domain
))))
4484 (if (variable-lower-bound x
)
4485 (let ((lower-bound (variable-lower-bound x
)))
4486 (setf enumerated-domain
4487 (remove-if #'(lambda (element) (< element lower-bound
))
4488 enumerated-domain
))))
4489 (setf enumerated-domain
4490 (if (eq (variable-enumerated-domain x
) t
)
4491 (set-difference enumerated-domain
4492 (variable-enumerated-antidomain x
)
4494 (intersection (variable-enumerated-domain x
) enumerated-domain
4496 (if (set-enumerated-domain! x enumerated-domain
) (run-noticers x
))))
4498 (defun restrict-enumerated-antidomain! (x enumerated-antidomain
)
4499 ;; note: X must be a variable such that (EQ X (VALUE-OF X)).
4500 ;; note: ENUMERATED-ANTIDOMAIN must not be a variable.
4501 (unless (typep enumerated-antidomain
'sequence
) (fail))
4502 (when (every #'ground? enumerated-antidomain
)
4503 (setf enumerated-antidomain
4505 (map 'list
#'eliminate-variables enumerated-antidomain
)
4508 ((eq (variable-enumerated-domain x
) t
)
4509 (setf enumerated-antidomain
4510 (union (variable-enumerated-antidomain x
) enumerated-antidomain
4512 (when (> (length enumerated-antidomain
)
4513 (length (variable-enumerated-antidomain x
)))
4514 (local (setf (variable-enumerated-antidomain x
) enumerated-antidomain
))
4516 ((set-enumerated-domain!
4517 x
(set-difference (variable-enumerated-domain x
) enumerated-antidomain
4519 (run-noticers x
)))))
4523 (defun +-rule-up
(z x y
)
4524 (if (and (variable-integer? x
) (variable-integer? y
)) (restrict-integer! z
))
4525 ;; note: We can't assert that Z in not an integer when either X or Y are not
4526 ;; integers since they may be Gaussian integers. But we can if either
4527 ;; X or Y is real. If the Screamer type system could distinguish
4528 ;; Gaussian integers from other complex numbers we could whenever X or
4529 ;; Y was not a Gaussian integer.
4530 (if (and (or (variable-noninteger? x
) (variable-noninteger? y
))
4531 (or (variable-real? x
) (variable-real? y
)))
4532 (restrict-noninteger! z
))
4533 (if (and (variable-real? x
) (variable-real? y
)) (restrict-real! z
))
4535 (if (and (or (variable-nonreal? x
) (variable-nonreal? y
))
4536 (or (variable-real? x
) (variable-real? y
)))
4537 (restrict-nonreal! z
))
4538 (if (and (variable-real? x
) (variable-real? y
) (variable-real? z
))
4541 (infinity-+ (variable-lower-bound x
) (variable-lower-bound y
))
4542 (infinity-+ (variable-upper-bound x
) (variable-upper-bound y
))))
4543 (let ((x (value-of x
))
4546 (if (and (not (variable? x
))
4552 (defun +-rule-down
(z x y
)
4553 ;; note: We can't assert that X and Y are integers when Z is an integer since
4554 ;; Z may be an integer when X and Y are Gaussian integers. But we can
4555 ;; make such an assertion if either X or Y is real. If the Screamer
4556 ;; type system could distinguish Gaussian integers from other complex
4557 ;; numbers we could make such an assertion whenever either X or Y was
4558 ;; not a Gaussian integer.
4559 (if (and (variable-integer? z
) (or (variable-real? x
) (variable-real? y
)))
4560 (restrict-integer! x
))
4562 (if (and (variable-real? z
) (or (variable-real? x
) (variable-real? y
)))
4564 (if (and (variable-real? x
) (variable-real? y
) (variable-real? z
))
4567 (infinity-- (variable-lower-bound z
) (variable-upper-bound y
))
4568 (infinity-- (variable-upper-bound z
) (variable-lower-bound y
))))
4569 (let ((x (value-of x
))
4572 (if (and (not (variable? x
))
4578 (defun /-rule
(z x y
)
4579 (when (and (variable-lower-bound x
) (plusp (variable-lower-bound x
)))
4580 (cond ((and (variable-upper-bound x
) (not (zerop (variable-upper-bound x
))))
4581 (if (variable-lower-bound z
)
4583 ((minusp (variable-lower-bound z
))
4584 (restrict-lower-bound!
4585 y
(/ (variable-lower-bound z
) (variable-lower-bound x
))))
4586 (t (restrict-lower-bound! y
0)
4587 (restrict-lower-bound!
4588 y
(/ (variable-lower-bound z
) (variable-upper-bound x
))))))
4589 (if (variable-upper-bound z
)
4591 ((plusp (variable-upper-bound z
))
4592 (restrict-upper-bound!
4593 y
(/ (variable-upper-bound z
) (variable-lower-bound x
))))
4594 (t (restrict-upper-bound! y
0)
4595 (restrict-upper-bound!
4596 y
(/ (variable-upper-bound z
) (variable-upper-bound x
)))))))
4597 (t (if (variable-lower-bound z
)
4599 ((minusp (variable-lower-bound z
))
4600 (restrict-lower-bound!
4601 y
(/ (variable-lower-bound z
) (variable-lower-bound x
))))
4602 (t (restrict-lower-bound! y
0))))
4603 (if (variable-upper-bound z
)
4605 ((plusp (variable-upper-bound z
))
4606 (restrict-upper-bound!
4607 y
(/ (variable-upper-bound z
) (variable-lower-bound x
))))
4608 (t (restrict-upper-bound! y
0)))))))
4609 (when (and (variable-upper-bound x
) (minusp (variable-upper-bound x
)))
4610 (cond ((and (variable-lower-bound x
) (not (zerop (variable-lower-bound x
))))
4611 (if (variable-upper-bound z
)
4613 ((plusp (variable-upper-bound z
))
4614 (restrict-lower-bound!
4615 y
(/ (variable-upper-bound z
) (variable-upper-bound x
))))
4616 (t (restrict-lower-bound! y
0)
4617 (restrict-lower-bound!
4618 y
(/ (variable-upper-bound z
) (variable-lower-bound x
))))))
4619 (if (variable-lower-bound z
)
4621 ((minusp (variable-lower-bound z
))
4622 (restrict-upper-bound!
4623 y
(/ (variable-lower-bound z
) (variable-upper-bound x
))))
4624 (t (restrict-upper-bound! y
0)
4625 (restrict-upper-bound!
4626 y
(/ (variable-lower-bound z
) (variable-lower-bound x
)))))))
4627 (t (if (variable-upper-bound z
)
4629 ((plusp (variable-upper-bound z
))
4630 (restrict-lower-bound!
4631 y
(/ (variable-upper-bound z
) (variable-upper-bound x
))))
4632 (t (restrict-lower-bound! y
0))))
4633 (if (variable-lower-bound z
)
4635 ((minusp (variable-lower-bound z
))
4636 (restrict-upper-bound!
4637 y
(/ (variable-lower-bound z
) (variable-upper-bound x
))))
4638 (t (restrict-upper-bound! y
0))))))))
4640 (defun *-rule-up
(z x y
)
4641 (if (and (variable-integer? x
) (variable-integer? y
)) (restrict-integer! z
))
4642 ;; note: We can't assert that Z in not an integer when either X or Y are not
4643 ;; integers since they may be Gaussian integers. But we can if either
4644 ;; X or Y is real. If the Screamer type system could distinguish
4645 ;; Gaussian integers from other complex numbers we could whenever X or
4646 ;; Y was not a Gaussian integer.
4647 (if (and (or (variable-noninteger? x
) (variable-noninteger? y
))
4648 (or (variable-real? x
) (variable-real? y
)))
4649 (restrict-noninteger! z
))
4650 (if (and (variable-real? x
) (variable-real? y
)) (restrict-real! z
))
4652 (if (and (or (variable-nonreal? x
) (variable-nonreal? y
))
4653 (or (variable-real? x
) (variable-real? y
)))
4654 (restrict-nonreal! z
))
4655 (if (and (variable-real? x
) (variable-real? y
) (variable-real? z
))
4656 ;; note: Can sometimes do better than the following even when ranges are
4661 (infinity-* (variable-lower-bound x
) (variable-lower-bound y
))
4663 (infinity-* (variable-lower-bound x
) (variable-upper-bound y
))
4665 (infinity-* (variable-upper-bound x
) (variable-lower-bound y
))
4666 (infinity-* (variable-upper-bound x
) (variable-upper-bound y
)))))
4668 (infinity-* (variable-lower-bound x
) (variable-lower-bound y
))
4670 (infinity-* (variable-lower-bound x
) (variable-upper-bound y
))
4672 (infinity-* (variable-upper-bound x
) (variable-lower-bound y
))
4673 (infinity-* (variable-upper-bound x
) (variable-upper-bound y
)))))))
4674 (let ((x (value-of x
))
4677 (if (and (not (variable? x
))
4683 (defun *-rule-down
(z x y
)
4684 ;; note: We can't assert that X and Y are integers when Z is an integer since
4685 ;; Z may be an integer when X and Y are Gaussian integers. But we can
4686 ;; make such an assertion if either X or Y is real. If the Screamer
4687 ;; type system could distinguish Gaussian integers from other complex
4688 ;; numbers we could make such an assertion whenever either X or Y was
4689 ;; not a Gaussian integer.
4690 (if (and (variable-integer? z
) (or (variable-real? x
) (variable-real? y
)))
4691 (restrict-integer! x
))
4693 (if (and (variable-real? z
) (or (variable-real? x
) (variable-real? y
)))
4695 (if (and (variable-real? x
) (variable-real? y
) (variable-real? z
))
4697 (let ((x (value-of x
))
4700 (if (and (not (variable? x
))
4706 (defun min-rule-up (z x y
)
4707 (if (and (variable-integer? x
) (variable-integer? y
)) (restrict-integer! z
))
4710 (infinity-min (variable-lower-bound x
) (variable-lower-bound y
))
4711 (if (variable-upper-bound x
)
4712 (if (variable-upper-bound y
)
4713 (min (variable-upper-bound x
) (variable-upper-bound y
))
4714 (variable-upper-bound x
))
4715 (variable-upper-bound y
)))
4716 (let ((x (value-of x
))
4719 (if (and (not (variable? z
))
4725 (defun min-rule-down (z x y
)
4726 ;; note: The analog of the following for upper bounds, namely restricting
4727 ;; the upper bound of either X or Y to (VARIABLE-UPPER-BOUND Z) is
4728 ;; nondeterministic.
4729 (if (variable-lower-bound z
)
4730 (restrict-lower-bound! x
(variable-lower-bound z
)))
4731 (let ((x (value-of x
))
4734 (if (and (not (variable? z
))
4740 (defun max-rule-up (z x y
)
4741 (if (and (variable-integer? x
) (variable-integer? y
)) (restrict-integer! z
))
4744 (if (variable-lower-bound x
)
4745 (if (variable-lower-bound y
)
4746 (max (variable-lower-bound x
) (variable-lower-bound y
))
4747 (variable-lower-bound x
))
4748 (variable-lower-bound y
))
4749 (infinity-max (variable-upper-bound x
) (variable-upper-bound y
)))
4750 (let ((x (value-of x
))
4753 (if (and (not (variable? z
))
4759 (defun max-rule-down (z x y
)
4760 ;; note: The analog of the following for lower bounds, namely restricting
4761 ;; the lower bound of either X or Y to (VARIABLE-LOWER-BOUND Z) is
4762 ;; nondeterministic.
4763 (if (variable-upper-bound z
)
4764 (restrict-upper-bound! x
(variable-upper-bound z
)))
4765 (let ((x (value-of x
))
4768 (if (and (not (variable? z
))
4776 ;; note: I forget why +-RULE *-RULE MIN-RULE and MAX-RULE must perform the
4777 ;; check in the second COND clause irrespective of whether the first
4778 ;; clause is executed.
4779 ((and (variable-real? x
) (variable-real? y
))
4780 (restrict-bounds! x
(variable-lower-bound y
) (variable-upper-bound y
))
4781 (restrict-bounds! y
(variable-lower-bound x
) (variable-upper-bound x
)))
4782 ((and (not (variable? x
)) (not (variable? y
)) (/= x y
)) (fail))))
4784 (defun <=-rule
(x y
)
4785 (if (variable-lower-bound x
)
4786 (restrict-lower-bound! y
(variable-lower-bound x
)))
4787 (if (variable-upper-bound y
)
4788 (restrict-upper-bound! x
(variable-upper-bound y
))))
4791 (if (variable-lower-bound x
)
4792 (restrict-lower-bound! y
(if (variable-integer? y
)
4793 (1+ (floor (variable-lower-bound x
)))
4794 (variable-lower-bound x
))))
4795 (if (variable-upper-bound y
)
4796 (restrict-upper-bound! x
(if (variable-integer? x
)
4797 (1- (ceiling (variable-upper-bound y
)))
4798 (variable-upper-bound y
))))
4799 (let ((x (value-of x
))
4801 (if (and (not (variable? x
)) (not (variable? y
)) (>= x y
)) (fail))))
4803 (defun /=-rule
(x y
)
4804 ;; note: Got rid of the nondeterministic version of /=-RULE.
4805 (let ((x (value-of x
))
4807 (if (and (not (variable? x
)) (not (variable? y
)) (= x y
)) (fail))))
4809 ;;; Lifted Arithmetic Functions (Two argument optimized)
4812 (assert!-numberpv x
)
4813 (assert!-numberpv y
)
4814 ;; needs work: The first two optimizations below violate CommonLisp type
4815 ;; propagation conventions.
4816 (cond ((and (bound? x
) (zerop (value-of x
))) (value-of y
))
4817 ((and (bound? y
) (zerop (value-of y
))) (value-of x
))
4818 ((and (bound? x
) (bound? y
)) (+ (value-of x
) (value-of y
)))
4819 (t (let ((x (variablize x
))
4823 #'(lambda () (+-rule-up z x y
) (+-rule-down z y x
)) x
)
4825 #'(lambda () (+-rule-up z x y
) (+-rule-down z x y
)) y
)
4827 #'(lambda () (+-rule-down z x y
) (+-rule-down z y x
)) z
)
4831 (assert!-numberpv x
)
4832 (assert!-numberpv y
)
4833 ;; needs work: The first optimization below violates CommonLisp type
4834 ;; propagation conventions.
4835 (cond ((and (bound? y
) (zerop (value-of y
))) (value-of x
))
4836 ((and (bound? x
) (bound? y
)) (- (value-of x
) (value-of y
)))
4837 (t (let ((x (variablize x
))
4841 #'(lambda () (+-rule-down x y z
) (+-rule-down x z y
)) x
)
4843 #'(lambda () (+-rule-up x y z
) (+-rule-down x z y
)) y
)
4845 #'(lambda () (+-rule-up x y z
) (+-rule-down x y z
)) z
)
4849 (assert!-numberpv x
)
4850 (assert!-numberpv y
)
4851 ;; needs work: The first four optimizations below violate CommonLisp type
4852 ;; propagation conventions.
4853 (cond ((and (bound? x
) (zerop (value-of x
))) 0)
4854 ((and (bound? y
) (zerop (value-of y
))) 0)
4855 ((and (bound? x
) (= (value-of x
) 1)) (value-of y
))
4856 ((and (bound? y
) (= (value-of y
) 1)) (value-of x
))
4857 ((and (bound? x
) (bound? y
)) (* (value-of x
) (value-of y
)))
4858 (t (let ((x (variablize x
))
4862 #'(lambda () (*-rule-up z x y
) (*-rule-down z y x
)) x
)
4864 #'(lambda () (*-rule-up z x y
) (*-rule-down z x y
)) y
)
4866 #'(lambda () (*-rule-down z x y
) (*-rule-down z y x
)) z
)
4870 (assert!-numberpv x
)
4871 (assert!-numberpv y
)
4872 ;; needs work: The first three optimizations below violate CommonLisp type
4873 ;; propagation conventions.
4874 (cond ((and (bound? x
) (zerop (value-of x
))) 0)
4875 ((and (bound? y
) (zerop (value-of y
))) (fail))
4876 ((and (bound? y
) (= (value-of y
) 1)) (value-of x
))
4877 ((and (bound? x
) (bound? y
)) (/ (value-of x
) (value-of y
)))
4878 (t (let ((x (variablize x
))
4882 #'(lambda () (*-rule-down x y z
) (*-rule-down x z y
)) x
)
4884 #'(lambda () (*-rule-up x y z
) (*-rule-down x z y
)) y
)
4886 #'(lambda () (*-rule-up x y z
) (*-rule-down x y z
)) z
)
4892 (cond ((known?-
<=v2-internal x y
) (value-of x
))
4893 ((known?-
<=v2-internal y x
) (value-of y
))
4894 (t (let ((x (variablize x
))
4898 #'(lambda () (min-rule-up z x y
) (min-rule-down z y x
)) x
)
4900 #'(lambda () (min-rule-up z x y
) (min-rule-down z x y
)) y
)
4902 #'(lambda () (min-rule-down z x y
) (min-rule-down z y x
)) z
)
4908 (cond ((known?-
<=v2-internal y x
) (value-of x
))
4909 ((known?-
<=v2-internal x y
) (value-of y
))
4910 (t (let ((x (variablize x
))
4914 #'(lambda () (max-rule-up z x y
) (max-rule-down z y x
)) x
)
4916 #'(lambda () (max-rule-up z x y
) (max-rule-down z x y
)) y
)
4918 #'(lambda () (max-rule-down z x y
) (max-rule-down z y x
)) z
)
4921 ;;; Lifted Type Functions (KNOWN? optimized)
4923 (defun known?-integerpv
(x)
4924 (let ((x (value-of x
)))
4927 (variable (variable-integer? x
))
4930 (defun known?-notv-integerpv
(x)
4931 (let ((x (value-of x
)))
4934 (variable (variable-noninteger? x
))
4937 (defun known?-realpv
(x)
4938 (let ((x (value-of x
)))
4941 (variable (variable-real? x
))
4944 (defun known?-notv-realpv
(x)
4945 (let ((x (value-of x
)))
4948 (variable (variable-nonreal? x
))
4951 (defun known?-numberpv
(x)
4952 (let ((x (value-of x
)))
4955 (variable (variable-number? x
))
4958 (defun known?-notv-numberpv
(x)
4959 (let ((x (value-of x
)))
4962 (variable (variable-nonnumber? x
))
4965 (defun known?-booleanpv
(x)
4966 (let ((x (value-of x
)))
4969 (variable (variable-boolean? x
))
4972 (defun known?-notv-booleanpv
(x)
4973 (let ((x (value-of x
)))
4976 (variable (variable-nonboolean? x
))
4979 ;;; Lifted Arithmetic Comparison Functions (Two argument KNOWN? optimized)
4981 (defun known?-
<=v2-variable
(x y
)
4982 (and (variable-upper-bound x
)
4983 (variable-lower-bound y
)
4984 (<= (variable-upper-bound x
) (variable-lower-bound y
))))
4986 (defun known?-
<v2-variable
(x y
)
4987 (and (variable-upper-bound x
)
4988 (variable-lower-bound y
)
4989 (< (variable-upper-bound x
) (variable-lower-bound y
))))
4991 (defun known?-
=v2-variable
(x y
)
4992 (or (and (variable-real? x
)
4994 (known?-
<=v2-variable x y
)
4995 (known?-
<=v2-variable y x
))
4996 (and (not (eq x
(variable-value x
)))
4997 (not (eq y
(variable-value y
)))
4998 (= (variable-value x
) (variable-value y
)))))
5000 (defun known?-
/=v2-variable
(x y
)
5001 (or (and (variable-real? x
)
5003 (or (known?-
<v2-variable x y
) (known?-
<v2-variable y x
)))
5004 (and (not (eq x
(variable-value x
)))
5005 (not (eq y
(variable-value y
)))
5006 (/= (variable-value x
) (variable-value y
)))))
5008 (defun known?-
=v2-internal
(x y
)
5009 (known?-
=v2-variable
(variablize x
) (variablize y
)))
5011 (defun known?-
<=v2-internal
(x y
)
5012 (known?-
<=v2-variable
(variablize x
) (variablize y
)))
5014 (defun known?-
<v2-internal
(x y
)
5015 (known?-
<v2-variable
(variablize x
) (variablize y
)))
5017 (defun known?-
/=v2-internal
(x y
)
5018 (known?-
/=v2-variable
(variablize x
) (variablize y
)))
5020 (defun known?-
=v2
(x y
)
5021 (assert!-numberpv x
)
5022 (assert!-numberpv y
)
5023 (known?-
=v2-internal x y
))
5025 (defun known?-
<=v2
(x y
)
5028 (known?-
<=v2-internal x y
))
5030 (defun known?-
<v2
(x y
)
5033 (known?-
<v2-internal x y
))
5035 (defun known?-
/=v2
(x y
)
5036 (assert!-numberpv x
)
5037 (assert!-numberpv y
)
5038 (known?-
/=v2-internal x y
))
5040 ;;; Lifted Type Functions (ASSERT! optimized)
5042 (defun assert!-integerpv
(x)
5043 (let ((x (value-of x
)))
5046 (variable (restrict-integer! x
))
5047 (otherwise (fail)))))
5049 (defun assert!-notv-integerpv
(x)
5050 (let ((x (value-of x
)))
5053 (variable (restrict-noninteger! x
))
5056 (defun assert!-realpv
(x)
5057 (let ((x (value-of x
)))
5060 (variable (restrict-real! x
))
5061 (otherwise (fail)))))
5063 (defun assert!-notv-realpv
(x)
5064 (let ((x (value-of x
)))
5067 (variable (restrict-nonreal! x
))
5070 (defun assert!-numberpv
(x)
5071 (let ((x (value-of x
)))
5074 (variable (restrict-number! x
))
5075 (otherwise (fail)))))
5077 (defun assert!-notv-numberpv
(x)
5078 (let ((x (value-of x
)))
5081 (variable (restrict-nonnumber! x
))
5084 (defun assert!-booleanpv
(x)
5085 (let ((x (value-of x
)))
5088 (variable (restrict-boolean! x
))
5089 (otherwise (fail)))))
5091 (defun assert!-notv-booleanpv
(x)
5092 (let ((x (value-of x
)))
5095 (variable (restrict-nonboolean! x
))
5098 ;;; Lifted Arithmetic Comparison Functions (Two argument ASSERT! optimized)
5100 (defun assert!-
=v2
(x y
)
5101 (assert!-numberpv x
)
5102 (assert!-numberpv y
)
5103 (let ((x (variablize x
))
5105 (attach-noticer! #'(lambda () (=-rule x y
)) x
)
5106 (attach-noticer! #'(lambda () (=-rule x y
)) y
)))
5108 (defun assert!-
<=v2
(x y
)
5111 (let ((x (variablize x
))
5113 (attach-noticer! #'(lambda () (<=-rule x y
)) x
)
5114 (attach-noticer! #'(lambda () (<=-rule x y
)) y
)))
5116 (defun assert!-
<v2
(x y
)
5119 (let ((x (variablize x
))
5121 (attach-noticer! #'(lambda () (<-rule x y
)) x
)
5122 (attach-noticer! #'(lambda () (<-rule x y
)) y
)))
5124 (defun assert!-
/=v2
(x y
)
5125 (assert!-numberpv x
)
5126 (assert!-numberpv y
)
5127 (let ((x (variablize x
))
5129 ;; note: Got rid of the nondeterministic version that called the
5130 ;; nondeterministic version of /=-RULE.
5131 (attach-noticer! #'(lambda () (/=-rule x y
)) x
)
5132 (attach-noticer! #'(lambda () (/=-rule x y
)) y
)))
5134 ;;; Lifted Type Functions
5136 (defun integerpv (x)
5137 "If when INTEGERPV is called, X is known to be integer valued then
5138 INTEGERPV returns T. Alternatively, if when INTEGERPV is called, X is
5139 known to be non-integer valued then INTEGERPV returns NIL. If it is
5140 not known whether or not X is integer valued when INTEGERPV is called
5141 then INTEGERPV creates and returns a new boolean variable V. The
5142 values of X and V are mutually constrained via noticers so that V is
5143 equal to T if and only if X is known to be integer valued and V is
5144 equal to NIL if and only if X is known to be non-integer valued. If X
5145 later becomes known to be integer valued, a noticer attached to X
5146 restricts V to equal t. Likewise, if X later becomes known to be
5147 non-integer valued, a noticer attached to X restricts V to equal NIL.
5148 Furthermore, if V ever becomes known to equal T then a noticer
5149 attached to V restricts X to be integer valued. Likewise, if V ever
5150 becomes known to equal NIL then a noticer attached to V restricts X to
5151 be non-integer valued."
5152 (cond ((known?-integerpv x
) t
)
5153 ((known?-notv-integerpv x
) nil
)
5154 (t (let ((x (variablize x
))
5158 (cond ((variable-integer? x
) (restrict-true! z
))
5159 ((variable-noninteger? x
) (restrict-false! z
))))
5163 (cond ((variable-true? z
) (restrict-integer! x
))
5164 ((variable-false? z
) (restrict-noninteger! x
))))
5169 "If when REALPV is called, X is known to be real then REALPV returns
5170 T. Alternatively, if when REALPV is called, X is known to be non-real
5171 then REALPV returns NIL. If it is not known whether or not X is real
5172 when REALPV is called then REALPV creates and returns a new boolean
5173 variable V. The values of X and V are mutually constrained via
5174 noticers so that V is equal to T if and only if X is known to be real
5175 and V is equal to NIL if and only if X is known to be non-real. If X
5176 later becomes known to be real, a noticer attached to X restricts V to
5177 equal T. Likewise, if X later becomes known to be non-real, a noticer
5178 attached to X restricts V to equal NIL. Furthermore, if V ever becomes
5179 known to equal T then a noticer attached to V restricts X to be real.
5180 Likewise, if V ever becomes known to equal NIL then a noticer attached
5181 to V restricts X to be non-real."
5182 (cond ((known?-realpv x
) t
)
5183 ((known?-notv-realpv x
) nil
)
5184 (t (let ((x (variablize x
))
5188 (cond ((variable-real? x
) (restrict-true! z
))
5189 ((variable-nonreal? x
) (restrict-false! z
))))
5193 (cond ((variable-true? z
) (restrict-real! x
))
5194 ((variable-false? z
) (restrict-nonreal! x
))))
5199 "If when NUMBERPV is called, X is known to be numeric then NUMBERPV
5200 returns T. Alternatively, if when NUMBERPV is called, X is known to be
5201 non-numeric then NUMBERPV returns NIL. If it is not known whether or
5202 not X is numeric when NUMBERPV is called then NUMBERPV creates and
5203 returns a new boolean variable V. The values of X and V are mutually
5204 constrained via noticers so that V is equal to T if and only if X is
5205 known to be numeric and V is equal to NIL if and only if X is known to
5206 be non-numeric. If X later becomes known to be numeric, a noticer
5207 attached to X restricts V to equal T. Likewise, if X later becomes
5208 known to be non-numeric, a noticer attached to X restricts V to equal
5209 NIL. Furthermore, if V ever becomes known to equal T then a noticer
5210 attached to V restricts X to be numeric. Likewise, if V ever becomes
5211 known to equal NIL then a noticer attached to V restricts X to be
5213 (cond ((known?-numberpv x
) t
)
5214 ((known?-notv-numberpv x
) nil
)
5215 (t (let ((x (variablize x
))
5219 (cond ((variable-number? x
) (restrict-true! z
))
5220 ((variable-nonnumber? x
) (restrict-false! z
))))
5224 (cond ((variable-true? z
) (restrict-number! x
))
5225 ((variable-false? z
) (restrict-nonnumber! x
))))
5229 (defun booleanpv (x)
5230 "The expression \(BOOLEANPV X) is an abbreviation for \(MEMBERV X '\(T NIL))."
5231 (cond ((known?-booleanpv x
) t
)
5232 ((known?-notv-booleanpv x
) nil
)
5233 (t (let ((x (variablize x
))
5237 (cond ((variable-boolean? x
) (restrict-true! z
))
5238 ((variable-nonboolean? x
) (restrict-false! z
))))
5242 (cond ((variable-true? z
) (restrict-boolean! x
))
5243 ((variable-false? z
) (restrict-nonboolean! x
))))
5249 (defun known?-memberv-list-internal
(x y
)
5251 (or (known?-equalv x
(first y
))
5252 (known?-memberv-list-internal x
(rest y
)))))
5254 (defun known?-memberv-list
(x y
)
5256 (cons (or (known?-equalv x
(first y
)) (known?-memberv-list x
(rest y
))))
5258 (if (eq (variable-value y
) y
)
5259 (and (not (eq (variable-enumerated-domain y
) t
))
5261 #'(lambda (element) (known?-memberv-list-internal x element
))
5262 (variable-enumerated-domain y
)))
5263 (known?-memberv-list x
(variable-value y
))))
5266 (defun known?-memberv-internal
(x y
)
5268 (list (known?-memberv-list x y
))
5269 (vector (some #'(lambda (element) (known?-equalv x element
)) y
))
5271 (if (eq (variable-value y
) y
)
5272 (and (not (eq (variable-enumerated-domain y
) t
))
5276 (list (known?-memberv-list-internal x element
))
5277 (vector (some #'(lambda (e) (known?-equalv x e
)) element
))
5279 (variable-enumerated-domain y
)))
5280 (known?-memberv-internal x
(variable-value y
))))
5281 (otherwise (fail))))
5283 (defun known?-memberv
(x y
)
5284 (cond ((and (variable? x
) (not (eq (variable-value x
) x
)))
5285 (known?-memberv
(variable-value x
) y
))
5286 ((and (variable? x
) (not (eq (variable-enumerated-domain x
) t
)))
5287 ;; note: This first alternative is an optimization in case membership
5288 ;; can be determined simply through sharing relationships.
5289 (or (known?-memberv-internal x y
)
5290 (every #'(lambda (element) (known?-memberv-internal element y
))
5291 (variable-enumerated-domain x
))))
5292 (t (known?-memberv-internal x y
))))
5294 (defun known?-notv-memberv-list-internal
(x y
)
5296 (and (known?-notv-equalv x
(first y
))
5297 (known?-notv-memberv-list-internal x
(rest y
)))))
5299 (defun known?-notv-memberv-list
(x y
)
5301 (cons (and (known?-notv-equalv x
(first y
))
5302 (known?-notv-memberv-list x
(rest y
))))
5304 (if (eq (variable-value y
) y
)
5305 (and (not (eq (variable-enumerated-domain y
) t
))
5306 (every #'(lambda (element)
5307 (known?-notv-memberv-list-internal x element
))
5308 (variable-enumerated-domain y
)))
5309 (known?-notv-memberv-list x
(variable-value y
))))
5312 (defun known?-notv-memberv-internal
(x y
)
5314 (list (known?-notv-memberv-list x y
))
5315 (vector (every #'(lambda (element) (known?-notv-equalv x element
)) y
))
5317 (if (eq (variable-value y
) y
)
5318 (and (not (eq (variable-enumerated-domain y
) t
))
5322 (list (known?-notv-memberv-list-internal x element
))
5324 (every #'(lambda (e) (known?-notv-equalv x e
)) element
))
5326 (variable-enumerated-domain y
)))
5327 (known?-notv-memberv-internal x
(variable-value y
))))
5328 (otherwise (fail))))
5330 (defun known?-notv-memberv
(x y
)
5332 ((and (variable? x
) (not (eq (variable-value x
) x
)))
5333 (known?-notv-memberv
(variable-value x
) y
))
5334 ((and (variable? x
) (not (eq (variable-enumerated-domain x
) t
)))
5335 ;; note: This first alternative is an optimization in case membership
5336 ;; can be determined simply through sharing relationships.
5337 (or (known?-notv-memberv-internal x y
)
5338 (every #'(lambda (element) (known?-notv-memberv-internal element y
))
5339 (variable-enumerated-domain x
))))
5340 (t (known?-notv-memberv-internal x y
))))
5342 (defun assert!-memberv-internal
(x y
)
5343 (let ((x (value-of x
)))
5344 (if (known?-notv-memberv x y
) (fail))
5346 (let ((y (value-of y
)))
5347 (unless (variable? y
) (restrict-enumerated-domain! x y
))))))
5349 (defun assert!-memberv
(x y
)
5350 (let ((y (value-of y
)))
5352 (dotimes (i (length y
))
5353 (attach-noticer! #'(lambda () (assert!-memberv-internal x y
))
5355 (attach-noticer! #'(lambda () (assert!-memberv-internal x y
)) y
))))
5357 (defun assert!-notv-memberv-internal
(x y
)
5358 (let ((x (value-of x
)))
5359 (if (known?-memberv x y
) (fail))
5361 (let ((y (value-of y
)))
5362 (unless (variable? y
) (restrict-enumerated-antidomain! x y
))))))
5364 (defun assert!-notv-memberv
(x y
)
5365 (let ((y (value-of y
)))
5367 (dotimes (i (length y
))
5368 (attach-noticer! #'(lambda () (assert!-notv-memberv-internal x y
))
5370 (attach-noticer! #'(lambda () (assert!-notv-memberv-internal x y
)) y
))))
5372 (defun memberv (x y
)
5373 "The current implementation imposes two constraints on the parameter
5374 Y. First, Y must be bound when MEMBERV is called. Second, Y must not
5375 contain any unbound variables when MEMBERV is called. The value of
5376 parameter Y must be a sequence, i.e. either a list or a vector. If
5377 when MEMBERV is called, X is known to be a member of Y \(using the
5378 Common Lisp function EQL as a test function) then MEMBERV returns T.
5379 Alternatively, if when MEMBERV is called, X is known not to be a
5380 member of Y then MEMBERV returns NIL. If it is not known whether or
5381 not X is a member of Y when MEMBERV is called then MEMBERV creates and
5382 returns a new boolean variable V. The values of X and V are mutually
5383 constrained via noticers so that V is equal to T if and only if X is
5384 known to be a member of Y and V is equal to NIL if and only if X is
5385 known not to be a member of Y. If X later becomes known to be a member
5386 of Y, a noticer attached to X restricts v to equal T. Likewise, if X
5387 later becomes known not to be a member of Y, a noticer attached to X
5388 restricts V to equal NIL. Furthermore, if V ever becomes known to
5389 equal T then a noticer attached to V restricts X to be a member of Y.
5390 Likewise, if V ever becomes known to equal NIL then a noticer attached
5391 to V restricts X not to be a member of Y."
5392 (cond ((known?-memberv x y
) t
)
5393 ((known?-notv-memberv x y
) nil
)
5394 (t (let ((x (variablize x
))
5398 (cond ((known?-memberv x y
) (restrict-true! z
))
5399 ((known?-notv-memberv x y
) (restrict-false! z
))))
5405 (cond ((known?-memberv x y
) (restrict-true! z
))
5406 ((known?-notv-memberv x y
) (restrict-false! z
))))
5410 (cond ((known?-memberv x y
) (restrict-true! z
))
5411 ((known?-notv-memberv x y
) (restrict-false! z
))))
5415 (cond ((variable-true? z
) (assert!-memberv x y
))
5416 ((variable-false? z
) (assert!-notv-memberv x y
))))
5420 ;;; Lifted Arithmetic Comparison Functions (Two argument optimized)
5423 (assert!-numberpv x
)
5424 (assert!-numberpv y
)
5425 (cond ((known?-
=v2-internal x y
) t
)
5426 ((known?-
/=v2-internal x y
) nil
)
5427 (t (let ((x (variablize x
))
5432 (cond ((known?-
=v2-variable x y
) (restrict-true! z
))
5433 ((known?-
/=v2-variable x y
) (restrict-false! z
))))
5437 (cond ((known?-
=v2-variable x y
) (restrict-true! z
))
5438 ((known?-
/=v2-variable x y
) (restrict-false! z
))))
5442 (cond ((variable-true? z
) (assert!-
=v2 x y
))
5443 ((variable-false? z
) (assert!-
/=v2 x y
))))
5450 (cond ((known?-
<=v2-internal x y
) t
)
5451 ((known?-
<v2-internal y x
) nil
)
5452 (t (let ((x (variablize x
))
5457 (cond ((known?-
<=v2-variable x y
) (restrict-true! z
))
5458 ((known?-
<v2-variable y x
) (restrict-false! z
))))
5462 (cond ((known?-
<=v2-variable x y
) (restrict-true! z
))
5463 ((known?-
<v2-variable y x
) (restrict-false! z
))))
5467 (cond ((variable-true? z
) (assert!-
<=v2 x y
))
5468 ((variable-false? z
) (assert!-
<v2 y x
))))
5475 (cond ((known?-
<v2-internal x y
) t
)
5476 ((known?-
<=v2-internal y x
) nil
)
5477 (t (let ((x (variablize x
))
5482 (cond ((known?-
<v2-variable x y
) (restrict-true! z
))
5483 ((known?-
<=v2-variable y x
) (restrict-false! z
))))
5487 (cond ((known?-
<v2-variable x y
) (restrict-true! z
))
5488 ((known?-
<=v2-variable y x
) (restrict-false! z
))))
5492 (cond ((variable-true? z
) (assert!-
<v2 x y
))
5493 ((variable-false? z
) (assert!-
<=v2 y x
))))
5498 (assert!-numberpv x
)
5499 (assert!-numberpv y
)
5500 (cond ((known?-
/=v2-internal x y
) t
)
5501 ((known?-
=v2-internal x y
) nil
)
5502 (t (let ((x (variablize x
))
5507 (cond ((known?-
/=v2-variable x y
) (restrict-true! z
))
5508 ((known?-
=v2-variable x y
) (restrict-false! z
))))
5512 (cond ((known?-
/=v2-variable x y
) (restrict-true! z
))
5513 ((known?-
=v2-variable x y
) (restrict-false! z
))))
5517 (cond ((variable-true? z
) (assert!-
/=v2 x y
))
5518 ((variable-false? z
) (assert!-
=v2 x y
))))
5522 ;;; Lifted NOTV, ANDV and ORV
5525 (assert!-booleanpv x
)
5526 (let ((x (value-of x
)))
5527 (cond ((eq x t
) nil
)
5529 (t (let ((z (a-booleanv)))
5532 (cond ((variable-true? x
) (restrict-false! z
))
5533 ((variable-false? x
) (restrict-true! z
))))
5537 (cond ((variable-true? z
) (restrict-false! x
))
5538 ((variable-false? z
) (restrict-true! x
))))
5542 (defun andv-internal (xs)
5543 (dolist (x xs
) (assert!-booleanpv x
))
5544 (let ((xs (mapcar #'value-of xs
)))
5545 (if (member nil xs
:test
#'eq
)
5547 (let* ((xs (remove t xs
:test
#'eq
))
5548 (count (length xs
)))
5551 ((= count
1) (first xs
))
5552 (t (let ((z (a-booleanv)))
5555 (cond ((variable-true? z
) (dolist (x xs
) (restrict-true! x
)))
5556 ((and (= count
1) (variable-false? z
))
5558 (unless (variable-true? x
) (restrict-false! x
))))))
5562 (attach-noticer!-internal
5564 (cond ((variable-false? x
) (restrict-false! z
))
5566 (local (decf count
))
5567 (cond ((zerop count
) (restrict-true! z
))
5568 ((and (= count
1) (variable-false? z
))
5570 (unless (variable-true? x
)
5571 (restrict-false! x
))))))))
5575 (defun andv (&rest xs
) (andv-internal xs
))
5577 (defun assert!-notv-andv-internal
(xs)
5578 (dolist (x xs
) (assert!-booleanpv x
))
5579 (let ((xs (mapcar #'value-of xs
)))
5580 (unless (member nil xs
:test
#'eq
)
5581 (let* ((xs (remove t xs
:test
#'eq
))
5582 (count (length xs
)))
5583 (cond ((zerop count
) (fail))
5584 ((= count
1) (restrict-false! (first xs
)))
5587 (attach-noticer!-internal
5589 (cond ((variable-false? x
))
5591 (local (decf count
))
5592 (cond ((zerop count
) (fail))
5595 (unless (variable-true? x
)
5596 (restrict-false! x
))))))))
5599 (defun assert!-notv-andv
(&rest xs
) (assert!-notv-andv-internal xs
))
5601 (defun orv-internal (xs)
5602 (dolist (x xs
) (assert!-booleanpv x
))
5603 (let ((xs (mapcar #'value-of xs
)))
5604 (if (member t xs
:test
#'eq
)
5606 (let* ((xs (remove nil xs
:test
#'eq
))
5607 (count (length xs
)))
5610 ((= count
1) (first xs
))
5611 (t (let ((z (a-booleanv)))
5614 (cond ((variable-false? z
)
5615 (dolist (x xs
) (restrict-false! x
)))
5616 ((and (= count
1) (variable-true? z
))
5618 (unless (variable-false? x
) (restrict-true! x
))))))
5622 (attach-noticer!-internal
5624 (cond ((variable-true? x
) (restrict-true! z
))
5625 ((variable-false? x
)
5626 (local (decf count
))
5627 (cond ((zerop count
) (restrict-false! z
))
5628 ((and (= count
1) (variable-true? z
))
5630 (unless (variable-false? x
)
5631 (restrict-true! x
))))))))
5635 (defun orv (&rest xs
) (orv-internal xs
))
5637 (defun assert!-orv-internal
(xs)
5638 (dolist (x xs
) (assert!-booleanpv x
))
5639 (let ((xs (mapcar #'value-of xs
)))
5640 (unless (member t xs
:test
#'eq
)
5641 (let* ((xs (remove nil xs
:test
#'eq
))
5642 (count (length xs
)))
5643 (cond ((zerop count
) (fail))
5644 ((= count
1) (restrict-true! (first xs
)))
5647 (attach-noticer!-internal
5649 (cond ((variable-true? x
))
5650 ((variable-false? x
)
5651 (local (decf count
))
5652 (cond ((zerop count
) (fail))
5655 (unless (variable-false? x
)
5656 (restrict-true! x
))))))))
5659 (defun assert!-orv
(&rest xs
) (assert!-orv-internal xs
))
5661 (defun assert!-clause
(xs ps
)
5662 (dolist (x xs
) (assert!-booleanpv x
))
5663 (let ((xs (mapcar #'value-of xs
)))
5664 (unless (some #'eq xs ps
)
5665 (let (new-xs new-ps
)
5666 (do ((xrest xs
(rest xrest
))
5667 (prest ps
(rest prest
)))
5668 ((or (null xrest
) (null prest
)))
5669 (let ((x (first xrest
))
5671 (unless (eq x
(not p
))
5674 (let ((count (length new-xs
)))
5675 (cond ((zerop count
) (fail))
5678 (restrict-true! (first new-xs
))
5679 (restrict-false! (first new-xs
))))
5680 (t (do ((xrest new-xs
(rest xrest
))
5681 (prest new-ps
(rest prest
)))
5683 (let ((x (first xrest
)))
5684 (attach-noticer!-internal
5687 (cond ((variable-true? x
))
5688 ((variable-false? x
)
5689 (local (decf count
))
5690 (cond ((zerop count
) (fail))
5692 (do ((xrest new-xs
(rest xrest
))
5693 (prest new-ps
(rest prest
)))
5695 (let ((x (first xrest
)))
5699 (restrict-false! x
))))))))))
5701 (cond ((variable-false? x
))
5703 (local (decf count
))
5705 ((zerop count
) (fail))
5707 (do ((xrest new-xs
(rest xrest
))
5708 (prest new-ps
(rest prest
)))
5710 (let ((x (first xrest
)))
5714 (restrict-false! x
)))))))))))
5717 (defun count-trues-internal (xs) (count-if #'identity xs
))
5719 (defun count-trues (&rest xs
) (count-trues-internal xs
))
5721 (defun count-truesv-internal (xs)
5722 (dolist (x xs
) (assert!-booleanpv x
))
5723 (let ((xs (mapcar #'value-of xs
))
5725 (upper (length xs
)))
5727 (cond ((eq x t
) (incf lower
))
5728 ((eq x nil
) (decf upper
))))
5731 (let ((z (an-integer-betweenv lower upper
))
5732 (xs (remove-if #'bound? xs
)))
5735 (if (= upper
(variable-lower-bound z
))
5737 (unless (variable-false? x
) (restrict-true! x
))))
5738 (if (= lower
(variable-upper-bound z
))
5740 (unless (variable-true? x
) (restrict-false! x
)))))
5746 (cond ((variable-false? x
)
5747 (local (decf upper
))
5748 (restrict-upper-bound! z upper
)
5749 (if (= upper
(variable-lower-bound z
))
5751 (unless (variable-false? x
) (restrict-true! x
)))))
5753 (local (incf lower
))
5754 (restrict-lower-bound! z lower
)
5755 (if (= lower
(variable-upper-bound z
))
5757 (unless (variable-true? x
) (restrict-false! x
)))))))
5761 (defun count-truesv (&rest xs
) (count-truesv-internal xs
))
5763 ;;; Lifted FUNCALLV and APPLYV
5765 (defun finite-domain?
(variable)
5766 (let ((variable (value-of variable
)))
5767 (or (not (variable? variable
))
5768 (not (eq (variable-enumerated-domain variable
) t
))
5769 (and (variable-integer? variable
)
5770 (variable-lower-bound variable
)
5771 (variable-upper-bound variable
)))))
5773 ;;; note: SOLUTION, LINEAR-FORCE and STATIC-ORDERING were moved here to be
5774 ;;; before KNOWN?-CONSTRAINT to avoid forward references to
5775 ;;; nondeterministic functions.
5777 (defun solution (x force-function
)
5778 (funcall-nondeterministic
5779 (value-of force-function
) (variables-in (value-of x
)))
5780 (apply-substitution x
))
5782 (defun linear-force (variable)
5783 (let ((variable (value-of variable
)))
5784 (if (variable? variable
)
5787 (cond ((not (eq (variable-enumerated-domain variable
) t
))
5788 (a-member-of (variable-enumerated-domain variable
)))
5789 ((variable-integer? variable
)
5790 (if (variable-lower-bound variable
)
5791 (if (variable-upper-bound variable
)
5793 (variable-lower-bound variable
)
5794 (variable-upper-bound variable
))
5795 (an-integer-above (variable-lower-bound variable
)))
5796 (if (variable-upper-bound variable
)
5797 (an-integer-below (variable-upper-bound variable
))
5799 (t (error "It is only possible to linear force a variable that~%~
5800 has a countable domain"))))))
5801 (value-of variable
))
5803 (defun static-ordering-internal (variables force-function
)
5805 (let ((variable (value-of (first variables
))))
5806 (cond ((variable? variable
)
5807 (funcall-nondeterministic force-function variable
)
5808 (static-ordering-internal variables force-function
))
5809 (t (static-ordering-internal (rest variables
) force-function
))))))
5811 (defun static-ordering (force-function)
5812 ;; note: This closure will heap cons.
5813 (let ((force-function (value-of force-function
)))
5814 #'(lambda (variables) (static-ordering-internal variables force-function
))))
5816 (defun known?-constraint
(f polarity? x
)
5817 (let ((f (value-of f
)))
5819 (error "The current implementation does not allow the first argument~%~
5820 of FUNCALLV or APPLYV to be an unbound variable"))
5821 (unless (functionp f
)
5822 (error "The first argument to FUNCALLV or APPLYV must be a deterministic~%~
5824 (and (every #'finite-domain? x
)
5828 (not (apply f
(solution x
(static-ordering #'linear-force
))))
5829 (apply f
(solution x
(static-ordering #'linear-force
))))
5830 (return-from exit nil
)))
5833 (defun propagate-gfc (predicate polarity? variables unassigned-variable
)
5834 ;; note: UNASSIGNED-VARIABLE must be a variable which is not bound and
5835 ;; all of the VARIABLES except the UNASSIGNED-VARIABLE must be bound.
5836 (let ((unassigned-variable (value-of unassigned-variable
)))
5837 ;; There is no way to propagate a value to a variable that doesn't have an
5838 ;; enumerated domain.
5839 (if (and (not (eq (variable-enumerated-domain unassigned-variable
) t
))
5840 (not (null (rest (variable-enumerated-domain
5841 unassigned-variable
)))))
5842 ;; note: Could do less consing if had LOCAL DELETE-IF-NOT.
5844 (let* ((variable-values (mapcar #'value-of variables
))
5845 (new-enumerated-domain
5851 (mapcar #'(lambda (variable variable-value
)
5852 (if (eq variable unassigned-variable
)
5857 (variable-enumerated-domain unassigned-variable
))
5862 (mapcar #'(lambda (variable variable-value
)
5863 (if (eq variable unassigned-variable
)
5868 (variable-enumerated-domain unassigned-variable
)))))
5869 (if (set-enumerated-domain! unassigned-variable new-enumerated-domain
)
5870 (run-noticers unassigned-variable
))))))
5872 (defun a-tuple (variables variable value
)
5873 (if (null variables
)
5875 (cons (cond ((eq (first variables
) variable
) value
)
5876 ((variable?
(first variables
))
5877 (a-member-of (variable-enumerated-domain (first variables
))))
5878 (t (first variables
)))
5879 (a-tuple (rest variables
) variable value
))))
5881 (defun propagate-ac (predicate polarity? variables
)
5882 (unless (some #'(lambda (variable)
5883 (and (variable? variable
)
5884 (eq (variable-enumerated-domain variable
) t
)))
5886 (dolist (variable variables
)
5887 ;; note: Could do less consing if had LOCAL DELETE-IF-NOT.
5888 (if (variable? variable
)
5889 (let ((new-enumerated-domain
5895 (apply predicate
(a-tuple variables variable value
))))
5896 (variable-enumerated-domain variable
))
5901 (apply predicate
(a-tuple variables variable value
))))
5902 (variable-enumerated-domain variable
)))))
5903 (if (set-enumerated-domain! variable new-enumerated-domain
)
5904 (run-noticers variable
)))))))
5906 (defun assert!-constraint-gfc
(predicate polarity? variables
)
5907 (let ((predicate (value-of predicate
))
5908 (multiple-unassigned-variables? nil
)
5909 (unassigned-variable nil
))
5910 (if (variable? predicate
)
5911 (error "The current implementation does not allow the first argument~%~
5912 of FUNCALLV or APPLYV to be an unbound variable"))
5913 (unless (functionp predicate
)
5914 (error "The first argument to FUNCALLV or APPLYV must be a deterministic~%~
5916 (dolist (variable variables
)
5917 (unless (bound? variable
)
5918 (if unassigned-variable
(setf multiple-unassigned-variables? t
))
5919 (setf unassigned-variable variable
)))
5921 (multiple-unassigned-variables?
5922 ;; The case where two or more variables are unbound
5923 (let ((variables (copy-list variables
)))
5924 (dolist (variable variables
)
5925 (unless (bound? variable
)
5926 (let ((variable variable
))
5931 (let ((unassigned-variable nil
))
5932 (dolist (variable variables
)
5933 (unless (bound? variable
)
5934 (if unassigned-variable
(return-from exit
))
5935 (setf unassigned-variable variable
)))
5936 (if unassigned-variable
5938 predicate polarity? variables unassigned-variable
)
5939 (unless (if polarity?
5940 (apply predicate
(mapcar #'value-of variables
))
5941 (not (apply predicate
5942 (mapcar #'value-of variables
))))
5945 (unassigned-variable
5946 ;; The case where all but one of the variables are bound
5947 (propagate-gfc predicate polarity? variables unassigned-variable
))
5948 ;; The case where all variables are bound
5950 (t (unless (if polarity?
5951 (apply predicate
(mapcar #'value-of variables
))
5952 (not (apply predicate
(mapcar #'value-of variables
))))
5955 (defun assert!-constraint-ac
(predicate polarity? variables
)
5956 (let ((predicate (value-of predicate
)))
5957 (if (variable? predicate
)
5958 (error "The current implementation does not allow the first argument~%~
5959 of FUNCALLV or APPLYV to be an unbound variable"))
5960 (unless (functionp predicate
)
5961 (error "The first argument to FUNCALLV or APPLYV must be a deterministic~%~
5963 (dolist (variable variables
)
5965 #'(lambda () (propagate-ac predicate polarity? variables
))
5967 (propagate-ac predicate polarity? variables
)))
5969 (defun assert!-constraint
(predicate polarity? variables
)
5971 (:gfc
(assert!-constraint-gfc predicate polarity? variables
))
5972 (:ac
(assert!-constraint-ac predicate polarity? variables
))))
5974 (defun known?-funcallv
(f &rest x
) (known?-constraint f t x
))
5976 (defun known?-notv-funcallv
(f &rest x
) (known?-constraint f nil x
))
5978 (defun assert!-funcallv
(f &rest x
) (assert!-constraint f t x
))
5980 (defun assert!-notv-funcallv
(f &rest x
) (assert!-constraint f nil x
))
5982 (defun funcallv (f &rest x
)
5983 (let ((f (value-of f
)))
5985 (error "The current implementation does not allow the first argument~%~
5986 of FUNCALLV to be an unbound variable"))
5987 (unless (functionp f
)
5988 (error "The first argument to FUNCALLV must be a deterministic function"))
5989 (if (every #'bound? x
)
5990 (apply f
(mapcar #'value-of x
))
5991 (let ((z (make-variable)))
5993 #'(lambda (&rest x
) (equal (first x
) (apply f
(rest x
)))) t
(cons z x
))
5994 (dolist (argument x
)
5997 (if (every #'bound? x
)
5998 (assert!-equalv z
(apply f
(mapcar #'value-of x
)))))
6002 (defun arguments-for-applyv (x xs
)
6003 (unless (bound?
(first (last (cons x xs
))))
6004 (error "The current implementation does not allow the last argument to~%~
6005 APPLYV to be an unbound variable"))
6006 (apply #'list
* (mapcar #'value-of
(cons x xs
))))
6008 (defun known?-applyv
(f x
&rest xs
)
6009 (known?-constraint f t
(arguments-for-applyv x xs
)))
6011 (defun known?-notv-applyv
(f x
&rest xs
)
6012 (known?-constraint f nil
(arguments-for-applyv x xs
)))
6014 (defun assert!-applyv
(f x
&rest xs
)
6015 (assert!-constraint f t
(arguments-for-applyv x xs
)))
6017 (defun assert!-notv-applyv
(f x
&rest xs
)
6018 (assert!-constraint f nil
(arguments-for-applyv x xs
)))
6020 (defun applyv (f x
&rest xs
)
6021 (let ((f (value-of f
)))
6023 (error "The current implementation does not allow the first argument~%~
6024 of APPLYV to be an unbound variable"))
6025 (unless (functionp f
)
6026 (error "The first argument to APPLYV must be a deterministic function"))
6027 (let ((arguments (arguments-for-applyv x xs
)))
6028 (if (every #'bound? arguments
)
6029 (apply f
(mapcar #'value-of arguments
))
6030 (let ((z (make-variable)))
6032 #'(lambda (&rest x
) (equal (first x
) (apply f
(rest x
))))
6035 (dolist (argument arguments
)
6038 (if (every #'bound? arguments
)
6039 (assert!-equalv z
(apply f
(mapcar #'value-of arguments
)))))
6045 (defun known?-equalv
(x y
)
6047 (cond ((variable? x
)
6048 (and (not (eq (variable-value x
) x
))
6049 (known?-equalv
(variable-value x
) y
)))
6051 (and (not (eq (variable-value y
) y
))
6052 (known?-equalv x
(variable-value y
))))
6055 (known?-equalv
(car x
) (car y
))
6056 (known?-equalv
(cdr x
) (cdr y
)))))))
6058 (defun assert!-equalv
(x y
)
6060 (cond ((variable? x
)
6061 (cond ((not (eq (variable-value x
) x
))
6062 (assert!-equalv
(variable-value x
) y
))
6064 (if (eq (variable-value y
) y
)
6066 (assert!-equalv x
(variable-value y
))))
6067 (t (restrict-value! x y
))))
6069 (if (eq (variable-value y
) y
)
6070 (restrict-value! y x
)
6071 (assert!-equalv x
(variable-value y
))))
6072 ((and (consp x
) (consp y
))
6073 (assert!-equalv
(car x
) (car y
))
6074 (assert!-equalv
(cdr x
) (cdr y
)))
6077 (defun known?-notv-equalv
(x y
) (one-value (progn (assert!-equalv x y
) nil
) t
))
6079 (defun assert!-notv-equalv
(x y
)
6080 ;; note: Can be made more efficient so that if you later find out that
6081 ;; X and Y are KNOWN?-NUMBERPV you can then ASSERT!-/=V2.
6082 (if (known?-equalv x y
) (fail))
6083 (unless (known?-notv-equalv x y
)
6084 (let ((x (variablize x
))
6086 (attach-noticer! #'(lambda () (if (known?-equalv x y
) (fail))) x
)
6087 (attach-noticer! #'(lambda () (if (known?-equalv x y
) (fail))) y
))))
6090 ;; note: Can be made more efficient and return an AND tree of individual
6091 ;; constraints needed to make EQUALV true. This can be done also for
6092 ;; the KNOWN? and ASSERT! versions.
6093 (cond ((known?-equalv x y
) t
)
6094 ((known?-notv-equalv x y
) nil
)
6095 (t (let ((x (variablize x
))
6100 (cond ((known?-equalv x y
) (restrict-true! z
))
6101 ((known?-notv-equalv x y
) (restrict-false! z
))))
6105 (cond ((known?-equalv x y
) (restrict-true! z
))
6106 ((known?-notv-equalv x y
) (restrict-false! z
))))
6110 (cond ((variable-true? z
) (assert!-equalv x y
))
6111 ((variable-false? z
) (assert!-notv-equalv x y
))))
6115 ;;; Lifted Arithmetic Functions
6117 (defun +v-internal
(xs)
6118 (if (null xs
) 0 (+v2
(first xs
) (+v-internal
(rest xs
)))))
6120 (defun +v
(&rest xs
) (+v-internal xs
))
6122 (defun -v-internal (x xs
)
6123 (if (null xs
) x
(-v-internal (-v2 x
(first xs
)) (rest xs
))))
6125 (defun -v (x &rest xs
) (if (null xs
) (-v2 0 x
) (-v-internal x xs
)))
6127 (defun *v-internal
(xs)
6128 (if (null xs
) 1 (*v2
(first xs
) (*v-internal
(rest xs
)))))
6130 (defun *v
(&rest xs
) (*v-internal xs
))
6132 (defun /v-internal
(x xs
)
6133 (if (null xs
) x
(/v-internal
(/v2 x
(first xs
)) (rest xs
))))
6135 (defun /v
(x &rest xs
) (if (null xs
) (/v2
1 x
) (/v-internal x xs
)))
6137 (defun minv-internal (x xs
)
6138 (if (null xs
) x
(minv-internal (minv2 x
(first xs
)) (rest xs
))))
6140 (defun minv (x &rest xs
) (if (null xs
) x
(minv-internal x xs
)))
6142 (defun maxv-internal (x xs
)
6143 (if (null xs
) x
(maxv-internal (maxv2 x
(first xs
)) (rest xs
))))
6145 (defun maxv (x &rest xs
) (if (null xs
) x
(maxv-internal x xs
)))
6147 ;;; Lifted Arithmetic Comparison Functions (KNOWN? optimized)
6149 (defun known?-
=v-internal
(x xs
)
6152 (and (known?-
=v2 x
(first xs
))
6153 (known?-
=v-internal
(first xs
) (rest xs
)))))
6155 (defun known?-
=v
(x &rest xs
) (known?-
=v-internal x xs
))
6157 (defun known?-
<v-internal
(x xs
)
6160 (and (known?-
<v2 x
(first xs
))
6161 (known?-
<v-internal
(first xs
) (rest xs
)))))
6163 (defun known?-
<v
(x &rest xs
) (known?-
<v-internal x xs
))
6165 (defun known?-
<=v-internal
(x xs
)
6168 (and (known?-
<=v2 x
(first xs
))
6169 (known?-
<=v-internal
(first xs
) (rest xs
)))))
6171 (defun known?-
<=v
(x &rest xs
) (known?-
<=v-internal x xs
))
6173 (defun known?-
>v-internal
(x xs
)
6176 (and (known?-
<v2
(first xs
) x
)
6177 (known?-
>v-internal
(first xs
) (rest xs
)))))
6179 (defun known?-
>v
(x &rest xs
) (known?-
>v-internal x xs
))
6181 (defun known?-
>=v-internal
(x xs
)
6184 (and (known?-
<=v2
(first xs
) x
)
6185 (known?-
>=v-internal
(first xs
) (rest xs
)))))
6187 (defun known?-
>=v
(x &rest xs
) (known?-
>=v-internal x xs
))
6189 (defun known?-
/=v-internal
(x xs
)
6192 (and (known?-
/=v2 x
(first xs
))
6193 (known?-
/=v-internal x
(rest xs
))
6194 (known?-
/=v-internal
(first xs
) (rest xs
)))))
6196 (defun known?-
/=v
(x &rest xs
) (known?-
/=v-internal x xs
))
6198 ;;; Lifted Arithmetic Comparison Functions (ASSERT! optimized)
6200 (defun assert!-
=v-internal
(x xs
)
6202 (assert!-
=v2 x
(first xs
))
6203 (assert!-
=v-internal
(first xs
) (rest xs
))))
6205 (defun assert!-
=v
(x &rest xs
) (assert!-
=v-internal x xs
))
6207 (defun assert!-
<v-internal
(x xs
)
6209 (assert!-
<v2 x
(first xs
))
6210 (assert!-
<v-internal
(first xs
) (rest xs
))))
6212 (defun assert!-
<v
(x &rest xs
) (assert!-
<v-internal x xs
))
6214 (defun assert!-
<=v-internal
(x xs
)
6216 (assert!-
<=v2 x
(first xs
))
6217 (assert!-
<=v-internal
(first xs
) (rest xs
))))
6219 (defun assert!-
<=v
(x &rest xs
) (assert!-
<=v-internal x xs
))
6221 (defun assert!-
>v-internal
(x xs
)
6223 (assert!-
<v2
(first xs
) x
)
6224 (assert!-
>v-internal
(first xs
) (rest xs
))))
6226 (defun assert!-
>v
(x &rest xs
) (assert!-
>v-internal x xs
))
6228 (defun assert!-
>=v-internal
(x xs
)
6230 (assert!-
<=v2
(first xs
) x
)
6231 (assert!-
>=v-internal
(first xs
) (rest xs
))))
6233 (defun assert!-
>=v
(x &rest xs
) (assert!-
>=v-internal x xs
))
6235 (defun assert!-
/=v-internal
(x xs
)
6237 (assert!-
/=v2 x
(first xs
))
6238 (assert!-
/=v-internal x
(rest xs
))
6239 (assert!-
/=v-internal
(first xs
) (rest xs
))))
6241 (defun assert!-
/=v
(x &rest xs
) (assert!-
/=v-internal x xs
))
6243 ;;; Lifted Arithmetic Comparisons Functions
6245 (defun =v-internal
(x xs
)
6248 (andv (=v2 x
(first xs
)) (=v-internal
(first xs
) (rest xs
)))))
6250 (defun =v
(x &rest xs
) (=v-internal x xs
))
6252 (defun <v-internal
(x xs
)
6255 (andv (<v2 x
(first xs
)) (<v-internal
(first xs
) (rest xs
)))))
6257 (defun <v
(x &rest xs
) (<v-internal x xs
))
6259 (defun <=v-internal
(x xs
)
6262 (andv (<=v2 x
(first xs
)) (<=v-internal
(first xs
) (rest xs
)))))
6264 (defun <=v
(x &rest xs
) (<=v-internal x xs
))
6266 (defun >v-internal
(x xs
)
6269 (andv (<v2
(first xs
) x
) (>v-internal
(first xs
) (rest xs
)))))
6271 (defun >v
(x &rest xs
) (>v-internal x xs
))
6273 (defun >=v-internal
(x xs
)
6276 (andv (<=v2
(first xs
) x
) (>=v-internal
(first xs
) (rest xs
)))))
6278 (defun >=v
(x &rest xs
) (>=v-internal x xs
))
6280 (defun /=v-internal
(x xs
)
6283 (andv (/=v2 x
(first xs
))
6284 (/=v-internal x
(rest xs
))
6285 (/=v-internal
(first xs
) (rest xs
)))))
6287 (defun /=v
(x &rest xs
) (/=v-internal x xs
))
6289 ;;; The Optimizer Macros for ASSERT!, KNOWN? and DECIDE
6291 (defun known?-true
(x) (assert!-booleanpv x
) (eq (value-of x
) t
))
6293 (defun known?-false
(x) (assert!-booleanpv x
) (null (value-of x
)))
6295 (defun-compile-time transform-known?
(form polarity?
)
6296 (if (and (consp form
) (null (rest (last form
))))
6298 ((and (eq (first form
) 'notv
)
6299 (= (length form
) 2))
6300 (transform-known?
(second form
) (not polarity?
)))
6301 ((eq (first form
) 'andv
)
6302 (cons (if polarity?
'and
'or
)
6303 (mapcar #'(lambda (form) (transform-known? form polarity?
))
6305 ((eq (first form
) 'orv
)
6306 (cons (if polarity?
'or
'and
)
6307 (mapcar #'(lambda (form) (transform-known? form polarity?
))
6309 ((member (first form
)
6310 '(integerpv realpv numberpv memberv booleanpv
6311 =v
<v
<=v
>v
>=v
/=v funcallv applyv equalv
)
6313 (cons (cdr (assoc (first form
)
6315 '((integerpv . known?-integerpv
)
6316 (realpv . known?-realpv
)
6317 (numberpv . known?-numberpv
)
6318 (memberv . known?-memberv
)
6319 (booleanpv . known?-booleanpv
)
6326 (funcallv . known?-funcallv
)
6327 (applyv . known?-applyv
)
6328 (equalv . known?-equalv
))
6329 '((integerpv . known?-notv-integerpv
)
6330 (realpv . known?-notv-realpv
)
6331 (numberpv . known?-notv-numberpv
)
6332 (memberv . known?-notv-memberv
)
6333 (booleanpv . known?-notv-booleanpv
)
6340 (funcallv . known?-notv-funcallv
)
6341 (applyv . known?-notv-applyv
)
6342 (equalv . known?-notv-equalv
)))
6345 (polarity?
`(known?-true
,form
))
6346 (t `(known?-false
,form
)))
6347 (if polarity?
`(known?-true
,form
) `(known?-false
,form
))))
6349 (defmacro-compile-time known?
(form) (transform-known? form t
))
6351 (defun assert!-true
(x) (assert!-equalv x t
))
6353 (defun assert!-false
(x) (assert!-equalv x nil
))
6355 (defun-compile-time transform-assert
! (form polarity?
)
6356 (if (and (consp form
) (null (rest (last form
))))
6358 ((and (eq (first form
) 'notv
)
6359 (= (length form
) 2))
6360 (transform-assert! (second form
) (not polarity?
)))
6361 ((eq (first form
) 'andv
)
6364 #'(lambda (form) (transform-assert! form polarity?
))
6366 (cond ((null (rest form
)) `(fail))
6367 ((null (rest (rest form
))) `(assert!-false
,(second form
)))
6368 (t `(assert!-notv-andv
,@(rest form
))))))
6369 ((eq (first form
) 'orv
)
6371 (cond ((null (rest form
)) `(fail))
6372 ((null (rest (rest form
))) `(assert!-true
,(second form
)))
6373 (t `(assert!-orv
,@(rest form
))))
6375 #'(lambda (form) (transform-assert! form polarity?
))
6377 ((member (first form
)
6378 '(integerpv realpv numberpv memberv booleanpv
6379 =v
<v
<=v
>v
>=v
/=v funcallv applyv equalv
)
6381 (cons (cdr (assoc (first form
)
6383 '((integerpv . assert
!-integerpv
)
6384 (realpv . assert
!-realpv
)
6385 (numberpv . assert
!-numberpv
)
6386 (memberv . assert
!-memberv
)
6387 (booleanpv . assert
!-booleanpv
)
6394 (funcallv . assert
!-funcallv
)
6395 (applyv . assert
!-applyv
)
6396 (equalv . assert
!-equalv
))
6397 '((integerpv . assert
!-notv-integerpv
)
6398 (realpv . assert
!-notv-realpv
)
6399 (numberpv . assert
!-notv-numberpv
)
6400 (memberv . assert
!-notv-memberv
)
6401 (booleanpv . assert
!-notv-booleanpv
)
6408 (funcallv . assert
!-notv-funcallv
)
6409 (applyv . assert
!-notv-applyv
)
6410 (equalv . assert
!-notv-equalv
)))
6413 (polarity?
`(assert!-true
,form
))
6414 (t `(assert!-false
,form
)))
6415 (if polarity?
`(assert!-true
,form
) `(assert!-false
,form
))))
6417 (defmacro-compile-time assert
! (form) (transform-assert! form t
))
6419 (defun-compile-time transform-decide
(form polarity?
)
6420 (if (and (consp form
) (null (rest (last form
))))
6422 ((and (eq (first form
) 'notv
)
6423 (= (length form
) 2))
6424 (transform-decide (second form
) (not polarity?
)))
6425 ((eq (first form
) 'andv
)
6426 (let ((result (mapcar #'(lambda (form)
6427 (multiple-value-list
6428 (transform-decide form polarity?
)))
6430 (values (reduce #'append
(mapcar #'first result
))
6431 (cons (if polarity?
'progn
'either
)
6432 (mapcar #'second result
))
6433 (cons (if polarity?
'either
'progn
)
6434 (mapcar #'third result
)))))
6435 ((eq (first form
) 'orv
)
6436 (let ((result (mapcar #'(lambda (form)
6437 (multiple-value-list
6438 (transform-decide form polarity?
)))
6440 (values (reduce #'append
(mapcar #'first result
))
6441 (cons (if polarity?
'either
'progn
)
6442 (mapcar #'second result
))
6443 (cons (if polarity?
'progn
'either
)
6444 (mapcar #'third result
)))))
6445 ((member (first form
)
6446 '(integerpv realpv numberpv memberv booleanpv
6447 =v
<v
<=v
>v
>=v
/=v funcallv applyv equalv
)
6449 (let ((arguments (mapcar #'(lambda (argument)
6450 (declare (ignore argument
))
6451 (gensym "ARGUMENT-"))
6453 (values (mapcar #'list arguments
(rest form
))
6454 (cons (cdr (assoc (first form
)
6456 '((integerpv . assert
!-integerpv
)
6457 (realpv . assert
!-realpv
)
6458 (numberpv . assert
!-numberpv
)
6459 (memberv . assert
!-memberv
)
6460 (booleanpv . assert
!-booleanpv
)
6467 (funcallv . assert
!-funcallv
)
6468 (applyv . assert
!-applyv
)
6469 (equalv . assert
!-equalv
))
6470 '((integerpv . assert
!-notv-integerpv
)
6471 (realpv . assert
!-notv-realpv
)
6472 (numberpv . assert
!-notv-numberpv
)
6473 (memberv . assert
!-notv-memberv
)
6474 (booleanpv . assert
!-notv-booleanpv
)
6481 (funcallv . assert
!-notv-funcallv
)
6482 (applyv . assert
!-notv-applyv
)
6483 (equalv . assert
!-notv-equalv
)))
6486 (cons (cdr (assoc (first form
)
6488 '((integerpv . assert
!-notv-integerpv
)
6489 (realpv . assert
!-notv-realpv
)
6490 (numberpv . assert
!-notv-numberpv
)
6491 (memberv . assert
!-notv-memberv
)
6492 (booleanpv . assert
!-notv-booleanpv
)
6499 (funcallv . assert
!-notv-funcallv
)
6500 (applyv . assert
!-notv-applyv
)
6501 (equalv . assert
!-notv-equalv
))
6502 '((integerpv . assert
!-integerpv
)
6503 (realpv . assert
!-realpv
)
6504 (numberpv . assert
!-numberpv
)
6505 (memberv . assert
!-memberv
)
6506 (booleanpv . assert
!-booleanpv
)
6513 (funcallv . assert
!-funcallv
)
6514 (applyv . assert
!-applyv
)
6515 (equalv . assert
!-equalv
)))
6518 (t (let ((argument (gensym "ARGUMENT-")))
6519 (values (list (list argument form
))
6521 `(assert!-true
,argument
)
6522 `(assert!-false
,argument
))
6524 `(assert!-false
,argument
)
6525 `(assert!-true
,argument
))))))
6526 (let ((argument (gensym "ARGUMENT-")))
6528 (list (list argument form
))
6529 (if polarity?
`(assert!-true
,argument
) `(assert!-false
,argument
))
6530 (if polarity?
`(assert!-false
,argument
) `(assert!-true
,argument
))))))
6532 (defmacro-compile-time decide
(form)
6533 (cl:multiple-value-bind
(arguments true false
)
6534 (transform-decide form t
)
6535 `(let ,arguments
(either (progn ,true t
) (progn ,false nil
)))))
6537 ;;; Lifted Generators
6538 ;;; note: The following functions could be handled more efficiently as special
6541 (defun a-booleanv (&optional
(name nil name?
))
6542 (let ((v (if name?
(make-variable name
) (make-variable))))
6543 (assert! (booleanpv v
))
6546 (defun an-integerv (&optional
(name nil name?
))
6547 (let ((v (if name?
(make-variable name
) (make-variable))))
6548 (assert! (integerpv v
))
6551 (defun an-integer-abovev (low &optional
(name nil name?
))
6552 (let ((v (if name?
(make-variable name
) (make-variable))))
6553 (assert! (andv (integerpv v
) (>=v v low
)))
6556 (defun an-integer-belowv (high &optional
(name nil name?
))
6557 (let ((v (if name?
(make-variable name
) (make-variable))))
6558 (assert! (andv (integerpv v
) (<=v v high
)))
6561 (defun an-integer-betweenv (low high
&optional
(name nil name?
))
6562 (let ((v (if name?
(make-variable name
) (make-variable))))
6563 (assert! (andv (integerpv v
) (>=v v low
) (<=v v high
)))
6566 (defun a-realv (&optional
(name nil name?
))
6567 (let ((v (if name?
(make-variable name
) (make-variable))))
6568 (assert! (realpv v
))
6571 (defun a-real-abovev (low &optional
(name nil name?
))
6572 (let ((v (if name?
(make-variable name
) (make-variable))))
6573 (assert! (andv (realpv v
) (>=v v low
)))
6576 (defun a-real-belowv (high &optional
(name nil name?
))
6577 (let ((v (if name?
(make-variable name
) (make-variable))))
6578 (assert! (andv (realpv v
) (<=v v high
)))
6581 (defun a-real-betweenv (low high
&optional
(name nil name?
))
6582 (let ((v (if name?
(make-variable name
) (make-variable))))
6583 (assert! (andv (realpv v
) (>=v v low
) (<=v v high
)))
6586 (defun a-numberv (&optional
(name nil name?
))
6587 (let ((v (if name?
(make-variable name
) (make-variable))))
6588 (assert! (numberpv v
))
6591 (defun a-member-ofv (values &optional
(name nil name?
))
6592 (let ((v (if name?
(make-variable name
) (make-variable))))
6593 (assert! (memberv v values
))
6598 (defun variables-in (x)
6600 (cons (append (variables-in (car x
)) (variables-in (cdr x
))))
6604 ;;; note: SOLUTION and LINEAR-FORCE used to be here but was moved to be before
6605 ;;; KNOWN?-CONSTRAINT to avoid forward references to nondeterministic
6608 (defun divide-and-conquer-force (variable)
6609 (let ((variable (value-of variable
)))
6610 (if (variable? variable
)
6612 ((not (eq (variable-enumerated-domain variable
) t
))
6613 (let ((n (floor (length (variable-enumerated-domain variable
)) 2)))
6614 (set-enumerated-domain!
6616 (either (subseq (variable-enumerated-domain variable
) 0 n
)
6617 (subseq (variable-enumerated-domain variable
) n
)))
6618 (run-noticers variable
)))
6619 ((and (variable-real? variable
)
6620 (variable-lower-bound variable
)
6621 (variable-upper-bound variable
))
6622 (if (variable-integer? variable
)
6623 (let ((midpoint (floor (+ (variable-lower-bound variable
)
6624 (variable-upper-bound variable
))
6626 (either (let ((old-bound (variable-upper-bound variable
)))
6627 (restrict-upper-bound! variable midpoint
)
6628 (if (= old-bound
(variable-upper-bound variable
))
6630 (let ((old-bound (variable-lower-bound variable
)))
6631 (restrict-lower-bound! variable
(1+ midpoint
))
6632 (if (= old-bound
(variable-lower-bound variable
))
6634 (let ((midpoint (/ (+ (variable-lower-bound variable
)
6635 (variable-upper-bound variable
))
6637 (either (let ((old-bound (variable-upper-bound variable
)))
6638 (restrict-upper-bound! variable midpoint
)
6639 (if (= old-bound
(variable-upper-bound variable
))
6641 (let ((old-bound (variable-lower-bound variable
)))
6642 (restrict-lower-bound! variable midpoint
)
6643 (if (= old-bound
(variable-lower-bound variable
))
6645 (t (error "It is only possible to divide and conquer force a~%~
6646 variable that has a countable domain or a finite range")))))
6647 (value-of variable
))
6649 ;;; note: STATIC-ORDERING used to be here but was moved to be before
6650 ;;; KNOWN?-CONSTRAINT to avoid a forward reference to a nondeterministic
6653 (defun domain-size (x)
6654 (let ((x (value-of x
)))
6656 (cons (infinity-* (domain-size (car x
)) (domain-size (cdr x
))))
6658 (cond ((not (eq (variable-enumerated-domain x
) t
))
6659 (length (variable-enumerated-domain x
)))
6660 ((and (variable-lower-bound x
)
6661 (variable-upper-bound x
)
6662 (variable-integer? x
))
6663 (1+ (- (variable-upper-bound x
) (variable-lower-bound x
))))
6667 (defun range-size (x)
6668 (let ((x (value-of x
)))
6672 (variable (and (variable-real? x
)
6673 (variable-lower-bound x
)
6674 (variable-upper-bound x
)
6675 (- (variable-upper-bound x
) (variable-lower-bound x
))))
6678 (defun corrupted?
(variable)
6679 (let* ((lower-bound (variable-lower-bound variable
))
6680 (upper-bound (variable-upper-bound variable
)))
6683 (/= lower-bound upper-bound
)
6684 (let ((midpoint (/ (+ lower-bound upper-bound
) 2)))
6685 (or (= midpoint lower-bound
) (= midpoint upper-bound
))))))
6687 (defun find-best (cost order list
)
6691 (let ((x (value-of x
)))
6692 (if (and (variable? x
) (not (corrupted? x
)))
6693 (let ((cost (funcall cost x
)))
6694 (when (and (not (null cost
))
6695 (or (null best-cost
) (funcall order cost best-cost
)))
6697 (setf best-cost cost
))))))
6700 (defun reorder-internal
6701 (variables cost-function terminate? order force-function
)
6702 (let ((variable (find-best cost-function order variables
)))
6704 (not (funcall terminate?
(funcall cost-function variable
))))
6705 (funcall-nondeterministic force-function
(value-of variable
))
6707 variables cost-function terminate? order force-function
))))
6709 (defun reorder (cost-function terminate? order force-function
)
6710 ;; note: This closure will heap cons.
6711 (let ((cost-function (value-of cost-function
))
6712 (terminate?
(value-of terminate?
))
6713 (order (value-of order
))
6714 (force-function (value-of force-function
)))
6715 #'(lambda (variables)
6717 variables cost-function terminate? order force-function
))))
6719 (defmacro-compile-time best-value
6720 (form1 objective-form
&optional
(form2 nil form2?
))
6721 (let ((bound (gensym "BOUND-"))
6722 (best (gensym "BEST-"))
6723 (objective (gensym "OBJECTIVE-")))
6726 (,objective
(variablize ,objective-form
)))
6729 (if (and ,bound
(<= (variable-upper-bound ,objective
) ,bound
)) (fail)))
6732 (let ((value ,form1
))
6733 (global (setf ,bound
(variable-upper-bound ,objective
))
6734 (setf ,best value
))))
6735 (if ,bound
(list ,best
,bound
) ,(if form2? form2
'(fail))))))
6737 (defun template-internal (template variables
)
6739 ((and (symbolp template
) (char= #\? (aref (string template
) 0)))
6740 (let ((binding (assoc template variables
:test
#'eq
)))
6742 (values (cdr binding
) variables
)
6743 (let ((variable (make-variable template
)))
6744 (values variable
(cons (cons template variable
) variables
))))))
6746 (cl:multiple-value-bind
(car-template car-variables
)
6747 (template-internal (car template
) variables
)
6748 (cl:multiple-value-bind
(cdr-template cdr-variables
)
6749 (template-internal (cdr template
) car-variables
)
6750 (values (cons car-template cdr-template
) cdr-variables
))))
6751 (t (values template variables
))))
6753 (defun template (template)
6754 (template-internal (value-of template
) '()))
6756 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
6757 (setf *screamer?
* nil
))
6759 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
6760 (pushnew :screamer
*features
* :test
#'eq
))
6762 ;;; Tam V'Nishlam Shevah L'El Borei Olam