Lisp со вкусом Pascal или 8501-й язык программирования

Некоторое время назад (года три) решил почитать учебник по Лиспу. Без всякой конкретной цели, просто ради общего развития и возможности шокировать собеседников экзотикой (один раз кажется, даже получилось).

Но при ближайшем рассмотрении Лисп оказался действительно мощным, гибким и как, ни странно, полезным в «быту». Все мелкие задачи автоматизации быстро перекочевали в скрипты на Лиспе, а так же появились возможности для автоматизации более сложной.

Здесь стоить отметить, что под «возможностью автоматизации» я подразумеваю ситуацию, когда суммарное время на написание и отладку программы меньше, чем время, затрачиваемое на решение той же задачи вручную.

Пол Грэм написал не одну статью и даже книгу о преимуществах Лиспа. На момент написания этой статьи Lisp занимает 33-е место в рейтинге TOIBE (в три раза мертвее мёртвого Delphi). Возникает вопрос: почему язык так мало распространён если он так удобен? Приблизительно два года использования дали несколько намёков на причины.

Недостатки

1. Разделяемые структуры данных
Концепция, позволяющая оптимизировать функциональные программы, но чреватая трудноуловимыми ошибками в императивных. Возможность случайного повреждения посторонней структуры данных при модификации переменной, не имеющей видимой связи со структурой, требует от программиста постоянного контроля происходящего за кулисами и знания внутренней реализации каждой используемой функции (и системной, и пользовательской). Самое удивительное — это возможность повредить тело функции, модификацией её возвращаемого значения.

2. Отсутствие инкапсуляции
Понятие пакета хотя и существует, но не имеет ничего общего с package в Ada или unit в Delphi. Любой код может добавить что угодно в любой пакет (кроме системных). Любой код может извлечь что угодно из любого пакета, используя оператор ::.

3. Бессистемные сокращения
Чем отличается MAPCAN от MAPCON? Почему в SETQ, последняя буква Q? С учётом возраста языка можно понять причины такого состояния дел, но хочется языка немного почище.

4. Многопоточность
Этот недостаток косвенно относится к Лиспу и, в основном, касается используемой мной реализации — SteelBank Common Lisp. Стандартом Common Lisp многопоточность не предусмотрена. Попытка использования реализации, предоставляемой SBCL, к успеху не привела.

Отказываться от такого удобного инструмента жалко, но неудовлетворённость постепенно накапливается.

Поиск решения

Сначала можно зайти на Википедию на страницу Лиспа. Осмотреть раздел «Диалекты». Прочитать краткое введение к каждому. И осознать, что на вкус и цвет все фломастеры разные.

Если хочешь что-то сделать, нужно это делать обязательно самому
— Жан Батист Эммануэль Зорг

Попробуем создать свой правильный Лисп, добавив в него немного Ады, много Delphi и совсем каплю Оберона. Назовём полученную смесь Лися.

Основные концепции

1. Никаких указателей
В рамках борьбы с ПРОБЛЕМОЙ-1 все операции должны производиться путём копирования значений. По виду структуры данных в коде или при выводе на печать должны быть полностью видны все её свойства, внешние и внутренние связи.

2. Добавим модули
В рамках борьбы с проблемой-2 импортируем из Ады операторы package, with и use. В процессе, отбросим избыточно сложную схему импорта/затенения символов Лиспа.

(package имя-пакета (список экспортируемых символов)
	(реализации)
	(функций))

(with имя-пакета) ;поиск файла «имя-пакета.lisya» и импорт содержимого

(use имя-пакета)  ;аналогично, но символы импортируются без имени пакета 

3. Меньше сокращений
Наиболее частые и общеупотребительные символы всё равно будут с сокращениями, но преимущественно наиболее очевидные: const, var. Функция форматированного вывода — FMT требует сокращения, поскольку часто встречается внутри выражений. Elt — взятие элемента — просочился из Common Lisp и прижился, хотя необходимости в сокращении нет.

4. Регистронезависимые идентификаторы
Я считаю, что правильный язык (и файловая система) {$HOLYWAR+} должен быть регистронезависимым {$HOLYWAR-}, чтобы не ломать лишний раз голову.

5. Удобство использования с русской раскладкой клавиатуры
Синтаксис Лиси всячески избегает использования символов, недоступных в одной из раскладок. Нет квадратных и фигурных скобок. Нет #, ~, &, <, >, |. При чтении численных литералов правильными десятичными разделителями считаются как запятая, так и точка.

6. Расширенный алфавит
Одной из приятных черт SBCL оказался UTF-8 в коде. Возможность объявлять константы МЕДВЕДЬ, ВОДКА и БАЛАЛАЙКА значительно упрощает написание прикладного кода. Возможность вставлять Ω, Ψ и Σ делает формулы в коде наглядней. Хотя теоретически существует возможность использовать любые символы юникода, гарантировать корректность работы с ними сложно (скорее лень, чем сложно). Ограничимся кириллицей, латиницей и греческим.

7. Численные литералы
Это наиболее полезное для меня расширение языка.

10_000 ;разделители разрядов для удобочитаемости
10k ;десятичные приставки для целых и дробных чисел
10к ;русские десятичные приставки для минимизации переключений раскладки
10° 10pi 10deg 10гр ;не десятичные приставки
10π ;приставка pi в более эстетичном варианте
10+i10 ;литерал комплексного числа 
10+м10 ;ещё раз комплексное число 
10а10deg ;литерал комплексного числа в показательной форме с аргументом в градусах

Последний вариант мне кажется самым не эстетичным, но он самый востребованный.

8. Циклы
Циклы в Лиспе нестандартны и изрядно запутаны. Упростим до минимального стандартного набора.

(for i 5  
	;повторить пять раз i = 0..4
	)
(for i 1..6 
	 ;повторить пять раз i = 1..5
	)
(for i список 
	 ;повторить для каждого элемента списка 
	;допускается присваивание нового значения переменной цикла
)
(for i (subseq список 2) 
	 ;повторить для элементов списка начиная со второго элемента и до конца
	)

Переменная цикла за его пределами не видна.

(while условие
	)

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

(block
	:метка
	(goto :метка)) ;этот блок кода иногда зависает

10. Унификация областей видимости
В Лиспе есть два различных типа областей видимости: TOPLEVEL и локальная. Соответственно есть два разных способа объявления переменных.

(defvar A 1)
(let ((a 1)) …)

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

(var A 1)

При необходимости ограничить область видимости используется оператор

(block 
	(var A 1)
	(set A 2)
	(fmt nil A))

Тело цикла содержится в неявном операторе BLOCK (как и тело функции/процедуры). Все объявленные в цикле переменные уничтожаются в конце итерации.

11. Однослотовость символов
В Лиспе функции являются особыми объектами и хранятся в специальном слоте символа. Один символ может одновременно хранить переменную, функцию и список свойств. В Лисе каждый символ связан только с одним значением.

12. Удобный ELT
Типичный доступ к элементу сложной структуры в Лиспе выглядит так

(elt (slot-value (elt структура 1) 'слот-2) 3) 

В Лисе реализован унифицированный оператор ELT, обеспечивающий доступ к элементам любых составных типов (списков, строк, записей, массивов байт, хэш-таблиц).

(elt структура 1 слот-2 3)

Идентичную функциональность можно получить и макросом на Лиспе

(defmacro field (object &rest f)
	"Извлекает элемент из сложной структуры по указанному пути.
	(field *object* 0 :keyword symbol "string")
	Каждый числовой параметр трактуется как индекс массива.
	Каждое ключевое слово трактуется как свойство в plist.
	Каждый символ (не ключевой) трактуется как функция доступа.
	Каждая строка трактуется как ключ в ассоциативном массиве."
	(if f 	(symbol-macrolet ((f0 (elt f 0))(rest (subseq f 1)))		
			(cond 
				((numberp f0) `(field (elt ,object ,f0) ,@rest))
				((keywordp f0) `(field (getf ,object ,f0) ,@rest))
				((stringp f0) `(field (cdr (assoc ,f0 ,object :test 'equal)) ,@rest))
				((and (listp f0) (= 2 (length f0)))
					`(field (,(car f0) ,(cadr f0) ,object) ,@rest))
				((symbolp f0) `(field (,f0 ,object) ,@rest))
				(t `(error "Ошибка форматирования имени поля"))))
		object))

13. Ограничение режимов передачи параметров подпрограмм
В Лиспе имеется, как минимум пять режимов передачи параметров: обязательные, &optional, &rest, &key, &whole и разрешена их произвольная комбинация. В действительности, большинство комбинаций дают странные эффекты.
В Лисе разрешено использовать только комбинацию из обязательных параметров и одного из следующих режимов на выбор :key, :optional, :flag, :rest.

14. Многопоточность
С целью предельного упрощения написания многопоточных программ, была принята концепция отделения памяти. При порождении потока все переменные, доступные новому потоку, копируются. Все ссылки на эти переменные заменяются ссылками на копии. Передача информации между потоками возможна только посредством защищённых объектов или через результат, возвращаемый потоком при завершении.

Защищённые объекты всегда содержат критические секции для обеспечения атомарности операций. Вход в критические секции осуществляется автоматически — отдельных операторов для этого в языке нет. К защищённым объектам относятся: очередь сообщений, консоль и файловые дескрипторы.

Создание потоков возможно многопоточной функцией отображения

(map-th (function (x) …) данные-для-обработки) 

Map-th автоматически запускает количество потоков, равное количеству процессоров в системе (или в два раза больше, если у вас Intel inside). При рекурсивном вызове, последующие вызовы map-th работают в один поток.

Дополнительно есть встроенная функция thread, выполняющая процедуру/функцию в отдельном потоке.

;пример асинхронного исполнения
(var поток (thread  длительные-вычисления-1))
(+ (длительные-вычисения-2) (wait поток))

15. Функциональная чистота в императивном коде
В Лисе есть функции для функционального программирования и процедуры для процедурного. На подпрограммы, объявленные с использованием ключевого слова function, налагаются требования отсутствия побочных эффектов и независимости результата от внешних факторов.

Нереализованное

Некоторые интересные возможности Лиспа остались не реализованными в силу низкого приоритета.

1. Обобщённые методы
Возможность выполнять перегрузку функций при помощи defgeneric/defmethod.

2. Наследование

3. Встроенный отладчик
При возникновении исключения интерпретатор Лиспа переключается в режим отладчика.

4. UFFI
Интерфейс для подключения модулей, написанных на других языках.

5. BIGNUM
Поддержка целых чисел произвольной разрядности

Отброшенные

Некоторые возможности Лиспа были рассмотрены и сочтены бесполезными/вредными.

1. Управляемая комбинация методов
При вызове метода для класса выполняется комбинация методов родителей и существует возможность изменять правила комбинации. Итоговое поведение метода представляется слабо предсказуемым.

2. Перезапуски
Обработчик исключения может внести изменения в состояние программы и послать команду перезапуска коду, сгенерировавшему исключение. Эффект от применения аналогичен использованию оператора GOTO для перехода из функции в функцию.

3. Римский счёт
Лисп поддерживает систему счисления, которая устарела незадолго до его появления.

Использование

Приведу несколько простых примеров кода

(function crc8 (data :optional seed)
    (var result (if-nil seed 0))
    (var s_data data)

    (for bit 8
        (if (= (bit-and (bit-xor result s_data) $01) 0)
            (set result (shift result -1 8))
        (else
            (set result (bit-xor result $18))
            (set result (shift result -1 8))
            (set result (bit-or result $80))))
        (set s_data (shift s_data -1 8)))
    result)

;поэлементное возведение списка в квадрат
(map (function (x) (** x 2)) (1 2 3))

;извлечение из списка строк, начинающихся с qwe и длиной более пяти символов
(filter (function (x) (regexp:match x «^qwe...»)) список-строк)

;но если строк много, а процессор шестиядерный, то лучше так
(filter-th (function (x) (regexp:match x «^qwe...»)) список-строк)

Реализация

Интерпретатор написан на Delphi (FreePascal в режиме совместимости). Собирается в Lazarus 1.6.2 и выше, под Windows и Linux 32 и 64 бита. Из внешних зависимостей требует libmysql.dll. Содержит около 15_000..20_000 строк. Имеются около 200 встроенных функций различного назначения (некоторые перегружены по восемь раз).

Хранится здесь

Поддержка динамической типизации выполнена тривиальным образом — все обрабатываемые типы данных представлены наследниками одного класса TValue.

Важнейший для Лиспа тип — список является, как и принято в Delphi, классом, содержащим динамический массив объектов типа TValue. Для данного типа реализован механизм CopyOnWrite.

Управление памятью автоматическое на основе подсчёта ссылок. Для рекурсивных структур выполняется подсчёт всех ссылок в структуре одновременно. Освобождения памяти запускается сразу при выходе переменных из области видимости. Механизмы отложенного запуска сборщика мусора отсутствуют.

Обработка исключений работает на механизме встроенном в Delphi. Таким образом, ошибки, возникающие в коде интерпретатора, могут быть обработаны выполняемым кодом на Лисе.

Каждый оператор или встроенная функция Лиси реализован как метод или функция в коде интерпретатора. Выполнение скрипта осуществляется путём взаимно-рекурсивного вызова реализаций. У кода интерпретатора и скрипта общий стек вызовов.

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

Особую сложность представляет собой реализация оператора присваивания (set) для элементов структур. Непосредственное вычисление указателя на требуемый элемент приводит к риску появления висячих ссылок, поскольку синтаксис Лиси не запрещает модификацию структуры в процессе вычисления требуемого элемента. Как компромиссное решение реализован «цепочечный указатель» — объект, содержащий ссылку на переменную и массив числовых индексов для указания пути внутри структуры. Такой указатель так же подвержен проблеме висячих ссылок, но в случае сбоя генерирует осмысленное сообщение об ошибке.

Инструменты разработки

1. Консоль

2. Текстовый редактор
Оборудован подсветкой синтаксиса и возможностью запуска редактируемого скрипта по F9.

Заключение

В текущем состоянии проект решает те проблемы, ради которых затевался, и не требует дальнейшей активной доработки. Множество присутствующих недоделок не оказывают существенного влияния на работу.

Автор: andrey_ssh

Источник