четверг, 28 января 2010 г.

Алгебраические типы данных в Common Lisp

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

data TaggedType a = NoneValue
                  | SingleValue a
                  | DoubleValue (a, a)

Здесь NoneValue, SingleValue и DoubleValue являются также конструкторами данных. Компилятор хаскеля по такому определению автоматически создает одноименные функции. Мы их тоже создадим. Будем делать все через списки. Первым элементом списка будет идти символическое имя конструктора, т.е. тег. Затем в списке будут идти данные. Это позволит нам различать значения.

(defun none-value ()
  (list 'none-value))

(defun single-value (a)
  (list 'single-value a))

 (defun double-value (a1 a2)
  (list 'double-value a1 a2))

Как видим, все очень просто. Теперь мы можем вручную устроить сопоставление с образцом (pattern-matching).

(defun test-tagged-type (v)
  (ecase (car v)
    (none-value (format t "NoneValue "))
    (single-value (format t "SingleValue ~A" (cadr v)))
    (double-value (format t "DoubleValue (~A, ~A)" (cadr v) (caddr v)))))

Писать каждый раз такой код – дело утомительное и ненужное. Поэтому я придумал вспомогательные утилиты.

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

(defmacro define-adt (name &rest args)
  `(defun ,name (,@args)
     (list ',name ,@args)))

Следующий макрос позволяет более наглядно сопоставлять с образцом. Его имя похоже на имена стандартных макросов CASE, CCASE и ECASE. Приставка ADT указывает, что работа идет с алгебраическими типами данных.

(defmacro adt-case (value &body cs)
  (let* ((t-defined nil)
         (ps (loop for c in cs collect
                  (cond
                    ((eql (car c) 't)
                     (setf t-defined t)
                     (append '(t) (cdr c)))
                    (t
                     (when t-defined
                       (error "The T clause can be only the last in the form."))
                     (destructuring-bind ((name &rest args) &body body) c
                       (adt-pattern value name args body)))))))
    (if t-defined
        `(case (car ,value) ,@ps)
        `(ecase (car ,value) ,@ps))))

(defun adt-pattern (value name args body)
  `(,name
    ,(if (null args)
         `(progn ,@body)
         `(destructuring-bind (,@args) (cdr ,value) ,@body))))

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

(define-adt none-value)
(define-adt single-value a)
(define-adt double-value a1 a2)

(defun test-tagged-type (v)
  (adt-case v
    ((none-value) (format t "NoneValue"))
    ((single-value a) (format t "SingleValue ~a" a))
    ((double-value a1 a2) (format t "DoubleValue (~a, ~a)" a1 a2))))

Сопоставление с образцом было бы неполным, если бы не было замены хаскелевского шаблона “_”. Я выбрал в качестве аналога лисповский терм T. Соответствующее условие должно быть самым последним в списке, иначе компилятор выдаст ошибку.

(defun test-tagged-type-2 (v)
  (adt-case v
    ((none-value) (format t "NoneValue"))
    (t (format t "Not NoneValue"))))

И, наконец, приведу функцию, которая берет значение типа TaggedType и возвращает либо NIL, либо новую CONS-пару.

(defun tagged-type->cons (v)
  (adt-case v
    ((none-value) nil)
    ((single-value a) (list a))
    ((double-value a1 a2) (cons a1 a2))))

Пример использования:

CL-USER> (tagged-type->cons (double-value 1 2))
(1 . 2)

пятница, 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.