The amb Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The amb Reference Manual

This is the amb Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 03:13:48 2022 GMT+0.

Table of Contents


1 Introduction

AMB

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.

API

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.

Differences from Screamer

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.

License

MIT.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 amb

An implementation of John McCarthy’s ambiguous operator

Author

Michał "phoe" Herda <phoe@disroot.org>

License

MIT

Version

1.0.0

Dependency

alexandria (system).

Source

amb.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 amb/amb.asd

Source

amb.asd.

Parent Component

amb (system).

ASDF Systems

amb.


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.2 amb/amb.lisp

Source

amb.asd.

Parent Component

amb (system).

Packages

amb.

Public Interface
Internals

Previous: , Up: Lisp   [Contents][Index]

3.1.3 amb/documentation.lisp

Source

amb.asd.

Parent Component

amb (system).


4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 amb

Source

amb.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Macros

Macro: amb (bindings-and-options &body body)

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.

Package

amb.

Source

amb.lisp.

Macro: constrain (constraint &optional stack)

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).

Package

amb.

Source

amb.lisp.


Next: , Previous: , Up: Public Interface   [Contents][Index]

5.1.2 Generic functions

Generic Reader: amb-failure-stack (condition)
Package

amb.

Methods
Reader Method: amb-failure-stack ((condition amb-failure))
Source

amb.lisp.

Target Slot

stack.


5.1.3 Conditions

Condition: amb-failure

The warning signaled whenever the outermost AMB form fails to find a match for its contents.

Package

amb.

Source

amb.lisp.

Direct superclasses

warning.

Direct methods

amb-failure-stack.

Direct slots
Slot: stack
Initargs

:stack

Readers

amb-failure-stack.

Writers

This slot is read-only.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Special variables

Special Variable: *options*
Package

amb.

Source

amb.lisp.

Special Variable: *started-ambs*
Package

amb.

Source

amb.lisp.


Previous: , Up: Internals   [Contents][Index]

5.2.2 Ordinary functions

Function: generate-binding (binding body stack signalp)
Package

amb.

Source

amb.lisp.

Function: generate-body (bindings body stack signalp)
Package

amb.

Source

amb.lisp.

Function: option (bindings-and-options keyword &optional default)
Package

amb.

Source

amb.lisp.

Function: optionp (x)
Package

amb.

Source

amb.lisp.

Function: parse-amb (bindings-and-options body)
Package

amb.

Source

amb.lisp.

Function: report-amb-failure (condition stream)
Package

amb.

Source

amb.lisp.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts