The Stack VM Plan

The Stack VM Plan: I have spent twenty years compiling Ruby onto other people's virtual machines, so for the strange round I built the inverse: a virtual machine made OUT OF the framework. An arithmetic expression compiles to stack bytecode (push/add/sub/ mul/div - a pocket YARV), and then each INSTRUCTION becomes a task: the plan is the instruction stream, the dependency chain is the program counter, and the stack threads through previous_output as an immutable value. …

source on github

a real captured run

THE STACK VM PLAN (a virtual machine whose instructions are jobs)

  (2 + 3) * (10 - 4)  =>  30   (Ruby says 30)
      push 2    -> [2]
      push 3    -> [2, 3]
      add       -> [5]
      push 10   -> [5, 10]
      push 4    -> [5, 10, 4]
      sub       -> [5, 6]
      mul       -> [30]
      peephole: 7 instructions -> 1 (push 30), same answer: true

  72 / (2 + 6) - 4  =>  5   (Ruby says 5)
      peephole: 7 instructions -> 1 (push 5), same answer: true

  1 + 2 * 3 - 4 / 2  =>  5   (Ruby says 5)
      peephole: 9 instructions -> 1 (push 5), same answer: true

  what the bit decompiles to: 'the plan is the program' stops
  being a metaphor when the tasks ARE instructions - the chain is
  the program counter, previous_output is the operand stack
  (frozen: this machine has no registers to corrupt), and the
  whole thing cross-checks against the only reference
  implementation that matters, Ruby herself. and the peephole
  pass is the JRuby lesson in one line: the fastest instruction
  is the one you delete before the executor ever sees it - every
  program above folded to a SINGLE push, because arithmetic on
  constants is the compiler's job, not the runtime's. twenty
  years of VM work, and the moral still fits in a peephole.

source

# frozen_string_literal: true

# The Stack VM Plan: I have spent twenty years compiling Ruby onto
# other people's virtual machines, so for the strange round I built
# the inverse: a virtual machine made OUT OF the framework. An
# arithmetic expression compiles to stack bytecode (push/add/sub/
# mul/div - a pocket YARV), and then each INSTRUCTION becomes a
# task: the plan is the instruction stream, the dependency chain is
# the program counter, and the stack threads through previous_output
# as an immutable value. Absurd? Completely. But it decompiles the
# word "executor" back to its roots - and it comes with a peephole
# optimizer, because no instruction stream of mine ships unoptimized.
#
#   bundle exec ruby examples/stack_vm_plan.rb
#
# Runs offline; exits 1 unless the plan-VM agrees with Ruby itself
# on every program, before AND after optimization.

require class="s">"bundler/setup"
require class="s">"agentic"

Agentic.logger.level = class="y">:fatal

# --- the compiler: recursive descent, postfix out (a pocket YARV) -------------------
def compile(src)
  tokens = src.scan(%r{\d+|[-+*/()]})
  code = []
  expr = term = factor = nil
  factor = -> {
    if tokens.first == class="s">"("
      tokens.shift
      expr.call
      tokens.shift # class="s">")"
    else
      code << [class="y">:push, tokens.shift.to_i]
    end
  }
  term = -> {
    factor.call
    while [class="s">"*", class="s">"/"].include?(tokens.first)
      op = tokens.shift
      factor.call
      code << [(op == class="s">"*") ? class="y">:mul : class="y">:div]
    end
  }
  expr = -> {
    term.call
    while [class="s">"+", class="s">"-"].include?(tokens.first)
      op = tokens.shift
      term.call
      code << [(op == class="s">"+") ? class="y">:add : class="y">:sub]
    end
  }
  expr.call
  code
end

# --- the peephole optimizer: constant folding until fixpoint ------------------------
def optimize(code)
  folded = code.dup
  loop do
    index = (0..folded.size - 3).find { |i|
      folded[i][0] == class="y">:push && folded[i + 1][0] == class="y">:push && [class="y">:add, class="y">:sub, class="y">:mul, class="y">:div].include?(folded[i + 2][0])
    }
    break unless index
    a, b, op = folded[index][1], folded[index + 1][1], folded[index + 2][0]
    value = {add: a + b, sub: a - b, mul: a * b, div: a / b}.fetch(op)
    folded[index, 3] = [[class="y">:push, value]]
  end
  folded
end

# --- the machine: one task per instruction, stack via previous_output ---------------
def run_on_plan_vm(code)
  orchestrator = Agentic:class="y">:PlanOrchestrator.new(concurrency_limit: 1) # a program counter, not a pool
  previous = nil
  trace = []
  code.each_with_index do |(op, arg), pc|
    task = Agentic:class="y">:Task.new(description: class="s">"pc=#{pc} #{op} #{arg}".strip, agent_spec: {class="s">"name" => op.to_s, class="s">"instructions" => class="s">"w"})
    orchestrator.add_task(task, previous ? [previous] : [], agent: ->(t) {
      stack = (t.previous_output || []).dup
      case op
      when class="y">:push then stack.push(arg)
      when class="y">:add then b = stack.pop
                     stack.push(stack.pop + b)
      when class="y">:sub then b = stack.pop
                     stack.push(stack.pop - b)
      when class="y">:mul then b = stack.pop
                     stack.push(stack.pop * b)
      when class="y">:div then b = stack.pop
                     stack.push(stack.pop / b)
      end
      trace << class="s">"#{"#{op} #{arg}class="s">".strip.ljust(9)} -> [#{stack.join(", class="s">")}]"
      stack.freeze
    })
    previous = task
  end
  result = orchestrator.execute_plan
  [result.task_result(previous.id).output.first, trace]
end

PROGRAMS = [class="s">"(2 + 3) * (10 - 4)", class="s">"72 / (2 + 6) - 4", class="s">"1 + 2 * 3 - 4 / 2"].freeze

puts class="s">"THE STACK VM PLAN (a virtual machine whose instructions are jobs)"
puts

failures = []
PROGRAMS.each do |src|
  code = compile(src)
  lean = optimize(code)
  value, trace = run_on_plan_vm(code)
  lean_value, = run_on_plan_vm(lean)
  truth = eval(src) # rubocop:disable Security/Eval -- the reference implementation is Ruby itself, on a literal from this file

  puts class="s">"  #{src}  =>  #{value}   (Ruby says #{truth})"
  trace.each { |line| puts class="s">"      #{line}" } if src == PROGRAMS.first
  puts class="s">"      peephole: #{code.size} instructions -> #{lean.size} (#{lean.map { |op, arg| "#{op} #{arg}class="s">".strip }.join("; class="s">")}), same answer: #{lean_value == value}"
  puts
  failures << class="s">"#{src}: plan-VM says #{value}, Ruby says #{truth}" unless value == truth
  failures << class="s">"#{src}: optimizer changed the answer" unless lean_value == truth
  failures << class="s">"#{src}: optimizer didn't optimize" unless lean.size < code.size
end

puts class="s">"  what the bit decompiles to: 'the plan is the program' stops"
puts class="s">"  being a metaphor when the tasks ARE instructions - the chain is"
puts class="s">"  the program counter, previous_output is the operand stack"
puts class="s">"  (frozen: this machine has no registers to corrupt), and the"
puts class="s">"  whole thing cross-checks against the only reference"
puts class="s">"  implementation that matters, Ruby herself. and the peephole"
puts class="s">"  pass is the JRuby lesson in one line: the fastest instruction"
puts class="s">"  is the one you delete before the executor ever sees it - every"
puts class="s">"  program above folded to a SINGLE push, because arithmetic on"
puts class="s">"  constants is the compiler's job, not the runtime's. twenty"
puts class="s">"  years of VM work, and the moral still fits in a peephole."
exit(failures.empty? ? 0 : 1)