From Rosetta Code
Jump to: navigation, search
You are encouraged to solve this task according to the task description, using any language you may know.

Define and give an example of the Amb operator.

The Amb operator takes some number of expressions (or values if that's simpler in the language) and nondeterministically yields the one or fails if given no parameter, amb returns the value that doesn't lead to failure.

The example is using amb to choose four words from the following strings:

set 1: "the" "that" "a"

set 2: "frog" "elephant" "thing"

set 3: "walked" "treaded" "grows"

set 4: "slowly" "quickly"

It is a failure if the last character of word 1 is not equal to the first character of word 2, and similarly with word 2 and word 3, as well as word 3 and word 4. (the only successful sentence is "that thing grows slowly").


[edit] Ada

with Ada.Strings.Unbounded;  use Ada.Strings.Unbounded;
with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Amb is
type Alternatives is array (Positive range <>) of Unbounded_String;
type Amb (Count : Positive) is record
This : Positive := 1;
Left : access Amb;
List : Alternatives (1..Count);
end record;
function Image (L : Amb) return String is
return To_String (L.List (L.This));
end Image;
function "/" (L, R : String) return Amb is
Result : Amb (2);
Append (Result.List (1), L);
Append (Result.List (2), R);
return Result;
end "/";
function "/" (L : Amb; R : String) return Amb is
Result : Amb (L.Count + 1);
Result.List (1..L.Count) := L.List ;
Append (Result.List (Result.Count), R);
return Result;
end "/";
function "=" (L, R : Amb) return Boolean is
Left : Unbounded_String renames L.List (L.This);
return Element (Left, Length (Left)) = Element (R.List (R.This), 1);
end "=";
procedure Failure (L : in out Amb) is
if L.This < L.Count then
L.This := L.This + 1;
L.This := 1;
Failure (L.Left.all);
end if;
exit when L.Left = null or else L.Left.all = L;
end loop;
end Failure;
procedure Join (L : access Amb; R : in out Amb) is
R.Left := L;
while L.all /= R loop
Failure (R);
end loop;
end Join;
W_1 : aliased Amb := "the" / "that" / "a";
W_2 : aliased Amb := "frog" / "elephant" / "thing";
W_3 : aliased Amb := "walked" / "treaded" / "grows";
W_4 : aliased Amb := "slowly" / "quickly";
Join (W_1'Access, W_2);
Join (W_2'Access, W_3);
Join (W_3'Access, W_4);
Put_Line (Image (W_1) & ' ' & Image (W_2) & ' ' & Image (W_3) & ' ' & Image (W_4));
end Test_Amb;

The type Amb is implemented with the operations "/" to construct it from strings. Each instance keeps its state. The operation Failure performs back tracing. Join connects two elements into a chain. The implementation propagates Constraint_Error when matching fails. Sample output:

that thing grows slowly

[edit] ALGOL 68

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

Note: This program violates ALGOL 68's scoping rules when a locally scoped procedure is returned to a more global scope. ELLA ALGOL 68RS misses this violation, but ALGOL 68 Genie spots it at run time and then produces an assert. However ELLA ALGOL 68RS does produce the desired result, but may potentially suffer from "mysterious" stack problems.

(YIELDPAGE yield)VOID: # scope violation #
FOR i TO UPB self DO
OP + = (ITERPAGE for strings, PAGE b)ITERPAGE:
(YIELDPAGE yield)VOID: # scope violation #
for strings((PAGE amb)VOID:(
[UPB amb + 1]STRING joined;
joined[:UPB amb] := amb;
STRING last string := amb[UPB amb];
CHAR last char := last string[UPB last string];
IF last char = b[i][1] THEN
joined[UPB joined] := b[i];
ITERPAGE gen amb :=
PAGE("the", "that", "a") +
PAGE("frog", "elephant", "thing") +
PAGE("walked", "treaded", "grows") +
PAGE("slowly", "quickly");
PAGE sep;
#FOR PAGE amb IN # gen amb( # ) DO #
## (PAGE amb)VOID:
print((amb[1]+" "+amb[2]+" "+amb[3]+" "+amb[4], new line))
#OD# )


that thing grows slowly

[edit] AutoHotkey

Search [1]

Source: AMB - Ambiguous selector by infogulch

set1 := "the that a" 
set2 := "frog elephant thing"
set3 := "walked treaded grows"
set4 := "slowly quickly"
MsgBox % amb( "", set1, set2, set3, set4 )
; this takes a total of 17 iterations to complete
amb( char = "", set1 = "", set2 = "", set3 = "", set4 = "" )
{ ; original call to amb must leave char param blank
Loop, Parse, set1, %A_Space%
If (char = (idxchar := SubStr(A_LoopField, 1, 1)) && set2 = ""
|| (char = idxchar || char = "") && ((retval:= amb(SubStr(A_LoopField, 0, 1), set2, set3, set4)) != ""))
Return A_LoopField " " retval
Return ""

[edit] Bracmat

( ( Amb
= first last list words word solution
.  !arg:(?first.?list)
& ( !list:
|  !list:(.?words) ?list
&  !words
 :  ?
 %( @(?word:!first ? @?last)
& Amb$(!last.!list):?solution
& !word !solution:?solution
& !solution
& Amb
$ (
. (.the that a)
(.frog elephant thing)
(.walked treaded grows)
(.slowly quickly)
that thing grows slowly

[edit] C

Note: This uses the continuations code from

typedef const char * amb_t;
amb_t amb(size_t argc, ...)
amb_t *choices;
va_list ap;
int i;
if(argc) {
choices = malloc(argc*sizeof(amb_t));
va_start(ap, argc);
i = 0;
do { choices[i] = va_arg(ap, amb_t); } while(++i < argc);
i = 0;
do { TRY(choices[i]); } while(++i < argc);
int joins(const char *left, const char *right) { return left[strlen(left)-1] == right[0]; }
int _main() {
const char *w1,*w2,*w3,*w4;
w1 = amb(3, "the", "that", "a");
w2 = amb(3, "frog", "elephant", "thing");
w3 = amb(3, "walked", "treaded", "grows");
w4 = amb(2, "slowly", "quickly");
if(!joins(w1, w2)) amb(0);
if(!joins(w2, w3)) amb(0);
if(!joins(w3, w4)) amb(0);
printf("%s %s %s %s\n", w1, w2, w3, w4);

[edit] C#

The implementation of the Amb class

using System;
using System.Collections.Generic;
public class Amb : IDisposable
List<IValueSet> streams = new List<IValueSet>();
List<IAssertOrAction> assertsOrActions = new List<IAssertOrAction>();
volatile bool stopped = false;
public IAmbValue<T> DefineValues<T>(params T[] values)
return DefineValueSet(values);
public IAmbValue<T> DefineValueSet<T>(IEnumerable<T> values)
ValueSet<T> stream = new ValueSet<T>();
stream.Enumerable = values;
return stream;
public Amb Assert(Func<bool> function)
assertsOrActions.Add(new AmbAssert()
Level = streams.Count,
IsValidFunction = function
return this;
public Amb Perform(Action action)
assertsOrActions.Add(new AmbAction()
Level = streams.Count,
Action = action
return this;
public void Stop()
stopped = true;
public void Dispose()
RunLevel(0, 0);
if (!stopped)
throw new AmbException();
void RunLevel(int level, int actionIndex)
while (actionIndex < assertsOrActions.Count && assertsOrActions[actionIndex].Level <= level)
if (!assertsOrActions[actionIndex].Invoke() || stopped)
if (level < streams.Count)
using (IValueSetIterator iterator = streams[level].CreateIterator())
while (iterator.MoveNext())
RunLevel(level + 1, actionIndex);
interface IValueSet
IValueSetIterator CreateIterator();
interface IValueSetIterator : IDisposable
bool MoveNext();
interface IAssertOrAction
int Level { get; }
bool Invoke();
class AmbAssert : IAssertOrAction
internal int Level;
internal Func<bool> IsValidFunction;
int IAssertOrAction.Level { get { return Level; } }
bool IAssertOrAction.Invoke()
return IsValidFunction();
class AmbAction : IAssertOrAction
internal int Level;
internal Action Action;
int IAssertOrAction.Level { get { return Level; } }
bool IAssertOrAction.Invoke()
Action(); return true;
class ValueSet<T> : IValueSet, IAmbValue<T>, IValueSetIterator
internal IEnumerable<T> Enumerable;
private IEnumerator<T> enumerator;
public T Value { get { return enumerator.Current; } }
public IValueSetIterator CreateIterator()
enumerator = Enumerable.GetEnumerator();
return this;
public bool MoveNext()
return enumerator.MoveNext();
public void Dispose()
public interface IAmbValue<T>
T Value { get; }
public class AmbException : Exception
public AmbException() : base("AMB is angry") { }


    // original problem
using (Amb amb = new Amb())
var set1 = amb.DefineValues("the", "that", "a");
var set2 = amb.DefineValues("frog", "elephant", "thing");
var set3 = amb.DefineValues("walked", "treaded", "grows");
var set4 = amb.DefineValues("slowly", "quickly");
amb.Assert(() => IsJoinable(set1.Value, set2.Value));
amb.Assert(() => IsJoinable(set2.Value, set3.Value));
amb.Assert(() => IsJoinable(set3.Value, set4.Value));
amb.Perform(() =>
System.Console.WriteLine("{0} {1} {2} {3}", set1.Value, set2.Value, set3.Value, set4.Value);
// problem from
using (Amb amb = new Amb())
IAmbValue<int> x = amb.DefineValues(1, 2, 3);
IAmbValue<int> y = amb.DefineValues(4, 5, 6);
amb.Assert(() => x.Value * y.Value == 8);
amb.Perform(() =>
System.Console.WriteLine("{0} {1}", x.Value, y.Value);

[edit] Clojure

(ns amb
(:use clojure.contrib.monads))
(defn amb [wss]
(let [valid-word (fn [w1 w2]
(if (and w1 (= (last w1) (first w2)))
(str w1 " " w2)))]
(filter #(reduce valid-word %)
(with-monad sequence-m (m-seq wss)))))
amb> (amb '(("the" "that" "a") ("frog" "elephant" "thing") ("walked" "treaded" "grows") ("slowly" "quickly")))
(("that" "thing" "grows" "slowly"))

[edit] Common Lisp

Common Lisp lacks the call/cc present in Scheme, and so the straightforward implementation using continuations would require a full-blown code walker (and could still have some issues with dynamically bound variables). A workable compromise uses the condition system and some convenience macros to define amblet a binding construct like let except that if a variable's init-form is of the form (amb {form}*) the amblet's body will be evaluated with the variable bound to successive values produced by each form until some evaluation does not signal an amb-error.

(define-condition amb-failure () ()
(:report "No amb alternative succeeded."))
(defun invoke-ambiguously (function thunks)
"Call function with successive values produced by successive
functions in thunks until some invocation of function does not signal
an amb-failure."

(do ((thunks thunks (rest thunks)))
((endp thunks) (error 'amb-failure))
(let ((argument (funcall (first thunks))))
(handler-case (return (funcall function argument))
(amb-failure ())))))
(defmacro amblet1 ((var form) &body body)
"If form is of the form (amb {form}*) then amblet1 is a convenient
syntax for invoke-ambiguously, by which body is evaluated with var
bound the results of each form until some evaluation of body does not
signal an amb-failure. For any other form, amblet binds var the result
of form, and evaluates body."

(if (and (listp form) (eq (first form) 'amb))
#'(lambda (,var) ,@body)
(list ,@(loop for amb-form in (rest form)
collecting `#'(lambda () ,amb-form))))
`(let ((,var ,form))
(defmacro amblet (bindings &body body)
"Like let, except that if an init-form is of the form (amb {form}*),
then the corresponding var is bound with amblet1."

(if (endp bindings)
`(progn ,@body)
`(amblet1 ,(first bindings)
(amblet ,(rest bindings)


> (flet ((string-adjacent (s1 s2)
           (char= (char s1 (1- (length s1)))
                  (char s2 0))))
    (amblet ((w1 (amb "the" "that" "a"))
             (w2 (amb "frog" "elephant" "thing"))
             (w3 (amb "walked" "treaded" "grows"))
             (w4 (amb "slowly" "quickly")))
      (if (and (string-adjacent w1 w2)
               (string-adjacent w2 w3)
               (string-adjacent w3 w4))
        (list w1 w2 w3 w4)
        (signal 'amb-failure))))
("that" "thing" "grows" "slowly")

[edit] Macro with dynamic variables

(defparameter *amb-ops* nil)
(defparameter *amb-hist* nil)
(setf *random-state* (make-random-state t))
(defun shuffle (items)
(loop for i from 0 with r = items with l = (length r) while (< i l) do
(rotatef (elt r i) (elt r (+ i (random (- l i)))))
finally (return r)))
;;; (assert '(mess in, mess out))
(defmacro amb (a &rest rest)
(let ((f (first rest))
(rest (rest rest)))
(if (not f)
`(let ((items (shuffle ,a)))
(let ((y (car (last *amb-hist*)))
(o (car (last *amb-ops*))))
(loop for x in items do
(if (or (not *amb-ops*)
(funcall o y x))
(return (append *amb-hist* (list x))))
(elt items (random (length items))))))
`(let ((items (shuffle ,a)))
(let ((y (car (last *amb-hist*)))
(o (car (last *amb-ops*))))
(loop for x in items do
(if (or (not *amb-ops*)
(funcall o y x))
(let ((*amb-hist* (append *amb-hist* (list x)))
(*amb-ops* (append *amb-ops* (list ,f))))
(let ((r ,@rest))
(if r (return r)))))))))))
;; test cases
(defun joins (a b)
(char= (char a (1- (length a))) (char b 0)))
(defun w34()
(amb '("walked" "treaded" "grows") #'joins
(amb '("slowly" "quickly"))))
(amb '("the" "that" "a") #'joins
(amb '("frog" "elephant" "thing") #'joins
(print (amb '(1 2 5) #'<
(amb '(2 3 4) #'=
(amb '(3 4 5))))) ; 1 4 4, 2 3 3, etc

[edit] D

import std.stdio, std.array;
/** This amb function takes a comparison function and
the possibilities that need to be checked.*/

//string[] amb(in bool function(in string, in string) pure comp,
const(string)[] amb(in bool function(in string, in string) pure comp,
in string[][] options,
in string prev = null) pure {
if (options.empty)
return null;
foreach (immutable opt; options.front) {
// If this is the base call, prev is null and we need to
// continue.
if (!prev.empty && !comp(prev, opt))
// Take care of the case where we have no options left.
if (options.length == 1)
return [opt];
// Traverse into the tree.
const res = amb(comp, options[1 .. $], opt);
// If it was a failure, try the next one.
if (!res.empty)
return opt ~ res; // We have a match!
return null; // No matches.
void main() {
immutable sets = [["the", "that", "a"],
["frog", "elephant", "thing"],
["walked", "treaded", "grows"],
["slowly", "quickly"]];
// Pass in the comparator and the available sets.
// (The comparator is not nothrow because of UTF.)
const result = amb((s, t) => s.back == t.front, sets);
if (result.empty)
writeln("No matches found!");
writefln("%-(%s %)", result);
that thing grows slowly

[edit] E

Some lines in this example are too long (more than 80 characters). Please fix the code if it's possible and remove this message.

E does not currently have any kind of backtracking control flow (though there is a proposal in the works to backtrack upon exceptions, for the sake of consistency). However, since (Almost) Everything Is Message Passing, we can create an object which represents a set of possible values.

This is complicated, however, by the fact that any given amb must appear to produce only one result; that is, def x := amb(["a", "b"]); x + x produces aa or bb, not aa,bb,ab,ba as amb(["a", "b"]) + amb(["a", "b"]) would. Therefore, each choice is associated with the decisions which produced it: a map from amb objects to which member of them was chosen; any combination of two ambs discards any combination of choices which have inconsistent decisions.

Note that the choices are not evaluated lazily; this is a breadth-first rather than depth-first search through possibilities. Also, every amb remembers all of the ambs which produced it. As such, this is probably not a practical system for large problems.

def [amb, unamb] := { # block hides internals
def Choice := Tuple[any, Map]
def [ambS, ambU] := <elib:sealing.makeBrand>("amb")
var counter := 0 # Used just for printing ambs
/** Check whether two sets of decisions are consistent */
def consistent(decA, decB) {
def overlap := decA.domain() & decB.domain()
for ambObj in overlap {
if (decA[ambObj] != decB[ambObj]) { return false }
return true
/** From an amb object, extract the possible choices */
def getChoices(obj, decisions) :List[Choice] {
if (decisions.maps(obj)) {
return [[decisions[obj], decisions]]
} else if (ambU.amplify(obj) =~ [[choices, _]]) {
return accum [] for [chosen, dec] ? (consistent(decisions, dec)) in choices { _ + getChoices(chosen, (decisions | dec).with(obj, chosen)) }
} else {
return [[obj, decisions]]
/** Construct an amb object with remembered decisions */
def ambDec(choices :List[Choice]) {
def serial := (counter += 1)
def ambObj {
to __printOn(out) {
out.print("<amb(", serial, ")")
for [chosen, decisions] in choices {
out.print(" ", chosen)
for k => v in decisions {
out.print(";", ambU.amplify(k)[0][1], "=", v)
to __optSealedDispatch(brand) {
if (brand == ambS.getBrand()) {
return ambS.seal([choices, serial])
match [verb, args] {
var results := []
for [rec, rdec] in getChoices(ambObj, [].asMap()) {
def expandArgs(dec, prefix, choosing) {
switch (choosing) {
match [] { results with= [, verb, prefix), dec] }
match [argAmb] + moreArgs {
for [arg, adec] in getChoices(argAmb, dec) {
expandArgs(adec, prefix.with(arg), moreArgs)
expandArgs(rdec, [], args)
return ambObj
/** Construct an amb object with no remembered decisions. (public interface) */
def amb(choices) {
return ambDec(accum [] for c in choices { _.with([c, [].asMap()]) })
/** Get the possible results from an amb object, discarding decision info. (public interface) */
def unamb(ambObj) {
return accum [] for [c,_] in getChoices(ambObj, [].asMap()) { _.with(c) }
[amb, unamb]
def join(a, b) {
# This must not use the builtin if, since it coerces to boolean rather than passing messages.
# false.pick(x, y) returns y and true.pick(x, y) returns x; we protect the amb([]) from causing
# unconditional failure by putting both options in functions.
# <=> is the comparison operator that happens to be message-based.
return (a.last() <=> b[0]).pick(fn {
a + " " + b
}, fn {
def w1 := amb(["the", "that", "a" ])
def w2 := amb(["frog", "elephant", "thing" ])
def w3 := amb(["walked", "treaded", "grows" ])
def w4 := amb(["slowly", "quickly" ])
unamb(join(join(join(w1, w2), w3), w4))

[edit] Comparison with Haskell

This can be compared with the Haskell use of lists as a monad to represent choice.

  • Haskell uses lazy evaluation; E does not. This implementation does not simulate lazy evaluation with thunks; it is eager (computes every intermediate choice before continuing) and therefore inefficient if you only need one successful result.
  • Haskell does not need to track decisions. This is because when using a monad in Haskell, the points of choice are explicitly written, either by monadic operators or combinators. The analogues to the two "ab" operations given above are: do x <- ["a","b"]; return (x ++ x) and do x <- ["a","b"]; y <- ["a","b"]; return (x ++ y) — the relevant difference being the number of <- operators. In this implementation, we instead absorb the choice into normal method calls; the Haskell analogue would be something like instance Monoid a => Monoid (Amb a) where Amb ... `mconcat` Amb ... = ..., which would have a similar need to track decisions.

[edit] Egison

; We don't need 'amb' in the code since pattern-matching of Egison automatically do backtracking.
(match-all {{"the" "that" "a"} {"frog" "elephant" "thing"} {"walked" "treaded" "grows"} {"slowly" "quickly"}} (list (multiset string))
[<cons <cons (& <snoc $c_1 _> $w_1) _>
(loop $i [2 $n]
<cons <cons (& <cons ,c_(- i 1) <snoc $c_i _>> $w_i) _> ...>
(map (lambda [$i] w_i) (between 1 n))])


{{"that" "thing" "grows" "slowly"}}

[edit] Ela

open list core
amb xs = x where
(Some x) = & join xs ""
join (x::xs) = amb' x (join xs)
join [] = \_ -> Some ""
eq' [] x = true
eq' w x = last w == head x
amb' [] _ _ = None
amb' (x::xs) n w
| eq' w x =
match n x with
Some v = Some (x ++ " " ++ v)
_ = amb' xs n w
| else = amb' xs n w


amb [

[edit] Elena

The implementation

#define system.
#define extensions.
#define extensions'routines.
// --- Joinable --
#symbol joinable = (:aFormer:aLater)
[ (aFormer @ (aFormer length - 1)) == (aLater @ 0) ].
// --- Activatora ---
#method eval : anArray
^ self eval:(anArray@0):(anArray@1).
#method eval : anArray
^ self eval:(anArray@0):(anArray@1):(anArray@2).
#method eval : anArray
^ self eval:(anArray@0):(anArray@1):(anArray@2):(anArray@3).
#method eval : anArray
^ self eval:(anArray@0):(anArray@1):(anArray@2):(anArray@3):(anArray@4).
// --- AmbValueCollection ---
#class AmbValueCollection
#field theCombinator.
#field theRole.
#constructor new : aSet1 : aSet2
theRole := Activator2.
theCombinator := CombinatorWithRepetition new:(aSet1,aSet2).
#constructor new : aSet1 : aSet2 : aSet3
theRole := Activator3.
theCombinator := CombinatorWithRepetition new:(aSet1,aSet2,aSet3).
#constructor new : aSet1 : aSet2 : aSet3 : aSet4
theRole := Activator4.
theCombinator := CombinatorWithRepetition new:(aSet1,aSet2,aSet3,aSet4).
#constructor new : aSet1 : aSet2 : aSet3 : aSet4 : aSet5
theRole := Activator5.
theCombinator := CombinatorWithRepetition new:(aSet1,aSet2,aSet3,aSet4,aSet5).
#method seek : aCondition
theCombinator reset.
control while:[ theCombinator next ] &do:
aCondition~theRole eval:(theCombinator get) ?
[ #break nil. ].
#method do : aFunction
#var aResult := theCombinator get.
nil != aResult
 ? [ aFunction~theRole eval:aResult. ]
 ! [ #throw InvalidArgumentException new. ].
// --- ambOperator ---
#symbol ambOperator =
for : aSet1 : aSet2
= AmbValueCollection new:aSet1:aSet2.
for : aSet1 : aSet2 : aSet3
= AmbValueCollection new:aSet1:aSet2:aSet3.
for : aSet1 : aSet2 : aSet3 : aSet4
= AmbValueCollection new:aSet1:aSet2:aSet3:aSet4.
for : aSet1 : aSet2 : aSet3 : aSet4 : aSet5
= AmbValueCollection new:aSet1:aSet2:aSet3:aSet4:aSet5.
// --- Program ---
#symbol program =
ambOperator for:(1,2,4):(4,5,6) seek: (:a:b) [ a * b == 8 ] do: (:a:b)
[ consoleEx writeLine: a : " * " : b : " = 8" ]
| if &InvalidArgumentError: e [ consoleEx writeLine:"AMB is angry". ].
for:("the","that","a"):("frog", "elephant", "thing"):("walked", "treaded", "grows"):("slowly", "quickly")
seek: (:a:b:c:d) [ (joinable:a:b) and:(joinable:b:c) and:(joinable:c:d) ]
do: (:a:b:c:d) [ consoleEx writeLine:a:" ":b:" ":c:" ":d. ]
| if &InvalidArgumentError: e [ consoleEx writeLine:"AMB is angry". ].

[edit] Factor

USING: backtrack continuations kernel prettyprint sequences ;
IN: amb
CONSTANT: words {
{ "the" "that" "a" }
{ "frog" "elephant" "thing" }
{ "walked" "treaded" "grows" }
{ "slowly" "quickly" }
: letters-match? ( str1 str2 -- ? ) [ last ] [ first ] bi* = ;
: sentence-match? ( seq -- ? ) dup rest [ letters-match? ] 2all? ;
: select ( seq -- seq' ) [ amb-lazy ] map ;
: search ( -- )
words select dup sentence-match? [ " " join ] [ fail ] if . ;
MAIN: search

Running it from the listener :

( scratchpad ) "amb" run
"that thing grows slowly"

[edit] F#

Translation of: Haskell

Important differences to the Haskell solution:

  • The list monad is not predefined in F#. (But it is easy to define it.)
  • F# is not lazy, so this will check all combinations even if we just want one solution.

Both problems could be addressed by using sequence expressions instead.

// define the List "workflow" (monad)
type ListBuilder() =
member o.Bind( lst, f ) = List.concat( (fun x -> f x) lst )
member o.Return( x ) = [x]
member o.Zero() = []
let list = ListBuilder()
let amb = id
// last element of a sequence
let last s = Seq.nth ((Seq.length s) - 1) s
// is the last element of left the same as the first element of right?
let joins left right = last left = Seq.head right
let example = list { let! w1 = amb ["the"; "that"; "a"]
let! w2 = amb ["frog"; "elephant"; "thing"]
let! w3 = amb ["walked"; "treaded"; "grows"]
let! w4 = amb ["slowly"; "quickly"]
if joins w1 w2 &&
joins w2 w3 &&
joins w3 w4
return String.concat " " [w1; w2; w3; w4]
printfn "%s" (List.head example)

[edit] Go

Solution with goroutines. See description on talk page.

package main
import (
func ambStrings(ss []string) chan []string {
c := make(chan []string)
go func() {
for _, s := range ss {
c <- []string{s}
return c
func ambChain(ss []string, cIn chan []string) chan []string {
cOut := make(chan []string)
go func() {
var w sync.WaitGroup
for chain := range cIn {
go func(chain []string) {
for s1 := range ambStrings(ss) {
if s1[0][len(s1[0])-1] == chain[0][0] {
cOut <- append(s1, chain...)
return cOut
func main() {
s1 := []string{"the", "that", "a"}
s2 := []string{"frog", "elephant", "thing"}
s3 := []string{"walked", "treaded", "grows"}
s4 := []string{"slowly", "quickly"}
c := ambChain(s1, ambChain(s2, ambChain(s3, ambStrings(s4))))
for s := range c {
[that thing grows slowly]

Alternative solution:

package main
import "fmt"
func amb(wordsets [][]string, res []string) bool {
if len(wordsets) == 0 {
return true
var s string
l := len(res)
if l > 0 { s = res[l - 1] }
res = res[0:len(res) + 1]
for _, res[l] = range(wordsets[0]) {
if l > 0 && s[len(s) - 1] != res[l][0] { continue }
if amb(wordsets[1:len(wordsets)], res) {
return true
return false
func main() {
wordset := [][]string { { "the", "that", "a" },
{ "frog", "elephant", "thing" },
{ "walked", "treaded", "grows" },
{ "slowly", "quickly" } }
res := make([]string, len(wordset))
if amb(wordset, res[0:0]) {
} else {
fmt.Println("No amb found")

[edit] Haskell

Haskell's List monad returns all the possible choices. Use the "head" function on the result if you just want one.

import Control.Monad
amb = id
joins left right = last left == head right
example = do
w1 <- amb ["the", "that", "a"]
w2 <- amb ["frog", "elephant", "thing"]
w3 <- amb ["walked", "treaded", "grows"]
w4 <- amb ["slowly", "quickly"]
unless (joins w1 w2) (amb [])
unless (joins w2 w3) (amb [])
unless (joins w3 w4) (amb [])
return (unwords [w1, w2, w3, w4])

Note that "amb" is defined as a no-op and is written only to help show the analogy with other implementations; ordinary style is to write e.g. w1 <- ["the", "that", "a"].

[edit] Haxe

class RosettaDemo
static var setA = ['the', 'that', 'a'];
static var setB = ['frog', 'elephant', 'thing'];
static var setC = ['walked', 'treaded', 'grows'];
static var setD = ['slowly', 'quickly'];
static public function main()
Sys.print(ambParse([ setA, setB, setC, setD ]).toString());
static function ambParse(sets : Array<Array<String>>)
var ambData : Dynamic = amb(sets);
for (data in 0...ambData.length)
var tmpData = parseIt(ambData[data]);
var tmpArray = tmpData.split(' ');
if (tmpArray.length == sets.length)
return tmpData;
return '';
static function amb(startingWith : String = '', sets : Array<Array<String>>) : Dynamic
if (sets.length == 0 || sets[0].length == 0) return;
var match : Dynamic = [];
for (reference in sets[0])
if (startingWith == '' || startingWith == reference.charAt(0))
var lastChar = reference.charAt(reference.length-1);
if (, sets.slice(1)), Array))
match.push([ reference, amb(lastChar, sets.slice(1))]);
match.push([ reference ]);
return match;
static function parseIt(data : Dynamic)
var retData = '';
if (, Array))
for (elements in
if ([elements], Array))
retData = retData + parseIt(data[elements]);
retData = retData + data[elements] + ' ';
return retData;

[edit] Icon and Unicon

procedure main()
s1 := ["the","that","a"]
s2 := ["frog","elephant","thing"]
s3 := ["walked","treaded","grows"]
s4 := ["slowly","quickly"]
procedure amb(exprs[])
s := ""
every e := !exprs do {
if \c ~== e[1] then fail
c := e[-1]
s ||:= e || " "
return s

[edit] J

   amb=. ([ , ' ' , ])&>/&.>@:((({:@:[ = {.@:])&>/&> # ])@:,@:({@(,&<)))
>@(amb&.>/) ('the';'that';'a');('frog';'elephant';'thing');('walked';'treaded';'grows');(<'slowly';'quickly')
|that thing grows slowly|

amb is a dyadic verb:

   ('the';'that';'a') amb ('frog';'elephant';'thing') amb ('walked';'treaded';'grows') amb ('slowly';'quickly')
|that thing grows slowly|

A structured derivation of amb follows:

   NB. Dynamic programming method...
o=. @: NB. Composing verbs
success=. {:o[ = {.o] NB. Is the last letter of the left word equal to the first of the right?
join=. [ , ' ' , ] NB. Joining the left and right words
cp=. {@(,&<) NB. Cartesian product
amb=. join&>/&.> o ((success&>/ &> # ]) o , o cp)f.
amb NB. Showing the point-free code...
([ , ' ' , ])&>/&.>@:((({:@:[ = {.@:])&>/&> # ])@:,@:({@(,&<)))

[edit] JavaScript

function ambRun(func) {
var choices = [];
var index;
function amb(values) {
if (values.length == 0) {
if (index == choices.length) {
choices.push({i: 0,
count: values.length});
var choice = choices[index++];
return values[choice.i];
function fail() { throw fail; }
while (true) {
try {
index = 0;
return func(amb, fail);
} catch (e) {
if (e != fail) {
throw e;
var choice;
while ((choice = choices.pop()) && ++choice.i == choice.count) {}
if (choice == undefined) {
return undefined;
ambRun(function(amb, fail) {
function linked(s1, s2) {
return s1.slice(-1) == s2.slice(0, 1);
var w1 = amb(["the", "that", "a"]);
var w2 = amb(["frog", "elephant", "thing"]);
if (!linked(w1, w2)) fail();
var w3 = amb(["walked", "treaded", "grows"]);
if (!linked(w2, w3)) fail();
var w4 = amb(["slowly", "quickly"]);
if (!linked(w3, w4)) fail();
return [w1, w2, w3, w4].join(' ');
}); // "that thing grows slowly"

[edit] Lua

function amb (set)
local workset = {}
if (#set == 0) or (type(set) ~= 'table') then return end
if #set == 1 then return set end
if #set > 2 then
local first = table.remove(set,1)
set = amb(set)
for i,v in next,first do
for j,u in next,set do
if v:byte(#v) == u[1]:byte(1) then table.insert(workset, {v,unpack(u)}) end
return workset
for i,v in next,set[1] do
for j,u in next,set[2] do
if v:byte(#v) == u:byte(1) then table.insert(workset,{v,u}) end
return workset

Usage example:

result = amb({{'the','that','a'},{'frog','elephant','thing'},{'walked','treaded','grows'},{'slowly','quickly'}})
for i,v in next,result do
io.write (i,':\t')
for j,u in next,v do
io.write (u,' ')
io.write ('\n')

[edit] Mathematica

Make all the tuples of all the lists, then filter out the good ones:


gives back:

{{"that", "thing", "grows", "slowly"}}

Note that it will return multiple values if multiple sentences match the requirement, that is why the returned value is a list of list (1 element, 4 elements).

Alternative algorithm (slightly faster on most data sets):

CheckValid2[i_List] := StringFreeQ[StringJoin[Riffle[i, ","]], a_ ~~ "," ~~ b_ /; a =!= b]

[edit] Mercury

Like Prolog, Mercury has built-in nondeterminacy; however, Mercury is explicit about it, and statically checks it.

:- module amb.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
:- implementation.
:- import_module list, string, char, int.
main(!IO) :-
( solution(S) -> io.write_string(S, !IO),!IO)
 ; io.write_string("No solutions found :-(\n", !IO) ).
:- pred solution(string::out) is nondet.
solution(S) :-
member(A, ["the", "that", "a"]),
member(N, ["frog", "elephant", "thing"]),
member(V, ["walked", "treaded", "grows"]),
member(E, ["slowly", "quickly"]),
S = join_list(" ", [A, N, V, E]),
rule1(A, N), rule1(N, V), rule1(V, E).
:- pred rule1(string::in, string::in) is semidet.
rule1(A, B) :- last_char(A) = C, first_char(B, C, _).
:- func last_char(string::in) = (char::out) is semidet.
last_char(S) = C :- index(S, length(S) - 1, C).

The Amb defined in the Prolog solution is similar to the use of list.member/2 above. Predicates could be used instead:

:- pred noun(string).
:- mode noun(out) is multi.  % provide any one noun.
:- mode noun(in) is semidet.  % fail if given string isn't a known noun.

[edit] NetRexx

 /* REXX **************************************************************
* 25.08.2013 Walter Pachl derived from REXX version 2

mkset(1,'the that a if',w,mm,l)
mkset(2,'frog elephant thing',w,mm,l)
mkset(3,'walked treaded grows trots',w,mm,l)
mkset(4,'slowly quickly',w,mm,l)
Loop i=1 to 3 /* loop over sets */
k=i+1 /* the following set */
Loop ii=1 To 10 /* loop over elements in set k*/
If w[i,ii].words=i Then Do /* a sentence part found */
Loop jj=1 To 10 /* loop over following words */
If w[i,ii].right(1)=w[k,jj].left(1) Then Do /* fitting */
ns=w[i,ii]' 'w[k,jj] /* build new sentence (part) */
If ns.words=k Then /* 'complete' part */
add(w,k,ns) /* add to set k */
Say 'Results:'
Loop jj=1 To 10 /* show the results */
If w[4,jj].words=4 Then
Say '-->' w[4,jj]
method add(w,k,s) public static
* add a fitting sentence (part) s to set w[k,*]

Loop i=1 To 10 While w[k,i]>'' /* look for an empty slot */
w[k,i]=s /* add the sentence (part) */
method mkset(n,arg,smp,mm,l) public static
* create set smp[n,*] from data in arg
* mm[0] maximum number of elements in any set
* l[n] maximum word length in set n

loop i = 1 to arg.words
smp[n,i] = arg.word(i)
If smp[n,i].length>l[n] Then
if i-1>mm[0] Then Do
method show(w,mm,l) public static
* show the input

Say 'Input:'
Loop j=1 To mm[0] /* output lines */
Loop i=1 To 4
ol=ol w[i,j].left(l[i])
Say ol.strip
say ''


the    frog     walked  slowly
that   elephant treaded quickly
a      thing    grows
if              trots

--> the elephant trots slowly
--> that thing grows slowly
--> if frog grows slowly

Note: the output of the input is truncated (columns three and four), but the results are correct for the data specified, but not for the input as specified for this task (ditto for the PL/I example and the REXX version 2 example).
length corrected. thanks. extraneous input: intentional and harmless !?!

[edit] Nimrod

Translation of: D
import future, strutils
proc amb(comp: proc(a, b: string): bool, options: seq[seq[string]],
prev: string = nil): seq[string] =
if options.len == 0: return @[]
for opt in options[0]:
# If this is the base call, prev is nil and we need to continue.
if prev != nil and not comp(prev, opt): continue
# Take care of the case where we have no options left.
if options.len == 1: return @[opt]
# Traverse into the tree.
let res = amb(comp, options[1..options.high], opt)
# If it was a failure, try the next one.
if res.len > 0: return opt & res # We have a match
return @[]
const sets = @[@["the", "that", "a"],
@["frog", "elephant", "thing"],
@["walked", "treaded", "grows"],
@["slowly", "quickly"]]
let result = amb((s, t: string) => (s[s.high] == t[0]), sets)
if result.len == 0:
echo "No matches found!"
echo result.join " "


that thing grows slowly

[edit] OCaml

There is no Amb operator in OCaml. So below are two solutions to solve the same task. The first one is the more idiomatic for OCaml (and is similar to the Haskell solution), it builds all possible combinations and then take the good result in it.

The second solution tries to be closer to the way of solving the problem of Amb. It does not build and accumulate the combinations, it iterates over these with a higher order function and it stops when it finds a solution that matches the predicate.

[edit] Filtering possible combinations

let set_1 = ["the"; "that"; "a"]
let set_2 = ["frog"; "elephant"; "thing"]
let set_3 = ["walked"; "treaded"; "grows"]
let set_4 = ["slowly"; "quickly"]
let combs ll =
let rec aux acc = function
| [] -> ( List.rev acc)
| hd::tl ->
let acc =
(fun _ac l ->
List.fold_left (fun _ac v -> (v::l)::_ac) _ac hd
) [] acc
aux acc tl
aux [[]] ll
let last s = s.[pred(String.length s)]
let joined a b = (last a = b.[0])
let rec test = function
| a::b::tl -> (joined a b) && (test (b::tl))
| _ -> true
let print_set set =
List.iter (Printf.printf " %s") set;
let () =
let sets = combs [set_1; set_2; set_3; set_4] in
let sets = List.filter test sets in
List.iter print_set sets;

We can take all the good results with List.filter or just take the first one with List.find.

[edit] Higher order function

Here the function comb_search replaces the function combs and uses arrays instead of lists. This function takes successively all the possible results by their indicies (with the array nx). When a result satisfies the predicate p, it is returned

let set_1 = [| "the"; "that"; "a" |]
let set_2 = [| "frog"; "elephant"; "thing" |]
let set_3 = [| "walked"; "treaded"; "grows" |]
let set_4 = [| "slowly"; "quickly" |]
let comb_search p aa =
let nx = Array.make (Array.length aa) 0 in
let lx = Array.length aa in
let la = Array.length aa in
let rec loop() =
let res = Array.mapi (fun i j -> aa.(i).(j)) nx in
if p res then (res)
( nx.(0) <- nx.(0) + 1;
if nx.(0) < lx.(0)
then loop()
( nx.(0) <- 0;
let rec roll n =
if n >= la then raise Not_found
( nx.(n) <- nx.(n) + 1;
if nx.(n) >= lx.(n)
then ( nx.(n) <- 0; roll (n+1) )
else loop()
roll 1
let last s = s.[pred(String.length s)]
let joined a b = (last a = b.[0])
let rec test = function
| a::b::tl -> (joined a b) && (test (b::tl))
| _ -> true
let test r = test(Array.to_list r)
let print_set set =
Array.iter (Printf.printf " %s") set;
let () =
let result = comb_search test [| set_1; set_2; set_3; set_4 |] in
print_set result;

[edit] OpenEdge/Progress

i_cwords AS CHAR,
i_iset AS INT
DEF VAR cresult AS CHAR.
DO ii = 1 TO NUM-ENTRIES( cset [ i_iset ] ) WHILE NUM-ENTRIES( cresult, " " ) < EXTENT( cset ):
cword = ENTRY( ii, cset[ i_iset ] ).
IF i_cwords = "" OR
SUBSTRING( i_cwords, LENGTH( i_cwords ), 1 ) = SUBSTRING( cword, 1, 1 )
IF i_iset = EXTENT ( cset ) THEN
cresult = i_cwords + " " + cword.
cresult = getAmb( i_cwords + " " + cword, i_iset + 1 ).
RETURN cresult.
END FUNCTION. /* getAmb */


 that thing grows slowly

[edit] Oz

Oz is, among other things, a logic programming language and has a choice operator. Using recursion we can easily build an Amb operator with it.

fun {Amb Xs}
case Xs of nil then fail
[] [X] then X
[] X|Xr then
choice X
[] {Amb Xr}
fun {Example}
W1 = {Amb ["the" "that" "a"]}
W2 = {Amb ["frog" "elephant" "thing"]}
W3 = {Amb ["walked" "treaded" "grows"]}
W4 = {Amb ["slowly" "quickly"]}
{List.last W1 W2.1}
{List.last W2 W3.1}
{List.last W3 W4.1}
W1#" "#W2#" "#W3#" "#W4
{ForAll {SearchAll Example} System.showInfo}

In Oz, the programmer explicitly controls how a logic program is executed (search strategy, number of required solutions, laziness, which physical machines are used for the search process...). In this case we use the predefined function SearchAll to eagerly calculate all possible solution. All work is done within the current process.

[edit] PARI/GP

if (#V == 0, return(concat(s)));
if(#s, s = concat(s,[" "]));
if ((#s == 0 | final == v[i][1]),
t = amb(U, concat(s, v[i]));
if (t, return(t))

[edit] Perl

This first perl implementation of the amb operator provides an interface which satisfies the terms of the task PRECISELY. I would NOT, however, suggest using it in real code, unless you know for a fact that the computer you are using it on has a very lightweight fork() system call.

I provide this simply to demonstrate that it CAN be done.

use strict;
use warnings;
use constant EXIT_FAILURE => 1;
use constant EXIT_SUCCESS => 0;
sub amb {
exit(EXIT_FAILURE) if !@_;
for my $word (@_) {
my $pid = fork;
die $! unless defined $pid;
return $word if !$pid;
my $wpid = waitpid $pid, 0;
die $! unless $wpid == $pid;
sub joined {
my ($join_a, $join_b) = @_;
substr($join_a, -1) eq substr($join_b, 0, 1);
my $w1 = amb(qw(the that a));
my $w2 = amb(qw(frog elephant thing));
my $w3 = amb(qw(walked treaded grows));
my $w4 = amb(qw(slowly quickly));
amb() unless joined $w1, $w2;
amb() unless joined $w2, $w3;
amb() unless joined $w3, $w4;
print "$w1 $w2 $w3 $w4\n";

The main purpose of the amb() operator is backtracking, and the preferred perl idiom for that purpose is for the user to pass a subroutine of their own into a function which acts as a backtracking engine.

The following code does just that: the first arguments for amb(...) are one or more arrays of values, followed by a user-defined subroutine. The amb(...) function arbitrarily selects one value from each of the arrays, and calls the user's supplied sub with the selected values.

If the user's supplied sub calls amb() with no arguments, the outer amb(...) will pick the next set of values. If the user's supplied sub returns normally, then the return value from the sub will be the return value of amb(...).

This version uses vastly less memory, and is quite reusable.

use strict;
use warnings;
sub amb {
if( @_ == 0 ) {
no warnings 'exiting';
next AMB;
my $code = pop;
my @words = @_;
my @index = (0) x @words;
AMB: while( 1 ) {
my @w = map $words[$_][$index[$_]], 0 .. $#_;
return $code->( @w );
} continue {
my $i = 0;
while( ++$index[$i] == @{$words[$i]} ) {
$index[$i] = 0;
return if ++$i == @index;
my @w1 = qw(the that a);
my @w2 = qw(frog elephant thing);
my @w3 = qw(walked treaded grows);
my @w4 = qw(slowly quickly);
sub joined {
my ($join_a, $join_b) = @_;
substr($join_a, -1) eq substr($join_b, 0, 1);
amb( \(@w1, @w2, @w3, @w4), sub {
my ($w1, $w2, $w3, $w4) = @_;
amb() unless joined($w1, $w2);
amb() unless joined($w2, $w3);
amb() unless joined($w3, $w4);
print "$w1 $w2 $w3 $w4\n";

Both versions produce the same output.


that thing grows slowly

[edit] Perl 6

Works with: niecza version 2012-02-29
sub infix:<lf> ($a,$b) {
next unless try $a.substr(*-1,1) eq $b.substr(0,1);
"$a $b";
multi dethunk(Callable $x) { try take $x() }
multi dethunk( Any $x) { take $x }
sub amb (*@c) { gather @c».&dethunk }
say first *, do
amb(<the that a>, { die 'oops'}) Xlf
amb('frog',{'elephant'},'thing') Xlf
amb(<walked treaded grows>) Xlf
amb { die 'poison dart' },
{ die 'fire' };
that thing grows slowly

This uses lazy lists, created by the X metaoperator applied to a user-defined function, lf, that asserts the last-first condition, and short-circuits the match so that it does not need to generate parts of the search tree that cannot match. We use the first function to pull one element from the lazy list; a subscript of [0] would have worked just as well.

The amb operator itself uses a hyper to run the dethunk calls in parallel. Results are returned asyncronously via gather/take. The dethunk call traps failures after the failure has bypassed the take.

If you consider lazy lists to be cheating on the idea of continuations, here's some admittedly grungy code that uses the continuation engine of regexes to solve it. At some point we'll wrap this up in nice syntax to let people write in a sublanguage of Perl 6 that looks more like a logic language.

sub amb($var,*@a) {
@a.pick(*).map: {"
||\{ $var = '$_' }"}
'' ~~ m/
:my ($a,$b,$c,$d);
<{ amb '$a', <the that a> }>
<{ amb '$b', <frog elephant thing> }>
<?{ substr($a,*-1,1) eq substr($b,0,1) }>
<{ amb '$c', <walked treaded grows> }>
<?{ substr($b,*-1,1) eq substr($c,0,1) }>
<{ amb '$d', <slowly quickly> }>
<?{ substr($c,*-1,1) eq substr($d,0,1) }>
{ say "$a $b $c $d" }

[edit] PicoLisp

For backtracking, Pilog (PicoLisp Prolog) is the natural choice.

Translation of: Prolog
(be amb (@E @Lst)
(lst @E @Lst) )
(be joins (@Left @Right)
(^ @T (last (chop (-> @Left))))
(^ @R (car (chop (-> @Right))))
((equal @T @R))
((amb @ NIL)) ) ) # Explicitly using amb fail as required
(be ambExample ((@Word1 @Word2 @Word3 @Word4))
(amb @Word1 ("the" "that" "a"))
(amb @Word2 ("frog" "elephant" "thing"))
(amb @Word3 ("walked" "treaded" "grows"))
(amb @Word4 ("slowly" "quickly"))
(joins @Word1 @Word2)
(joins @Word2 @Word3)
(joins @Word3 @Word4) )


: (? (ambExample @Result))
 @Result=("that" "thing" "grows" "slowly")
-> NIL

[edit] PL/I

*process or(!) source attributes xref;
amb: Proc Options(main);
* 25.08.2013 Walter Pachl

Dcl w(4,10) Char(40) Var
Init('the','that','a','if',(6)(1)' ',
'frog','elephant','thing',(7)(1)' ',
'walked','treaded','grows','trots',(6)(1)' ',
'slowly','quickly',(8)(1)' ');
Dcl ns Char(40) Var;
Dcl (i,k,j,ii,jj,m,n) Bin Fixed(31);
n=hbound(w,1); /* number of sets */
m=hbound(w,2); /* max number of words in set */
Call show; /* show the input */
Do i=1 To n-1; /* loop over sets */
k=i+1; /* the following set */
Do ii=1 To m; /* loop over elements in set k*/
If words(w(i,ii))=i Then Do; /* a sentence part found */
Do jj=1 To m; /* loop over following words */
If right(w(i,ii),1)=left(w(k,jj),1) Then Do; /* fitting */
ns=w(i,ii)!!' '!!w(k,jj); /* build new sentence (part) */
If words(ns)=k Then /* 'complete' part */
Call add(k,ns); /* add to set k */
Do jj=1 To m; /* show the results */
If words(w(4,jj))=4 Then
put edit('--> ',w(4,jj))(Skip,a,a);
add: Proc(ni,s);
* add a sentence (part) to set ni

Dcl (i,ni) Bin Fixed(31);
Dcl s Char(40) Var;
Do i=1 To m While(w(ni,i)>''); /* look for an empty slot */
w(ni,i)=s; /* add the sentence (part) */
words: Proc(s) Returns(Bin Fixed(31));
* return the number of blank separated words in s

Dcl s Char(40) Var;
Dcl nw Bin Fixed(31) Init(0);
Dcl i Bin Fixed(31) Init(1);
If s>'' Then Do;
Do i=1 To length(s);
If substr(s,i,1)=' ' Then
show: Proc;
* show the input sets

Dcl (i,j,mm) Bin Fixed(31) Init(0);
Dcl l(4) Bin Fixed(31) Init((4)0);
Do i=1 To n;
Do j=1 To m;
If w(i,j)>'' Then Do;
mm=max(mm,j); /* max number of words in any set */
l(i)=max(l(i),length(w(i,j))); /* max word length in set i */
Put Edit('Input:')(Skip,a);
Do j=1 To mm; /* output lines */
Put Skip;
Do i=1 To n;
Put Edit(w(i,j),' ')(a(l(i)),a);
Put Skip;


Input: (extended by 2 words!)
the  frog     walked  slowly
that elephant treaded quickly
a    thing    grows
if            trots

--> the elephant trots slowly
--> that thing grows slowly
--> if frog grows slowly     

[edit] Prolog

amb(E, [E|_]).
amb(E, [_|ES]) :- amb(E, ES).
joins(Left, Right) :-
append(_, [T], Left),
append([R], _, Right),
( T \= R -> amb(_, []) % (explicitly using amb fail as required)
; true ).
amb_example([Word1, Word2, Word3, Word4]) :-
amb(Word1, ["the","that","a"]),
amb(Word2, ["frog","elephant","thing"]),
amb(Word3, ["walked","treaded","grows"]),
amb(Word4, ["slowly","quickly"]),
joins(Word1, Word2),
joins(Word2, Word3),
joins(Word3, Word4).

[edit] PureBasic

Procedure Words_Ok(String1.s, String2.s)
If Mid(String1,Len(String1),1)=Mid(String2,1,1)
ProcedureReturn #True
ProcedureReturn #False
Procedure.s Amb(Array A.s(1), Array B.s(1), Array C.s(1), Array D.s(1))
Protected a, b, c, d
For a=0 To ArraySize(A())
For b=0 To ArraySize(B())
For c=0 To ArraySize(C())
For d=0 To ArraySize(D())
If Words_Ok(A(a),B(b)) And Words_Ok(B(b),C(c)) And Words_Ok(C(c),D(d))
ProcedureReturn A(a)+" "+B(b)+" "+C(c)+" "+D(d)
ProcedureReturn "" ; Empty string, e.g. fail
If OpenConsole()
Define Text.s
Dim Set1.s(2)
Dim Set2.s(2)
Dim Set3.s(2)
Dim Set4.s(1)
Set1(0)="the": set1(1)="that": set1(2)="a"
Set2(0)="frog": set2(1)="elephant": set2(2)="thing"
Set3(0)="walked": set3(1)="treaded": set3(2)="grows"
Set4(0)="slowly": set4(1)="quickly"
If Text<>""
PrintN("Correct sentence would be,"+#CRLF$+Text)
PrintN("Failed to fine a correct sentence.")
PrintN(#CRLF$+#CRLF$+"Press ENTER to exit."): Input()

[edit] Python

(Note: The code is also imported and used as a module in the solution to this task).

Python does not have the amb function, but the declarative style of programming and the use of the one "function" to do all three tasks of:

  • Setting ranges
  • Setting the constraint
  • Iterating over all solutions

can be done in what appears to be a declarative manner with the following class Amb:

import itertools as _itertools
class Amb(object):
def __init__(self):
self._names2values = {} # set of values for each global name
self._func = None # Boolean constraint function
self._valueiterator = None # itertools.product of names values
self._funcargnames = None # Constraint parameter names
def __call__(self, arg=None):
if hasattr(arg, '__code__'):
## Called with a constraint function.
globls = arg.__globals__ if hasattr(arg, '__globals__') else arg.func_globals
# Names used in constraint
argv = arg.__code__.co_varnames[:arg.__code__.co_argcount]
for name in argv:
if name not in self._names2values:
assert name in globls, \
"Global name %s not found in function globals" % name
self._names2values[name] = globls[name]
# Gather the range of values of all names used in the constraint
valuesets = [self._names2values[name] for name in argv]
self._valueiterator = _itertools.product(*valuesets)
self._func = arg
self._funcargnames = argv
return self
elif arg is not None:
## Assume called with an iterable set of values
arg = frozenset(arg)
return arg
## blank call tries to return next solution
return self._nextinsearch()
def _nextinsearch(self):
arg = self._func
globls = arg.__globals__
argv = self._funcargnames
found = False
for values in self._valueiterator:
if arg(*values):
# Set globals.
found = True
for n, v in zip(argv, values):
globls[n] = v
if not found: raise StopIteration
return values
def __iter__(self):
return self
def __next__(self):
return self()
next = __next__ # Python 2
if __name__ == '__main__':
if True:
amb = Amb()
print("\nSmall Pythagorean triples problem:")
x = amb(range(1,11))
y = amb(range(1,11))
z = amb(range(1,11))
for _dummy in amb( lambda x, y, z: x*x + y*y == z*z ):
print ('%s %s %s' % (x, y, z))
if True:
amb = Amb()
print("\nRosetta Code Amb problem:")
w1 = amb(["the", "that", "a"])
w2 = amb(["frog", "elephant", "thing"])
w3 = amb(["walked", "treaded", "grows"])
w4 = amb(["slowly", "quickly"])
for _dummy in amb( lambda w1, w2, w3, w4: \
w1[-1] == w2[0] and \
w2[-1] == w3[0] and \
w3[-1] == w4[0] ):
print ('%s %s %s %s' % (w1, w2, w3, w4))
if True:
amb = Amb()
print("\nAmb problem from "
x = amb([1, 2, 3])
y = amb([4, 5, 6])
for _dummy in amb( lambda x, y: x * y != 8 ):
print ('%s %s' % (x, y))

Sample output:

Small Pythagorean triples problem:
3 4 5
4 3 5
6 8 10
8 6 10

Rosetta Code Amb problem:
that thing grows slowly

Amb problem from
1 4
1 5
1 6
2 5
2 6
3 4
3 5
3 6

[edit] R

A brute force approach that depends on the expand.grid() function, which generates all possible paths through a list of vectors:

checkSentence <- function(sentence){
# Input: character vector
# Output: whether the sentence formed by the elements of the vector is valid
for (index in 1:(length(sentence)-1)){
first.word <- sentence[index]
second.word <- sentence[index+1]
last.letter <- substr(first.word, nchar(first.word), nchar(first.word))
first.letter <- substr(second.word, 1, 1)
if (last.letter != first.letter){ return(FALSE) }
amb <- function(sets){
# Input: list of character vectors containing all sets to consider
# Output: list of character vectors that are valid
all.paths <- apply(expand.grid(sets), 2, as.character)
all.paths.list <- split(all.paths, 1:nrow(all.paths))
winners <- all.paths.list[sapply(all.paths.list, checkSentence)]

Some sample output:

sentence1 <- c("that", "thing", "grows", "slowly")
sentence2 <- c("rosetta", "code", "is", "cool")
sentence <- list(sentence1, sentence2)
sapply(sentence, checkSentence)
set1 <- c("the", "that", "a")
set2 <- c("frog", "elephant", "thing")
set3 <- c("walked", "treaded", "grows")
set4 <- c("slowly", "quickly")
sets <- list(set1, set2, set3, set4)
[1] "that" "thing" "grows" "slowly"

[edit] Racket

#lang racket
;; A quick `amb' implementation (same as in the Twelve Statements task)
(define failures null)
(define (fail)
(if (pair? failures) ((first failures)) (error "no more choices!")))
(define (amb/thunks choices)
(let/cc k (set! failures (cons k failures)))
(if (pair? choices)
(let ([choice (first choices)]) (set! choices (rest choices)) (choice))
(begin (set! failures (rest failures)) (fail))))
(define-syntax-rule (amb E ...) (amb/thunks (list (lambda () E) ...)))
(define (assert condition) (unless condition (fail)))
;; Problem solution
(define (joins? left right)
(regexp-match? #px"(.)\0\\1" (~a left "\0" right)))
(let ([result (list (amb "the" "that" "a")
(amb "frog" "elephant" "thing")
(amb "walked" "treaded" "grows")
(amb "slowly" "quickly"))])
(for ([x result] [y (cdr result)]) (assert (joins? x y)))
;; -> '("that" "thing" "grows" "slowly")

[edit] REXX

[edit] version 1

An assumption was made that lowercase and uppercase (Latin) letters are considered a match.

/*REXX program demonstrates Amd operator, choosing a word from each set.*/
@.= /*default value for any # of sets*/
@.1 = "the that a"
@.2 = "frog elephant thing"
@.3 = "walked treaded grows"
@.4 = "slowly quickly"
do j=1 until @.j==''; end; @.0=j-1 /*set @.0 to the number of sets.*/
call Amb 1 /*find combo of words that works.*/
exit /*stick a fork in it, we're done.*/
/*─────────────────────────────────────AMB procedure────────────────────*/
Amb: procedure expose @.; parse arg # _; arg . u; if #=='' then return
if #>@.0 then do; if u=='' then return /*return if no words are left. */
w=word(u,1) /*use upper case version of word.*/
do n=2 to words(u); c=word(u,n)
if left(c,1)\==right(w,1) then return; w=c
end /*n*/
say strip(_) /* _ has an extra leading blank. */
do k=1 for words(@.#)
call amb #+1 _ word(@.#,k) /*generate the next combination. */
end /*k*/


that thing grows slowly

[edit] version 2

 /* REXX **************************************************************
* 25.08.2013 Walter Pachl derived from PL/I

Call mkset 1,'the that a if'
Call mkset 2,'frog elephant thing'
Call mkset 3,'walked treaded grows trots'
Call mkset 4,'slowly quickly'
Call show
Do i=1 to 3 /* loop over sets */
Call showm
k=i+1 /* the following set */
Do ii=1 To 10 /* loop over elements in set k*/
If words(w.i.ii)=i Then Do /* a sentence part found */
Do jj=1 To 10 /* loop over following words */
If right(w.i.ii,1)=left(w.k.jj,1) Then Do /* fitting */
ns=w.i.ii' 'w.k.jj /* build new sentence (part) */
If words(ns)=k Then /* 'complete' part */
Call add k,ns /* add to set k */
Do jj=1 To 10 /* show the results */
If words(w.4.jj)=4 Then
Say '-->' w.4.jj
add: Procedure Expose w.
* add a sentence (part) to set ni

Parse Arg ni,s
Do i=1 To 10 While>'' /* look for an empty slot */
End /* add the sentence (part) */
mkset: Procedure Expose w. mm l.
* initialize the sets

Parse Arg i,wl
Do j=1 By 1 While wl<>''
Parse Var wl w.i.j wl
show: Procedure Expose w. mm l.
* show the input

Say 'Input:'
Do j=1 To mm /* output lines */
Do i=1 To 4
ol=ol left(w.i.j,l.i)
Say strip(ol)
say ''
showm: Procedure Expose w.
* show the sets' contents

If dbg Then Do
Do i=1 To 4
Do j=1 To 10
If w.i.j>'' Then
Say i j w.i.j

Output: identical to PL/I's

[edit] Ruby

class Amb
class ExhaustedError < RuntimeError; end
def initialize
@fail = proc { fail ExhaustedError, "amb tree exhausted" }
def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
if choice.respond_to? :call
def failure
def assert(cond)
failure unless cond
A =
w1 = A.choose("the", "that", "a")
w2 = A.choose("frog", "elephant", "thing")
w3 = A.choose("walked", "treaded", "grows")
w4 = A.choose("slowly", "quickly")
A.choose() unless w1[-1] == w2[0]
A.choose() unless w2[-1] == w3[0]
A.choose() unless w3[-1] == w4[0]
puts w1, w2, w3, w4

[edit] Scala

object Amb {
def amb(wss: List[List[String]]): Option[String] = {
def _amb(ws: List[String], wss: List[List[String]]): Option[String] = wss match {
case Nil => ((Some(ws.head): Option[String]) /: ws.tail)((a, w) => a match {
case Some(x) => if (x.last == w.head) Some(x + " " + w) else None
case None => None
case ws1 :: wss1 => ws1.flatMap(w => _amb(w :: ws, wss1)).headOption
_amb(Nil, wss.reverse)
def main(args: Array[String]) {
println(amb(List(List("the", "that", "a"),
List("frog", "elephant", "thing"),
List("walked", "treaded", "grows"),
List("slowly", "quickly"))))

[edit] Scheme

(define fail 
(lambda ()
(error "Amb tree exhausted")))
(define-syntax amb
(syntax-rules ()
((AMB) (FAIL)) ; Two shortcuts.
((AMB expression) expression)
((AMB expression ...)
((CALL-WITH-CURRENT-CONTINUATION ; Capture a continuation to
(LAMBDA (K-SUCCESS) ; which we return possibles.
(LAMBDA (K-FAILURE) ; K-FAILURE will try the next
(SET! FAIL K-FAILURE) ; possible expression.
(K-SUCCESS ; Note that the expression is
(LAMBDA () ; evaluated in tail position
expression)))) ; with respect to AMB.
(SET! FAIL FAIL-SAVE) ; Finally, if this is reached,
FAIL-SAVE))))))) ; we restore the saved FAIL.
(let ((w-1 (amb "the" "that" "a"))
(w-2 (amb "frog" "elephant" "thing"))
(w-3 (amb "walked" "treaded" "grows"))
(w-4 (amb "slowly" "quickly")))
(define (joins? left right)
(equal? (string-ref left (- (string-length left) 1)) (string-ref right 0)))
(if (joins? w-1 w-2) '() (amb))
(if (joins? w-2 w-3) '() (amb))
(if (joins? w-3 w-4) '() (amb))
(list w-1 w-2 w-3 w-4))

[edit] Seed7

$ include "seed7_05.s7i";
const type: setListType is array array string;
const func array string: amb (in string: word1, in setListType: listOfSets) is func
var array string: ambResult is 0 times "";
var string: word2 is "";
for word2 range listOfSets[1] do
if length(ambResult) = 0 and word1[length(word1) len 1] = word2[1 len 1] then
if length(listOfSets) = 1 then
ambResult := [] (word1) & [] (word2);
ambResult := amb(word2, listOfSets[2 ..]);
if length(ambResult) <> 0 then
ambResult := [] (word1) & ambResult;
end if;
end if;
end if;
end for;
end func;
const func array string: amb (in setListType: listOfSets) is func
var array string: ambResult is 0 times "";
var string: word1 is "";
for word1 range listOfSets[1] do
if length(ambResult) = 0 then
ambResult := amb(word1, listOfSets[2 ..]);
end if;
end for;
end func;
const proc: main is func
var array string: ambResult is 0 times "";
var string: word is "";
ambResult := amb([] ([] ("the", "that", "a"),
[] ("frog", "elephant", "thing"),
[] ("walked", "treaded", "grows"),
[] ("slowly", "quickly")));
for word range ambResult do
write(word <& " ");
end for;
end func;


that thing grows slowly 

[edit] SETL

program amb;
sets := unstr('[{the that a} {frog elephant thing} {walked treaded grows} {slowly quickly}]');
words := [amb(words): words in sets];
if exists lWord = words(i), rWord in {words(i+1)} |
lWord(#lWord) /= rWord(1) then
end if;
proc amb(words);
return arb {word in words | ok};
end proc;
end program;

Sadly ok and fail were only ever implemented in CIMS SETL, and are not in any compiler or interpreter that is available today, so this is not very useful as it stands.

[edit] Alternate version (avoids backtracking)

program amb;
sets := unstr('[{the that a} {frog elephant thing} {walked treaded grows} {slowly quickly}]');
proc amb(sets);
return amb1([], {}, sets);
end proc;
proc amb1(prev, mbLast, sets);
if sets = [] then
return prev;
words fromb sets;
if exists word in words |
(forall last in mbLast |
last(#last) = word(1)) and
(exists sentence in {amb1(prev with word, {word}, sets)} |
true) then
return sentence;
end if;
end if;
end proc;
end program;

We cheat a bit here - this version of amb must be given the whole list of word sets, and that list is consumed recursively. It can't pick a word from an individual list.

[edit] Tcl

[edit] Brute Force

Brute force, with quick kill of failing attempts:

set amb {
{the that a}
{frog elephant thing}
{walked treaded grows}
{slowly quickly}
proc joins {a b} {
expr {[string index $a end] eq [string index $b 0]}
foreach i [lindex $amb 0] {
foreach j [lindex $amb 1] {
if ![joins $i $j] continue
foreach k [lindex $amb 2] {
if ![joins $j $k] continue
foreach l [lindex $amb 3] {
if [joins $k $l] {
puts [list $i $j $k $l]

[edit] With Coroutines

A more sophisticated using Tcl 8.6's coroutine facility that avoids the assumption of what the problem is in the code structure:

package require Tcl 8.6
proc cp {args} {
coroutine cp.[incr ::cps] apply {{list args} {
yield [info coroutine]
foreach item $list {
if {[llength $args]} {
set c [cp {*}$args]
while 1 { yield [list $item {*}[$c]] }
} else { yield $item }
return -code break
}} {*}$args
proc amb {name filter args} {
coroutine $name apply {{filter args} {
set c [cp {*}$args]
yield [info coroutine]
while 1 {
set value [$c]
if {[{*}$filter $value]} { yield $value }
return -code break
}} $filter {*}$args
proc joins {a b} {
expr {[string index $a end] eq [string index $b 0]}
proc joins* list {
foreach a [lrange $list 0 end-1] b [lrange $list 1 end] {
if {![joins $a $b]} {return 0}
return 1
amb words joins* \
{the that a} \
{frog elephant thing} \
{walked treaded grows} \
{slowly quickly}
while 1 { puts [words] }


LOOP w1=set1
lastw1=EXTRACT (w1,-1,0)
LOOP w2=set2
IF (w2.sw.$lastw1) THEN
lastw2=EXTRACT (w2,-1,0)
LOOP w3=set3
IF (w3.sw.$lastw2) THEN
lastw3=EXTRACT (w3,-1,0)
LOOP w4=set4
IF (w4.sw.$lastw3) sentence=JOIN (w1," ",w2,w3,w4)
PRINT sentence


that thing grows slowly

[edit] TXR

This is not exactly the implementation of an operator, but a solution worth presenting. The language has the built in pattern matching and backtracking behavior suited for this type of text mining task.

For convenience, we prepare the data in four files:

$ cat amb/set1
$ cat amb/set2
$ cat amb/set3
$ cat amb/set4


@(define first_last (first last whole))
@ (all)
@(skip :greedy)@{last 1}
@ (and)
@{first 1}@(skip)
@ (and)
@ (end)
@(next "amb/set1")
@(first_last fi1 la1 w1)
@(next "amb/set2")
@(first_last la1 la2 w2)
@(next "amb/set3")
@(first_last la2 la3 w3)
@(next "amb/set4")
@(first_last la3 la4 w4)
@w1 @w2 @w3 @w4


$ ./txr amb.txr 
that thing grows slowly

As you can see, this has the "nondeterministic flavor" of Amb. The @(skip) directives"magically" skip over the lines of input that do not succeed.

This example naturally handles empty strings, since the first_last function simply does not match such inputs.

Here is how to embed the task's specific data in the code:

@(define first_last (first last whole))
@ (all)
@(skip :greedy)@{last 1}
@ (and)
@{first 1}@(skip)
@ (and)
@ (end)
@(next :list ("the" "that" "a"))
@(first_last fi1 la1 w1)
@(next :list ("frog" "elephant" "thing"))
@(first_last la1 la2 w2)
@(next :list ("walked" "treaded" "grows"))
@(first_last la2 la3 w3)
@(next :list ("slowly" "quickly"))
@(first_last la3 la4 w4)
@w1 @w2 @w3 @w4

[edit] VBScript

[edit] Implementation
class ambiguous
dim sRule
public property let rule( x )
sRule = x
end property
public default function amb(p1, p2)
amb = eval(sRule)
end function
end class
[edit] Invocation
dim amb
set amb = new ambiguous
amb.rule = "right(p1,1)=left(p2,1)"
dim w1, w2, w3, w4
for each w1 in split("the that a", " ")
for each w2 in split("frog elephant thing", " ")
for each w3 in split("walked treaded grows", " ")
for each w4 in split("slowly quickly", " ")
if amb(w1, w2) and amb(w2, w3) and amb(w3, w4) then
wscript.echo w1, w2, w3, w4
end if
[edit] Output
that thing grows slowly

[edit] zkl

fcn amb(text){text.split().reduce(fcn(p,w){
if(p[-1]!=w[0])return(Void.Stop,False); w}) != False}
amb("this is a test")          //--> False
amb("that thing grows slowly") //-->True
amb("frog elephant thing")     //-->False

Not sure if is a bug or not but "" and "hoho" are also True

Personal tools