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.
\nSmith 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*.
\nSo, 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.<\/p>\n
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. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-170","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-2K","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/170\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nWant 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!
\nYou *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.
\nLet’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*]);
\nThe instructions are:
\n1. MOV target, value<\/code>. 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.
\n2. MOV target, stringlit<\/code>. A special form of MOV; stores the characters of stringlit in sequence at (target, target+1, target+2, etc.)
\n3. SUB target, value<\/code>. 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.
\n4. MUL target, value<\/code>: multiply the target by the value, and store the result in the target. The parameters are the same as in “SUB”.
\n5. NOT target<\/code>. 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.
\n6. COR target, start, length<\/code>. 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.
\n7. NOP<\/code>. A no-op; does nothing. This gives us one of our two ways of doing something sort-of conditional; we can copy a NOP<\/code> over another copy instruction.
\n9. STOP<\/code>. End the execution of the program.
\n10. BLA target, NOP, length<\/code>. Similar to the “COR” instruction, except that this just copies a sequence of “length” NOP<\/code> instructions to the target offset.
\nThere’s also one pseudo-instruction, “REP<\/code>“. REP int, instruction<\/code> inserts “int” copies of “instruction” at the current line of the source file. So “REP 3, NOP<\/code>” is equivalent to three lines, each of which contains a single “NOP<\/code>“.
\nNow that we’ve seen the instructions, let’s look at a classic “Hello world” program:
\n; Hello, world in SMITH – version 2 (loop)
\n; R0 -> index into string (starts at R10)
\n; R2 -> -1
\nMOV R0, 10
\nMOV R2, 0
\nSUB R2, 1
\nMOV R[R0], “Hello, world!”
\nMOV TTY, R[R0]
\nSUB R0, R2
\nMOV R1, R0
\nSUB R1, 23
\nNOT R1
\nNOT R1
\nMUL R1, 8
\nCOR +1, -7, R1
\n* MOV,MOV,SUB<\/code>L 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.
\n* MOV R[R0],string<\/code>. Store “Hello world” starting at location 10.
\n* MOV TTY, R[R0]<\/code>. Output the value stored at the address contained by location 0, which is initially 10 – that’s the first character of the string.
\n* SUB R0, R2<\/code>. Add one to R0, so that it points at the next character of the string.
\n* MOV R1, R0<\/code>. Put the value of the pointer into the string into R1.
\n* SUB R1, 23<\/code>. 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.
\n* NOT R1\/NOT R1<\/code>. Converts whatever is in R1 into 0 (if we’ve output the last character already) or 1 (if we haven’t).
\n* MUL R1, 8<\/code>. 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.
\n* COR +1, -7, R1<\/code>. 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.
\nNow, is that brilliantly evil, or what?
\nHere’s another example – really quite a remarkably clever one. It does brace matching on an input file.
\n; Check input file for matching brackets in SMITH!
\n; Prints nothing if there was an error or ‘OK’ if brackets match.
\n; R0 -> stack pointer (starts at R32)
\n; R1 -> work register
\n; R2 -> -1
\n; R3 -> input char
\n; R4 -> scratch temp copy of PC
\n; R5 -> scratch temp copy of *
\n; R6 -> scratch for PC\/* arithmetic
\n; R7 -> 2
\n; R8 -> 9
\n; R9 -> scratch char
\n; R10 -> 15
\n; R11 -> 1
\n; set up stack
\nMOV R0, 32
\nMOV R2, 0
\nSUB R2, 1
\nMOV R8, 9
\nMOV R7, 2
\nMOV R10, 15
\nMOV R11, 1
\n; push ‘S’
\nMOV R[R0], “S”
\nSUB R0, R2
\n; LABEL MainLoop
\n; read char
\nMOV R3, TTY
\n; if char == ‘{‘ push
\nMOV R1, R3
\nMOV R[R8], “{”
\nSUB R1, R9
\nNOT R1
\nMUL R1, 2 ; LENGTH PushLeftBrace
\nMOV R4, PC ; R4 = PC
\nMOV R5, *
\nMOV R6, 0
\nSUB R6, 10048; bytes between here and PushLeftBrace
\nSUB R5, R6 ; R5 = PushLeftBrace
\nSUB R5, R4 ; R5 = PushLeftBrace – PC
\nBLA +2, NOP, R7
\nCOR +1, R5, R1
\nNOP
\nNOP
\n; if char == ‘}’ pop
\nMOV R1, R3
\nMOV R[R8], “}”
\nSUB R1, R9
\nNOT R1
\nMUL R1, 15 ; LENGTH PopLeftBrace
\nMOV R4, PC ; R4 = PC
\nMOV R5, *
\nMOV R6, 0
\nSUB R6, 10035; bytes between here and PopLeftBrace
\nSUB R5, R6 ; R5 = PopLeftBrace
\nSUB R5, R4 ; R5 = PopLeftBrace – PC
\nBLA +2, NOP, R10
\nCOR +1, R5, R1
\nREP 15 NOP
\n; if char != 0 goto MainLoop
\nMOV R1, R3
\nNOT R1
\nNOT R1
\nMUL R1, 49 ; LENGTH MainLoop + 1
\n; LENGTH MainLoop
\nCOR +1, -48, R1
\nREP 10000 NOP ; This space intentionally left blank
\n; x = pop
\nSUB R0, 1
\nMOV R1, R[R0]
\n; if x != ‘S’ stop
\nMOV R[R8], “S”
\nSUB R1, R9
\nNOT R1
\nNOT R1
\nCOR +1, +6, R1
\nNOP
\n; print ‘OK’
\nMOV R[R8], “O”
\nMOV TTY, R9
\nMOV R[R8], “K”
\nMOV TTY, R9
\nSTOP
\n; LABEL PushLeftBrace
\n; push ‘{‘
\nMOV R[R0], “{”
\nSUB R0, R2
\n; LENGTH PushLeftBrace == 2
\n; LABEL PopLeftBrace
\n; x = pop;
\nSUB R0, 1
\nMOV R1, R[R0]
\n; if x != “{” stop
\nMOV R[R8], “{”
\nSUB R1, R9
\nNOT R1
\nNOT R1
\nMOV R4, PC ; R4 = PC
\nMOV R5, *
\nMOV R6, 0
\nSUB R6, 1 ; bytes between here and Halt
\nSUB R5, R6 ; R5 = Halt
\nSUB R5, R4 ; R5 = Halt – PC
\nBLA +2, NOP, R11
\nCOR +1, R5, R1
\nNOP
\n; LENGTH PopLeftBrace == 15
\n; LABEL Halt
\nSTOP
\n; LENGTH Halt == 1
\nBecause 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.<\/p>\n","protected":false},"excerpt":{"rendered":"