如何查明 Prolog 是否执行尾调用优化

使用SWI Prolog（Win x64）的开发版本， 我为 a 编写了一个 DCG 谓词确定性词法分析器（托管在 github 上） https://github.com/sebgod/goldparser-prolog（因此所有外部谓词都没有留下选择点）：

read_token(parser(Grammar, Tables),
       lexer(dfa-DFAIndex, last_accept-LastAccept, chars-Chars0),
       Token) -->
(   [Input],
    {
     dfa:current(Tables, DFAIndex, DFA),
     char_and_code(Input, Char, Code),
     dfa:find_edge(Tables, DFA, Code, TargetIndex)
    }
->  { table:item(dfa_table, Tables, TargetIndex, TargetDFA),
      dfa:accept(TargetDFA, Accept),
      atom_concat(Chars0, Char, Chars),
      NewState = lexer(dfa-TargetIndex,
                       last_accept-Accept,
                       chars-Chars)
    },
    read_token(parser(Grammar, Tables), NewState, Token)
;   {
     (   LastAccept \= none
     ->  Token = LastAccept-Chars0
     ;   (   ground(Input)
         ->  once(symbol:by_type_name(Tables, error, Index, _)),
             try_restore_input(Input, FailedInput, InputR),
             Input = [FailedInput | InputR],
             format(atom(Error), '~w', [FailedInput]),
             Token = Index-Error
         ;   once(symbol:by_type_name(Tables, eof, Index, _)),
             Token = Index-''
         )
     )
    }
).

现在使用(;) and ->很多，我想知道SWI-Prolog可以优化递归read_token(parser(Grammar, Tables), NewState, Token)使用尾调用优化， 或者如果我必须手动将谓词分成几个子句。 我只是不知道如何找出解释器的作用，特别是知道运行调试器时 TCO 被禁用。

为了回答你的问题，我首先寻找可能阻止最后一次调用优化的“琐碎”目标。如果发现一些：

     ;   (   ground(Input)
         ->  once(symbol:by_type_name(Tables, error, Index, _)),
             try_restore_input(Input, FailedInput, InputR),
             Input = [FailedInput | InputR],
             format(atom(Error), '~w', [FailedInput]),
             Token = Index-Error
         ;   once(symbol:by_type_name(Tables, eof, Index, _)),
             Token = Index-''
         )
  

在这两种情况下，仅通过这些目标就可以防止 LCO。

现在，我编译了你的规则并查看了扩展listing:

?- listing(read_token).
read_token(parser(O, B), lexer(dfa-C, last_accept-T, chars-J), Q, A, S) :-
        (   A=[D|G],
            dfa:current(B, C, E),
            char_and_code(D, K, F),
            dfa:find_edge(B, E, F, H),
            N=G
        ->  table:item(dfa_table, B, H, I),
            dfa:accept(I, L),
            atom_concat(J, K, M),
            P=lexer(dfa-H, last_accept-L, chars-M),
            R=N,
            read_token(parser(O, B),
                       P,
                       Q,
                       R,
                       S)        % 1: looks nice!
        ;   (   T\=none
            ->  Q=T-J
            ;   ground(D)
            ->  once(symbol:by_type_name(B, error, W, _)),
                try_restore_input(D, U, V),
                D=[U|V],
                format(atom(X), '~w', [U]),
                Q=W-X    % 2: prevents LCO
            ;   once(symbol:by_type_name(B, eof, W, _)),
                Q=W-''   % 3: prevents LCO
            ),
            S=A    % 4: prevents LCO
        ).
  

ad 1) 这是您最可能正在寻找的递归情况。在这里，一切看起来都很美好。

ad 2,3) 上面已经讨论过，也许你想交换目标

ad 4) 这是精确、坚定的方式所带来的效果{}//1在 DCG 中处理。根据经验，实施者更愿意坚定不移，而不是努力实现 LCO。请参阅：DCG扩展：坚定性被忽视了吗？ https://stackoverflow.com/questions/13100364/dcg-expansion-is-steadfastness-ignored

另请注意，这不仅仅是调用框架的简单重用。与垃圾收集有很多交互。为了克服 SWI 中的所有这些问题，需要额外的 GC 阶段。

有关更多信息，请参阅中的微小基准测试Prolog 中的精确垃圾收集 http://www.complang.tuwien.ac.at/ulrich/papers/PDF/#2008-ciclops

所以最后回答你的问题：你的规则可能会被优化；前提是在递归目标之前没有留下选择点。

还有真正的低级方法。我从不使用它来开发代码：vm_list。该列表最终向您显示 SWI 是否可能考虑 LCO（假设没有选择点）。

i_call and i_callm永远不会执行 LCO。仅有的i_depart会做。在：142 i_depart(read_token/5)

?- vm_list(read_token).
========================================================================
read_token/5
========================================================================
   0 s_virgin
   1 i_exit
----------------------------------------
clause 1 ((0x1cc4710)):
----------------------------------------
   0 h_functor(parser/2)
   2 h_firstvar(5)
   4 h_firstvar(6)
   6 h_pop
   7 h_functor(lexer/3)
   9 h_functor((-)/2)
  11 h_const(dfa)
  13 h_firstvar(7)
  15 h_pop
  16 h_functor((-)/2)
  18 h_const(last_accept)
  20 h_firstvar(8)
  22 h_pop
  23 h_rfunctor((-)/2)
  25 h_const(chars)
  27 h_firstvar(9)
  29 h_pop
  30 i_enter
  31 c_ifthenelse(26,118)
  34 b_unify_var(3)
  36 h_list_ff(10,11)
  39 b_unify_exit
  40 b_var(6)
  42 b_var(7)
  44 b_firstvar(12)
  46 i_callm(dfa,dfa:current/3)
  49 b_var(10)
  51 b_firstvar(13)
  53 b_firstvar(14)
  55 i_call(char_and_code/3)
  57 b_var(6)
  59 b_var(12)
  61 b_var(14)
  63 b_firstvar(15)
  65 i_callm(dfa,dfa:find_edge/4)
  68 b_unify_fv(16,11)
  71 c_cut(26)
  73 b_const(dfa_table)
  75 b_var(6)
  77 b_var(15)
  79 b_firstvar(17)
  81 i_callm(table,table:item/4)
  84 b_var(17)
  86 b_firstvar(18)
  88 i_callm(dfa,dfa:accept/2)
  91 b_var(9)
  93 b_var(13)
  95 b_firstvar(19)
  97 i_call(atom_concat/3)
  99 b_unify_firstvar(20)
 101 b_functor(lexer/3)
 103 b_functor((-)/2)
 105 b_const(dfa)
 107 b_argvar(15)
 109 b_pop
 110 b_functor((-)/2)
 112 b_const(last_accept)
 114 b_argvar(18)
 116 b_pop
 117 b_rfunctor((-)/2)
 119 b_const(chars)
 121 b_argvar(19)
 123 b_pop
 124 b_unify_exit
 125 b_unify_fv(21,16)
 128 b_functor(parser/2)
 130 b_argvar(5)
 132 b_argvar(6)
 134 b_pop
 135 b_var(20)
 137 b_var2
 138 b_var(21)
 140 b_var(4)
 142 i_depart(read_token/5)
 144 c_var_n(22,2)
 147 c_var_n(24,2)
 150 c_jmp(152)
 152 c_ifthenelse(27,28)
 155 b_var(8)
 157 b_const(none)
 159 i_call((\=)/2)
 161 c_cut(27)
 163 b_unify_var(2)
 165 h_functor((-)/2)
 167 h_var(8)
 169 h_var(9)
 171 h_pop
 172 b_unify_exit
 173 c_var(10)
 175 c_var_n(22,2)
 178 c_var_n(24,2)
 181 c_jmp(101)
 183 c_ifthenelse(28,65)
 186 b_firstvar(10)
 188 i_call(ground/1)
 190 c_cut(28)
 192 b_functor((:)/2)
 194 b_const(symbol)
 196 b_rfunctor(by_type_name/4)
 198 b_argvar(6)
 200 b_const(error)
 202 b_argfirstvar(22)
 204 b_void
 205 b_pop
 206 i_call(once/1)
 208 b_var(10)
 210 b_firstvar(23)
 212 b_firstvar(24)
 214 i_call(try_restore_input/3)
 216 b_unify_var(10)
 218 h_list
 219 h_var(23)
 221 h_var(24)
 223 h_pop
 224 b_unify_exit
 225 b_functor(atom/1)
 227 b_argfirstvar(25)
 229 b_pop
 230 b_const('~w')
 232 b_list
 233 b_argvar(23)
 235 b_nil
 236 b_pop
 237 i_call(format/3)
 239 b_unify_var(2)
 241 h_functor((-)/2)
 243 h_var(22)
 245 h_var(25)
 247 h_pop
 248 b_unify_exit
 249 c_jmp(33)
 251 b_functor((:)/2)
 253 b_const(symbol)
 255 b_rfunctor(by_type_name/4)
 257 b_argvar(6)
 259 b_const(eof)
 261 b_argfirstvar(22)
 263 b_void
 264 b_pop
 265 i_call(once/1)
 267 b_unify_var(2)
 269 h_functor((-)/2)
 271 h_var(22)
 273 h_const('')
 275 h_pop
 276 b_unify_exit
 277 c_var(10)
 279 c_var_n(23,2)
 282 c_var(25)
 284 b_unify_vv(4,3)
 287 c_var_n(11,2)
 290 c_var_n(13,2)
 293 c_var_n(15,2)
 296 c_var_n(17,2)
 299 c_var_n(19,2)
 302 c_var(21)
 304 i_exit