Функциональная "симултаниты"?

Question

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

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

λf(x) ::= x f(x)

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

0   - f(x)
1   - x f(x)
2   - x x f(x)
3   - x x x f(x)

Дело в том, что мы должны предположить, что 'f()' и 'x' на шаге три миллиона имеют то же значение, что и на шаге один.

На этом этапе те из вас, кто знает кое-что о FP, бормочут "ссылочную прозрачность" под своим коллективным дыханием. Я знаю. Я побью это за минуту. А пока просто приостановите свое неверие настолько, чтобы признать, что ограничение действительно существует, и амардвар не пострадает.

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

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

Больше слов... для этого нужна другая функция... к счастью, она простая:

λg(x) ::= x x

Теперь.. когда мы делаем заявление:

g(f(x))

Оценка предварительного заказа говорит, что мы должны полностью расширить f(x), прежде чем подключать его к g(). Но это занимает вечность, что... неудобно. Оценка Postorder говорит, что мы можем сделать это:

0   - g(f(x))
1   - f(x) f(x)
2   - x f(x) x f(x)
3   - x x f(x) x x f(x)

, , , Может ли кто-нибудь объяснить мне, что здесь подразумевается? Я понятия не имею, что говорится. Может быть, укажите мне действительно хороший учебник FP, который бы начал меня.

Answer 1

(Внимание, этот ответ очень многословен. Я подумал, что лучше всего включить общие знания о лямбда-исчислении, потому что почти невозможно найти хорошие объяснения этого)

Автор, кажется, использует синтаксис λg(x) означать именованную функцию, а не традиционную функцию в лямбда-исчислении. Автор также, похоже, подробно рассказывает о том, как лямбда-исчисление не является функциональным программированием, так же, как машина Тьюринга не является императивным программированием. Есть практичности и идеалы, которые существуют с теми абстракциями, которых нет в языках программирования, часто используемых для их представления. Но прежде чем углубиться в это, может помочь учебник по лямбда-исчислению. В лямбда-исчислении все функции выглядят так:

λarg.body

Вот и все. Есть λ символ (называемый "лямбда", отсюда и название), за которым следует именованный аргумент и только один именованный аргумент, затем следует точка, затем следует выражение, представляющее тело функции. Например, identity функция, которая берет что-либо и просто возвращает его обратно, будет выглядеть так:

λx.x

А оценка выражения - это просто серия простых правил для обмена функций и аргументов с их выражениями тела. Выражение имеет вид:

function-or-expression arg-or-expression

Сокращение его обычно имеет правила: "Если левая вещь - это выражение, уменьшите его. В противном случае, это должна быть функция, поэтому используйте arg-or-expression в качестве аргумента функции, и замените это выражение на body функции. Очень важно отметить, что не требуется, чтобы arg-or-expression быть уменьшенным, прежде чем использоваться в качестве аргумента. То есть оба из следующих являются эквивалентными и математически идентичными сокращениями выражения λx.x (λy.y 0) (при условии, что у вас есть какое-то определение для 0, потому что лямбда-исчисление требует, чтобы вы определяли числа как функции):

λx.x (λy.y 0)
=> λx.x 0
=> 0

λx.x (λy.y 0)
=> λy.y 0
=> 0

В первом сокращении аргумент был уменьшен перед использованием в λx.x функция. Во втором случае аргумент был просто заменен на λx.x тело функции - это не было уменьшено перед использованием. Когда эта концепция используется в программировании, она называется "ленивая оценка" - вы на самом деле не оцениваете (уменьшаете) выражение, пока вам это не нужно. Важно отметить, что в лямбда-исчислении не имеет значения, сокращается ли аргумент перед заменой. Математика лямбда-исчисления доказывает, что вы получите один и тот же результат в любом случае до тех пор, пока оба не завершатся. Это определенно не относится к языкам программирования, потому что все виды вещей (обычно связанные с изменением состояния программы) могут отличать ленивую оценку от обычной.

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

λname(arg).body

Скажем, это означает, что функция λarg.body связан с nameи в любом другом месте в любых сопровождающих лямбда-выражениях мы можем заменить name с λarg.body, Таким образом, мы могли бы сделать это:

λidentity(x).x

И теперь, когда мы пишем identityмы просто заменим его λx.x, Это создает проблему, однако. Что происходит, если именованная функция ссылается на себя?

λevil(x).(evil x)

Теперь у нас есть проблема. Согласно нашему правилу, мы должны быть в состоянии заменить evil в body с чем связано имя. Но так как имя связано с λx.(evil x), как только мы попробуем:

λevil(x).(evil x)
=> λevil(x).(λx.(evil x) x)
=> λevil(x).(λx.(λx.(evil x) x) x)
=> ...

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

Важным моментом здесь является то, что это полностью отличается от обычной программы лямбда-исчисления, которая оценивает бесконечно и никогда не заканчивается. Например, рассмотрим функцию self application, которая берет что-то и применяет это к себе:

λx.(x x)

Если мы оценим это с identity Функция, мы получаем:

λx.(x x) λx.x
=> λx.x λx.x
=> λx.x

Использование именованных функций и именование этой функции self:

self identity
=> identity identity
=> identity

Но что будет, если мы пройдем self к себе?

λx.(x x) λx.(x x)
=> λx.(x x) λx.(x x)
=> λx.(x x) λx.(x x)
=> ...

Мы получаем выражение, которое повторяется self self в self self снова и снова. Это простой старый бесконечный цикл, который можно найти в любом (полном по Тьюрингу) языке программирования.

Разница между этим и нашей проблемой с рекурсивными определениями заключается в том, что наши имена и определения не являются лямбда-исчислением. Они являются сокращениями, которые мы можем расширить до лямбда-исчисления, следуя некоторым правилам. Но в случае λevil(x).(evil x)Мы не можем расширить его до лямбда-исчисления, поэтому мы даже не запускаем выражение лямбда-исчисления. Наша именованная функция "не компилируется" в некотором смысле, аналогично тому, когда вы отправляете компилятор языка программирования в бесконечный цикл, и ваш код даже не запускается, в отличие от того, когда зацикливается фактическая среда выполнения. (Да, вполне возможно, чтобы компилятор попадал в бесконечный цикл.)

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

λevil(f).λy.(f y)

Если мы оценим evil identityмы получим новую функцию, которая принимает аргумент и просто вызывает identity с этим. Следующая оценка показывает сначала замену имени с помощью ->, а затем сокращение с помощью =>:

(evil identity) 0
-> (λf.λy.(f y) identity) 0
-> (λf.λy.(f y) λx.x) 0
=> λy.(λx.x y) 0
=> λx.x 0
=> 0

Где вещи становятся интересными, если мы проходим evil себе вместо identity:

(evil evil) 0
-> (λf.λy.(f y) λf.λy.(f y)) 0
=> λy.(λf.λy.(f y) y) 0
=> λf.λy.(f y) 0
=> λy.(0 y)

Мы закончили с функцией, которая является полной чепухой, но мы достигли чего-то важного - мы создали один уровень рекурсии. Если бы мы должны были оценить (evil (evil evil))мы бы получили два уровня. С (evil (evil (evil evil))), три. Так что нам нужно сделать, вместо того, чтобы передать evil нам нужно передать функцию, которая каким-то образом выполняет эту рекурсию для нас. В частности, это должна быть функция с самостоятельным применением. То, что мы хотим, это Y-комбинатор:

λf.(λx.(f (x x)) λx.(f (x x)))

Эта функция довольно сложна, чтобы обернуть голову вокруг определения, поэтому лучше просто вызвать ее Y и посмотрим, что произойдет, когда мы попытаемся оценить несколько вещей:

Y evil
-> λf.(λx.(f (x x)) λx.(f (x x))) evil
=> λx.(evil (x x)) λx.(evil (x x))
=> evil (λx.(evil (x x))
         λx.(evil (x x)))
=> evil (evil (λx.(evil (x x))
               λx.(evil (x x))))
=> evil (evil (evil (λx.(evil (x x))
                     λx.(evil (x x)))))

И, как мы видим, это продолжается бесконечно. То, что мы сделали, взято evil, который принимает сначала одну функцию, а затем принимает аргумент и оценивает этот аргумент, используя функцию, и передает ей специально модифицированную версию evil функция, которая расширяется, чтобы обеспечить рекурсию. Таким образом, мы можем создать "точку рекурсии" в evil функция за счет уменьшения evil (Y evil), Так что теперь, когда мы видим именованную функцию, используя рекурсию, вот так:

λname(x).(.... some body containing (name arg) in it somewhere)

Мы можем преобразовать его в:

λname-rec(f).λx.(...... body with (name arg) replaced with (f arg))
λname(x).((name-rec (Y name-rec)) x)

Мы превращаем функцию в версию, которая сначала принимает функцию для использования в качестве точки рекурсии, затем мы предоставляем функцию Y name-rec в качестве функции для использования в качестве точки рекурсии.

Причина, по которой это работает, и возвращение waaaaay обратно к первоначальной точке зрения автора, заключается в том, что выражение name-rec (Y name-rec) не нужно полностью уменьшать Y name-recдо начала собственного сокращения. Я не могу подчеркнуть это достаточно. Мы уже видели, что сокращениеY name-rec приводит к бесконечному циклу, поэтому рекурсия работает, если в name-rec функция, которая означает, что следующий шаг Y name-rec возможно, не нужно уменьшать.

Это ломается во многих языках программирования, включая функциональные, потому что они не поддерживают этот тип ленивых вычислений. Кроме того, почти все языки программирования поддерживают мутацию. То есть, если вы определите переменную x = 3позже в том же коде вы можете сделать x = 5 и весь старый код, который ссылался на x когда было 3, теперь увидим x как 5. Это означает, что ваша программа может иметь совершенно разные результаты, если этот старый код "задерживается" с ленивой оценкой и вычисляется только позже, потому что к тому времени x может быть 5. В языке, где вещи могут быть выполнены произвольно в любом порядке в любое время, вы должны полностью исключить зависимость вашей программы от таких вещей, как порядок операторов и изменяющиеся во времени значения. Если вы этого не сделаете, ваша программа может вычислить произвольно разные результаты в зависимости от порядка выполнения вашего кода.

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

Racket, диалект Scheme, указывает, что в обычном языке Racket все выражения оцениваются "с нетерпением" (без задержки), а все аргументы функции оцениваются с нетерпением слева направо, но программа Racket включает в себя специальные формы, которые позволяют выборочно выполнять некоторые выражения ленивые, такие как (promise ...), Haskell делает обратное, с выражениями по умолчанию для ленивых вычислений и с помощью компилятора запускает "анализатор строгости", чтобы определить, какие выражения нужны функциям, которые специально объявлены для аргументов, которые должны быть с нетерпением оценены.

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