From: Ruby Quiz <james@...>
Date: 2006-11-04T00:32:46+09:00
Subject: [QUIZ] Bytecode Compiler (#100)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ross Bamford

Note: This quiz isn't really as much work as it might seem!

This quiz involves writing (in Ruby, of course) a compiler for basic arithmetic
expressions. The output from this compiler should be an array of unsigned
byte-sized ints, which can be fed into the included interpreter
(http://www.rubyquiz.com/interp.rb) in order to execute the compiled expression.

The bytecode format is very simple, while the interpreter is also very simple,
implemented as a stack machine. They have the following general characteristics:

	* Bytecode is stored as an array of unsigned byte-sized Fixnums.
	* All stack-bound numbers are signed integers
	* The following operations are supported:
	  * Addition
	  * Subtraction
	  * Multiplication
	  * Division
	  * Raise to power
	  * Integer modulo
	* Where an operator would return a floating point value,
	  the value is truncated to an integer.
	* Short CONST and long LCONST instructions allow constants
	  to be pushed to the stack. These instructions expect their
	  operands to hold a signed short or long, respectively,
	  in network byte order.

Your compiler interface should be via a singleton method on a module 'Compiler',
taking a string, such that:

	Compiler.compile('3+2')

Returns an array of instructions (and operands) that, when fed to the
interpreter, will execute the expression 3+2 and return the result (hopefully
5). For example, a correct (but non-optimal) result from the above call would
be:

	[2,0,0,0,3,   # LCONST 3
	 2,0,0,0,2,   # LCONST 2
	 10]          # ADD

Your compiler should support all basic arithmetic operations and explicit
precedence (parenthesis). As standard, syntax/precedence/ associativity/etc.
should follow Ruby itself. Obviously, specific implementation is entirely up to
you, though bear in mind that your compiler must be capable of running inline in
the same Ruby process as the interpreter, without affecting any code outside
itself.

The quiz also includes a number of tests
(http://www.rubyquiz.com/test_bytecode.rb) that will test your compiler's
functionality, with expressions becoming more complex as the tests go on. To
pass all the tests, a compiler will have to not only generate correct bytecode,
but it will also need to generate the shortest code it can for a given
expression.

Here is the bytecode spec:

	# 0x01: CONST (cbyte1, cbyte2) ... => ..., const
	  Push a 15-bit signed integer to the stack.
	  The two bytes immediately following the instruction represent the
	  constant.
	
	# 0x02: LCONST (cbyte1, cbyte2, cbyte3, cbyte4) ... => ..., const
	  Push a 31-bit signed integer to the stack.
	  The four bytes immediately following the instruction represent the
	  constant.
	
	# 0x0a: ADD () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, add them, and push the result
	  back onto the stack.
	
	# 0x0b: SUB () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, subtract value2 from value1,
	  and push the result back onto the stack.
	
	# 0x0c: MUL () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, multiply value1 by value2,
	  and push the result back onto the stack.
	
	# 0x0d: POW () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, raise value1 to the power of
	  value2, and push the result back onto the stack.
	
	# 0x0e: DIV () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, divide value1 by value2,
	  and push the result back onto the stack.
	
	# 0x0f: MOD () ..., value1, value2 => ..., result
	  Pop the top two values from the stack, modulo value1 by value2,
	  and push the result back onto the stack.
	
	# 0xa0: SWAP () ..., value1, value2 => ..., value2, value1
	  Swap the top two stack values.