How to add a print command to DCG syntax

Question

I want to add a print command to my DCG syntax, here is what I have:

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

To add the print I need to change R0 --> R to R0 --> OutTape, where OutTape is the output of the program.

I thought I can do the following:

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?

But I don't know how to append R to the Tape, can you please lead me to the right direction?

Answer 1

In Prolog, you cannot reassign variables. So expressions such as R is R // 2 will fail since, in Prolog, it semantically says that *R is itself integer divide by 2 which would only be true if R was 0.

Likewise, given that a Tape is a list, you cannot continue to append to the same list (or tape). You have to provide the previous state of the tape and then new state after the print to the tape. This requires an extra argument in your predicates representing that prior tape state. At the beginning, the tape is empty, so that prior state is [].

In addition, although it hasn't been explained completely in your question, it looks like you might want to "print" intermediate results to the tape. That means you need to carry intermediate results along as well so that it can be "printed" to the tape any time a print instruction is encountered. So that would be another argument.

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].

Also, in the above code, I used reverse as a quick way to put the tape in process order, left to right, although I am not sure if that's what your requirement is.

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

Tape = [13,26] ? ;

(1 ms) no
| ?-

---

Epilog

The use of --> as a functor for the argument in this context, although syntactically allowable, is a bit unusual and could be confusing. It would be more canonical to just to use a comma:

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].