Как заставить интерпретатор 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.