continuations - Erlang implementing an amb operator. -

on wikipedia says using call/cc can implement amb operator nondeterministic choice, , question how implement amb operator in language in support continuations write in continuation passing style, in erlang?

if can encode constraints constitutes successful solution or choice guards, list comprehensions can used generate solutions. example, list comprehension documentation shows example of solving pythagorean triples, problem solved using amb (see example exercise 4.35 of sicp, 2nd edition). here's more efficient solution, pyth1/1, shown on list comprehensions page:

pyth1(n) ->     [ {a,b,c} ||         <- lists:seq(1,n-2),         b <- lists:seq(a+1,n-1),         c <- lists:seq(b+1,n),         a+b+c =< n,         a*a+b*b == c*c      ]. 

one important aspect of amb efficiently searching solution space, done here generating possible values a, b, , c lists:seq/2 , constraining , testing values guards. note page shows less efficient solution named pyth/1 a, b, , c generated identically using lists:seq(1,n); approach generates permutations slower pyth1/1 (for example, on machine, pyth(50) 5-6x slower pyth1(50)).

if constraints can't expressed guards, can use pattern matching , try/catch deal failing solutions. example, here's same algorithm in pyth/1 rewritten regular functions triples/1 , recursive triples/5:

-module(pyth). -export([triples/1]).  triples(n) ->     triples(1,1,1,n,[]). triples(n,n,n,n,acc) ->     lists:reverse(acc); triples(n,n,c,n,acc) ->     triples(1,1,c+1,n,acc); triples(n,b,c,n,acc) ->     triples(1,b+1,c,n,acc); triples(a,b,c,n,acc) ->     newacc = try                  true = a+b+c =< n,                  true = a*a+b*b == c*c,                  [{a,b,c}|acc]              catch                  error:{badmatch,false} ->                      acc              end,     triples(a+1,b,c,n,newacc). 

we're using pattern matching 2 purposes:

• in function heads, control values of a, b , c respect n , know when we're finished
• in body of final clause of triples/5, assert conditions a+b+c =< n , a*a+b*b == c*c match true

if both conditions match true in final clause of triples/5, insert solution our accumulator list, if either fails match, catch badmatch error , keep original accumulator value.

calling triples/1 yields same result list comprehension approaches used in pyth/1 , pyth1/1, it's half speed of pyth/1. so, approach constraint encoded normal function , tested success within try/catch expression.