F# на юниксе

Оказывается, можно замечательно использовать F# на маке с помощью Mono и Xamarin Studio. Очень удобно, и мой проект от Visual Studio работает прекрасно. Попробовал редактировать и создавать файлы в Xamarin Studio. Мне понравилось. Даже лень было сегодня загружаться в винду, где у меня установлена Visual Studio. 

Надо сказать, что ребята из Xamarin достигли заметного прогресса. Что меня больше всего потрясло, так это то, что в некоторых моих тестах Mono заметно обгоняет .NET, делая поправку на то, что гонял я тесты на одной машине, но под разными операционками, да и тесты, вероятно были несколько специфическими. Ни за что бы не поверил в возможность такого еще пару лет назад!

А вдруг есть такой чудесный плагин для Scala?

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

Есть у меня одна уже работающая задумка, но мне нужен для Scala хороший и удобный синтаксический сахар для монад (эх, еще бы для стрелок…). Мечтаю о чем-то подобном computation expressions из F# - это такой аналог нотации do для языка, в котором нет классов типов. Как понимаю, нужен плагин к компилятору в случае Scala.

Ни встроенный for-comprehension, ни плагин продолжений не впечатляют нисколько. Отчасти они дублируют друг друга, но ни одно из них не решает свою задачу хорошо в моем понимании, давно извращенным другими языками. В общем, тот случай, где количество не переходит в качество, и даже не помышляет о том.

Очень хотел использовать Scala, но сейчас пребываю в полной печали. Для моей задачи технически идеально подходит Haskell, но я хочу продвинуть библиотеку в широкие массы, а потому Haskell пока хорош только как полигон для выработки, обкатки и кристаллизации моих безумных идей, и здесь он свою миссию уже выполнил на все 350% с блеском и шиком. Но сейчас хочется получить уже широкую аудиторию из исключительно меркантильных соображений, а потому интересует Scala. 

Комментарий о хвостовой рекурсии

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

В прошлом году вышел замечательный перевод книги Пола Грэма "ANSI Common Lisp". В оригинале этой книги на странице 216 есть такое предложение: "A good compiler can compile a tail call into a goto, and so can compile a tail-recursive function into a loop". Дальше идет довольно общее описание того, как это может быть сделано.

Проблема в том, что без знания контекста тот текст можно неправильно истолковать. Все встает на свои места, если обратиться к книге PAIP Питера Норвига, которую Пол Грэм безусловно читал. В той книге приведена некая абстрактная машина. Там действительно хвостовая рекурсия компилируется в циклы, но в циклы не языка высокого уровня, а в циклы ассемблера той абстрактной машины (фактически через goto). Вот, в чем загвоздка.

Многие почему-то считают, что хвостовую рекурсию можно всегда преобразовать в циклы Scala, F# или Common Lisp. Мне кажется это неправильным. Можно придумать контр-пример. Достаточно обернуть рекурсивный вызов в лямбду и дальше передать эту лямбду другой функции. Например, компилятор Scala не сможет это превратить в цикл на уровне явовского байт-кода, а на уровне абстрактной машины из PAIP цикл получился бы сам собою.

Функциональная чистота и ссылочная прозрачность

Есть мнение, что термин "ссылочная прозрачность" является ненадежным, поскольку люди до сих пор не могут договориться об его точном определении, точно также как не могут договориться о том, какие языки программирования считать функциональными, а какие - нет. Тем не менее, термин широко встречается в литературе.

Что касается "функциональной чистоты", то с нею более-менее понятно: результат зависит только от входных параметров, и функция не производит внешних побочных эффектов в том смысле, что не изменяет состояние окружающего мира. Для статически типизированных языков это обычно означает, что все, что функция делает и производит, описано в ее сигнатуре. Тут я изучал самые разные источники, включая учебники по Common Lisp, Haskell, F# и Scala. Трактовка везде примерно такая, почему-то за исключением одного русскоязычного учебника (не буду называть).

Для определенности возьмем такую вариацию этих терминов из еще невышедшей книги "Functional Programming in Scala":

"An expression e is referentially transparent if for all programs p, all occurrences of e in p can be replaced by the result of evaluating e, without affecting the observable behavior of p. A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x."

Здесь содержатся одно из возможных определений для ссылочной прозрачности и вывод о том, что если выражение f(x) ccылочно-прозрачно для всех ссылочно-прозрачных x, то функция f является чистой. Определение чистоты в книге дается обычное в другом месте. Меня смущает то, что хотя используется слово "if" в последнем предложении, трактуется оно почему-то как "if and only if".

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

Второе. У меня складывается ощущение, что ссылочная прозрачность жестко привязана к конкретному языку программирования, тогда как свойство функции быть чистой является в большой степени над-языковым. Припоминая ассемблер PDP-11, сдается мне, что даже на уровне ассемблера можно оперировать чистотой, если ввести определенные допущения для стека (или стеков). Это так? Если да, то тогда оба понятия действительно не могут быть эквивалентными уже по этому.

В общем, прошу вразумить и поставить на путь истинный.

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

Давеча рекламировал свои обобщенные последовательности (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) 

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

Рекламирую свою новую библиотеку 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.

[1] https://github.com/dsorokin/generic-sequences

[2] https://github.com/dsorokin/generic-sequences/blob/master/doc/generic-sequences-manual.pdf

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

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

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

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

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

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