Redcode's OISC - the DJN Computer

An OISC is an abstract computer designed to be Turing complete with only one instruction. OISC is short for One-Instruction Set Computer.

The instruction used by most variants of OISC subtracts and branches on certain conditions, for example the URISC / RSSB Single Instruction Computer. It may come as a surprise that the Redcode instruction set contains a primative instuction suitable for building a One-Instruction Computer, DJN.

DJN X, Y uses Y as a pointer into memory. 1 is subtracted from the value stored at location Y. If the result is non-zero, DJN jumps to X. Here's an example demonstrating how to copy A to B using DJN:

        DJN 0,   TEMP
        DJN 0,   B
        DJN 1,   TEMP
        DJN -1,  A
        DJN 1,   A
        DJN 1,   B
        DJN -2,  TEMP

Unfortunately, the performance is poor, 56000 cycles to execute a MOV!

The following code proves DJN is Turing complete by equivalence to SUBLEQ A, B, C:

         DJN 0,   TEMP
         DJN 1,   TEMP
         DJN 10,  B
         DJN 4,   SCRATCH
         DJN 3,   SCRATCH
         DJN 1,   TEMP
         DJN 1,   B
         DJN -2,  A
         DJN 1,   A
         DJN -1,  TEMP
         DJN C,   SCRATCH
         DJN C,   SCRATCH
         DJN -11, A
         DJN 1,   A
         DJN -1,  TEMP

So, who's volunteering to implement the first self-interpreter? ;-)

Happy 25th Birthday Core War

When David Jones and A. K. Dewdney produced their Core War Guidelines in March 1984, they could hardly have imagined the success it would achieve. Core War is still going strong 25 years later and I'd like to wish everyone in the Core War community a very happy birthday.

Core War, a Short History:

Shortly after the guidelines were complete, an article in Dewdney's Computer Recreations column in Scientific American introduce the world to Core War. The wheels on the Core War machine had been put in motion.

The following year the ICWS was formed to standardise and promote Core War, with Mark Clarkson as director. The ICWS published The Core Wars Standard and organised the First International Core War Tournament at the Computer Museum in Boston, Mass.

William R. Buckley began publication of The Core War Newsletter in early 1987, providing a forum for Core War players. Early issues covered what we now consider the basic techniques of Core War. Later issues discussed advance topics, for example the holy grail of Core War: self-repairing programs.

Core War, 25 Years On:

Fast forward to 2009. Dozens of players are competing on the Core War hills and the possibilities seem endless. I can't help wondering what a Core War player from 1984 would make of our battle programs, or if they ever imagined how we'd be creating them 25 years later. Computer optimized constants and evolved code are the order of the day.

The ICWS has fallen by the wayside, as has TCWN. However, a number of irregular Core War journals have florished and the online Core War community organise the occasional tournament as an alternative to competing on the hill.

Let's hope Core War is still going strong in 2034, to celebrate it's 50th birthday! :-)

More About Core War:

Here are the top resources to discover more about Core War:

• Beginner's Guide to Redcode covers the basics of Redcode, the language of Core War
• pMARS is a portable Core War virtual machine, implemented in C
• The Core War Bibliography lists tutorials covering almost every aspect of Core War
• KOTH.org and KOTH@SAL organise the King of the Hill tournaments, played by email
• Koenigstuhl is a huge archive of published Core War battle programs
• #corewars is the Core War IRC channel, hosted on irc.freenode.net

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

Underload Interpreter in Redcode

Underload is a stack-based esoteric programming language designed by ais523. A set of 8 single character instructions operate on a stack of variable length strings:

Ins	Description
:	copy the top stack entry
!	drop the top stack entry
~	swap the top two stack entries
*	join the top two stack entries
S	display then drop the top stack entry
^	drop then run the top stack entry
a	enclose the top stack entry in parentheses
( )	add a new stack entry

A combination of different factors make an interpreter for Underload an interesting project to tackle in Redcode:

• parsing single character instructions is easy, I don't like writing parsers
• handling variable length data can be tricky
• no operands / no side effects to worry about
• only 8 instructions, the size of the interpreter should be reasonable
• ^ is the only means of flow control

The final code weighs in at a mere 79 instructions. Here's the final version of the Underload Interpreter. If you have any improvements to suggest, please leave a comment below.