Implementing Forth in Redcode

I'm currently working on a threaded Forth interpreter in Redcode. The first version should provide about 20 key Forth instructions in 50 lines of code.

Threading

The Forth program will be stored as a list of subroutine calls, for example:

        dat    lit     ; push 1111
        dat    1111
        dat    lit     ; push 1234
        dat    1234
        dat    plus    ; add TOS to 2OS
        dat    udot    ; display TOS

A more compact representation would be to store addresses in both the a-field and b-field. Unfortunately this would be at the expense of more complex flow control:

        dat    lit,      1111
        dat    lit,      1234
        dat    plus,     udot

I'm open to suggestions how the interpreter can use the compact representation without causing too many difficulties.

Instruction Set

I'm planning to support the following instructions in version 1. Have I missed anything important, or have I included something which can be left out:

Ins	Description
-	subtract TOS from 2OS
+	add TOS to 2OS
*	multiply TOS by 2OS
U.	print TOS as an unsigned number
SPACE	print a space
DUP	copy TOS
DROP	remove TOS
ABS	replace TOS with its absolute value
NEGATE	replace TOS with -TOS
!	2OS is stored at the address in TOS
+!	2OS is added to the address in TOS
@	fetch the value at the address in TOS
=	TRUE if TOS=2OS, else FALSE
SWAP	exchange TOS with 2OS
DEPTH	number of elements on stack
BEGIN	start of BEGIN .. UNTIL structure
UNTIL	if TRUE, return to matching BEGIN
DO	start of DO .. LOOP structure
LOOP	inc counter, jump to DO if below limit

Signed vs Unsigned

Unfortunately numbers in Forth are signed and numbers in Redcode are unsigned. This affects a number of instructions, including division and comparison. Would it be worth the extra code to support unsigned numbers in Redcode Forth?

Example Code

The following example interprets +, U. and literals. New instructions can easily be added in Redcode. Support for calling new instuctions written in Forth needs to be added:

        org    next

stack   dat    0,         0

; LIT - place the next value on the stack

lit     mov.b  }ip,       <stack
        jmp    next

; + - remove 2OS and TOS and put their sum on stack

plus    add.b  >stack,    @stack
        jmp    next

; U. - remove and display TOS as an unsigned number

udot    mov.b  @stack,    <stack
        div    #10,       >stack
        mod    #10,       @stack
        add    #48,       @stack
        add    #1,        udcount
        jmn    udot,      <stack
        add    #1,        stack
udloop  sts    >stack,    0
udcount djn    udloop,    #0
        sts.a  #32,       0
        jmp    next

; --------------------------------

next
ip      jmp    @prog,     }ip

; --------------------------------

prog
        dat    lit     ; push 1111
        dat    1111
        dat    lit     ; push 1234
        dat    1234
        dat    plus    ; add TOS to 2OS
        dat    udot    ; display TOS

        end

Display Signed Number in Base X

The following Redcode displays a signed number is a chosen number base:

dot     slt    @stack,    #1+CORESIZE/2
        sts.a  #45,       0
        slt    @stack,    #1+CORESIZE/2
        mul    #-1,       @stack
udot    mov.b  @stack,    <stack
        div.b  base,      >stack
        mod.b  base,      @stack
        slt    @stack,    #10
        add    #7,        @stack
        add    #48,       @stack
        add    #1,        udcount
        jmn    udot,      <stack
        add    #1,        stack
udloop  sts    >stack,    0
udcount djn    udloop,    #0

base    dat    10

Unfortunately, the code is pretty ugly. Can you suggest a more elegant solution?

Redcode Interpreter for the RSSB Single Instruction Computer

The RSSB single instruction computer is a minimal, Turing complete virtual machine. The instruction used is Reverse Subtract and Skip if Borrow. RSSB subtracts the accumulator from the contents of a memory location and stores the result in both. The next instruction will be skipped if the accumulator was greater than the value in memory.

Jumps can be implemented by manipulating the instruction pointer at memory location 0. Other special locations are as follows:

1. accumulator
2. always contains 0
3. input
4. output

Here's the code for the interpreter. I've included a Hello World program written in RSSB. If you think you can reduce the size of Hello World, please let me know how.

        org    rssbint

rssbint mov.ba >ip,       ip    ; load next instruction

        mov    #0,        zero  ; set zero

        sne.a  #3,        ip    ; handle input
        lds    in,        0

        sne.a  #4,        ip    ; handle output
        sts    acc,       0
        mov    acc,       out
        add    out,       out

        slt    *ip,       acc   ; set flag for skip
        mov    #2,        skip

        sub.b  acc,       *ip   ; acc, *ip = *ip - acc
        mov.b  *ip,       acc

skip    djn    noskip,    #1    ; skip if required
        nop    >ip,       >skip

noskip  slt    #7900,     @ip   ; protect interpreter

        jmn    rssbint,   ip    ; loop until ip = 0

; --------------------------------------

ip      dat    5      ; instruction pointer
acc     dat    0      ; accumulator
zero    dat    0      ; always 0
in      dat    0      ; character input
out     dat    0      ; character output

; --------------------------------------

loop    dat    -ip+   acc       ; acc = character from ptr
ptr     dat    -ip+   hello        

        dat    -ip+   out       ; display character

        dat    -ip+   zero      ; acc = -acc

        dat    -ip+   zero      ; always skipped

        dat    -ip+   sum       ; subtract acc from sum

        dat    -ip+   ip        ; skipped if sum is negative,
                                ; otherwise jump to 0

one     dat    -ip+   acc       ; subtract 1 from ptr
        dat    -ip+   one
        dat    -ip+   ptr

        dat    -ip+   acc       ; jump to loop
        dat    -ip+   loopoff
        dat    -ip+   ip
loopoff dat    -loop

sum     dat    -1116

        dat    33         ; '!'
        dat    100        ; 'd'
        dat    108        ; 'l'
        dat    114        ; 'r'
        dat    111        ; 'o'
        dat    87         ; 'W'
        dat    32         ; ' '
        dat    44         ; ','
        dat    111        ; 'o'
        dat    108        ; 'l'
        dat    108        ; 'l'
        dat    101        ; 'e'
hello   dat    72         ; 'H'

        end

Write Number (implemented using a data stack)

Here's an alternative version of the routine to display numbers using exMARS Stream's sts opcode. The code executes in 8x+1 cycles, where x is the number of digits. This implementation uses a data stack.

printd  mov.a  *stack,    {stack
        div.a  #10,       }stack
        mod.a  #10,       *stack
        add.a  #48,       *stack
        add    #1,        pcount
        jmn.a  printd,    {stack
        add.a  #1,        stack
ploop   sts.a  }stack,    0
pcount  djn    ploop,     #0

Hello World in Redcode

Here's the shortest "Hello, World!" program I could implement, written using the sts opcode which is available in exMARS Streams.

write   sts.a  hello,     0
        sts.b  }write,    0
        djn    write,     #7

hello   dat    72,        101
        dat    108,       108
        dat    111,       44
        dat    32,        87
        dat    111,       114
        dat    108,       100
        dat    33,        10

Write Number

Here's a short iterative routine to write a number to standard out. Although longer than the recursive algorithm, it avoids the need to maintain a data / return stack. 9x+1 cycles are required, where x is the number of digits.

The sts opcode is available in exMARS Streams.

writedec  mov    number,         temp
          jmp    _wdloop+1,      >_wdloop

_wdloop   mul    #10,            #0
          div    #10,            temp
          jmn    _wdloop,        temp

_wdprint  mov    number,         temp
          div.b  _wdloop,        temp
          add    #48,            temp
          sts    temp,           0
          mod.b  _wdloop,        number
          div    #10,            _wdloop
          jmn    _wdprint,       _wdloop