Может ли * любая * задача программы быть выражена без состояния?

13

Это теоретический вопрос, но после многих лет программирования в том, что, как я теперь понимаю, является «нормальной» императивной техникой, в основном с использованием C ++, я открыл для себя этот другой мир функционального программирования, на который я наткнулся случайно, случайно изучая JavaScript.

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

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

johnbakers
источник
1
Соответствующий ответ StackOverflow: stackoverflow.com/questions/3722084/…
jfriend00
Независимо от того, существует ли состояние, которое сохраняется от одного момента времени к другому, зависит не от того, какую программную парадигму вы используете, а от того, какую проблему или задачу вы кодируете. Если вы подсчитываете количество нажатий кнопки, то, очевидно, существует состояние для записи этого счетчика, и не имеет значения, какую технику кодирования вы используете, должно быть состояние, чтобы отслеживать счет во время процесса. Таким образом, эта конкретная задача не может быть выполнена без указания состояния, независимо от того, как вы ее кодируете.
Jfriend00
6
Если вы хотите обсудить состояние; однозначно государство требуется, хотя бы для самой программы. Звучит так, будто вы думаете о изменчивом и неизменном состоянии - вы можете указать, что вы имеете в виду в вопросе.
Билли ОНил
1
Это все равно, что спросить, все ли программы могут быть преобразованы в настоящие машины Тьюринга. Технически да, даже программы, которые сохраняют и загружают из базы данных, однако становится все труднее моделировать это поведение на машине Тьюринга. Аналогично, вы могли бы иметь программу, сторона контроллера которой в архитектуре MVC удалена, и вы выполняете все вызовы, хотя, опять же, с ней становится сложнее работать (вы, по сути, становитесь контроллером, чтобы сделать программу без сохранения состояния).
Нил

Ответы:

17

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

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

Док Браун
источник
2
Ваш тот же аргумент может быть отменен, говоря, что, будучи исчислением лямбы, эквивалентным путешествующим машинам, каждое вычисление должно иметь (более или менее скрытое) состояние. Является ли is представленным как внешний по отношению к коду (посредством переменных) или как внутренний по отношению к потоку (посредством вызова функции на основе стека), всегда «состояние» есть.
Эмилио Гаравалья
3
Лямбда-исчисление имеет состояние; его ограничение заключается в том, что государство является неизменным. Неизменное состояние остается государственным. Параметры функций, включая лямбды, все еще находятся в состоянии; предположительно, вы хотите, чтобы у функции было другое поведение при разных параметрах.
Билли Онил
@emilio Заявление о том, что существует эквивалентное решение проблемы на основе состояния (как вы описываете), не является доказательством того, что не существует версии этого решения без сохранения состояния.
Билли ONEAL
2
@EmilioGaravaglia, то вы ссылаетесь на состояние интерпретатора лямбда-исчисления. При рассуждении в лямбда-исчислении нет необходимости рассуждать о состоянии. Также аспект "изменчивости" отличается.
wirrbel
1
@EmilioGaravglia: Состояние в императивном программировании - это конфигурация памяти за раз, здесь пространство параметров задается всеми возможными значениями памяти, а состояние - это одна конфигурация за один раз (диапазон машины Тьюринга). При написании программы в лямбда-исчислении не существует прямой сущности, такой как поле памяти. Выполнение программы - это применение лямбда-преобразований. Промежуточные шаги могут напоминать «состояние», но они являются просто эквивалентными выражениями одного и того же значения. Ничего не меняется во время оценки, выражения просто переписываются и обрабатываются в «более простую» форму.
wirrbel
14

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

Есть ли у вас что-то, чтобы «запомнить», или это зависит от того, что вы сделали, у вас есть состояние.

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

Теперь, в зависимости от вычислительной модели, на которую вы ссылаетесь, состояние может быть представлено явно (в форме переменной) или неявно (в форме «адреса возврата»).

когда вы это делаете, fna(fnb(x))вы даете состояние fnb, которое, в свою очередь, создает состояние для fna. Это связано с тем, что xсуществуют до вызова fnb (то есть из своего «прошлого»).

Дело не в «государственном существовании» или «государстве не существует». Это вопрос «Я забочусь» или «Я не забочусь».

Эмилио Гаравалья
источник
0

Состояние означает способность реагировать на текущий стимул таким образом, который зависит от прошлых стимулов, а не только на основе настоящего стимула.

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

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

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

Atsby
источник
0

Вы можете избежать явного изменяемого состояния, если вам не нужно взаимодействовать с внешним миром.

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

Конечно, вы по-прежнему полагаетесь на состояние, так как окно браузера и DOM по своей природе являются состояниями. Любому интерактивному приложению присуще состояние с сохранением состояния, но вы все равно можете структурировать свой код так, чтобы минимизировать явное состояние.

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

JacquesB
источник
0

Подумайте, как бы вы реализовали «конечный автомат» на языке программирования без состояния.

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

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()
Джеймс Андерсон
источник