Как вы можете сделать что-нибудь полезное без изменяемого состояния?

265

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

Почти каждое пользовательское приложение, которое я могу представить, включает в себя состояние как основную концепцию. Если вы пишете документ (или сообщение SO), состояние меняется с каждым новым вводом. Или, если вы играете в видеоигру, существует множество переменных состояния, начиная с позиций всех персонажей, которые имеют тенденцию постоянно перемещаться. Как вы можете сделать что-нибудь полезное, не отслеживая изменения значений?

Каждый раз, когда я нахожу что-то, что обсуждает эту проблему, это написано в действительно техническом функционале, который предполагает тяжелый фон FP, которого у меня нет. Кто-нибудь знает способ объяснить это кому-то с хорошим, твердым пониманием императивного кодирования, но кто полный n00b с функциональной стороны?

РЕДАКТИРОВАТЬ: куча ответов до сих пор, кажется, пытаются убедить меня в преимуществах неизменных ценностей. Я получил эту часть. Это имеет смысл. Чего я не понимаю, так это как вы можете отслеживать значения, которые должны меняться, и постоянно меняться без изменяемых переменных.

Мейсон Уилер
источник
2
Смотрите это: stackoverflow.com/questions/844536/…
Саша Чедыгов
1
Мое личное скромное мнение таково, что это как сила и деньги. Действует закон убывающей доходности. Если вы достаточно сильны, у вас может быть немного стимула стать немного сильнее, но это не помешает работать над этим (а некоторые люди делают это со страстью). То же касается и глобального изменяемого состояния. Я лично согласен с тем, что по мере развития моих навыков кодирования полезно ограничивать количество глобальных изменяемых состояний в моем коде. Возможно, оно никогда не будет идеальным, но хорошо бы работать для минимизации глобального изменчивого состояния.
AturSams
Как и в случае с деньгами, точка будет достигнута, если инвестировать в нее больше времени, она больше не будет очень полезной, а другие приоритеты поднимутся на вершину. Например, если вы достигнете максимально возможной силы (согласно моей метафоре), это может не служить какой-либо полезной цели и даже может стать бременем. Но все же хорошо стремиться к этой, возможно, недостижимой цели и вкладывать в нее умеренные ресурсы.
AturSams
7
Вкратце, в FP функции никогда не изменяют состояние. В конце концов они вернут то, что заменяет текущее состояние. Но состояние никогда не изменяется (видоизменяется) на месте.
Jinglesthula
Есть способы получить состояние без мутаций (используя стек из того, что я понимаю), но этот вопрос в некотором смысле не имеет смысла (хотя он и великолепен). Трудно говорить кратко, но вот пост, который, мы надеемся, ответит на ваш вопрос medium.com/@jbmilgrom/… . TLDR заключается в том, что семантика даже функциональной программы с состоянием является неизменной, однако чередование ч / б функции программы обрабатывается.
jbmilgrom

Ответы:

166

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

Если вам интересно, вот серия статей, которые описывают программирование игр с Erlang.

Вам, вероятно, не понравится этот ответ, но вы не получите функциональную программу, пока не воспользуетесь ею. Я могу опубликовать примеры кода и сказать: «Вот, разве вы не видите », но если вы не понимаете синтаксис и основополагающие принципы, тогда ваши глаза просто глазурят. С вашей точки зрения, похоже, что я делаю то же самое, что и императивный язык, но просто устанавливаю все виды границ, чтобы целенаправленно усложнять программирование. Моя точка зрения, вы просто испытываете парадокс Блюба .

Сначала я был настроен скептически, но несколько лет назад я запрыгнул на поезд по функциональному программированию и влюбился в него. Уловка с функциональным программированием заключается в способности распознавать шаблоны, конкретные назначения переменных и перемещать императивное состояние в стек. Например, цикл for становится рекурсией:

// Imperative
let printTo x =
    for a in 1 .. x do
        printfn "%i" a

// Recursive
let printTo x =
    let rec loop a = if a <= x then printfn "%i" a; loop (a + 1)
    loop 1

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

// Preferred
let printTo x = seq { 1 .. x } |> Seq.iter (fun a -> printfn "%i" a)

Метод Seq.iter будет перечислять в коллекции и вызывать анонимную функцию для каждого элемента. Очень кстати :)

Я знаю, печать цифр не очень впечатляет. Однако мы можем использовать тот же подход с играми: удерживать все состояния в стеке и создавать новый объект с нашими изменениями в рекурсивном вызове. Таким образом, каждый кадр представляет собой моментальный снимок игры без сохранения состояния, где каждый кадр просто создает новый объект с желаемыми изменениями любых объектов без сохранения состояния, которые необходимо обновить. Псевдокод для этого может быть:

// imperative version
pacman = new pacman(0, 0)
while true
    if key = UP then pacman.y++
    elif key = DOWN then pacman.y--
    elif key = LEFT then pacman.x--
    elif key = UP then pacman.x++
    render(pacman)

// functional version
let rec loop pacman =
    render(pacman)
    let x, y = switch(key)
        case LEFT: pacman.x - 1, pacman.y
        case RIGHT: pacman.x + 1, pacman.y
        case UP: pacman.x, pacman.y - 1
        case DOWN: pacman.x, pacman.y + 1
    loop(new pacman(x, y))

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

Это масштабируется до любого количества объектов в игре, потому что все объекты (или коллекции связанных объектов) могут быть представлены в их собственном потоке.

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

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

using System;

namespace ConsoleApplication1
{
    static class Stack
    {
        public static Stack<T> Cons<T>(T hd, Stack<T> tl) { return new Stack<T>(hd, tl); }
        public static Stack<T> Append<T>(Stack<T> x, Stack<T> y)
        {
            return x == null ? y : Cons(x.Head, Append(x.Tail, y));
        }
        public static void Iter<T>(Stack<T> x, Action<T> f) { if (x != null) { f(x.Head); Iter(x.Tail, f); } }
    }

    class Stack<T>
    {
        public readonly T Head;
        public readonly Stack<T> Tail;
        public Stack(T hd, Stack<T> tl)
        {
            this.Head = hd;
            this.Tail = tl;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Stack<int> x = Stack.Cons(1, Stack.Cons(2, Stack.Cons(3, Stack.Cons(4, null))));
            Stack<int> y = Stack.Cons(5, Stack.Cons(6, Stack.Cons(7, Stack.Cons(8, null))));
            Stack<int> z = Stack.Append(x, y);
            Stack.Iter(z, a => Console.WriteLine(a));
            Console.ReadKey(true);
        }
    }
}

Приведенный выше код создает два неизменяемых списка, складывает их вместе, чтобы создать новый список, и добавляет результаты. Никакое изменяемое состояние не используется нигде в приложении. Это выглядит немного громоздко, но это только потому, что C # - многословный язык. Вот эквивалентная программа на F #:

type 'a stack =
    | Cons of 'a * 'a stack
    | Nil

let rec append x y =
    match x with
    | Cons(hd, tl) -> Cons(hd, append tl y)
    | Nil -> y

let rec iter f = function
    | Cons(hd, tl) -> f(hd); iter f tl
    | Nil -> ()

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
let y = Cons(5, Cons(6, Cons(7, Cons(8, Nil))))
let z = append x y
iter (fun a -> printfn "%i" a) z

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

Используя более важный пример, я также написал этот синтаксический анализатор SQL, который полностью не имеет состояния (или, по крайней мере, мой код не имеет состояния, я не знаю, является ли лежащая в основе библиотека лексирования без сохранения состояния).

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

Джульетта
источник
7
Мне нравится пример Пакмана. Но это может решить одну проблему только для того, чтобы поднять другую: что если что-то еще содержит ссылку на существующий объект Pacman? Тогда он не будет собирать мусор и заменять его; вместо этого вы получите две копии объекта, одна из которых недействительна. Как вы справляетесь с этой проблемой?
Мейсон Уилер
9
Очевидно, вам нужно создать новое «что-то еще» с новым объектом Pacman;) Конечно, если мы зайдем слишком далеко, мы в конечном итоге создадим заново граф объектов для всего нашего мира каждый раз, когда что-то меняется. Лучший подход описан здесь ( prog21.dadgum.com/26.html ): вместо того, чтобы объекты обновляли себя и все свои зависимости, гораздо проще заставить их передавать сообщения о своем состоянии в цикл обработки событий, который обрабатывает все обновление. Это значительно облегчает решение о том, какие объекты в графе необходимо обновить, а какие нет.
Джульетта
6
@ Джульетта, у меня есть одно сомнение - в моем полностью императивном мышлении рекурсия должна закончиться в какой-то момент, иначе в конечном итоге вы получите переполнение стека. В рекурсивном примере pacman, как стопроцентно удерживается стек - неявно ли выталкивается объект в начале функции?
BlueStrat
9
@BlueStrat - хороший вопрос ... если это "хвостовой вызов" ... т.е. рекурсивный вызов - это последнее, что есть в функции ... тогда системе не нужно генерировать новый кадр стека ... это может просто используйте предыдущий. Это общая оптимизация для функциональных языков программирования. en.wikipedia.org/wiki/Tail_call
reteptilian
4
@MichaelOsofsky, при взаимодействии с базами данных и API всегда существует «внешний мир», с которым есть состояние, с которым можно общаться. В этом случае вы не можете перейти на 100% функциональность. Важно сохранить этот «нефункциональный» код изолированным и абстрагированным, чтобы была только одна запись и один выход во внешний мир. Таким образом, вы можете сохранить оставшуюся часть кода функциональной.
Chielt
76

Краткий ответ: вы не можете.

Так в чем же суть неизменности?

Если вы хорошо разбираетесь в императивном языке, то вы знаете, что «глобалы плохие». Зачем? Потому что они вводят (или имеют потенциал для внедрения) некоторые очень трудно распутываемые зависимости в вашем коде. И зависимости не хороши; Вы хотите, чтобы ваш код был модульным . Части программы не влияют на другие части как можно меньше. И FP приводит вас к святому Граалю модульности: никаких побочных эффектов вообще . Вы просто имеете свой f (x) = y. Положи х, получи уй. Без изменений х или чего-либо еще. FP заставляет вас перестать думать о состоянии и начать думать с точки зрения ценностей. Все ваши функции просто получают значения и производят новые значения.

Это имеет несколько преимуществ.

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

Во-вторых, это делает программу тривиально распараллеливаемой (другое дело - эффективное распараллеливание).

В-третьих, есть несколько возможных преимуществ производительности. Скажем, у вас есть функция:

double x = 2 * x

Теперь вы вводите значение 3, и вы получаете значение 6. Каждый раз. Но вы можете сделать это в обязательном порядке, верно? Ага. Но проблема в том, что в императиве вы можете сделать еще больше . Я могу сделать:

int y = 2;
int double(x){ return x * y; }

но я мог бы также сделать

int y = 2;
int double(x){ return x * (y++); }

Императивный компилятор не знает, будут ли у меня побочные эффекты или нет, что усложняет оптимизацию (т. Е. Double 2 не обязательно должно быть 4 каждый раз). Функциональный знает, что я не буду - следовательно, он может оптимизировать каждый раз, когда он видит "двойные 2".

Теперь, хотя создание новых значений каждый раз кажется невероятно расточительным для сложных типов значений с точки зрения памяти компьютера, это не обязательно должно быть так. Потому что, если у вас есть f (x) = y, а значения x и y "в основном одинаковы" (например, деревья, которые отличаются только несколькими листами), то x и y могут совместно использовать части памяти - потому что ни одно из них не будет мутировать ,

Так что, если эта неизменяемая вещь настолько хороша, почему я ответил, что без изменяемого состояния вы не сможете сделать ничего полезного. Ну, без изменчивости, вся ваша программа была бы гигантской функцией f (x) = y. И то же самое относится ко всем частям вашей программы: только к функциям и функциям в «чистом» смысле. Как я уже сказал, это означает, что f (x) = y каждый раз. Так, например, readFile ("myFile.txt") должен будет возвращать одно и то же строковое значение каждый раз. Не слишком полезно

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

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

Oggy
источник
2
<< readFile ("myFile.txt") должен будет возвращать одно и то же строковое значение каждый раз. Не слишком полезно. >> Я предполагаю, что это полезно, пока вы скрываете глобальную файловую систему. Если вы рассматриваете его как второй параметр и позволяете другим процессам возвращать новую ссылку на файловую систему каждый раз, когда они изменяют ее с помощью filesystem2 = write (filesystem1, fd, pos, "string"), и позволяют всем процессам обмениваться ссылками на файловую систему мы могли бы получить более чистую картину операционной системы.
угорь ghEEz
@eelghEEz, это тот же подход, который Datomic применяет к базам данных.
Джейсон
1
+1 за четкое и краткое сравнение парадигм. Одно из предложений состоит в int double(x){ return x * (++y); }том, что текущим будет 4, хотя у него все еще будет непредсказуемый побочный эффект, а ++yвернется 6.
BrainFRZ
@eelghEEz Я не уверен в альтернативе, правда, кто-нибудь еще? Чтобы ввести информацию в (чистый) контекст FP, вы «проводите измерение», например, «при отметке времени X температура равна Y». Если кто-то спрашивает о температуре, он может неявно означать X = сейчас, но он не может запрашивать температуру как универсальную функцию времени, верно? FP имеет дело с неизменным состоянием, и вы должны создать неизменное состояние - из внутренних и внешних источников - из изменяемого. Индексы, временные метки и т. Д. Полезны, но ортогональны изменчивости - подобно VCS для контроля версий.
Джон П
29

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

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

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

Приложение: (Относительно вашего редактирования того, как отслеживать значения, которые нужно изменить)
Конечно, они будут храниться в неизменной структуре данных ...

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

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

jerryjvl
источник
2
ОК, я изменил название. Ваш ответ, похоже, приводит к еще худшей проблеме. Если мне придется воссоздавать каждый объект каждый раз, когда что-то в его состоянии изменяется, я буду тратить все свое процессорное время, занимаясь только созданием объектов. Я имею в виду программирование игр здесь, когда на экране (и за кадром) одновременно перемещается множество вещей, которые должны иметь возможность взаимодействовать друг с другом. Весь движок имеет установленную частоту кадров: все, что вы собираетесь делать, вы должны делать за X миллисекунд. Конечно, есть лучший способ, чем постоянно перерабатывать целые объекты?
Мейсон Уилер
4
Прелесть этого в том, что неизменность зависит от языка, а не от реализации. С помощью нескольких приемов вы можете получить неизменное состояние в языке, в то время как реализация фактически меняет его на месте. Смотрите, например, ST монаду Haskell.
CesarB
4
@Mason: Дело в том, что компилятор может гораздо лучше решить, где (поток) безопасно изменить состояние на месте, чем вы можете.
jerryjvl
Я думаю, что для игр вы должны избегать неизменности для любых частей, где скорость не имеет значения. В то время как неизменный язык может оптимизировать для вас, ничто не будет быстрее, чем изменение памяти, что быстры в процессорах. И поэтому, если окажется, что есть 10 или 20 мест, где вам нужен императив, я думаю, что вам следует просто полностью избегать неизменности, если вы не можете использовать его для модульных областей, таких как игровые меню. И игровая логика, в частности, может быть хорошим местом для использования неизменяемого, потому что я чувствую, что она отлично подходит для сложного моделирования чистых систем, таких как бизнес-правила.
LegendLength
@ LegendLength ты противоречишь себе.
Ixx
18

Я думаю, что есть небольшое недоразумение. Чисто функциональные программы имеют гос. Разница в том, как моделируется это состояние. В чисто функциональном программировании состоянием управляют функции, которые принимают некоторое состояние и возвращают следующее состояние. Последовательность через состояния затем достигается путем передачи состояния через последовательность чистых функций.

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

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

Рассмотрим этот код:

int x = 1;
int y = x + 1;
x = x + y;
return x;

Довольно болотный стандартный императивный код. Ничего интересного не делает, но это нормально для иллюстрации. Я думаю, вы согласитесь, что здесь участвует государство. Значение переменной x меняется со временем. Теперь давайте немного изменим обозначение, придумав новый синтаксис:

let x = 1 in
let y = x + 1 in
let z = x + y in z 

Поставьте скобки, чтобы было понятнее, что это значит:

let x = 1 in (let y = x + 1 in (let z = x + y in (z)))

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

Вы обнаружите, что этот шаблон может моделировать любое состояние, даже IO.

Apocalisp
источник
Это что-то вроде монады?
CMCDragonkai
Считаете ли вы это: A декларативным на уровне 1 B декларативным на уровне 2, он считает A императивным. C является декларативным на уровне 3, он считает, что B является обязательным условием. Поскольку мы увеличиваем уровень абстракции, он всегда считает языки ниже уровня абстракции более важными, чем он сам.
CMCDragonkai
14

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

f_imperative(y) {
  local x;
  x := e;
  while p(x, y) do
    x := g(x, y)
  return h(x, y)
}

становится этим функциональным кодом (Схемоподобный синтаксис):

(define (f-functional y) 
  (letrec (
     (f-helper (lambda (x y)
                  (if (p x y) 
                     (f-helper (g x y) y)
                     (h x y)))))
     (f-helper e y)))

или этот гаскельский код

f_fun y = h x_final y
   where x_initial = e
         x_final   = loop x_initial
         loop x = if p x y then loop (g x y) else x

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

Вы можете найти хороший учебник с множеством примеров в статье Джона Хьюза « Почему функциональное программирование имеет значение» .

Норман Рэмси
источник
13

Это просто разные способы сделать одно и то же.

Рассмотрим простой пример, такой как добавление чисел 3, 5 и 10. Представьте, что вы думаете об этом, сначала изменив значение 3, добавив к нему 5, затем добавьте 10 к этому «3», а затем выведите текущее значение « 3 "(18). Это кажется явно нелепым, но это, по сути, то, как часто выполняется государственное императивное программирование. Действительно, у вас может быть много разных «3», которые имеют значение 3, но разные. Все это кажется странным, потому что мы так глубоко укоренились в весьма разумной идее, что числа неизменны.

Теперь подумайте о добавлении 3, 5 и 10, когда вы принимаете значения неизменяемыми. Вы добавляете 3 и 5 для получения другого значения 8, затем добавляете 10 к этому значению для получения еще одного значения 18.

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

Клин
источник
10

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

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

Первый императивный путь (в псевдокоде)

moveTo(dest, cur):
    while (cur != dest):
         if (cur < dest):
             cur += 1
         else:
             cur -= 1
    return cur

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

predicate ? if-true-expression : if-false-expression

Вы можете связать троичное выражение, поместив новое троичное выражение вместо ложного выражения.

predicate1 ? if-true1-expression :
predicate2 ? if-true2-expression :
else-expression

Итак, имея в виду, вот функциональная версия.

moveTo(dest, cur):
    return (
        cur == dest ? return cur :
        cur < dest ? moveTo(dest, cur + 1) : 
        moveTo(dest, cur - 1)
    )

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

  1. Урок заключается в том, что функциональные языки «видоизменяют» состояние, вызывая функцию с различными параметрами. Очевидно, что на самом деле это не мутирует никакие переменные, но именно так вы получаете похожий эффект. Это означает, что вам придется привыкать к рекурсивному мышлению, если вы хотите заниматься функциональным программированием.

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

Я рекомендую сделать Little Schemer (обратите внимание, что я говорю «делать», а не «читать»), а затем выполнять все упражнения в SICP. Когда вы закончите, у вас будет другой мозг, чем когда вы начали.

Просто еще один Джастин
источник
8

На самом деле довольно легко иметь что-то, что выглядит как изменяемое состояние даже в языках без изменяемого состояния.

Рассмотрим функцию с типом s -> (a, s). В переводе с синтаксиса Haskell это означает, что функция принимает один параметр типа " s" и возвращает пару значений типов " a" и " s". Если sэто тип нашего состояния, эта функция принимает одно состояние и возвращает новое состояние и, возможно, значение (вы всегда можете вернуть «единицу измерения» (), что эквивалентно « void» в C / C ++, как « a» тип). Если вы объединяете несколько вызовов функций с такими типами (получение состояния, возвращаемого из одной функции и передача его следующей), вы получаете «изменяемое» состояние (фактически вы находитесь в каждой функции, создавая новое состояние и отказываясь от старого. ).

Может быть легче понять, если вы представляете изменяемое состояние как «пространство», в котором выполняется ваша программа, а затем думаете о временном измерении. В момент времени t1 «пространство» находится в определенном состоянии (например, некоторая ячейка памяти имеет значение 5). В более поздний момент времени t2 он находится в другом состоянии (например, ячейка памяти теперь имеет значение 10). Каждый из этих временных «кусочков» является состоянием, и оно является неизменным (вы не можете вернуться во времени, чтобы изменить их). Итак, с этой точки зрения вы перешли от полного пространства-времени со стрелкой времени (ваше изменяемое состояние) к набору кусочков пространства-времени (несколько неизменяемых состояний), и ваша программа просто обрабатывает каждый кусочек как значение и вычисляет каждый из них как функция, примененная к предыдущему.

ОК, может быть, это было не легче понять :-)

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

В качестве примера предположим, что компилятор предоставляет нам следующие функции:

readRef :: Ref a -> State# -> (a, State#)
writeRef :: Ref a -> a -> State# -> (a, State#)

Переводя из этих объявлений, подобных Haskell, readRefполучает что-то, напоминающее указатель или дескриптор, значение типа " a" и ложное состояние, и возвращает значение типа " a", на которое указывает первый параметр, и новое ложное состояние. writeRefаналогично, но изменяет значение, на которое указывает

Если вы вызываете readRefи затем передаете ему ложное состояние, возвращаемое writeRef(возможно, с другими вызовами несвязанных функций в середине; эти значения состояния создают «цепочку» вызовов функций), он вернет записанное значение. Вы можете вызывать writeRefснова с тем же указателем / дескриптором, и он будет записывать в ту же ячейку памяти, но, поскольку концептуально он возвращает новое (поддельное) состояние, состояние (поддельное) все еще остается неизменным (новое было создано «). Компилятор будет вызывать функции в том порядке, в котором он должен был бы вызывать их, если бы существовала переменная реального состояния, которую нужно было вычислить, но единственным состоянием, которое там было, является полное (изменяемое) состояние реального оборудования.

(Те , кто знает Haskell заметит я упростил вещи много и несколько важных опущен деталей. Для тех , кто хочет видеть больше деталей, посмотрите на Control.Monad.Stateот mtl, так и на ST sи IO(AKA ST RealWorld) монад.)

Вы можете задаться вопросом, зачем делать это окольным путем (вместо того, чтобы просто иметь изменяемое состояние в языке). Настоящее преимущество в том, что вы улучшили состояние своей программы. То, что раньше было неявным (состояние вашей программы было глобальным, учитывая такие вещи, как действие на расстоянии ), теперь явное. Функции, которые не получают и не возвращают состояние, не могут изменять его или влиять на него; они "чисты". Более того, у вас могут быть отдельные потоки состояний, и с небольшим количеством магии типов они могут использоваться для встраивания императивных вычислений в чистые, не делая их нечистыми ( STмонада в Хаскеле - та, которая обычно используется для этого трюка; State#я уже упоминал выше, в том , GHC, State# s, используется его реализации из STиIO монады).

CesarB
источник
7

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

Jherico
источник
Когда я был более антифункциональным, я задавался вопросом, как может быть хорошо, когда что-то вроде жесткого диска изменчиво. Все мои c # классы были в изменяемом состоянии и могли очень логически моделировать жесткий диск или любое другое устройство. В то время как с функционалом было несоответствие между моделями и реальными машинами, которые они моделировали. Углубившись в функционал, я понял, что преимущества, которые вы получаете, могут значительно перевесить этот вопрос. И если бы было физически возможно изобрести жесткий диск, который сделал бы саму копию, это было бы на самом деле полезно (как это уже делает журнал).
LegendLength
5

В дополнение к отличным ответам, которые дают другие, подумайте о классах Integerи о StringJava. Экземпляры этих классов являются неизменяемыми, но это не делает классы бесполезными только потому, что их экземпляры нельзя изменить. Неизменность дает вам некоторую безопасность. Вы знаете, что если вы используете экземпляр String или Integer в качестве ключа Map, ключ не может быть изменен. Сравните это с Dateклассом в Java:

Date date = new Date();
mymap.put(date, date.toString());
// Some time later:
date.setTime(new Date().getTime());

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

Эдди
источник
2
Я понимаю это, но это не отвечает на мой вопрос. Помня, что компьютерная программа - это модель какого-то реального события или процесса, если вы не можете изменить свои значения, то как вы смоделируете что-то, что изменится?
Мейсон Уилер
Ну, вы, безусловно, можете делать полезные вещи с классами Integer и String. Это не значит, что их неизменность означает, что вы не можете иметь изменяемое состояние.
Эдди
@ Мейсон Уилер - Понимая, что вещь и ее состояние - это две разные "вещи". Что такое pacman, не меняется со времени A на время B. Где pacman действительно меняется. Когда вы переходите от времени A ко времени B, вы получаете новую комбинацию pacman + state ... это один и тот же pacman, другое состояние. Не изменилось состояние ... другое состояние.
RHSeeger
4

Для интерактивных приложений, таких как игры, функциональное реактивное программирование - ваш друг: если вы можете сформулировать свойства игрового мира в виде изменяющихся во времени значений (и / или потоков событий), вы готовы! Эти формулы иногда будут даже более естественными и более интересными, чем изменение состояния, например, для движущегося шара вы можете напрямую использовать известный закон x = v * t . И что еще лучше, правила игры, написанные таким образом, сочетаются лучше, чем объектно-ориентированные абстракции. Например, в этом случае скорость мяча может быть также изменяющейся во времени величиной, которая зависит от потока событий, состоящего из столкновений мяча. Для получения более подробной информации о дизайне см. Создание игр в Elm .

thSoft
источник
4

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

а также раскатывающиеся демки:

и визуализации:

Пол Суатте
источник
3

Вот как FORTRAN будет работать без блоков COMMON: вы будете писать методы, в которых будут значения, которые вы передали, и локальные переменные. Вот и все.

Объектно-ориентированное программирование объединило нас в состояние и поведение, но это была новая идея, когда я впервые столкнулся с ней из C ++ в 1994 году.

Боже, я был функциональным программистом, когда был инженером-механиком, и я этого не знал!

duffymo
источник
2
Я бы не согласился, что это то, что вы можете прикрепить на ОО. Языки до ОО поощряли соединение состояний и алгоритмов. ОО просто предоставил лучший способ управлять им.
Джейсон Бейкер
«Ободренный» - возможно. ОО сделайте это явной частью языка. Вы можете делать инкапсуляцию и скрывать информацию в C, но я бы сказал, что ОО-языки делают это намного проще.
duffymo
2

Имейте в виду: функциональные языки Тьюринга полны. Поэтому любое полезное задание, которое вы выполняете на непостоянном языке, может быть выполнено на функциональном языке. В конце концов, я думаю, что можно сказать о гибридном подходе. Такие языки, как F # и Clojure (и я уверен, что другие) поощряют дизайн без сохранения состояния, но допускают изменчивость при необходимости.

Джейсон Бейкер
источник
Тот факт, что два языка Тьюринга завершены, не означает, что они могут выполнять одни и те же задачи. Это означает, что они могут выполнять одинаковые вычисления. Brainfuck завершен по Тьюрингу, но я вполне уверен, что он не может общаться через стек TCP.
RHSeeger
2
Конечно, это возможно. Имея такой же доступ к оборудованию, как, скажем, C, он может. Это не значит, что это будет практично, но такая возможность есть.
Джейсон Бейкер
2

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

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

Up.
источник
-3

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

Вот пример:

function ReadDataFromKeyboard() {
    $input_values = $_POST[];
    return $input_values;
}
function ProcessInformation($input_values) {
    if ($input_values['a'] > 10)
        return ($input_values['a'] + $input_values['b'] + 3);
    else if ($input_values['a'] > 5)
        return ($input_values['b'] * 3);
    else
        return ($input_values['b'] - $input_values['a'] - 7);
}
function DisplayToPage($data) {
    print "Based your input, the answer is: ";
    print $data;
    print "\n";
}

/* begin: */
DisplayToPage (
    ProcessInformation (
        GetDataFromKeyboard()
    )
);
Джон Доу
источник
Джон, что это за язык?