Home

Screen Shots

Overview

Getting Started

Organisms and Cells

Spores

Genetics

KFORTH Language

Mutations/Replication

Simulation

CPU Architecture

Activities

FAQ

Links

The KFORTH Language

• Introduction
• Labels
• Registers
• Comments
• Flow Control
• Nested Code Blocks
• Data Types
• RAM
• Self Modifying Code
• Traps and Trap Handlers
• Trap Safety
• Protections
• Interrupts
• Interrupt Safety
• Instruction Reference
• Examples

Introduction:

So you want to learn KFORTH, do you? Well lets start with a simple example.

First launch the KFORTH Interpreter from the Evolve program. You'll see this dialog:

Now lets write a program to subtract two years. In the KFORTH SOURCE CODE pane enter the following KFORTH program:

{ 2022  1968 - }

All KFORTH instructions must be enclosed within curly braces. This is called a "code block". Code blocks are assigned numbers starting with 0. Inside of the curly braces goes "the code". This consists of numbers and instructions (using in postfix notation).

Now press the [Compile] button. And this is what you will see in the upper pane:

main:
{
     2022  1968 -
}

The compiled version looks very similar to what we typed it. The first thing to note is the label main: was added in front our code block. In KFORTH the first code block (code block 0) is where program execution starts. That is why the disassmbler inserted the label main:.

Now click on [RUN]. The answer '54' will appear in the data stack pane. You can also single-step through this example. To single step, first press [Reset].

Lets add another code block to this example.

Your neighbor is building a BBQ, to measure for the foundation he needs to know what 'x' is (I know, lame example, but I'm hungry right now). You want to help him so he'll invite you over for BBQ. You realize that this is a perfect job for KFORTH! We will add a new code block to our example, which when executed will compute 'x':

Here, type this:

{ 2022 1968 - }
{ 98 dup * 71 dup * + sqrt }

When you compile this program, the disassembly will be shown as:

main:
{
	2022 1968 -
}

row1:
{
	98 dup * 71 dup * + sqrt
}

The disassembler gives every code block a label. The first one, as we already saw is called main: subsequent code blocks are labeled row1, row2, row3 and so on...

Now click on [Run]. Whoooa! What the fuck? The data stack only shows the same value '54'? What's wrong?

The problem is KFORTH automatically executes code block 0, but all other code blocks must be explictly called, using the call instruction.

Let's try this again.... Now we will add '1 call' to the end of the first code block, like so:

{ 2022 1968 - 1 call }
{ 98 dup * 71 dup * + sqrt }

Now click on [Compile] and then [Run].

Hopefully, when the program terminates there are two items on the stack. '121' and '54'. The '121' is the answer to our "find x?" problem. Since KFORTH only uses integers the answer has been rounded to the nearest whole number.

This example shows how code blocks are treated as executable functions. The call instructions pops a number from the top of the data stack and treats it as a code block number, and calls that code block.

When humans write KFORTH they should use labels, so here is the same program with labels added:

main:
	{ 2022 1968 - findx call }

findx:
	{ 98 dup * 71 dup * + sqrt }

When your [Compile] this, your labels are lost and the disassembler picks labels like: "main, row1, row2, row3, ...". Anyway, here is what you'll see in the disassembly pane:

main:
{
	2022 1968 - 1 call
}

row1:
{
	98 dup * 71 dup * + sqrt
}

Also notice the label before the call instruction is 1 not row1. This is because the disassembler cannot reliably regenerate labels INSIDE of code blocks (I don't want to go into the reasons why, but you could calculate the code block number rather than hard code a value).

Labels

A label is any text followed by a colon :'. A label can consist of any characters except: whitespace, colon :', semi-colon ;', or curly braces {', }'. Also, a label cannot clash with the name of an existing instruction.

To define a label simply follow it by a colon (without spaces). The value of the label is the next code block number to be assigned (code block numbers are assigned startig at 0 and then incrementing by 1 for each new code block).

To use a label, just enter its name (do not use colon). The compiler will convert this label reference to the code block number.

Case Insensitive

Instructions and labels are case insensitive. So "MAKE-SPORE" is the same as "Make-Spore".

Registers

The KFORTH computing model includes ten registers R0 through R9. These can be used to store/retrieve temporary values. For example,

main:
{	2022 1968 - R1!
	findx call R5!
	R1 R5 + R9!
}

findx:
{
	98 dup * 71 dup * + sqrt
}

This is the same example as before, but we have added 'R5!' and 'R1!'. These instructions take the value on top of the data stack and stores it into the indicated register.

The line R1 R5 + R9! fetches the value of R1 and R5 and adds these values and then writes the result to register R9.

Registers are not used by any KFORTH instructions, so they can be managed and used by the user without worrying about conflicts.

Comments

Use the semi-colon ; to insert a comment into a KFORTH program. The rest of the line after the semi-colon is ignored.

; my first KFORTH program
main:
{
	2022 1968 - R1! ; compute difference between 2022 and 1968
	findx call R5!  ; call the findx routine and store in result in R5.
	R1 R5 + R9!
}

; my first KFORTH subroutine
findx:
{
	98 dup * 71 dup * + sqrt
}

Stack Underflow

It can be expected that a mutated KFORTH program would attempt instructions without having enough data on the data stack. How does KFORTH handle this?

KFORTH's policy for stack underflow is to treat the operation as a NO-OP. Meaning the program just continues to the next instruction without removing anything from the stack.

For example, this code calls the plus (+) instruction but only 1 data item is on the stack.

main:
{
	200 + 3 *
}

The '+' operation needs two values on the stack. Since this is not the case, the stack underflow policy is to simply proceed to the next instruction. When the '*' operation is executed it finds two values on the data stack, so it is able to perform its job (computes 600, replacing 200 and 3 on the data stack).

Undefined Functions

In addition to stack underflow, sometimes the value to an instruction (a function) are not defined. For example division by 0 and trying to take the square root of a negative number. Therefore, div mod, and /mod will act as NO-OP instructions when the second operand is zero. And when the argument to sqrt is negative the instruction leaves the stack unchanged.

Flow Control

We already know about the call instruction, which transfers control to a new code block. What else can we do? KFORTH includes the following instructions for flow control:

• call - call a code block
• if - call a code block IF true
• ifelse - call one of two code blocks IF true/false
• ?loop - jump to beginning of code block if true
• ?exit - jump to end of code block if true
• trap1 ... trap9 - call one of the trap handlers

call

We have already seen this instruction at work. It's the unconditional form of subroutine call. Below we explore if and ifelse which are conditional subroutine call instructions.

You may be wondering what "call" does with a bogus code block number? For example, "-900 call", or "555 call". When call instruction (and if, ifelse) is used with a bogus code block number, it removes the values from the stack, as if this were a normal instruction, but it won't call any code block. Conceptually, we can think of a KFORTH program as having empty rows for every possible integer (except the ones that have been defined).

main:
{
	5000 call
}

row1: { }
row2: { }
row3: { }
row4: { }
row5: { }
row6: { }
...
row9999999: { }

if

Here's an example of using the IF instruction.

main:
{
	521 R1!
	R1 dup 500 >= blah if
}

blah:
{
	500 -
}

This code checks if R1 is greater than 500 and if true, calls the subroutine blah. Blah will subtract 500. The 'dup' instruction creates a 2nd copy of R1 on the data stack.

Nested Code Blocks:

main:
{
	521 R1!
	R1 dup 500 >= { 500 - } if
}

We nested the code block that use to be blah, directly into main. If you [Compile], you'll notice that the nesting is removed. This reveals how the nesting actually works. Nesting code blocks is just for human convienience.

When compiled it maps to the orginal version we wrote that used the code block blah, see:

main:
{
	521 R1! R1 dup 500 >= 1 if
}

row1:
{
	500 -
}

Nesting can be of unlimited depth. But, again this nesting is a lexical feature, and does not imply and special powers in the KFORTH language. It is simply a way to make writing KFORTH programs simpler.

ifelse

This instruction calls one of two code blocks depening on if the condition is true or false.

main:
{
	499 R1!
	R1 dup 500 >=
		{ 500 - R1! }
		{ 2 / R1! }  ifelse
}

First notice that the KFORTH compiler is free-format, allowing you to space your KFORTH programs any way which you desire.

This is what the code will be converted into by the compiler:

main:
{
	499 R1! R1 dup 500 >= 1 2 ifelse
}

row1:
{
	500 - R1!
}

row2:
{
	2 / R1!
}

Which does the same as this C code:

/* C code, not KFORTH */
void main()
{
	int R1;

	R1 = 499;
	if( R1 >= 500 ) {
		R1 = R1 - 500;
	} else {
		R1 = R1 / 2;
	}
}

The ifelse instruction requires three arguments to be on the data stack. If this is not the case, then the stack underflow policy is to just treat the ifelse as a no-op.

?loop

As this awsome diagram illustrates, the ?loop instruction loops! It is a form of controlled goto. It does not do a subroutine call, instead we simply branch back to the beginning of the current code block (if the value on top of the stack is non-zero). Otherwise we continue to the next instruction.

main:
{
	{ ...stuff... 1 ?loop } call
}

The instructions 1 ?loop causes execution to return to the start of the code block, therefore this will loop forever running the instructions ...stuff....

?exit

This diagram shows how the exit instruction works. The ?exit instruction conditionally exits (branches to the end of the code block) the current code block. If the top of the data stack is non-zero then we jump to the end of the code-block. Otherwise we continue to the next instruction. As with ?loop, this instruction does not involve any subroutine calling. It is a branch.

These are the only branching instructions in KFORTH.

DATA TYPES

KFORTH has the most elaborate and rich data types in the whole history of computer languages!!!! Bwhahahahaha! Just kidding. KFORTH only has one data type: a 16-bit signed integer.

That's it. There are no strings, booleans, arrays, etc...

A 16-bit number isn't very large. Here is the min/max range of this data type:

-32,768 to +32,767

Only decimal notation is accepted. Numeric literals may be preceeded by a minus (-) sign to indicate a negative value.

RAM

The kforth program is itself a memory store. It appears to be just code, but it is in fact a read and write storage. The numbers and instructions share the same 16-bit word. This means numbers stored in RAM must be reduced to 15-bit values by dropping the top bit.

The instructions: NUMBER, NUMBER!, ?NUMBER!, OPCODE, OPCODE! read and write to RAM. There are 16,000 code block addressess. And each code block can hold 16,000 values. This gives about 256MB of storage.

Before:

main:
{
	666 mydata 2 NUMBER!
	777 mydata 5 NUMBER!
}
mydata: { 0 0 0 0 0 0 0 }

After:

main:
{
	666 mydata 2 NUMBER!
	777 mydata 5 NUMBER!
}
mydata: { 0 0 666 0 0 777 0 }

Self Modifying Code

The previous example shows that the program area can be written to. In addition to being able to read & write numbers, you can write instructions with the OPCODE! instruction.

Before:

main:
{
	OPCODE' >= myfunc 2 OPCODE!
	OPCODE' ?exit myfunc 3 OPCODE!
}
myfunc: { nop nop nop nop }

After:

main:
{
	OPCODE' >= myfunc 2 OPCODE!
	OPCODE' ?exit myfunc 3 OPCODE!
}
myfunc: { nop nop >= ?exit }

Traps & Trap Handlers

There are 9 instructions, TRAP1, TRAP2, ..., TRAP9, which are for implementing system calls. The trap instructions call the code block numbers 1, 2, ... 9. They are the same as,

 {
	trap2		; call code block 2
	2 call		; call code block 2, if not going from unprotected to protected code.
 }

The difference between trap2 and 2 call is the call instruction respects the boundary between the protected code and unprotected code. Unprotected code cannot call protected code (unless a trap is used).

You can reserve the first 10 code blocks for your trap handlers. Then protect your code. Here _trap9 is the label for the 9th code block. It will get called when the instruction trap9 is executed.

main:
{
	evolve call
}

_trap1: { }
_trap2: { }
_trap3: { }
_trap4: { }
_trap5: { }
_trap6: { }
_trap7: { }
_trap8: { }
_trap9: { EAT }

; ---- protected / unprotected ----

evolve: { 10 -9 trap9  }

How does this help implement system calls? If you split your program into two parts. A protected part and an unprotected part. You can implement special operations that only protected code can do. You can expose this functionality as a trap handler. Now the unprotected code must call a trap to use this functionality.

In this example EAT is the special operation. To make this special you would mark this instruction as PROTECTED. That way it won't be available in the unprotected part of the program.

Trap Safety

If you write your own evolving robots with traps/interrupts you will discover that evolving code will call your trap handlers with all possible stack states. A full or partially full data stack can cause your protected code to misbehave and end up doing unintended things. Evolution likes to exploit such opportunities. This section covers how to protect your trap handler.

The trap instruction will not call the trap handler unless there are at least 2 data stack elements available on the data stack. If there is not, then the trap instruction behaves like NOP. There must also be 1 call stack element available to perform the subroutine call to the trap handler. This is done so that the trap handler can always perform safety checks such as these:

_trap7: {
	DSLEN 60 > ?exit
	CSLEN 59 > ?exit
	DSLEN 3 < ?exit		; make sure three arguments provided
	do_something call
}

Here we ensure there at least 4 (64-60) data stack elements and 5 (64-59) call stack elements available before proceeding. Why are these safety checks important? Because the caller won't be expected to follow your API conventions. The caller of this trap could be evolving code, which could have all of their stacks filled up. Or any other strange state.

Why is this a concern? Why not allow the trap handler to fail in strange ways when the evolved code has called you in strange ways? Won't this just harm the evolving creature and it won't persists? It ends up exposing a whole host of functionality you didn't intend to the evolving code, and that will mess up your newly invented physics.

Protections

This section documents the properites of Protected Code Blocks and Protected Instructions. See the section, CPU Architecture, for a good explaination of protections. Here are the rules they follow inside the simulator.

Protected Instructions

A protected instruction,

1. will not be generated by the mutation algorithm


2. cannot be generated by OPCODE, OPCODE! and OPCODE' (when executed in unprotected code)

This applies to the 'insert code block' and 'insert instruction' mutations as well as the 'modify instruction' and 'modify code block' mutations.

This means you are allowed to have a kforth program that starts out with protected instructions inside of unprotected code. There is no restriction on this (by the rules above).

But if you choose to make an instruction only available to your protected code, then you shouldn't put any protected instructions into the unprotected zone, this would defeat the purpose.

Protected Code Blocks

A protected code block,

1. will not be mutated by the mutation algorithm


2. is not callable from unprotected code (except via TRAP instructions)


3. is not readable from unprotected code (CBLEN / OPCODE / NUMBER / ?NUMBER! instructions)


4. is not writable from unprotected code (OPCODE! / NUMBER! / ?NUMBER! instructions)

Configuring: Use this dialog to configure protections.

Them's the rules.

Interrupts

Some of the instructions that interact with other cells can be configured to interrupt the cell which was acted on. For example, the SEND instruction will write a value to another cell, but if configured, it will also cause that other cell to be interrupted.

When a cell is interrupted its flow of control transferred to one of the trap handlers.

Masking: All interrupt handling logic will mask an interrupt if it finds that the target cell is already running inside of the corresponding trap code block. If you transfer control to another code block number, then you will need to set a flag to ensure the interrupt remains masked (See Interrupt Safety below).

Other rules: As with traps, if the data stack does not have 2 elements available, then the interrupt will not be triggered. Also, at least 1 call stack element must be available to perform the subroutine call to the trap handler.

Configuring: There are three bits in the Instruction Modes for some instructions. These three bits control which trap handler will be called. This only allows trap's 1 thru 7 to be configured (not trap8 or trap9). For example a three bit value of 110 corresponds to trap6.

Interrupt Safety

The normal trap safety applies to interrupt handlers. You will want to add a way to check if you are already inside of the interrupt handler. If you keep your logic within the original trap handler you are okay, because the interrupt will be masked for you. But if you call another code block, you'll need to check a flag.

With the test-and-set instruction you can ensure only one cell enters the interrupt handler logic. When done, you clear the flag, and the interrupt is re-activated.

;
; interrupt handler.
; 'flag' will be set to 1 if somebody is already servicing this interrupt.
;
_trap3: {
    DSLEN 60 > ?exit
    CSLEN 59 > ?exit
    1 flag 0 ?NUMBER!  not ?exit   ; check lock flag
    do_something call
    0 flag 0 NUMBER!        ; clear the flag, re-enable this interrupt.
}

...

do_something:
{
    ...
}

flag: { 0 }

KFORTH INSTRUCTION REFERENCE

The core KFORTH instructions are summarized below, complete instruction documentation is available here.

The instructions that control organisms/cells are listed here.

The USAGE column uses forth notation to document these instructions. This notation attempts to show the data stack before and after the call to the instruction. For example,

(a b c -- n )

The stuff before -- is the state of the data stack before calling the instruction. And the stuff after -- is state of the data stack AFTER this instruction finishes.

In this example, the instruction takes three arguments a, b, and c. After the instruction executes those three arguments are replaced with a single value n (which is the result).

Example Code 1

main:
{

    3 cube call
    99 cube call

   ; this line computes (9^3)^3
   9 cube call cube call

}

;
; cube the value on top of the stack
;
cube:
{
    dup dup * *
}

Example Code 2

main:
{
	20 fact call
}

;
; Recursive factorial algorithm:
; ( n -- factorial(n) )
;
fact:
{
	dup 0 =
		{ pop 1 }
		{ dup 1 - fact call * } ifelse
}

Example Code 3

;
; compute: (R0 * 8 / R3 + R1) * R2
;
; Where:
;   R0 = 10
;   R1 = 20
;   R2 = 5
;   R3 = 2
;
main:
{
    10 R0!
    20 R1!
    5  R2!
    2 R3!

   R0 8 * R3 / R1 + R2 *
}

Example Code 4

main:
{
	20 fact call
}

;
; non-recursive factorial algorithm:
; ( n -- factorial(n) )
;
fact:
{
    1 swap
    {
        dup 0 = ?exit
        dup 1- -rot
        * swap
        1 ?loop
    } call

    pop
}

Example Code 5

;
; use code blocks as a form of array/table lookup.
; This will fetch the pair (5, 6) from the "table":
;
main:
{
    mytable 3 + call
}


mytable:
   { 2 3 }		; index 0
   { 1 1 }		; index 1
   { 3 4 }		; index 2
   { 5 6 }		; index 3
   { 10 5 }	; index 4

Example Code 6

;
; Code blocks can also be used as a cheap
; way to implement named contants.
; (see PI).
;
main: {
	ugly call 100 511 897 + + +
}

ugly: {
    987 PI call +
}

; a constant, as a code block
PI: { 3 }

Example Code 7

;
; look_n_fertilize
; ----------------
;
; USAGE: (x y e -- r)
;
; DESCRIPTION:
;	This subroutine looks for a spore in direction (x, y).
;	If a spore is found, then ferilize it with a second
;	spore with energy 'e'
;
; RETURNS
;	0 is no spore found, or could not create a spore
;	1 is returned on success
;
; HOW TO CALL:
;	1 0 5 look_n_fertilize call
;
look_n_fertilize:
{
	-rot 2dup look-spore
		{ rot make-spore } { 2pop pop 0 } ifelse
}

Example Code 8

main:
{
    -100 19 normalize call
    -40 -234 normalize call
}

;
;  ( x y -- NORM(x) NORM(y) )
;
; normalized a pair of values:
;
normalize:
{
         norm1 call swap norm1 call swap
}

;
; (n -- NORM(n))
;
; Compute this function:
;
;	n < 0	NORM(n) = -1
;	n = 0	NORM(n) = 0
;	n > 0	NORM(n) = 1
;
norm1:
{
	dup 0 > { pop 1 } { 0= { 0 } { -1 } ifelse } ifelse
}

Example Code 9

See an example of Towers of Hanoi in KFORTH.