Как заставить интерпретатор Ruby выполнить программу, написанную на естественном языке

Многие языки программирования позиционируют себя как почти естественные. Ruby не отстает и позиционирует себя как "natural to read and easy to write". Однако, первый же гайд по Rails (да, Ruby это всё еще Rails) предложит вам что–то такое:

class UserController < ApplicationController
end

То есть это вот абсолютно естественный (natural) английский текст, правда? Кажется, нас обманули. Было бы здорово писать код на полностью естественном языке, например таком:

assign variable a value 1
assign variable b value 2
sum a with b

Давайте попробуем запустить эту программу!

Запускаем первую программу

Cкопируем код выше в файлик natural.rb и запустим его (irb ./natural.rb). Разумеется, программма должна упасть, однако ошибка, которую мы увидим, может показаться неожиданной: <main>: undefined method value for main:Object (NoMethodError). Почему интерпретатор не ругается на другие незнакомые ему слова, такие как assign или b?

Дело в том, что код выше является абсолютно корректным с точки зрения парсера. К примеру, строку sum a with b можно прочитать так:

• происходит вызов метода b либо чтение значения переменной b;

• результат передается методу with в качестве аргумента;

• результат вызова with передается методу a в качестве аргумента;

• результат вызова a передается методу sum в качестве аргумента.

Когда интерпретатор начинает выполнять этот код (справа налево), он падает с ошибкой: метод value нигде не определен. Давайте убедимся, что порядок вызовов и правда такой:

def assign(*)
  puts "assign"
end

def variable(*)
  puts "variable"
end

def a
  puts "a"
end

assign variable a

# => a
# => variable
# => assign

Благодаря * (который принимает любые аргументы) наш код больше не падает, однако он и не делает ничего полезного. Давайте это исправим с помощью максимально топорной реализации:

@variables = {}
@unknown_token = nil
@current_value = nil
@with = nil

def assign(*); end

def variable(*)
  @variables[@unknown_token] = @current_value
end

def value(value)
  @current_value = value
end

def method_missing(m, *args, &block)
  @unknown_token = m
end

def sum(*)
  result = @variables[@unknown_token] + @with
  print "#{result}\n"
end

def with(*)
  @with = @variables[@unknown_token]
end

# Program

assign variable a value 1
assign variable b value 2
sum a with b

Запуск этой программы приведет к выводу значения 3 в консоль.

Вам могло показаться, что язык, который мы пытаемся интерпретировать не очень–то натуральный. Я полностью разделяю ваше возмущение и хотел бы сделать что–то вроде assign 1 to variable a. Проблема в том, что такой код не является валидным с точки зрения парсера Ruby, который ожидает запятую либо конец строки после числа ?‍♂️

Давайте прочитаем код слева направо, так, как это делает интерпретатор. Сначала выполняется метод value, который принимает число и сохраняет его в глобальной переменной:

@current_value = nil

def value(value)
  @current_value = value
end

Похоже, что все, что нам нужно сделать — это объявить метод для каждого слова, которое существует в нашем «языке»! Какое слово следующее? Это a, имя переменной, и похоже что объявление методов для всех возможных имен переменных — не лучшая идея. Однако, к нам на помощь придет method_missing.

method_missing вызывается, когда объект получает сообщение, на которое он не может ответить (подробности тут)

Давайте попробуем сохранять имя последней обнаруженной переменной в другую глобальную переменную:

@unknown_token = nil

def method_missing(m, *args, &block)
  @unknown_token = m
end

Теперь нам нужно реализовать метод variable. Мы могли бы принять в качестве аргумента результат вызова метода справа от variable, но это был method_missing, поэтому мы можем просто прочитать значение из глобальной переменной. Значение переменной будет храниться в глобальной переменной @variables:

@variables = {}

def variable(*)
  @variables[@unknown_token] = @current_value
end

Наконец, метод assign (пока) ничего не делает, поэтому мы просто оставим его пустым. В результате работы первых двух строчек нашей программы (той, которая на естественном языке), в @variables будет храниться { a: 1, b: 2 }. Теперь кратко разберемся с тем, как работает sum:

1. b заставляет method_missing присвоить значение :b переменной @unknown_token;

2. with читает значение из @variables используя в качестве ключа значение переменной @unknown_token и сохраняет его в глобальной переменной @with;

3. a заставляет method_missing присвоить значение :a переменной @unknown_token;

4. sum читает значение из@variables используя в качестве ключа значение переменной @unknown_token, складывает его со значением переменной @with и печатает результат.

Здорово, правда? Безусловно! Однако, код, который мы написали не выглядит как что–то, что я хотел бы поддерживать: у нас есть неявные зависимости между вызовами методов (например, метод variable предполагает, что method_missing был вызван прямо перед ним). Что будет, если мы попробуем выполнить sum a? Мы получим непонятную ошибку, текст который никак не поможет нам ее исправить: method_missing: can't modify frozen NilClass: nil. С другой стороны, можем ли мы выполнить строчку variable a value 1? Да, но мы получим бессмысленный результат!

Возможно вы заметили, что наш «интерпретатор» не способен обрабатывать все возможные фразы естественного языка. Это правда, мы сможем реализовать только небольшое подмножество, но это все равно должно быть весело!

Интерпретатор фраз на основе стека

Наша следующая задача — создать явные зависимости между методами и данными: другими словами — использовать инкапсуляцию. Кроме того, хотелось бы помогать программисту на естественном языке исправлять ошибки в коде; для этого нам нужно переосмыслить то, как мы на них реагируем и реализовать более удобные сообщения об их возникновении.

Вместо чтения и записи глобальных переменных попробуем другой подход. Самый левый метод на каждой строчке (т.е., assign и sum) будут запускать вычисление, которое будет построено в результате вызовов методов справа от него. Вычисление будет формироваться справа налево и храниться в некоторой структуре данных, а assign — читать из неё слева направо и выполнять действия. Вероятно вы уже догадались, что подходящая структура данных — это стек.

Стек — структура данных, которая содержит список элементов и реализует две операции: push для добавление элемента наверх и pop для извлечения последнего добавленного элемента.

Вот наша новая реализация:

@variables = {}

Value = Struct.new(:value)
Token = Struct.new(:name)
Keyword = Struct.new(:type)

class Stack < Array
  def pop_if(expected_class)
    return pop if last.is_a?(expected_class)
    raise "Expected #{expected_class} but got #{last.class}"
  end

  def pop_if_keyword(keyword_type)
    pop_if(Keyword).tap do |keyword|
      unless keyword.type == keyword_type
        raise "Expected #{keyword_type} but got #{keyword.type}"
      end
    end
  end
end

@stack = Stack.new

def assign(*)
  @stack.pop_if_keyword(:variable)
  token = @stack.pop_if(Token)
  assignment = @stack.pop_if(Value)

  @variables[token.name] = assignment.value
end

def variable(*)
  @stack << Keyword.new(:variable)
end

def value(value)
  @stack << Value.new(value)
end

def method_missing(token, *args, &block)
  @stack << Token.new(token)
end

def sum(*)
  left = @stack.pop_if(Token)
  @stack.pop_if_keyword(:with)
  right = @stack.pop_if(Token)
  print @variables[left.name] + @variables[right.name]
end

def with(*)
  @stack << Keyword.new(:with)
end

# Program

assign variable a value 1
assign variable b value 2
sum a with b

Начнем с трех структур для представления возможных объектов нашего языка:

• Value содержит значения, которые присвоены переменным;

• Token содержит то, что было поймано в method_missing (пока это могут быть только имена переменных);

• Keyword это ожидаемое в выражении ключевое слово, которое нужно для того, чтобы получившаяся фраза была осмысленной.

Value и Keyword очень похожи, но представляют разные сущности: Keyword содержит имя некоторого метода, аValue хранит значение, которе было передано методу value в качестве аргумента.

После этого мы создаем наследник класса Array для реализации стека. Он содержит два дополнительных метода:

• pop_if(expected_class) проверяет, что значение на стеке является объектом переданного класса и возвращает его, а в противном случае — выбрасывает исключение;

• pop_if_keyword(keyword_type) делает почти то же самое: проверяет, что значение на стеке это Keyword, содержащий переданное значение.

Методы variable, value, method_missing и with не делают ничего кроме добавления соответствующих объектов в глобальную переменную @stack. К примеру, строчка assign variable a value 1 работает так (смотрите GIF):

1. value 1 добавляет Value.new(1) в стек;

2. a добавляет Token.new(:a) в стек;

3. variable добавляет Keyword.new(:variable) в стек.

assign пытается достать ожидаемыые данные из стека, и, если не возникло исключений — добавляет переменную в @variables:

def assign(*)
  @stack.pop_if_keyword(:variable)
  token = @stack.pop_if(Token)
  assignment = @stack.pop_if(Value)

  @variables[token.name] = assignment.value
end

Попробуйте разобраться с тем как работает sum самостоятельно (отличия минимальны), а мы перейдем к следующей проблеме. Теперь у нас есть явные связи между командными методами (assign and sum) и их данными, однако у нас осталась куча шаблонного кода, и добавление новых команд будет довольно трудоемким занятием. Давайте используем метапрограммирование и добавим небольшой DSL!

DSL для команд

Как обычно, сначала посмотрим на реализацию целиком. Обратите внимание: я не привожу класс Stack, а так же методы variable, value, method_missing и with — они не изменились.

@variables = {}
@stack = Stack.new

# Command definition DSL

class Command
  attr_reader :execution_block

  def initialize(stack, variables)
    @stack = stack
    @variables = variables
    @expectations = []
  end

  def build(&block)
    self.tap { |command| command.instance_eval(&block) }
  end

  def args
    @expectations.each_with_object([]) do |expectation, args|
      if expectation.is_a?(Keyword)
        @stack.pop_if_keyword(expectation.type)
      else
        args << @stack.pop_if(expectation)
      end
    end
  end

  private

  def token
    @expectations << Token
  end

  def value
    @expectations << Value
  end

  def keyword(type)
    @expectations << Keyword.new(type)
  end

  def execute(&block)
    @execution_block = block
  end
end

def command(command_name, &block)
  command = Command.new(@stack, @variables).build(&block)

  define_method(command_name) do |*|
    command.execution_block.call(@variables, *command.args)
  end
end

# Command definitions

command(:assign) do
  keyword(:variable)
  token
  value

  execute do |variables, token, value|
    variables[token.name] = value.value
  end
end

command(:sum) do
  token
  keyword(:with)
  token

  execute do |variables, left, right|
    result = variables[left.name] + variables[right.name]
    print "#{result}\n"
  end
end

# Program

assign variable a value 1
assign variable b value 2
sum a with b

Начyем с класса Command, содержащего данные команды. Каждая команда ожидает найти определенные объекты в стеке, поэтому нам нужно несколько методов для регистрации этих ожиданий. К примеру, так мы можем обозначить, что дальше мы ожидаем ключевое слово:

def keyword(type)
  @expectations << Keyword.new(type)
end

Кроме этого, класс содержит метод для запоминания блока, содержащего логику команды:

def execute(&block)
  @execution_block = block
end

Когда настанет время выполнить команду, мы будем сравнивать ожидаемые значения со стеком и готовить аргументы для передачи в@execution_block. pop_if и pop_if_keyword позаботятся о случаях, когда ожидаемого значения в стеке не оказалось:

def args
  @expectations.each_with_object([]) do |expectation, args|
    if expectation.is_a?(Keyword)
      @stack.pop_if_keyword(expectation.type)
    else
      args << @stack.pop_if(expectation)
    end
  end
end

Теперь давайте сделаем так, чтобы наш класс мог быть использован как часть DSL:

def build(&block)
  self.tap { |command| command.instance_eval(&block) }
end

Когда мы передаем блок в метод build, этот блок выполняется в контексте объекта этого класса с помощью метода instance_eval. В результате, все инстанс–методы становятся доступны внутри блока.

Метод command создает объект класса Commandи создает новый метод, который заставляет команду выполнить её execution_block с аргументами:

def command(command_name, &block)
  command = Command.new(@stack, @variables).build(&block)

  define_method(command_name) do |*|
    command.execution_block.call(@variables, *command.args)
  end
end

Наконец, нам нужно сконфигурировать наши команды с помощью нового DSL:

command(:assign) do
  keyword :variable
  token
  value

  execute do |variables, token, value|
    variables[token.name] = value.value
  end
end

Команда assign ожидает ключевое слово :variable, некоторый токен и некоторое значение. Токен и значение будут переданы в блок execute, внутри которого мы произведем присвоение.

Давайте убедимся, что наш DSL поможет добавлять дополнительные фразы в наш язык. К примеру, вычитание можно реализовать так:

def from(*)
  @stack << Keyword.new(:from)
end

command(:deduct) do
  token
  keyword :from
  token

  execute do |variables, left, right|
    result = variables[right.name] - variables[left.name]
    print "#{result}\n"
  end
end

assign variable x value 12
assign variable y value 5
deduct y from x

Выглядит гораздо лучше!

Теперь нам нужно разобраться с method_missing, который объявлен на верхнем уровне . Если вы запускали предыдущие примеры, то скорее всего видели предупреждение от интерпретатора. Проблема в том, что из–за него любой вызов метода на nil попадет в method_missing, что сильно усложнит отладку. Давайте попробуем инкапсулировать его в контейнер для исполнения кода.

Пишем виртуальную машину

Взгляните на реализацию виртуальной машины для выполнения программы на естественном языке:

class VM
  attr_reader :variables, :stack

  def initialize
    @variables = {}
    @stack = Stack.new
  end

  def run(&block)
    instance_eval(&block)
  end

  class << self
    def command(command_name, &block)
      define_method(command_name) { |*| Command.build(&block).run(self) }
    end

    def run(&block)
      new.run(&block)
    end
  end

  # Commands: same as before

  # command(:assign)
  # command(:sum)

  # Primitives: same as before

  # def variable(*)
  # def value(value)
  # def method_missing(token, *args, &block)
  # def with(*)
  # def from(*)
end

# Program

VM.run do
  assign variable a value 1
  assign variable b value 2
  sum a with b
end

Основное изменение — программа на естественном языке будет выполняться внутри блока VM.run do. Для того, чтобы это заработало, мы используем тот же трюк, что и в Command: все нужные методы (такие как variable) перемещаются в класс Vm и становятся доступными внутри блока благодаря instance_eval:

def run(&block)
  instance_eval(&block)
end

@stack и @variables перестали быть глобальными и переместились в VM.

В принципе, на этом можно было бы закончить, но давайте попробуем кое–что еще: что если наша виртуальная машина сможет запускать программы на разных естественных языках? Для создания языков мы сможем использовать специальный DSL, а затем передавать их в экземпляр VM для исполнения:

lang = Lang.define do
  command :assign do
    keyword :variable
    token
    value

    execute { |vm, token, value| vm.assign_variable(token, value) }
  end

  command :sum do
    token
    keyword :with
    token

    execute do |vm, left, right|
      result = vm.read_variable(left) + vm.read_variable(right)
      print "#{result}\n"
    end
  end
end

VM.run(lang) do
  assign variable a value 1
  assign variable b value 2
  sum a with b
end

Главное преимущество такого подхода — наши «примитивы» (variable, with, etc.) также будут определяться динамически, на основе синтаксиса языка.

DSL для создания «естественных» языков

Как обычно, начнем с полного решения:

class Lang
  def self.define(&block)
    new.tap { |lang| lang.instance_eval(&block) }
  end

  def command(command_name, &block)
    command = Command.build(command_name, &block)
    register_keywords(command)
    commands[command_name] = command
  end

  def keywords
    @keywords ||= []
  end

  def commands
    @commands ||= {}
  end

  private

  def register_keywords(command)
    command.expectations
      .filter { |expectation| expectation.is_a?(Keyword) }
      .reject { |keyword| keywords.include?(keyword.type) }
      .each { |keyword| keywords << keyword.type }
  end
end

class VM
  def self.run(lang, &block)
    lang.commands.each do |command_name, command|
      define_method(command_name) { |*| command.run(self) }
    end

    new(lang).run(&block)
  end

  attr_reader :variables, :stack

  def initialize(lang)
    @lang = lang
    @variables = {}
    @stack = Stack.new
  end

  def run(&block)
    instance_eval(&block)
  end

  def assign_variable(token, value)
    @variables[token.name] = value.value
  end

  def read_variable(token)
    @variables[token.name]
  end

  def value(value)
    @stack << Value.new(value)
  end

  def method_missing(unknown, *args, &block)
    klass = @lang.keywords.include?(unknown) ? Keyword : Token
    @stack << klass.new(unknown)
  end
end

# Language definition

lang = Lang.define do
  command :assign do
    keyword :variable
    token
    value

    execute { |vm, token, value| vm.assign_variable(token, value) }
  end

  command :sum do
    token
    keyword :with
    token

    execute do |vm, left, right|
      result = vm.read_variable(left) + vm.read_variable(right)
      print "#{result}\n"
    end
  end
end

# Program

VM.run(lang) do
  assign variable a value 1
  assign variable b value 2
  sum a with b
end

КлассLang используется для настройки синтаксиса естественного языка. Обратите внимание, уже знакомый нам instance_eval снова в деле:

def self.define(&block)
  new.tap { |lang| lang.instance_eval(&block) }
end

command — единственный метод, который мы будем использовать внутри блока, переданного в define. Он принимает на вход название команды и её тело. Оба аргумента затем передаются в фабричный метод класса Command:

def command(command_name, &block)
  command = Command.build(command_name, &block)
  register_keywords(command)
  commands[command_name] = command
end

После инициализации команды нам нужно добавить её в список команд, а также зарегистрировать ключевые слова, которые она содержит:

def register_keywords(command)
  command.expectations
    .filter { |expectation| expectation.is_a?(Keyword) }
    .reject { |keyword| keywords.include?(keyword.type) }
    .each { |keyword| keywords << keyword.type }
end

Теперь мы можем создать язык, который содержит два ключевых слова (variable и with) и две команды (assign и sum):

lang = Lang.define do
  command :assign do
    keyword :variable
    token
    value

    execute { |vm, token, value| vm.assign_variable(token, value) }
  end

  command :sum do
    token
    keyword :with
    token

    execute do |vm, left, right|
      result = vm.read_variable(left) + vm.read_variable(right)
      print "#{result}\n"
    end
  end
end

Теперь нам нужно внести изменения в класс VM. Описание языка переехалов в отдельный класс, поэтому все относящиеся к конкретному языку можно удалить. Давате внесем изменения в метод run чтобы добавлять их в виртуальную машину при запуске конкретного языка:

def self.run(lang, &block)
  lang.commands.each do |command_name, command|
    define_method(command_name) { |*| command.run(self) }
  end

  new(lang).run(&block)
end

Такое решение не идеально, так как эти методы останутся объявленными в экземпляре класса. Впрочем, для наших целей такое поведение допустимо, поэтому не будем усложнять ?

Еще одно важное изменение — появление низкоуровневых опереций в классе VM. Их можно использовать внутри тела команд:

def assign_variable(token, value)
  @variables[token.name] = value.value
end

def read_variable(token)
  @variables[token.name]
end

def value(value)
  @stack << Value.new(value)
end

Последнее изменение касается method_missing: теперь метод может обрабатывать и токены и ключевые слова, как как список возможных ключевых слов есть в объекте класса Lang:

def method_missing(unknown, *args, &block)
  klass = @lang.keywords.include?(unknown) ? Keyword : Token
  @stack << klass.new(unknown)
end

Все готово! Давайте создадим новый язык с другим синтаксисом и убедимся что он работает:

another_lang = Lang.define do
  command(:set) do
    keyword :variable
    token
    keyword :to
    value

    execute { |vm, token, value| vm.assign_variable(token, value) }
  end

  command(:access) do
    keyword :variable
    token

    execute do |vm, token|
      result = vm.read_variable(token)
      print "#{result}\n"
    end
  end
end

VM.run(another_lang) do
  set variable a to value 42
  access variable a # => 42
end

Таки работает!

Travel planning

Вероятно вы думаете, что все, на что способен наш конструктор языков — это чтение и запись переменных. Попробую вас разубедить: сейчас мы создадим язык запросов, который сможет отвечать на вопросы о длительности маршрутов между городами. Вот как выглядит его синтаксис:

VM.run(lang) do
  route from london to glasgow takes 22
  route from paris to prague takes 12
  how long will it take to get from london to glasgow
end

Было бы здорово сделать синтаксис вида route from london to glasgow takes 22 hours но этот код не является валидным с точки зрения парсера ?

Возможно ли реализовать такой язык? Конечно, но есть одна проблема: в текущей реализации мы не можем использовать takes как метод, который принимает значение, стоящее после него. Дело в том, что для этой цели у нас есть метод value и нет способа его переименовать.

Давайте внесем изменение в класс Command так, чтобы его метод value принимал аргумент и использовал его в качестве имени метода для сохранения значения (полная версия тут):

class Command
  attr_reader :execution_block, :value_method_names

  # ...

  def value_method_names
    @value_method_names ||= []
  end

  private

  def value(method_name)
    value_method_names << method_name
    expectations << Value
  end

  # ...
end

Теперь нам нужно поменять класс Lang так, чтобы он создавал соответствующий метод в классе VM:

class VM
  def self.run(lang, &block)
    lang.commands.each do |command_name, command|
      define_method(command_name) { |*| command.run(self) }

      command.value_method_names.each do |value_method_name|
        define_method(value_method_name) do |value|
          @stack << Value.new(value)
        end
      end
    end

    new(lang).run(&block)
  end

  # no changes, but `value` method is removed
end

Всё, что нам осталось сделать — это создать наш язык запросов:

lang = Lang.define do
  command :route do
    keyword :from
    token
    keyword :to
    token
    value :takes

    execute do |vm, city1, city2, distance|
      distances = vm.read_variable(:distances) || {}
      distances[[city1, city2]] = distance
      vm.assign_variable(:distances, Value.new(distances))
    end
  end

  command :how do
    keyword :long
    keyword :will
    keyword :it
    keyword :take
    keyword :to
    keyword :get
    keyword :from
    token
    keyword :to
    token

    execute do |vm, city1, city2|
      distances = vm.read_variable(:distances) || {}
      distance = distances[[city1, city2]].value
      puts "Travel from #{city1.name} to #{city2.name} takes #{distance} hours"
    end
  end
end

Как вы видите, мы используем наши низкоуровневые методы VM#read_variable и VM#assign_variable для того, чтобы сохранять и читать расстояния. Мы могли бы даже реализовать алгоритм Дейкстры и искать кратчайший путь по графу, но это выходит за рамки этого поста ?

---

На этом все! С помощью метапрограммирования мы смогли заставить интерпретатор Ruby запускать программы на «почти естественном языке». Разумеется, возможности такого интерпретатора довольно ограничены. Если у вас осталось желание поэксперементировать еще — ниже пара идей, которые я решил не реализовывать в рамках статьи:

1. Реализовать присвоение значения одной переменной из другой (e.g., assign variable b value a).

2. Сделать DSL команд менее многословным:

command(:assign, keyword(:variable).token.value) do |vm, token, value|
  vm.assign_variable(token, value)
end

Подсказка: для реализации keyword(:variable).token.value можно использовать CPS.