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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

Это все, что вам нужно знать, чтобы использовать IO в 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и мы готовы! Все чисто, у него просто причудливый синтаксис.

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

Answer 3

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

Я написал:

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

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

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

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

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

Answer 7

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

Например, проверьте Государственную Монаду Хаскелла.

Answer 8

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

Answer 9

Haskell:

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

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

Answer 10

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

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

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

Очень осторожно!

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

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

---

^{... погоди: «поистине бесконечное количество операций, ориентированных на ввод-вывод»? Конечная реализация не может вместить все это, поэтому полностью денотативный язык всегда будет каким-то образом ограничен в отношении внешнего взаимодействия своих программ. Поэтому ввод-вывод всегда должен быть частью любого языка программирования общего назначения.}