Как работают языки функционального программирования?

Ответ 1

Если языки функционального программирования не могут сохранять какое-либо состояние, как они выполняют некоторые простые вещи, такие как чтение ввода от пользователя (я имею в виду, как они "хранят" его) или хранят какие-либо данные в этом отношении?

Как вы собрали, функциональное программирование не имеет состояния &mdash, но это не значит, что он не может хранить данные. Разница в том, что если я напишу инструкцию (Haskell) вдоль строк

let x = func value 3.14 20 "random"
in ...

Я уверен, что значение x всегда одинаково в ...: ничто не может его изменить. Точно так же, если у меня есть функция f :: String -> Integer (функция, берущая строку и возвращающую целое число), я могу быть уверен, что f не будет изменять свой аргумент или изменять любые глобальные переменные или записывать данные в файл, и скоро. Как сказал sepp2k в комментарии выше, эта не-изменчивость действительно полезна для рассуждений о программах: вы пишете функции, которые складывают, шпинделя и калечат ваши данные, возвращая новые копии, чтобы вы могли связать их вместе, и вы можете быть уверены, что никто эти вызовы функций могут делать что угодно "вредно". Вы знаете, что x всегда x, и вам не нужно беспокоиться о том, что кто-то написал x := foo bar где-то между объявлением x и его использованием, потому что это невозможно.

Теперь, если я хочу читать данные от пользователя? Как сказал KennyTM, идея состоит в том, что нечистая функция - это чистая функция, которая передала весь мир в качестве аргумента и возвращает как ее результат, так и мир. Конечно, вы не хотите на самом деле делать это: во-первых, это ужасно неуклюже, а для другого, что произойдет, если я повторно использую один и тот же объект мира? Так что это как-то абстрагируется. Haskell обрабатывает его с типом ввода-вывода:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

Это говорит нам, что main - это действие IO, которое ничего не возвращает; выполнение этого действия - это то, что означает запуск программы Haskell. Правило заключается в том, что типы IO никогда не смогут избежать действия ввода-вывода; в этом контексте мы вводим это действие с использованием do. Таким образом, getLine возвращает IO String, который можно рассматривать двумя способами: во-первых, как действие, которое при запуске создает строку; во-вторых, как строка, "испорченная" IO, так как она была получена нечисто. Первое правильнее, но второе может быть более полезным. <- выводит String из IO String и сохраняет его в str — но поскольку мы находимся в действии ввода-вывода, нам придется его завернуть, поэтому он не может "побег". Следующая строка пытается прочитать целое число (reads) и захватывает первое успешное совпадение (fst . head); это все чисто (без ИО), поэтому мы даем ему имя с let no = .... Затем мы можем использовать как no, так и str в .... Таким образом, мы сохранили нечистые данные (от getLine до str) и чистые данные (let no = ...).

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

Это все, что вам нужно знать, чтобы использовать IO в Haskell; если это все, что вы хотите, вы можете остановиться здесь. Но если вы хотите понять, почему это работает, продолжайте читать. (И обратите внимание, что этот материал будет специфичным для Haskell — другие языки могут выбрать другую реализацию.)

Таким образом, это, вероятно, показалось немного обманом, каким-то образом добавив примеси к чистому Haskell. Но это не так: оказывается, что мы можем реализовать тип ввода-вывода полностью в чистом Haskell (если нам дано RealWorld). Идея такова: действие IO IO type совпадает с функцией RealWorld -> (type, RealWorld), которая принимает реальный мир и возвращает как объект типа type, так и модифицированный RealWorld. Затем мы определяем пару функций, поэтому мы можем использовать этот тип без сумасшедшего:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

Первый позволяет нам говорить о действиях IO, которые ничего не делают: return 3 - это действие IO, которое не запрашивает реальный мир и просто возвращает 3. Оператор >>=, выраженный "bind", позволяет нам запускать операции ввода-вывода. Он извлекает значение из действия ввода-вывода, передает его и реальный мир через функцию и возвращает результат IO-действия. Обратите внимание, что >>= применяет наше правило, чтобы результаты IO-действий никогда не удалялись.

Затем мы можем включить вышеприведенный main в следующий обычный набор приложений функций:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Сценарий запуска Haskell начинается main с начальным RealWorld, и мы настроены! Все чисто, у него просто фантастический синтаксис.

[ Edit: Как указывает @Conal, на самом деле это не то, что Haskell использует для ввода IO. Эта модель ломается, если вы добавите concurrency, или действительно любой способ изменить мир в середине действия ввода-вывода, поэтому Haskell не сможет использовать эту модель. Это точно только для последовательных вычислений. Таким образом, может быть, что Haskell IO немного уклоняется; даже если это не так, это, конечно, не совсем так элегантно. Per @Conal наблюдение, см. То, что Саймон Пейтон-Джонс говорит в Борьба с неуклюжей командой [pdf], раздел 3.1; он представляет то, что может быть эквивалентно альтернативной модели в этом направлении, но затем бросает ее за ее сложность и принимает другой подход.]

Опять же, это объясняет (в значительной степени), как IO и изменчивость вообще работают в Haskell; если это все, что вы хотите знать, вы можете перестать читать здесь. Если вам нужна последняя доза теории, продолжайте читать, но помните, что в этот момент мы ушли очень далеко от вашего вопроса!

Итак, последнее: получается эта структура: параметрический тип с return и >>= — очень общий; он называется монадой, а обозначение do, return и >>= работают с любым из них. Как вы видели здесь, монады не волшебны; все это магическое, что блоки do превращаются в вызовы функций. Тип RealWorld - это единственное место, где мы видим любую магию. Такие типы, как [], конструктор списка, также являются монадами, и они не имеют ничего общего с нечистым кодом.

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

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

(PS: Извините за длину. Я прошел немного далеко.)

Ответ 2

Здесь много хороших ответов, но они длинные. Я попытаюсь дать полезный короткий ответ:

• Функциональные языки ставят состояние в тех же местах, что и в C: в именованных переменных и в объектах, выделенных в куче. Различия заключаются в следующем:

  • В функциональном языке "переменная" получает свое начальное значение, когда оно входит в область (через вызов функции или let-binding), и это значение не изменяется после этого. Аналогично, объект, выделенный в куче, немедленно инициализируется значениями всех его полей, которые после этого не изменяются.

  • "Изменения состояния" обрабатываются не путем изменения существующих переменных или объектов, а путем связывания новых переменных или выделения новых объектов.

• IO работает под управлением. Вычисление побочных эффектов, которое создает строку, описывается функцией, которая принимает аргумент World как, и возвращает пару, содержащую строку и новый мир. Мир включает в себя содержимое всех дисковых накопителей, историю каждого переданного или принятого сетевого пакета, цвет каждого пикселя на экране и тому подобное. Ключом к хитрости является то, что доступ к миру тщательно ограничен, чтобы

  • Никакая программа не может сделать копию мира (где бы вы выразились?)

  • Никакая программа не может выбросить мир

  Использование этого трюка позволяет создать один, уникальный Мир, состояние которого эволюционирует со временем. Система времени выполнения языка, которая не написана на функциональном языке, реализует побочные вычисления путем обновления уникального мира вместо того, чтобы возвращать новый.

  Этот трюк прекрасно объясняется Саймоном Пейтоном Джонсом и Филом Вадлером в их знаменательной статье "Императивное функциональное программирование" .

Ответ 3

Я отлаживаю ответ комментария к новому ответу, чтобы дать больше места:

Я написал:

Насколько я могу судить, эта история IO (World -> (a,World)) является мифом применительно к Haskell, так как эта модель объясняет только чисто последовательные вычисления, тогда как тип Haskell IO включает concurrency. Под "чисто последовательным" я имею в виду, что даже мир (юниверс) не может меняться между началом и концом императивного вычисления, кроме этого из-за этого вычисления. Например, пока ваш компьютер отрывается, ваш мозг и т.д. Не может. Concurrency может обрабатываться чем-то более похожим на World -> PowerSet [(a,World)], что допускает недетерминизм и чередование.

Норман писал:

@Conal: Я думаю, что история IO очень хорошо делится на недетерминизм и чередование; если я правильно помню, там довольно хорошее объяснение в газете "Неловкий отряд". Но я не знаю хорошей бумаги, которая четко объясняет истинную parallelism.

@Norman: Обобщает в каком смысле? Я предполагаю, что обычно обозначенная денотационная модель/объяснение World -> (a,World) не соответствует Haskell IO, потому что она не учитывает недетерминизм и concurrency. Может быть более сложная модель, которая подходит, например World -> PowerSet [(a,World)], но я не знаю, была ли эта модель разработана и показана адекватная и последовательная. Я лично сомневаюсь, что такого зверя можно найти, учитывая, что IO заполняется тысячами FFI-импортных императивных вызовов API. И как таковой IO выполняет свою задачу:

Открытая проблема: монада IO стала Haskells sin-bin. (Всякий раз, когда мы ничего не понимаем, мы бросаем его в монаду IO.)

(Из Simon PJ POPL talk Ношение рубашки для волос Ношение рубашки для волос: ретроспектива на Haskell.)

В Разделе 3.1 Схватив неуклюжий отряд, Саймон указывает, что не работает над type IO a = World -> (a, World), включая "Подход не масштабируется хорошо, когда мы добавляем concurrency". Затем он предлагает возможную альтернативную модель, а затем отказывается от денотационных объяснений, говоря

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

Это неспособность найти точную и полезную денотационную модель лежит в основе того, почему я вижу Haskell IO как отход от духа и глубокие преимущества того, что мы называем "функциональным программированием", или то, что Питер Ландин более конкретно назвал "денотативное программирование". См. комментарии здесь.

Ответ 4

Функциональное программирование происходит из лямбда-исчисления. Если вы действительно хотите понять Функциональное программирование, выберите http://worrydream.com/AlligatorEggs/

Это "забавный" способ изучить лямбда-исчисление и привести вас в захватывающий мир функционального программирования!

Как знание Lambda Calculus полезно в функциональном программировании.

Итак, Lambda Calculus является основой для многих языков программирования в реальном мире, таких как Lisp, Scheme, ML, Haskell,....

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

plus3 x = succ(succ(succ x)) 

Чтение "plus3 - это функция, которая при применении к любому числу x дает преемника наследника преемника x"

Обратите внимание, что функция, которая добавляет 3 к любому числу, не должна называться plus3; имя "плюс3" является просто удобным сокращением для обозначения этой функции

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Обратите внимание, что мы используем символ лямбда для функции (я думаю, что это похоже на Аллигатор, я предполагаю, что откуда взялась идея для аллигаторных яиц)

Символом лямбда является Аллигатор (функция), а x - его цвет. Вы также можете думать о x как о аргументе (функции Lambda Calculus действительно только допускают один аргумент), остальное вы можете думать о нем как о теле функции.

Теперь рассмотрим абстракцию:

g ≡ λ f. (f (f (succ 0)))

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

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

Если вы заметили, что вы видите, что наш λ f Alligator съедает наш λ x Alligator, а затем λ x Alligator и умирает. Тогда наш λ x Аллигатор перерождается в яйцах А f-аллигаторов. Затем процесс повторяется, а λ x Alligator слева теперь съедает другую λ x Alligator справа.

Затем вы можете использовать этот простой набор правил " Alligators" есть " Аллигаторы" для разработки грамматики, и поэтому родились языки функционального программирования!

Итак, вы можете увидеть, знаете ли вы Lambda Calculus, как вы поймете, как работают функциональные языки.

Ответ 5

Техника обработки состояния в Haskell очень проста. И вам не нужно понимать монады, чтобы получить ручку.

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

Итак, вместо того, чтобы иметь какое-то состояние типа X, вы пишете функции, которые отображают X в X. Это так! Вы переходите от мысли о состоянии думать о том, какие операции вы хотите выполнять в государстве. Затем вы можете объединить эти функции и объединить их разными способами для создания целых программ. Конечно, вы не ограничены только отображением X на X. Вы можете писать функции, чтобы принимать различные комбинации данных в качестве входных данных и возвращать различные комбинации в конце.

Монады - один из многих способов помочь организовать это. Но монады на самом деле не являются решением проблемы. Решение состоит в том, чтобы думать о преобразованиях состояний вместо состояния.

Это также работает с I/O. Фактически, это происходит: вместо того, чтобы вводить пользователя с каким-то прямым эквивалентом scanf и хранить его где-то, вместо этого вы пишете функцию, чтобы сказать, что вы сделали бы с результатом scanf, если бы вы его, а затем передать эту функцию API-интерфейсу ввода-вывода. То, что >>= делает, когда вы используете монаду IO в Haskell. Поэтому вам никогда не нужно записывать результат любого ввода-вывода в любом месте - вам просто нужно написать код, в котором говорится, как вы хотите его преобразовать.

Ответ 6

(Некоторые функциональные языки допускают нечистые функции.)

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

RealWorld pureScanf(RealWorld world, const char* format, ...);

Различные языки имеют разные стратегии, чтобы отвлечь мир от программиста. Например, Haskell использует монады, чтобы скрыть аргумент world.

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

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

Вы включаете часть модификации в вызов функции, обычно поворачивая петли в рекурсии:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

Ответ 7

Функциональный язык может сохранить состояние! Обычно они просто поощряют или заставляют вас быть откровенными в этом.

Например, проверьте Haskell State Monad.

Ответ 8

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

Ответ 9

Haskell:

main = do no <- readLn
          print (no + 1)

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