Особенности учебного процедурного языка

В коде используется pattern matching из Ruby 2.7.

Виртуальная машина в целом реализуется по тем же лекалам, что и в примере micro-LISP интерпретатора.

Единственным существенным отличием, добавляющим сложность реализации, является механика вызова функций (и наличие встроенных функций input, output, to_integer).

Встроенные функции

Реализовать функции можно по-разному, но в нашем упрощённом варианте виртуальной машины без байт-кода будем создавать на каждую функцию целевого языка программирования Ruby-объект lambda.

Каждой такой «лямбде» понадобится иметь список ссылок на все другие определённые функции в случае, если в данной функции какие-то другие будут вызваны (при каждом вызове данной функции может быть любая комбинация всех иных пользовательских функций, в зависимости от текста конкретной программы).

Будем передавать ссылки на другие функции именованым параметром functions. Тогда вот так определим встроенные функции:

# lib/vm.rb

BUILT_IN = {
  "input" => ->(functions: nil) { STDIN.gets },
  "output" => ->(x, functions: nil) { puts(x) },
  "to_integer" => ->(x, functions: nil) { x.to_i }
}

Стартовые параметры виртуальный машины

Мы пойдём самым простым путём и будем создавать «виртуальные машины» рекурсивно на каждый чих каждый вычисляемый фрагмент.

Например, если виртуальной машине 1 дана задача вычислить выражение 1 + 2 * 3, то она породит виртуальную машину 2, которая вычислит 2 * 3 = 6, затем сложит 1 + 6 и вернёт результат 7.

Для всех операций: вызов функций, выполнение if-ов и т. д. и т. п. будет рекурсивно создаваться новая виртуальная машина.

Поэтому наша виртуальная машина должна как-то ориентироваться в текущем контексте своего выполнения и поддерживать связь с породившими их машинами. Обычно подобные вещи делаются с помощью имитации регистров и стека, у нас же (упрощённый и менее эффективный вариант) каждая дочерняя машина будет просто получать ссылку на хранилище всех переменных (@variables, которые она по ходу выполнения может изменить) и всех функций (@functions, которые она менять не должна):

# lib/vm.rb

def initialize(body, variables: {}, functions: {})
  @functions = functions
  @variables = variables
  @program = body
end

Создание Ruby-функций из fn-блоков целевого языка

Теперь мы, наконец, можем разобраться, как «скомпилировать» Ruby-функцию из AST функции нашего учебного процедурного языка.

AST (см. предыдущую лекцию) определения всех функций программы (которые, в соответсвии с описанием языка, идут в начале программы и никак иначе) выглядит вот так:

# массив всех объявленных функций
[
  # конкретная функция
  [:function_definition, '<название>',
    # строки-названия формальных аргументов/переменных
    ['x', ...],
    # инструкции
    [<массив инструкций>]
  ],
  ...
]

Если данный массив всех функций будет в переменной function_definitions интерпретатора, то вот как из него мы можем «наклепать» Ruby-функций:

functions = function_definitions.map do |(_, name, formal_arguments, body)|
  # Обрабатываем функции по одной:
  #
  # name: строка-название функции
  # formal_arguments: массив строк-названий аргументов
  # body: массив инструкций

  # Создаём "рубишную лябмду"
  f =
    # Лямбда принимает на вход список реальных аргументов
    # и ссылки на другие функции
    ->(*actual_arguments, functions:) {
      # Проверяем, что количество реальных и формальных аргументов
      # совпадает
      if actual_arguments.size != formal_arguments.size
        raise "Expected #{formal_arguments.size} arguments, got #{actual_arguments.size} " \
          "for function #{name}"
      end

      # Сцепляем формальные и реальные аргументы и получаем из них хеш
      # Например, если формальные аргументы ['x', 'y'], а реальные [1, 2]
      # то получим {'x' => 1, 'y' => 2}
      #
      variables = formal_arguments.zip(actual_arguments).to_h

      # Настраиваем и запускаем виртуальную машину, которая исполнит
      # заданный в теле функции набор инструкций при условии
      # заданных значений формальных аргументов (становящихся для
      # созданной виртуальной машины просто переменными программы)
      begin
        new(body, variables: variables, functions: functions).run
      # Обрабатываем коварный return - об этом далее
      rescue ReturnValueThrower => r
        r.value
      end
    }

  # Получаем хеш, ключами которого выступают имена свежесозданных функций,
  # а значениями - "лямбды" (аналогично хешу встроенных функций BUILT_IN)
  [name, f]
end.to_h

Каждая функция при своём вызове будет создавать новую «виртуалку», для которой:

• тело функции представлено как тело программы;
• аргументы функции представлены как заданные значения переменных программы;
• результат выполнения программы возвращаем

Стоит обратить внимание, что при таком подходе мы запрещаем использование в теле функций любых переменных, кроме формальных аргументов. «Замыканий» не реализуем. Глобальных переменных тем более.

Костяк виртуальной машины

Центральным методом виртуальной машины бдует метод run, который должен по порядку выполнить массив сохранённых инструкций @program и вернуть результат последней исполненной инструкции:

@program.each do |statement|
in [:binary_operator, '+', left, right]
  clone_and_eval_expression(left) + clone_and_eval_expression(right)
in [:binary_operator, '-', left, right]
  clone_and_eval_expression(left) + clone_and_eval_expression(right)
# и т.д.
end

Весь рутинный код обработки всех операторов приводить не буду.

Ключевой момент: в AST на месте left и right стоит не вычисленное значение операндов (например) сложения или вычитания, а тоже фрагмент AST, соответствующий выражению, которое ещё надо вычислить.

Как описано выше, для его вычисления мы запускаем отдельную виртуалку. За что отвечает метод clone_and_eval_expression, опирающийся на метод clone_and_eval_statements:

def clone_and_eval_statements(ast)
  self.class.new(ast, variables: @variables, functions: @functions).run
end

def clone_and_eval_expression(expression)
  clone_and_eval_statements([expression])
end

Метод clone_and_eval_statements создаёт и запускает новую виртуалку с переданным списком инструкций (возвращая результат их выполнения), а clone_and_eval_expression просто формирует вырожденный список инструкций, содержащий одно выражение.

Коварный return

Все бинарные операторы (и арифметические, и логические) и управляющие конструкции реализуются легко «по накатанной».

Единственная проблема, на которой можно всерьёз споткнуться, это метод return. return должен выходить из функции. Но к моменту вызова оператора return у нас может быть запущено куча рекурсивно вложенных виртуалок.

К примеру, рассмотрим такой код:

fn f(x)
  if x == 0
    return x
  end

  x - 1
end

f()

При выполнении единственной строки тела программы произойдёт следующее:

• запустится ВМ-1, вычисляющая выражение
  • запустится ВМ-2 из Ruby “лямбды”, соответствующей f()
    • запустится ВМ-3, вычисляющая if
      • запустится ВМ-4, вычисляющая x == 0; затем
      • запустится ВМ-5, вычисляющая return x
    • затем запустится ВМ-6, вычисляющая x - 1

Прикол в том, что после вызова return нам надо вернуться не только из ВМ-5, и не только из ВМ-3, но и из ВМ-2. То есть нам надо вызов return пробросить наверх по этому набору (фактически, стеку) виртуальных машин, до тех пор, пока его не поймает выделенная жирным шрифтом виртуалка. Которая запустила изначальную функцию (а не какое-то из включенных в тело функций вычислений).

Такое пробрасывание можно реализовать разными способами: например, мы можем помечать ВМ как «корневую» и в качестве возвращаемого значения передавать не только результат выполнения, но и было ли сделано прерывание выполнения с помощью метода return. Если было, то сразу же выходить из всех ВМ, пока управление не вернётся в «корневую», которая и вернёт окончательный результат функции.

Но можно сделать проще: в нашем языке разработки Ruby, как и во многих других, уже есть инструмент «прокидывания» информации из нижних уровней стека вызовов наверх — это исключения! Исключение «разматывает» стек вызванных функций, пока рано или поздно не наткнётся на инструкцию rescue (либо совсем в итоге не выпадет из программы, если rescue нигде нет).

Вот этим свойством исключений и воспользуемся:

# lib/vm.rb

module ProceduralInterpreter
  class VM
    class ReturnValueThrower < StandardError
      attr_reader :value

      def initialize(value)
        @value = value
      end
    end

    def run
      # ...

      @program.each do |statement|
        case statement

        # ...

        in [:return, expression]
          result = clone_and_eval_expression(expression)
          raise ReturnValueThrower.new(result)

        # ...
      end
    end
  end
end

Данный raise:

• прервёт цикл выполнения инструкций @program.each данной ВМ;
• прервёт цикл выполнения инструкций всех родительских ВМ;
• будет перехвачен в коде вызова функции внутри лямбды, который мы писали выше.

Заключение

Результирующий код с тестами можно посмотреть на Гитхабе.