Erlang 实现了 amb 运算符。

Question

在维基百科上，它说使用 call/cc 你可以实现 amb 运算符来进行非确定性选择，我的问题是如何在一种语言中实现 amb 运算符，在这种语言中，对延续的唯一支持是以延续传递风格编写，就像在 erlang 中一样？

Answer 1

如果您可以将构成成功解决方案或选择的约束编码为守卫，则可以使用列表推导式来生成解决方案。例如，list comprehension documentation显示解决 Pythagorean triples 的示例，这是一个经常使用 amb 解决的问题(例如参见 exercise 4.35 of SICP, 2nd edition )。这是更有效的解决方案，pyth1/1 ，显示在列表推导页面上:

pyth1(N) ->
    [ {A,B,C} ||
        A <- 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 
    ].

amb 的一个重要方面正在有效地搜索解决方案空间，这是通过为 A 生成可能的值来完成的, B ，和C与 lists:seq/2然后用 guard 约束和测试这些值。请注意，该页面还显示了一个名为 pyth/1 的效率较低的解决方案。哪里A , B ，和C全部使用 lists:seq(1,N) 相同地生成;该方法生成所有排列，但比 pyth1/1 慢(例如，在我的机器上， pyth(50) 比 pyth1(50) 慢 5-6 倍)。

如果您的约束无法表示为防护，您可以使用模式匹配和 try/catch 来处理失败的解决方案。例如，pyth/1 中的算法相同。重写为常规函数 triples/1和递归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).

我们使用模式匹配有两个目的:

• 在函数头中，控制 A 的值, B和C关于N并知道我们何时完成
• 在triples/5最后一个子句的正文中，断言条件 A+B+C =< N和A*A+B*B == C*C匹配true

如果两个条件都匹配true在 triples/5 的最后一个子句中，我们将解决方案插入到累加器列表中，但如果其中一个无法匹配，我们会捕获 badmatch错误并保留原始累加器值。

调用triples/1产生与 pyth/1 中使用的列表理解方法相同的结果和pyth1/1 ，但它的速度也是 pyth/1 的一半。即便如此，使用这种方法，任何约束都可以编码为普通函数，并在 try/catch 表达式中测试是否成功。