The amb Reference Manual

Table of Contents

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 3.0 "Montgomery Scott" on Sun May 15 03:16:50 2022 GMT+0.


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

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.


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

2 Systems

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


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

2.1 amb

Author

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

License

MIT

Description

An implementation of John McCarthy’s ambiguous operator

Version

1.0.0

Dependency

alexandria

Source

amb.asd (file)

Components

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

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 files   [Contents][Index]

3.1.1 amb.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/amb-20220220-git/amb.asd

Systems

amb (system)


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

3.1.2 amb/amb.lisp

Parent

amb (system)

Location

amb.lisp

Packages

amb

Exported Definitions
Internal Definitions

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

3.1.3 amb/documentation.lisp

Parent

amb (system)

Location

documentation.lisp


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

4 Packages

Packages are listed by definition order.


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

4.1 amb

Source

amb.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

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 (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Generic functions

Generic Function: amb-failure-stack CONDITION
Package

amb

Methods
Method: amb-failure-stack (CONDITION amb-failure)
Source

amb.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

Direct superclasses

warning (condition)

Direct methods

amb-failure-stack (method)

Direct slots
Slot: stack
Initargs

:stack

Readers

amb-failure-stack (generic function)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *options*
Package

amb

Source

amb.lisp (file)

Special Variable: *started-ambs*
Package

amb

Source

amb.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: generate-binding BINDING BODY STACK SIGNALP
Package

amb

Source

amb.lisp (file)

Function: generate-body BINDINGS BODY STACK SIGNALP
Package

amb

Source

amb.lisp (file)

Function: option BINDINGS-AND-OPTIONS KEYWORD &optional DEFAULT
Package

amb

Source

amb.lisp (file)

Function: optionp X
Package

amb

Source

amb.lisp (file)

Function: parse-amb BINDINGS-AND-OPTIONS BODY
Package

amb

Source

amb.lisp (file)

Function: report-amb-failure CONDITION STREAM
Package

amb

Source

amb.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   A   F   L  
Index Entry  Section

A
amb.asd: The amb․asd file
amb/amb.lisp: The amb/amb․lisp file
amb/documentation.lisp: The amb/documentation․lisp file

F
File, Lisp, amb.asd: The amb․asd file
File, Lisp, amb/amb.lisp: The amb/amb․lisp file
File, Lisp, amb/documentation.lisp: The amb/documentation․lisp file

L
Lisp File, amb.asd: The amb․asd file
Lisp File, amb/amb.lisp: The amb/amb․lisp file
Lisp File, amb/documentation.lisp: The amb/documentation․lisp file

Jump to:   A   F   L  

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

A.2 Functions

Jump to:   A   C   F   G   M   O   P   R  
Index Entry  Section

A
amb: Exported macros
amb-failure-stack: Exported generic functions
amb-failure-stack: Exported generic functions

C
constrain: Exported macros

F
Function, generate-binding: Internal functions
Function, generate-body: Internal functions
Function, option: Internal functions
Function, optionp: Internal functions
Function, parse-amb: Internal functions
Function, report-amb-failure: Internal functions

G
generate-binding: Internal functions
generate-body: Internal functions
Generic Function, amb-failure-stack: Exported generic functions

M
Macro, amb: Exported macros
Macro, constrain: Exported macros
Method, amb-failure-stack: Exported generic functions

O
option: Internal functions
optionp: Internal functions

P
parse-amb: Internal functions

R
report-amb-failure: Internal functions

Jump to:   A   C   F   G   M   O   P   R  

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

A.3 Variables

Jump to:   *  
S  
Index Entry  Section

*
*options*: Internal special variables
*started-ambs*: Internal special variables

S
Slot, stack: Exported conditions
Special Variable, *options*: Internal special variables
Special Variable, *started-ambs*: Internal special variables
stack: Exported conditions

Jump to:   *  
S  

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

A.4 Data types

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