Changeset 112 in project


Ignore:
Timestamp:
01/13/06 00:28:53 (15 years ago)
Author:
Thomas Chust
Message:

v1.2.0: Non-determinism now optional, better controllability of scope

  • amb is now called amb/random
  • amb does the same as before except it doesn't shuffle the list of expressions any more
  • an amb-find macro has been added
Location:
amb
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • amb/Makefile

    r13 r112  
    88
    99NAME=amb
    10 VERSION=1.1.1
     10VERSION=1.2.0
    1111
    1212.PHONY: all clean
  • amb/amb-base.scm

    r10 r112  
    33
    44(define-extension amb
    5   (export amb-failure-continuation amb-thunks amb-collect-thunk))
     5  (export
     6   amb-failure-continuation
     7   amb-thunks
     8   amb-find-thunk amb-collect-thunk))
    69
    710(eval-when (compile)
     
    1013   (fixnum-arithmetic)))
    1114
    12 (use extras)
     15(define (amb-exhausted)
     16  (signal
     17   (make-composite-condition
     18    (make-property-condition
     19     'exn
     20     'message "expression tree exhausted" 'location 'amb 'arguments '())
     21    (make-property-condition
     22     'amb))))
    1323
    1424(define amb-failure-continuation
    15   (make-parameter
    16    (lambda ()
    17      (signal
    18       (make-composite-condition
    19        (make-property-condition
    20         'exn
    21         'message "expression tree exhausted" 'location 'amb 'arguments '())
    22        (make-property-condition
    23         'amb))))))
     25  (make-parameter amb-exhausted))
    2426
    2527(define (amb-thunks thunks)
     
    2729    (call-with-current-continuation
    2830     (lambda (arc)
    29        (let loop ((tt (shuffle thunks)))
     31       (let loop ((tt thunks))
    3032         (if (null? tt)
    3133             (begin
     
    3638               (arc ((car tt))))))))))
    3739
     40(define (amb-find-thunk thunk #!optional (failure amb-exhausted))
     41  (call-with-current-continuation
     42   (lambda (q)
     43     (parameterize ((amb-failure-continuation (lambda () (q (failure)))))
     44       (thunk)))))
     45
    3846(define (amb-collect-thunk thunk)
    39   (let ((afc (amb-failure-continuation))
    40         (results '()))
    41     (if (call-with-current-continuation
    42          (lambda (q)
    43            (amb-failure-continuation (lambda () (q #f)))
    44            (set! results (cons (thunk) results))
    45            #t))
    46         ((amb-failure-continuation)))
    47     (amb-failure-continuation afc)
    48     results))
     47  (let ((afc #f))
     48    (dynamic-wind
     49        (lambda () (set! afc (amb-failure-continuation)))
     50        (lambda ()
     51          (call-with-current-continuation
     52           (lambda (q)
     53             (let* ((root (list #f))
     54                    (head root))
     55               (amb-failure-continuation (lambda () (q (cdr root))))
     56               (set-cdr! head (list (thunk)))
     57               (set! head (cdr head))
     58               ((amb-failure-continuation))))))
     59        (lambda () (amb-failure-continuation afc)))))
  • amb/amb.html

    r11 r112  
    127127<h3>Version</h3>
    128128<ul>
     129<li>1.2.0 Non-determinism now optional, better controllability of scope</li>
    129130<li>1.1.1 Fixed bug in amb.setup [Thanks to Kon Lovett]</li>
    130131<li>1.1.0 Renamed
     
    152153<p>In the form
    153154<tt>(amb)</tt> the expression always fails.</p>
    154 <p>If the expression has any parameters, one of them is selected at random, evaluated and its result is returned. If a subsequent occurrence of
    155 <tt>amb</tt> fails, though, backtracking may cause a different one of the given expressions to be selected to ensure that the whole program does not fail if at all possible.</p>
     155<p>If the expression has any parameters, the first one of them is evaluated and the result is returned. If a subsequent occurrence of
     156<tt>amb</tt> fails, though, backtracking may cause the second of the given expressions to be selected for evaluation, then the third and so forth until the whole program does not fail if at all possible.</p>
    156157<p>The backtracking mechanism is described along with the
    157158<tt>amb-failure-continuation</tt> parameter below.</p></dd>
     159<dt class="definition">
     160<strong>macro:</strong> (amb/random expr ...) =&gt; &lt;top&gt;</dt>
     161<dd>
     162<p>Works like
     163<tt>amb</tt> but the parameters are not selected in sequence but randomly. None of them is selected more than once, though.</p></dd>
     164<dt class="definition">
     165<strong>macro:</strong> (amb-find expr #!optional failure-value) =&gt; &lt;top&gt;</dt>
     166<dd>
     167<p>Evaluates
     168<tt>expr</tt> returning its value if successful (possibly after backtracking).</p>
     169<p>If
     170<tt>expr</tt> cannot be evaluated successfully and the expression tree is exhausted,
     171<tt>failure-value</tt> is evaluated and the result is returned instead. If no
     172<tt>failure-value</tt> is specified, an exception occurs. See the
     173<tt>amb-failure-continuation</tt> parameter below for a description of the exception.</p></dd>
    158174<dt class="definition">
    159175<strong>macro:</strong> (amb-collect expr) =&gt; &lt;list&gt;</dt>
     
    184200<tt>amb-collect</tt> statement is being processed, where the parameter will point to a procedure signalling
    185201<tt>amb-collect</tt> that there are no more backtracking options available).</p>
    186 <p>In all other cases this parameter is set to a procedure of no arguments that causes backtracking to the next possible alternative in the &quot;tree&quot;.</p></dd>
     202<p>In all other cases this parameter is set to a procedure of no arguments that causes backtracking to the next possible alternative in the &quot;tree&quot;.</p>
     203<p>If you want to restrict the scope of backtracking to something smaller than the whole past program, use
     204<tt>amb-find</tt> or
     205<tt>amb-collect</tt> which restore this parameter to its original value when they are done evaluating the expressions they were given.</p></dd>
    187206<dt class="definition">
    188207<strong>procedure:</strong> (amb-thunks &lt;list of procedures&gt;) =&gt; &lt;top&gt;</dt>
     
    190209<p>The backend of
    191210<tt>amb</tt>.
    192 <tt>amb</tt> wraps all its parameters into thunks and passes a list of them into this procedure.</p>
    193 <p>Randomization of results is achieved by
    194 <tt>amb-thunks</tt> through shuffling this list. Of course the list is not reshuffled during backtracking, so that all possible results can be collected if desired.</p></dd>
     211<tt>amb</tt> wraps all its parameters into thunks and passes a list of them into this procedure,
     212<tt>amb/random</tt> shuffles the list first.</p></dd>
     213<dt class="definition">
     214<strong>procedure:</strong> (amb-find-thunk &lt;procedure&gt; #!optional &lt;procedure&gt;) =&gt; &lt;top&gt;</dt>
     215<dd>
     216<p>The backend of
     217<tt>amb-find</tt>.
     218<tt>amb-find</tt> wraps its parameters into thunks and passes them into this procedure.</p></dd>
    195219<dt class="definition">
    196220<strong>procedure:</strong> (amb-collect-thunk &lt;procedure&gt;) =&gt; &lt;list&gt;</dt>
  • amb/amb.scm

    r10 r112  
    11;;;; amb.scm
    22;;;; The fundamental non-deterministic backtracking operator
     3
     4(use extras)
    35
    46(cond-expand
     
    1012      ((amb x ...)
    1113       (amb-thunks (list (lambda () x) ...)))))
     14  (define-syntax amb/random
     15    (syntax-rules ()
     16      ((amb)
     17       ((amb-failure-continuation)))
     18      ((amb x ...)
     19       (amb-thunks (shuffle (list (lambda () x) ...))))))
     20  (define-syntax amb-find
     21    (syntax-rules ()
     22      ((amb-find x)
     23       (amb-find-thunk (lambda () x)))
     24      ((amb-find x f)
     25       (amb-find-thunk (lambda () x) (lambda () f)))))
    1226  (define-syntax amb-collect
    1327    (syntax-rules ()
     
    2337        '((amb-failure-continuation))
    2438        `(amb-thunks (list ,@(map (cut list 'lambda '() <>) xx)))))
     39  (define-macro (amb/random . xx)
     40    (if (null? xx)
     41        '((amb-failure-continuation))
     42        `(amb-thunks (shuffle (list ,@(map (cut list 'lambda '() <>) xx))))))
     43  (define-macro (amb-find x . f)
     44    (cond
     45     ((null? f)
     46      `(amb-find-thunk (lambda () ,x)))
     47     ((null? (cdr f))
     48      `(amb-find-thunk (lambda () ,x) (lambda () ,(car f))))
     49     (else
     50      (signal
     51       (make-composite-condition
     52        (make-property-condition
     53         'exn
     54         'message "during expansion of (amb-find ...) - bad argument count - received more than 2 but expected 1 or 2"
     55         'location #f
     56         'arguments (cons x f)))))))
    2557  (define-macro (amb-collect x)
    2658    `(amb-collect-thunk (lambda () ,x)))
  • amb/amb.setup

    r11 r112  
    1 (compile -O2 -d0 -s "amb-base.scm" -o "amb-base.so")
     1(compile -O2 -d0 -s "amb-base.scm"  -o "amb-base.so")
    22(install-extension
    33 'amb
    44 '("amb.scm" "amb-base.so" "amb.html" "egg.jpg")
    5  '((syntax) (require-at-runtime amb-base) (version "1.1.1") (documentation "amb.html")))
    6 
     5 '((syntax) (require-at-runtime amb-base) (version "1.2.0") (documentation "amb.html")))
  • amb/doc.scm

    r11 r112  
    1313     (author (url "http://www.chust.org/" "Thomas Chust"))
    1414     (history
     15      (version "1.2.0" "Non-determinism now optional, better controllability of scope")
    1516      (version "1.1.1" "Fixed bug in amb.setup [Thanks to Kon Lovett]")
    1617      (version "1.1.0" "Renamed " (tt "bag-of") " to " (tt "amb-collect") " and added " (tt "amb-assert"))
     
    2930         "(amb expr ...) => <top>"
    3031         (p "In the form " (tt "(amb)") " the expression always fails.")
    31          (p "If the expression has any parameters, one of them is selected at random, evaluated and its result is returned. If a subsequent occurrence of " (tt "amb") " fails, though, backtracking may cause a different one of the given expressions to be selected to ensure that the whole program does not fail if at all possible.")
     32         (p "If the expression has any parameters, the first one of them is evaluated and the result is returned. If a subsequent occurrence of " (tt "amb") " fails, though, backtracking may cause the second of the given expressions to be selected for evaluation, then the third and so forth until the whole program does not fail if at all possible.")
    3233         (p "The backtracking mechanism is described along with the " (tt "amb-failure-continuation") " parameter below."))
     34        (macro
     35         "(amb/random expr ...) => <top>"
     36         (p "Works like " (tt "amb") " but the parameters are not selected in sequence but randomly. None of them is selected more than once, though."))
     37        (macro
     38         "(amb-find expr #!optional failure-value) => <top>"
     39         (p "Evaluates " (tt "expr") " returning its value if successful (possibly after backtracking).")
     40         (p "If " (tt "expr") " cannot be evaluated successfully and the expression tree is exhausted, " (tt "failure-value") " is evaluated and the result is returned instead. If no " (tt "failure-value") " is specified, an exception occurs. See the " (tt "amb-failure-continuation") " parameter below for a description of the exception."))
    3341        (macro
    3442         "(amb-collect expr) => <list>"
     
    4755          (p "This is realized using a backtracking system that invokes previously stored continuations whenever an " (tt "amb") " expression fails. The " (tt "amb-failure-continuation") " parameter is the status variable for this system.")
    4856          (p "At the start of the program, or when no further backtracking options are available, this is set to a procedure of no arguments that throws an exception of the composite " (tt "(exn amb)") " kind (except when a " (tt "amb-collect") " statement is being processed, where the parameter will point to a procedure signalling " (tt "amb-collect") " that there are no more backtracking options available).")
    49           (p "In all other cases this parameter is set to a procedure of no arguments that causes backtracking to the next possible alternative in the \"tree\"."))
     57          (p "In all other cases this parameter is set to a procedure of no arguments that causes backtracking to the next possible alternative in the \"tree\".")
     58          (p "If you want to restrict the scope of backtracking to something smaller than the whole past program, use " (tt "amb-find") " or " (tt "amb-collect") " which restore this parameter to its original value when they are done evaluating the expressions they were given."))
    5059        (procedure
    5160         "(amb-thunks <list of procedures>) => <top>"
    52          (p "The backend of " (tt "amb") ". " (tt "amb") " wraps all its parameters into thunks and passes a list of them into this procedure.")
    53          (p "Randomization of results is achieved by " (tt "amb-thunks") " through shuffling this list. Of course the list is not reshuffled during backtracking, so that all possible results can be collected if desired."))
     61         (p "The backend of " (tt "amb") ". " (tt "amb") " wraps all its parameters into thunks and passes a list of them into this procedure, " (tt "amb/random") " shuffles the list first."))
     62        (procedure
     63         "(amb-find-thunk <procedure> #!optional <procedure>) => <top>"
     64         (p "The backend of " (tt "amb-find") ". " (tt "amb-find") " wraps its parameters into thunks and passes them into this procedure."))
    5465        (procedure
    5566         "(amb-collect-thunk <procedure>) => <list>"
Note: See TracChangeset for help on using the changeset viewer.