January 5th, 2010

Лениво и без эффектов

Функциональное программирование:
  • программа - λ-терм
  • исполнение программы - редукция исходного терма
Если терм удается свести к нормальной форме (нф) из одних констант, вычисления успешны, нф - их результат.

Нф любого терма зависит только от переменных и констант, лежащих в его основе, причем зависимость от переменных легко свести к вертикальной зависимости от констант:

если x - переменная ⇒ ∃ минимальный терм вида tλ = λ x . ( ... x ... ) и ∃ tβ = tλ y
  если y - константа
    доказано
  иначе
    y содержит переменные x1 ... xN
    x1 - переменная ⇒ ∃ минимальный терм вида tλ1 = λ x1 . ( ... x1 ... ) и ∃ tβ1 = tλ1 y1 и так далее
    ...
высота синтаксического дерева ограничена ⇒ процесс сходится.

Вывод: в функциональных программах нет никаких зависимостей, кроме вертикальных.

Для полноты картины, сделаем одно отступление.

Императивное программирование:
  • программа - последовательность операторов, работающих с переменными
  • переменные можно читать и записывать в соответствующих областях видимости
  • области либо вложены друг в друга, либо не пересекаются
Легко показать, что в императивном программировании могут быть не только вертикальные зависимости: пусть S = (define x; s1; s2) - исходная область, si - вложены в S. Не исключен сценарий, когда sзапишет x, а sего прочитает и вычисления в s2 окажутся зависимыми от x. Запись в x не является результатом s1 в классическом смысле, это побочный эффект.

Замечание: от переменных можно абстрагироваться и рассматривать любой ввод/вывод (например работать не с переменной, а с файлом).


Утверждение: В функциональном программировании (чего не скажешь об императивном) нет побочных эффектов.

Что из этого можно извлечь?

Несколько важных плюсов:
  1. Отладка осуществляется за один проход вверх по дереву
  2. Дерево можно обсчитывать по слоям, вычисляя узлы каждого слоя параллельно
  3. Можно не вычислять узлы, не влияющие на конечный результат (агрессивная оптимизация, ленивое вычисление)
При императивном подходе:
  1. При отладке на каждом уровне приходится заглядывать и ко всем левым братьям
  2. Не вертикальные зависимости препятствуют автоматическому распараллеливанию
  3. Не понятно, что является результатом, ведь все операторы имеют какой-то эффект.
И только один минус: программирование без ввода/вывода :)