Действительно ли чисто функциональные языки гарантируют неизменность? - PullRequest
3 голосов
/ 09 апреля 2011

На чисто функциональном языке нельзя по-прежнему определять оператор «присваивания», скажем, «<-», такой, чтобы команда, скажем, «i <- 3» вместо непосредственного присваивания неизменяемой переменной i , создаст ли копию всего текущего стека вызовов, кроме замены i на 3 в новом стеке вызовов и выполнения нового стека вызовов с этого момента? Учитывая, что данные на самом деле не изменились, разве это не будет считаться «чисто функциональным» по определению? Конечно, компилятор просто выполнил бы оптимизацию, чтобы просто присвоить 3 i, и в этом случае какая разница между императивным и чисто функциональным? </p>

Ответы [ 3 ]

5 голосов
/ 09 апреля 2011

Чисто функциональные языки, такие как Haskell, имеют способы моделирования императивных языков, и они не стесняются допустить это. :)

См. http://www.haskell.org/tutorial/io.html,, в частности, 7,5:

Итак, в конце концов, Haskell просто заново изобрел императивное колесо?

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

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

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

Обновление

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

Но, конечно, вместо этого вы просто пишете функцию, которая действует как тело цикла, а затем заставляете ее вызывать себя. Каждый вызов функции соответствует «шагу итерации». И в области действия каждого вызова параметр имеет другое значение, действуя как инкрементная переменная. Наконец, среда выполнения может заметить, что рекурсивный вызов появляется в конце вызова, и поэтому он может повторно использовать верхнюю часть стека вызовов функций вместо его увеличения ( tail call ). Даже этот простой шаблон имеет почти весь смысл вашей идеи - включая незаметное вмешательство компилятора / среды выполнения и фактическую мутацию (перезаписывающую вершину стека). Он не только логически эквивалентен циклу с изменяющимся счетчиком, но фактически заставляет процессор и память выполнять одно и то же физически.

Вы упомянули GetStack, который вернул бы текущий стек как структуру данных. Это действительно было бы нарушением функциональной чистоты, учитывая, что оно обязательно будет возвращать что-то другое каждый раз, когда вызывается (без аргументов). Но как насчет функции CallWithStack, которой вы передаете собственную функцию, и она вызывает вашу функцию и передает ей текущий стек в качестве параметра ? Это было бы совершенно нормально. CallCC работает примерно так.

4 голосов
/ 09 апреля 2011

Haskell с готовностью не дает вам способов анализировать или «выполнять» стеки вызовов, поэтому я бы не стал слишком беспокоиться об этой конкретной причудливой схеме.Однако в целом верно , что можно подорвать систему типов, используя небезопасные «функции», такие как unsafePerformIO :: IO a -> a.Идея состоит в том, чтобы сделать трудным, а не невозможным нарушение чистоты.

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

Есть предложение, чтобы действительно гарантировать безопасность, запретив такие подрывные действия системы типов;Я не слишком знаком с этим, но вы можете прочитать об этом здесь .

2 голосов
/ 09 апреля 2011

Неизменность - это свойство языка, а не реализации.

Операция a <- expr, которая копирует данные, по-прежнему является обязательной операцией, если значения, относящиеся к расположению a, изменилисьс точки зрения программистов.

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

...