Разработка интерпретатора LISP

Барабаш Константин Алексеевич студент кафедры компьютерных систем Казанского национального исследовательского технического университета им. А.Н.Туполева-КАИ 420015, Россия, республика Татарстан, г. Казань, ул. Большая Красная, 55 Barabash Konstantin Alekseevich Student, Computer Systems Department, Kazan National Research Technical University named after A.N.Tupolev-KAI 420015, Russia, Republic of Tatarstan, Kazan, Bolshaya Krasnaya str., 55 kostyandriy@mail.ru Другие публикации этого автора     Мангушева Алина Раисовна кандидат физико-математических наук доцент кафедры интеллектуальных систем и управления информационными ресурсами Казанского национального исследовательского технологического университета 420015, Россия, республика Татарстан, г. Казань, ул. Карла Маркса, 68 Mangusheva Alina Raisovna PhD in Physics and Mathematics Associate Professor, Department of Intelligent Systems and Information Resource Management, Kazan National Research Technological University 420015, Russia, Republic of Tatarstan, Kazan, Karl Marx str., 68 alinamr@mail.ru Обухова Маргарита Юрьевна старший преподаватель кафедры компьютерного моделирования и техносферной безопасности Казанского инновационного университета 420111, Россия, республика Татарстан, г. Казань, ул. Московская, 42 Obukhova Margarita Yur'evna Senior Lecturer, Department of Computer Modeling and Technosphere Safety, Kazan Innovative University 420111, Russia, Republic of Tatarstan, Kazan, Moskovskaya str., 42 obuhova@ieml.ru

Григорян Карен Альбертович кандидат экономических наук магистрант кафедры интеллектуальных систем и управления информационными ресурсами Казанского национального исследовательского технологического университета 420015, Россия, республика Татарстан, г. Казань, ул. Карла Маркса, 68 Grigoryan Karen Al'bertovich PhD in Economics Master's student, Department of Intelligent Systems and Information Resource Management, Kazan National Research Technological University 420015, Russia, Republic of Tatarstan, Kazan, Karl Marx str., 68 karigri@yandex.ru

Архитектура интерпретатора

Разработанный интерпретатор LISP имеет три основные подпрограммы: read, eval, print. Процедура read:

● Отвечает за считывание входных данных и их обработку – разложение на имена атомов, знаки препинания; введение новых обычных атомов в таблицу атомов и новых числовых атомов в таблицу чисел; создание S-выражения, представляющего входные данные. (Термин «атом» является историческим; этот термин использовал разработчик LISP Джон Маккарти.) ^{[1, 2]}

● Возвращает типизированный указатель на созданное S-выражение. При этом, если входное S-выражение не является атомом, в области списка будет создана соответствующая структура списка.

Типизированный указатель, созданный в качестве вывода read, затем передается в качестве входных данных подпрограмме eval. Процедура eval реализует функцию EVAL из LISP. eval интерпретирует вычисление S-выражения, на которое указывает его ввод, рекурсивно вызывая себя для вычисления подвыражений.

Конечным результатом является S-выражение, которое при необходимости создается в области списка, и в качестве вывода возвращается типизированный указатель на это результирующее S-выражение. Если входное S-выражение недопустимо, eval выводит сообщение об ошибке и переходит к точке, где вызывается read, чтобы получить дополнительные входные данные.

Если исходный ввод поддается оценке, вывод типизированного указателя из eval направляется в качестве ввода для записи. Процедура print собирает имена и знаки препинания, необходимые для формирования текстовой строки, представляющей заданное S-выражение, и печатает эту строку на терминале (см. рисунок 1) ^{[3, 4]}.

Рисунок 1. REPL

Таким образом, интерпретатор LISP имеет следующую форму.

1. Инициализация

2. o = read()

3. r = eval(o)

4. print(r)

5. перейти к шагу 2

Описание типов данных

Все типы данных представляются одной структурой l_object. Это сделано для возможности передавать любые объекты как аргументы для функций. Структура объекта выглядит следующим образом:

Листинг 1. Структура объекта

Поле class определяет класс объекта, сам класс, имеет тип данных класса, а его имя располагается в поле raw.s. Поле vars является таблицей символов и используется для хранения собственных переменных объекта. В случае пользовательской функции внутри vars создаются две переменные: args типа c_list и body типа c_list. Для встроенной функции или специальной формы в vars создается только args типа c_list, а ссылка на функцию указывается в raw.fn. Таблицу символов в свою очередь представляет следующая структура l_var, которая является обычным связным списком объектов, дополнительно содержащую поле name:

Листинг 2. Структура l_var

Инициализация

До начала работы интерпретатора все классы, функции и специальные формы должны быть проинициализированы. Инициализация классов происходит вызовом соответствующего метода init. В то время как стандартные функции и специальные формы должны быть добавлены в env отдельно.

Листинг 3. Структура l_var

Создание объектов

Класс создается с помощью функции new_class, которая возвращает объект класса. Функция принимает имя класса и таблицу символов класса. Для более удобной работы созданы доп функции, возвращающие необходимые объекты: list, raw_fn, fn, raw_spec, spec, object и т. д.

Листинг 4. Структура класса c_int

Если функция написана на языке C, то создать такой объект можно при помощи raw_fn. Первым аргументом передается список аргументов получаемых функцией, вторым передается адрес на нее.

Листинг 5. Описание встроенного метода plus для класса c_int

Если в функцию придет больше аргументов чем в списке аргументов, то все остальные будут автоматически записаны в переменную под именем “&rest” хранящую лист оставшихся переменных.

Чтение S-выражений

Данная процедура сканирует входную строку посредством чтения следующего символа, и возвращает:

● NULL если символ равен “)”;

● результат выполнения parse_list если символ равен “(”;

● результат выполнения parse_quote если символ равен “””;

● результат выполнения parse_string если символ равен “‘“;

● результат выполнения функции parse_token.

В любых иных случаях read создает S-выражение ^[5], соответствующее входной строке, и возвращает в качестве результата указатель на нее.

Листинг 6. Функция чтения S-выражений

Исполнение

Для исполнения объект, полученный после этапа чтения, передается в функцию eval.

Листинг 7. Функция eval

Листинг 8. Функция exec

Функция eval работает следующим образом:

● Если eval получает лист, то тогда, согласно правилам, вызывается eval сначала для первого элемента списка.

● Если результатом будет специальная форма, то eval не вызывается для остальных элементов, а в форму передаются все последующие значения листа.

● Если eval получает символ, то в окружении по имени ищется объект и возвращается. Если объект не найден, то создается переменная с именем символа и с объектом типа “c_undefined”.

Во всех остальных случаях возвращается сам объект.

Сборка мусора

Так как S-выражения поступают в интерпретатор LISP для оценки, то различные структуры в области списка создаются либо на основе ввода, либо на основе оценки. Большинство этих структур списка используются единожды. Такие структуры называются мусорными объектами. А в случае узлов области списка мусорными узлами являются те, которые недоступны.

Нам нужно найти такие бесполезные узлы списка и поместить их в список свободного пространства области списка, чтобы их можно было использовать повторно; в противном случае у нас закончится память области списка. Каждый раз, когда при пересчете числа ссылок на объект получаем нуль, то данный объект удаляется из памяти.

Листинг 9. Функция new_object

Для сбора мусора используется метод подсчета ссылок. Он заключается в том, что каждый объект подсчитывает количество указателей на него. Когда есть указатель на себя, значение счетчика увеличивается на 1; когда указатель на себя удаляется, значение счетчика уменьшается на 1, если значение счетчика уменьшается до 0, что указывает на отсутствие указателя на объект, то его можно безопасно уничтожить. Это можно представить в виде следующего рисунка:

Рисунок 2. Иллюстрация работы счетчика сборщика мусора

Преимущество алгоритма подсчета ссылок заключается в том, что накладные расходы на управление памятью распределяются по всему периоду работы приложения. Также преимущество связно с тем, что когда значение счетчика ссылок объекта становится равным 0, системе не нужно обращаться к блокам, расположенным на других страницах в куче.

Примеры работы отдельных частей интерпретатора

Для демонстрации работы интерпретатора приведем несколько примеров. В листингах будут указаны результаты работы функции через комментарии вида “;; =>”, после которого будет указано возвращаемое значение.

Приведем пример функции факториала:

Листинг 10. Функция вычисления факториала

Пример, демонстрирующий работу в стиле объектно-ориентированного программирования (ООП). Опишем класс “Человек”. “Человек” имеет метод взросления, который прибавляет к его годам 1, также имеет метод изменения уровня счастья:

Листинг 11. Пример ООП

По сравнению с Common lisp, данная реализация языка имеет более интуитивный синтаксис. В листинге 11 код, написанный на LISP, противопоставляется коду на языке Common lisp (листинг 12). Как видим, новому пользователю не придется запоминать большое количество функций выполняющих схожие действия, что в совокупности с динамической типизацией добавляет гибкости.

Листинг 12. Сравнение. Код на данной реализации LISP

Листинг 13. Сравнение. Код Common lisp

Также можно переопределить функции для использования со своим классом, например для смешивания цветов (листинг 14). Это сделает LISP более удобным для конечного пользователя. Если бы данная реализация LISP не позволяла переопределять функции, то это было бы проблемой, ведь стандарта в названиях нет и они могут отличаться от библиотеки к библиотеке. Например, функция сложения цветов могла бы называться следующими именами: mixcolor, add-color, color-add, color+ и т.д.

Листинг 14. Класс color

Следующий пример демонстрирует работу макросов LISP. Здесь (листинг 15) имеется макрос n+, он принимает один аргумент n и объявляет глобальную функцию, которая принимает один аргумент x и прибавляет к нему n.

Листинг 15. Макрос n+

Апробация разработанного интерпретатора

В качестве демонстрации работы интерпретатора представим реализацию игры “Жизнь”. Опишем суть данной игры.

Место действия – плоскость, размеченная на клетки, которая может быть замкнутой, ограниченной или бесконечной. У каждой клетки есть восемь соседей, окружающих её, и она может быть в двух состояниях: клетка либо “жива”, либо "мертва”. Живые клетки, которые стоят в начале игры, называются первым поколением. Каждое последующее поколение строится на основе предыдущего по правилам:

● для “мертвой” клетки: если живых соседей не меньше трех, то клетка становится “живой”;

● для “живой” клетки: если живых соседей два или три, то клетка продолжает жить, а в иных случаях умирает.

Игра прекращается, когда на поле не остается ни одной живой клетки. Несмотря на простоту правил, в игре может возникать огромное разнообразие форм.

Определим вспомогательные функции, которые реализуют некоторые существующие функции LISP. Функция map вызывает переданную ей функцию для всех элементов листа. Nth возвращает n-ный элемент с начала листа, в то время как nth-tail возвращает n-ный элемент с конца.

Листинг 16. Реализация дополнительных функций

Далее описываются функции для работы с полем. Get возвращает символ, находящийся по координатам x и y на поле. Alive возвращает булево значение состояния клетки. Print печатает поле. Count возвращает количество живых клеток, находящихся вокруг данной клетки. Next в зависимости от текущего состояния поля возвращает значение клетки на следующий ход.

Листинг 17. Вспомогательные функции

Функция запуска представляет собой циклический перебор по всем клеткам и выявление их состояния на следующий ход.

Листинг 18. Функция запуска

Определим стартовое поле в виде колонии (листинг 19). Данная конструкция называется планером, так как способна перемещаться бесконечно далеко. В данном случае, так как границы мира ограничены, планер остановится в углу, где приобретет стабильную форму в виде квадрата.

Листинг 19. Колония 1

Рисунок 3. Эволюция колонии 1

Существуют формы колоний, которые способны изменяться бесконечно. Самым простым примером такой формы является прямая линия, состоящая из трех элементов в ряд.

Листинг 20. Колония 2

Результатом жизни такой колонии является циклическая смена вертикального положения на горизонтальное и наоборот.

Рисунок 4. Эволюция колонии 2

Заключение

По результатам проделанной работы создан интерпретатор языка LISP на языке C, упрощающий написание программ посредством более простого синтаксиса с возможностью перегрузки функций. На примере реализованного игрового приложения “Жизнь” язык разработанного интерпретатора продемонстрировал более упрощённый стиль написания программы. Также в работе дан посыл для развития языка LISP посредством включения языковых конструкций, обеспечивающих объектно-ориентированные подходы программирования.

Таким образом, коллектив авторов создал фундамент для дальнейшего развития языка LISP и рассматривает предметом дальнейших работ по применению и модернизации интерпретатора в целях создания программного обеспечения в таких предметных областях, как нейронные сети в промышленной индустрии ^[6], параллельное программирование ^[7], защита информации ^{[8, 9]}.