Интерпретатор стекового языка программирования удовлетворяет следующим условиям:
- Интерпретатор вызывается как процедура
(interpret [program] [stack]), которая принимает программу на исходном языке[program]и начальное состояние стека данных[stack]и возвращает его состояние после вычисления программы; - Программа на исходном языке задана вектором литеральных констант, соответствующих словам исходного языка;
- Исходное и конечное состояния стека данных являются списком, голова которого соответствует вершине стека.
Пример вызова интерпретатора:
(interpret #(define abs
dup 0 <
if neg endif
end
abs) ; программа
'(-9)) ; исходное состояние стека
⇒ (9)
Язык, интерпретатор которого реализован, является видоизмененным ограниченным подмножеством языка Forth.
В языке операции осуществляются с целыми числами. Используется постфиксная запись операторов. Все вычисления осуществляются на стеке данных. При запуске интерпретатора стек может быть инициализирован некоторыми исходными данными или быть пустым.
Программа на исходном языке представляет собой последовательность слов. Интерпретатор анализирует слова по очереди:
- Если слово является целым числом, то оно (число) помещается на вершину стека данных;
- В противном случае слово интерпретируется как оператор (процедура):
- Если в программе уже встретилось определение этого слова (статья), то выполняется код этого определения;
- В противном случае слово рассматривается как встроенное в интерпретатор и выполняется соответствующей процедурой интерпретатора. Затем осуществляется возврат из процедуры (переход к слову, следующему за последним вызовом);
- Выполнение программы заканчивается, когда выполнено последнее слово.
Процедуры (операторы) снимают свои аргументы с вершины стека данных и кладут результат вычислений также на вершину стека данных. Ввод-вывод или какое-либо взаимодействие с пользователем не предусматривается.
Например: (interpret #(2 3 * 4 5 * +) '()) ⇒ (26)
Ниже представлен список встроенных слов с кратким описанием их значений. Состояние стека до и после интерпретации каждого слова показаны с помощью схем — стековых диаграмм.
Например, программа: 1 2 3 может быть показана стековой диаграммой: () → (1 2 3).
В интерпретаторе в качестве стека используется список. Голова этого списка является вершиной стека, поэтому вершина стека в этих диаграммах находится слева. Такая запись отличается от традиционных стековых диаграмм, принятых, например, в языке Forth, в которых голова стека записывается справа.
Как уже было сказано язык использует постфиксную нотацию, то есть, например, операция сложения чисел 1 и 2 будет записана как: 1 2 +, аналогично с остальными операциями (в том числе и унарными).
| Операция | Стэковая диаграмма | Описание |
|---|---|---|
| + | (n2 n1) → (сумма) | Cумма: n1 + n2 |
| - | (n2 n1) → (разность) | Разность: n1 − n2 |
| * | (n2 n1) → (произведение) | Произведение: n2 * n1 |
| / | (n2 n1) → (частное) | Целочисленное деление n1 на n2 |
| mod | (n2 n1) → (остаток) | Остаток от деления n1 на n2 |
| neg | (n) → (−n) | Смена знака числа |
Булевы значения представлены с помощью целых чисел: −1 соответствует значению «истина», 0 — значению «ложь».
| Операция | Стэковая диаграмма | Описание |
|---|---|---|
| = | (n2 n1) → (флаг) | Флаг равен −1, если n1 = n2, иначе флаг равен 0 |
| > | (n2 n1) → (флаг) | Флаг равен −1, если n1 > n2, иначе флаг равен 0 |
| < | (n2 n1) → (флаг) | Флаг равен −1, если n1 < n2, иначе флаг равен 0 |
Эти операции также дают правильный результат, если в одном или обеих операндах «истина» представлена любым ненулевым целым числом.
| Операция | Стэковая диаграмма | Описание |
|---|---|---|
| not | (n) → (результат) | НЕ n |
| and | (n2 n1) → (результат) | n2 И n1 |
| or | (n2 n1) → (результат) | n2 ИЛИ n1 |
При выполнении вычислений на стеке часто возникает необходимость изменять порядок следования элементов, удалять значения, копировать их и т.д.
| Операция | Стэковая диаграмма | Описание |
|---|---|---|
| drop | (n1) → () | Удаляет элемент на вершине стека |
| swap | (n2 n1) → (n1 n2) | Меняет местами два элемента на вершине стека |
| dup | (n1) → (n1 n1) | Дублирует элемент на вершине стека |
| over | (n2 n1) → (n1 n2 n1) | Копирует предпоследний элемент на вершину стека |
| rot | (n3 n2 n1) → (n1 n2 n3) | Меняет местами первый и третий элемент от головы стека |
| depth | (...) → (n ...) | Возвращает число элементов в стеке перед своим вызовом |
Пусть слово define word начинает определение слова word. В теле определения (словарной статьи) следуют слова, которые надо вычислить, чтобы вычислить слово word. Статья заканчивается словом end. Определенное таким образом слово может быть использовано в программе так же, как и встроенное. Завершить выполнение процедуры до достижения её окончания end можно с помощью слова exit.
В статьях допускаются рекурсивные определения. Вложенные словарные статьи не допускаются. Конструкции if...endif или if...else..endif могут быть вложенными.
| Операция | Стэковая диаграмма | Описание |
|---|---|---|
| define word | () → () | Начинает словарную статью — определение слова word |
| end | () → () | Завершает статью |
| exit | () → () | Завершает выполнение процедуры (кода статьи) |
| if | (флаг) → () | Если флаг не равен 0, то выполняется код в теле if..endif, иначе выполняется код в теле else...endif |
| endif | () → () | Завершает тело if или else |
| else | () → () | Открытвает тело else |
| clear word | () → () | Удаляет последнее объявление статьи word |
| variable name | (value) → () | Добавляет значение value новой переменной name в словарь |
| set name | (value) → () | Изменяет значение переменной name на value |
В составе интерпретатора определена главная процедура, которая обрабатыват каждое слово программы, состояние интерпретатора описывают аргументы этой процедуры: вектор слов, счетчик слов (индекс текущего слова), стек данных, стек возвратов и словарь статей (ассоциативный список), словарь переменных (ассоциативный список).
Главная процедура классифицирует слово, на которое указывает счетчик, и интерпретирует его как число или слово (определенное в программе или встроенное). Встроенные слова принимают состояние интерпретатора и возвращают его измененным согласно семантике слова. Изменяться могут счетчик, стек данных, стек возвратов и словарь.
Если в программе встречается определение статьи, то в словарь помещается новое слово (ключ) и индекс первого слова в статье (значение). При вызове такой статьи в стек возвратов помещается индекс слова, следующего за вызовом. Он будет снят с вершины стека и возвращен в качестве значения счетчика слов при возврате из статьи (слова end и exit). Такой подход позволяет интерпретировать вложенные и рекурсивные вызовы.
Определение и вызов глобальных переменных, находящихся в отдельном пространстве имен, по принципу работы фактически являются частными случаями определения и вызова статей, однако реализованы, как отдельная механика. При определении переменной в словарь помещается новое название переменной и её значение. При вызове переменной на стэк кладется её значение.
Примеры программ можно посмотреть тут.