Build interpreter for non-existent language Build an interpreter for a fake, stack-based language that gets an input, interprets it, and outputs the result as an array of numbers. It should iterate through each byte and perform a different function based on this table:

0000 (0):
Concatenate (Combine top two numbers in a stack as if they were a string. ex: 12,5 -> 125)
0001 (1):
Increment (Add 1 to the number on the top of the stack)
0010 (2):
Decrement (Subtract one from the number at the top of the stack)
0011 (3):
Multiply (Multiply the top two numbers in the stack)
0100 (4):
Divide (Divide the 2nd-to-top number by the top number on the stack)
0101 (5):
Add (Add the top two numbers on the stack)
0110 (6):
Subtract (Subtract the top number on the stack from the one below it)
0111 (7):
Exponent (Calculate the second-to-top number to the power of the top number)
1000 (8):
Modulus: (Find the second-to-top number modulo the top one)
1001 (9):
Rotate Right (Shift the stack down one. The number on the bottom is now on the top)
1010 (A):
Rotate Left (Shift the stack up one. The number on the top is now on the bottom)
1011 (B):
Duplicate (Copy the top number so that it appears twice. ex: 4,1 becomes 4,1,1)
1100 (C):
Double Duplicate (Copy the top two numbers on the stack. ex: 4,1,2 becomes 4,1,2,1,2)
1101 (D):
Swap (Swap the top two numbers on the stack. ex: 4,1,2 becomes 4,2,1)
1110 (E):
Double Swap (Swap the top two numbers with two below them.ex: 1,2,3,4,5 becomes 1,4,5,2,3)
1111 (F):
Delete/Pop (Remove the number at the top of the stack)

For example, a file containing


1 1 B C 5 C 5 B 9 5    - Input (hex)
| | | | | | | | | |
1 2 2 2 4 4 6 6 2 8    - Stack
    2 2 2 2 4 6 6 6
      2 2 4 2 4 6 4
      2   2 2 2 4 2
          2   2 2


would output [8,6,4,2]

Rules:


Unicode/symbols are okay, but ASCII is best.
Be creative! Shortness counts, but creativity is great!
If bytes are too hard, use "$iv*/+-^%&gt;&lt;dtsz." or "0123456789ABCDEF" instead of actual bytes.
SPEED! The faster, the better.
The score is based on reputation, but size is a huge factor.


Bonus:

Try to complete this challenge using your newly made interpreter in as short of a string as possible.

Note:

The thing that makes this challenging as opposed to other code-golfing challenges is that there is no code to go by with this. If, lets say, you had to write a brainf*ck interpreter, you could look at other people's implementations. With this, you can't do that.



I forgot to put and ending date on this. I guess I'll make it one month from when I created this. Person with the highest votes at Feb. 22 wins!
Ruby, 67 lines of regex substitutions

I decided to write the interpreter in regex, while sticking to efficient algorithms.

I could have gone for plain bytes, but using symbols makes the code more readable in my opinion. Of course, if we could pack two instructions in one byte...

Concatenation of negative values results in ten's complement behavior, reflecting the internal representation.

Division is integer division and the remainder is never negative.



subs = [
  # stack expansion
  [/^ ?([$iv*\/+\-^%dtsz.])/,  ' 0 \1'  ],
  [/^ (\d+ [$*\/+\-^%tsz])/,   ' 0 \1'  ],
  [/^ ((\d+ ){2,3}z)/,         ' 0 \1'  ],
  [/ (0|9)\1+/,                ' \1'    ],
  # concatenation
  [/ (\d+) (?:0+|9+)(\d+) \$/, ' \1\2 ' ], 
  [/ (\d+) (0|9) \$/,          ' \1\2 ' ],
  # swaps
  [/ ((?:\d+ )*)(\d+) &lt;/,      ' \2 \1' ],
  [/ (\d+)((?: \d+)*) &gt;/,      '\2 \1 ' ],
  [/ (\d+) (\d+) s/,           ' \2 \1 '],
  [/ (\d+ \d+) (\d+ \d+) z/,   ' \2 \1 '],
  # dups
  [/ (\d+) d/,                 ' \1 \1 '],
  [/ (\d+ \d+) t/,             ' \1 \1 '],
  # pop
  [/ (\d+) \./,                ' '      ],

  # increment / decrement
  [/ (\d+) i/, ' \1I '], [/ (\d+) v/, ' \1V '],
  *(%w[0I 1I 2I 3I 4I 5I 6I 7I 8I 9I].zip [*?1..?9, 'I0']),
  *(%w[0V 1V 2V 3V 4V 5V 6V 7V 8V 9V].zip ['V9', *?0..?8]), 
  [' 1', ' 01'], [' 8', ' 98'], [' I', ' '], [' V', ' '],
  # addition, subtraction
  [/ (\d+) (\d+) \+/,                ' \1P \2P '       ], #init addition
  [/ (\d+) (\d+) \-/,                ' \1S \2S '       ], #init subtraction
  [/ ([PS](\d)\w*) (\d+[PS]\w*) /,   ' \2\1 \3 '       ], #sign extend left
  [/ (\d+[PS]\w*) ([PS](\d)\w*) /,   ' \1 \3\2 '       ], #sign extend right
  [/ (\d*)(\d)P(\S*) (\d*)0P(0*) /,  ' \1P\2\3 \4P0\5 '], #advance addition
  [/ (\d*)(\d)S(\S*) (\d*)0S(0*) /,  ' \1S\2\3 \4S0\5 '], #advance subtraction
  [/ (\d+)P(\S*) (\d*[1-5])P(0*) /,  ' \1IP\2 \3VP\4 ' ], #transfer left
  [/ (\d+)P(\S*) (\d*[6-9])P(0*) /,  ' \1VP\2 \3IP\4 ' ], #transfer right
  [/ (\d+)S(\S*) (\d*[1-5])S(0*) /,  ' \1VS\2 \3VS\4 ' ], #decrement both
  [/ (\d+)S(\S*) (\d*[6-9])S(0*) /,  ' \1IS\2 \3IS\4 ' ], #increment both
  [/ [PS](\S+) [PS]0+ /,             ' \1 '            ], #finish 

  # digitwise negation
  *(%w[9N 8N 7N 6N 5N 4N 3N 2N 1N 0N].zip [*'N0'..'N9']),
  #multiplication and division by 2
  *([*'H0'..'H9'].zip %w[0H 0F 1H 1F 2H 2F 3H 3F 4H 4F]),
  *([*'F0'..'F9'].zip %w[5H 5F 6H 6F 7H 7F 8H 8F 9H 9F]),  
  *(%w[0T 1T 2T 3T 4T 5T 6T 7T 8T 9T].zip %w[T0 T2 T4 T6 T8 TI0 TI2 TI4 TI6 TI8]), 
  ['H ', ' '], [' T', ' '],

  # sign correction for */%
  [/ (\d+) (9\d*) ([*\/%])/, ' \1NI \2NI \3'], [' N', ' '],
  # multiplication
  [/ (0+ \d+|\d+ 0+) \*/,     ' 0 '          ], #multiplication by zero
  [/ (\d+) (0\d*[02468]) \*/, ' \1T H\2 *'   ], #multiplication by an even number
  [/ (\d+) (0\d*[13579]) \*/, ' \1 \1 \2V *+'], #multiplication by an odd number
  # division / modulo
  [?/, 'r.'], [?%, 'rs.'],
  [/ (0|9)(\d*) (0\d+) r/,           ' \3 0 \1D\2 '          ], #init division
  [/ (\d+) (\d+) (0\d*)D(\d*) /,     ' \1 \2I \3SD\4 \1S '   ], #subtract divisor
  [/ (\d+) (\d+) (9\d*)D(\d)(\d*) /, ' \1 \2V0 \3P\4D\5 \1P '], #add divisor and advance
  [/ (\d+) (\d+) (9\d*)D /,          ' \2V \3P \1P '         ], #add divisor and finish  

  #exponentiation
  [/ \d+ 0+ \^/,             ' 01 '          ], # case: zeroth power
  [/ 9\d+ 9+ \^/,            ' 9 '           ], # case: reciprocal of negative
  [/ \d+ 9\d+ \^/,           ' 0 '           ], # case: high negative power
  [/ 0\d+ 9\d+ \^/,          ' 0 '           ], # case: reciprocal of positive
  [/ (\d+) 0+1 \^/,          ' \1 '          ], # case: power of one
  [/ (\d+) (\d*[02468]) \^/, ' \1 \1 *H\2 ^' ], # case: even exponent
  [/ (\d+) (\d*[13579]) \^/, ' \1 \2V ^\1 *' ], # case: odd exponent
]                                   

x = gets.tr '^$iv*/+\-^%&gt;&lt;dtsz.', ''
until x =~ /^ (\d+ )*$/
  subs.each do |sub|
    x.sub!(*sub) # &amp;&amp; (puts x; sleep 0.1)
  end
end


As for the bonus round, the shortest solution I've come up with (13 characters) is a clean solution:

iistisii$&lt;$&lt;$