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

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

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

Как знание лямбда-исчисления полезно в функциональном программировании.

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

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

plus3 x = succ(succ(succ x)) 

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

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

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

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

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

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

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

Аргумент f используется в позиции функции (при вызове). Мы вызываем функцию g более высокого порядка, потому что она принимает другую функцию в качестве входных данных. {{1 }} Вы можете думать о других вызовах функции 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 Аллигатор ест нашего λ x Аллигатора и тогда λ x Аллигатор и умирает. Затем наш Аллигатор λ x возрождается в яйцах Аллигатора λ f. Затем процесс повторяется, и аллигатор λ x слева теперь ест другого аллигатора λ x справа.

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

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

haskell:

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

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

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

Например, посмотрите Haskell's State Monad .

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

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

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

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

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

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

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

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

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

Так что это, вероятно, показалось немного обманом, каким-то образом добавляющим примеси в чистый Haskell. Но это не так - оказывается, что мы можем реализовать тип ввода-вывода полностью в чистом Haskell (пока нам дан RealWorld ). Идея заключается в следующем: действие ввода-вывода Тип ввода-вывода совпадает с функцией RealWorld -> (тип, RealWorld) , которая принимает реальный мир и возвращает как объект типа типа и модифицированного 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'

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

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

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

Запуск среды выполнения Haskell main с начальным RealWorld ], и мы готовы! Все чисто, просто имеет навороченный синтаксис.

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

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

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

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

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

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

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

Я писал:

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

Norman писал:

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

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

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

(Из доклада Саймона ПиДжея на POPL Wearing the hair shirt Wearing the hair shirt: a retrospective on Haskell.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но сама чистая часть функционального языка уже является полной по Тьюрингу, то есть все, что можно сделать на 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);
}

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

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

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

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

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

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