如何向 DCG 语法添加打印命令

Question

我想在我的 DCG 语法中添加一个 print 命令，这是我所拥有的：

program( (R0 --> R) ) -->
    [begin],instructs(( R0 --> R )),[end].
instructs( ( R0 --> R ) ) -->
    instr(( R0 --> R )).
instructs( ( R0 --> R ) ) -->
    instr(( R0 --> R1 )),
    instructs(( R1 --> R )).
instr( ( R0 --> R ) ) -->
    [ dte], { R is 2*R0}.
instr( ( R0 --> R ) ) -->
    [ dto], { R is 2*R0 + 1}.
instr( ( R0 --> R ) ) -->
    [ halve], { R is R0 // 2}.

要添加 print，我需要将 R0 --> R 更改为 R0 --> OutTape，其中 OutTape 是程序的输出。

我认为我可以做到以下几点：

program( (R0 --> OutTape) ) -->
  [begin],instructs(( R --> Tape )),[end].
instructs( ( R --> Tape ) ) -->
  instr(( R --> Tape )).
instructs( ( R --> Tape ) ) -->
  instr(( R --> Tape)),
  instructs(( R --> Tape )).
instr( ( R --> Tape ) ) -->
  [ dte], { R is 2*R}. % is this a legal term?
instr( ( R --> Tape ) ) -->
  [ dto], { R is 2*R + 1}.
instr( ( R --> Tape ) ) -->
  [ halve], { R is R // 2}.
instr( ( R --> Tape ) ) -->
    [ print], {append()}. % how to append R to Tape?

但我不知道如何将 R 附加到磁带上，能否请您指引我正确的方向？

Answer 1

在 Prolog 中，您不能重新分配变量。所以像 R is R // 2 这样的表达式会失败，因为在 Prolog 中，它在语义上说 *R 本身是除以 2 的整数，只有当 R 为 0 时才为真。

同样，鉴于 Tape 是一个列表，您不能继续追加到同一个列表（或磁带）。您必须提供磁带的先前状态，然后提供打印到磁带后的新状态。这需要在表示先前磁带状态的谓词中有一个额外的参数。一开始，磁带是空的，所以先验状态是[].

此外，虽然您的问题中没有完全解释，但看起来您可能希望 "print" 将中间结果录入磁带。这意味着您还需要携带中间结果，以便在遇到 print 指令时随时可以将其 "printed" 写入磁带。所以那将是另一个论点。

program((R0 --> Tape)) -->
    % Initially, the tape is empty: []
    % OutTape is needed here, not "Tape" as originally shown
    % The second argument of `instructs` will have the final value,
    %   but we'll use `_` here since we only care about the values
    %   "printed" to the `OutTape`
    [begin], instructs((R0 --> OutTape), _, []), [end], { reverse(OutTape, Tape) }.
instructs((R0 --> Tape), R, PrevTape) -->
    instr((R0 --> Tape), R, PrevTape).
instructs((R0 --> Tape), R, PrevTape) -->
    instr((R0 --> NextTape), R1, PrevTape),   % NextTape is an intermediate tape state
    instructs((R1 --> Tape), R, NextTape).
instr((R0 --> PrevTape), R, PrevTape ) -->
    [dte], { R is 2*R0 }.
instr((R0 --> PrevTape), R, PrevTape) -->
    [dto], { R is 2*R0 + 1 }.
instr((R0 --> PrevTape), R, PrevTape) -->
    [halve], { R is R0 // 2 }.
instr((R --> [R|PrevTape]), R, PrevTape) -->
    [print].

另外，在上面的代码中，我使用 reverse 作为一种快速的方式来按进程顺序排列磁带，从左到右，虽然我不确定这是否是您的要求。

| ?- phrase(program((3 --> Tape)), [begin, dte, dto, print, dte, print, end], []).

Tape = [13,26] ? ;

(1 ms) no
| ?-

结语

在此上下文中使用 --> 作为参数的函子，虽然在句法上是允许的，但有点不寻常并且可能会造成混淆。仅使用逗号会更规范：

program(R0, Tape) -->
    % Initially, the tape is empty: []
    % OutTape is needed here, not "Tape" as originally shown
    % The 3rd argument of `instructs` will have the final value,
    %   but we'll use `_` here since we only care about the values
    %   "printed" to the `OutTape`
    [begin], instructs(R0, OutTape, _, []), [end], { reverse(OutTape, Tape) }.
instructs(R0, Tape, R, PrevTape) -->
    instr(R0, Tape, R, PrevTape).
instructs((R0, Tape, R, PrevTape) -->
    instr(R0, NextTape, R1, PrevTape),   % NextTape is an intermediate tape state
    instructs(R1, Tape, R, NextTape).
instr(R0, PrevTape, R, PrevTape ) -->
    [dte], { R is 2*R0 }.
instr(R0, PrevTape, R, PrevTape) -->
    [dto], { R is 2*R0 + 1 }.
instr(R0, PrevTape, R, PrevTape) -->
    [halve], { R is R0 // 2 }.
instr(R, [R|PrevTape], R, PrevTape) -->
    [print].

如何向 DCG 语法添加打印命令

How to add a print command to DCG syntax

prolog

dcg