пятница, 30 апреля 2010 г.

Парсим reStructuredText на Common Lisp. Часть 1.

Читая регулярно Russian Lambda Planet можно увидеть описания всевозможных грамматик, парсер-комбинаторов (или как там они называются) и прочих вещей, о которых мне даже думать страшно. Впрочем, наверно не одному мне, ибо в реальных проектах на php и python, которые я просматривал, ничего подобного не используется, а используется весьма простой и эффективный метод, основанных на регулярных выражениях и "машине состояний", позволяющий удобно сочетать описание грамматики с помощью рег. выражений с вставками произвольного кода. Мне, кстати, попадалось утверждения (которое я не могу не подтвердить, не опровергнуть, ибо абсолютно не разбираюсь в этих вопросе), что все эти грамматики бесполезны для разбора wiki-разметок. Так вот, поскольку у меня есть проблемы с математическим образование, то приходиться парсить по "быдлокодерски" ;)

Почему reStructuredText
Я имею большое желание начать писать мануал для RESTAS, но в мире Common Lisp нет инструмента для документирования, который бы меня устроил. С другой стороны, мне очень нравиться как сделана документация на Django, да и вообще, в мире Python с документированием всё нормально. Документация к Django основана на Sphinx, который использует reStructuredText, поддержку которого обеспечивает пакет docutils. А почему бы не реализовать соответствующий функционал для Common Lisp? Правда, я нашёл пакет cl-docutils, но его размер (около 10 000 строк кода) меня сильно смутил - ну зачем может потребоваться столько строк кода для решения подобной задачи??? Так что решил делать сам (у меня всяко столько кода не будет).

Моя система
Я уже пару раз рассказывал, что мой подход (библиотека wiki-parser) к парсингу (который я опробовал в restas-wiki и cl-closure-template) основан на подходе, подсмотренном в исходниках Dokuwiki, который я правда переработал с учётом возможностей Common Lisp, так что мне кажется, что он стал значительно мощнее. Итак, сначала объявим парсер:
(wiki-parser:define-parser #:wiki-parser.re-structured-text
(:use #:cl #:iter)
(:export #:paragraph))

(in-package #:wiki-parser.re-structured-text)

(define-toplevel-mode
(:allowed :formatting :sections :paragraphs))

(defmethod wiki-parser:parse ((markup (eql :re-structured-text)) (obj string))
(wiki-parser:parse #.*package* obj)))
Макрос define-parser создаёт новый пакет и проводит некоторую его инициализацию - данный подход, когда пакет используется в качестве объекта, я использую также и в RESTAS - это позволяет легко разбить описания синтаксиса на множество отдельных форм (вместо этих огромных простыней, которые можно наблюдать, например, в коде на базе cl-yacc).

Макрос define-toplevel-mode совершенно необходим и определяет какие режимы доступны в начальном состоянии, смысл их стане ясен чуть позже.

Метод wiki-parser:parse используется для непосредственного разбора текста.

Теперь, опередить правила для разбора, например, strong-элемента (например, "*Hello world*") можно чрезвычайно просто:
(define-mode strong (80 :formatting)
(:allowed :formatting)
(:not-allowed strong)
(:entry "\\*\\*(?=.*\\*\\*)")
(:exit "\\*\\*"))

CL-USER> (wiki-parser:parse :re-structured-text
"**Hello world**")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:STRONG "Hello world"))
Напомню, что парсер обеспечивает машину состояний и здесь макрос define-mode определяет режим для разбора strong-режима. Его параметры означают следующее
  • strong - название режима. Во-первых, оно фигурирует в результате разбора (как можно увидеть в примере), во-вторых - может использоваться при описании других режимов.
  • 80 - приоритет, регулярные выражения для всех определённых режимов собираются в одно регулярное выражение и с помощью приоритета можно (нужно) управлять очередность проверок.
  • :formatting - означает, что данный режим входит в группу :formatting. Например, выше в макросе define-toplevel-mode я указывал разрешённые режимы в начальном состоянии.
  • (:allowed :formatting) - означает, что внутри данного режима разрешены режимы из группы :formatting. Можно указать несколько групп или отдельных режимов. Легко заметить, что группы обозначается с помощью :keyword, а отдельный режим простым символом
  • (:not-allowed strong) - исключает режим strong из списка разрешённых состояний внутрирежима.
  • (:entry "\\*\\*(?=.*\\*\\*)") - регулярное выражение, позволяющее найти начало режима и убедиться, что он имеет правильное завершение
  • (:exit "\\*\\*") - регулярное выражения, определяющее завершение режима
Мне кажется, что всё предельно просто.


В разметках часто встречаются элементы, которые не имеют начального и завершающего "признака", например, надо опознавать простые гиперссылки. Это можно следующим образом:
(define-mode standalone-hyperlink (330 :formatting)
(:special "(?:ht|f)tp(?:s?)://[0-9a-zA-Z](?:[-.\\w]*[0-9a-zA-Z])*(?::(?:0-9)*)*(?:/?)(?:[a-zA-Z0-9\\-\\.\\?\\,/\\+&%\\$#\\*]*)?"))
Здесь тэг :special используется для описания регулярного выражения, которое позволяет "выкусить" кусок текста целиком:
CL-USER> (wiki-parser:parse :re-structured-text
"http://www.lisp.org/")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:STANDALONE-HYPERLINK "http://www.lisp.org/"))
В разметке reStructuredText широко используются ссылки, которые формируются следующим образом: Python_ или `Common Lisp`_. Здесь видно, в первом варианте отсутствует признак начала режима. Для разбора подобных элементов (в разметке reStructuredText используется несколько вариантов ссылок) я используют такой код:
(defun trim-backquotes (str)
(let ((last (1- (length str))))
(if (char= #\`
(char str 0)
(char str last))
(subseq str 1 last)
str)))

(define-mode reference (70 :formatting)
(:special "`.*`_"
"[^\\s]+_")
(:post-handler (item)
(let* ((str (second item)))
(list 'reference
(trim-backquotes
(subseq str 0 (1- (length str))))))))
Здесь тэг :post-handler используется для описания функции, которая должна быть вызвана для финальной обработки распарсенного элемента:
CL-USER> (wiki-parser:parse :re-structured-text
"Python_")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:REFERENCE "Python"))

CL-USER> (wiki-parser:parse :re-structured-text
"`Common Lisp`_")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:REFERENCE "Common Lisp"))
После описания всех режимов в конец файла необходимо вставить вызов (init-parser), который произведёт инициализация парсера. При определении какого-либо режима в Slime с помощью C-M-x (не С-с С-с) - данный вызов будет производиться автоматически.

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

четверг, 29 апреля 2010 г.

cl-mssql-0.0.2

Поскольку у меня возникла по работе необходимость писать в MS SQL (ранее я только читал оттуда), то добавил к пакету функцию mssql:execute и поддержку транзакций (путём тривиальной адаптации кода из postmodern).

По-прежнему, для развития проекта ищется человек, который имеет более серьёзные чем я потребности по работе с MS SQL из Common Lisp (из под Linux).

вторник, 27 апреля 2010 г.

Обновил lisper.ru

Провёл больше обновление кода на lisper.ru. Функциональность должна остаться той же самой, но реализация многих вещей сильно изменилась. Сейчас код на сайте соответствует коду в git.

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

P.S. И да, я НЕНАВИЖУ Debian, особенно тамошний common-lisp-controller.

Уф... restas-forum

Взял таки себя в руки, нашёл мотивацию и доделал restas-forum - версию форума, используемого на lisper.ru, теперь это отдельный пакет, а соответствующий код полностью удалил из исходников rulisp. И чё было так тянуть (эх, мотивация), там то работы... Без интерфейса к БД (которая не входит в состав, сейчас есть реализация только для lisper.ru) размер исходного кода (CL-части) - примерно 200 строк. Ну да ладно. Теперь вот осталось только перенести это на боевой сервер, возможно сделаю этой ночью.

пятница, 23 апреля 2010 г.

Локальная memoization в RESTAS

Memoization - мощная техника оптимизации/кэширования, когда результат функции сохраняется и в последующем используется вместо повторного вычисления функции. Изначально, я планировал использовать эту технику для построения каркаса для кэширования в рамках RESTAS (впрочем, когда я размышлял об этом, то ещё не знал этого термина). Правда, для кэширования в веб-приложениях данный подход должен быть модифицирован: функции, которые всегда для одних и тех же входных данных возвращают один и тот же результат на практике являются экзотикой, а вот функции удовлетворяющие этому условию в течении некоего ограниченного промежутка времени встречаются весьма регулярно. Т.е. имеет смысл говорить об memoization, которая ограничена по времени, я даже придумал термин - soft memoization :) В общем, я погрузился в размышления как совместить всё это с ключевыми проблемами кэширования:
  • Контролем за размером кэша
  • Устареванием кэша
  • Согласованностью кэша
  • Проблемой согласованного доступа
И решил посмотреть что на тему memoization есть в мире Common Lisp. Нашёл пару пакетов, которые реализуют дизайн, предложенный ещё Peter Norvig и понял, почему эта техника практически не применяется. Шутка в том, что дизайн от Peter Norvig основан на возможностях Common Lisp (предлагается динамически мемоизировать уже существующие функции за счёт манипуляций с symbol-function) и при этом мало совместим с реальной практикой программирования на Common Lisp :) Действительно, применять memoization для тривиальных случаев не очень интересно, а memoization для функций, зависящих от других просто опасно - интерактивное переопределение какой-либо функции может скомпрометировать все ранее вычисленные результаты. Размышляя на тему возможности отслеживания зависимостей (например, с помощью sb-introspec) и пришёл к выводу, что практически полезное решение построить не так уж и просто и необходима более тщательная проработка.

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

Просматривая в очередной раз разделы посвященные кэшированию в книге "Профессиональное программирование на PHP" от Джордж Шлосснейгл я обнаружил, что он рассматривает в том числе memoization (правда, не использует данный термин) и показывает, что данная техника может быть весьма полезна даже без сохранения мемоизированных данных между запросами (хм, я был удивлен, интересно, как часто в литературе по PHP можно встретить сравнительный анализ эффективности алгоритмов "хвостовая рекурсия" vs. memoization? в этой книге это есть!). Т.е. подход, при котором memoization локальна относительно обработчика запроса является полезной, просто реализуемой и не имеет серьёзных проблем, связанных с возможность компрометации данных в результате изменения среды.

Именно это я сейчас и реализовал. Для каждого запроса поддерживается своя *memotable*, в которой сохраняются результаты вызовов функций, объявленных с помощью restas:define-memoized-function, что позволило исключить многократную расшифровку cookie достаточно общим способом.

вторник, 20 апреля 2010 г.

Асинхронный веб

Поскольку я имею твердое желание фокрнуть Hunchentoot (при удобном случае), то обдумываю эту возможность в "фоновом режиме". Ниже кое-какие соображения.

Сейчас много пишут про использование асинхронного ввода/вывода в контексте веб приложений и всячески расхваливают event model, которая позволяет добиться небывалых высот производительности, ну и конечно, nginx как главный флагман и пример для подражания, а Apache как главный враг прогрессивного человечества. Но кажется, что "не всё в порядке в Датском королевстве" (с) :) Итак, по порядку, как известно Apache при обслуживании действительно большого количества одновременных соединений сталкивается со следующими основными проблемами:
  • Большое количество процессов/потоков требует существенного объёма памяти для самого факта своего существования
  • Постоянное переключение контекста между большим количеством процессов/потоков приводит к тому, что львиная часть системных ресурсов тратиться именно на переключение контекста
  • Используемый блокирующий ввод/вывод приводит к постоянным и довольно дорогостоящим операциям замораживая/размораживания, что при рассматриваемых масштабах также превращается в существенную проблему
  • Усугубляет ситуацию тот факт, что один процесс/поток полностью обслуживает одно соединение и не завершается до тех пор, пока соединение не будет закрыто. А это значит, что если к ресурсу присоединяется большое количество клиентов с медленными каналами, то они существенно повышают общую нагрузку на систему даже если выполняемые для них запросы были очень простыми и лёгкими
Решения на базе event model используют асинхронный ввод/вывод, что позволяет производить обработку запросов в одном (в случае одного ядра) потоке и максимально задействовать мощности процессора именно для выполнения полезной работы (а не обслуживания системы). Это обеспечивается за счёт поддержки современными системы вызовов наподобие epoll, которые очень хорошо масштабируются даже на очень большого количества соединений. Жизнь прекрасна?

Как бы не так. По-факту, "хвалёный" nginx используется в основном как front-end к "проклятому" Apache. Подобная схема позволяет задействовать многие из преимуществ nginx, но реальная обработка запросов по прежнему ведётся в отдельных процессах/потоках. Думается, что данная ситуация обусловленная следующими причинами:
  • Большинство средств для работы с базами данных работают в синхронном режиме, а значит их нельзя использовать в рамках одно-поточной обработки. Собственно, дело не только в базах данных, но это самый характерный пример.
  • event model - это БОЛЬ, программирование в подобном режиме значительно сложнее традиционного подхода, используемого при разработке веб-приложений. Я, помнится, изрядно помучился с подобных подходом при разработке GUI. Скажем, если нужно было на основе пользовательского ввода нарисовать какую-нибудь замысловатую фигуру, т.е. обработать последовательность связанных пользовательских действий (например - щелчков мышкой), сопровождая их различными свиристелками (подсказками и прочими визуальными эффектами), как одну операцию. При программировании с помощью MFC мне пришлось практический сразу отказаться от стандартной карты событий и реализовать свой диспетчер, работавший в режиме конечного автомата. Но и этого было мало. Самым эффективным и удобным был подсмотренный мной в недрах MFC приём (позже я сталкивался с ним при работе с Autocad) по организации собственного локального цикла выборки сообщений (он начинался в начале операции построении фигуры и заканчивался в её конце) с целью создать хоть какую-то иллюзию синхронного режима работы. В этой связи, мне кажется, что предложение распространить схожие подходы на широкий круг веб-приложений заранее обречено на провал и я этому буду только рад.
Я хочу, что бы веб-сервер Hunchentoot обеспечивал высокую производительность на основе существующих современных подходов, но при этом был бы удобным инструментом для разработки веб-приложений. Т.е. есть желание эффективно совместить асинхронный ввод/вывод с возможностью писать обработчики в традиционном синхронном виде.

Простая модель обработки запроса, которую я буду рассматривать далее:
  • Сервер получает запрос
  • Вызывает обработчик, который сначала производит какую-то предварительную его обработку,
  • затем делает запрос к базе данные,
  • на основе полученных данных формирует ответ,
  • и отправляет его клиенту
Первая идея заключается в том, чтобы освободить обработчик запроса от блокирующего ввода/вывода, связанного с обработкой протокола HTTP: сервер асинхронным образом полностью считывает запрос и только после этого вызывает (в отдельном потоке) обработчик, который формирует ответ в памяти, отдаёт его серверу и на этом завершается, сервер отправляет ответ клиенту асинхронным образом. Подобная схема отвязывает длительность жизни потока-обработчика от ширины канала и возможного наличия "медленных" клиентов. Но что делать с базой?

Для начала идеальный вариант (основанный на том, что postmodern это "pure lisp" реализация сокетного протокола взаимодействия с PostgreSQL, а значит её можно относительно легко приспособить/пропатчить для нужного поведения): при выполнении запроса к базе выполнение код обработчика запроса прерывается, поток обработчика начинает выполнять какую-нибудь другую работу (обрабатывает другие запросы), взаимодействие с базой производиться на основе асинхронного ввода/вывода, а после его завершения в удобный момент работа обработчика запроса возобновляется с прерванного места. Описанное уж очень сильно напоминает "продолжения" и будь для Common Lisp чистая (в смысле, без граблей) и эффективная реализация "продолжений", то вкупе с первым пунктом можно было бы обеспечить высокоэффективную одно-поточную обработку запросов, выжав из железа и инвесторов максимум возможного ;) Но... Продолжений в Common Lisp нет. Я знаю про cl-cont и т.п., но во-первых - это грабли, во-вторых - грабли с набором ограничений, в-третьих - грабли с высокими накладными расходами. Если разбираться внимательней, то напрашивающиеся "продолжения" в описанной схеме выполняют одну единственную функцию - переключение контекста выполнения. Но разве не для этого же нужны потоки? А почему переключение контекста с помощью кода, реализованного средствами языка, должно быть более эффективным, чем переключение контекста средствами ядра операционной системы, которая задействует для этого особенности современных архитектур? Тут можно было бы вспомнить про green threads, которые способны обеспечить дешёвое переключение контекста, но для многоядерных систем нужны и нативные треды, а поддержка и тех и тех есть, кажется, только в Allegro CL, так что об этом варианте можно даже особо не размышлять. Ценители, конечно, укажут не Erlang, но это определённо не тот язык, на котором я бы хотел писать на постоянной основе. Допускаю, что Erlang можно терпеть, когда очень надо, как приходиться порой терпеть C. Но позиционировать данный язык как основной - извините.

Самая страшная страшилка для модели "поток на соединение" описывается как "10 000 одновременных запросов", что будет с системой, имеющий 10 000 потоков? Ответ, в общем-то, не так однозначен, но похоже в этом заключается суть: а зачем нам нужно 10 000 одновременных потоков? Очевидно, что всегда имеется какое-то разумное количество потоков, которые имеет смысл держать в системе и их количество, вероятно, коррелирует с числом ядер + числом запросов, которые может эффективно обрабатывать база данных. Ну да, надо учитывать, что база данных является не единственным подобным ресурсом, есть ещё всякие распределённые кэши или там очереди сообщений, но сути это не меняет. Суть: систему всегда можно "нагрузить" образом, близким к "оптимальному". В общем, в данный момент я вижу следующие аспекты, которые необходимо разрешить для превращений Hunchentoot в удобный и высокопроизводительный веб-сервер:
  • Асинхронная обработка протокола HTTP
  • Каркас для выполнения асинхронных операций в рамках синхронного потока выполнения
  • Балансировщик нагрузки, способный поддерживать оптимальную количество потоков и их статус в зависимости от характеристик железа и выполняемых ими задач
Вроде всё просто, осталось только реализовать ;) Ну и ещё не помешало бы много критики.

среда, 14 апреля 2010 г.

RESTAS и карта сайта

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

#<ROUTES:MAPPER {EE36869}>
--------------------

Tree of routes
--------------------------------------------------

rulisp:main
apps/
rulisp:tools-list
format/
restas.colorize:main
all restas.colorize:list-pastes
create/
restas.colorize:create-paste
restas.colorize:save-paste
restas.colorize:preview-paste
css/$file restas.colorize:css
$id restas.colorize:view-paste
articles/
restas.wiki:wiki-main-page
css/$file restas.wiki:css
edit/$page/
restas.wiki:edit-wiki-page/post
restas.wiki:edit-wiki-page
history/$page/
restas.wiki:history-wiki-page
$time restas.wiki:view-archive-wiki-page
$page/
pdf restas.wiki:view-wiki-page-in-pdf
restas.wiki:view-wiki-page
files/*path restas.directory-publisher:route
forgot/
restas.simple-auth:forgot/post
restas.simple-auth:forgot
forum/
restas.forum:list-forums
css/*path restas.directory-publisher:route
thread/$topic-id restas.forum:topic-message-replies
$forum-id restas.forum:list-topics
login/
restas.simple-auth:login/post
restas.simple-auth:login
logout restas.simple-auth:logout
pcl/
rulisp.pcl:pcl-main
pcl.pdf rulisp.pcl:pcl-pdf
pdf/$chapter rulisp.pcl:pcl-chapter-pdf
$chapter rulisp.pcl:pcl-chapter-view
planet/
restas.planet:planet-main
atom.xml restas.planet:planet-atom
$file restas.planet:planet-resources
register/
confirmation/$invite/
restas.simple-auth:accept-invitation
restas.simple-auth:accept-invitation/post
restas.simple-auth:register/post
restas.simple-auth:register
reset-password/$mark/
restas.simple-auth:reset-password/post
restas.simple-auth:reset-password
wiki/
restas.wiki:wiki-main-page
css/$file restas.wiki:css
edit/$page/
restas.wiki:edit-wiki-page/post
restas.wiki:edit-wiki-page
history/$page/
restas.wiki:history-wiki-page
$time restas.wiki:view-archive-wiki-page
$page/
pdf restas.wiki:view-wiki-page-in-pdf
restas.wiki:view-wiki-page
*path restas.directory-publisher:route

Reset route map
Здесь наглядно видно дерево маршрутов. Переменные шаблонов подсвечиваются и показываются с префиксами $ и * (для wilcard переменных). Каждую переменную также можно исследовать, например, что бы увидеть с помощью какой функции производиться парсинг переменной. В конце каждого листа этого дерева находиться объект-маршрут, нажав на нём "." можно перейти к месту определения маршрута, а Enter позволит исследовать его более детально (какой HTTP-метод обрабатывает, какие для него проводятся дополнительные проверки и т.п.). Таким образом, данный функционал позволяет исследовать и лучше понять как именно идёт обработка запроса и также может использоваться для простой, ориентированной на специфику веб-приложений, навигации по коду.

пятница, 9 апреля 2010 г.

puri-unicode

В общем, я не стал продолжать дискуссию с Kevin Rosenberg по поводу включения моего патча для поддержки UTF-8 (ему это, в конце концов, не очень нужно) и просто решил, что буду поддерживать альтернативный пакет - puri-unicode.

Внёс соответствующие изменения в свой форк gentoo-lisp-overlay: добавил пакет dev-lisp/puri-unicode, добавил virtual/puri и изменил зависимости для пакетов с dev-lisp/puri на virtual/puri. Если где что упустил - пишите.

среда, 7 апреля 2010 г.

virtual/slime

В свой форк gentoo-lisp-overlay добавил пакет app-emacs/slime-archimag - мой форк slime, он будет нужен в последующем для интеграции restas с emacs. Поскольку, очевидно, app-emacs/slime и app-emacs/slime-archimag не совместимы между собой, а от app-emacs/slime зависят dev-lisp/atdoc и dev-lisp/arnesi, то также добавил virtual/slime и изменил зависимости для этих пакетов.