[QUIZ] Bytecode Compiler (#100)

Discussion in 'Ruby' started by Ruby Quiz, Nov 3, 2006.

  1. Ruby Quiz

    Ruby Quiz Guest

    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.
     
    Ruby Quiz, Nov 3, 2006
    #1
    1. Advertising

  2. On 11/3/06, Ruby Quiz <> wrote:
    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    >
    > 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.
    >



    Well... this took me longer than it probably should have.
    I didn't find out about this:
    http://en.wikipedia.org/wiki/Shunting_yard_algorithm
    ..until I was pretty much done anyway.

    Also, helpful tip I'd like to send back to my past self.. Regular
    expressions aren't powerful enough to find matched parentheses.

    Anyway, thanks for the quiz. Fun stuff.

    class Compiler
    def self.compile(input)
    @bytecodes = {'+' => 0x0a, '-' => 0x0b, '*' => 0x0c, '**' => 0x0d,
    '/' => 0x0e, '%' => 0x0f}
    encode postfix(input)
    end

    def self.encode(tokens)
    tokens.collect do |token|
    number = token =~ /\-?\d+/ ? token.to_i : nil
    if (-32768..32767).include?(number)
    [0x01] + [number].pack('n').split(//).collect {|byte| byte[0]}
    elsif !number.nil? # long
    [0x02] + [number].pack('N').split(//).collect {|byte| byte[0]}
    else
    @bytecodes[token]
    end
    end.flatten
    end

    def self.postfix(infix)
    stack, stream, last, op = [], [], nil, nil
    tokens = infix.scan(/\d+|\*\*|[-+*\/()%]/)
    tokens.each_with_index do |token,i|
    case token
    when /\d+/; stream << token
    when *@bytecodes.keys
    if token == '-' and last.nil? || (last =~ /\D/ && tokens[i+1] =~ /\d/)
    tokens[i+1] = "-#{tokens[i+1]}"
    else
    stream << stack.pop while stack.any? && preceded?(stack.last, token)
    stack << token
    end
    when '('; stack << token
    when ')'; stream << op while (op = stack.pop) && (op != '(')
    end
    last = token
    end
    stream << op while op = stack.pop
    stream
    end

    def self.preceded?(last, current)
    ops = {'+' => 1, '-' => 1, '%' => 2, '/' => 2, '*' => 2, '**' =>
    3, '(' => 0, ')' => 0}
    ops[last] >= ops[current] rescue true
    end
    end
     
    Wilson Bilkovich, Nov 5, 2006
    #2
    1. Advertising

  3. Ruby Quiz

    Bill Dolinar Guest

    require 'interp'

    module Compiler

    # use eval and Value class below to compile
    # expression into bytecode
    def Compiler.compile(s)
    s.gsub!(/([0-9]+)/, 'Value.new(stack, \1)')
    stack = []
    eval(s)
    stack
    end

    class Value
    attr_reader :number # constant value or nil for on stack
    ON_STACK = nil

    def initialize(stack, number)
    @number = number
    @stack = stack
    end

    # generate code for each binary operator (except -@)
    # algorithm:
    # push constants (or don't if already on stack)
    # swap if necessary
    # push bytecode
    # create stack item
    {'+' => Interpreter::Ops::ADD,
    '-' => Interpreter::Ops::SUB,
    '*' => Interpreter::Ops::MUL,
    '**'=> Interpreter::Ops::pOW,
    '/' => Interpreter::Ops::DIV,
    '%' => Interpreter::Ops::MOD}.each do |operator, byte_code|
    Value.module_eval <<-FUNC
    def #{operator}(rhs)
    push_const(@number)
    push_const(rhs.number)
    # may need to swap integers on stack for all but plus
    #{
    if operator != "+"
    "@stack << Interpreter::Ops::SWAP if rhs.number == nil &&
    @number != nil"
    end
    }
    @stack << #{byte_code}
    Value.new(@stack, ON_STACK)
    end
    FUNC
    end

    def -@
    if @number != ON_STACK
    @number = -@number
    push_const(@number)
    else
    push_const(@number)
    push_const(0)
    @stack << Interpreter::Ops::SWAP
    @stack << Interpreter::Ops::SUB
    end
    Value.new(@stack, ON_STACK)
    end

    def push_const(number)
    if number != ON_STACK
    if (-32768..32767).include?(number)
    @stack << Interpreter::Ops::CONST
    else
    @stack << Interpreter::Ops::LCONST
    @stack << ((number >> 24) & 0xff)
    @stack << ((number >> 16) & 0xff)
    end
    @stack << ((number >> 8) & 0xff)
    @stack << (number & 0xff)
    end
    end
    end
    end
     
    Bill Dolinar, Nov 5, 2006
    #3
  4. Ruby Quiz

    Cameron Pope Guest

    Re: Bytecode Compiler (#100)

    The simplest way I found to do this problem was to let Ruby do the
    legwork of parsing the expression for me, so I didn't have to worry
    about things like parens or operator precedence.

    I defined a Const and an Expr class and defined operators inside of
    them to create a parse tree, added a to_const method to Fixum and
    created a regular expression to convert an expression 1+1 to
    '1.to_const() + 1.to_const()', so evaluating that expression would
    produce a parse tree for that experssion.

    Emitting the bytescodes is then a post-order traversal of the parse
    tree.

    ---- Compiler.rb

    # Operator overrides to create an expression tree. Mixed into
    # Const and Expr so:
    # Const <op> Const => Expr
    # Const <op> Expr => Expr
    # Expr <op> Const => Expr
    module CreateExpressions
    def +(other) Expr.new:)add, self, other) end
    def -(other) Expr.new:)sub, self, other) end
    def *(other) Expr.new:)mul, self, other) end
    def /(other) Expr.new:)div, self, other) end
    def %(other) Expr.new:)mod, self, other) end
    def **(other) Expr.new:)pow, self, other) end
    end

    # Add a method to fixnum to create a const from an integer
    class Fixnum
    def to_const
    Const.new(self)
    end
    end

    # An integer value
    class Const
    include CreateExpressions
    # Opcodes to push shorts or longs respectively onto the stack
    OPCODES = {2 => 0x01, 4 => 0x02}

    def initialize(i)
    @value = i
    end

    def to_s
    @value
    end

    # Emits the bytecodes to push a constant on the stack
    def emit
    # Get the bytes in network byte order
    case @value
    when (-32768..32767): bytes = [@value].pack("n").unpack("C*")
    else bytes = [@value].pack("N").unpack("C*")
    end
    bytes.insert 0, OPCODES[bytes.size]
    end
    end

    # A binary expression
    class Expr
    include CreateExpressions
    OPCODES = {:add => 0x0a, :sub => 0x0b, :mul => 0x0c, :pow => 0x0d,
    :div => 0x0e, :mod => 0x0f}

    def initialize(op, a, b)
    @op = op
    @first = a
    @second = b
    end

    # Emits a human-readable s-expression for testing
    # (preorder traversal of parse tree)
    def to_s
    "(#{@op.to_s} #{@first.to_s} #{@second.to_s})"
    end

    # Bytecode emitter for an expression (postorder traversal of parse
    tree)
    def emit
    # emit LHS, RHS, opcode
    @first.emit << @second.emit << OPCODES[@op]
    end
    end

    # Compile and print out parse tree for expressions
    class Compiler
    # Creates bytecodes from an arithmatic expression
    def self.compile(expr)
    self.mangle(expr).emit.flatten
    end

    # Prints a representation of the parse tree as an S-Expression
    def self.explain(expr)
    self.mangle(expr).to_s
    end

    private
    # Name-mangles an expression so we create a parse tree when calling
    # Kernel#eval instead of evaluating the expression:
    # [number] => [number].to_const()
    def self.mangle(expr)
    eval(expr.gsub(/\d+/) {|s| "#{s}.to_const()"})
    end
    end
     
    Cameron Pope, Nov 5, 2006
    #4
  5. Ruby Quiz

    Dennis Ranke Guest

    Here is my solution, a simple recursive descent parser. It's a bit more
    code than is strictly necessary because it is loosely modeled after a
    parser for a real language I have written recently.

    require 'English'

    class Compiler
    def self.compile(expr)
    return self.new(expr).compile.unpack('C*')
    end

    def initialize(expr)
    # a very simple tokenizer
    @tok = []
    until expr.empty?
    case expr
    when /\A\s+/ # skip whitespace
    # don't tokenize '1-1' as '1', '-1'
    when (@tok.last.is_a? Integer) ? /\A\d+/ : /\A\-?\d+/
    @tok << $MATCH.to_i
    # any other character and '**' are literal tokens
    when /\A\*\*|./
    @tok << $MATCH
    end
    expr = $POSTMATCH
    end
    end

    def compile
    code = compile_expr(0)
    raise "syntax error" unless @tok.empty?
    return code
    end

    private

    OPS = {'+'=>0xa, '-'=>0xb, '*'=>0xc, '**'=>0xd, '/'=>0xe, '%'=>0xf}

    def compile_expr(level)
    # get the tokens to parse at this precedence level
    tok = [['+', '-'], ['*', '/', '%'], ['**']][level]
    if tok
    # if we are to actually parse a bi-op, do so
    left = compile_expr(level + 1)
    # for left-associative ops, find as many ops in a row as possible
    while tok.include?(@tok.first)
    op = OPS[@tok.shift]
    # '**' is right-associative, so add a special case for that
    right = compile_expr(op == OPS['**'] ? level : level + 1)
    left << right + op.chr
    end
    return left
    end
    # if we are at a level higher than the ops, try to parse an
    # atomic - either a numeral or an expression in paranthesis
    tok = @tok.shift
    if tok == '('
    expr = compile_expr(0)
    raise "')' expected" unless @tok.shift == ')'
    return expr
    end
    raise 'number expected' unless tok.is_a? Integer
    return (tok < -32768 || tok > 32767) ? [2, tok].pack('CN') :
    [1, tok].pack('Cn')
    end
    end

    if $0 == __FILE__
    p Compiler.compile(ARGV[0])
    end
     
    Dennis Ranke, Nov 5, 2006
    #5
  6. On Nov 5, 2006, at 9:43 AM, Wilson Bilkovich wrote:

    > Also, helpful tip I'd like to send back to my past self.. Regular
    > expressions aren't powerful enough to find matched parentheses.


    Perl's regex engine can do this, as can Ruby 1.9's Oniguruma engine.
    Both allow recursive definitions, which is what it takes.

    James Edward Gray II
     
    James Edward Gray II, Nov 5, 2006
    #6
  7. On Nov 5, 2006, at 11:18 AM, Dennis Ranke wrote:

    > Here is my solution, a simple recursive descent parser. It's a bit
    > more code than is strictly necessary because it is loosely modeled
    > after a parser for a real language I have written recently.


    Did you write that language in Ruby? I'm just curious.

    James Edward Gray II
     
    James Edward Gray II, Nov 5, 2006
    #7
  8. Ruby Quiz

    Dennis Ranke Guest

    James Edward Gray II wrote:
    > On Nov 5, 2006, at 11:18 AM, Dennis Ranke wrote:
    >
    >> Here is my solution, a simple recursive descent parser. It's a bit
    >> more code than is strictly necessary because it is loosely modeled
    >> after a parser for a real language I have written recently.

    >
    > Did you write that language in Ruby? I'm just curious.


    I wrote the (fairly simple) compiler in Ruby and the bytecode
    interpreter in C++. The whole thing is used as a scripting language for
    a Nintendo DS game.
     
    Dennis Ranke, Nov 5, 2006
    #8
  9. On 11/5/06, Daniel Martin <> wrote:
    > Note that the creator of this quiz left out one important case from
    > their tests:
    >
    > def test_02a
    > assert_equal [2**1**2], Interpreter.new(Compiler.compile('2**1**2')).run
    > end
    >
    > This tests that your compiler is properly making **
    > right-associative. Some solutions already posted fail this test.
    >
    > 2**2**2 was an unfortunate test case to choose, since 2**4 == 4**2.


    Good catch. Here's an updated copy of mine that:
    A) Steals your cool C* unpack trick. :)
    B) Gets rid of a temporary variable and a couple of 'pop' loops in
    exchange for some more golf.
    C) Avoids re-initializing the hashes for improved performance.
    D) Passes your new test_02a

    class Compiler
    def self.compile(input)
    @bytecodes ||= {'+' => 0x0a, '-' => 0x0b, '*' => 0x0c, '**' =>
    0x0d, '/' => 0x0e, '%' => 0x0f}
    encode postfix(input)
    end

    def self.encode(tokens)
    tokens.collect do |token|
    number = token =~ /\-?\d+/ ? token.to_i : nil
    if (-32768..32767).include?(number)
    [0x01] + [number].pack('n').unpack('C*')
    elsif !number.nil? # long
    [0x02] + [number].pack('N').unpack('C*')
    else
    @bytecodes[token]
    end
    end.flatten
    end

    def self.postfix(infix)
    stack, stream, last = [], [], nil
    tokens = infix.scan(/\d+|\*\*|[-+*\/()%]/)
    tokens.each_with_index do |token,i|
    case token
    when /\d+/; stream << token
    when *@bytecodes.keys
    if token == '-' and last.nil? || (last =~ /\D/ && tokens[i+1] =~ /\d/)
    tokens[i+1] = "-#{tokens[i+1]}"
    else
    stream << stack.pop while stack.any? && preceded?(stack.last, token)
    stack << token
    end
    when '('; stack << token
    when ')'; (stream += stack.slice!(stack.rindex('('),
    stack.size).reverse).pop
    end
    last = token
    end
    stream += stack.reverse
    end

    def self.preceded?(last, current)
    @ops ||= {'+' => 1, '-' => 1, '%' => 2, '/' => 2, '*' => 2, '**'
    => 3, '(' => 0, ')' => 0}
    @ops[last] >= @ops[current] && current != '**' # right associative mayhem!
    end
    end
     
    Wilson Bilkovich, Nov 6, 2006
    #9
  10. Ruby Quiz

    Mike Harris Guest

    My solution is a bit different than all the ones I've seen so far. I
    had no intention of writing an expression parser :) All it does is

    1. Define a method (to_bc) to have a fixnum return its own bytecode
    2. Redefine the array operators to return the appropriate bytecode
    representations
    3. Add .to_bc after every number in the expression string

    Here it is:

    class Compiler
    def self.compile(str)

    eval(str.gsub(/(\d+)([^\d])/,'\1.to_bc\2').gsub(/([^\d])(\d+)$/,'\1\2.to_bc'))
    end
    end

    class Fixnum
    def to_bc
    return (self >= 0 ? [1,self/256,self%256] :
    [1,(self+32768)/256+128,(self+32768)%256]) if self <= 32767 and self >=
    -32768
    res = [(24..30),(16..23),(8..15),(0..7)].map { |range| range.map {
    |x| self[x] } }.map { |byte| byte.inject_with_index(0) { |s,x,i|
    s+x*2**i } }
    ([2] << (self > 0 ? res[0] : res[0]+128) << res[1..3]).flatten
    end
    end

    class Array
    {:+ => 10, :- => 11, :* => 12, :** => 13, :/ => 14, :% => 15}.each do
    |op,opcode|
    define_method(op) { |x| self.concat(x).concat([opcode]) }
    end
    def inject_with_index(sum)
    each_with_index { |x,i| sum = yield(sum,x,i) }
    sum
    end
    end
     
    Mike Harris, Nov 6, 2006
    #10
  11. Ruby Quiz

    Marcel Ward Guest

    On 03/11/06, Ruby Quiz <> wrote:
    > Note: This quiz isn't really as much work as it might seem!


    Ouch! :) Oh well, I don't think my Ruby is up to some of the more
    cunning techniques I see many have employed.

    > Your compiler should support all basic arithmetic operations and explicit
    > precedence (parenthesis). As standard, syntax/precedence/ associativity/etc.
    > should follow Ruby itself.


    By associativity does this also mean that "+--+1" - which could be
    rewritten as "0+(0-(0-(0+1)))" - should be parsed into a bytecode
    which, however well optimised, on execution results in the answer "1"?

    I should warn that my solution below is rather long. I went down a
    possibly more traditional route of writing a generic tokenizer/lexer.
    I don't know if these are still commonly used but I couldn't find an
    existing implementation in the Ruby Standard Library.

    I also tried to document the functions using rdoc so someone else
    might make use of it. For those who haven't tried it yet, just type
    'rdoc' at the command prompt and it makes a nice doc directory under
    the current directory with an index.html to start browsing the
    file/classes/methods. Nice!

    Back to the task...

    My wanting a solution that coped with all difficult expressions that
    Ruby itself can deal with (using the lexicon allowed) meant having to
    get things like the aforementioned negation with parentheses working:

    -(---3) # => 3

    ...and power precedence (as others have pointed out) combined with
    negation and parentheses turned out to be tricky:

    64**-(-(-3+5)**3**2) #=> a big number

    There's a big list of test cases such as these in my unit tests (included).

    So having written the lexer class, I now set up the state transition
    table and ask the lexer to tokenize the expression. The tokens are
    then parsed and the bytecode is generated using a simple mapping.

    The code follows; there are two files in total.

    Thanks for another fun challenge and congrats all round for reaching
    the 100th Ruby Quiz!

    Marcel

    #!/usr/bin/env ruby
    ##################################################################
    # = compiler_mw.rb - bytecode compiler
    #
    # Author:: Marcel Ward <wardies ^a-t^ gmaildotcom>
    # Documentation:: Marcel Ward
    # Last Modified:: Monday, 06 November 2006

    require 'interp'
    require 'lexer_mw'

    module Compiler
    # The lexer needs to know the character sets involved in deciding
    # which state transition will be fired...
    CHAR_SETS = {
    :plus => [?+], :minus => [?-],
    :digit => /\d/,
    :div_mod => [?/, ?%], # matches '/' or '%'
    :asterisk => [?*],
    :eek:pen_paren => [?(], :close_paren => [?)]
    }

    # Tell the lexer how to parse a datastream: which tokens to
    # generate, what state to switch to, etc.
    # This table was designed according to my vague recollection of
    # the dragon book on compiler construction by Aho/Sethi/Ullman.
    STATE_TRANS_TABLE = {
    :s_start => {
    :plus => {:next_s_skip => :s_start},
    :minus => {:next_s => :s_negate},
    :digit => {:next_s => :s_numeric},
    :eek:pen_paren => {:next_s => :s_start,
    :token => :tok_open_paren}
    },
    :s_negate => {
    :plus => {:next_s_skip => :s_negate},
    :minus => {:next_s => :s_start},
    :digit => {:next_s => :s_numeric},
    :eek:pen_paren => {:next_s_backtrack => :s_start,
    :token => :tok_negate}
    },
    :s_numeric => {
    :plus => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    :minus => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    :digit => {:next_s => :s_numeric},
    :div_mod => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    :asterisk => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    :close_paren => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    :eof => {:next_s_backtrack => :s_operator,
    :token => :tok_int},
    },
    :s_operator => {
    :plus => {:next_s => :s_start,
    :token => :tok_add},
    :minus => {:next_s => :s_start,
    :token => :tok_subtract},
    :div_mod => {:next_s => :s_start,
    :token => :tok_div_mod},
    :asterisk => {:next_s => :s_mult_or_power},
    :close_paren => {:next_s => :s_operator,
    :token => :tok_close_paren},
    :eof => {} # when :next_s... is absent, finish
    },
    :s_mult_or_power => {
    :plus => {:next_s_backtrack => :s_start,
    :token => :tok_multiply},
    :minus => {:next_s_backtrack => :s_start,
    :token => :tok_multiply},
    :digit => {:next_s_backtrack => :s_start,
    :token => :tok_multiply},
    :asterisk => {:next_s => :s_start,
    :token => :tok_power},
    :eek:pen_paren => {:next_s_backtrack => :s_start,
    :token => :tok_multiply}
    }
    }

    # Compiles a string expression _sum_ into bytecode and returns
    # the bytecode array (as per Ruby Quiz 100 requirements).
    def self.compile(sum)
    lexer = LexerMW.new()
    lexer.init_char_sets(CHAR_SETS)
    lexer.init_state_transitions(STATE_TRANS_TABLE)

    toks = lexer.tokenize(sum)

    puts toks.inspect + "\n\n" + toks.map {|a,b| b}.join(' ') \
    if $DEBUG == 1

    # Get the mnemonic stack by parsing the tokens.
    mnemonic_stack = parse(toks)
    puts "\nParsed toks => #{mnemonic_stack.inspect}" if $DEBUG == 1

    # Last stage now, we convert our internal mnemonics directly
    # to a byte stack in the required bytecode format.
    mnemonics_to_bytecode(mnemonic_stack)
    end

    MNEMONIC_TO_BYTECODE = {
    :tok_add => Interpreter::Ops::ADD,
    :tok_subtract => Interpreter::Ops::SUB,
    :tok_multiply => Interpreter::Ops::MUL,
    :tok_divide => Interpreter::Ops::DIV,
    :tok_modulo => Interpreter::Ops::MOD,
    :tok_power => Interpreter::Ops::pOW
    }


    # This exception is raised by the mnemonic-to-bytecode method when
    # an integer constant cannot be pushed onto the interpreter
    # bytecode stack because it is too big to fit the
    # Interpreter::Ops::LCONST instruction.
    class OutOfRangeError < StandardError
    end

    # Convert our internal _mnemonics_ directly to a byte array and
    # return this in the required bytecode format, ready to execute.
    def self.mnemonics_to_bytecode(mnemonics)
    bc = []
    mnemonics.each do
    |mnem|
    if MNEMONIC_TO_BYTECODE.has_key? mnem
    bc << MNEMONIC_TO_BYTECODE[mnem]
    else
    # Try packing this value as a 2-or 4-byte signed string
    # and ensure we get back the same value on unpacking it.
    if [mnem] == [mnem].pack('s').unpack('s')
    # 2-bytes will be enough
    bc << Interpreter::Ops::CONST
    bc.concat([mnem].pack('n').unpack('C*'))
    elsif [mnem] == [mnem].pack('l').unpack('l')
    # 4-bytes will be enough
    bc << Interpreter::Ops::LCONST
    bc.concat([mnem].pack('N').unpack('C*'))
    else
    # It could be dangerous to silently fail when a
    # number will not fit in a 4-byte signed int.
    raise OutOfRangeError
    end
    end
    end
    bc
    end

    # If there is a mismatch in the number of parenthesis, this
    # exception is raised by the #parse routine.
    # E.g. "3+(4-2" and "(3-10))" are both considered invalid.
    class ParenthesisError < Exception
    end

    # The operator precedence hash helps the #parse method to
    # decide when to store up operators and when to flush a load
    # out. The
    PAREN_PRECEDENCE = 0
    OP_PRECEDENCE = {
    :tok_end => -1,
    :tok_open_paren => PAREN_PRECEDENCE,
    :tok_close_paren => PAREN_PRECEDENCE,
    :tok_add => 1, :tok_subtract => 1,
    :tok_multiply => 2, :tok_div_mod => 2,
    :tok_power => 3,
    :tok_negate => 4
    }

    # Parse an array of [token,value] pairs as returned by
    # LexerMW::tokenize. Returns our own internal quasi-bytecode
    # mnemonic array.
    def self.parse(tokens)
    operator_stack = []
    ops = []

    # Push the bottom-most element with precedence equivalent to that
    # of :tok_end so when we see :tok_end all pending operation
    # tokens on the stack get popped
    precedence_stack = [OP_PRECEDENCE[:tok_end]]

    tokens.each do
    |tok, val|
    if tok == :tok_int
    # "--3".to_i => 0 is bad, so use eval("--3") => 3 instead.
    ops << eval(val)
    else
    precedence = OP_PRECEDENCE[tok]
    if not tok == :tok_open_paren
    while precedence <= precedence_stack.last &&
    precedence_stack.last > PAREN_PRECEDENCE
    # Workaround for the fact that the ** power operation
    # is calculated Right-to-left,
    # i.e. 2**3**4 == 2**(3**4) /= (2**3)**4
    break if tok == :tok_power &&
    precedence_stack.last == OP_PRECEDENCE[:tok_power]

    precedence_stack.pop
    ops << operator_stack.pop
    end
    end

    # Divide and modulo come out of the lexer as the same token
    # so override tok according to its corresponding value
    tok == :tok_div_mod && \
    tok = (val == '/') ? :tok_divide : :tok_modulo

    case tok
    when :tok_close_paren
    precedence_stack.pop == PAREN_PRECEDENCE \
    or raise ParenthesisError
    when :tok_negate
    # val contains just the minuses ('-', '--', '---', etc.)
    # Optimise out (x) === --(x) === ----(x), etc.
    if val.size % 2 == 1
    # No negate function for -(x) so simulate using 0 - (x)
    precedence_stack.push precedence
    operator_stack.push :tok_subtract
    ops << 0
    end
    when :tok_end
    raise ParenthesisError if precedence_stack.size != 1
    else
    precedence_stack.push precedence
    operator_stack.push tok unless tok == :tok_open_paren
    end
    end
    end
    ops
    end
    end

    if $0 == __FILE__
    eval DATA.read, nil, $0, __LINE__+4
    end

    __END__

    require 'test/unit'

    class TC_Compiler < Test::Unit::TestCase
    def test_simple
    @test_data = [
    '8', '124', '32767', # +ve CONST
    '-1', '-545', '-32768', # -ve CONST
    '32768', '294833', '13298833', # +ve LCONST
    '-32769', '-429433', '-24892810', # -ve LCONST
    '4+5', '7-3', '30+40+50', '14-52-125', # ADD, SUB
    '512243+1877324', '40394-12388423', # LCONST, ADD, SUB
    '3*6', '-42*-90', '94332*119939', # MUL
    '8/3', '-35/-15', '593823/44549', # DIV
    '8%3', '243%-59', '53%28%9', # MOD
    '531%-81%14', '849923%59422', #
    '-2147483648--2147483648', # SUB -ve LCONST
    '2**14', '-4**13+2' # POW
    ]
    @test_data.each do
    |sum|
    assert_equal [eval(sum)],
    Interpreter.new(Compiler.compile(sum)).run,
    "whilst calculating '#{sum}'"
    end
    end

    def test_advanced
    @test_data = [
    '-(423)', '-(-523*32)', '---0',
    '-(-(-(16**--++2)))',
    '3**(9%5-1)/3+1235349%319883+24*-3',
    '+42', '((2*-4-15/3)%16)', '4**3**((2*-4-15/3)%16)',
    '64**-(-(-3+5)**3**2)', '4*165%41*341/7/2/15%15%13',
    '--(---(4**3**((2*-4-15/3)%16))+++-410--4)'
    ]
    @test_data.each do
    |sum|
    assert_equal [eval(sum)],
    Interpreter.new(Compiler.compile(sum)).run,
    "whilst calculating '#{sum}'"
    end
    end
    end


    #!/usr/bin/env ruby
    ##################################################################
    # = lexer_mw.rb - generic lexical analyser
    #
    # Author:: Marcel Ward <wardies ^a-t^ gmaildotcom>
    # Documentation:: Marcel Ward
    # Last Modified:: Monday, 06 November 2006
    #
    # Solution for Ruby Quiz number 100 - http://www.rubyquiz.com/

    $DEBUG = 0

    # If the lexer fails to find an appropriate entry in the state
    # transition table for the current character and state, it
    # raises this exception.
    class LexerFailure < StandardError
    end

    # If the lexer encounters a character for which no matching charset
    # has been supplied then it raises this exception.
    #
    # This exception will never be raised if #init_state_transitions
    # has been called with an appropriate catch-all charset id.
    class InvalidLexeme < StandardError
    end

    class LexerMW
    # Creates an instance of the lexer class.
    #
    # _lexer_eof_ascii_::
    # defines the ASCII byte value that the lexer considers as
    # end-of-file when it is encountered. When #tokenize is called,
    # the supplied datastream is automatically appended with this
    # character.
    def initialize(lexer_eof_ascii = 0)
    @s_trans = {}
    @columns = {}
    @lex_eof = lexer_eof_ascii
    end

    # Initialize the character set columns to be used by the lexer.
    #
    # _cs_defs_::
    # a hash containing entries of the form <tt>id => match</tt>,
    # where _match_ defines the characters to be matched and _id_
    # is the id that will be passed to the finite state machine
    # to inidicate the character grouping encountered.
    # _eof_charset_id_::
    # defines the character set identifier which the lexer will
    # attempt to match in the state machine table when the
    # end-of-file character defined in #new is encountered.
    #
    # The content of _match_ falls into one of two main categories:
    #
    # _regexp_:: e.g. <tt>/\d/</tt> will match any digit 0..9; or
    # _enum_:: an enumeration that describes the set of allowed
    # character byte values, e.g.
    # the array <tt>[?*, ?/, ?%]</tt> matches
    # <b>*</b>, <b>/</b> or <b>%</b>, while the range
    # <tt>(?a..?z)</tt> matches lowercase alphas.
    #
    # e.g.
    #
    # init_char_sets({
    # :alphanum => /[A-Z0-9]/,
    # :underscore => [?_],
    # :lower_vowel => [?a, ?e, ?i, ?o, ?u],
    # :special => (0..31)
    # },
    # :end_line)
    #
    # It is the responsibility of the caller to ensure that the
    # match sets for each column are mutually exclusive.
    #
    # If a 'catch-all' set is needed then it is not necessary
    # to build the set of all characters not already matched.
    # Instead, see #init_state_transitions parameter list.
    #
    # Note, the contents of the hash is duplicated and stored
    # internally to avoid any inadvertent corruption from outside.
    def init_char_sets(cs_defs, eof_charset_id = :eof)
    @charsets = {}
    # Make a verbatim copy of the lexer charset columns
    cs_defs.each_pair do
    |charset_id, match|
    @charsets[charset_id] = match.dup # works for array/regexp
    end
    # Add an end-of-file charset column for free
    @charsets[eof_charset_id] = [@lex_eof]
    puts "@charsets =\n#{@charsets.inspect}\n\n" if $DEBUG == 1
    end

    # Initialize the state transition table that will be used by the
    # finite state machine to convert incoming characters to tokens.
    #
    # _st_::
    # a hash that defines the state transition table to be used
    # (see below).
    # _start_state_::
    # defines the starting state for the finite state machine.
    # _catch_all_charset_id_::
    # defines an optional charset id to be tried if the character
    # currently being analysed matches none of the charsets
    # in the charset table. The default +nil+ ensures that the
    # InvalidLexeme exception is raised if no charsets match.
    #
    # The state transition table hash _st_ maps each valid original
    # state to a hash containing the _rules_ to match when in that
    # state.
    #
    # Each hash entry _rule_ maps one of the character set ids
    # (defined in the call to #init_char_sets) to the _actions_ to be
    # carried out if the current character being analysed by the lexer
    # matches.
    #
    # The _action_ is a hash of distinct actions to be carried out for
    # a match. The following actions are supported:
    #
    # <tt>:next_s => _state_</tt>::
    # sets the finite state machine next state to be _state_ and
    # appends the current character to the lexeme string being
    # prepared, absorbing the current character in the datastream.
    #
    # <tt>:next_s_skip => _state_</tt>::
    # as above but the lexeme string being prepared remains static.
    #
    # <tt>:next_s_backtrack => _state_</tt>::
    # as for _next_s_skip_ above but does not absorb the current
    # character (it will be used for the next state test).
    #
    # <tt>:token => _tok_</tt>::
    # appends a hash containing a single entry to the array of
    # generated tokens, using _tok_ as the key and a copy of the
    # prepared lexeme string as the value.
    #
    # When the end of the datastream is reached, the lexer looks for
    # a match against charset <tt>:eof</tt>.
    #
    # When the performed actions contain no +next_s+... action, the
    # lexer assumes that a final state has been reached and returns
    # the accumulated array of tokens up to that point.
    #
    # e.g.
    #
    # init_state_transitions({
    # :s1 => {:alpha => {next_s = :s2},
    # :period => {:token => :tok_period}},
    # :s2 => {:alphanum => {next_s = :s2},
    # :underscore => {next_s_skip == :s2},
    # :period => {next_s_backtrack = :s1}
    # :eof => {}}, // final state, return tokens
    # }, :s1, :eek:ther_chars)
    #
    # Note, the contents of the hash is duplicated and stored
    # internally to avoid any inadvertent corruption from outside.
    def init_state_transitions(st, start_state = :s_start,
    catch_all_charset_id = nil)
    @start_state = start_state
    @others_key = catch_all_charset_id
    @s_trans = {}
    # Make a verbatim copy of the state transition table
    st.each_pair do
    |orig_state, lexer_rules|
    @s_trans[orig_state] = state_rules = {}
    lexer_rules.each_pair do
    |lexer_charset, lexer_actions|
    state_rules[lexer_charset] = cur_actions = {}
    lexer_actions.each_pair do
    |action, new_val|
    cur_actions[action] = new_val
    end
    end
    end
    puts "@s_trans =\n#{@s_trans.inspect}\n\n" if $DEBUG == 1
    end

    # Tokenize the datastream in _str_ according to the specific
    # character set and state transition table initialized through
    # #init_char_sets and #init_state_transitions.
    #
    # Returns an array of token elements where each element is
    # a pair of the form:
    #
    # [:token_name, "extracted lexeme string"]
    #
    # The end token marker [:tok_end, nil] is appended to the end
    # of the result on success, e.g.
    #
    # tokenize(str)
    # # => [[:tok_a, "123"], [:tok_b, "abc"], [:tok_end, nil]]
    #
    # Raises the LexerFailure exception if no matching state
    # transition is found for the current state and character.
    def tokenize(str)
    state = @start_state
    lexeme = ''
    tokens = []
    # Append our end of file marker to the string to be tokenized
    str += "%c" % @lex_eof
    str.each_byte do
    |char|
    char_as_str = "%c" % char
    loop do
    match = @charsets.find {
    |id, match|
    (match.kind_of? Regexp) ? \
    (match =~ char_as_str) : (match.include? char)
    } || [@others_key, @charsets[@others_key]] or \
    raise InvalidLexeme

    # Look for the action matching our current state and the
    # character set id for our current char.
    action = @s_trans[state][match.first] or raise LexerFailure

    # If found, action contains our hash of actions, e.g.
    # {:next_s_backtrack => :s_operator, :token => :tok_int}
    puts "#{char==@lex_eof?'<eof>':char_as_str}: " \
    "#{state.inspect} - #{action.inspect}" if $DEBUG == 1

    # Build up the lexeme unless we're backtracking or skipping
    lexeme << char_as_str if action.has_key? :next_s

    tokens << [action[:token], lexeme.dup] && lexeme = '' if \
    action.has_key? :token

    # Set the next state, or - when there is no specified next
    # state - we've finished, so return the tokens.
    state = action[:next_s] || action[:next_s_skip] ||
    action[:next_s_backtrack] or
    return tokens << [:tok_end, nil]

    break unless action.has_key? :next_s_backtrack
    end
    end
    tokens
    end
    end


    if $0 == __FILE__
    eval DATA.read, nil, $0, __LINE__+4
    end

    __END__

    require 'test/unit'

    class TC_LexerMW < Test::Unit::TestCase
    def test_simple
    @lexer = LexerMW.new()

    @char_sets = {
    :letter => (?a..?z),
    :digit => (/\d/),
    :space => [?\s, ?_]
    }

    @lexer.init_char_sets(@char_sets)

    @st = {
    :extract_chars => {
    :letter => {:next_s => :extract_chars},
    :digit => {:next_s => :extract_chars},
    :space => {:next_s_skip => :extract_chars,
    :token => :tok_text},
    :eof => {:token => :tok_text}
    },
    :extract_alpha => {
    :letter => {:next_s => :extract_alpha},
    :digit => {:next_s_backtrack => :extract_num,
    :token => :tok_alpha},
    :space => {:next_s_skip => :extract_alpha,
    :token => :tok_alpha},
    :eek:ther => {:next_s_skip => :extract_alpha},
    :eof_exit => {}
    },
    :extract_num => {
    :letter => {:next_s_backtrack => :extract_alpha,
    :token => :tok_num},
    :digit => {:next_s => :extract_num},
    :space => {:next_s_skip => :extract_num},
    :eek:thers => {:next_s_skip => :extract_alpha,
    :token => :tok_num}
    }
    }
    @lexer.init_state_transitions(@st, :extract_chars)
    assert_equal [
    [:tok_text, "123"], [:tok_text, "45"],
    [:tok_text, "6"], [:tok_text, "78"],
    [:tok_text, "abcd"], [:tok_text, "efghi"],
    [:tok_text, "jklmn"], [:tok_end, nil]
    ], @lexer.tokenize("123 45 6_78 abcd efghi_jklmn")

    @lexer = LexerMW.new(?$)
    @lexer.init_char_sets(@char_sets, :eof_exit)
    @lexer.init_state_transitions(@st, :extract_num, :eek:thers)
    assert_equal [
    [:tok_num, "12345678"], [:tok_alpha, "abcd"],
    [:tok_alpha, "efghi"], [:tok_num, "445"],
    [:tok_alpha, ""], [:tok_num, "1222"], [:tok_end, nil]
    ], @lexer.tokenize("123 45 6_78 abcd efghi445!12_22!ab$45")

    end
    end
     
    Marcel Ward, Nov 6, 2006
    #11
  12. Ruby Quiz

    Bill Dolinar Guest

    Changed my previous solution to use some of the things others have
    used that need to be pounded into my skull like \d in regular
    expression and pack/unpack. Also added unary + and cleaned up code.

    ############
    require 'interp'

    module Compiler

    # compile expression into bytecode array
    def Compiler.compile(s)
    stack = []
    eval(s.gsub(/(\d+)/, 'Value.new(stack, \1)'))
    stack
    end

    class Value
    attr_reader :value # constant value or nil for on stack
    ON_STACK = nil

    def initialize(stack, value)
    @stack = stack
    @value = value
    end

    # generate code for each binary operator
    {'+' => Interpreter::Ops::ADD,
    '-' => Interpreter::Ops::SUB,
    '*' => Interpreter::Ops::MUL,
    '**'=> Interpreter::Ops::pOW,
    '/' => Interpreter::Ops::DIV,
    '%' => Interpreter::Ops::MOD}.each do |operator, byte_code|
    Value.module_eval <<-OPERATOR_CODE
    def #{operator}(rhs)
    push_if_value(@value)
    push_if_value(rhs.value)
    # swap stack items if necessary
    #{if operator != "+"
    "@stack << Interpreter::Ops::SWAP if rhs.value == nil &&
    @value != nil"
    end}
    @stack << #{byte_code}
    Value.new(@stack, ON_STACK)
    end
    OPERATOR_CODE
    end

    def -@
    if @value != ON_STACK
    push_if_value(-@value)
    else
    push_if_value(0)
    @stack << Interpreter::Ops::SWAP << Interpreter::Ops::SUB
    end
    Value.new(@stack, ON_STACK)
    end

    def +@
    push_if_value(@value)
    Value.new(@stack, ON_STACK)
    end

    def push_if_value(value)
    if value != ON_STACK
    if (-32768..32767).include?(value)
    @stack << Interpreter::Ops::CONST
    @stack.concat([value].pack("n").unpack("C*"))
    else
    @stack << Interpreter::Ops::LCONST
    @stack.concat([value].pack("N").unpack("C*"))
    end
    end
    end

    end
    end
     
    Bill Dolinar, Nov 7, 2006
    #12
  13. Ruby Quiz

    Robert Conn Guest

    Here's my effort. I really enjoyed this quiz but spent way more than
    the 1 hour on it (and it's still not correct)!

    I tokenized the expression with a regex and then used the Shunting
    Yard Algorithm to do the parsing. However, I fail some of tests -

    1. Unary minus [-2+(2-2)]

    2. Order of evaluation in this expression is right-->left as opposed
    to left-->right and gives wrong result [(1+3)/(2/2)*(10-8)]

    3. The optional efficient storage test.

    I'll try to fix these if I have more time.

    Thanks

    Bob

    require "Interpreter.rb"

    class Compiler

    @PRECEDENCE = {
    '(' => -1,
    ')' => -1,
    '+' => 0,
    '-' => 0,
    '*' => 1,
    '/' => 1,
    '**' => 3,
    '%' => 3
    }

    @BYTECODE = {
    'CONST' => 0x01,
    'LCONST' => 0x02,
    '+' => 0x0a,
    '-' => 0x0b,
    '*' => 0x0c,
    '**' => 0x0d,
    '/' => 0x0e,
    '%' => 0x0f,
    'SWAP' => 0xa0
    }

    def Compiler.compile(expression)
    te = self.tokenize(expression)
    be = self.parse(te)
    self.to_bytecode(be)
    end

    def Compiler.tokenize(expression)
    tokenized_expression = []

    expression.gsub!(/\s+/, "")
    expression.scan(/(\d+|\(|\)|\+|-|\*\*|\*|\/|\%)/) { |e|
    tokenized_expression.push(e) }
    tokenized_expression
    end

    def Compiler.parse(tokenized_expression)
    output_queue, operator_stack = [], []
    operator = nil

    tokenized_expression.each { |token|

    # If token is a number, place on output queue
    if (token[0] =~ /^\d+$/)
    output_queue.push(token[0].to_i)
    elsif (token[0] == '(')
    operator_stack.push(token[0])
    elsif (token[0] == ')')
    # Pop operators off stack and onto output queue until left
    # bracket encountered
    while (operator != '(')
    if ((operator = operator_stack.pop) != '(')
    output_queue.push(operator)
    end
    end
    else
    # If there are any operators, check precedence of current token
    # against last operator on queue. If the operator on queue is
    # more important, add it to the output before pushing the
    current
    # operator on
    if (operator_stack.any? && (@PRECEDENCE[token[0]] <=
    @PRECEDENCE[operator_stack.last]))
    output_queue.push(operator_stack.pop)
    end
    operator_stack.push(token[0])
    end
    }

    # Add the remaining operators to end of the output queue
    operator_stack.reverse_each { |operator|
    output_queue.push(operator)
    }

    output_queue
    end

    def Compiler.to_bytecode(bnf_expression)
    stack = []

    bnf_expression.delete("(")
    bnf_expression.each { |token|
    case token
    when Integer
    # If number is small enough, use smaller 2 byte storage

    if ((token >= -32768) && (token <= 32767))
    stack.push(@BYTECODE['CONST'])
    stack.push(token >> 8, token)
    else
    stack.push(@BYTECODE['LCONST'])
    stack.push(token >> 24, token >> 16, token >> 8, token)
    end
    else
    stack.push(@BYTECODE[token])
    end
    }
    stack
    end

    end

    require "TestByteCode.rb"
     
    Robert Conn, Nov 7, 2006
    #13
  14. Some people started doing the Ruby quiz problems using Haskell, and
    this was a perfect opportunity for me to learn some Haskell. So here's
    my solution below, in Haskell. It's hard to test the byte code
    interpretation but all the expression do evaluate to the correct
    values.

    If anyone has questions about the Haskell code, please let me know.
    I'm just learning it and its really cool!

    BTW, I too spent way more time on this than I should have!

    (this solution, along with others, can be found on
    http://www.haskell.org/haskellwiki/Haskell_Quiz/Bytecode_Compiler)

    This solution should work correctly. I was unable to test the byte
    codes generated, for obvious reasons. However, all test strings from
    the quiz do evaluate to the correct values.

    To see the (symbolic) byte codes generated, run generate_tests. To see
    the actual byte codes, run compile_tests. To see that the values
    produced by each expression match those expected, run eval_tests. The
    tests are contained in the variables test1,test2, ..., test6, which
    correspond to the six "test_n" methods fouind in the quiz's test
    program.

    The byte codes aren't optimized. For example, SWAP is never used.
    However, they should produce correct results (even for negative and
    LCONST/CONST values).

    The code below is literate Haskell.

    \begin{code}
    import Text.ParserCombinators.Parsec hiding (parse)
    import qualified Text.ParserCombinators.Parsec as P (parse)
    import Text.ParserCombinators.Parsec.Expr
    import Data.Bits

    -- Represents various operations that can be applied
    -- to expressions.
    data Op = Plus | Minus | Mult | Div | Pow | Mod | Neg
    deriving (Show, Eq)

    -- Represents expression we can build - either numbers or expressions
    -- connected by operators.
    data Expression = Statement Op Expression Expression
    | Val Integer
    | Empty
    deriving (Show)

    -- Define the byte codes that can be generated.
    data Bytecode = NOOP | CONST Integer | LCONST Integer
    | ADD
    | SUB
    | MUL
    | POW
    | DIV
    | MOD
    | SWAP
    deriving (Show)


    -- Using imported Parsec.Expr library, build a parser for expressions.
    expr :: Parser Expression
    expr =
    buildExpressionParser table factor
    <?> "expression"
    where
    -- Recognizes a factor in an expression
    factor =
    do{ char '('
    ; x <- expr
    ; char ')'
    ; return x
    }
    <|> number
    <?> "simple expression"
    -- Recognizes a number
    number :: Parser Expression
    number = do{ ds <- many1 digit
    ; return (Val (read ds))
    }
    <?> "number"
    -- Specifies operator, associativity, precendence, and constructor to execute
    -- and built AST with.
    table =
    [[prefix "-" (Statement Mult (Val (-1)))],
    [binary "^" (Statement Pow) AssocRight],
    [binary "*" (Statement Mult) AssocLeft, binary "/" (Statement
    Div) AssocLeft, binary "%" (Statement Mod) AssocLeft],
    [binary "+" (Statement Plus) AssocLeft, binary "-" (Statement
    Minus) AssocLeft]
    ]
    where
    binary s f assoc
    = Infix (do{ string s; return f}) assoc
    prefix s f
    = Prefix (do{ string s; return f})


    -- Parses a string into an AST, using the parser defined above
    parse s = case P.parse expr "" s of
    Right ast -> ast
    Left e -> error $ show e

    -- Take AST and evaluate (mostly for testing)
    eval (Val n) = n
    eval (Statement op left right)
    | op == Mult = eval left * eval right
    | op == Minus = eval left - eval right
    | op == Plus = eval left + eval right
    | op == Div = eval left `div` eval right
    | op == Pow = eval left ^ eval right
    | op == Mod = eval left `mod` eval right

    -- Takes an AST and turns it into a byte code list
    generate stmt = generate' stmt []
    where
    generate' (Statement op left right) instr =
    let
    li = generate' left instr
    ri = generate' right instr
    lri = li ++ ri
    in case op of
    Plus -> lri ++ [ADD]
    Minus -> lri ++ [SUB]
    Mult -> lri ++ [MUL]
    Div -> lri ++ [DIV]
    Mod -> lri ++ [MOD]
    Pow -> lri ++ [POW]
    generate' (Val n) instr =
    if abs(n) > 32768
    then instr ++ [LCONST n]
    else instr ++ [CONST n]

    -- Takes a statement and converts it into a list of actual bytes to
    -- be interpreted
    compile s = toBytes (generate $ parse s)

    -- Convert a list of byte codes to a list of integer codes. If LCONST or CONST
    -- instruction are seen, correct byte representantion is produced
    toBytes ((NOOP):xs) = 0 : toBytes xs
    toBytes ((CONST n):xs) = 1 : (toConstBytes (fromInteger n)) ++ toBytes xs
    toBytes ((LCONST n):xs) = 2 : (toLConstBytes (fromInteger n)) ++ toBytes xs
    toBytes ((ADD):xs) = 0x0a : toBytes xs
    toBytes ((SUB):xs) = 0x0b : toBytes xs
    toBytes ((MUL):xs) = 0x0c : toBytes xs
    toBytes ((POW):xs) = 0x0d : toBytes xs
    toBytes ((DIV):xs) = 0x0e : toBytes xs
    toBytes ((MOD):xs) = 0x0f : toBytes xs
    toBytes ((SWAP):xs) = 0x0a : toBytes xs
    toBytes [] = []

    -- Convert number to CONST representation (2 element list)
    toConstBytes n = toByteList 2 n
    toLConstBytes n = toByteList 4 n

    -- Convert a number into a list of 8-bit bytes (big-endian/network byte order).
    -- Make sure final list is size elements long
    toByteList :: Bits Int => Int -> Int -> [Int]
    toByteList size n =
    if (length bytes) < size
    then (replicate (size - (length bytes)) 0) ++ bytes
    else bytes
    where
    bytes = reverse $ toByteList' n
    -- for negative, and with signed bit and remove negative. Then
    continue recursion.
    toByteList' 0 = []
    toByteList' a | a < 0 = (a .&. 511) : toByteList' (abs(a) `shiftR` 8)
    | otherwise = (a .&. 255) : toByteList' (a `shiftR` 8)

    -- All tests defined by the quiz, with the associated values they
    should evaluate to.
    test1 = [(2+2, "2+2"), (2-2, "2-2"), (2*2, "2*2"), (2^2, "2^2"), (2
    `div` 2, "2/2"),
    (2 `mod` 2, "2%2"), (3 `mod` 2, "3%2")]

    test2 = [(2+2+2, "2+2+2"), (2-2-2, "2-2-2"), (2*2*2, "2*2*2"), (2^2^2,
    "2^2^2"), (4 `div` 2 `div` 2, "4/2/2"),
    (7`mod`2`mod`1, "7%2%1")]

    test3 = [(2+2-2, "2+2-2"), (2-2+2, "2-2+2"), (2*2+2, "2*2+2"), (2^2+2, "2^2+2"),
    (4 `div` 2+2, "4/2+2"), (7`mod`2+1, "7%2+1")]

    test4 = [(2+(2-2), "2+(2-2)"), (2-(2+2), "2-(2+2)"), (2+(2*2),
    "2+(2*2)"), (2*(2+2), "2*(2+2)"),
    (2^(2+2), "2^(2+2)"), (4 `div` (2+2), "4/(2+2)"), (7`mod`(2+1), "7%(2+1)")]

    test5 = [(-2+(2-2), "-2+(2-2)"), (2-(-2+2), "2-(-2+2)"), (2+(2 * -2),
    "2+(2*-2)")]

    test6 = [((3 `div` 3)+(8-2), "(3/3)+(8-2)"), ((1+3) `div` (2 `div`
    2)*(10-8), "(1+3)/(2/2)*(10-8)"),
    ((1*3)*4*(5*6), "(1*3)*4*(5*6)"), ((10`mod`3)*(2+2),
    "(10%3)*(2+2)"), (2^(2+(3 `div` 2)^2), "2^(2+(3/2)^2)"),
    ((10 `div` (2+3)*4), "(10/(2+3)*4)"), (5+((5*4)`mod`(2+1)),
    "5+((5*4)%(2+1))")]

    -- Evaluates the tests and makes sure the expressions match the expected values
    eval_tests = map eval_tests [test1, test2, test3, test4, test5, test6]
    where
    eval_tests ((val, stmt):ts) =
    let eval_val = eval $ parse stmt
    in
    if val == eval_val
    then "True" : eval_tests ts
    else (stmt ++ " evaluated incorrectly to " ++ show eval_val ++
    " instead of " ++ show val) : eval_tests ts
    eval_tests [] = []

    -- Takes all the tests and displays symbolic bytes codes for each
    generate_tests = map generate_all [test1,test2,test3,test4,test5,test6]
    where generate_all ((val, stmt):ts) = generate (parse stmt) : generate_all ts
    generate_all [] = []

    -- Takes all tests and generates a list of bytes representing them
    compile_tests = map compile_all [test1,test2,test3,test4,test5,test6]
    where compile_all ((val, stmt):ts) = compile stmt : compile_all ts
    compile_all [] = []

    \end{code}
     
    Justin Bailey, Nov 7, 2006
    #14
  15. Ruby Quiz

    Mike Harris Guest

    My 2nd solution, it's the same as the first except i stole the
    pack/unpack stuff.

    class Compiler
    def self.compile(s)
    eval(s.gsub(/(\d+)([^\d])/,'\1.bc\2').gsub(/([^\d])(\d+)$/,'\1\2.bc'))
    end
    end

    class Fixnum
    def bc
    lead,pt = ( (-2**15...2**15)===self ? [1,'n'] : [2,'N'] )
    [lead].concat([self].pack(pt).unpack('C*'))
    end
    end

    class Array
    {:+ => 10,:- => 11,:* => 12,:** => 13,:/ => 14,:% => 15}.each do |op,code|
    define_method(op) { |x| self.concat(x).concat(
    Code:
    ) }
    end
    end
     
    Mike Harris, Nov 8, 2006
    #15
  16. Re: Bytecode Compiler (#100)

    #!/usr/bin/env ruby
    #
    # compiler.rb - Byte-code compiler for simple arithmetic expressions
    #
    # Lou Scoras <>
    # Wed Nov 8 20:33 EST 2006
    #
    # Here's my solution for Rubyquiz 100. Nothing too fancy on this one: I went
    # for trying to make the shunting algorith as readable as possile.
    #
    # As for the parsing, StringScanner is very nice, although it might have been
    # overkill for this problem.
    #
    # Thanks again to Ross and James for another fun quiz.

    require 'enumerator'
    require 'interp'
    require 'optparse'
    require 'strscan'

    class Token
    attr_reader :type, :value

    def initialize(value)
    @value = value
    end

    %w|number lparen rparen op|.each do |a|
    module_eval %{ def #{a}?; false end }
    end
    end

    class Paren < Token
    def initialize(value, type)
    super(value)
    @type = type
    end
    def lparen?; @type == :lparen end
    def rparen?; @type == :rparen end
    end

    class Number < Token
    def initialize(value)
    super(value.to_i)
    end

    def to_bc
    code, fmt = ((-32768..32767).include? value) ? [0x01, 'n'] : [0x02, 'N']
    [code, *[value].pack(fmt).to_enum:)each_byte).to_a]
    end
    def number?; true end
    end

    class Op < Token
    attr_reader :precedence

    CodeTable = [:+, :-, :*, :**, :/, :%].to_enum:)each_with_index).
    inject({}) {|h, (op,i)| h[op] = i + 0x0a; h}

    def initialize(value,assoc,prec)
    super(value.to_sym)
    @assoc, @precedence = assoc, prec
    end

    %w|assoc lassoc rassoc|.each do |a|
    module_eval %{
    def #{a}?
    @assoc == :#{a}
    end
    }
    end

    def op?; true end

    def to_bc
    CodeTable[value]
    end
    end

    class Compiler
    class << self

    def compile(exp)
    shunting_yard(exp).collect {|t| t.to_bc }.flatten
    end

    def tokens(i)
    input = StringScanner.new(i)
    until input.eos?
    case
    when t = input.scan(/\d+/) : yield Number.new(t)
    when t = input.scan(/[(]/) : yield Paren.new(t, :lparen)
    when t = input.scan(/[)]/) : yield Paren.new(t, :rparen)
    when t = input.scan(/\*\*/) : yield Op.new(t, :rassoc, 3)
    when t = input.scan(%r<[%/]>) : yield Op.new(t, :lassoc, 2)
    when t = input.scan(%r<[*]>) : yield Op.new(t, :assoc, 2)
    when t = input.scan(%r<[-]>) : yield Op.new(t, :lassoc, 1)
    when t = input.scan(%r<[+]>) : yield Op.new(t, :assoc, 1)
    when input.scan(/\s+/) : # skip ws
    else
    raise RuntimeError, "Parse Error: near '#{input.peek(8)}'"
    end
    end
    end

    def shunting_yard(s)
    stack, queue = [] , []
    last_tok, negate = nil, false # detect unary minus
    tokens(s) do |token|
    case
    when token.number?
    queue << (negate ? Number.new(-token.value) : token)
    negate = false
    when token.op?
    if !last_tok || (last_tok.op? || last_tok.lparen?) &&
    (token.value == :)
    negate = true
    else
    while stack.size > 0 and stack.last.op?
    other_op = stack.last
    if ( token.assoc? || token.lassoc? and
    token.precedence <= other_op.precedence) ||
    (token.rassoc? and token.precedence < other_op.precedence)
    queue << stack.pop
    else
    break
    end
    end
    stack << token
    end
    when token.lparen?
    stack << token
    when token.rparen?
    while stack.size != 0 and op = stack.pop
    break if op.lparen?
    queue << op
    end
    end
    last_tok = token
    end
    stack.reverse.each do |op|
    queue << op
    end
    queue
    end

    def to_rpn(exp)
    shunting_yard(exp).collect{|t| t.value}.join(' ')
    end

    DCBin = '/usr/bin/dc'

    def dc_eval(exp)
    if File.executable?(DCBin)
    exp = to_rpn(exp)
    IO.popen(DCBin, "w+") do |f|
    f.write(exp.gsub(/\*\*/, '^') + ' p')
    f.close_write
    f.read
    end
    end
    end

    end
    end


    if $0 == __FILE__
    opt = OptionParser.new do |opt|
    opt.banner = "Usage: #$0 compile_method"
    opt.separator ''

    opt.on('-c', '--compile [expression]',
    'prints bytecode sequence for [expression]') do |exp|
    p Compiler.compile(exp)
    end

    opt.on('-d', '--dc-eval [expression]',
    'trys to evaluate [expression] using dc(1)') do |exp|
    puts Compiler.dc_eval(exp)
    end

    opt.on('-i', '--interpret [expression]',
    'uses the byte-code interpreter to process [expression]') do |exp|
    puts Interpreter.new(Compiler.compile(exp)).run
    end

    opt.on('-r', '--show-rpn [expression]',
    'prints out an RPN translated version of [expression]') do |exp|
    puts Compiler.to_rpn(exp)
    end

    opt.on('-h', '--help') { puts opt }
    end
    if ARGV.empty?
    puts opt
    else
    opt.parse(ARGV)
    end
    end
     
    Louis J Scoras, Nov 9, 2006
    #16
  17. On 11/9/06, Ross Bamford <> wrote:
    >
    > Aww man, now I'm gonna have to look into Haskell a bit more :) I've been
    > putting it off for a while, but this is too cool to not have a play
    > with!


    You won't be disappointed. Haskell is an amazingly cool language.

    > Because I'm currently Haskell-ignorant, however, I don't know how to run
    > your solution :( . What interpreter (or compiler?) should be used? I
    > have Hugs installed, but that complains about a "Syntax error in input
    > (unexpected backslash (lambda))" at line 1.


    It looks like its supposed to be embedded in LaTeX. Just remove the
    first and last lines since the TeX directives look like lambdas to
    Haskell.

    \x -> x * x
    <==>
    lamba {|x| x*x}

    Also, Haskell is very picky about formatting. Your going to get a
    bunch of errors because of line wraps.


    --
    Lou.
     
    Louis J Scoras, Nov 9, 2006
    #17
  18. On 11/9/06, Ross Bamford <> wrote:
    > Aww man, now I'm gonna have to look into Haskell a bit more :) I've been
    > putting it off for a while, but this is too cool to not have a play
    > with!


    Awesome!

    >
    > Because I'm currently Haskell-ignorant, however, I don't know how to run
    > your solution :( . What interpreter (or compiler?) should be used? I
    > have Hugs installed, but that complains about a "Syntax error in input
    > (unexpected backslash (lambda))" at line 1.


    Like someone else pointed out, it's meant to be in a LateX document.
    It's called "literate coding" and Haskell is the first place I
    encountered it. The basic idea is you flip the normal source/comments
    order and make comments the number 1 element in the document. Code is
    then embedded in \begin{code} & \end{code} directives. (throwaway
    comment: enabling ruby to run "literate code" would make a cool quiz).

    Anyways, to run a literate haskell file in hugs, just save it with a
    "lhs" extension. At least, that works for me in WinHugs.

    To get a properly formatted version, its available on the web at:

    http://www.haskell.org/haskellwiki/Haskell_Quiz/Bytecode_Compiler/Solution_Justin_Bailey

    That version actually works (I'll be resubmitting in a minute). To run
    all the tests there, type "interpret_tests" after you load the file.

    Justin

    p.s. One nice thing about literate haskell is you can copy that entire
    page (i.e. don't worry about trying to grab only the code), paste it
    into an lhs file, and run it. Works great on blogs too!
     
    Justin Bailey, Nov 9, 2006
    #18
  19. My solution in Haskell - and this time it actually works. The previous
    implementation didn't work well with negative numbers and CONST/LCONST
    weren't generating correctly.

    The code is "literate" haskell, which means it must be saved in a file
    with "lhs" extension to run under WinHugs. To test the generated byte
    codes, run "interpret_tests" after loading the file. Other functions
    which demonstrate what is generated are:

    compile_tests - Spits out byte codes for all test expressions
    generate_tests - Spits out symbolic byte codes for all test expressions
    evaluate_tests - Evaluates ASTs generated (not bytecode) for all
    test expressions.

    This solution is also posted at

    http://www.haskell.org/haskellwiki/Haskell_Quiz/Bytecode_Compiler/Solution_Justin_Bailey

    Thanks again for a great quiz!

    Justin

    \begin{code}
    import Text.ParserCombinators.Parsec hiding (parse)
    import qualified Text.ParserCombinators.Parsec as P (parse)
    import Text.ParserCombinators.Parsec.Expr
    import Data.Bits
    import Data.Int

    -- Represents various operations that can be applied
    -- to expressions.
    data Op = Plus | Minus | Mult | Div | Pow | Mod | Neg
    deriving (Show, Eq)

    -- Represents expression we can build - either numbers or expressions
    -- connected by operators. This structure is the basis of the AST built
    -- when parsing
    data Expression = Statement Op Expression Expression
    | Val Integer
    | Empty
    deriving (Show)

    -- Define the byte codes that can be generated.
    data Bytecode = NOOP | CONST Integer | LCONST Integer
    | ADD
    | SUB
    | MUL
    | POW
    | DIV
    | MOD
    | SWAP
    deriving (Show)


    -- Using imported Parsec.Expr library, build a parser for expressions.
    expr :: Parser Expression
    expr =
    buildExpressionParser table factor
    <?> "expression"
    where
    -- Recognizes a factor in an expression
    factor =
    do{ char '('
    ; x <- expr
    ; char ')'
    ; return x
    }
    <|> number
    <?> "simple expression"
    -- Recognizes a number
    number :: Parser Expression
    number = do{ ds <- many1 digit
    ; return (Val (read ds))
    }
    <?> "number"
    -- Specifies operator, associativity, precendence, and constructor to execute
    -- and built AST with.
    table =
    [[prefix "-" (Statement Mult (Val (-1)))],
    [binary "^" (Statement Pow) AssocRight],
    [binary "*" (Statement Mult) AssocLeft, binary "/" (Statement
    Div) AssocLeft, binary "%" (Statement Mod) AssocLeft],
    [binary "+" (Statement Plus) AssocLeft, binary "-" (Statement
    Minus) AssocLeft]
    ]
    where
    binary s f assoc
    = Infix (do{ string s; return f}) assoc
    prefix s f
    = Prefix (do{ string s; return f})

    -- Parses a string into an AST, using the parser defined above
    parse s = case P.parse expr "" s of
    Right ast -> ast
    Left e -> error $ show e

    -- Take AST and evaluate (mostly for testing)
    eval (Val n) = n
    eval (Statement op left right)
    | op == Mult = eval left * eval right
    | op == Minus = eval left - eval right
    | op == Plus = eval left + eval right
    | op == Div = eval left `div` eval right
    | op == Pow = eval left ^ eval right
    | op == Mod = eval left `mod` eval right

    -- Takes an AST and turns it into a byte code list
    generate stmt = generate' stmt []
    where
    generate' (Statement op left right) instr =
    let
    li = generate' left instr
    ri = generate' right instr
    lri = li ++ ri
    in case op of
    Plus -> lri ++ [ADD]
    Minus -> lri ++ [SUB]
    Mult -> lri ++ [MUL]
    Div -> lri ++ [DIV]
    Mod -> lri ++ [MOD]
    Pow -> lri ++ [POW]
    generate' (Val n) instr =
    if abs(n) > 32768
    then LCONST n : instr
    else CONST n : instr

    -- Takes a statement and converts it into a list of actual bytes to
    -- be interpreted
    compile s = toBytes (generate $ parse s)

    -- Convert a list of byte codes to a list of integer codes. If LCONST or CONST
    -- instruction are seen, correct byte representantion is produced
    toBytes ((NOOP):xs) = 0 : toBytes xs
    toBytes ((CONST n):xs) = 1 : (toConstBytes (fromInteger n)) ++ toBytes xs
    toBytes ((LCONST n):xs) = 2 : (toLConstBytes (fromInteger n)) ++ toBytes xs
    toBytes ((ADD):xs) = 0x0a : toBytes xs
    toBytes ((SUB):xs) = 0x0b : toBytes xs
    toBytes ((MUL):xs) = 0x0c : toBytes xs
    toBytes ((POW):xs) = 0x0d : toBytes xs
    toBytes ((DIV):xs) = 0x0e : toBytes xs
    toBytes ((MOD):xs) = 0x0f : toBytes xs
    toBytes ((SWAP):xs) = 0x0a : toBytes xs
    toBytes [] = []

    -- Convert number to CONST representation (2 element list)
    toConstBytes n = toByteList 2 n
    toLConstBytes n = toByteList 4 n

    -- Convert a number into a list of 8-bit bytes (big-endian/network byte order).
    -- Make sure final list is size elements long
    toByteList :: Bits Int => Int -> Int -> [Int]
    toByteList size n = reverse $ take size (toByteList' n)
    where
    toByteList' a = (a .&. 255) : toByteList' (a `shiftR` 8)

    -- All tests defined by the quiz, with the associated values they
    should evaluate to.
    test1 = [(2+2, "2+2"), (2-2, "2-2"), (2*2, "2*2"), (2^2, "2^2"), (2
    `div` 2, "2/2"),
    (2 `mod` 2, "2%2"), (3 `mod` 2, "3%2")]

    test2 = [(2+2+2, "2+2+2"), (2-2-2, "2-2-2"), (2*2*2, "2*2*2"), (2^2^2,
    "2^2^2"), (4 `div` 2 `div` 2, "4/2/2"),
    (7`mod`2`mod`1, "7%2%1")]

    test3 = [(2+2-2, "2+2-2"), (2-2+2, "2-2+2"), (2*2+2, "2*2+2"), (2^2+2, "2^2+2"),
    (4 `div` 2+2, "4/2+2"), (7`mod`2+1, "7%2+1")]

    test4 = [(2+(2-2), "2+(2-2)"), (2-(2+2), "2-(2+2)"), (2+(2*2),
    "2+(2*2)"), (2*(2+2), "2*(2+2)"),
    (2^(2+2), "2^(2+2)"), (4 `div` (2+2), "4/(2+2)"), (7`mod`(2+1), "7%(2+1)")]

    test5 = [(-2+(2-2), "-2+(2-2)"), (2-(-2+2), "2-(-2+2)"), (2+(2 * -2),
    "2+(2*-2)")]

    test6 = [((3 `div` 3)+(8-2), "(3/3)+(8-2)"), ((1+3) `div` (2 `div`
    2)*(10-8), "(1+3)/(2/2)*(10-8)"),
    ((1*3)*4*(5*6), "(1*3)*4*(5*6)"), ((10`mod`3)*(2+2),
    "(10%3)*(2+2)"), (2^(2+(3 `div` 2)^2), "2^(2+(3/2)^2)"),
    ((10 `div` (2+3)*4), "(10/(2+3)*4)"), (5+((5*4)`mod`(2+1)),
    "5+((5*4)%(2+1))")]

    -- Evaluates the tests and makes sure the expressions match the expected values
    eval_tests = concat $ map eval_tests [test1, test2, test3, test4, test5, test6]
    where
    eval_tests ((val, stmt):ts) =
    let eval_val = eval $ parse stmt
    in
    if val == eval_val
    then ("Passed: " ++ stmt) : eval_tests ts
    else ("Failed: " ++ stmt ++ "(" ++ show eval_val ++ ")") : eval_tests ts
    eval_tests [] = []

    -- Takes all the tests and displays symbolic bytes codes for each
    generate_tests = concat $ map generate_all [test1,test2,test3,test4,test5,test6]
    where generate_all ((val, stmt):ts) = (stmt, generate (parse stmt))
    : generate_all ts
    generate_all [] = []

    -- Takes all tests and generates a list of bytes representing them
    compile_tests = concat $ map compile_all [test1,test2,test3,test4,test5,test6]
    where compile_all ((val, stmt):ts) = (stmt, compile stmt) : compile_all ts
    compile_all [] = []

    interpret_tests = concat $ map f' [test1, test2, test3, test4, test5, test6]
    where
    f' tests = map f'' tests
    f'' (expected, stmt) =
    let value = fromIntegral $ interpret [] $ compile stmt
    in
    if value == expected
    then "Passed: " ++ stmt
    else "Failed: " ++ stmt ++ "(" ++ (show value) ++ ")"

    fromBytes n xs =
    let int16 = (fromIntegral ((fromIntegral int32) :: Int16)) :: Int
    int32 = byte xs
    byte xs = foldl (\accum byte -> (accum `shiftL` 8) .|. (byte))
    (head xs) (take (n - 1) (tail xs))
    in
    if n == 2
    then int16
    else int32

    interpret [] [] = error "no result produced"
    interpret (s1:s) [] = s1
    interpret s (o:xs) | o < 10 = interpret ((fromBytes (o*2) xs):s) (drop (o*2) xs)
    interpret (s1:s2:s) (o:xs)
    | o == 16 = interpret (s2:s1:s) xs
    | otherwise = interpret (((case o of 10 -> (+); 11 -> (-); 12 ->
    (*); 13 -> (^); 14 -> div; 15 -> mod) s2 s1):s) xs

    \end{code}
     
    Justin Bailey, Nov 9, 2006
    #19
  20. On Nov 9, 2006, at 12:58 PM, Justin Bailey wrote:

    > (throwaway comment: enabling ruby to run "literate code" would make
    > a cool quiz).


    Great, write it up for us so we can all learn how it works!



    James Edward Gray II
     
    James Edward Gray II, Nov 9, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andreas Klemt
    Replies:
    2
    Views:
    416
    Marina
    Jul 28, 2003
  2. Not4u
    Replies:
    9
    Views:
    1,045
    Not4u
    Feb 27, 2004
  3. Ruby Quiz

    [SUMMARY] Bytecode Compiler (#100)

    Ruby Quiz, Nov 9, 2006, in forum: Ruby
    Replies:
    0
    Views:
    119
    Ruby Quiz
    Nov 9, 2006
  4. fred
    Replies:
    3
    Views:
    284
    Zifud
    Mar 17, 2005
  5. Replies:
    5
    Views:
    891
Loading...

Share This Page