Expanding on last weeks theme of minimalism, this week, we’ve got OISC: the One Instruction Set Computer. This is a machine-code level primitive language with exactly one instruction. There are actually a few variants on this, but my favorite is the “subleq” OISC, which I’ll describe beneath the fold.<\/p>\n
Expanding on last weeks theme of minimalism, this week, we’ve got OISC: the One Instruction Set Computer. This is a machine-code level primitive language with exactly one instruction. There are actually a few variants on this, but my favorite is the “subleq” OISC, which I’ll describe beneath the fold.<\/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-154","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-2u","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/154","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=154"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/154\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=154"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nOISC, aka the “One Instruction Set Computer” is based on the idea of the *Minsky Machine*. The Minsky machine is an extremely simply Turing complete machine proposed by Marvin Minsky. Back at the original GM\/BM, I wrote an [article on the Minsky machine][minsky] and a simple [Minsky interpreter][minsky-interp]. A Minsky machine is a register machine with two basic instructions: increment, and decrement-and-branch.
\nOISC does it one better. You don’t need the increment instruction. Given an unbounded set of registers, you can be Turing complete with only *one* instruction: subtract and branch if less than or equal to zero. (aka SUBLEQ<\/code>.) SUBLEQ takes 3 operands: two registers A and B, and a jump location, C. What SUBLEQ does is subtract the contents of B from the contents of A; and if the resulting value in A is less than or equal to zero, it jumps to C; otherwise, it proceeds to the next instruction. For simplicity of notation, if C is the next instruction, we’ll just leave it blank. So if instruction N is “SUBLEQ 2, 4, N+1”, we’ll just write it as “SUBLEQ 2, 4”
\nTo make things easy, we’ll use numbers for the registers, and assume that register 0 contains the value 0 at all times. We can initialize it that way pretty easily; just start off the program with:
\nSUBLEQ 0, 0
\nSo how do we do anything real with this bugger? Let’s build some instructions. We definitely want to be able to do addition, right? So let’s suppose we want to add registers X and Y.
\nAdd(X,Y) = SUBLEQ 0, Y ;; R0 now contains (-Y)
\nSUBLEQ X, 0 ;; X now contains X-(-Y) = X+Y
\nSUBLEQ 0, 0 ;; Restore R0=0
\nStoring a specific value in a register:
\nStore(X,V) = SUBLEQ X,X ;; clear X so that it contains 0
\nSUBLEQ 0, V ;; put -V in 0
\nSUBLEQ X, 0 ;; put -(-V) in X
\nSUBLEQ 0, 0 ;; restore 0
\nHow about a non-conditional jump to C? That’s an easy one.
\nJump(C) = SUBLEQ 0, 0, C
\nBranch to T if X=Y, or F otherwise, using
\nBranchIfEquals(X, Y, T, F) =
\nStore(1, X) ;; Store copies of X and Y that we can alter
\nStore(2, Y)
\nSUBLEQ 1, Y, L1 ;; subtract Y from X. If true, then x <= y.
\nJump(F) ;; X was not <= y, so branch to false
\nL1: SUBLEQ 2, X, T ;; subtract X from Y. If true, then Y <= X, and
\n;; we already know X <= Y, so X = Y
\nJump(F) ;; Y was not <= X, so X != Y.
\nSo now, we've got a useful conditional branch, addition, subtraction, unconditional branch, and copying values. That's pretty much the whole story – you don't need any more than that to be turing complete.
\nWant to see a real OISC program? There's an [OISC Interpreter written in OISC][interp], which is quite cute:
\n# Written by Clive Gifford, 29\/30 August 2006 based on the Wikipedia
\n# description of a OISC using the "subleq" instruction.
\n# 3 Sep 2006: did some "constant folding", removing a few instructions.
\n# 8 Sep 2006, a few more changes resulting in smaller memory footprint.
\nstart:
\n# [A1] = [PC]
\nsubleq A1 A1
\nsubleq PC ZERO
\nsubleq ZERO A1
\nsubleq ZERO ZERO
\n# Code below (after modification from above) is equivalent to [A] = [[PC]]
\nsubleq A A
\nA1: data 0
\ndata ZERO
\ndata A2
\nA2: subleq ZERO A
\nsubleq ZERO ZERO
\n# [A] = [A] + [LEN]
\nsubleq NEGL A
\n# [PC] = [PC] + 1
\nsubleq NEG1 PC
\n# [B1] = [PC]
\nsubleq B1 B1
\nsubleq PC ZERO
\nsubleq ZERO B1
\nsubleq ZERO ZERO
\n# Code below (after modification from above) is equivalent to [B] = [[PC] + 1]
\nsubleq B B
\nB1: data 0
\ndata ZERO
\ndata B2
\nB2: subleq ZERO B
\nsubleq ZERO ZERO
\n# [B] = [B] + [LEN]
\nsubleq NEGL B
\n# We have to copy [C] now, just in case the emulated subtraction modifies [[PC] + 2].
\n# [PC] = [PC] + 1
\nsubleq NEG1 PC
\n# [C1] = [PC]
\nsubleq C1 C1
\nsubleq PC ZERO
\nsubleq ZERO C1
\nsubleq ZERO ZERO
\n# Code below (after modification from above) is equivalent to [C] = [[PC] + 2]
\nsubleq C C
\nC1: data 0
\ndata ZERO
\ndata C2
\nC2: subleq ZERO C
\nsubleq ZERO ZERO
\n# [[B]] = [[B]] – [[A]];
\n# if [[B]] <= 0 goto LEQZ
\n# Earlier code referring to addresses A and B has modified the next
\n# couple of words to create the equivalent of "subleq [A] [B] LEQZ"
\n# This is where we're "emulating" the subtraction…
\nA: data 0
\nB: data 0
\ndata LEQZ
\n# [PC] += 1
\nsubleq NEG1 PC
\nsubleq ZERO ZERO START
\n# We come to address LEQZ when the emulated subleq is going to take
\n# the branch to the emulated address C.
\nLEQZ:
\n# First save the "raw" new PC
\n# [PC] = [C]
\nsubleq PC PC
\nsubleq C ZERO
\nsubleq ZERO PC
\nsubleq ZERO ZERO
\n# Check if [C] is less than zero. Halt if it is.
\n# We don't care about changing [C] as we've already copied the value to [PC] above.
\nsubleq NEG1 C -1
\n# [PC] = [PC] + [LEN]
\nsubleq NEGL PC
\n# Go back to the start of the loop ready for the next instruction
\nsubleq ZERO ZERO START
\nNEGL: data -119 # make this == -PROG (my assembler is too primitive!)
\nNEG1: data -1
\nZERO: data 0
\nC: data 0
\nPC: data PROG
\n# Code for the program to be interpreted must start at the PROG address…
\nPROG:
\n[interp]: http:\/\/eigenratios.blogspot.com\/2006\/09\/mark-ii-oisc-self-interpreter.html
\n[minsky]: http:\/\/goodmath.blogspot.com\/2006\/05\/minsky-machine.html
\n[minsky-interp]: http:\/\/goodmath.blogspot.com\/2006\/05\/minsky-machine-to-play-with.html<\/p>\n","protected":false},"excerpt":{"rendered":"