Кожура. Интерпретатор диалекта Lisp

Программирование - Практика программирования

Игрушечная реализация интерпретатора диалекта языка Лисп. Без претензий на практическую ценность.

(Функция Привет (Читатель) (Сообщить (+ "Привет, " Читатель "!")))

На днях мне пришла в голову мысль попробовать написать интерпретатор Лиспа на языке 1С. Сделать это оказалось даже проще чем думалось. Изделие носит гордое название "Кожура".
До полноценного Лиспа конечно далеко, но знаменитая гибкость этого языка позволяет расширять интерпретатор новым функционалом буквально за 5 минут. А если добавить поддержку макросов, то новый функционал (синтаксические конструкции) можно будет реализовать на самой Кожуре без правок интерпретатора.

(+ Всё есть список)

Кожура - это диалект и никаким стандартам не следует. По сему кратко опишу этот мини-язык.
Если вы не знакомы с языками семейства Lisp, то ничего страшного. Поверьте, они очень просты.
Давайте разберемся на примере Кожуры.

Программа на Кожуре - это один большой односвязный список. Да, именно так как написано! Программа - это данные и наоборот.
Элемент списка на языке 1С определен так:

Новый ФиксированнаяСтруктура("Тип, Данные, Следующий", Тип, Данные, Следующий);

Поле Тип может содержать следующие значения:

  • "Объект" - это значит что элемент содержит идентификатор (любое слово кроме чисел и строк)
  • "Число" - любое число
  • "Строка" - любая строка в двойных кавычках
  • "Список" - фиксированная структура (первый элемент другого списка)

Поле Данные содержит либо текст слова из исходного кода, который соответствует элементу, либо фиксированную структуру (если тип элемента "Список").

Поле Следующий содержит либо фиксированную структуру (следующий элемент в списке), либо Неопределено.

Например, следующая программа на Кожуре:

(+ 1 2)

может быть записана на языке 1С так:

Программа = Новый ФиксированнаяСтруктура("Тип, Данные, Следующий",
	"Объект",
	"+",
	Новый ФиксированнаяСтруктура("Тип, Данные, Следующий",
		"Число",
		"1",
		Новый ФиксированнаяСтруктура("Тип, Данные, Следующий",
			"Число",
			"2",
			Неопределено
		)
	)
)

или с использованием вспомогательной функции так:

Функция Список(Знач Тип, Знач Данные, Знач Следующий)
	Возврат Новый ФиксированнаяСтруктура("Тип, Данные, Следующий", Тип, Данные, Следующий);
КонецФункции // Список()

Программа = Список("Объект", "+", Список("Число", "1", Список("Число", "2", Неопределено)));

Превращение исходного кода на Кожуре в такой вот список (ну или дерево структур) - это первый этап работы интерпретатора. Разбор исходного кода тривиален. Список начинается с открывающей скобки и заканчивается закрывающей скобкой. Элементами списка могут быть идентификаторы, числа, строки и списки. Разделяются элементы любыми пробельными символами. Идентификаторы не могут начинаться с цифры и двойной кавычки, но при этом могут содержать символы: _=+-*/<>%!?

После построения списка-программы начинается его обход и выполнение.

(Функция Бесконечность Бытия (Бесконечность Бытия))

Процесс интерпретации тоже тривиален. Первый элемент списка считается функцией (встроенной или пользовательской). Остальные элементы считаются аргументами.

Встроенные функции можно условно разделить на два вида:

  • Примитивы - в Кожуре это функции: +, -, /, *, %, >, <, <=, >=, =, <> (аналогичны 1С, но принимают произвольное число аргументов)
  • Особые формы - в Кожуре это функции: Функция, Если, Сообщить

Интерпретатор смотрит на первый элемент списка и определяет встроенная это функция или пользовательская. Если встроенная, то вызывается встроенный механизм вычисления. Каждый аргумент при этом вычисляется рекурсивно тем же способом. Интерпретатор - это по сути рекурсивный диспетчер функций.

Процесс вычисления примитивов довольно очевиден. Немного магической может показаться только интерпретация определения функции и ее параметров.

(Функция Глобальная X (Функция Локальная Y (+ X Y)) (Локальная 1))

Что происходит когда интерпретатор встречает данное определение?

Сначала он распознает встроенную функцию Функция и понимает, что это определение. Затем распознает имя "Глобальная", параметр "Х" и остальные элементы списка как тело функции (выражение). Эту информацию интерпретатор помещает в текущее окружение.

Окружение (контекст, скоп) определено на языке 1С так:

Окружение = Новый Структура("ВнешнееОкружение, Элементы", ВнешнееОкружение, Новый Соответствие);

Для глобального окружения "ВнешнееОкружение" равно Неопределено.

Распознанная функция помещается в окружение так:

Окружение.Элементы[Имя] = Список("Функция", Параметры, Выражение);

Если интерпретатор встречает вызов пользовательской функции, то смотрит в окружение и извлекает из него параметры с телом функции. Затем создает новое локальное окружение, вычисляет аргументы и помещает значения в это окружение по именам параметров (по порядку). Далее значения параметров извлекаются как только будут встречены в теле функции. После вычисления функции локальное окружение уничтожается. Для вложенных функции происходит все то же самое рекурсивно. Но происходит это только тогда, когда интерпретатор встретит вызов родительской функции.

(Функция Это Всё? (Если Всё? ("Заканчивай") (Это Всё?)))

В целом да. Есть еще некоторые детали определения функций, но в данной статье обойдемся без них.
Исходный код находится по адресу: https://github.com/tsukanov-as/kojura
Там же есть ссылка на чат для обсуждений.

Приведу несколько примеров программ на Кожуре:

"Примитивы"
(* 1 2 3 4 5)
(/ 8 2 4)
(+ "Привет " "мир")
(> 3 2 1)


"Вычисление по условию"
(Функция Максимум (А Б)
    (Если (> А Б)
		(А)
		(Б)))
(Максимум 3 10)


"Рекурсивное вычисление"
(Функция Факториал! n
   (Если (= n 0)
       1
       (* (Факториал! (- n 1)) n)))
(Факториал! 100)


"Функция с одним параметром"
(Функция Инкремент Параметр (+ Параметр 1))
(Инкремент 2)


"Функция с двумя параметрами"
(Функция Сумма (Параметр1 Параметр2) (+ Параметр1 Параметр2))
(Сумма 2 2)


"Функция с двумя параметрами и промежуточным выражением"
(Функция Сумма (Параметр1 Параметр2)
	(Сообщить "Параметры функции:" Параметр1 Параметр2)
	(+ Параметр1 Параметр2))
(Сумма 2 2)


"Функция с вложенной функцией"
(Функция Сумма-квадратов (Параметр1 Параметр2)
	(Функция Квадрат Параметр1 (* Параметр1 Параметр1))
	(+ (Квадрат Параметр1) (Квадрат Параметр2)))
(Сумма-квадратов 2 3)

 

Выглядит обработка так:

ps Интепретатор писать было легче чем статью... :)

Скачать файлы

Наименование Файл Версия Размер
Кожура.epf
.epf 9,01Kb
10.02.18
0
.epf 9,01Kb Скачать

См. также

Комментарии
1. Александр Цуканов (tsukanov) 101 11.02.18 14:06 Сейчас в теме
После написания статьи добавлена поддержка лямбд (анонимных функций) и конструкции Выбор (аналог выбора в запросах).
Примеры можно посмотреть тут: https://github.com/tsukanov-as/kojura/blob/master/test.jur
2. Александр Цуканов (tsukanov) 101 11.02.18 18:16 Сейчас в теме
Добавил примитивную поддержку работы со списками и написал ридми: https://github.com/tsukanov-as/kojura/blob/master/README.md
Больше пока ничего с этим делать не планирую.
3. Николай Зевеке (zekrus) 153 14.02.18 08:01 Сейчас в теме
Доброе утро!
Тема весьма актуальная.
Есть аналог тут: http://www.gendoc.ru/
С уважением
4. Валентин Бомбин (so-quest) 129 14.02.18 09:13 Сейчас в теме
5. Александр Цуканов (tsukanov) 101 14.02.18 09:16 Сейчас в теме
(4) Вау, плохо я гуглил однако )
6. Петр Малыгин (pm74) 61 14.02.18 09:21 Сейчас в теме
(4) на оф выглядит эффектнее
зачем убрали подсветку синтаксиса в уф непонятно

упс. глупость написал
вобще круто и там и тут
7. Александр Цуканов (tsukanov) 101 14.02.18 09:30 Сейчас в теме
(4) А исходники этого чуда техники есть где-то?
8. Валентин Бомбин (so-quest) 129 14.02.18 09:32 Сейчас в теме
9. Александр Цуканов (tsukanov) 101 14.02.18 09:35 Сейчас в теме
(8) Спасибо, прикольно. Посмотрю вечером как реализовано
11. Дмитрий Бардасов (18101986) 33 27.02.18 21:55 Сейчас в теме
Интересно где это может пригодиться?
12. Александр Цуканов (tsukanov) 101 27.02.18 22:13 Сейчас в теме
(11) Вы видели в самом начале "Без претензий на практическую ценность"?
13. Денис Будяк (user930656) 07.03.18 12:10 Сейчас в теме
А я два года писал некое подобие 1С на лиспе, правда, на данный момент не осилил.

http://программирование-по-русски.рф/
https://bitbucket.org/budden/iar
Оставьте свое сообщение