Некоторые вопросы при чтении Почему функциональное программирование важно

1. Расширяемые языки

Вероятно, наиболее распространенными примерами расширяемого языка являются семейство Lisp (Common Lisp, Scheme, Clojure), в которых есть синтаксическая макросистема. Эта система макросов позволяет вам думать о программах на Лиспе как о программах, которые выполняются в два момента времени - один раз «во время компиляции» и снова «во время выполнения». Фаза «во время компиляции» берет определенные части программы на Лиспе и синтаксически расширяет их до более сложных программ на Лиспе. Часть «во время выполнения» работает как обычный язык.

Это разделение фаз позволяет нам расширить управляющие структуры языка, потому что мы можем абстрагироваться от общих идиом, ничего не выполняя. Например, учитывая, что у нас есть конструкция if

(if true  then else) ==> then
(if false then else) ==> else

мы можем построить cond структуру, где каждый body оценивается, только если он соединен с истинным значением

(cond (test1 body1) (test2 body2) (test3 body3))

преобразовав его в набор вложенных операторов if во время выполнения

(do (if test1 body1 null)
    (if test2 body2 null)
    (if test3 body3 null))

Обратите внимание, что это не может быть выполнено (обычно) во время выполнения, потому что при обычной оценке Lisp мы должны были бы оценить каждое из тел 1-3, прежде чем мы сможем даже определить, должны ли они выполняться, что делает cond довольно бесполезным.

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

1. Лень

Думать о лени можно так: всякий раз, когда у вас есть вычисления, какими бы глупыми они ни были

f = 3 -- pending!

он «откладывается» до тех пор, пока он не понадобится.

print f  -- now we compute `f` and print it

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

-- [1,2,3,...] infinite list
nums = let go n = n : go (n+1)
       in go 1

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

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

> take 3 [1,2,3,4,5,6]
[1,2,3]

> take 5 [1,2,3]
[1,2,3]

Но что менее очевидно, так это то, что в ленивой настройке он отлично работает и с бесконечными структурами.

> take 5 nums
[1,2,3,4,5]

Таким образом, мы определили вычисление nums более широко, чем это часто требуется при использовании нотации перечисления, такой как [1..10]. Фактически, мы просто запросили «все» числа вместо того, чтобы объединять определение nums с некоторой информацией о том, как выбрать какие числа нам нужны.

Мы оставляем это потребителю. В конце концов, потребитель - это тот, кто знает, сколько чисел ему нужно. Снова рассмотрим утверждение типа (take n) nums, где take n, потребитель, знает, что ему нужны n числа, и, следовательно, nums, производитель, не должен беспокоиться об этом.

В этой концепции есть гораздо больше, но чтобы прямо ответить на ваш последний вопрос о f

f n = 1 + f n

важно говорить о том, что значит для потребителя «требовать» что-то точно так же, как take «требует» список определенного размера. Ваша функция f действительно никогда не будет завершена и никогда не может быть «принудительно завершена» потребителем, за исключением одной ситуации: потребитель может просто полностью ее проигнорировать.

consumer fun = 3

> consumer f 
3

Мы можем говорить об этом с точки зрения того, какие виды продукции f могут быть «частично востребованы». В частности, все, что мы можем ожидать от f, - это конечный результат, и поэтому мы должны дождаться его завершения, чтобы «потребовать» от него что-либо вообще. Нам нужно проявлять творческий подход и думать о способе давать частичные ответы, чтобы нас осмысленно остановил потребитель.

Один из способов - кодировать числа с помощью чисел Пеано. Они выглядят так (в Haskell)

data Peano = Zero | Successor Peano

и мы напишем

0 ==> Zero
1 ==> Successor Zero
3 ==> Successor (Successor (Successor Zero))

Мы можем настроить f для работы с Peano, заменив (1+) на Successor, поскольку они означают примерно то же самое.

f n = Successor (f n)

А теперь, если мы напишем потребителя, который, скажем, является предикатом о том, является ли Peano больше или равно n

gte :: Peano -> Peano -> Bool
gte Zero Zero                   = True
gte Zero (Successor n)          = True
gte (Successor n) (Successor m) = gte n m

мы можем говорить о таких заявлениях, как

gte Zero n ==> True             -- even without evaluating `n` at all
gte (Successor Zero) n ==> True -- while evaluating only one "layer" of `n`

и оценивать такие вещи, как

> gte (Successor (Successor Zero)) (f 10)
True

где gte "принудительно останавливает" f после вычисления двух слоев, достаточное требование для продолжения gte.

Сделаем это на Haskell.

f :: Integer -> Integer
f n = 1 + f n

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

g = const v

для некоторой глобальной константы v. Теперь, если вы попробуете

Prelude> let v = "Я постоянный!"
Prelude> let g _ = v
Prelude> g (f 1)
"Я постоянный!"
Prelude> g (f 2)
«Я постоянен!»
Prelude> g (f 3)
«Я постоянен!»
Prelude> g (f 37)
«Я постоянен ! "

GHC справляется с этим просто, даже не начиная оценивать результат f: он сразу видит g, который на самом деле не нужен, и сразу же выдаёт результат. Однако это деталь реализации. Однако в спецификации языка фиксируется то, что оценка является нестрогой, что означает правильность того, что вы процитировали: оценка не должна зависать бесконечно, пытаясь полностью получить результат f. Таким образом, в принципе, компилятор также может сделать так, чтобы f сначала немного вычислялся (т. Е. Зацикливался) до тех пор, пока не истечет некоторый тайм-аут, когда будет решено проверить, достаточно ли уже сделано результата для использования g. Ответ будет положительным (поскольку в g ничего не требуется), что помешает возобновлению вычисления f.

Конечно, это не очень интересно: постоянные функции тривиальны, в лучшем случае актуальны для короткозамкнутого оператора && или чего-то в этом роде. Но проблема становится гораздо более интересной, когда вы имеете дело со структурами данных, которые можно частично оценить. Самый простой пример: списки Haskell. Рассмотреть возможность

f' :: Integer -> [Integer]
f' n = [n ..]

Это дает (бесконечный) список всех чисел ≥ чем n. Как и f, очевидно, что это никогда не закончится полным результатом, но в данном случае теперь нет необходимости использовать результат. Например,

g' :: [Integer] -> Integer
g' (start:l) = sum $ takeWhile (< start^2) l

Prelude> g '(f' 1)
0
Prelude> g '(f' 2)
3
Prelude> g '(f' 3)
30
Prelude> g '(f' 37)
935693