{"id":130,"date":"2006-08-25T12:23:34","date_gmt":"2006-08-25T12:23:34","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/08\/25\/ultimate-spaghetti-coding-with-linguine\/"},"modified":"2006-08-25T12:23:34","modified_gmt":"2006-08-25T12:23:34","slug":"ultimate-spaghetti-coding-with-linguine","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/08\/25\/ultimate-spaghetti-coding-with-linguine\/","title":{"rendered":"Ultimate Spaghetti Coding with Linguine"},"content":{"rendered":"

Todays dose of programming pathology is a monstrosity called *Linguine*. Linguine is a language that (obviously) carries spaghetti code to an extreme. You can see the [language specification][linguine-spec], or download an [implementation with examples][linguine-impl].
\nIt’s really a remarkably simple language. There are only 10 commands, including input and output:
\n1. “`x=y`”: assign the value of y to the variable x.
\n2. “`x+y`”: assign the value of x+y to the variable x.
\n3. “`x-y`”: assign the value of x-y to the variable x.
\n4. “`x|y`”: assign the value of x NAND y to the variable x.
\n5. “`x>y`”: assign the value of shifting x by y bits to x. If y is positive, then it shifts y bits right; if y is negative, then it shifts -y bits left.
\n6. “`x?`”: Input one character and store it in the variable x.
\n7. “`x$`”: Output the content of register x as a character.
\n8. “`x#`”: Output the content of register x as an integer.
\n9. “`x<y:loc`”: if x < y then jump to the program line labeled “loc”.
\n10. “`x~y:loc`”: if x = y then jump to the program line labeled “loc”.
\nCommand operands on either integer literals, or on the contents of an unlimited set of numbered registers each of which contains an integer. Valid operands are either an integer (which identifies a register number if it appears on the left, or a literal value on the right); or an operand preceeded by “*”, which performs an indirection on the value it precedes. So for example, “*3” is the contents of register three. “**3” is the contents of the register whose number is stored in register 3, etc. Any of the operands may be any of these forms, so for example, “1~*3:**4” is a valid command.
\nA linguine statement consists of three parts: a line label, a list of commands, and a branch target, written “label[commands]target”. When executed, the line evaluates each command in the list in sequence. If it reaches the end of the list without having branched, then it will branch to the statement labeled by the branch target.
\nThe lines of the program may appear in any order. The first statement executed will be the statement whose label is smallest. Branching to 0 ends program execution.
\nComments start with a “‘”, and extend to the end of the line.
\nAll quite simple, right?
\nAs usual, we’ll start with hello world.
\n1[0=72,0$,0+29,0$,0+7,0$,0$,0+3,0$,1=32,1$,0-24,0$,0+24,0$,0+3,0$,0-6,0$,0-8,0$,1+1,1$,1-23,1$]0
\nThat’s perfectly clear, isn’t it? Actually, it’s basically the same as the hello world program we saw in brainfuck.\tWe’ll piece it apart.
\n* 0=72,0$<\/code>: 72 is the ascii code for “H”. So store that in register 0. Then output register 0.
\n* 0+29,0$<\/code>: 101 is the ascii code for “e”. So add 29 to the contents of register 0, which will make the new value of register 0 be 101. Then output that.
\n* etc.
\nHow about something a tad more interesting? Let’s look at generating the
\nFibonacci sequence:
\n1[0=32,2=1,1#,0$,2#]2
\n2[1+*2,3=*1,1=*2,2=*3,0$,2#]2
\n* This starts with line 1:
\n* “0=32<\/code>: Store the ascii code for a whitespace in register 0.
\n* “`2=1`”: store the value 0 in register 2.
\n* “`1#`”: output the value of register 1. (Since registers contain 0 when the program starts, that prints a zero.)
\n* “`0$`”: output the contents of register 0 as a character, which prints a whitespace.
\n* “`2#`”: print the contents of register 2 (1).
\n* Finally, branch to statement 2.
\n* Statement 2: registers 1 and 2 contain the previous two fibonacci numbers. So this adds them together to get the next one, and then rotates the values of the registers so that the newest fibonacci number is in register 2, and the one before that is in register one.
\n* “`1+*2`”: add the value of register 2 to register 1.
\n* “`3=*1`”: store the value of register 1 in register 3.
\n* “`1=*2`”: store the value of register 2 in register 1.
\n* “`2=*3`”: store the value of register 3 in register 2.
\n* “`0$,2#`”: output a space, and then output the value of register 2.
\n* Finally, the branch instruction repeats statement 2, to keep generating fibonacci numbers.
\nHere’s a nice little multiply program, which demonstrates how to write subroutines. Note that recursion doesn’t work here, because we need to use fixed register numbers. (You can set up recursion using additional levels of indirection, it’s just messy as heck.)
\n‘Multiply: -2 *= *-3
\n‘Programmed by Jeffry Johnston, 2005
\n‘-1=return jump, -4=temp, -5=temp
\n100[-4=*-3,-5=*-2,-2=0,-4<0:101]102
\n101[-4~0:*-1,-2-*-5,-4+1]101 '-3 is negative
\n102[-4~0:*-1,-2+*-5,-4-1]102 '-3 is positive
\nThis takes the address of the instruction to return to in register -1; it takes the left operand of multiple (which is also the target of the result) in register -2, and the right operand in register -3. Registers -4 and -5 are used for temporary storage.
\n* Line 100: set up, and determine whether the right operand is positive or negative.
\n* "`-4=*-3,-5=*-2`": Copy the contents of register -3 to register -4, and the contents of register -2 to register -5.
\n* "`-2=0`": Store 0 in register -2.
\n* "`-4<0:101`": If the contents of register -4 is less than 0, then branch to statement 101.
\n* If you reach the end of this line, then the contents of register -4 is non-negative, and you branch to statement 102.
\n* Line 101: do multiplication by repeated subtraction
\n* "`-4~0:*-1`": If the contents of register -4 is zero, then we're done, so return by branching to the line labeled by the contents of register -1.
\n* "`-2-*-5`": Subtract the contents of register -5 from the contents of register -2 (the result register).
\n* "`-4-1`": decrement (or increment, depending on your point of view) the contents of register four, to show that you've done one subtraction.
\n* Repeat the line.
\n* Line 102: basically exactly the same as 101, except that the does a repeated add rather than a subtract.
\nAn example of calling this would be:
\n1[-1=2,-2=36,-3=13]200
\n2[-2#]0
\nThis stores 36 and 13 as the parameters to the multiple subroutine, and then invokes it by branching to it at line 200. The "return address" is set to statement 2 by storing 2 in register -1. When control returns to statement 2, the result of the multiplication is printed out.
\nOne last example, which you can puzzle out on your own. A brainfuck interpreter in 21 lines of Linguine:
\n'BF interpreter in Linguine
\n'Programmed by Jeffry Johnston, 2005
\n1[*-2?,*-2~33:2,-2+1]1
\n2[*-2=-1,-2+1]3
\n3[-3=**-1,-3~-1:0,-3~43:4,-3~44:6,-3~45:7,-3~46:9,-3~60:10,-3~62:11,-3~91:12,-3~93:14]15
\n4[*-2+1,*-2~256:5]15 '+
\n5[*-2=0]15
\n6[*-2?,*-2~-1:5]15 ',
\n7[*-2-1,*-2~-1:8]15 '-
\n8[*-2=255]15
\n9[*-2$]15 '.
\n10[-2-1]15 '
\n12[*-2~0:13]15 ‘[
\n13[-3=1]16
\n14[-3=-1]16 ‘]
\n15[-1+1]3
\n16[-4=1]17
\n17[-1+*-3,*-1~91:18,*-1~93:19]20
\n18[-4+*-3]20
\n19[-4-*-3]20
\n20[-4~0:21]17
\n21[-3~1:15]3
\n[linguine-spec]: http:\/\/kidsquid.com\/files\/linguine\/README
\n[linguine-impl]: http:\/\/kidsquid.com\/files\/linguine\/linguine.tar.gz<\/p>\n","protected":false},"excerpt":{"rendered":"

Todays dose of programming pathology is a monstrosity called *Linguine*. Linguine is a language that (obviously) carries spaghetti code to an extreme. You can see the [language specification][linguine-spec], or download an [implementation with examples][linguine-impl]. It’s really a remarkably simple language. There are only 10 commands, including input and output: 1. “`x=y`”: assign the value of […]<\/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-130","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-26","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/130","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=130"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/130\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=130"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}