Interactive Fiction: 4K Adventure

I've always been a fan of text adventures - exploring a fantasy world, drawing a map and solving a few puzzles along the way. A couple of my early favourites were The Hobbit and Heroes of Khan. When I discovered shareware I spent hours puzzling over Humbug, Curses and t-zero. Even now I'm still working through The Lost Treasures of Infocom :-)

So when I needed a project to exercise my new 8086 assembly skills a text adventure seemed the natural choice. I decided to cram as much as possible into a 4K program - verb-noun parser, text decompression and a snowy forest to explore.

After 35 hours coding I'd created 4K Adventure complete with dwarves, mischievous elves and stolen magic. It managed to work despite the spaghetti code and a couple of dubious algorithms!

Impressed that I'd actually completed a project I immediately started work on a sequel and a simple operating system...  I still haven't completed either. Maybe one day ;-)

• 4K Adventure is available to download from The Interactive Fiction Archive and runs perfectly using DOSBox.

CoreLife: Artificial Life Simulator

A few years ago when using either Lycos or the WWWW (remember those?) to search for CoreLife I came across a program with the same name. The program I discovered is an artificial life simulator written by Erik de Neve.

CoreLife supports two VCPUs:

• The CoreLife VCPU - supports 32 instructions that resemble 8086 assembly
• The Tierra VCPU - supports the 32 instructions of Thomas Ray's software

After seeding memory with a handwritten organism the simulation begins. Each organism attempts to replicate while the simulator randomly mutates instructions or causes them to fail. Thanks to the mutation the copied organism often differs slightly from the parent.

In some cases the mutation renders the child organism less effective or too damaged to replicate. In other cases the child is smaller and faster, able to out-replicate the less efficient parent.

Watching the code evolve made me wonder if I could beat evolution. I set myself a challenge: could I create the ultimate organism to out-replicate everything else and resist mutation?

Unfortunately any attempt to resist mutation quickly died out so I settled for creating the smallest self-contained replicator, just 22 instructions:

;22 Instruction Replicator
;for the Tierra Virtual CPU
nop_1
adrb
nop_0
push ax
sub_ac
divide
mov_ab
adrf
nop_1
sub_ab
inc cx
mal
nop_1
dec cx
mov_ii
ifz
ret
inc bx
inc ax
jmpb
nop_0
pop dx

• CoreLife is available on Erik de Neve's webpage and runs perfectly using DOSBox.

Recursion via Pascal

Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming. Recursion is a technique where a problem is defined in terms of a simpler version of itself.

The book has over 100 examples and although the code is in Pascal it shouldn't pose too much of a problem for C / Java programmers.

Factorials are the classic example of recursion:

The factorial of a number n (written as n!) is the product of all positive integers below or equal to n.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.

n! can be defined recursively as:

0! = 1
n! = n × (n-1)!

Here's the code to calculate factorials in Pascal:

function factorial( n:integer ):integer;
begin
    if n = 0 then
        factorial := 1
    else
        factorial := n * factorial( n-1 )
end

Or in C:

unsigned int factorial( unsigned int n )
{
    if ( n == 0 )
        return 1;
    else
        return n * factorial( n-1 );
}

Or Forth:

: factorial
    dup 0= if
        drop 1
    else
        dup 1- recurse *
    then
;

Rohl first examines some simple examples of recusion: factorials, highest common factor and displaying numbers before moving on to more advanced topics:

• two-level procedures
• recursive data structures
• binary recursion
• recursive sorting algorithms
• mutual recusion

Throughout the book Rohl compares the runtime / complexity to the equivalent iterative code and warns against any potential pitfalls. My favourite example is the code to calculate x^n from “developing the power example, a cautionary tale”:

function p(x:real; n:integer):real;
begin
  if n = 0 then
    p := 1
  else if odd(n) then
    p := p( x, n div 2 ) * p( x, n div 2 ) * x
  else
    p := p( x, n div 2 ) * p( x, n div 2 )
end

Thanks to a small oversight the order of complexity is Ο(n) instead of Ο(log n).

Recursion via Pascal was published in 1984 but remains relevant despite it's age. The text is easy to follow and I'd recommend the book to anyone curious enough to delve further into recursion :-)