пятница, 22 января 2010 г.

Монадические макросы для Common Lisp

Изобрел монадические макросы для Common Lisp и оформил их в виде пакета cl-monad-macros. На мой взгляд, получилась довольно интересная вещь, основным достоинством которой является высокая эффективность генерируемого кода. Здесь было бы интересно посостязаться с хаскелевскими компиляторами. Потом поместил объявление на comp.lang.lisp.

Основная идея состоит в том, что мы задаем монадические макросы типа WITH-MONAD, которые внутри себя через MACROLET определяют унифицированные макросы UNIT, FUNCALL!, LET! и PROGN!. Макрос UNIT – это хасклевская функция return, FUNCALL! – это bind с обратным порядком параметров (=<<), LET! – альтернатива стрелке, а PROGN! – замена хаскелевского then (>>). Причем LET! по виду похож на стандартный LET*, а PROGN! – на стандартный PROGN. Более того, в случае монады Identity (макрос WITH-IDENTITY-MONAD) макрос LET! совпадает с LET*, PROGN! – с PROGN, FUNCALL! – c FUNCALL, а UNIT становится эквивалентным обычной функции IDENTITY. Все это позволяет писать код в единой нотации – меняем только монадические макросы типа WITH-MONAD.

Например, макрос WITH-LIST-MONAD задает монаду List. Следующая функция возвращает все возможные перестановки заданного списка.

(defun perms (xs)
  (with-list-monad
      (if (null xs)
          (unit nil)
          (let! ((y xs)
                 (ys (perms (remove y xs :count 1))))
                (unit (cons y ys))))))

Функцию можно протестировать:

CL-USER> (perms '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

По своей сути LET!  – это обобщенный случай List Comprehension. PROGN! создает последовательность вычислений. Самое интересное, что реализация всех этих макросов в общем случае проста как топор. За это отвечает монадический макрос WITH-MONAD.

Пакет cl-monad-macros предоставляет также готовые монадические макросы для монад Identity, List, Maybe, Reader, State и Writer. Последняя монада несколько отличается от канона, но суть та же. Такие специализированные макросы порождают намного более эффективный код для своих монад, чем обобщенный макрос WITH-MONAD.

Были сложности с монадными трансформерами. Для них, кстати, отдельные макросы – необходимость. В пакете есть макросы для трансформеров Reader, State и Writer. Это параметризуемые монадические макросы, где параметром является другой монадический макрос. Довольно мощная абстракция, которая позволяет комбинировать несколько монад в одной.

Если пытаться использовать монадические макросы для транформеров непосредственно в коде, то легко загнать лисповский компилятор в ступор. Дело в том, что эти макросы при раскрытии создают множество вложенных MACROLET-ов. У компиляторов от этого сносит голову напрочь. Но пока мне такая кодо-генерация представляется единственно возможной для трансформеров, если делать именно через макросы, а не generic-функции. Но, к счастью, есть простое решение. Назвал его упрощением (редукцией) монадических макросов. С обычными же непараметризуемыми макросами типа WITH-MONAD и WITH-LIST-MONAD все нормально.

Теперь вот думаю дополнить монадические макросы вспомогательными макросами. Нужны аналоги хаскелевских полиморфных функций типа fmap, sequence, join и т.д. Еще нужно что-то придумать для циклов. В хаскеле этого уже нет, но зато есть в F#.

Это все собираюсь использовать для симуляции моделей системной динамики. Обнаружил, что динамический процесс может быть определен как вариация монады Reader. Что важно, это позволяет задавать задачи моделирования декларативно, т.е. на высоком уровне абстракции. Я уже написал такую библиотеку на F#, но меня не устраивает ее скорость – слишком много накладных расходов, связанных с монадами. Надеюсь, что лисповская реализация на основе придуманных мною монадических макросов будет быстрее, во многом благодаря особой технике генерации кода для монады Reader. Там получается, что FUNCALL и LAMBDA чередуются друг с другом, то есть их можно сократить, но об этом написано уже у меня в документации к пакету cl-monad-macros.

2 комментария:

  1. А какой смысл иметь типы-обвёртки (Maybe, Either, IO, ...) и классы типов (Functor, Monad, Applicator, ...) в динамическом ill-typed языке?

    Возьмете любой пример на котором можно проследить генезис типов данных вроде Maybe и Either (вроде "клонирования овец" или "рекурсивный лабиринт"):

    1) В Haskell вам необходимо ввести эти типы чтобы "примешивать" значения или варианты к основному типу.

    2) Если вы попытаетесь обойтись без них - вы разрушите well-typed свойство языка.

    А вот в CL:

    1) Типы данных-обвёртки вроде Maybe и Either просто не нужны, т.к. вы можете примешивать эти значения на уровне типов (квантификатор or по типам), или вообще типизировать всё наиболее широким типом T.

    2) Конечно, это возможно потому что язык ill-typed.

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

    ОтветитьУдалить
  2. Как минимум, Either и Maybe имеют смысл, на счет остальных не могу сказать. Наверное, просто нет стандартного способа их реализации.

    А вообще, я несколько пересмотрел свое мнение на счет библиотеки. На мой взгляд было бы интереснее развиваться в направлении cl-cont с его code walker, но там получается не все гладко. А так, интересна сама идея автоматической обработки сложных конструкций, таких как циклы.

    ОтветитьУдалить