Tuesday, 24 February 2009

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:

InsDescription
-subtract TOS from 2OS
+add TOS to 2OS
*multiply TOS by 2OS
U.print TOS as an unsigned number
SPACEprint a space
DUPcopy TOS
DROPremove TOS
ABSreplace TOS with its absolute value
NEGATEreplace 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
SWAPexchange TOS with 2OS
DEPTHnumber of elements on stack
BEGINstart of BEGIN .. UNTIL structure
UNTILif TRUE, return to matching BEGIN
DOstart of DO .. LOOP structure
LOOPinc 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

1 comment:

Kyle said...

You can drop DO and a few others. In the past two decades, Moore has focused entirely on making the most minimal Forth system possible, a sort of anti-ANSI crusade.

Look at the instruction set for Machine Forth and VentureForth. Machine might be the closer fit for you, half of Venture is for message passing between cores.