Главная » Хабрахабр » [Из песочницы] Lisp со вкусом Pascal или 8501-й язык программирования

[Из песочницы] Lisp со вкусом Pascal или 8501-й язык программирования

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

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

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

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

Недостатки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Численные литералы
Это наиболее полезное для меня расширение языка. 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. В Лисе каждый символ связан только с одним значением. Один символ может одновременно хранить переменную, функцию и список свойств.

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

(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, налагаются требования отсутствия побочных эффектов и независимости результата от внешних факторов.

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

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

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

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

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

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

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

Отброшенные

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

Управляемая комбинация методов
При вызове метода для класса выполняется комбинация методов родителей и существует возможность изменять правила комбинации. 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.

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

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

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

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

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

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

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

1. Консоль

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

Заключение

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Несостоявшийся полёт на Луну: что рассказывает неизвестная ранее запись советской миссии «Зонд-6»

Мы уже писали о том, как учёные оцифровали архив переговоров американских астронавтов с командным центром. Теперь услышать можно и звук с советских космических кораблей. Этот аппарат был прототипом корабля, на котором советских космонавтов хотели отправить на Луну. Британская обсерватория Джодрелл-Бэнк ...

Как устроен Heisenbug

Под одной крышей собрались не только тестировщики, но ещё и программисты, специалисты по автоматическому и нагрузочному тестированию, менеджеры команд и все остальные, для кого тестирование является важнейшей частью жизни. Совсем недавно прошёл Heisenbug 2018 Moscow. Фотки в действительно хорошем качестве ...