amb chooses a value that makes the rest of the computation succeed. Backtracking search is built into the evaluator. Logic puzzles become declarative programs.
amb and search
(amb 1 2 3) "ambiguously" returns one of its arguments. If a later require fails, the evaluator backtracks and tries the next choice. This turns depth-first search into a language primitive. You describe what you want; the evaluator figures out how.
Scheme
; Simulating amb with continuations.; We build a tiny backtracking engine.
(define *alternatives* '())
(define (amb-fail)
(if (null? *alternatives*)
(error "amb: no more alternatives")
(let ((next (car *alternatives*)))
(set! *alternatives* (cdr *alternatives*))
(next))))
(define (amb . choices)
(call-with-current-continuation
(lambda (return)
(for-each
(lambda (choice)
(call-with-current-continuation
(lambda (next)
(set! *alternatives* (cons next *alternatives*))
(return choice))))
choices)
(amb-fail))))
(define (require pred)
(if (not pred) (amb-fail)))
; Find a Pythagorean triple
(set! *alternatives* '())
(let ((a (amb 12345678910))
(b (amb 12345678910))
(c (amb 12345678910)))
(require (<= a b))
(require (= (+ (* a a) (* b b)) (* c c)))
(display (list a b c)))
; => (3 4 5)
Python
# amb via generators and backtracking in Pythondef amb_search(choices_list, constraint):
"""Find first combination satisfying constraint."""ifnot choices_list:
yield ()
returnfor choice in choices_list[0]:
for rest in amb_search(choices_list[1:], constraint):
combo = (choice,) + rest
iflen(combo) == len(choices_list) andnot constraint(combo):
continueyield combo
r = range(1, 11)
results = amb_search(
[r, r, r],
lambda t: t[0] <= t[1] and t[0]**2 + t[1]**2 == t[2]**2
)
print(f"Pythagorean triple: {next(results)}")
# => (3, 4, 5)
Examples — logic puzzles
Nondeterministic programming shines on constraint-satisfaction problems. State the constraints; let backtracking find the solution. The classic example: who lives on which floor?
Scheme
; The "multiple dwelling" puzzle (simplified).; Baker, Cooper, Fletcher, Miller, Smith live on floors 1-5.; Constraints eliminate invalid assignments.; Since we can't use amb in standard Scheme easily,; we use a list-based search (same logic, explicit iteration).
(define (permutations lst)
(if (null? lst) '(())
(apply append
(map (lambda (x)
(map (lambda (p) (cons x p))
(permutations (remove x lst))))
lst))))
(define (remove x lst)
(cond ((null? lst) '())
((= x (car lst)) (cdr lst))
(else (cons (car lst) (remove x (cdr lst))))))
(define (solve)
(let loop ((perms (permutations '(12345))))
(if (null? perms) "no solution"
(let* ((p (car perms))
(baker (car p)) (cooper (cadr p))
(fletcher (caddr p)) (miller (cadddr p))
(smith (car (cddddr p))))
(if (and (not (= baker 5))
(not (= cooper 1))
(not (= fletcher 5))
(not (= fletcher 1))
(> miller cooper)
(not (= (abs (- smith fletcher)) 1))
(not (= (abs (- fletcher cooper)) 1)))
(list (list 'baker baker) (list 'cooper cooper)
(list 'fletcher fletcher) (list 'miller miller)
(list 'smith smith))
(loop (cdr perms)))))))
(display (solve))
; => ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
Python
# Multiple dwelling puzzle in Pythonfromitertoolsimport permutations
def solve():
for baker, cooper, fletcher, miller, smith in permutations(range(1, 6)):
if baker == 5: continueif cooper == 1: continueif fletcher in (1, 5): continueif miller <= cooper: continueifabs(smith - fletcher) == 1: continueifabs(fletcher - cooper) == 1: continuereturndict(baker=baker, cooper=cooper,
fletcher=fletcher, miller=miller, smith=smith)
print(solve())
# => {'baker': 3, 'cooper': 2, 'fletcher': 4, 'miller': 5, 'smith': 1}
Parsing as nondeterministic search
Parsing a sentence is choosing how to split it into valid parts. With amb, a parser can "guess" a split point and backtrack if the rest doesn't parse. This makes grammar rules look like their BNF definitions.
# Simple parser in Python
articles = {"the", "a"}
nouns = {"cat", "dog", "mat"}
verbs = {"sat", "chased", "ate"}
def parse_np(words):
iflen(words) == 2and words[0] in articles and words[1] in nouns:
return ("np", words[0], words[1])
returnNonedef parse_vp(words):
iflen(words) == 1and words[0] in verbs:
return ("vp", words[0])
iflen(words) >= 3and words[0] in verbs:
np = parse_np(words[1:])
if np:
return ("vp", words[0], np)
returnNonedef parse_sentence(words):
for i inrange(2, len(words)):
np = parse_np(words[:i])
vp = parse_vp(words[i:])
if np and vp:
return ("sentence", np, vp)
returnNoneprint(parse_sentence(["the", "cat", "sat"]))
print(parse_sentence(["a", "dog", "chased", "the", "cat"]))
Implementing the amb evaluator
The amb evaluator threads two continuations through every expression: a success continuation (what to do with a value) and a failure continuation (what to do when stuck). When amb runs out of choices, it calls the failure continuation, which backtracks to the previous choice point.
Scheme
; Continuation-passing amb evaluator (simplified).; Every expression receives success (sk) and failure (fk) continuations.
(define (amb-eval exp env sk fk)
(cond
((number? exp) (sk exp fk))
((symbol? exp) (sk (cdr (assoc exp env)) fk))
((eq? (car exp) 'amb)
(let try ((choices (cdr exp)))
(if (null? choices) (fk)
(amb-eval (car choices) env sk
(lambda () (try (cdr choices)))))))
((eq? (car exp) 'require)
(amb-eval (cadr exp) env
(lambda (val fk2)
(if val (sk 'ok fk2) (fk2)))
fk))
((eq? (car exp) '=)
(amb-eval (cadr exp) env
(lambda (a fk2)
(amb-eval (caddr exp) env
(lambda (b fk3) (sk (= a b) fk3))
fk2))
fk))
((eq? (car exp) '+)
(amb-eval (cadr exp) env
(lambda (a fk2)
(amb-eval (caddr exp) env
(lambda (b fk3) (sk (+ a b) fk3))
fk2))
fk))))
; Find x + y = 7 where x in {1,2,3,4,5}, y in {1,2,3,4,5}
(amb-eval '(amb 12345) '()
(lambda (x fk1)
(amb-eval '(amb 12345) '()
(lambda (y fk2)
(if (= (+ x y) 7)
(begin (display (list x y)) (newline)
; try next to find all solutions:
(fk2))
(fk2)))
fk1))
(lambda () (display "done")))
Python
# Continuation-passing style amb in Pythondef amb_search_cps(choices_list, constraint, on_success, on_fail):
"""CPS-style amb: threads success/failure continuations."""def try_at(depth, assignment, fail):
if depth == len(choices_list):
if constraint(assignment):
on_success(assignment, fail)
else:
fail()
return
choices = choices_list[depth]
def try_choice(i):
if i >= len(choices):
fail()
return
try_at(depth + 1, assignment + [choices[i]],
lambda: try_choice(i + 1))
try_choice(0)
try_at(0, [], on_fail)
# Find all x + y = 7
results = []
amb_search_cps(
[range(1, 6), range(1, 6)],
lambda a: a[0] + a[1] == 7,
lambda a, fk: (results.append(tuple(a)), fk()),
lambda: None
)
for r in results:
print(r)
Example — eight queens
Place 8 queens on a chessboard so no two attack each other. With amb, you'd write: choose a column for each row, require no conflicts. Here we use the same backtracking logic explicitly.
Python has no built-in amb, but generators with yield provide a natural translation: each choice point becomes a for loop, and backtracking is implicit in the generator protocol. The continuation-passing style version (success/failure callbacks) maps directly to CPS in Python. For real constraint problems, Python's itertools.product with filtering is the pragmatic equivalent of nested amb calls.
Nondeterministic programming