Лисп — философия разработки

Всеволод Дёмкин, Александр Манзюк

Аннотация:

В статье исследуются подходы к разработке, практикуемые в Лисп-среде, на примерах решения различных прикладных задач на языке Common Lisp. Вы узнаете о том, что макросы — это не только синтаксический сахар, но и прекрасный инструмент инкапсуляции, что кроме глобальных и локальных переменных бывают еще специальные, что полиморфные интерфейсы можно создавать без привязки к классам, а также о том, что определять стратегии передачи управления можно не только с помощью монад. Рассмотрены и решения прикладных задач: клиент для хранилища данных Redis, прокси между двумя бизнес-приложениями, внутренний API веб-сервиса, библиотека парсерных комбинаторов.


The article describes the development techniques used in the Lisp environment, illustrated by solving several practical tasks in Common Lisp. You will discover that macros are not only syntactic sugar, but also a way to provide incapsulation; that besides local and global variables there are also special ones; that polymorphic interfaces can be defined without any relation to classes; and that monads are not the only way to model computation control. Examples are drawn from real-world codebases: a client for Redis persistent key-value database, a proxy linking two business applications, and internal API of a web service, and a parser combinator library.



Обсуждение статьи ведется в LiveJournal.

1  Кратко о Common Lisp

Common Lisp — это язык, который появился в 80-х годах как попытка объединить многочисленные разрозненные реализации концепции Лиспа, а также задействовать последние на тот момент достижения в области языков программирования. Вероятно, на сегодняшний момент он является наиболее используемым на практике Лиспом.

Его основные характеристики:

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

Динамичность подразумевает динамическую типизацию с возможностью явного объявления типов. Кроме того она означает представление программы в виде живого образа (live image), в котором любой объект, за исключением 25 базовых операторов языка, может быть переопределен в ходе исполнения теми же средствами, что и в момент его создания. Наконец, динамичность поддерживается полноценными возможностями интроспекции.

Синтаксис этого языка — это единообразная префиксная нотация (S-выражения). Вот простейший пример Лисп-кода: (defun sum (a b) (+ a b)), эквивалентом которого в языке Алгол-семейства был бы function sum(ab) { return a + b; }. Благодаря этому исходный код гомоморфен синтаксическому дереву, используемому компилятором. Языки, обладающие таким свойством, называются также гомоиконными языками.

Программируемость подразумевает возможность добавлять к языку собственные дополнения, которые будут на равных правах сосуществовать со стандартными языковыми средствами. Это подкреплено тем, что в отличие от большинства других платформ, в Лисп-среде программисту дается возможность влиять (одними и теми же средствами языка) на все три этапа существования программы: синтаксический разбор, компиляцию и исполнение, а не только на самый последний этап — исполнение.

Среди других Лиспов его также характеризуют:

Исторически Common Lisp развивался в сообществе исследователей искуственного интеллекта, поэтому широко распространен в различных экспертных системах, CAD/CAM системах и в научной среде. Однако, этим отнюдь не ограничивается сфера его применения — скорее наоборот, сейчас Лисп больше развивается в других областях. Примерами удачного использования Common Lisp являются высоконагруженная система расчета цен на авиабилеты QPX, вдохновивший многие Интернет-проекты, один из первых веб-сервисов Viaweb, а также сервис централизованного администрирования компьютеров Paragent.com.

Наконец, нужно сказать, что Лисп всегда был источником, из которого черпались идеи для других языков1. Среди этих идей — автоматическое управление памятью, REPL, интроспекция, замыкания и функции высших порядков. На данный момент может показаться, что этот процесс остановился, однако, по моему мнению, это не совсем так: ведь в Лиспе остается еще много уникальных решений. Свидетельством того, что он продолжает вдохновлять разработчиков других языков программирования, являются, например, работа Реджинальда Брайтвайта в рамках Ruby или Ола Бини над Ioke, не говоря уже о новом языке для виртуальной машины Java — Clojure.

Это, конечно, не значит, что миру Лиспа нечему поучиться у других языков — наоборот. И, что как раз демонстрирует язык Clojure, этот процесс впитывания достижений из других областей идет очень активно. Стоит отметить, что благодаря своей гибкости Лисп всегда был отличным выбором для адаптации и тестирования новых идей.

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

Первые разделы предполагают минимальное знакомство с языком, но с каждым разделом сложность демонстрируемого кода возрастает, и последние два раздела требуют определенного концептуального понимания, которое можно почерпнуть, например, из книги [7]. Эта часть статьи должна быть прежде всего интересна тем, кто уже имеет существенный опыт программирования на Лиспе или же функциональных языках.

2  Код или данные?

Классической моделью создания больших систем в рамках Лиспа является итеративная разработка, ставящая себе целью постепенное «сближение» программы с предметной областью. Она включает в себя такие подходы, как метапрограммирование, т. е. программирования самого языка; проблемно-ориентированное программирование, подразумевающее адаптацию языка к предметной области; и, наконец, т. н. разработка «от данных» (data-driven design).

Широко известна максима Лиспа, выражающая суть метапрограммирования: «код — это данные». Она означает, что саму программу можно рассматривать в виде данных, с которыми можно и нужно работать точно так же, как и с любыми другими.

Обратное также верно: «данные — это код», ведь представление данных играет немаловажную роль в логике программы. В этой формулировке – суть подхода к разработке «от данных».

Посмотрим, как же это все применяется на практике.

2.1  Практический пример: клиент для Redis

Redis — это одна из новых баз данных нереляционного типа, которая по сути представляет собой персистентную хеш-таблицу. Кроме того в ней поддерживается работа с данными как со списками, множествами и отсортированными множествами (единственное, что не поддерживается — это вложенность этих структур). Эти базовые структуры данных являются родными и для Лиспа, поэтому Redis выглядит очень естественным дополнением к Лисп-среде. Единственный метод взаимодействия с сервером — низкоуровневый socket API. Соответственно, чтобы связать любой язык и Redis, необходимо реализовать клиент, который бы скрывал эти низкоуровневые аспекты за более абстрактным и удобным фасадом. Попробуем реализовать такой клиент на Лиспе.

С точки зрения пользователя такая библиотека должна давать ему возможность, вооружившись только базовыми знаниями языка и спецификацией команд Redis, взаимодействовать с сервером БД. Кроме того, в идеале, еще желательна возможность управлять в определенных пределах эффективностью такого взаимодействия.

С точки зрения разработчика стоят задачи сделать библиотеку:

  1. слабо связанной, чтобы при необходимости можно было вносить изменения в ее отдельные функциональные части, не затрагивая остальных;
  2. легко расширяемой. Redis — молодой проект, в котором часто происходят изменения. Например, начальная разработка клиента велась, когда актуальной была версия 0.9, а в текущей на момент написания статьи версии 1.1 по сравнению с ней появился новый тип взаимодействия с сервером, новая группа из десятка команд и две новых самостоятельных команды;
  3. легко поддающейся тестированию.

Если рассмотреть предметную область данной задачи, то можно выделить три уровня:

  1. нижний уровень управления соединением через socket API;
  2. средний уровень реализации протокола взаимодействия;
  3. верхний уровень пользовательских команд.

2.1.1  Реализация клиента

Именно так и структурирован исходный код библиотеки2.

В файле connection.lisp описывается способ установления соединения, реакции на сбои, а также более высокоуровневые конструкции, позволяющие управлять параметрами подключения. Эти конструкции реализованы в принятом в Лиспе with-шаблоне, при котором код, непосредственно выполняющий действие, с помощью макроса оборачивается в шаблонный код, выполняющий служебные задачи, такие как гарантированное освобождение ресурсов или иное восстановление исходного состояния, обработка ошибок, вывод отладочной информации и т. д. Например, следующий фрагмент кода открывает соединение к Redis на локальной машине по нестандартному порту 7000 и выполняет команды SELECT 1 и KEYS * (это и есть типичный клиентский код, который пишут пользователи библиотеки):

(with-connection (:port 7000) (red-select 1) (red-keys "*"))

Если посмотреть на него через macroexpand, можно увидеть, какие вспомогательные действия добавлены в этот вызов:

(LET ((*CONNECTION* (MAKE-INSTANCE 'REDIS-CONNECTION :HOST #(127 0 0 1) :PORT 7000 :ENCODING :UTF-8))) (UNWIND-PROTECT (PROGN (RED-SELECT 1) (RED-KEYS "*")) (CLOSE-CONNECTION *CONNECTION*)))

В файле redis.lisp реализуется протокол взаимодействия с сервером. Прочитав спецификацию протокола, можно заключить, что абстракцией, которая хорошо описывает взаимодействие с Redis, является модель запрос-ответ, что характерно для многих (но не всех) приложений, основанных на socket API. При этом синтаксис протокола описывает несколько способов отправить запрос и несколько вариантов форматирования ответа. На этом и построено ядро библиотеки. Методы на обобщённых функциях3 TELL и EXPECT реализуют конкретные способы взаимодействия в рамках протокола. Для выбора специфического метода используется его идентификатор: :inline, :bulk, :multi(-bulk), :integer и т. д. Пример вызова этих функций может выглядеть таким образом:

(tell :bulk 'set "key" "value") (expect :ok)

Дополнительно для функции EXPECT определена операция DEF-EXPECT-METHOD, которая создает новый метод, оборачивая его тело в одинаковый для большинства методов код. Этот код выполняет чтение и первичный разбор строки ответа, формирует очищенную от служебной информации строку в виде локальной переменной reply, а также содержит вызов функций отладки. Создание подобных шаблонов для обёртки методов — еще одна идея Лиспа, взятая на вооружение мейнстримными языками, и получившая в данном контексте название «аспектно-ориентированное программирование».

Итак, определения конкретных методов для TELL и EXPECT выглядят следующим образом.

(defmethod tell ((type (eql :bulk)) cmd &rest args) (multiple-value-bind (args bulk) (butlast2 args) (check-type bulk string) (write-redis-line "~A~{ ~A~} ~A" cmd args (byte-length bulk)) (write-redis-line "~A" bulk))) (def-expect-method :boolean (ecase (char reply 0) (#\0 nil) (#\1 t)))

и его макро-раскрытие:

(DEFMETHOD EXPECT ((TYPE (EQL :BOOLEAN))) "Receive and process the reply of type BOOLEAN." (LET* ((#:G1767 (READ-LINE (REDIS::CONNECTION-STREAM *CONNECTION*))) (#:G1768 (CHAR #:G1767 0)) (REDIS::REPLY (SUBSEQ #:G1767 1))) (WHEN *ECHO-P* (FORMAT *ECHO-STREAM* "S: ~A~%" #:G1767)) (CASE #:G1768 ((#\-) (ERROR 'REDIS-ERROR-REPLY :MESSAGE REDIS::REPLY)) ((#\+ #\: #\$ #\*) (ECASE (CHAR REPLY 0) (#\0 NIL) (#\1 T))) (OTHERWISE (ERROR 'REDIS-BAD-REPLY :MESSAGE (FORMAT NIL "Received ~C as the initial reply byte." #:G1768))))))

Наконец, в файле commands.lisp объявляются команды взаимодействия с сервером. В данном случае они реализованы в виде обычных функций, создание которых происходит программно, а определение — в полностью декларативном стиле на основании минимального набора необходимых данных: списка аргументов, идентификаторов методов отправки запроса и получения ответа, а также документирующей строки. Таким образом, объявление команды имеет вид, практически повторяющий ее описание в Redis Wiki:

(def-cmd SINTER (&rest keys) "Return the intersection between the Sets stored at key1, key2, ..., keyN." :inline :multi)

которое раскрывается в:

(PROGN (DEFUN RED-SINTER (&REST KEYS) "Return the intersection between the Sets stored at key1, key2, ..., keyN." (REDIS::WITH-RECONNECT-RESTART REDIS::*CONNECTION* (APPLY #'TELL :INLINE 'SINTER KEYS) (EXPECT :MULTI))) (EXPORT 'RED-SINTER :REDIS))

Возможны также альтернативные варианты реализации команд. Например, можно создать обобщённую функцию redis-command, которая бы принимала идентификатор команды и ее аргументы. Преимуществом такого подхода является единая «точка входа» для взамодействия с Redis, а также то, что мы воспользуемся наиболее простым способом расширения, заложенным в язык — обобщёнными функциями. Недостатки же — большая громоздкость вызовов и меньшая гибкость. Мы выбрали первый подход. Второй подход мы планируем добавить в будущих версиях библиотеки в качестве альтернативы. Пример успешного применения этого подхода также можно будет увидеть в разделе статьи, посвященной созданию интерфейсов.

2.1.2  Анализ предложенного решения

API любой библиотеки с точки зрения клиента можно считать своего рода языком, описывающим какую-то предметную область (DSL). Язык взаимодействия с БД Redis включает типы данных, команды и описание способов соединения. В своем скринкасте «Написание DSL в Лиспе» Райнер Джосвиг утверждает, что оно сводится к тому, чтобы «расставить скобки вокруг спецификации и заставить ее запуститься». Приведенный пример определения команд как раз буквально подтверждает это суждение. Единственная загвоздка заключается во фразе «заставить запуститься». Именно в этой сфере сосредоточена основная работа при написании DSL, и она выполнена в данном случае в модулях connection.lisp и redis.lisp. Впрочем, от этого никуда не деться в любом случае, а вот возможность сделать спецификацию действительно исполняемой, и, более того, полноценной частью языка, по нашему мнению, довольно ценна. Но еще ценнее то, что при таком подходе мы совершим плавный переход от описания предметной области к ее реализации.

Данная библиотека обладает высокой степенью модульности, в чем мы убедились, когда к работе подключился Александр. Он взялся за преобразование изначально достаточно примитивной реализации модуля соединения (которую я выбрал просто для того, чтобы иметь возможность тестировать остальную функциональность, работу над которой я считал более приоритетной) по образцу более зрелой библиотеки — Postmodern (клиента СУБД PostgreSQL). Ему это удалось без существенных изменений в других частях кода.

Очень важна возможность постепенного совершенствования и детализации программы. Например, оказалось, что команда SORT имеет способ задания аргументов, не полностью совместимый с принятым в Лиспе, поэтому для нее пришлось реализовать особый их разбор в методе TELL. Сделать это, не влияя на способ реализации других команд, позволило то, что обобщённые функции при необходимости могут быть специализированы на любом из своих обязательных аргументов, чем мы и воспользовались, введя дополнительную специализацию по названию именно этой команды. Таким образом, описание метода TELL для команды SORT приобрело такую форму:

(defmethod tell ((type (eql :inline)) (cmd (eql 'SORT)) &rest args) (flet ((send-request (key &key by get desc α start end) (unless (xor2 start end) (error "START and COUNT must be either both NIL or both non-NIL.")) (write-redis-line "SORT ~a~:[~; BY ~:*~a~]~{ GET ~ ~a~}~:[~; DESC~]~:[~; ALPHA~]~:[~; LIMIT ~:*~a ~a~]" key by (mklist get) desc alfa start end))) (apply #'send-request args)))

На данный момент это единственное исключение из общего правила для всех команд, но кто знает, как проект будет развиваться дальше? Когда в новой версии Redis появились новые команды, добавление их поддержки в библиотеку потребовало лишь чтения спецификации, «копирования» ее в файл commands.lisp и добавления соответствующего юнит-теста в тестовый набор. Появление нового вида запросов (multi-bulk команд) потребовало аналогичных, незначительных усилий.

Тестирование библиотеки также довольно прямолинейно и не представляет особых проблем благодаря модульности и наличию интерфейсов к каждой отдельной ее части. Соответственно, для нас не представляет труда поддерживать практически полноценный набор тестов для нее.

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

В заключение хочу упомянуть о пути развития самого подхода: интересно было бы посмотреть на его обобщение для любых socket-приложений — ведь модель взаимодействия и сложности, связанные с управлением соединением, везде примерно одинаковы. Не будет ли это дублированием самого socket API? Полагаю, что нет, если сконцентрироваться на вопросах, которые не покрываются им: на разделении потока символов на отдельные сообщения, на восстановлении соединения в случае сбоев и ошибок и т. п. Также речь идет не о полноценной платформе, которая полностью скрывает сокеты и добавляет дополнительные сервисы и уровни маршализации (вроде CORBA), а лишь о тонком слое, который бы автоматизировал и унифицировал решения стандартных проблем.

3  Проектирование «от данных» (data-driven design)

Проектирование, ведомое данными (data-driven design) — это ещё один подход при создании «больших» систем в Лисп.

Начнем с того, что нет единого определения и понимания термина «data-driven design». В разных отраслях он может означать разные вещи. Мы здесь рассматриваем это понятие под тем углом, как его сформулировал Питер Норвиг в своей книге «Парадигмы программирования искусственного интеллекта» [4]. Data-driven design — это проектирование системы таким образом, чтобы выделить максимально общий и в то же время простой алгоритм решения задачи, а часть специфичной логики закодировать в обычных структурах данных языка. Интересные примеры использования этого подхода в разных языках программирования приведены в девятой главе книги «Искусство программирования под Unix» Эрика Реймонда [6]4. Таким образом, можно уверенно говорить, что проектирование от данных (как, впрочем, и другие описанные в этой статье методы) не является чем-то уникальным для Лиспа и может практиковаться с тем или иным успехом в других средах. Отличие заключается в том, что Лисп поощряет применение этого подхода и предоставляет для этого развитые инструменты.

В результате декомпозиции «от данных» мы получаем программу, которую условно можно разделить на три части:

  1. ядро исполняемого кода (в рамках применяемого стиля разработки: императивного, функционального и т. д.);
  2. описание специфичной логики (в декларативном стиле): таким образом обретает смысл выражение «данные — это код»;
  3. код диспетчеризации, в котором, как правило, приходиться учитывать особенности (нерегулярности) конкретной задачи.

В идеале, таким образом достигаются такие полезные, на мой взгляд, качества програмного кода как:

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

3.1  Практический пример

Подход «от данных» был применен при решении задачи создания проксирующей прослойки между двумя бизнес-приложениями. Их интерфейсами с одной стороны были вызовы PL/SQL процедур Oracle, а с другой — XML-RPC API. Необходимо было обеспечить двустороннее взаимодействие путем обмена по HTTP XML-сообщениями в рамках заданного протокола. Более детально, модель взаимодействия такова: одна сторона может отправить HTTP-запрос с XML-содержимым для инициации какой-то операции, в результате чего должен быть вызван PL/SQL метод на другой стороне, а его результат отправлен назад в теле HTTP-ответа в виде XML-документа. Другая сторона может выполнить HTTP-запрос к нашему приложению, передавая данные, из которых должно сформироваться XML-содержимое запроса, который будет отправлен с помощью HTTP первой стороне. На первый взгляд, логика каждого из путей взаимодействия различается. Но ведь по сути они одинаковы: необходимо принять одно сообщение, транслировать его в другую форму и отправить другой стороне, а затем обработать специфичный для другой стороны ответ. В обоих случаях используются те же отдельные базовые блоки. В первом случае формат входящего сообщения — XML-документ, исходящего — параметры вызова хранимой процедуры, а результирующего — тоже XML-документ. Во втором: входящее сообщение — POST-параметры, исходящее — XML-документ, результирующее — параметры вызова хранимой процедуры.

В качестве языка реализации был выбран PHP, поскольку он вписывался в среду заказчика (LAMP), а также, в принципе, хорошо адаптирован к решению задач, связанных с технологиями HTTP, XML и взаимодействия с реляционными БД.

Решение задачи с применением проектирования от данных начинается с выбора наиболее удобного формата представления ключевых данных бизнес-логики и описания этих данных.

В данном случае специфику каждого отдельного взаимодействия, описанного в протоколе (который включает 14 типов запросов), можно представить в виде карты соответствия типа XML-запроса, соответствующего имени корневого узла и параметров вызова PL/SQL хранимых процедур. Для одной стороны этого взаимодействия часть этой карты показана ниже:

$ACTIONS = array('GetBalance' => array(ORA_FUNC, 'get_user_balance', array('SubscriberID', SQLT_CHR, 'AccountID', SQLT_CHR)) 'AuthorizePurchase' => array(ORA_FUNC, 'authorize_purchase', array('SubscriberID', SQLT_CHR, 'AccountID', SQLT_CHR, 'ApplicationID', SQLT_CHR, 'ProductID', SQLT_CHR, 'SubProductID', SQLT_CHR, 'AssetPrice', SQLT_INT, 'AssetTitle', SQLT_CHR, 'ProductName', SQLT_CHR)), 'RegisterPurchase' => array(ORA_PROC, 'register_purchase', array('ReferenceID', SQLT_INT, 'SubscriberID', SQLT_CHR)), 'RollbackPurchase' => array(ORA_PROC, 'rollback_purchase', array('ReferenceID', SQLT_INT, 'SubscriberID', SQLT_CHR)));

Также в результате каждого взаимодействия должен быть сформирован XML-ответ, включающий определенный набор узлов, состоящий из стандартного для всех множества (например, `ResultCode'), а также дополнительных узлов, которые могут добавляться к ответу на специфичные запросы.

Для другой стороны перечень также задается картой, и если какой-то из типов запросов в ней отсутствует, то ответ для него включает только стандартный перечень узлов. Фрагмент карты выглядит так:

$OUTPUT_SPEC = array('GetBalance' => array('Balance'), 'AuthorizePurchase' => array('ReferenceID', 'AuthCode'), 'RollbackPurchase' => array('ReferenceID', 'AuthCode'));

В целом, приложение строится из двух файлов, один из которых содержит общие функции, а другой реализует логику взаимодействия конкретного типа. Первичная диспетчеризация происходит по URL запроса, которому в силу специфики PHP соответствует вызываемый файл. Основное содержание обоих специфических файлов составляют приведенные выше карты соответствий, а также код диспетчеризации второго уровня, которая выполняется по типу XML-запроса (для первого варианта) или же по одному из POST-параметров (для второго). Ну и, конечно, служебный код для установки глобальных параметров, ведения логов, отладки и т. п.

Посмотрим на код диспетчеризации для одного из вариантов (для второго выполняется примерно тот же набор действий, только в другой последовательности):

$xml = @ simplexml_load_string($HTTP_RAW_POST_DATA); // пропущен фрагмент обработки ошибок $action = $xml->getName(); switch ($action) { case 'AuthorizePurchase': case 'RollbackPurchase': $ref_id = null; $out = array($ref_id, SQLT_INT); break; default: $out = null; } $auth_code = ''; $err = null; if (DEBUGGING) { $rez = plsql_req($ACTIONS[$action][0], $ACTIONS[$action][1], xml_to_plsql_args($xml, $ACTIONS[$action][2]), $out, $err); } else { // suppress warnings $rez = @ plsql_req($ACTIONS[$action][0], $ACTIONS[$action][1], xml_to_plsql_args($xml, $ACTIONS[$action][2]), $out, $err); }

Из этого кода можно сделать следующие выводы:

  1. во-первых, основную диспетчеризацию по типу запроса мы получаем «бесплатно»;
  2. во-вторых, для некоторых типов запросов предварительно добавляются дополнительные «выходные» параметры для вызова PL/SQL процедур (если мы хотим получить больше одного результирующего значения). Определение этих параметров также можно было бы произвести в декларативном стиле через карту соответствия, однако для данного простейшего случая в этом нет необходимости.
  3. некоторые вещи в PHP делаются просто отвратительно (это про дублирование кода в случае DEBUGGING).

Оправдывает ли себя такой подход для системы, которая имеет всего два разных сценария работы? Его преимущество в том, что программа получилась довольно понятной и легко расширяемой: добавление нового типа сообщений выполняется по единому принципу для обоих типов взаимодействия и в базовом случае потребует только добавления нового отношения в обе карты ($ACTIONS и $OUTPUT_SPEC). Кроме того, как и в предыдущем случае с клиентом для Redis, мы в какой-то мере декларативно (а не императивно) вписали протокол в сам код — хотя в данном варианте в нем также появилась не описанная в протоколе часть, связанная с вызовами PL/SQL. Впрочем, так даже лучше, поскольку теперь мы получили формальную спецификацию интерфейса PL/SQL. Конечно, такой подход не универсален: он хорошо работает в тех случаях, когда проблема состоит из нескольких похожих задач, в которых можно выделить какую-то общую часть.

Приведенный пример довольно прост, однако и на нем уже становятся видны некоторые синтаксические проблемы PHP, связанные с плохой поддержкой декларативного программирования и манипуляций собственным кодом. Также для data-driven подхода очень полезной является возможность оперирования такими структурами данных как первоклассные объекты (наличие синтаксиса литералов, полноценная поддержка в высокоуровневых функциях, итераторах и т. п.), а также хорошие возможности интроспекции.

3.2  Диспетчеризация

По сути дела, подход к проектированию от данных задействует полиморфизм, однако без привязки к наследованию и иерархиям классов. Ведь в ОО-языке можно было бы аналогично декомпозировать приведенную задачу, создав отдельные классы и реализовав каждый из методов взаимодействия в виде методов этих классов. Это было бы вполне в духе объектно-ориентированного проектирования. В чем же разница, помимо того, что в данном случае меньше «накладных расходов» как для программиста, так и для среды исполнения в связи с отсутствием необходимости поддержания иерархии классов, создания объектов и т. п.? Разница становится хорошо видна на более масштабных примерах, один из которых будет приведен в следующем разделе статьи.

Вообще говоря, каждая школа разработки рассматривает понятие полиморфизма под собственным углом зрения. Для функциональной школы он прежде всего основывается на типе [8], для объектно-ориентированной — на иерархии классов5, а для подхода «от данных» — на любом подходящем для задачи способе. Объяснить это можно таким образом: в очень многих случаях для диспетчеризации, кроме самого идентификатора, больше ничего не нужно, в то время, как в редких случаях могут возникнуть специфические потребности, которые трудно выразить через иерархию классов или систему типов. Таким образом идентификатором для диспетчиризации может служить: просто строка (или даже интернированная строка, что еще лучше, так как для сравнения таких строк достаточно сравнения адресов памяти), тип/класс объекта или даже значение, получаемое в результате вызова произвольной функции. И все эти варианте неплохо бы предоставлять в рамках языковой среды, в идеале так, чтобы простота применения того или иного подхода коррелировала с частотой его использования.

На практике же можно выделить четыре подхода к диспетчеризации:

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

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

Подходом, лишенным всех этих недостатков, является разделение механизма диспетчеризации и механизма задания специфических методов. Одной из его реализаций является система generic functions (обобщённых функций), встроенная в Common Lisp. Принято считать, что они являются частью Объектной Системы Common Lisp (CLOS, Common Lisp Object System), однако это не совсем так: кроме диспетчеризации по классам аргументов (как в обычном ОО-подходе со множественным наследованием), они также поддерживают и выбор по произвольному ключу (EQL-диспетчеризация). Среди возможностей обобщённых функций:

Тот же подход взят за основу в механизме мультиметодов языка Clojure, который пошел дальше, позволяя задавать для диспетчеризации произвольную функцию от аргументов. Впрочем, такая возможность есть и для обобщённых функций Common Lisp, только не «из коробки». Приведу пример одно из вариантов ее реализации через механизм комбинации методов, определяемый пользователем:

(define-method-combination multi (dispatch-fn) ((all *)) (:arguments &whole args) `(or ,@(mapcar (lambda (method) `(when (member (apply ,dispatch-fn ,args) (method-qualifiers ,method)) (call-method ,method))) all))) CL-USER> (defgeneric foo (collection) (:method-combination multi #'length) (:documentation "Dispatches on COLLECTION's length")) #<STANDARD-GENERIC-FUNCTION FOO (0)> CL-USER> (defmethod foo 3 (x) (format t "~a contains 3 things.~%" x)) #<STANDARD-METHOD FOO 3 (T) {B6238A9}> CL-USER> (defmethod foo 10 (_) (format t "A collection of 10 elements.~%")) #<STANDARD-METHOD FOO 10 (T) {B03CBC9}> CL-USER> (foo "yes") yes contains 3 things NIL CL-USER> (foo (range 10)) A collection of 10 elements. NIL

Еще более детализированный и интегрированный вариант — это библиотека Filtered functions Паскаля Костансы, основанная на использовании мета-объектного протокола Common Lisp.

4  Использование обобщённых функций для создания API

В предыдущем разделе обсуждалась диспетчеризация как один из ключевых моментов для обеспечения модульности и определения наиболее обобщённых алгоритмов — т. е. основных принципов проектирования от данных. В Common Lisp для поддержки этого подхода существует механизм обобщённых функций. Посмотрим, как их можно использовать на примере приложения среднего размера и уровня сложности. Это веб-приложение «MindShare»6, предоставляющее некоторые дополнительные сервисы для пользователей популярного сервиса микроблоггингового сайта Twitter.com. Twitter предоставляет REST-интерфейс для получения основных данных о пользователях, однако у него довольно жесткие ограничения. Для работы ключевой функции MindShare, выдачи рекомендаций пользователям, необходимо обрабатывать большой объем данных. Их получение напрямую через Twitter API на практике оказывается невозможным из-за необходимости выполнения сотен, а то и тысяч API-запросов для выдачи одной рекомендации: даже не учитывая ограничение по запросам API, время на их выполнение исчисляется минутами и десятками минут в связи с задержкой сети. Поэтому мы выбрали стратегию кеширования данных, получаемых через API, а также их предзагрузки как через API, так и путем получения информации напрямую с web-страниц пользователей (scraping).

Задачей Александра на определенном этапе стало проектирование и разработка внутреннего API, абстрагирующего разные способы получения данных и управляющее их гибким комбинированием. Этот API, в свою очередь, должен использоваться в модуле, обрабатывающем запросы пользователей (frontend).

Итак, у приложения есть три основных способа получения данных:

  1. Получение информации о пользователе по его имени или идентификационному номеру посредством Twitter API. Например, GET-запрос по адресу

    http://api.twitter.com/1/followers/ids.json?screen_name=N

    возвращает JSON-массив идентификаторов пользователей, следящих за сообщениями пользователя N.

  2. Получение информации о пользователях без обращения к Twitter API путем извлечения данных из HTML-кода личной страницы пользователя (например, с помощью регулярных выражений).
  3. Получения данных из кеша. Кеширование необходимо, поскольку оба приведенных метода получения информации достаточно медленные, и просто не работают, когда Twitter перегружен (что случается достаточно часто). Кроме того, значительная часть информации изменяется относительно редко (например, профили пользователей), и ее актуальность не играет решающей роли для нашего приложения, поэтому неразумно каждый раз получать ее заново (хотя периодически обновлять эту информацию все же необходимо; для этих целей в Redis, который мы выбрали в качестве кеша c сохранением данных на диске, весьма удобной оказалась возможность устанавливать для ключей «срок годности», т. е. промежуток времени, по истечению которого ключ и данные, сохраненные под этим ключом, удаляются из базы).

    Кстати, создание этого внутреннего API получения данных позволило сделать приложение более модульным. Изначально для кэширования всей информации использовался Redis, однако мы столкнулись с тем, что он не справляется со всем необходимым объемом информации на имеющихся вычислительных ресурсах7. Тогда мы решили перенести часть данных в более «тяжеловесное» хранилище. Этот переход мы смогли осуществить относительно легко, практически без изменений в остальных частях кода.

Что должен представлять собой такой API? В качестве прямолинейного варианта можно было бы для каждого свойства пользователя (например, списка последователей), каждого из перечисленных способов получения информации (Twitter API, HTTP или кеш), и каждого типа аргумента (строка или число) ввести отдельную функцию. Кроме того, что при данном подходе пространство имен загрязняется большим количеством неудобоваримых имен, вроде get-followers-via-api-by-screen-name (для каждого свойства приходится вводить шесть новых функций, в которых легко запутаться), этот подход обладает и другим серьезным недостатком — он ведет к дублированию кода. Например, код функции для получения списка последователей практически идентичен коду функции для получения списка тех, за кем следит сам пользователь.

С другой стороны, если бы мы попробовали применить объектно-ориентированную декомпозицию, то нам, наверное, пришлось бы создать классы AccessMethod с потомками вроде APIAccessMethod, HTTPAcessMethod и StoreAccessMethod, которые бы не имели практически никакого внутреннего состояния, за исключением разве что статических переменных, хранящих служебную информацию, и определить для них методы получения информации типа GetFollowersByScreen_name (в общем-то, очень похоже на предыдущий вариант). Впрочем, и из этой ситуации, будь мы экспертами OOD, можно было бы найти выход: например, применив шаблон «визитёр» (Visitor pattern). Довольно сложно для такой на первый взгляд простой задачи.

В Lisp принято решать задачу наиболее простым (но не настолько тупым, как в первом предложенном варианте) способом. Учитывая приведенные в начале соображения, естественнее всего сделать тип извлекаемого атрибута аргументом функции. В Common Lisp для этой цели хорошо подходят ключевые слова — символы, интернированные в специальном пакете keywords и доступные в любом пакете без явной квалификации (вместо keywords:foo можно писать просто :foo). Ключевые слова удобны тем, что (при удачном выборе) имя символа можно включить в строку-шаблон, например, при построении URL, по которому производится запрос (это как раз пример data-driven подхода, когда ключевое слово внутреннего API используется также в качестве идентификатора, по которому осуществляется доступ к внешнему API).

Сделав тип атрибута аргументом функции, мы наталкиваемся на проблему диспетчеризации: поскольку логика извлечения списка последователей отличается от, скажем, логики получения личных данных пользователя, необходимо проводить разбор частных случаев. Делать его в теле функции с помощью оператора case — не совсем удачный вариант, так как при этом, как было замечено ранее, страдает модульность. Common Lisp предлагает весьма элегантное решение этой проблемы: обобщённые функции.

У нас есть три метода получения информации, которые мы можем задать ключами :twitter, :http и :store, а также два типа идентификаторов пользователей: имя (строка) и идентификационный номер (число). Для каждой тройки (метод, пользователь, атрибут) имеется алгоритм извлечения данного атрибута для заданного пользователя и заданным методом. Эти алгоритмы можно собрать в трехмерную таблицу, измерения которой соответствуют трем аргументам. Эта таблица и есть обобщённая функция. Применение обобщённой функции к заданным аргументам сводится к вызову другой функции, которая принимает в качестве аргументов саму обобщённую функцию (т. е. таблицу) и ее аргументы, и на их основе проводит диспетчеризацию: находит подходящую функцию в таблице и применяет ее. Более детальное обсуждение этой идеи заинтересованный читатель найдет в [3, Разделе 2.5]. Механизм обобщённых функций, реализованный в Common Lisp, несколько сложнее, чем в Scheme, но для наших потребностей приведенного объяснения должно быть достаточно (хоть оно и не до конца точное).

Итак, определим обобщённую функцию retrieve.

(defgeneric retrieve (method attribute user))

Тогда методы, принадлежащие этой обобщённой функции (элементы таблицы) определяются с помощью макроса defmethod, например:

(defmethod retrieve ((method (eql :api)) (attribute (eql :followers)) (id integer)) ;; код метода )

Из всех методов алгоритм диспетчеризации однозначно выбирает наиболее специфичный. Аргументы, переданные в обобщённую функцию, сверяются в порядке старшинства с типами или значениями, по которым специализированы методы обощенной функции. По умолчанию, порядок старшинства (precedence order) совпадает с порядком аргументов в определении функции, но его можно изменить с помощью опции :argument-precedence-order в макросе defgeneric. На самом деле, для корректной диспетчеризации нам пришлось изменить старшинство аргументов в retrieve:

(defgeneric retrieve (method attribute user) (:argument-precedence-order attribute method user))

Этот подход позволил кроме основных методов :api, :http и :store легко добавить также комбинированные методы :fast и :all. Первый метод сначала ищет заданный атрибут в кеше; если там его нет, делает запрос к Twitter API; и наконец, если это срывается по какой-то причине, пытается извлечь нужную информацию через HTTP.

(defmethod retrieve ((method (eql :fast)) attribute user) "First try to lookup ATTRIBUTE in Redis; if it is not available, try the Twitter API, and finally if this fails retrieve through the HTTP." (handler-case (let ((rez (multiple-value-list (retrieve :store attribute user)))) (if (car (mklist rez)) (apply #'values rez) (handler-case (retrieve :api attribute user) ((or twi-error http-client-error) () (retrieve :http attribute user))))) ((or error sb-ext:timeout) (e) (log-message :error "Error, while FAST retrieving ~A ~A: ~A" attribute user e))))

Второй метод, наоборот, сначала пытается получить наиболее актуальную информацию посредством запроса к Twitter API; если это не удается, пытается получить данные через HTTP; наконец, ищет в кеше прошлую версию.

Следует отметить, что совсем необязательно специализировать метод по всем аргументам — неспециализированные аргументы на самом деле специализируются по типу T, который является корневым в иерархии типов в Common Lisp. В ходе работы над API нам потребовалось определить всего 23 отдельных метода для этой функции, при том, что теоретически возможное число комбинаций составляет 5× 7× 2=70 вариантов.

Еще одна крайне удобная возможность, которую предоставляет механизм обобщённых функций — это определение методов-декораторов (:before, :after и :around). Например, все методы функции retrieve обращаются к Redis для поиска или кеширования данных, поэтому мы хотели бы убедиться, что в случае обрыва соединения с Redis-сервером в процесе выполнения того или иного метода мы автоматически переподключимся к серверу. Для этого тело каждого метода необходимо завернуть в форму handler-bind, которая устанавливает обработчик для ошибок соединения с Redis:

(handler-bind ((redis-connection-error #`(invoke-restart :reconnect))) ;; тело метода )

Оборачивать явно тело каждого метода в handler-bind — это, без сомнения, дублирование кода. К счастью, в Common Lisp есть штатное средство для борьбы с ним — макросы. Мы могли бы определить специальный макрос для добавления методов к функции retrieve, который генерировал бы необходимый оберточный код, однако механизм обобщённых функций предоставляет стандартное решение: методы-декораторы. Мы определим :around-метод для функции retrieve.

(defmethod retrieve :around (method attribute id) "Ensure that Redis connection persists." (handler-bind ((redis-connection-error #`(invoke-restart :reconnect))) (call-next-method)))

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

Что при этом происходит? Мы добавляем метод, который выполняется до любого другого метода нашей обобщённой функции. Этот метод устанавливает динамический контекст, в котором для ошибок типа redis-connection-error установлен обработчик, и вызывает следующий более специфический метод с помощью (call-next-method). В конечном счете мы имеем тот же эффект — тело метода выполняется в динамической среде, в которой виден обработчик для ошибок типа redis-connection-error, но при этом мы не пользовались макросами (это сделал за нас компилятор). Таким образом, методы :before, :after и :around позволяют добавлять и изменять функциональность существующих методов, не меняя их собственный код. Кроме того, они могут иметь разный уровень специализации с основными методами: в нашем случае метод задан для всех аргументов, однако, если бы нам понадобилось добавить такой код только при получении данных из кеша, мы бы могли изменить его следующим образом:

(defmethod retrieve :around ((method (eql :store)) attribute id) ;; код метода )

Итак, подытожим преимущества, которые дает нам использование обобщённых функций.

Таким образом можно сделать вывод, что механизм обобщённых функций прекрасно подходит для определения различных API. Идеальным вариантом его использования является случай, когда API основывается на большом числе однообразных операций, которые удобно представить в виде многомерной таблицы.

5  Использование сигнального протокола вне системы обработки ошибок

Еще одной важной технологией Common Lisp (явно недооцененной, на наш взгляд, в том числе и самими Лисп-разработчиками) является сигнальный протокол. Он лежит в основе системы обработки ошибок, однако может применяться гораздо шире, так как по сути является четко структурированной реализацией синхронной нелокальной передачи управления. Хороший обзор протокола представлен в [7, главе 19]. Именно там сформулирована мысль, что сигнальный протокол может быть использован для реализации многих интересных решений, вплоть до со-процедур. (Нужно сказать, что в Common Lisp невозможно полноценное использование стиля передачи продолжений (continuation-passing style), с помощью которого принято реализовывать со-процедуры в функциональных языках. Это связано с наличием специального оператора unwind-protect и, вкратце, может быть выражено афоризмом «непреодолимая сила против непробиваемой брони».)

5.1  Парсерные комбинаторы

Задача, которую мы будем решать — это создание библиотеки парсерных комбинаторов по образцу библиотеки Parsec в Haskell. Путь ее решения, который приходит в голову сразу же — это портировать основанную на монадах реализацию (именно так устроена, например, библиотека CL-PARSER-COMBINATORS). Однако мне хотелось понять, можно ли получить столь же прозрачный и удобный интерфейс без использования монад. Таким образом, на мой взгляд, можно уменьшить уровень дополнительной сложности, связанной с решением задачи в силу особенностей реализации (incidental complexity), и, в идеале, довести сложность до минимального уровня, определяемого самой предметной областью.

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

Рассмотрим простейший пример записи правил разбора для арифметических выражений (без правил приоритета операторов). На «языке» CL-PARSEC9 он имеет следующий вид:

(defparser spaces () (skip-many #\Space)) (defparser expression () (prog1 (many+ #'tok) (spaces) (eof))) (defparser tok () (spaces) (either #`(parse-integer (coerce (many+ #`(parsecall #'digit-char-p)) 'string)) #`(parsecall #\( :lparen) #`(parsecall #\) :rparen) #'operator)) (defparser operator () (list :op (parsecall '(member (#\- #\+ #\* #\/)))))

Здесь spaces, skip-many, expression, many+, tok, eof, either и operator — это парсеры (в том числе высокоуровневые). Prog1, parse-integer, coerce, digit-char-p, parsecall и list — обычные формы языка.

Вот пример использования этого кода:

PARSEC-TEST> (with-input-from-string (stream "(1 + 2)/10") (parse stream 'expression)) (:LPAREN 1 (:OP #\+) 2 :RPAREN (:OP #\/) 10)

Тот же пример на Haskell выглядит так:

module Main where import Text.ParserCombinators.Parsec data Token = Atom String | Op String | LParen | RParen parse' :: String -> [Token] parse' s = case (parse expression "expr" s) of Left err -> error (show err) Right x -> x -- operator token operator :: Parser Token operator = do c <- char '-' <|> char '+' <|> char '*' <|> char '/' <?> "operator" return $ Op (c:[]) -- atom token atom :: Parser Token atom = do a <- many1 alphaNum <?> "atom" return (Atom a) -- single-char tokens lparen = char '(' >> return LParen rparen = char ')' >> return RParen -- one token tok :: Parser Token tok = do t <- atom <|> operator <|> lparen <|> rparen skipMany space return t -- the whole expression expression :: Parser [Token] expression = do skipMany space ts <- many1 tok eof return ts

Как видно, разница в интерфейсе определения парсеров невелика (за исключением внешнего синтаксического различия). Однако реализация разная. Рассмотрим основные идеи CL-PARSEC и роль, которую в ней играет сигнальный протокол.

5.2  Реализация CL-PARSEC

Каждый парсер — это обычная функция, которая возвращает результат разбора: это может быть отдельный символ, уже разобранная строка или число, а также значения NIL или T. Эти значения превращаются в итоговое значение c помощью обычного Лисп-кода без каких-либо дополнительных ограничений10, как можно видеть из примера выше.

Наибольшей проблемой для любой библиотеки, связанной с синтасическим анализом, на мой взгляд, являются возвраты (backtracking), особенно в случае таких потоков (streams), как в CL, которые позволяют отмотать (unread) только на один символ назад11. Поэтому на каждый парсер накладываются следующие условия:

  1. Во-первых, чтобы не передавать между вызовами поток, из которого происходит чтение, он передается неявно в специальной переменной *stream*. Более того, даже если бы мы решили передавать этот поток, нам бы все равно пришлось организовывать определенный механизм для просмотра вперед и возврата назад более, чем на 1 символ. Для этого добавлена специальная переменная *backlog*, в которую заносятся символы в случае невозможности вернуть их назад во входной поток.
  2. Для того, чтобы инкапсулировать механизм чтения из потока или же из бэклога, введен макрос next-item, с помощью которого осуществляется получение следующего символа. Таким образом, клиентский код вообще не работает со специальными переменными. Более того, практически никогда ему не придется задействовать и next-item, поскольку для большинства случаев этот вызов инкапсулируется еще более высокоуровневым макросом mkparser, о котором далее.
  3. В случае удачного разбора любой парсер, который вызывает next-item, должен просигнализировать parsec-success и в этом сигнале передать прочитанный символ. Семантика сигнала такова, что если никто его не обработает, то он просто будет проигнорирован. В то же время, обработать его можно на произвольном числе уровней выше по стеку. Необходимость в этом сигнале продиктована именно потребностью собирать знаки в бэклоге для такого оператора, как try, который выходит за пределы простых LL(1)-парсеров.
  4. Наконец, в случае неудачи разбора любой парсер должен сигнализировать ошибку типа parsec-error. Соответственно, все парсеры высших порядков должны быть готовы обрабатывать эту ошибку тем или иным образом.

Благодаря последним двум пунктам пользователи при создании парсеров могут сосредоточиться всецело на логике их работы, особо не думая о том, каким образом они будут комбинироваться с другими: всё это берет на себя библиотека, предоставляя несколько макросов.

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

(defun parse (stream parser) "Parses STREAM with the given PARSER function. Binds specials." (let ((*stream* stream) *backlog* (*source* :stream) *current-item*) (funcall parser)))

Следующий макрос позволяет определять парсеры. Это обертка вокруг формы defun, служащей для определения функций, которая, во-первых, добавляет свое имя к стеку ошибок при возникновении parsec-error, а, во-вторых, предоставляет в своем теле локальную переменную _parser-name_, которую можно использовать в коде определения парсеров. В принципе, все эти задачи являются служебными, так что по сути определение парсера — это просто определение функции.

(defmacro defparser (name (&rest args) &body body) "DEFUN a parser function with the given NAME and ARGS. BODY is wrapped in HANDLER-CASE, that traps PARSEC-ERROR and resignals it with NAME added to the error stack. Provides internal variable _PARSER-NAME_. Intended for top-level use, like DEFUN." `(defun ,name (,@args) ,(when (stringp (car body)) (car body)) (let ((_parser-name_ ',name)) (handler-case (progn ,@body) (parsec-error (e) (?! ',name e))))))

Однако эти фрагменты кода не дают ответа на вопрос, как же производится чтение и возврат символов. Для описания этой логики используются макрос mkparser и функция parsecall, которые необходимо использовать в коде, использующем библиотеку.

(defun parsecall (test &optional (return :parsed)) "Funcall TEST as if it was already passed to MKPARSER. RETURN semantics repeats MKPARSER's one." (funcall (mkparser test return))) (defmacro mkparser (test &optional (return :parsed)) "Creates the parser, that implements the following strategy: it reads the NEXT-ITEM, checks it with PARSE-TEST (that implements the polymorphic logic of testing, depending on TEST's type), * if test passes, it signals PARSEC-SUCCESS and returns - the item (default case) - TEST (if return = :test) - otherwise RETURN itself * otherwise it performs UNREAD-LAST-ITEM and signals PARSEC-ERROR." (with-gensyms (cur item gtest greturn) `(lambda () (let ((,gtest ,test) (,greturn ,return) (,cur (next-item))) (if (parse-test ,gtest ,cur) (progn (signal 'parsec-success :result ,cur) (case ,greturn (:parsed ,cur) (:test ,gtest) (otherwise ,greturn))) (progn (unread-last-item) (?! `(parser ,,gtest))))))))

Если убрать весь служебный код, то логика символьного парсера, создаваемого mkparser такова:

  1. прочитать символ с помощью next-item;
  2. проверить его с помощью обобщённой функции parse-test (это синтаксический сахар для того, чтобы можно было задавать функции принадлежности к классам символов не только непосредственно, как в (mkparser #'alpahnumericp), но и прямо символами ((mkparser #\a)), а также, например, списками, обозначающими применение функции ((mkparser '(member (#\a #\b))));
  3. в случае успеха вернуть этот символ, просигнализировав на более высокие уровни с помощью parsec-success;
  4. в случае неудачи вернуть символ обратно в поток с помощью unread-last-item и просигнализировать ошибку parsec-error с помощью ?!.

Осталось рассмотреть, собственно, работу next-item и unread-last-item. Они полагаются на обобщённые функции read-item и unread-item, реализующие специфичную логику для чтения/возврата для потока и списка (бэклога).

(defmacro next-item () "Sets *CURRENT-ITEM* to newly READ-ITEM from *STREAM* or *BACKLOG* and returns it." (with-gensyms (cur) `(prog1 (setf *source* (if *backlog* :backlog :stream) *current-item* (read-item (or *backlog* *stream*))) (when *echo-p* (format *echo-stream* "~:@c" *current-item*))))) (defmacro unread-last-item () "Unread *CURRENT-ITEM* to current *SOURCE*." `(unread-item *current-item* (if (eq *source* :stream) *stream* *backlog*)))

На этом примере можно видеть, что внутренняя реализация символьного парсера довольно сильно полагается на манипуляцию специальными переменными. Это не создаёт проблем благодаря изоляции таких переменных, обусловленной отличием специальных переменных от глобальных, а также четкой концептуальной границей, создаваемой с помощью макросов. Да, в этом случае возможно преднамеренное нарушение этой логики путем создания и использования парсера, который будет «портить» значения этих переменных. Но, оставив этот вариант в стороне12, случайное вмешательство в нее, например, по ошибке, является невозможным. В то же время, за счет того, что в самой основе лежат полиморфные операции read-item и unread-item, можно легко расширить библиотеку для использования других источников символов для разбора (например, бинарных потоков), не меняя логику передачи значений.

Теперь рассмотрим реализацию различных парсеров в этой парадигме.

Простейшие парсеры определены в файле simple.lisp и не принимают ничего на вход.

(defparser eof () (if-eof (return-from eof t) (next-item)) (?!))

Парсеры, параметризуемые классом символов, определены в item-level.lisp:

(defparser skip (test) (parsecall test) nil) (defparser look-ahead (test) "LL(1) lookahead" (progn (parsecall test) (unread-last-item) t))

Парсеры высших порядков определены в higher-order.lisp:

(defparser either (&rest parsers) "If either of the PARSERS returns, return its result. Ordering matters. LL(1) variant. If it doesn't suit you, use this pattern: (EITHER (TRY ...))" (dolist (parser parsers) (if-err nil (return-from either (funcall parser)))) (?!)) (defparser try (parser) "Returns the result of PARSER's application or `unreads' all the read items back." (let (backlog) (prog1 (intercept-signals cur-signal ((parsec-success (push (parsing-result cur-signal) backlog)) (try-success (setf backlog (append (parsing-backlog cur-signal) backlog)))) (if-end (progn (setf *backlog* (append (reverse backlog) *backlog*) *source* :backlog) (?!)) (funcall parser))) (signal 'try-success :backlog backlog)))) (defparser maybe (parser) "A wrapper around TRY to ignore unsuccessful attempts and simply return NIL." (if-err nil (try parser)))

Какие общие черты можно выделить в этих определениях?

Кроме того, в случае try используется более низкоуровневый макрос intercept-signals. Для приведенного случая он имеет следующее раскрытие:

(HANDLER-BIND ((PARSEC-SUCCESS (LAMBDA (THIS-SIGNAL) (UNLESS (MEMBER _PARSER-NAME_ (SIGNAL-FEATURES _THIS-SIGNAL_)) (PUSH (PARSING-RESULT THIS-SIGNAL) BACKLOG)) (PUSHNEW _PARSER-NAME_ (SIGNAL-FEATURES THIS-SIGNAL)))) (TRY-SUCCESS (LAMBDA (THIS-SIGNAL) (UNLESS (MEMBER _PARSER-NAME_ (SIGNAL-FEATURES THIS-SIGNAL)) (SETF BACKLOG (APPEND (PARSING-BACKLOG THIS-SIGNAL) BACKLOG))) (PUSHNEW _PARSER-NAME_ (SIGNAL-FEATURES THIS-SIGNAL))))) (IF-END (PROGN (SETF *BACKLOG* (APPEND (REVERSE BACKLOG) *BACKLOG*) *SOURCE* :BACKLOG) (?!)) (FUNCALL PARSER)))

Таким образом, в макросе инкапсулируется проверка на повторную обработку одного и того же сигнала в одноименных парсерах выше по стеку. Для случая try это необходимо, поскольку каждый такой парсер представляет отдельную ветку разбора, которая будет «свернута» в общее дерево в случае неудачи. Нужно отметить, что такая относительно сложная реализация понадобилась только для данного нестандартного парсера. Специальный сигнал try-success понадобился в данном случае для того, чтобы учесть случай вложенных вызовов try — когда более низкоуровневый вызов перехватывает часть символов, которые могут затем потеряться в случае отката, происходящего после успешного возврата из try на том же уровне вложенности.

Наконец, рассмотрим пример применения этих парсеров для описания правил, подобных тем, которые были приведены в заметке Ивана Веселова. В них активно используется мой собственный макрос чтения #` для компактного задания анонимных функций от нуля или одной переменной, который позволяет существенно сократить функциональный код и сделать его более единообразным (с записью #').

(defparser spaces () (skip-many #\Space)) (defparser expression () (prog1 (subexpression) (spaces) (eof))) (defparser subexpression () (spaces) (many+ #'element)) (defparser element () (spaces) (either #`(try #'func) #'token #'operator)) (defparser token () (list :atom (coerce (many+ #`(parsecall #'alphanumericp)) 'string))) (defparser operator () (list :op (parsecall '(member (#\- #\+ #\* #\/ #\^ #\.))))) (defparser func-arg () (prog1 (subexpression) (spaces) (either #`(look-ahead #\)) #`(parsecall #\,)))) (defparser func-end () (spaces) (parsecall #\))) (defparser func () (append (list :func (second (prog1 (token) (spaces) (parsecall #\()))) (prog1 (many #'func-arg) (func-end))))

Например, по ним может разбираться следующее выражение:

PARSEC-TEST> (with-input-from-string (in "1 + 2-10a ^ ac1(bd+f(), z)") (parse in 'expression)) ((:ATOM "1") (:OP #\+) (:ATOM "2") (:OP #\-) (:ATOM "10a") (:OP #\^) (:FUNC "ac1" ((:ATOM "bd") (:OP #\+) (:FUNC "f")) ((:ATOM "z"))))

Также интерес представляет случай небольшого изменения входной строки: уберем из нее последний аргумент функции, z, оставив в тексте запятую. В данном варианте, поскольку мы оперируем в рамках контекстно-свободной грамматики, и не можем в правилах задать проверку на висящую запятую, разбор даст следующий результат:

((:ATOM "1") (:OP #\+) (:ATOM "2") (:OP #\-) (:ATOM "10a") (:OP #\^) (:FUNC "ac1" ((:ATOM "bd") (:OP #\+) (:FUNC "f"))))

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

(defvar *more-func-args* nil) (defparser func-arg () (prog1 (subexpression) (setf *more-func-args* nil) ; еще один нашелся (spaces) (either #`(look-ahead #\)) #`((parsecall #\,) ; должны быть еще (setf *more-func-args* t))))) (defparser func () (nconc (list :func (second (prog1 (token) (spaces) (parsecall #\()))) (let (*more-func-args*) (prog1 (many #'func-arg) (when *more-func-args* ;; закончили разбор аргументов, а должен быть еще один (?!)) (func-end)))))

Теперь вызов

PARSEC-TEST> (with-input-from-string (in "1 + 2-10a ^ ac1(bd+f(), )") (parse in 'expression))

вернет ошибку: Parsing error.  Error stack: ((EXPRESSION) (EOF)).

5.3  Выводы

В данном примере, как и в предыдущих, был задействован целый ряд технологий языка:

Все вместе они позволяют решить задачу создания высокоуровневого декларативного языка описания парсеров, которые являются полноценными объектами хост-языка (обычными функциями), в то же время предоставляя возможность при необходимости влиять на детали внутренней реализации на любом необходимом уровне.

Последнее, на чем я хотел бы остановиться — это возможности по отладке этого решения, которые я имел в Лисп-среде. Часто отладка кода такого рода, включающего высокоуровневые правила и две параллельных нити принятия решений о передаче управления, требует особого подхода. Однако в данном случае мне вполне хватило механизма трассировки, представленного стандартной функцией trace (а также пары print-выражений).

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

PARSEC-TEST> (with-input-from-string (in "f") (parse in 'expression)) 0: (SUBEXPRESSION) 1: (SKIP-MANY #\ ) 2: (UNREAD-ITEM #\f #<SB-IMPL::STRING-INPUT-STREAM {ACC6309}>) 2: UNREAD-ITEM returned NIL 1: SKIP-MANY returned NIL 1: (MANY+ #<FUNCTION ELEMENT>) 2: (SKIP-MANY #\ ) 3: (UNREAD-ITEM #\f #<SB-IMPL::STRING-INPUT-STREAM {ACC6309}>) 3: UNREAD-ITEM returned NIL 2: SKIP-MANY returned NIL 2: (EITHER #<FUNCTION (LAMBDA #) {A92F355}> #<CLOSURE SB-IMPL::ENCAPSULATION {A92F40D}> #<CLOSURE SB-IMPL::ENCAPSULATION {A930F8D}>) 3: (TRY #<FUNCTION FUNC>) 4: (TOKEN) 5: (MANY+ #<FUNCTION (LAMBDA #) {A92081D}>) 6: (MANY #<FUNCTION (LAMBDA #) {A92081D}>) 6: MANY returned NIL 5: MANY+ returned (#\f) 4: TOKEN returned (:ATOM "f") 4: (SKIP-MANY #\ ) 4: SKIP-MANY returned NIL 3: (TOKEN) 4: (MANY+ #<FUNCTION (LAMBDA #) {A92081D}>) 5: (MANY #<FUNCTION (LAMBDA #) {A92081D}>) 5: MANY returned NIL 4: MANY+ returned (#\f) 3: TOKEN returned (:ATOM "f") 2: EITHER returned (:ATOM "f") 2: (MANY #<FUNCTION ELEMENT>) 3: (SKIP-MANY #\ ) 3: SKIP-MANY returned NIL 3: (EITHER #<FUNCTION (LAMBDA #) {A92F355}> #<CLOSURE SB-IMPL::ENCAPSULATION {A92F40D}> #<CLOSURE SB-IMPL::ENCAPSULATION {A930F8D}>) 4: (TRY #<FUNCTION FUNC>) 5: (TOKEN) 6: (MANY+ #<FUNCTION (LAMBDA #) {A92081D}>) 4: (TOKEN) 5: (MANY+ #<FUNCTION (LAMBDA #) {A92081D}>) 2: MANY returned NIL 1: MANY+ returned ((:ATOM "f")) 0: SUBEXPRESSION returned ((:ATOM "f")) 0: (SKIP-MANY #\ ) 0: SKIP-MANY returned NIL ((:ATOM "f"))

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

6  Роль протоколов в языке

В предыдущих разделах статьи не раз упоминался термин «протокол», в основном в контексте внешних для языковой среды процессов: передаче данных по сети, способам взаимодействия с сервером БД и т. п. Однако эта концепция находит плодотворное применение и в рамках собственно языка.

Как говорит Википедия, протокол — это набор правил, используемых компьютерами при взаимодействии. Кент Питман, один из авторов стандарта Common Lisp и разработчик его системы обработки исключений, пишет [5], что:

Установление протоколов — это определенная заблаговременная страховка от дилеммы узника (prisoner’s dilemma), которая дает очевидный способ структурирования независимо разрабатываемого кода для людей, которые не общаются напрямую, так, чтобы при последующем комбинировании этого кода он оставался согласованным.

В объектно-ориентированном программировании понятие протокола часто объединяют с концепцией интерфейса13. Следует отметить, что это несколько ограничивает его: «набор правил», составляющих протокол, не обязательно должен относиться к одному классу, более того он может быть выражен в языке разными способами, примеры которых будут приведены ниже. В общем случае, протокол — это больше чем отдельный интерфейс.

Протоколы являются инфраструктурными компонентами языка, на основе которых могут строиться его «прикладные» модули. Таким образом в Common Lisp реализована объектная система CLOS (включая и описанный ранее механизм обобщённых функций), в основе которой лежит мета-объектный протокол (MOP), спецификации которого посвящена целая книга [2]. В основе системы обработки исключений — сигнальный протокол. Да и само ядро Лиспа, в определенном приближении, построено на протоколе манипуляции списками (во всяком случае это касалось первых реализаций языка). Также в Common Lisp можно выделить и другие протоколы, такие как, например: протокол функций по работе с последовательностями (sequences) и протокол множественных возвращаемых значений.

Протокол функций по работе с последовательностями представляет из себя набор именованных параметров, присутствующих во всех таких функциях, а именно: параметры key, test, test-not, from-end, start, end, а также неформальные правила их использования. Таким образом определяется удобный фреймворк для объединения последовательностей и функций высших порядков. Это очень простой пример, который даже не описан формально.

Протокол множественных возвращаемых значений — это набор форм языка, создающих инфраструктуру для того, чтобы функция могла вернуть больше одного значения, а вызывающая сторона могла распорядиться ими по своему усмотрению или же, вообще ничего не зная об этом, работать с основным значением. Таким образом, в том числе, устраняется многолетнее противоречие по поводу того, как возвращать ошибки из функции: с помощью кодов ошибок или исключений14, ведь в таком варианте можно вернуть как значение, так и код ошибки. Этот протокол составляют формы values и values-list, и несколько макросов (multiple-value-* (-bind, -list, ...), а также интеграция возможности возвращения нескольких значений в специальном операторе progn (который повсеместно используется в языке). Это пример протокола, поддержка которого требует вмешательства в ядро языка.

Как видите, эти протоколы не требуют для своей спецификации целой книги или даже статьи, более того, они определены неформально. Однако, продуманные протоколы приносят пользу как благодаря тому, что могут служить основой для построения более высокоуровневых абстракций, так и в качестве «лучших практик» реализации подобных вещей (это особенно применимо к протоколу работы с последовательностями). Можно привести достаточно примеров инфраструктурных библиотек для Common Lisp, использующих MOP: CLSQL, Elephant или же ранее упомянутая Filtered Functions). На основе сигнального протокола можно создать много интересных решений, об одном из которых мы рассмотрели ранее. Это одна из тех сфер в Лиспе, которые все еще остаются малоизученными и не задействованными полноценно.

«Протокольный» подход как основа построения схем межсистемного взаимодействия распространен не только в Лиспе. Тот же Redis использует эту концепцию для описания способа взаимодействия с клиентом; интересным «экстремальным» примером является рассмотрение системы контроля версий git как своеборазного протокола, на основе которого можно строить рабочий процесс разработки. Как было видно в примере из первой части статьи, Лисп дает возможность реализовать (продублировать) подобные протоколы.

Таким образом, протоколы — это не столько формальный прием или шаблон, сколько определенный взгляд на проектирование. Они могут быть реализованы в языке разными способами, вплоть до включения непосредственно в его ядро. В примере, который будет приведен далее, реализация протокола по сути мало чем отличается от описания интерфейса ISeq в языке Java (единственное, чего нельзя сделать в Java — это задействовать макросы для создания многоуровневых абстракций). Как и многие другие подходы, описанные в статье, протоколы — это прием, в той или иной степени доступный для использования в любом языке.

6.1  Практический пример: протоколы для последовательностей

Нельзя сказать, что в Common Lisp концепция протоколов учтена и реализована сполна. Несмотря на наличие определенного «протокола» работы с последовательностями, он не проработан до конца. Вот что пишет Питер Норвиг [4]:

Common Lisp находится в переходном положении между Лиспами прошлого и будущего. Нигде это так не заметно, как в функциях работы с последовательностями. Первые Лиспы имели дело только с символами, числами и списками. [...] Современные Лиспы добавили поддержку векторов, строк и других типов данных, и ввели понятие последовательности.

С новыми типами данных пришла проблема названий функций, которые ими оперируют. В некоторых случаях Common Lisp решил развить существующую функцию (length). В других старые имена были сохранены специально для функций манипуляции списками (mapcar) и для обобщённых функций над последовательностями(map) были придуманы новые имена. В третьих случаях новые функции были придуманы для операций над специфическими типами данных (aref). [...]

Еще большей проблемой оказалось то, что в определенном плане CLOS не был до конца интегрирован в язык, из-за чего существует разделение между стандартными классами (такими как типы последовательностей) и определяемыми пользователем. Выражаясь в объектно-ориентированных терминах, первые можно сравнить с финальными классами в Java (от которых нельзя унаследовать), а вторые — с открытыми классами в Ruby (с которыми можно сделать в общем-то все, что угодно). Это принято обосновывать необходимостью дать создателям реализаций языка определенное пространство для маневра для эффективной реализации ядра. Однако в Лиспе в отличие от некоторых других языков (вспомнить хотя бы примитивные типы в JVM или же Python, в котором как основа для наследования созданы специальные классы-обертки, типа UserDict для словарей или UserList для списков) подобные компромиссы c единообразностью не поощряются сообществом.

Описывая свою мотивацию для реализации языка Clojure в тесной привязке к JVM-платформе, его создатель Рич Хики написал следующее15:

Когда я смотрю на CL, я вижу подобную рефлексивную, полиморфную расширяемость только на уровне CLOS. CLOS реализован на более низкоуровневом языке (Lisp без CLOS, а этот Lisp в свою очередь на C или чем-то подобном), который не предоставляет полиморфной расширяемости. Clojure написан на языке, который предоставляет оную. Так что, например, first/rest в Clojure (и вещи, построенные на них) могут быть полиморфно расширяемы пользователями (в Clojure или Java), тогда как car и cdr во всех Лиспах, с которыми я знаком, не могут.

Справедливости ради нужно сказать, что проблема «неповсеместного» использования CLOS в качестве механизма для полиморфизма не является неразрешимой (так что вряд ли это можно признать основной причиной, почему Clojure появился на JVM — скорее, тут дело в перспективах этой платформы в индустрии). Во-первых, вполне практичным представляется использование описанного выше Python-подхода. Во-вторых, все же Lisp остается языком, в котором создаваемые пользователем конструкции почти всегда являются первоклассными объектами, существующими на равных правах с тем, что предоставляет сам язык. Поэтому есть и яркий практический контр-пример в этом случае — это FSet, Common Lisp-библиотека теоретико-множественных персистентных коллекций, эквивалентная (а в некоторых аспектах, даже более широкая) по своим возможностям библиотеке функциональных структур Clojure. При ее реализации активно использовался механизм затенения имен (shadowing), который можно применять в том числе и к стандартной библиотеке языка. Таким образом автор смог создать полноценный протокол манипуляции такими структурами данных, используя необходимые ему имена и абстракции (библиотека основанна на обобщённых функциях) в рамках языка.

Еще одним примером расширяемости, о котором говорит Хики, является реализованный в Clojure SEQ-протокол итерации над абстрактными последовательностями (те самые полиморфные first/rest). В его основе идея об отказе от привязки концепции «списка» к конкретным аспектами реализации на основе cons-ячеек, а рассмотрение его как абстрактного интерфейса. Используя такой подход, можно программировать обобщённые алгоритмы, которые смогут работать с любыми конкретными структурами, реализующими SEQ-интерфейс.

Впрочем, SEQ-протокол нетрудно реализовать и в Common Lisp, используя механизмы расширения, которые предоставляет язык. Пример такой реализации приводится ниже. Для экономии места она представлена только для двух конкретных структур данных: последовательностей (к которым в CL относятся список и разные варианты векторов) и хеш-таблиц, — как для принципиально разных типов коллекций. Протокол основывается на классе-обертке seq, который создается вызовом обобщённой функции seq на экземпляре конкретной или абстрактной (SEQ) коллекции, а также обобщённых функциях head, tail и next, которые возвращают первый элемент коллекции, ее хвост, а также следующий элемент при итерации, удаляя его из коллекции (aналог pop для списков). Кроме того, определены такие вспомогательные функции, как seqp, отвечающая на вопрос, является ли объект экземпляром класса seq, into для преобразования из конкретной коллекции в абстрактную и обратно, а также elm для получения элемента коллекции по ключу (для последовательностей ключ — это порядковый номер элемента).

Ниже для примера приведены некоторые классы и функции ядра подобного SEQ-протокола (в общей сложности его реализация заниманием 100 строк кода).

(defclass seq () ((ref :initarg :ref :reader ref :documentation "reference to the underlying concrete data-structure") (pos :initarg :pos :initform 0 :accessor pos :documentation "current postion in REF, used for copying by reference") (itr :initarg :itr :initform (error "ITR should be provided") :documentation "iterator closure, which returns 2 values: value and key (for simple sequences key is number); when end is reached should just return nil (no errors)") (kv? :initarg :kv? :initform nil :documentation "wheather keys are meaningful for the collection (e.g. for hash-tables they are)")) (:documentation "A wrapper around a concrete data structure for use in SEQ protocol.")) (defgeneric head (coll) (:documentation "Return first element of a collection COLL. 2nd value: it's key (for sequences key is the number)") (:method ((coll sequence)) (values (first coll) 0)) (:method ((coll hash-table)) (with-hash-table-iterator (gen-fn coll) (multiple-value-bind (valid key val) (gen-fn) (when valid (values val key))))) (:method ((coll seq)) (with-slots (pos itr) coll (funcall itr pos)))) (defgeneric next (coll) (:documentation "The analog of POP. Return the first element of COLL and remove it from the top of COLL. For SEQ it's done in functional manner, while for concrete types the removal may be destructive.") (:method ((coll list)) (values (pop coll) 0)) (:method ((coll hash-table)) (with-hash-table-iterator (gen-fn coll) (multiple-value-bind (valid key val) (gen-fn) (when valid (remhash key coll) (values val key))))) (:method ((coll seq)) (multiple-value-prog1 (head coll) (incf (pos coll)))))

На этой основе далее можно создавать различные высокоуровневые конструкции для итерации. Например doseq — это простой макрос в духе dolist:

(defmacro doseq ((var-form coll &optional result) &body body) "The analog of DOLIST for any COLLection, which can be put in a SEQ. VAR-FORM can be either ATOM, in which case this name is bound to the value (1st), returned by NEXT, or LIST, in which case the first symbol will be bound to the 1st value (value), returned by NEXT, and the 2nd - to the 2nd (key). If RESULT form is provided, its value will be returned." (with-gensyms (gseq key val) `(let ((,gseq (seq ,coll))) (loop ;; first we obtain VAL and KEY separately (multiple-value-bind (,val ,key) (next ,gseq) ;; and then bind them to the VAR-FORM (multiple-value-bind ,(mklist var-form) (values ,val ,key) (if ,key (progn ,@body) (return ,result))))))))

Пример его применения:

CL-USER> (doseq (v (seq '(1 2))) (print v)) 1 2

Стоит отметить, что основная задача SEQ-протокола — это дать возможность единообразной итерации на разных конкретных коллекциях. Но он не призван решать проблему аккумуляции значений в процессе итерации. Точнее, такая проблема просто не стоит: можно спокойно использовать список как самую простую и эффективную структуру для этой цели, а затем преобразовывать его в требуемый конкретный тип при наличии такой необходимости (например, с помощью операции into). Вполне можно определить аналог операции cons в семантике Clojure, но ее использование будет достаточно неэффективным: на каждой итерации прийдется выполнять generic-диспечеризацию (в Clojure это неизбежно, а вот в Common Lisp у нас есть выбор). Для формализации использования предложенного выше подхода с аккумуляцией в список был создан макрос with-acc:

(defmacro with-acc ((var-form acc-name coll &optional result-type) &body body) "Iterate over COLL with accumulation to list and conversion INTO either RESULT-TYPE or TYPE-OF COLL itself. VAR-FORM can be either ATOM, in which case this name is bound to the value (1st), returned by NEXT, or LIST: the first symbol will be bound to the 1st value (value), returned by NEXT, and the 2nd - to the 2nd (key). If RESULT form is provided, it's value will be returned." (with-gensyms (gseq) `(let ((,gseq (seq ,coll))) (into (or ,result-type (ref ,gseq)) (with-output-to-list (,acc-name) (doseq (,var-form ,gseq) ,@body))))))

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

(defun filter (fn coll) "Sequentially apply FN to all elements of COLL and return the collection of the same type, holding only non-null results" (let ((seq (seq coll))) (with-slots (kv?) seq (ref (with-acc ((v k) acc seq) (when-it (funcall fn v) (when kv? (push k acc)) (push it acc)))))))

На примере реализации SEQ-протокола снова хорошо видно, каким образом в Лиспе принято строить высокоуровневые абстракции: в их основе лежит ортогональный набор базовых операций и структур данных, на которые затем уровень за уровнем наслаиваются новые абстракции. Именно так реализован и сам язык [1].

Впрочем, это не последний вариант протокола, созданного вокруг последовательностей и итерации: на самом деле, в CL их еще несколько! Одной из более общих альтернатив является библиотека ITERATE. Ее основная цель — исправить недостатки, присущие другому, более древнему, квази-протоколу итерации LOOP, а именно:

В отличие от LOOP, ITERATE, как и любой полноценный протокол, предоставляет механизм пользовательского расширения — это макросы defclause и defdriver-clause. Попробуем использовать второй из них для интеграции нашего SEQ-протокола с ITERATE-макросом — это весьма несложно:

#+:iter (defdriver-clause (:FOR var :SEQ coll) "Iterate over COLL as a SEQ." (with-gensyms (gseq k v) `(progn (:with ,gseq := (seq ,coll)) (:for ,var :next (multiple-value-bind (,v ,k) (next ,gseq) (if ,k ,v (:terminate)))))))

И в качестве примера использования этого нового драйвера можно привести такой простейший код:

CL-USER> (iter (:for item :seq #{:a 1 :b 2}) (print item)) 1 2

Вот мы и пришли к протокольно-ориентированному программированию! Кстати, кроме шуток: как раз в Clojure недавно была предложена такая концепция, как defprotocol, позволяющая формулировать группы интерфейсов (вроде SEQ) как протоколы, в общем случае без привязки к конкретному классу. Вот так и происходит развязывание полиморфизма и наследования16.

Примечание: в последних фрагментах кода использованы некоторые синтаксические расширения Common Lisp, которые я использую в своей работе, и которые для себя может произвести любой программист. В частности, это анафорический макрос when-it, литеральный синтаксис для чтения хеш-таблиц #{} и анонимных функций #`. Кроме того, продемонстрирована возможность Common Lisp, позволяющая одновременно использовать класс, функцию и переменную с одним и тем же именем seq17, и использован стандартный макрос чтения #+, который позволяет выполнять код условно в зависимости от наличия определенных ключевых слов в списке возможностей (features) данного программного образа. Поскольку библиотека ITERATE является инфраструктурной, она добавляет индикатор своего присутствия, чтобы об этом «знали» другие библиотеки и могли задействовать её через механизм #+. Таким же образом объявляет себя конкретная реализация (например, :sbcl), указывается, загружены ли некоторые важные компоненты среды (например, :sb-thread), какая у нас операционная система (например, :win32 или :posix), вплоть до того, что это среда конкретного программиста (например, :vseloved). Кстати, механизм #+ позволяет проверять не только на наличие отдельных свойств, но и на булевые предикаты от них.

7  Заключение: с расширяемостью в уме

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

Если рассмотреть каждый отдельный язык, то, как правило, можно найти его объединяющую идею. На ее основе принимаются ключевые решения на всех уровнях языка: от высокоуровневой архитектуры до подхода к реализации конкретных технологий. Для Common Lisp объединяющей идеей на данный момент является как раз расширяемость. Это, кстати, ключевое различие между Common Lisp и Scheme, которое на данный момент разделяет эти два направления развития изначальной Лисп-идеи. Это не значит, что Scheme — не расширяемый язык, наоборот его возможности в этом плане хорошо иллюстрирует [3]. Но это не является на данный момент ключевым свойством, на который делается упор при развитии языка. Также это тот критерий, по которому язык Clojure, хотя он и взял некоторые черты от Scheme, относится все-таки к Лисп-направлению.

Еще одним языком, который в основе своей поставил расширяемость, является Java. И в этом смысле интересно сравнить эти два направления развития. Java известна своей многословностью и церемониальностью, она не имеет практически никаких средств для синтаксической абстракции. В то же время у нее есть и сильная сторона, а именно пронизывающая весь язык модель семантической расширяемости через интерфейсы. Так что в общем-то не удивительно, что язык Clojure появился именно на Java-платформе, так же как многие другие языки в свое время вышли из Lisp-платформы (самый яркий пример тут, пожалуй, Smalltalk).

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

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

В этом смысле показателен пример Python, известного своим девизом «Батарейки в комплекте», который подразумевает наличие в стандартной библиотеке (почти) всего, что нужно для разработки. В нём также существует развитая традиция фреймворков: от Zope и Django для веб до Numpy и Scipy в научной среде. Обратная сторона медали тут отмечена в другой цитате: «Пакет, который попадает в стандартную библиотеку, стоит одной ногой в могиле»19. Также к таким языкам (среди тех, с которыми мне приходилось иметь дело) мы бы по разным причинам отнесли C, C++, PHP и JavaScript.

Для создания удобной инфраструктуры библиотек важны такие свойства, как возможность четкого разделения внешнего API и реализации (и его декларативного описания), для описания компонент системы, средства управления зависимостями (в том числе управления версиями, чтобы не попадать в ситуацию типа «DLL hell»), а также учета особенностей прикладной платформы (включающей аппаратную платформу, ОС и конкретную реализацию языковой среды).

В Common Lisp для этого используются следующие технологии:

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

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

Список литературы

[1]
Paul Graham. The roots of lisp, 2001.
[2]
Daniel G. Bobrow Gregor Kiczales, Jim des Rivieres. The Art of the Metaobject Protocol. 1991.
[3]
Jerald Sussman Harold Abelson. Structure and Interpretation of Computer Programs, second edition. 1996.
[4]
Peter Norvig. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp. 1992.
[5]
Kent M. Pitman. Condition handling in the lisp language family. 2001.
[6]
Eric S. Raymond. The Art of Unix Programming. 2003.
[7]
Peter Seibel. Practical Common Lisp. 2006. Есть русский перевод: http://lisper.ru/pcl/.
[8]
Роман Душкин. Полиморфизм в языке Haskell. 2009.

1
«Мы целились в программистов на C++, и у нас получилось затащить многих из них примерно примерно на полпути к Лиспу», Guy Steele о Java, http://en.wikiquote.org/wiki/Lisp_programming_language
2
Полностью он доступен по адресу: http://github.com/vseloved/cl-redis
3
Generic functions — основной инструмент полиморфизма в Common Lisp. Они представляют собой исполняемый объект, который обеспечивает диспетчеризацию (выбор конкретного метода выполнения) в зависимости от типа или значения входных аргументов.
4
http://http://www.faqs.org/docs/artu/ch09s01.html
5
Более того, хотя он и считается одним из трех «китов» ООП, но в чистом виде (без задействования наследования) полиморфизм в обычных ОО-языках не возможен. Это хорошо видно на примере языка JavaScript, который отказался от основанного на классе наследования в пользу прототипной передачи свойств, и таким образом полностью потерял ОО-полиморфизм.
6
http://mshare.tw/
7
В текущей версии (1.2) он не умеет использовать виртуальную память, т. е. весь кеш находится в оперативной памяти и при выходе размера БД за пределы физического объема оперативной памяти работа сервера становится непредсказуемой из-за свопинга.
8
Разделение на базовый тип и класс в данном случае условно. Под этим не подразумевается такое разделение, которое есть в Java между примитивными и объектными типами.
9
Код доступен по адресу: http://github.com/vseloved/cl-parsec.
10
Ограничения, накладываемые на парсеры в силу особенностей самой предметной области, описаны далее.
11
Я так и не смог понять, каким образом с этим справляется Parsec: то ли собственно потоки имеют в Haskell другую семантику, то ли за счет механизма, подобного описанной здесь реализации.
12
Если формулировать это как проблему безопасности, то решение ее должно быть глобально для всего кода. В Lisp’е как динамическом языке есть очень много возможностей вмешательства помимо этой: например, переопределения функций.
13
http://en.wikipedia.org/wiki/Protocol\_(object-oriented\_programming)
14
http://www.joelonsoftware.com/items/2003/10/13.html
15
http://groups.google.com/group/comp.lang.lisp/msg/570cc2eaadea36af
16
Можно также провести параллель между defprotocol и классами типов в Haskell.
17
То, что во введении названо свойством «Лисп-N».
18
Прим. ред. — несмотря на то, что маркетинговые обещания JavaBeans действительно никогда не были в полной степени реализованы, эта технология повсеместно используется в Java-окружении и является частью любого сколько-нибудь серьезного фреймворка.
19
http://tarekziade.wordpress.com/2010/03/03/the-fate-of-distutils-pycon-summit-packaging-sprint-detailed-report/

Этот документ был получен из LATEX при помощи HEVEA