среда, 30 декабря 2009 г.

Комбинатор неподвижной точки

Когда мне впервые задали вопрос о том может ли существовать функция вида Func<Func<T,T>,T> без использования конструкций вида default(T) он поверг меня в глубокий когнитивный диссонанс.
Как может существовать функция у которой неоткуда взять значения? Об очевидном варианте
T Fix<T>(Func<T,T> func){
   return func(Fix(func));
}
я не мог даже подумать. Разве возможно делать такие функции? Она будет вызываться бесконечно и не даст результата. В языках типа C# такая конструкция и правда вызовет зацикливание, но вполне может работать в языках вроде питона или хаскеля. Сейчас будет немного кода на Haskell, надеюсь синтаксис будет более-менее понятен всем.
Самый простой пример:
fix f = f( fix f)
const42 x = 42
print(fix const42) -- Угадайте, что выведет эта конструкция?
Если разложить вызов, то мы увидим, чтo имеет место быть следующая цепочка вычислений:
fix const42 -> const42 ( fix const42) -> 42
Последний переход произойдёт из-за того, что нам не нужен аргумент функции, чтобы вычислить её значение.
Возникает вопрос: если же функция будет зависеть от своего аргумента то вычисление не остановится, то как нам быть?
Ну не остановиться, и ладно. Если значение не будет использоваться, то оно и не должно быть вычислено, за что спасибо ленивости Haskell.
: - это функция добавления элемента в голову списка. Например: 1:[2,3] = [1,2,3], n:[] = [n]

Рассмотрим функцию fix (1:). Она возвращает список, который, очевидно, будет бесконечным, но тем не менее его можно будет использовать.
take 3 (fix (1:)) -> take 3 (1:fix (1:)) -> 1:take 2 (fix (1:)) -> 1:(1:take 1 (fix (1:)))
-> 1:(1:(1:take 0 (fix (1:)))) -> 1:(1:(1:[])) -> 1:(1:[1]) -> 1:[1,1] -> [1,1,1]
Вот так просто мы получили результат от функции, которая использует свой параметр. Мы даже создали полезную вещь:
repeat n = fix (n:) - Порождение бесконечного списка из одного повторяющегося элемента.
Бесконечность это не порок, главное чтобы где-нибудь, всё равно внутри или снаружи, цепочка вычислений оборвалась. Какие конструкции могут прервать цепочку?
До этого момента мы предполагали, что тип функции для fix является значимым типом. Но почему бы нам не начать использовать функцию высшего порядка? Попробуем традиционный пример:
factCore f = \x -> if x == 0 then 1 else x * f (x-1)
Тогда функция fix factCore будет являться обыкновенным факториалом. По сути каждый раз вместо функции f будет подставляться функция factCore, из-за чего всё станет крайне похоже на обыкновенную рекурсию.

Давайте попробуем что-нибудь посложнее. Например создать все последовательности длинны k состоящие из чисел от 1 до n, притом чтобы не было двух рядом стоящих одинаковых чисел. Задача высосана из пальца, но тем не менее.
allDiffCore n f = \k cond -> if k == 1 then map (\x->[x]) $ filter cond [1..n] else concat $ map (\x -> map (x:) (f (k-1) (/=x)) ) (filter cond [1..n])
sequences n k = fix (allDiffCore n) k (\x->True)
Небольшие пояснения:
filter - функция, принимающая два параметра: условия и список. Возвращает список объектов, которые удовлетворяют условию.
/= - обыкновенное "не равно". Такая вот весьма математическая запись.
concat - функция, которая объединяет список списков в один список.
На каждом шаге мы берём несколько подходящих элементов и задаём функцию которая определит, подходит ли нам следующий элемент. При помощи такого шаблона можно генерировать много разнообразных последовательностей. Например, чтобы получить все возрастающие последовательности достаточно лишь поменять часть отвечающую за функцию фильтрации, то есть (/=x) заменить на (>x).

А теперь задача на подумать: как написать функцию, которая разрешит задачу о ферзях на шахматной доске размера n*n?
Как вы уже заметили, использование функции fix (кстати она является частным случаем комбинатора неподвижной точки), позволяет избежать прямой рекурсии в функциях, что может быть полезно, например, в лямбда исчислении, поскольку там нельзя использовать обыкновенную рекурсию.

Бонусом предлагаю некий, сильно урезанный комбинатор неподвижной точки, для c#:
public static Func<T1, T2> Fix(Func<Func<T1, T2>, Func<T1, T2>> f)
{
   // Создание функции необходимо использовать, чтобы дальнейшие вызовы происходили непосредственно
   // во время передачи значения внутрь. Это позволяет избежать зацикливания

   return f(x => Fix(f)(x));
}
И дальше использование:
var fact = Fix<int, int>(self => x =>
   {
      if (x == 0)
         return 1;
      return x * self(x - 1);
   });
var result = fact(5);   // 120

Если использовать кодогенератор, то можно наплодить приемлемое для дальнейшего использования число функций.

суббота, 26 декабря 2009 г.

Не переусердствуй.

Типичная задача: если коллекция IEnumerable<T>. Требуется определить, содержится ли в нём как минимум n элементов.
Уже не раз и не два видел подобное решение:
   var answer = collection.Count() > n;
Вопрос: зачем так делают люди? Даже если я отброшу чисто функциональные претензии о работе с бесконечными спискам, то остаётся проблемы производительности, возможные эффекты.
Неужели так сложно делать:
   var answer = collection.Skip(n).Any();
И все будут счастливы. Быть как можно более ленивым выгодно.

пятница, 25 декабря 2009 г.

Ленивость и строгость.

Начнём цикл лекций по ленивым вычислениям.
Цикл лекций окончен, задавайте Ваши вопросы.

У любой вещи может быть ровно 4 состояния, к которым можно приписать определённые риски:

  •  Не надо и не сделано. Риска нет
  •  Не надо и сделано. Риск минимален, за редкими исключениями.
  •  Надо и сделано. Всё хорошо, риска нет.
  •  Надо и не сделано. Риск высокий, единственная действительно нехорошая ситуация.

А теперь давайте посмотрим на типичный подход некоторых языков программирования. Как некогда шутили, про отличая функционального программирования от императивного:
В функциональном программировании Вы объясняете свою проблему математику, в императивном Вы объясняете ту-же самую проблему идиоту.
С ленью можно провести некоторые подобные аналогии. Неленивое программирование недалеко ушло от идиота, скажешь — сделает. Зато ленивое имеет отличительную Русскую черту — пока не припрёт делать ничего не будет.
Императивные языки программирования обычно являются неленивыми, есть паттерны вроде Синглтонов и Итераторов, но общей картины они не меняют, поскольку это сознательный уход от традиционной парадигмы в угоду производительности и удобству. Соответственно, если мы наложим поведение на шаблон, изложенный в самом начале поста, то помимо положительных результатов, мы получим вариант «Не надо и сделано». Запомним это и ненадолго отложим.

Многие функциональные языки по природе являются ленивыми. Это не обязательный критерий, но весьма полезный. Довольно сложно работать с бесконечными списками, функциями высшего порядка и прочими прелестями, если всё что написано исполняется сразу-же. Процессорные ресурсы, как и память, к сожалению, ограничены. Примером функционального ленивого языка может служить Haskell, который лишь чуть менее ленив, чем полностью, и, если его специально не пнуть, делать ничего не будет. Любое действии, которое должно быть выполнено нужно обязательно обозначить. Я бы не стал писать этот пункт в минус, так как это особенность реализации. Соответственно исключив пункт «Надо и не сделано» у нас остаётся только один вариант «Надо и сделано», который нас более чем устраивает.

Вроде бы всё хорошо и там и там, разве не так? Частично соглашусь, но отмечу лишь, что минимальный риск — это тоже риск. Любое действие в императивном языке может порождать сайд-эффекты. Изменение состояния класса, вывод во внешний мир (монитор, консоль, файл) и так далее. Огромный процентов ошибок, которые в принципе существуют, связан именно с сайд эффектами. Часто из-за того, что ненужное изменение было произведено (кинутое не вовремя событие, заранее инициализированный объект породивший утечку памяти, не вовремя запрошенный критический ресурс, породивший блокировку). В языке с ленивой структурой выполняются лишь те действия, которые необходимы для получения конкретного результата, что значительно сокращает ряд возможных ошибок, но к сожалению не до конца. Об остальном призвана позаботиться «строгость», которой обладает, например, тот-же Haskell. Всё, что вам дано извне пришло в качестве аргументов функции, которые всегда неизменяемые (на самом деле это не так, но прежде чем начать использовать что-то изменяемое, Вы десять раз подумаете, а так ли это Вам необходимо), взаимодействия со сторонним кодом практически никакого. Сложно что-то сломать, если Вам оно попросту недоступно. Это огромный плюс, значительно увеличивающий стабильность приложения.

Слишком хорошо, чтобы быть правдой, хочется сразу же спросить — а где подвох? Подвох действительно есть. Любые правила — это ограничения, которые как позволяют избежать ошибок, так сокращают размах возможного действа. Из-за этого бывает сложно, а иногда и невозможно, построить адекватную модель. Программы на Haskell являются крайне стабильными, часто переиспользуемыми, но практически всегда маленькими. Большую модель крайне сложно уместить в рамках строгих ограничений.

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