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

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

Например: как эта простая вещь C может быть переведена на функциональный язык программирования, такой как Haskell?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(Мой вопрос был вдохновлен этим отличным постом: «Исполнение в царстве существительных» . Прочитав его, я смог лучше понять, что такое объектно-ориентированное программирование, как Java реализует его одним крайним способом и насколько языки функционального программирования контраст.)

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

Как вы уже поняли, функциональное программирование не имеет состояния, но это не значит, что оно не может хранить данные. Разница в том, что если я напишу оператор (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возвращает объект IO String, который можно рассматривать двумя способами: во-первых, как действие, которое при запуске создает строку; во-вторых, как строка, "испорченная" ИО, поскольку она была получена нечисто. Первый более правильный, но второй может оказаться более полезным. <-Берет Stringиз ряда IO Stringи сохраняет его в strбут , так как мы находимся в действии IO, мы должны обернуть его резервную копию, поэтому он не может «бежать». Следующая строка пытается прочитать целое число (reads ) и захватывает первое успешное совпадение (fst . head); это все чисто (без ввода-вывода), поэтому мы даем ему имя с помощью ).let no = .... Затем мы можем использовать оба noи strв .... Таким образом, мы сохранили нечистые данные (из getLineв str) и чистые данные (let no = ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я написал:

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

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

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

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

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

(Из выступления Саймона ПиДжея о POPL « Носить рубашку для волос». Носить рубашку для волос: ретроспектива на Haskell .)

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

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

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

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

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

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

Итак, 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 как об аргументе (функции лямбда-исчисления на самом деле предполагают, что они имеют только один аргумент), а остальное вы можете рассматривать как тело функции.

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

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

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

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

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

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

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

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

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

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);
}

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

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

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

haskell:

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

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