Programming without Control: Smith

Joy of joys, [Cat's Eye Technologies](http://catseye.mine.nu:8080/projects/), the home of Chris Pressey, one of the most prolific designers of thoroughly bizarre languages is back up! And so, today, we're going to take a look at one of his masterpieces, the language *Smith*. This is one of my personal all-time favorite pathological languages; it's positively brilliantly twisted.

Smith is, mostly, a pretty typical memory-oriented machine language. So what makes it pathological? It's got *no* jumps, *no* branches, *no* control flow whatsoever. The program counter starts at zero, and every step, it increments by one *and only one*.

So, you might quite sensibly ask, how on earth could this beast do anything useful, much less be Turing complete? The answer is: self-modifying code; in particular, the program can *copy* its own instructions.

Want to do a loop? No problem: it's just a set of instructions that repeats, right? So the last instruction *copies* the loop *including* the copy instruction. But how do you terminate the loop? There's no compare instruction!
You *compute* the number of instructions to copy. So you cleverly arrange to have a register holding the length of the loop *without* the copy instruction. And then you do a computation that winds up either adding 0 or 1 to that length.

Let's take a quick look at the instructions, so that we can show examples to make that a bit clearer. The SMITH machine is a pretty typical memory-based machine with the conditional branch and comparison instructions removed. Most operations work on memory locations, which SMITH calls registers. (They behave like memory, not like normal machine registers.) The basic values in the Smith language are literals (written as signed numbers); locations (written R*N*, where *N* is the numeric address); and the values stored in locations (written R[R*N*]);

The instructions are:

1. MOV target, value. Copy the value to the target. The target is either a register or TTY. If it is a register, it can be either a direct or indirect (RN or R[RN]); if it is TTY, then the value is copied to standard out. The value can be a literal, a register, an indirect register (N, RN, R[RN]), PC (for the value of the program counter), TTY (which reads a value from standard in), or "\*" which is the current line number in the source file.
2. MOV target, stringlit. A special form of MOV; stores the characters of stringlit in sequence at (target, target+1, target+2, etc.)
3. SUB target, value. Subtract the value from the target, storing the result in the target. Target is a register, either direct or indirect; value is either a register or a literal.
4. MUL target, value: multiply the target by the value, and store the result in the target. The parameters are the same as in "SUB".
5. NOT target. Target is a register. This is the closest thing to a conditional in SMITH. If the value of target is 0, then this makes it 1; if the target is non-zero, then this makes it 0. So this basically converts a value to a boolean and reverses it.
6. COR target, start, length. Copy a sequence of "length" instructions, starting with the instruction located "start" away from the PC to an address starting at an offset of "target" from the current PC. Start, target, and length can all be either literals or locations.
7. NOP. A no-op; does nothing. This gives us one of our two ways of doing something sort-of conditional; we can copy a NOP over another copy instruction.
9. STOP. End the execution of the program.
10. BLA target, NOP, length. Similar to the "COR" instruction, except that this just copies a sequence of "length" NOP instructions to the target offset.

There's also one pseudo-instruction, "REP". REP int, instruction inserts "int" copies of "instruction" at the current line of the source file. So "REP 3, NOP" is equivalent to three lines, each of which contains a single "NOP".

Now that we've seen the instructions, let's look at a classic "Hello world" program:

; Hello, world in SMITH - version 2 (loop)
; R0 -> index into string (starts at R10)
; R2 -> -1
MOV R0, 10
MOV R2, 0
SUB R2, 1
MOV R[R0], "Hello, world!"
MOV TTY, R[R0]
SUB R0, R2
MOV R1, R0
SUB R1, 23
NOT R1
NOT R1
MUL R1, 8
COR +1, -7, R1

* MOV,MOV,SUBL This starts by putting the value "10" into R0, and -1 into R2. 10 is the address where the "hello world" string is going to start; and the "-1" is going to be used for incrementing a pointer to the current index in the string. Since there is no "ADD" instruction, we have to stick with subtracting -1.
* MOV R[R0],string. Store "Hello world" starting at location 10.
* MOV TTY, R[R0]. Output the value stored at the address contained by location 0, which is initially 10 - that's the first character of the string.
* SUB R0, R2. Add one to R0, so that it points at the next character of the string.
* MOV R1, R0. Put the value of the pointer into the string into R1.
* SUB R1, 23. This is where it gets clever. 22 is the location of the last character of the string. So if R1 is now 23, then we've already output the last character. So by doing this subtraction, we end up with "0" in R1 if we've output the last character, or some negative value if we haven't.
* NOT R1/NOT R1. Converts whatever is in R1 into 0 (if we've output the last character already) or 1 (if we haven't).
* MUL R1, 8. There are 8 instructions to copy if we want to do another iteration of the loop. So multiple R1 by 8. If there's more iterations to be performed, R1 is now 8; if not, then R1 is now 0.
* COR +1, -7, R1. Copy R1 instructions to the *next* instruction address, starting from 7 instructions before here. So if we've already output all of the characters, this instruction copies 0 instructions, and we're at the end of the program. Otherwise, it copies 8 instructions - which is the loop.

Now, is that brilliantly evil, or what?

Here's another example - really quite a remarkably clever one. It does brace matching on an input file.

; Check input file for matching brackets in SMITH!
; Prints nothing if there was an error or 'OK' if brackets match.
; R0 -> stack pointer (starts at R32)
; R1 -> work register
; R2 -> -1
; R3 -> input char
; R4 -> scratch temp copy of PC
; R5 -> scratch temp copy of *
; R6 -> scratch for PC/* arithmetic
; R7 -> 2
; R8 -> 9
; R9 -> scratch char
; R10 -> 15
; R11 -> 1

; set up stack
MOV R0, 32
MOV R2, 0
SUB R2, 1
MOV R8, 9
MOV R7, 2
MOV R10, 15
MOV R11, 1
; push 'S'
MOV R[R0], "S"
SUB R0, R2
; LABEL MainLoop
; read char
MOV R3, TTY

; if char == '{' push
MOV R1, R3
MOV R[R8], "{"
SUB R1, R9
NOT R1
MUL R1, 2 ; LENGTH PushLeftBrace

MOV R4, PC ; R4 = PC
MOV R5, *
MOV R6, 0
SUB R6, 10048; bytes between here and PushLeftBrace
SUB R5, R6 ; R5 = PushLeftBrace
SUB R5, R4 ; R5 = PushLeftBrace - PC

BLA +2, NOP, R7

COR +1, R5, R1

NOP
NOP

; if char == '}' pop

MOV R1, R3
MOV R[R8], "}"
SUB R1, R9
NOT R1
MUL R1, 15 ; LENGTH PopLeftBrace

MOV R4, PC ; R4 = PC
MOV R5, *
MOV R6, 0
SUB R6, 10035; bytes between here and PopLeftBrace
SUB R5, R6 ; R5 = PopLeftBrace
SUB R5, R4 ; R5 = PopLeftBrace - PC

BLA +2, NOP, R10

COR +1, R5, R1

REP 15 NOP

; if char != 0 goto MainLoop

MOV R1, R3
NOT R1
NOT R1
MUL R1, 49 ; LENGTH MainLoop + 1

; LENGTH MainLoop
COR +1, -48, R1

REP 10000 NOP ; This space intentionally left blank

; x = pop

SUB R0, 1
MOV R1, R[R0]

; if x != 'S' stop

MOV R[R8], "S"
SUB R1, R9
NOT R1
NOT R1

COR +1, +6, R1

NOP

; print 'OK'

MOV R[R8], "O"
MOV TTY, R9
MOV R[R8], "K"
MOV TTY, R9

STOP

; LABEL PushLeftBrace
; push '{'
MOV R[R0], "{"
SUB R0, R2

; LENGTH PushLeftBrace == 2
; LABEL PopLeftBrace

; x = pop;

SUB R0, 1
MOV R1, R[R0]

; if x != "{" stop

MOV R[R8], "{"
SUB R1, R9
NOT R1
NOT R1

MOV R4, PC ; R4 = PC
MOV R5, *
MOV R6, 0
SUB R6, 1 ; bytes between here and Halt
SUB R5, R6 ; R5 = Halt
SUB R5, R4 ; R5 = Halt - PC
BLA +2, NOP, R11
COR +1, R5, R1
NOP
; LENGTH PopLeftBrace == 15
; LABEL Halt
STOP
; LENGTH Halt == 1

Because I'm a thoroughly insane person, I'm actually working on a brainfuck interpreter in SMITH. If I ever manage to get it working, I'll be sure to post it.