SMITH
=====
**S**elf-**M**odifying **I**ndecent **T**uring **H**ack
Version 2.1-2012.0916.
Copyright ©2000-2012 Chris Pressey, Cat's Eye Technologies.
All rights reserved.
* * * * *
> "This space intentionally left blank."
>
> — MIT's *Dungeon* (later Infocom's *Zork I*)
> "The only thing that really worried me was the ether. There is nothing
> in the world more helpless and irresponsible and depraved than a man
> in the depths of an ether binge. And I knew we'd get into that rotten
> stuff pretty soon."
>
> — Hunter S. Thompson, *Fear and Loathing in Las Vegas*
What is SMITH?
--------------
SMITH, the successor to [SMETANA][], is a programming language that goes
one better than [Bullfrog][]. Not only are there no conditional jumps,
there are no jumps **whatsoever**. The program counter can *only* be
incremented, and *only* instruction by instruction.
[SMETANA]: http://catseye.tc/projects/smetana/
[Bullfrog]: http://esolangs.org/wiki/Bullfrog
### What the...???
*But*, you ask, *how can such an ungodly beast be Turing-Complete?
Surely this goes against all that is decent and good and sane in the
world we know.* (OK, maybe you won't put it exactly that way - I forgive
you.)
Well, there's actually a relatively straightforward answer. Instead of
jumping back into code to repeat and/or recheck something, you must
instead copy blocks of code forward, where they will be checked in the
near future.
And if the code copied forward includes the instruction that *caused*
the copy in the first place, that will happen again (and again and
again) when the copy executes. A loop, but not by means of iteration or
recursion but instead by *self-propogation*.
Otherwise, SMITH is basically a small generic imperative CISC-ish
virtual machine with only the most basic arithmetic operations, loosely
modelled on the "[imaginary] register machine that is representative of
several minicomputers" described in section 9.2 of the Dragon Book.
And when I say loosely modelled, I mean it. Differences between this and
the 'Dragon' machine include the fact that this has no `ADD`
instruction, and that here, the destination is specified *before* the
source (not after;) also, the `#` before an immediate (literal) is
allowed but not required here, and the indirection syntax is completely
different (there's only indirect references to registers, not memory,
anyway.)
Overview
--------
Consider the SMITH machine to have an unlimited number of registers.
These are called `R0` to `Rn` where no arbitrary limit is imposed on
`n`. In some instructions, they may be referenced indirectly, and in
that case they are called `R[R0]` to `R[Rn]`.
An indirect reference like `R[R0]` refers to 'the register whose number
is the number stored in register zero.' If `R0` contained 7, then
`R[R0]` would be synonymous with `R7`.
Each instruction has the general form:
OPCODE [destination[, source[, length]]]
(Here, the square breackets denote "may be omitted", not indirect
references.)
`destination` is either the name of a register or an immediate offset
from the current program counter. `source` is either a register, an
immediate offset from the current program counter, or an immediate
integer. `length`, if present, is the name of a register. All integers
are notated in decimal. `#` may precede immediate integers if the
programmer desires. However, it may not precede offsets (they should be
preceded by either `+` or `-`.)
Instructions
------------
The basic instructions (available in the original version) are:
MOV register, immediate e.g. MOV R0, 0
MOV register, register MOV R1, R0
SUB register, immediate SUB R1, 1
SUB register, register SUB R0, R1
MUL register, immediate MUL R0, 2
NOT register NOT R0
COR offset, offset, register COR +1, -5, R0
STOP STOP
The instructions in the following table were made available in SMITH v2
(June 25 2000).
MOV [register], register MOV R[R1], R0
MOV register, [register] MOV R1, R[R0]
MOV [register], "string" MOV R[R0], "nights and weird mornings"
MOV register, PC MOV R303, PC
MOV register, * MOV R304, *
MOV TTY, register MOV TTY, R1
MOV TTY, [register] MOV TTY, R[R65535]
MOV register, TTY MOV R0, TTY
MOV [register], TTY MOV R[R0], TTY
MUL register, register MUL R999999999, R123456789
COR offset, register, register COR +1, R22, R23
BLA offset, NOP, register BLA +2, NOP, R10
NOP NOP
SMITH v2 also added two directives:
; arbitrary text comprising a source comment ; Kilroy was here
REP int OPCODE [destination[, source[, length]]] REP 50 STOP
Explanation
-----------
`MOV` will assign a register a value without modifying it.
The `TTY` forms of `MOV` are just a lazy way to refer to some
(potentially complex) system routine for the 'usual' input and output
character streams, so the program can communicate (in some primitive
fashion) with the user.
The `PC` and `*` forms of `MOV` facilitate calculating absolute
addresses of subroutines. Actually, `*` is more like a macro which
expands to the current line number in the source file.
The `"string"` form of `MOV` moves each character of the immediate
string into a successive register. If `R0` contained 7, then
`MOV R[R0], "cat"` would result in `R7 == 'c', R8 == 'a', R9 == 't'`.
`SUB` and `MUL` will subtract or multiply a register by a value,
respectively. `NOT` will boolean-negate a register (false = 0/zero, true
= 1/nonzero.)
`COR` is the truly interesting opcode; it stands for `CO`py by
`R`egister. The value of the length operand (which is always in a
register) is a count of instructions. This many instructions is copied
from the source offset (which may be immediate or in a register) to the
destination offset (which is always immediate), modifying the program
(thus, self-modifying code.)
> Note: prior to version 2007.0722 of the SMITH language, the result of
> actually **overwriting** existing instructions with other instructions
> was not defined. The original idea was that SMITH programs would
> merely **extend** themselves by copying bits of themselves to just
> past the end of the program, like Sylvester chasing Tweety around the
> Christmas tree on a toy train -- and I still think that's all that's
> needed for SMITH to be Turing-complete. However, since the language
> does reasonably claim to be fully "self-modifying" and not just
> "self-extending" (SEITH?!?), it's official: as of version 2007.0722,
> you can overwrite instructions with other instructions using `COR`.
> Even when the source and destination ranges of such a copy overlap,
> the resulting series of instructions at the destination should be an
> exact copy of the series at the source.
>
> > Note note: It seems some of you are having trouble understanding the
> > version system being used for SMITH, which is eminently
> > understandable given that it is completely inconsistent. The first
> > version had no version. The second version, released a scant few
> > days later, containing many new instructions, was "v2". That version
> > was re-christened "version 2.0L" when we added the BSD license to it
> > (because "L" is for "license", y'see?) The third version, released a
> > scant few years later, was "version 2007.0722". This was back when
> > we thought date-based version numbers could substitute entirely for
> > sequence-based version numbers. This version was also known as
> > "version 2.1 revision 2007.0722" when we dropped that idea. The
> > current version, which differs mainly in that its documentation
> > contains this paragraph, is version **2.1-2012.0916**. Your
> > knowledge is now complete. Go home.
`BLA` is kind of a special version of `COR` that makes some programming
a lot easier. It stands for `BLA`nk and as part of it's very special
format it takes an *immediate opcode* as its second argument. It copies
that opcode (which must be either `NOP` or `STOP`) to the offset, and
uses the number found in the length register as a multiplier.
Execution starts at the beginning of the program (well, naturally,) and
stops when the program counter tries to execute beyond the last
instruction specified in the program. A `STOP` instruction will also
serve this purpose, if you choose to use it.
### Huh.
So there you go. Myth debunked. You don't need `if` or `goto` or `while`
or anything so fancy to be Turing-Complete. All you need is to be able
to `memcpy` yourself! Don't that just take the cake?