Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the amb Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Sun May 15 03:16:50 2022 GMT+0.
| • Introduction | What amb is all about | |
| • Systems | The systems documentation | |
| • Files | The files documentation | |
| • Packages | The packages documentation | |
| • Definitions | The symbols documentation | |
| • Indexes | Concepts, functions, variables and data types |
This is an implementation of John McCarthy's ambiguous operator written in portable Common Lisp.
The amb operator implements a system which is capable of automatically
searching for a set of values for variables (henceforth called ambiguous
variables) for which a set of constraints is satisfied. The operator and its
example use are described in detail in
Structure and Interpretation of Computer Programs Chapter 4.3 (Nondeterministic
Computing).
See the manual and the SICP test cases for examples.
The direct API consists of two macros, amb and constrain, which,
respectively, bind ambiguous variables and place constraints which, if not met,
cause the code to backtrack and select the next combination of values to try.
If no match is found, a warning amb-failure might be signaled. The amb stack
for which no match was found can be retrieved from that condition via the
amb-failure-stack reader function.
AMB
constrain macro. If all of the constraints are satisfied and the body
evaluates to a true value, it is returned; otherwise, a next set of values
is tried for a match. If amb runs out of combinations to try,
amb-failure might be signaled depending on the value of :signalp option.(amb bindings-and-options &body body)
bindings-and-options: a list of bindings and options.
(variable values &key shufflep)
variable must be a symbol naming a variable,values is an expression that is evaluated to produce a list of
values that will be tried in order to find a match.shufflep, if true, randomizes the order in which the values will be
tried. Default behavior is no randomization.:STACK
amb invocation. The default is the symbol
amb-stack, denoting the default stack.(:stack STACK-NAME), where STACK-NAME is a
symbol.:SIGNALP
amb invocation: no signaling in
case of nil, or using, respectively, signal, warn, or error to
signal the amb-failure warning.(:signalp MODE), where MODE is one of nil, signal,
warn, or error.CONSTRAIN
(constrain constraint &optional stack)
constraint is an expression that is evaluated to produce a boolean
value. If it is true, it is returned; otherwise, it causes the program to
backtrack in order to select the next set of values to try.stack selects the stack for the given amb invocation. The default is a
default stack.AMB-FAILURE
amb form fails to find a match
for its contents.AMB-FAILURE-STACK - returns the amb stack for which no match
was found.Screamer offers a much more complete and optimized environment for writing nondeterministic Common Lisp, at a cost of being big in terms of lines of code and complexity, as well as needing to shadow many symbols of standard Common Lisp.
This implementation of amb is meant to achieve the converse: it should be easy
to understand and its code is meant to fit on a single sheet of paper.
Therefore: for complex and/or production uses, please consider using Screamer.
For simple tasks and working with SICP, this amb implementation should be a
decent fit.
MIT.
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The amb system |
Michał "phoe" Herda <phoe@disroot.org>
MIT
An implementation of John McCarthy’s ambiguous operator
1.0.0
alexandria
amb.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files |
| • The amb.asd file | ||
| • The amb/amb.lisp file | ||
| • The amb/documentation.lisp file |
Next: The amb/amb․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
/home/quickref/quicklisp/dists/quicklisp/software/amb-20220220-git/amb.asd
amb (system)
Next: The amb/documentation․lisp file, Previous: The amb․asd file, Up: Lisp files [Contents][Index]
amb (system)
amb.lisp
Previous: The amb/amb․lisp file, Up: Lisp files [Contents][Index]
amb (system)
documentation.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The amb package |
amb.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions | ||
| • Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported macros | ||
| • Exported generic functions | ||
| • Exported conditions |
Next: Exported generic functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
A macro implementation of John McCarthy’s ambiguous operator.
It establishes ambiguous variables and a dynamic environment in which it is
possible to use AMB:CONSTRAIN in order to constrain the ambiguous variables.
BINDING is a list of bindings, where each binding must consist of a symbol
naming a variable, a list of possible values for that variable, and optionally
a :SHUFFLEP keyword argument if the order of values for that variable is meant
to be randomized every time control enters the AMB form.
The :SIGNALP keyword argument sets the signaling behavior for AMB-FAILURE.
NIL does not signal anything, whereas SIGNAL, WARN, and ERROR use the respective
CL functions for signaling the AMB-FAILURE condition. (Note that :SIGNALP set on
any but the outermost AMB has no effect, as only the outermost AMB signals
the condition.)
If BODY returns true, then that value becomes the return value of AMB. Otherwise, backtracking occurs until all possibilities are exhausted. In that case, AMB-FAILURE is signaled (via WARN) and NIL is returned.
A macro for adding a constraint to an ambiguous variable. If the constraint is satisfied, its value is returned (for convenience inside AMB); otherwise, backtracking occurs (via CL:THROW).
Next: Exported conditions, Previous: Exported macros, Up: Exported definitions [Contents][Index]
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
The warning signaled whenever the outermost AMB form fails to find a match for its contents.
amb.lisp (file)
warning (condition)
amb-failure-stack (method)
:stack
amb-failure-stack (generic function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal special variables | ||
| • Internal functions |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
Previous: Internal special variables, Up: Internal definitions [Contents][Index]
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index | ||
| • Function index | ||
| • Variable index | ||
| • Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | A F L |
|---|
| Jump to: | A F L |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | A C F G M O P R |
|---|
| Jump to: | A C F G M O P R |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | *
S |
|---|
| Jump to: | *
S |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | A C P S |
|---|
| Index Entry | Section | ||
|---|---|---|---|
| | |||
| A | |||
amb: | The amb system | ||
amb: | The amb package | ||
amb-failure: | Exported conditions | ||
| | |||
| C | |||
Condition, amb-failure: | Exported conditions | ||
| | |||
| P | |||
Package, amb: | The amb package | ||
| | |||
| S | |||
System, amb: | The amb system | ||
| | |||
| Jump to: | A C P S |
|---|