标签: prolog-tabling

我在这个语法中有一个左递归的小问题.我正在尝试在Prolog中编写它,但我不知道如何删除左递归.

<expression> -> <simple_expression>
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression>
<simple_expression> -> <function>
<function> -> <function> <atom>
<function> -> <atom>
<atom> -> <number> | <variable>

<binary_operator> -> + | - | * | /

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }.
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }.
simple_expression(SExpr) --> function(Func), { SExpr = Func }.
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }.
function(Func) --> atom(At), { Func = At }.

我写过类似的东西,但它根本不起作用.如何更改它以使该程序正常工作？

I am curious about how tabling works to improve efficiency of Prolog programs. How is it implemented? Both explanation and references are welcome.

我用b-prolog版本8.1 的表格功能做了一些实验, 并且对我观察到的性能感到非常惊讶.

这是我使用的代码.它计算将一些正整数减少到以下所需的Collat​​z步N数:I1

%:- table posInt_CollatzSteps/2.               % remove comment to enable tabling
posInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  1 is I /\ 1 
   -> I0 is I*3+1, posInt_CollatzSteps(I0,N0), N is N0+1   % odd
   ;  I0 is I>>1,  posInt_CollatzSteps(I0,N0), N is N0+1   % even
   ).

要确定从所有整数需要减少最大步数I0来I:

i0_i_maxSteps0_maxSteps(I0,I,M0,M) :-
   (  I0 > I
   -> M0 = M
   ;  posInt_CollatzSteps(I0,N0),
      I1 is …

最近，我开始在 Prolog 中玩表；我用b-prolog和xsb做的一些实验可以在这个问题中找到。

随着表格越来越大，我意识到我需要找到一些表格选项/参数来限制专用于表格的内存量。

到目前为止，我在yap、b-prolog和xsb的手册中没有找到任何合适的内容。

你能给我指出一些有用的信息吗？