@mattn氏の方じゃなくてこっちのやつ。
http://qiita.com/shuetsu@github/items/ac21e597265d6bb906dc

IExpression は lambda に押し込んで極力手を抜いていくスタイル。

エラー処理？
そんなものはない。

orelang.rb

#!/usr/bin/env ruby

module Orelang
  module Operator
    extend self
    attr_reader :op

    @op = {}

    @op["+"] = -> (e, args) {
      args.reduce(0) { |a, n| a + e.eval(n) }
    }
    @op["*"] = -> (e, args) {
      args.reduce(1) { |a, n| a * e.eval(n) }
    }
    @op["="] = -> (e, args) {
      e.eval(args[0]) === e.eval(args[1])
    }
    @op["set"] = -> (e, args) {
      e.vars[e.eval(args[0])] = e.eval(args[1])
    }
    @op["get"] = -> (e, args) {
      e.vars[e.eval(args[0])]
    }
    @op["until"] = -> (e, args) {
      e.eval(args[1]) while ! e.eval(args[0])
    }
    @op["step"] = -> (e, args) {
      args.reduce(0) { |r, n|
        r = e.eval(n)
      }
    }
  end

  class Engine
    attr_accessor :vars

    def initialize
      @vars = {}
    end

    def eval(expr)
      if expr.instance_of?(Array)
        op = Operator::op[expr[0]]
        args = expr[1..-1]
        -> {
          op.call(self, args)
        }
      else
        -> {
          expr
        }
      end.call
    end
  end
end

test_orelang.rb

#!/usr/bin/env ruby

require 'test/unit'
require "json"
require './orelang'

class TestOrelang < Test::Unit::TestCase
  def test_expr1
    engine = Orelang::Engine.new
    result = engine.eval(JSON.parse('["+", 1, 2, ["*", 3, 4]]'))
    assert_equal 15, result
  end

  def test_expr2
    str = <<-EOD
["step",
  ["set", "i", 10],
  ["set", "sum", 0],
  ["until", ["=", ["get", "i"], 0], [
    "step",
    ["set", "sum", ["+", ["get", "sum"], ["get", "i"]]],
    ["set", "i", ["+", ["get", "i"], -1]]
  ]],
  ["get", "sum"]
]
    EOD
    engine = Orelang::Engine.new
    result = engine.eval(JSON.parse(str))
    assert_equal 55, result
  end
end