如何确定Prolog是否执行尾部呼叫优化

Question

使用SWI Prolog（Win x64）的开发版本，我为确定性词法分析器（托管在github上）写了DCG谓词（因此，所有外部谓词都没有选择点）：

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-''
         )
     )
    }
).

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

Answer 1

为了回答您的问题，我首先寻找了可能阻碍上次通话优化的“琐碎”目标。如果发现一些：

     ; （地面（输入）
         ->一次（符号：by_type_name（表，错误，索引，_）），
             try_restore_input（Input，FailedInput，InputR），
             输入= [失败输入| InputR]，
             格式（atom（Error），'〜w'，[FailedInput]），
             令牌=索引错误
         ; 一次（符号：by_type_name（表，eof，索引，_）），
             代币=索引-''
         ）

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

现在，我遵守了您的规则，并通过以下方式查看了扩展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，
                       问
                       R，
                       S）％1：看起来不错！
        ; （T \ =无
            -> Q = TJ
            ; 地面（D）
            ->一次（符号：by_type_name（B，错误，W，_）），
                try_restore_input（D，U，V），
                D = [U | V]，
                格式（atom（X），'〜w'，[U]），
                Q = WX％2：防止LCO
            ; 一次（符号：by_type_name（B，eof，W，_）），
                Q = W-''％3：防止LCO
            ），
            S = A     ％4：防止LCO
        ）。

广告1）这是您很可能在寻找的递归案例。在这里，一切似乎都很好。

广告2,3）上面已经讨论过，也许您想交换目标

广告4）这是{}//1DCG中处理方式精确，坚定的结果。根据经验：与实施LCO风格相比，实施者宁愿坚定不移。请参阅：DCG扩展：牢固性是否被忽略？

还请注意，除了简单重复使用调用帧外，还有很多其他功能。垃圾回收有很多交互作用。为了克服SWI中的所有这些问题，有必要增加一个GC阶段。

有关更多信息，请参考Prolog中的Precise Garbage Collection中的微小基准。

因此，最后回答您的问题：您的规则可能已优化；前提是递归目标之前没有选择点。

也有真正的底层方法。我从未将其用于代码开发：vm_list。该清单最终显示了SWI是否可以考虑LCO（假设那里没有选择点）。

i_call并且i_callm永远不会执行LCO。只有i_depart会做。在：142 i_depart(read_token/5)

？-vm_list（read_token）。
================================================== ======================
read_token / 5
================================================== ======================
   0 s_virgin
   1次i_exit
----------------------------------------
条款1（（0x1cc4710））：
----------------------------------------
   0 h_functor（解析器/ 2）
   2 h_firstvar（5）
   4 h_firstvar（6）
   6小时
   7 h_functor（lexer / 3）
   9 h_functor（（-）/ 2）
  11 h_const（dfa）
  13 h_firstvar（7）
  15小时
  16 h_functor（（-）/ 2）
  18 h_const（last_accept）
  20小时_firstvar（8）
  22小时
  23 h_rfunctor（（-）/ 2）
  25 h_const（字符）
  27 h_firstvar（9）
  29小时
  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（表格，表格：项目/ 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（字符）
 121 b_argvar（19）
 123 b_pop
 124 b_unify_exit
 125 b_unify_fv（21,16）
 128 b_functor（解析器/ 2）
 130 b_argvar（5）
 第132章（一更）
 134 b_pop
 135 b_var（20）
 第137章
 138 b_var（21）
 140 b_var（4）
 142我_离开（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章（小幸运）
 161 c_cut（27）
 163 b_unify_var（2）
 165 h_functor（（-）/ 2）
 167小时_var（8）
 169 h_var（9）
 171小时
 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章（二更）
 188我叫（地面/ 1）
 190 c_cut（28）
 第192章（二更）
 194 b_const（符号）
 第196章（一更）
 第198章（二更）
 200 b_const（错误）
 202 b_argfirstvar（22）
 204 b_void
 205 b_pop
 206 i_call（一次/ 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章
 219 h_var（23）
 221 h_var（24）
 223小时
 224 b_unify_exit
 225 b_functor（atom / 1）
 第227章（二更）
 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章（二更）
 241 h_functor（（-）/ 2）
 243小时_var（22）
 245小时_var（25）
 247小时
 248b_unify_exit
 249 c_jmp（33）
 251 b_functor（（：）/ 2）
 253 b_const（symbol）
 255 b_rfunctor（by_type_name / 4）
 第257章（二更）
 第259章
 261 b_argfirstvar（22）
 第263章
 264 b_pop
 265 i_call（一次/ 1）
 第267章（二更）
 269 h_functor（（-）/ 2）
 271 h_var（22）
 第273章
 275小时
 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章