Интерпретаторы, компиляторы и виртуальные машины
Таблица указателей сопоставляет операции и функции, выполняющие операции:
Вычисление использует операции для индексирования в таблице указанной на функции для вызова этих функций; в этой версии другие функции вызываются рекурсивно.
Обе наши версии eval применяют рекурсию. Существуют способы устранить ее – в частности, весьма хитрый способ, называемый шитым кодом ireaded code), который практически не использует стек вызовов. Самым изящным способом избавления от рекурсии будет сохранение функций в массиве, с последующим выполнением этих функций в записанном порядке. Таким образом, этот массив становится просто последовательностью конструкций, исполняемых некоторой специальной машиной.
Для представления частично вычисленных значений из нашего выражения мы, так же как и раньше, будем использовать стек, так что, несмотря на изменение формы функций, преобразования отследить будет трудно. Фактически мы изобретаем некую стековую машину, в которой инструкции представлены небольшими функциями, а операнды хранятся в отдельном стеке операндов. Естественно, это не настоящая машина, но мы можем писать программу так, как будто подобная машина все же существует: в конце концов, мы можем без труда реализовать ее в виде интерпретатора.
При обходе дерева вместо подсчета его значения мы будем генерировать массив функций, исполняющих программу. Массив будет также содержать значения данных, используемых командами, такие как константы и переменные (символы), так что тип элементов массива должен быть объединением:
