понедельник, 10 декабря 2012 г.

Ряд Фибоначчи


Давеча рекламировал свои обобщенные последовательности (Generic Sequences), а какие могут быть последовательности без ряда Фибоначчи? Это что-то вроде обязательного ритуала. Опустим здесь тот факт, что я создал эту библиотеку для вполне практической задачи, когда мне понадобилось быстро и эффективно сравнивать деревья, а там ленивые последовательности дюже полезны.

Итак, ниже приведена рабоче-крестьянская версия, которая выдает ленивую бесконечную последовательности ряда Фибоначчи через то, что я назвал Sequence Comprehension:

(defparameter *fibs-1*
  (with-seq/cc
    (do ((a 1 b)
         (b 1 (+ a b)))
        (nil)
      (yield/cc a))))

Очень просто, не правда ли?

Теперь каноническая версия через поток:

(defparameter *fibs-2*
  (reclet 
      ((fibs (seq->stream
              (seq-cons
               1 (seq-cons
                  1 (seq-map
                     (lambda (x)
                       (+ (first x) (second x)))
                     (seq-zip
                      (delay-seq fibs)
                      (delay-seq (seq-cdr fibs)))))))))
    fibs))

Проверка:

? (seq->list (seq-take 20 *fibs-1*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

? (seq->list (seq-take 20 *fibs-2*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Дополнение.

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

(defparameter *fibs-3*
  (make-seq
   (labels ((traverse (a b)
              (enum-cons a (traverse b (+ a b)))))
     (traverse 1 1))))

Основная идея заключается в том, что мы работаем как с обычным списком, что очень удобно при обходе индуктивных/рекурсивных структур данных. Собственно, все комбинаторы написаны у меня в таком стиле.

И если вам по какой-то причине не нравятся комбинаторы, то результат можно получить с помощью известного макроса iter, для которого я добавил конструкцию in-seq:

? (iter (for i from 1 to 20)
        (for x in-seq *fibs-3*)
        (collect x))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) 

воскресенье, 9 декабря 2012 г.

Обобщенные последовательности


Рекламирую свою новую библиотеку Generic Sequences [1] для Common Lisp. Она вводит обобщенные последовательности похожие на обычные списки Common Lisp, ленивые последовательности clojure, списки Haskell, а также похожие на итераторы, которые можно встретить в таких языках программирования как C#, F#, Java и Scala. С помощью комбинаторов легко создавать обобщенные последовательности, и их легко итерировать с помощью макроса ITER.

Более того, есть так называемое Sequence Comprehension, основанное на продолжениях из пакета CL-CONT. Это что-то похожее на синтаксис Sequence Expression из F# и конструкцию Yield из C#, где мы можем определить ленивую последовательность очень простым и декларативным способом.

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

Есть небольшая документация [2] в формате PDF.


суббота, 7 июля 2012 г.

Порт библиотеки Айвика на язык Scala


После полугода раздумий решил выложить новый порт своей библиотеки имитационного моделирования Айвика. Теперь языком реализации является Scala. Это значит, что можно использовать Java в имитационных моделях. Лицензия - BSD3.

https://github.com/dsorokin/scala-aivika

Основное отличие от двух других реализаций на F# и Haskell состоит в том, что сейчас можно получать результаты моделирования и частично их анализ в виде HTML, графиков и таблиц. Для этого задается так называемый эксперимент. Он описывает либо единичную симуляцию, либо серию по методу Монте-Карло, которая может зависеть от внешних параметров. Также описывается, что мы желаем получить. Всего в нескольких строках можно запросить график отклонения по правилу “три сигма”. Также легко можно запросить таблицы в формате CSV с результатами моделирования, гистограммы, графики траекторий случайных процессов, сводную статистику и т.п. Затем информацию можно посмотреть с помощью вашего любимого браузера.

Здесь так же как в F# легко задавать обыкновенные дифференциальные уравнения, что позволяет красиво и просто строить модели системной динамики. Процессы же дискретно-событийных моделей задаются с помощью продолжений. Через объекты задаются агенты и их состояния. Все это вместе работает на основе единой достаточно простой схемы.

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

вторник, 22 мая 2012 г.

О хвостовой рекурсии


Тут вышла статья на хабре [1], где написано:

"Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией."

Я почему-то всегда считал, что хвостовая рекурсия сложнее. Применительно к F# можно взять такой контр-пример.

Возьмем реализацию оператора while для F# Async. В исходниках F# это будет функция whileA. Если считать, что bindA - это монадическая связка для Async, то видим, что:

1) функция whileA вызывает bindA и передает последней вызов на саму себя, т.е. whileA определяется рекурсивно;

2) функции whileA и bindA используют хвостовые вызовы.

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

В данном случае все хвостовые вызовы внутри whileA и bindA будут помечены в IL специальным тегом, который опознается виртуальной машиной .NET. Это ощутимо замедляет выполнение кода, но стек вызовов не увеличивается, что и требуется.

Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET. Может быть, виртуальная машина и использует итерации, но это уже совсем другой внешний уровень.

[1] http://habrahabr.ru/post/143690/

четверг, 26 января 2012 г.

А не пора ли разбить Scala Library на части?


Библиотека Scala времени исполнения (она же, Scala Library) выросла к версии 2.9.1 аж до восьми с половиной мегабайт с лишним от почти четырех в версии 2.7.7. Для распространения десктопных приложений на Scala это очень плохо. Конечно, есть ProGuard, который убирает все лишнее, но в него нет веры.

Так, только что пропустил свой код через ProGuard и стал тестировать. Ужалось все до мегабайта, но на выходе из приложения получил неприятное NoSuchMethodException. Там создавался анонимный класс, и почему-то один его метод был безжалостно вырезан ProGuard'ом.

Интересно, а собираются ли разбивать Scala Library на части по примеру того, как сделано в .NET? По-моему пора.

понедельник, 16 января 2012 г.

Глубоко-вложенные вычисления


Тема возникла из моих ответов на вопросы, заданные другим человеком на форумах. Речь пойдет о рекурсивных вычислениях, когда глубина вложенности выше предельно допустимой для стека вызовов. Я покажу, как такая задача может быть решена на Common Lisp. Сразу отмечу, что это возможно не всегда, но в большинстве случаев работает.

В основе лежит та же самая идея, что используется в F# Async. Мы просто переводим наши рекурсивные функции на язык продолжений.  Пугаться здесь не стоит, сами мы этого делать не станем. За нас все самое сложное и рутинное сделают WITH-CALL/CC и его специальная версия для функций DEFUN/CC из пакета CL-CONT. Ниже везде предполагается, что пакет CL-CONT импортирован.

Но прежде определимся с исходной задачей. Ниже приведены функции, которые вылетают со Stack Overflow.

(defun compute (x)
  (cond ((zerop x) 0)
        (t (+ (compute (1- x))
              1))))


(defun run ()
  (compute 10000000)) ;; Stack Overflow

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

Перепишем функции через продолжения. Функцию COMPUTE определим через DEFUN/CC. Т.е. она будет возвращать не обычное значение, а вычисление, которое еще нужно запустить. В F# это примерно означало бы то, что функция COMPUTE возвращала бы некоторое значение типа Async<'a>.

(defun/cc compute/cc (x)
  (cond ((zerop x) 0)
        (t (+ (compute/cc (1- x))
              1))))

Таким образом мы должны преобразовать всякую функцию, вложенность которой может быть огромной. Вызывать их можно из DEFUN/CC и WITH-CALL/CC:

(defun run/cc ()
  (with-call/cc (compute/cc 10000000)))

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

Увы, не все лисп-машины хорошо оптимизируют хвостовые вызовы. Для CLozure CL и LispWorks Personal мы по-прежнему получим Stack Overflow. К счастью есть выход - использовать трамплин.

Внутри вычисления DEFUN/CC нам доступно продолжение. Если глубина стека вызовов стала большой, то мы можем запомнить продолжение и раскрутить в обратную сторону стек, возвращая управление некоторому внешнему циклу. Внутри этого цикла мы будем проверять, а нет ли у нас очередного продолжения для, так сказать, продления вычисления. Если есть, то запускаем это продолжение. Фокус состоит в том, что при запуске продолжения стек вызовов уже очищен, что нам и требуется.

Сначала определим утилиты трамплина:

(defparameter *cont* nil)


(defun/cc trampoline-push/cc ()
  (call/cc 
   (lambda (k)
     (push k *cont*))))


(defmacro trampoline/cc (expr)
  (let ((result (gensym)))
    `(progn
       (trampoline-push/cc)
       (let ((,result ,expr))
         (trampoline-push/cc)
         ,result))))


(defmacro with-trampoline/cc (&body body)
  (let ((result (gensym)))
    `(let ((,result nil))
       (with-call/cc
         (trampoline-push/cc)
         ,@body)
       (loop while *cont*
          do (let ((cont (pop *cont*)))
               (setf ,result (funcall cont))))
       ,result)))

Утилита TRAMPOLINE-PUSH/CC кладет продолжение вычисления в ячейку *CONT* и возвращает управление внешнему циклу из WITH-TRAMPOLINE/CC, откуда все должно быть запущено. Макрос TRAMPOLINE/СС оборачивает заданное выражение, где трамплин вызывается до и после вычисления выражения.

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

(defun/cc smart-compute/cc (x)
  (cond ((zerop x) 0)
        ((zerop (mod x 100))  
         ;; on every 100th iteration use the trampoline
         (+ (trampoline/cc (smart-compute/cc (1- x)))
            1))
        (t 
         (+ (smart-compute/cc (1- x))
            1))))


 ;; No Stack Overflow
 (defun smart-run/cc ()
  (with-trampoline/cc (smart-compute/cc 10000000)))

Это работает даже для CLISP, где нет никакой оптимизации хвостового вызова. Мы успешно имитирует рекурсивный вызов с глубиной вложенности десять миллионов!

суббота, 14 января 2012 г.

Первые впечатления о CAPI из LispWorks

Сегодня впервые использовал CAPI для создания каркаса будущего редактора диаграмм. Остался очень довольным. Местами не похоже на Windows Forms, WPF/Silverlight, Swing, SWT, но разобраться можно. Работает, что отрадно.

Еще очень радует среда LispWorksСейчас в проекте 250 килобайт кода на лиспе. Секунда или две после внесения изменений – и я уже вижу обновленное окошко моего редактора. Помню, как я мучился в ожидании, когда почти ту же самую задачу реализовывал на Scala с помощью IntelliJ Idea. Приходилось ждать целую вечность!