Монадические макросы для 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.