{"id":408,"date":"2007-05-04T08:30:00","date_gmt":"2007-05-04T08:30:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/05\/04\/even-more-stack-pathology\/"},"modified":"2007-05-04T08:30:00","modified_gmt":"2007-05-04T08:30:00","slug":"even-more-stack-pathology","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/05\/04\/even-more-stack-pathology\/","title":{"rendered":"Even More Stack Pathology"},"content":{"rendered":"

I thought that it would be fun to stick with the “stack-based” theme of last week’s pathological post, but this time, to pick an utterly pointlessly twisted stack based language, but one that would be appreciated by the mascot of one of my fellow ScienceBlogs<\/a>. Orac, this one’s for you! \ud83d\ude42 Our target these week is the language “Enema”. <\/p>\n

<\/p>\n

Enema is a remarkably simple stack based language. In fact, it mostly looks like a
\nthoroughly trivial language – something like False, only simpler. It has a small family
\nof simple commands:<\/p>\n

\n
0-9<\/dt>\n
Push the value of the digit onto the stack.<\/dd>\n
+<\/dt>\n
Pop the top two values on the stack, add them, and push the result.<\/dd>\n
–<\/dt>\n
Pop the top two values on the stack, subtract the first from the second, and push the result.<\/dd>\n
*<\/dt>\n
Pop the top two values on the stack, multiply them, and push the result.<\/dd>\n
\/<\/dt>\n
Pop the top two values on the stack, integer-divide the first by the second, and push the result.<\/dd>\n
%<\/dt>\n
Pop the top two values on the stack, integer-divide the first by the second, and
\nand push the remainder onto the stack.<\/dd>\n
&<\/dt>\n
Pop the top two values on the stack, perform logical-and on them, and push the result.<\/dd>\n
|<\/dt>\n
Pop the top two values on the stack, perform logical or on them, and push the result.<\/dd>\n
^<\/dt>\n
Pop the top two values on the stack, perform logical exclusive-or on them, and push the result.<\/dd>\n
I<\/dt>\n
Input a single character, and push it onto the stack.<\/dd>\n
O<\/dt>\n
Output the value on top of the stack as a character.<\/dd>\n
X<\/dt>\n
Discard the value on top of the stack.<\/dd>\n
D<\/dt>\n
Duplicated the value on top of the stack.<\/dd>\n
S<\/dt>\n
Swap the top two values on the stack.<\/dd>\n
R<\/dt>\n
Rotate the stack: take the top three values on the stack S1,S2,S3, and push them back as S3,S1,S2.<\/dd>\n
G<\/dt>\n
Pop the top-most stack value as a memory address and push the value stored at
\nthat address.<\/dd>\n
P<\/dt>\n
Pop the top value on the stack as a memory address, and the second value on the stack
\nas a number, and store them number in memory at the address<\/dd>\n
[<\/dt>\n
Mark the beginning of a loop.<\/dd>\n
]<\/dt>\n
Mark the end of a loop. When code reaches the “]” and the end of a loop, it jumps back
\nto the corresponding “[“.<\/dd>\n
B<\/dt>\n
Exit (break out of) the current loop, starting execution at the instruction after the next “]”.<\/dd>\n
Z<\/dt>\n
Conditional execution: skip the next instruction if the value on top of the stack is greater than 0.<\/dd>\n
“chars”<\/dt>\n
Push the ascii codes of the characters between the quotes onto the stack.<\/dd>\n
?<\/dt>\n
Push the current depth of the stack onto the top of the stack.<\/dd>\n
#<\/dt>\n
Push the maximum address of memory that has been used by the program onto the stack. (This is effectively the amount of memory that has been allocated by the program.)<\/dd>\n
: char<\/em> code<\/em> :<\/dt>\n
Define char<\/em> as a new function, whose body is the code up to the next “:”.<\/dd>\n
! char<\/em><\/dt>\n
Discard the function definition associated with the character.<\/dd>\n
Q<\/dt>\n
Return from function call.<\/dd>\n
.<\/dt>\n
End of program: halt.<\/dd>\n<\/dl>\n

So, for example, here’s a basic “Hello world” program:<\/p>\n

\n052*\"!dlroW ,olleH\"[DZBO].\n<\/pre>\n
 It pushes 0, 5, and 2 onto the stack; then multiplies 5 times 2, leaving 10 on top, and 0 beneath it. Then it pushes the characters of “Hello world” onto the stack – so the stack is “0\/10\/”!”\/”d”\/”l”\/”r”\/”o”\/”W”\/” “\/”,”\/”o”\/”l”\/”l”\/”e”\/”H”. Then it runs a loop containing the commands “DZBO”. “D” duplicates the top value on the stack; then “Z” skips the next instruction if the stack-top is not zero. So if the character on top of the stack was not zero, then it skips to “O”, and outputs the stack top, and then goes back to the next iteration.  If the stack top was<\/em> 0, then it executes “B”, which breaks out of the loop, and halts. So it will output each of the characters in “Hello, World!”, followed by character 10 (which is newline); and then it will halt. Very straightforward, if awkward.<\/p>\n
 Ok… So far, we’ve got a pretty typical (if ugly-ish) stack-based language. But there’s nothing particularly pathological about it. It’s just another stack language. So why does this justify a name like “Enema”? Why is it worth a coveted FPP slot? Here’s
\na simple example to illustrate why:<\/p>\n
\n23*\n68*+\nO\n<\/pre>\n
 This is a very simple program. It multiplies 2*3, and then adds 48 to it (converting the numeric value to a digit character value), and outputs it. So it outputs “6”.<\/p>\n
\n:23:\n23*\n68*+\nO\n<\/pre>\n
 This is the same program, except that we’ve added a function definition to the beginning. The program now<\/em> outputs “9” – because we’ve redefined “2” to push the value “3” onto the stack.<\/p>\n
 “:” can redefine<\/em> any<\/em> command in  the program. “:23:” will redefine 2<\/em> so that instead of pushing the value 2 onto the stack, it pushes the value 3!  “::stuffQ” will redefine<\/em> the “:” command so that instead of starting a definition, it will now be a command that does “stuff”. <\/p>\n
 That gives you some idea of how twisted this can get. Alas, it’s really hard<\/em> to write programs when your primitives can be arbitrarily redefined out from under you! So the author just totally wimped out, and never uses this in any of their examples.<\/p>\n
 But for you, my readers, I’m willing to endure all sorts of terrible punishment. So here is my rendition of a new and extra-twisted version of an enema program to
\ncompute the integer exponent of a number.<\/p>\n
\n:qX:\n:39Q:\n:41Q:\n{ output null-terminated string to stdout }\n:o[DZBO]qQ:\n{ count n-th power of v (v n -> p) }\n:p4[SDZBRDR*SR1-S]qSqQ:\n{ convert integer to null-terminated string (n -> 0 c1 c2 c3 ...) }\n:i0S[D34+%\"0\"+S34+\/DZB]qQ:\n{ read integer terminated with character < '0' }\n:r0[I"0"-D1+ZBS34+*+]qQ:\n{ prompt user to enter data }\n:a0" :eulav"352*" atad retnE"or0" :rewop"3orQ:\n{ main program }\n?Zapio52*O.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
I thought that it would be fun to stick with the “stack-based” theme of last week’s pathological post, but this time, to pick an utterly pointlessly twisted stack based language, but one that would be appreciated by the mascot of one of my fellow ScienceBlogs. Orac, this one’s for you! \ud83d\ude42 Our target these week […]<\/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-408","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-6A","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/408","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=408"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/408\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=408"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}