Iterative Ruby(ish) Interpreter

iterative_ruby_interpreter.rb

# helper
def seq(seq)
  seq.reverse.reduce do |rest, crnt|
    Parser::AST::Node.new(:seq, [crnt, rest])
  end
end

# convert parser's AST to our AST
require 'parser/ruby25'
def parse(code)
  transform Parser::Ruby25.parse code
end

def transform(ast)
  return ast unless ast.kind_of? Parser::AST::Node
  case ast.type
  when :begin
    seq ast.children.map { |child| transform child }
  when :class
    name, _, defn = ast.children
    seq [
      Parser::AST::Node.new(:push, [
        Parser::AST::Node.new(:open_class, [name.children[1]]),
      ]),
      transform(defn),
      Parser::AST::Node.new(:pop, []),
    ]
  when :def
    name, args, body = ast.children
    Parser::AST::Node.new(:def, [name, transform(args), transform(body)])
  when :ivasgn, :lvasgn
    type = ast.type
    name, val = ast.children
    Parser::AST::Node.new(type, [name, transform(val)])
  when :send
    receiver, name, *args = ast.children
    Parser::AST::Node.new(:send_lookup_receiver, [transform(receiver), name, args.map { |arg| transform arg }])
  when :const
    _ns, name = ast.children
    Parser::AST::Node.new(:const, [name])
  when :int
    Parser::AST::Node.new(:int, [
      { class: :Integer, ivars: {}, value: ast.children[0] }
    ])
  when :str
    Parser::AST::Node.new(:str, [
      { class: :String, ivars: {}, value: ast.children[0] }
    ])
  when :args, :ivasgn, :lvar, :ivar
    ast
  when :splat
    expr, * = ast.children
    Parser::AST::Node.new(:splat, [transform(expr)])
  else
    ast
    # =>
    raise "wat: #{ast.type}"
  end
end



# one iteration of evaluation
def iterate(ast, stack, classes)
  result_ast, result_value = case ast.type
  when :seq
    first, rest = ast.children
    first, value = iterate first, stack, classes
    if first
      [seq([first, rest])]
    else
      [rest, nil]
    end
  when :push
    val_ast, * = ast.children
    val_ast, value = iterate val_ast, stack, classes
    if val_ast
      [Parser::AST::Node.new(:push, [val_ast]), nil]
    else
      stack.push locals: {}, this: value, value: nil
      [nil, value]
    end
  when :pop
    [nil, stack.pop.fetch(:value)]
  when :open_class
    name, * = ast.children
    [nil, (classes[name] ||= { class: :Class, name: name, methods: {} })]
  when :def
    name, params, body = ast.children
    stack.last[:this][:methods][name] = { params: params, body: body }
    [nil, name]
  when :lvasgn
    name, value_ast = ast.children
    value_ast, value = iterate(value_ast, stack, classes)
    if value_ast
      ast = Parser::AST::Node.new(:lvasgn, [name, value_ast])
      [ast, nil]
    else
      stack.last[:locals][name] = value
      [nil, value]
    end
  when :const
    name, * = ast.children
    [nil, classes.fetch(name)]
  when :send_lookup_receiver
    receiver_ast, name, arg_asts = ast.children
    if receiver_ast
      receiver_ast, receiver = iterate(receiver_ast, stack, classes)
    else
      receiver = stack.last.fetch(:this)
    end
    if receiver_ast
      [ Parser::AST::Node.new(:send_lookup_receiver, [receiver_ast, name, arg_asts]), nil ]
    else
      [ Parser::AST::Node.new(:send_eval_args, [receiver, name, [], arg_asts]), nil ]
    end
  when :send_eval_args
    receiver, name, args, arg_asts = ast.children
    if arg_asts.empty?
      [ Parser::AST::Node.new(:send_lookup_method, [receiver, name, args]), nil ]
    else
      arg_ast, *arg_asts = arg_asts
      if arg_ast.type == :splat
        arg_ast, arg = iterate(arg_ast.children[0], stack, classes)
        if arg_ast
          [ Parser::AST::Node.new(:send_eval_args, [
              receiver, name, args, [
                Parser::AST::Node.new(:splat, [arg_ast]), *arg_asts
              ]
            ]),
            nil
          ]
        else
          [ Parser::AST::Node.new(:send_eval_args, [receiver, name, [*args, *arg], arg_asts]), nil ]
        end
      else
        arg_ast, arg = iterate(arg_ast, stack, classes)
        if arg_ast
          [ Parser::AST::Node.new(:send_eval_args, [receiver, name, args, [arg_ast, *arg_asts]]), nil ]
        else
          [ Parser::AST::Node.new(:send_eval_args, [receiver, name, [*args, arg], arg_asts]), nil ]
        end
      end
      
    end
  when :send_lookup_method
    receiver, name, args = ast.children
    klass  = classes.fetch(receiver.fetch(:class))
    method = klass.fetch(:methods).fetch(name)
    [ Parser::AST::Node.new(:send_invoke, [receiver, method, args]), nil ]
  when :send_invoke
    receiver, method, args = ast.children
    case method
    when Proc
      method.call(receiver, args, stack, classes)
    else
      params = method.fetch(:params).children.dup
      body   = method.fetch :body
      locals = {}
      args   = args.dup
      while params.any?
        param = params.shift
        case param.type
        when :restarg
          locals[param.children[0]] = args
        when :arg
          locals[param.children[0]] = args.shift
        else
          raise "UNKNOWN PARAM #{param.inspect}"
        end
      end
      stack.push locals: locals, this: receiver, value: nil
      [seq([body, Parser::AST::Node.new(:pop, [])]), nil]
    end

  when :lvar
    name, * = ast.children
    [nil, stack.last.fetch(:locals).fetch(name)]
    
  when :str, :int
    [nil, ast.children[0]]

  when :ivasgn
    name, val_ast = ast.children
    val_ast, val = iterate val_ast, stack, classes
    if val_ast
      [Parser::AST::Node.new(:ivasgn, [name, val_ast]), nil]
    else
      stack.last.fetch(:this).fetch(:ivars)[name] = val
      [nil, val]
    end

  when :ivar
    name, * = ast.children
    value = stack.last.fetch(:this).fetch(:ivars).fetch(name)
    [nil, value]

  else
    raise "wat: #{ast.type}"
  end

  if result_value
    stack.last[:value] = result_value
  end
  
  [result_ast, result_value]
end

# builtin classes and objects
printed = ""
main = { class: :Object, ivars: {} }
stack = [{locals: {}, this: main, value: nil}]
classes = {
  Class: {
    name: :Class,
    methods: {
      allocate: lambda { |this, args, stack, classes|
        [nil, { class: this[:name], ivars: {} }]
      },
    },
  },
  Object: {
    name: :Object,
    methods: {
      puts: lambda { |this, args, stack, classes|
        args.each do |arg|
          arg = arg.fetch(:value, arg)
          printed << "#{arg.to_s.chomp}\n"
        end
        [nil, nil]
      },
    },
  },
  Integer: {
    name: :Integer,
    methods: {
      "+": lambda { |this, args, stack, classes|
        value = this.fetch(:value) + args.fetch(0).fetch(:value)
        [nil, {**this, value: value}]
      },
    },
  },
}

# the code we'll evaluate
ast = parse <<~RUBY
class Class
  def new(*args)
    instance = allocate
    instance.initialize(*args)
    instance
  end
end

class User
  def initialize(name, age)
    @name = name
    @age = age
  end
  def name
    @name
  end
  def age
    @age
  end
  def birthday!
    @age = @age + 1
  end
end
user = User.new "Alice", 70
puts user.name
puts user.age
user.birthday!
puts user.age
RUBY


# evaluate it
iterations = 0
value = nil
while ast
  iterations += 1
  ast, value = iterate(ast, stack, classes)
end

printed
# => "Alice\n" +
#    "70\n" +
#    "71\n"