Глобальное состояние в ФП

Ага, «глобальное».

Что тебя смущает, мудило? Если у меня в шелле глобальная переменная определена, значит и в твоем тоже будет? Или в твоем недомозге?

Да, см пример с МТ в начале топика, может так дойдет. Состояние машины с глобальным состоянием детерменировано положением вычислителя во времени-пространстве.

детка, в общем случае в ФП каждая функция выполняется в своём контексте, и имеет своё состояние. Слово «своё» тебе понятно? Это антоним к «глобальное». И МТ тут вообще не при чём. Это лишь одна из возможных реализаций. Представь себе МТ с бесконечным числом лент, на каждой из которых одновременно выполняются бесконечное число операций, в т.ч. и переключение входной ленты на любую выходную в любое её место. Получишь ФП.

Представь себе МТ с бесконечным числом лент, на каждой из которых одновременно выполняются бесконечное число операций, в т.ч. и переключение входной ленты на любую выходную в любое её место. Получишь ФП.

Описанная тобой машина эквивалентна классической МТ с одной бесконечной лентой. Разницы вообще нет.

А, пардон, уточни, что значит «одновременно»? Сразу не заметил. Как одна головка может производить одновременно более 1-й операции?

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

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

Если у меня в шелле глобальная переменная определена, значит и в твоем тоже будет?

идиот, какие же они «глобальные», если они в разных шеллах? Они глобальные только внутри своего шелла.

Они глобальные только внутри своего шелла.

Ну так и состояние вычисления глобально только в рамках этого вычисления.

Описанная тобой машина эквивалентна классической МТ с одной бесконечной лентой. Разницы вообще нет.

ты просто не видишь разницы. Что-бы её осознать, напиши алгоритм, который работает на МТ №1, и узнаёт состояние МТ №2, в случае, если связи между МТ нет, и данные поступившие в МТ №2 неизвестны для МТ №1.

Ну к примеру узнай, какой стороной упадёт рубль, который я сейчас подброшу?

Нет, ты определись уже, что ты называешь МТ с несколькими лентами. В данном случае ты описываешь несколько независимых машин. Конкретезируй, наконец, что ты имеешь в виду, а то говорим о конях.

Держи ссылку — http://en.wikipedia.org/wiki/State_transition_system

As a mathematical object, an unlabeled state transition system is identical with an (unindexed) abstract rewriting system. If we consider the rewriting relation as an indexed set of relations, as some authors do, then a labeled state transition system is equivalent to an abstract rewriting system with the indices being the labels. The focus of the study and the terminology are different however. In a state transition system one is interested in interpreting the labels as actions, whereas in an abstract rewriting system the focus is on how objects may be transformed (rewritten) into others.

       | physics            | abstract machines    | term rewriting systems
-------+--------------------+----------------------+-------------------------------------
*      | state space        | set of states        | set of terms (language)
* -> * | evolution operator | translation function | reduction relation and its closures

Но не нужно сваливать в кучу — я кинул две ссылки на книжки про третий вариант (нетипизированный и в сторону логики и оснований) и одну про второй с третьим (там есть про построение http://en.wikipedia.org/wiki/SECD_machine, graph reduction, B-machines, G-machines для LC — глобальные состояния, все дела).

А, пардон, уточни, что значит «одновременно»? Сразу не заметил. Как одна головка может производить одновременно более 1-й операции?

кто сказал, что там одна головка? Впрочем это не важно. Важно то, что неизвестное состояние невозможно вычислить _любым_ алгоритмом.

Ну к примеру возьми два банкомата, и сначала у них есть связь, и они знают, что у меня на счету 1000руб. А если связь прервётся, то счетов станет 2. И если разрешённый овердрафт равен 200руб, то банкомат мне может дать не более 600руб, т.к. не знает, сколько даст второй. И рассчитывает на худший вариант, что я пойду ко второму, и сниму ещё 600руб. А может не пойду. Т.о. состояние моего счёта будет неизвестно ни одному из банкоматов. Фактически, мой счёт буду знать только я. А я к банкоматам не отношусь.

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

Но если ты считаешь, что ситуация, когда ты не знаешь, эквивалентна ситуации, когда ты делаешь тупой вид, но знаешь...

Ну так и состояние вычисления глобально только в рамках этого вычисления.

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

Я так понимаю, что «глобальное состояние» системы это множество её состояний :)

Т.е., например http://en.wikipedia.org/wiki/Turing_machine#Formal_definition — тут будет Q как состояния («глобальные», других же нет) машины, ну и ленту можно тоже умножить (типа code segment).

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

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

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

Гы, спасибо кэп, я даже догадываюсь как это называется — инкапсуляция. Непонятно тогда, зачем ты пытался расширять МТ, для прояснения этой простой мысли.

Ну к примеру возьми два банкомата, и сначала у них есть связь, и они знают, что у меня на счету 1000руб. А если связь прервётся, то счетов станет 2. И если разрешённый овердрафт равен 200руб, то банкомат мне может дать не более 600руб, т.к. не знает, сколько даст второй. И рассчитывает на худший вариант, что я пойду ко второму, и сниму ещё 600руб. А может не пойду. Т.о. состояние моего счёта будет неизвестно ни одному из банкоматов. Фактически, мой счёт буду знать только я. А я к банкоматам не отношусь.

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

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

В данном случае ты описываешь несколько независимых машин.

вот именно. В ФП оно так и есть. В принципе, в ФП всего одно состояние: «начать и кончить». И в принципе нельзя выделить «промежуточные состояния».

Это и называется «разделяемый ресурс»

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

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

Ты чо охренел чтоли? Все там есть, происходит, в лучшем случае, под капотом. А такой алгоритм, за который ты треш, в рамках чистого ФП вообще невозможен.

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

И в принципе нельзя выделить «промежуточные состояния».

Десятый раз объясняю, что в вычислении это легко выделяется — шаг редукции. И никаких «разных машин» там нет. Есть одна машина, которая выполняет код и имеет состояние, изменяющееся при каждой редукции. Это не МТ, разумеется.

Я так понимаю, что «глобальное состояние» системы это множество её состояний

теоретически да, на практике это состояние принципиально невозможно узнать иначе, кроме как остановив ВСЮ систему, и дождавшись завершения ВСЕХ транзакций.

Т.е. состояние существует только если ты всевидящий Бог, и можешь узнать ВСЕ состояния ОДНОВРЕМЕННО.

Конечно для нужд бекапов делают «снимок» системы скажем «в 20 часов». Но это состояние будет готово(как единое целое) не в 20 часов, а намного позже, пока затянется на сервер бекапов, и там соберётся.

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

не пори чушь, ей больно. Станешь Богом, тогда будешь писать такие графы. IRL получить состояние можно только намного позже момента потери актуальности. Причём начинать создавать нужно намного меньше. Т.е. в 19:00 ты начинаешь делать снимок 20:00, который будет готов(скорее всего, но не обязательно) в 21:00. И это при том, что сам снимок делается мгновенно.

Свои деревья можешь бросить в печь.

на практике это состояние принципиально невозможно узнать

Да какая нахрен разница, можно его узнать или нет. Вопрос в том, есть ли оно. И оно есть.

А путяга, в которой ты заканчивал своё образование - однозначно была для детей-инвалидов.

Откуда у тебя взялись какие-то моменты времени? В ФП нет времени.

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

Гы, спасибо кэп, я даже догадываюсь как это называется — инкапсуляция.

инкапсуляция тут не причём. Ты В ПРИНЦИПЕ НЕ МОЖЕШЬ ЗНАТЬ. А инкапсуляцию можешь вскрыть. Потому возможно только моделирование ФП на реальной локальной машины ФП. А вот на нескольких вычислителях ФП работает намного лучше, ибо там ресурсы УЖЕ разделены, и не нужно мучится их объединяя «типа в один», ну как память в CPU (IRL там же свои кеши на каждое ядро. А адрес типа один. Плюс ещё по тому же адресу обычная память)

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

нигде я не запутался: после выдачи денег ОБА банкомата не будут знать моего баланса. Т.е. банк тоже не будет знать(ну для простоты в банке всего два банкомата).

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

самое прямое. Кто в банке знает мой баланс после потери связи? Да, он «есть», но никому неизвестен(кроме Бога конечно). Это по твоему «есть»?

Ок, ты первый банкомат, на моём счету было 1000руб, а сколько сейчас? Отвечай, жду с нетерпением.

Ты про что-то своё («бекапы» и т.п.)?

теоретически да, на практике это состояние принципиально невозможно узнать

Потому что state != observable != measurement. Но состояния всё равно состояния, а для типичных (классических) абстрактных машин они ещё и доступны непосредственному наблюдению на метауровне.

не пори чушь, ей больно

Станешь Богом, тогда будешь писать такие графы

Т.е. в 19:00 ты начинаешь делать снимок 20:00, который будет готов(скорее всего, но не обязательно) в 21:00.

Точно про что-то своё.

http://en.wikipedia.org/wiki/Graph_reduction

http://en.wikibooks.org/wiki/Haskell/Graph_reduction

Свои деревья можешь бросить в печь.

То есть выбросить все языки, я понял (мы в абстрактом топике, можешь выбросить в печь свои ассоциации :)).

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

А что есть «ФП», фраза которую ты часто используешь?

В чистом ФП есть state monad (с операцией присваивания — меняй свой счёт, пожалуйста).

Есть explicit state добавленный к «ФП» до кучи сбоку (IO monad — тоже).

Глобального состояния в хаскеле нет. Это типа баго-фича — http://www.haskell.org/haskellwiki/Top_level_mutable_state.

У рантайма GHC который выполняет редукции и зовёт IO? Ну есть, конечно.

Абстрактного вычислителя который сопоставляется чистому языку переопределением термы = состояния, редукции = переходы? Ну раз определили понятия состояний, то вот они, да :)

Это как раз детали реализации, а речь — о модели вычислений.

Вот я и выясняю, является ли, с твоей точки зрения, этот «вычислитель» деталью реализации, а если нет — то почему.

Глобального состояния в хаскеле нет

Точнее, для такого-то набора глобальных переменных которые нам нужны можно написать трансформер (или один трансформер с одной динамической табличкой, но это не вполне Ъ в сравнении) и начать с main = runThisT $ do ... и верхним слоем в стеке приложения иметь этот ThisT. Но тогда следующим на очереди будет вопрос про TLS.

ФП не может «проскочить» сквозь редукцию

Что это вообще означает?

А что есть «ФП», фраза которую ты часто используешь?

Ну, я подразумеваю некое чистое ФП в вакууме:) Идеальное ФП, что то вроде lambda-calculus. Понятно, что в конкретных реализациях куча костылей для императивщины, иначе вообще ничего не напишешь. Но для понимания концепции удобно использовать идеальную модель.

этот «вычислитель» деталью реализации

Да я вообще не понимаю, о какой реализации ты говоришь. Является ли машина тьюринга деталью реализации процесса вычисления ей произвольного алгоритма?

Ну вот в самом чистом есть state monad, http://hackage.haskell.org/package/mtl-2.2.0.1/docs/src/Control-Monad-State-C....

IO monad тоже есть в самом чистом без всяких костылей — оно будет на выходе давать что-то вроде описания императивных действий (можно сделать им трансляцию в какой-нибудь императивный язык (в тот же хаскель :))). IO как абстрактный тип это просто какой-то абстрактный тип (которых можно сколько угодно добавить в язык), семантика есть, никаких костылей. У GHC IO это тот же state — Rts :: #; IO a = Rts -> (Rts, a), только с UB относительно неправильного вытаскивания a из Rts (можно упасть с лесенки :)).

Что это вообще означает?

1. (((/x -> /y -> x y ) expr2) expr1)
2. ((/y -> expr1 y) expr2) - шаг редукции, который ты не можешь не сделать, чтобы получилось
3. (expr1 expr2)

Неужели так трудно?

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

ничего я не путал. Включи мозг: представь, что у меня железная дорога, но одна колея. Но я всем говорю, что две колеи. А если так получилось, что надо пустить поезд на юг, а у меня уже идёт на север, я тяну время, и жду, пока поезд с юга проедет. Это разделяемый ресурс.

ФП это другое. Это когда у меня два паровоза. И машинисты без связи. Потому они могут _гарантировать_ доставку только половины груза. Или всего, но за двойное время(потому что второй машинист может уже договорился везти груз в два рейса). Или если рацию починят и связь наладят.

Т.е. в обоих случаях мы имеем «два паровоза» если повезёт, и один паровоз с гарантией. Но случаи принципиально разные.

Ты чо охренел чтоли? Все там есть, происходит, в лучшем случае, под капотом.

это ты охренел. Ясное дело, что клерки не знают, как работает софт в их банке. А ты что, клерк? А я на каком форуме, и в каком разделе?

А такой алгоритм, за который ты треш, в рамках чистого ФП вообще невозможен.

да, конечно. Рассказывай.

Мало того, в фп ты не можешь менять состояние ресурса, поэтому, если бы даже было по счету на каждый банкомат (что само по себе — бред)

а там оператор присваивания и не нужен. Счёт (мой) у каждого банкомата свой, локальный. Есть функция «выдать емулеку денег, если он хочет и вернуть остаток», и функция «проверить счёт емулека на другом банкомате(если есть связь), и вернуть остаток с учётом того, сколько емулек снял в другом банкомате», они и зациклены одна на другую(f1 вызывает f2, а f2 вызывает f1). Зачем тут operator=() ? Чистое ФП.

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

ничего я не путал. Включи мозг: представь, что у меня железная дорога, но одна колея. Но я всем говорю, что две колеи. А если так получилось, что надо пустить поезд на юг, а у меня уже идёт на север, я тяну время, и жду, пока поезд с юга проедет. Это разделяемый ресурс.

ФП это другое. Это когда у меня два паровоза. И машинисты без связи. Потому они могут _гарантировать_ доставку только половины груза. Или всего, но за двойное время(потому что второй машинист может уже договорился везти груз в два рейса). Или если рацию починят и связь наладят.

Т.е. в обоих случаях мы имеем «два паровоза» если повезёт, и один паровоз с гарантией. Но случаи принципиально разные.

Ты чо охренел чтоли? Все там есть, происходит, в лучшем случае, под капотом.

это ты охренел. Ясное дело, что клерки не знают, как работает софт в их банке. А ты что, клерк? А я на каком форуме, и в каком разделе?

А такой алгоритм, за который ты треш, в рамках чистого ФП вообще невозможен.

да, конечно. Рассказывай.

Мало того, в фп ты не можешь менять состояние ресурса, поэтому, если бы даже было по счету на каждый банкомат (что само по себе — бред)

а там оператор присваивания и не нужен. Счёт (мой) у каждого банкомата свой, локальный. Есть функция «выдать емулеку денег, если он хочет и вернуть остаток», и функция «проверить счёт емулека на другом банкомате(если есть связь), и вернуть остаток с учётом того, сколько емулек снял в другом банкомате», они и зациклены одна на другую(f1 вызывает f2, а f2 вызывает f1). Зачем тут operator=() ? Чистое ФП.

И в принципе нельзя выделить «промежуточные состояния».

Десятый раз объясняю, что в вычислении это легко выделяется — шаг редукции.

ещё раз: в ФП нет «времени» и нет «шагов». Ты это всё нафантазировал.

Да какая нахрен разница, можно его узнать или нет. Вопрос в том, есть ли оно. И оно есть.

блжад! Не тупи. У тебя есть 1000 рублей, которую ты в принципе не можешь потратить(например она фальшивая, и на ней х*й нарисован во всю купюру). У тебя есть 1000руб? Да нет у тебя ни*я. Другой пример: ты можешь зарабатывать в день по 100 рублей. Ты можешь в таких условиях купить личный самолёт? Да ты даже самокат не можешь купить! Ибо тебе даже на жрат не хватает. Ну а «в теории» можешь. Если будешь работать Over9000 лет, при этом ничего не жрать.

А путяга, в которой ты заканчивал своё образование - однозначно была для детей-инвалидов.

нет. Это у тебя школа была для инвалидов, из которой тебя выперли.

Ты про что-то своё («бекапы» и т.п.)?

просто, хотя в ФП и нет времени, IRL оно таки есть. И твои графы/деревья IRL тоже нужно бекапить (если они кому-то кроме тебя нужны конечно). Т.е. IRL имеется некоторое противоречие, которое требует разрешения. Но такому теоретику как ты, этого не понять.

Потому что state != observable != measurement. Но состояния всё равно состояния, а для типичных (классических) абстрактных машин они ещё и доступны непосредственному наблюдению на метауровне.

ЯННП

Точно про что-то своё.

это ты про что-то своё. При чём тут вообще какие-то глобальные состояния-то? Просто ты тут сворачиваешь одинаковые ветки дерева в одну ветку. Типичная оптимизация, и к последовательным вычислениям не имеет отношения. Вот например: http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Expression_Graph.svg...

В сишке это будет result=add(add(3,3), (t=add(2,2), add(t,t))); в принципе для этого запятую и придумали. А сейчас она не нужна, т.к. компилятор сам в курсе.

Фишка в том, что это _одно_ выражение.

То есть выбросить все языки

нет. Выбрось своё неправильное понимание понятия «состояние». Это несколько не то, что ты думаешь. Внутри одной функции _одно_ состояние. Даже выше, которая result=add(…);

Пример функции с несколькими состояниями был мною выше продемонстрирован. Но там пришлось использовать два банкомата(и связь, которая то есть, то нет), и мне бегать между ними, и (не)снимать деньги.

Еще раз повторяю, что это не имеет отношения к сабжу

ещё раз повтори, что ты не понимаешь сабжа.

Счет находится не в банкомате. Это запись в базе на компьютере

достал ты. «Компьютер» установлен в банке, в этом же банке банкомат. Второй банкомат установлен хрен знает где.

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

если связи нет, то не могут. Потому что я пойду к другому, и сниму всё оттуда же. А овердрафт по условию всего 200руб.

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

ты заблудился: всё ещё проще, и центральная находится в первом банкомате. Но первый не может дать мне всё, т.к. может я выпотрошил второй, а овердрафт всего 200р. Максимум, что он может мне дать, так это то, что у меня есть(по своим данным), минус то, что может мне дать второй, плюс овердрафт. Т.е. если у меня 100р, то оба могут дать по 150руб максимум. И по данным первого у меня после выдачи первым 150р будет на счету ≥-200 и ≤-50. Без овердрафта всё совсем просто: если у меня на счету было 1000руб, банкоматы могут дать мне по 500руб, и всё.

В чистом ФП есть state monad (с операцией присваивания — меняй свой счёт, пожалуйста).

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

Глобального состояния в хаскеле нет. Это типа баго-фича — http://www.haskell.org/haskellwiki/Top_level_mutable_state.

и состояний тоже нет.

Я говорю — ты что-то своё придумал и об это разговариваешь. Когда я говорю графы/деревья, то подразумевается что-то весьма конкретное и всем (ну почти :)) известное, но ты начинаешь скакать мыслью непонятно о чём :(

Я на первой странице называл источники.

Открываешь «The Lambda Calculus, Its Syntax and Semantics» и читаешь о чём вообще тут речь. Лямбда-термы представляются (конкретно синтаксически) деревьями, ну или натуральными числами, как хочешь, отношение редукции это бинарное отношение на этом множестве термов (деревьев, чисел), его замыкания (последовательные применения) дают тебе полные редукции, то есть вычисления в значения (если есть).

Простейшая реализация — свёртка дерева.

Потом открываешь «Abstract Computing Machines: A Lambda Calculus Perspective» — и про деревья с редексами и редукциями

The first machine that we are going to talk about is a slightly modified version of the secd machine invented by Landin in 1962 as an abstract evaluator for λ-expressions that employs an applicative order strategy.

The operating principle of this machine centers around the idea of delayed substitutions. Rather than performing β-reductions as atomic operations, the machine partitions them, as a measure to improve runtime efficiency, into two steps that are distributed over time. When encountering β-redices, it just collects mappings of bound variables to (operand) expressions in a runtime structure called the environment. All substitutions are subsequently done while traversing the body expressions only once in search of bound-variable occurrences.

и про графы с редукциями

Another concept for performing β-reductions has been proposed by Wadsworth in 1971. It avoids some of the complexity of directly operating on linear representations of expressions, as Berkling’s machine does. The idea is to represent λ-expressions as graphs, i.e., as structures whose inner (or constructor) nodes include pointers to subgraphs, and to realize β-reductions by copying, deleting and rearranging pointers. Reductions are fully effected within the graphs themselves; again there is no environment involved.

The terms graph and graph reduction refer to the fact that, beyond the tree structures generated by the (constructor) syntax of λ-expressions, we have the binding structures of abstractions represented by pointers as well, as a consequence of which we may have subgraphs referenced by several pointer occurrences and also cyclic references.

ЯННП

Говорили про состояния, ты зачем-то заговорил про их наблюдения. Ну и что значит на метауровне — на уровне описания/исполнения машины (а не того что она исполняет — не на уровне термов там, например) её состояния прекрасно видны (например, как значения runtime system объектов — их же в коде RTS можно видеть, без этого вообщем-то и никак, ты даже можешь сделать и предоставить в исходный язык stop_the_world(); show_world_state(); — даже на основном уровне всё видно).

Фишка в том, что это _одно_ выражение.

А откуда ты знаешь?

Почитай что-нибудь по теме, вот ещё — http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/, http://www.scs.stanford.edu/11au-cs240h/notes/ghc-slides.html.

Выбрось своё неправильное понимание понятия «состояние». Это несколько не то, что ты думаешь.

Где конкретно моё неправильное понимание чего вообще и что я думаю? :)

Пример функции с несколькими состояниями был мною выше продемонстрирован. Но там пришлось использовать два банкомата(и связь, которая то есть, то нет), и мне бегать между ними, и (не)снимать деньги.

См. первый абзац, хз о чём ты вообще.

Эээ… Чушь какая-то. Ты сейчас говоришь что у хэша есть глобальное состояние и не важно каким образом ты к нему пришёл, дальнейшие вычисления зависят только от этого состояния. У программы на каком-нибудь хаскеле есть глобальное состояние — граф G-машины. И в известных пределах для дальнейшего вычисления не важно как ты пришёл к такому графу.

Вот например http://chimera.labs.oreilly.com/books/1230000000929/ch02.html (:sprint и картинки — не стесняемся взять сложных ленивых структур данных, вычислений, замкнуть узлы для цикличности и т.п.), а emulek говорит «_одно_ выражение».

И вот ещё — http://thoughtpolice.github.io/vacuum/.

А в чём неполноценность?

[scheme][haskell][oop][fp] Мысли вслух — там полноценные присваивания.

Вот чистый стек (это пример из SICP):

{-# LANGUAGE GeneralizedNewtypeDeriving, NoMonomorphismRestriction #-}

import Data.Default
import Control.Monad.State
import Control.Monad.Error
import Control.Monad.Identity

type ErrorMessage = String

type Transaction balance result =
  StateT balance (ErrorT ErrorMessage Identity) result

type Final balance result = Either ErrorMessage (result, balance)

data Action amount = Withdraw amount | Deposit amount | Show

newtype Account balance = Account { _getBalance :: balance } deriving Default

action :: (Ord amount, Num amount) => Action amount -> Transaction amount amount
action (Withdraw amount) = do
  current <- get
  if current >= amount
  then do modify (flip (-) amount); get
  else throwError "Insufficient funds"
action (Deposit amount) = do modify (+amount); get
action Show = get

run :: Account balance -> Transaction balance result -> Final balance result
run account = runIdentity . runErrorT . flip runStateT (_getBalance account)

runDef :: Default balance => Transaction balance result -> Final balance result
runDef = run def

cont :: Final balance result -> Transaction balance ()
cont = either throwError (put . snd)

t1 = runDef $ do
  action $ Deposit 777
  action $ Deposit 777
  action $ Withdraw 1000
-- Right (554,554)

t2 = runDef $ do
  cont t1
  action $ Deposit 100
  action Show
-- Right (654,654)

t3 = runDef $ do
  cont t2
  action $ Withdraw 1000
-- Left "Insufficient funds"

Я говорю — ты что-то своё придумал и об это разговариваешь. Когда я говорю графы/деревья, то подразумевается что-то весьма конкретное и всем (ну почти :)) известное, но ты начинаешь скакать мыслью непонятно о чём :(

я прекрасно понимаю, про какие ты деревья. Я не понимаю, при чём тут мутабельные состояния? Или как их там ты называешь?

Говорили про состояния, ты зачем-то заговорил про их наблюдения.

я про другие состояния говорил. Весь твой обход дерева — _одно_ состояние. Как у трубы с говном. Или у дерева труб с текущим по ним говном. У такой системы всего _одно_ состояние, и время не для такой системы не имеет смысла.

Фишка в том, что это _одно_ выражение.

А откуда ты знаешь?

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

Почитай что-нибудь по теме

это другая тема.

хз о чём ты вообще.

о том, что в чистом ФП нет состояний. А в не совсем чистом хоть и есть, но они локальные для каждого контекста. А глобальных может и не быть в принципе.

Вот например http://chimera.labs.oreilly.com/books/1230000000929/ch02.html (:sprint и картинки — не стесняемся взять сложных ленивых структур данных, вычислений, замкнуть узлы для цикличности и т.п.), а emulek говорит «_одно_ выражение».

и что же вы такие умные рабочий код не пишете?

там полноценные присваивания.

counter = (=~ (+ 1)) <$> new 0

ну да. Это в C пишется ++counter

знаешь, после ЭТОГО я даже смотреть не буду на что-нибудь практически применимое. Инкремент на sed может чуть длиннее, но намного более понятный.

Я не понимаю, при чём тут мутабельные состояния?

Ты первый употребляешь слово «мутабельные» в этом треде.

Или как их там ты называешь?

Тут вроде было про переписывание термов. Ну как в хаскеле — в куче лежит структура представляющая вычисление, в т.ч. с невычисленными кусками (лень же), ты её как-то вычисляешь — память в куче мутируется (или создаётся новая), так как невычесленные куски вычисляются, уже другая структура.

о том, что в чистом ФП нет состояний

Но есть «монада состояний», отлично :)

1. Считай, что процесс (он-то хоть есть?) создания новых значений (в той же или нет памяти) из старых это переход между состояниями в процессе вычисления.

2. У соответствующей машины которая выполняет вычисления состояния есть.

А в не совсем чистом хоть и есть, но они локальные для каждого контекста

Если ты про ссылки в IO, то они не локальные (но для этого нужно рабочий код писать, чтобы разбираться :)).