3

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

4

1 回答 1

3

如果您可以将构成成功解决方案或选择的约束编码为警卫，则可以使用列表推导来生成解决方案。例如，列表理解文档显示了解决毕达哥拉斯三元组的示例，这是一个经常使用解决的问题amb（参见例如SICP 的练习 4.35，第 2 版）。这是列表推导页面上显示的更有效的解决方案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是有效地搜索解决方案空间，这是通过为 、 和 with 生成可能的值来完成的A，B然后C使用lists:seq/2守卫约束和测试这些值。请注意，该页面还显示了一个效率较低的解决方案，名为pyth/1where A、B和 ，C它们都是使用lists:seq(1,N);生成的。该方法会生成所有排列，但比 慢pyth1/1（例如，在我的机器上，pyth(50)比 慢 5-6 倍pyth1(50)）。

如果您的约束不能表示为警卫，您可以使用模式匹配和 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错误并保留原始的累加器值。

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

于 2015-07-08T16:15:17.627 回答