LINUX.ORG.RU

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

 ,


2

3

А правильно ли я понимаю, что под «отсутствием состояния» в ФП понимается только отсутствие состояния переменных. У самого вычислителя, есть глобальное состояние, он в каждый момент времени находится в состоянии одной из редукций выражения, подобно тому, как машина Тьюринга в каждый момент вычисления «обозревает» строго определенную ячейку, на которой находится головка? Из этого следует, что ФП вычислитель относится к классу «Global State Machine» и у него, разумеется, ЕСТЬ глобальное состояние?

Ответ на: комментарий от emulek

Это в C пишется ++counter

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

quasimoto ★★★★
()
Ответ на: комментарий от avtoritetniy-expert

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

А я не понимаю, о каком «вычислителе» ты говоришь.

Miguel ★★★★★
()
Ответ на: комментарий от avtoritetniy-expert

шаг редукции, который ты не можешь не сделать, чтобы получилось

То есть, ты таки про детали реализации говоришь.

Процесс редукций — не единственная и не самая простая семантика лямбда-исчисления.

Miguel ★★★★★
()
Ответ на: комментарий от quasimoto

Отношение редукций (substitution + reflexive + transitive) не симметрично, оно порождает отношение эквивалентности (reflexive + transitive + symmetric) как x ~R y <=> exists z. x ->R z & y ->R z.

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

anonymous
()
Ответ на: комментарий от quasimoto

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

а откуда у меня ссылка http://www.haskell.org/haskellwiki/Top_level_mutable_state ?

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

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

Но есть «монада состояний»

именно. Ты считаешь, что вычисление f(7)+f(7) происходит в два состояния:

1. вычисляется f(7)→t

2. вычисляется t+t.

А на самом деле это только видимость состояний, если ты получаешь не все биты сразу, а по одному, то ты можешь начать сложения не после f(7), а после получения первого бита. Т.е. всё будет сделано в один единственный этап, за время выполнения одной операции. В сишке тут необходимо 3 «такта», т.к. каждый оператор должен дождаться полного завершения предыдущих, и исполнения всех побочных эффектов.

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

что-бы «считать» нужно ВРЕМЯ, т.е. ДО и ПОСЛЕ. А его в ФП тупо НЕТ. Переходы между «состояниями» есть, но мы не знаем, КОГДА закончилось состояние1 И началось состояние2. Дело в том, что такого момента вполне себе может НЕ БЫТЬ, т.к. состояние2 может начать ДО начала состояния1, т.о. два «состояния» будут ОДНОВРЕМЕННО существовать. Т.о. будет момент, когда общее состояние НЕ ИМЕЕТ СМЫСЛА.

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

ну и что? Вот смотри: Мы вычисляем x*y+z. Даже если мы считаем на i8080, этот i8080 может НАЧАТЬ выполнять сложение ДО завершения умножения. Мало того, для длинных чисел он так и делал (тупо потому, что не нужно тратить драгоценное место для всего произведения). Посему, хотя у i8080 состояния конечно есть, и он безусловно императивный, состояниЯ при вычислении x*y+z отсутствуют. Они существуют только в твоём воображении, а i8080 выполняет две операции ОДНОВРЕМЕННО, т.к. память драгоценная, и её надо экономить. Т.ч. получив первый байт x*y i8080 его складывает с первым(мл) байтом z, а потом это место использует для второго байта произведения. Т.о. произведение занимает в памяти всего 9 бит(+1 бит на CF).

Т.о. ты не можешь выделить «состояние умножения» и «состояние сложения» даже на i8080.

Хотя можешь фантазировать, что в x*y+z есть две отдельные операции, которые выполняются по очереди. Я понимаю, это проще.

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

не тупи. Чёрного не бывает. И белого не бывает. Есть только светло-серый, и тёмно-серый. Монада IO это и есть «капля чёрной краски в банке с белой», а разделить эти краски ты можешь только в фантазиях.

На самом деле, «чистого императивного» не существует даже в коде для i8080, см. выше. И как только в iPentium появился второй вычислитель, он сразу стал «немножко функциональным», т.к. многие команды выполнял одновременно, каждую в своём контексте, две штуки за 1 такт.

emulek
()
Ответ на: комментарий от quasimoto

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

я хочу, что-бы существовал единственный и однозначный момент перехода 0→1. Вот тогда ВСЮ программу можно разделить на два этапа(состояния)

state1. counter=0

state2. counter=1

причём ЛЮБОЙ процесс должен иметь возможность всегда читать counter, а то ты ведь обманешь, сказав что state2, а на самом деле сейчас state1.

emulek
()
Ответ на: комментарий от quasimoto

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

Дал только ссылку в которой есть код counter = (=~ (+ 1)) <$> new 0, в котором ЯННП, и ты тоже.

emulek
()
Ответ на: комментарий от emulek

а откуда у меня ссылка

Из моего вопроса к ТС про то чем у него являются ФП и состояния — я сказал что вот таких глобальных переменных нет.

Просто выражение f(7)+f(7) вычисляется с однократным выполнением f(7), а не с двухкратным.

GHC с -O0 дважды вычисляет, оставаясь ленивым при этом.

если ты получаешь не все биты сразу, а по одному, то ты можешь начать сложения не после f(7), а после получения первого бита. Т.е. всё будет сделано в один единственный этап, за время выполнения одной операции.

f False + f False — лучше начать с Bool (0, 1) для самых маленьких тогда, чтобы биты не размазывать.

но мы не знаем, КОГДА закончилось состояние1 И началось состояние2

Стратегия вычислений вполне определяет когда что происходит.

а i8080 выполняет две операции ОДНОВРЕМЕННО

Ну и редукция графов бывает параллельной, только к чему это тут?

quasimoto ★★★★
()
Ответ на: комментарий от emulek

в котором ЯННП

Ну да, ты ссылаешься на код который использует IORef (то есть настоящие такие куски памяти, у них виртуальный/физический адрес есть), что ты хочешь сделать (можешь на си написать) и что непонятно?

А в чистом варианте есть state monad — тоже, что нужно и что не получается?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

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

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

О чём я и говорю второй день: NoWay.

GHC с -O0 дважды вычисляет, оставаясь ленивым при этом.

что дальше? Он может и трижды вычислять, для гарантии.

f False + f False — лучше начать с Bool (0, 1) для самых маленьких тогда, чтобы биты не размазывать.

не важно, с чего ты начнёшь. Важно — КОГДА.

Стратегия вычислений вполне определяет когда что происходит.

нет. Она определяет только когда НЕ происходит. Т.е. ты не можешь НАЧАТЬ вторую операцию перед первой, если вторая зависит от первой. Но вот если ты начал первую, то стратегия вычислений НЕ определяет момент начала второй. Любой момент подойдёт.

Ну и редукция графов бывает параллельной, только к чему это тут?

к тому, что в терминах «умножение» и «сложение» есть только ОДНО состояние. Несколько состояний есть только в терминах «ассемблерная инструкция». А в терминах «сложение» и «умножения» нет, т.к. их ассемблерные инструкции могут быть перепутаны, а значит не существует состояния «умножение» и второго состояния «сложение». Есть только ОДНО состояние «сложение-умножение». А твоё дерево — просто модель реального мира. Некий абстрактный идеальный случай.

emulek
()
Ответ на: комментарий от Miguel

А я не понимаю, о каком «вычислителе» ты говоришь.

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

То есть, ты таки про детали реализации говоришь.

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

avtoritetniy-expert
() автор топика
Ответ на: комментарий от emulek

не будет и глобальных состояний.

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

avtoritetniy-expert
() автор топика
Ответ на: комментарий от emulek

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

Ну на самом деле ты можешь делать

count :: IORef Int
count = unsafePerformIO $ newIORef 0
{-# NOINLINE count #-}

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

struct State {
    ...
};

void f(State &state, ...) {
    modify state...
}

int main() {
    State state = initial state...
    f(state, ...);
}

Или неявное такого:

void f(...) {
    modify shared state
}

int main() {
    initialize shared state
    f(...);
}

что дальше?

Ты что-то про суть ленивых вычислений сказать хотел (но получилось про мемоизацию).

f False + f False

То есть

     @
    / \
   /   \
  @     @
 / \   / \
+   @ f   0
   / \    
  f   0

внешний редекс это применение применения (+), его начинаем редуцировать первым, потом он вызывет редукцию левого (например) применения f

     @
    / \
   /   \
  @     @
 / \   / \
+   r f   0

потом правого

     @
    / \
   /   \
  @     r
 / \
+   r

после чего завершается редукция (+).

Или с разделением:

     @
    / \
   /   \
  @-----@
 /     / \
+     f   0

     @
    / \
   /   \
  @-----r
 /
+
quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

что ты хочешь сделать

я хочу тебе и ТСу объяснить, что делить на ноль нельзя. И что сабж в ФП невозможен в принципе. А если возможен, то значит это уже НЕ ФП.

А в ИП невозможно выполнение функций в изолированных своих контекстах. Как следствие, невозможны ленивые вычисления как в твоём хаскеле. Точнее возможны, но в буквальном смысле «на честном слове», если ты поклялся не давать функциям указатели(которые в C/C++ всегда глобальны) и клянёшься не использовать статические переменные, или будешь их юзать, но делать вид, что их можно использовать только внутри той функции, в которой они объявлены. А передать наружу религия не позволяет и Святая Клятва. Ну и да, ещё ты Свято Веруешь, что стек в сишечке бесконечный и ничем неограниченный. Вот для адептов такой Веры можно и в сишке сделать ленивые вычисления, как в хаскеле. И они будут ничуть не хуже. И всё остальное тоже можно сделать. Как и из хаскеля можно сделать убогое подобие сишки, только Канон нужен. Ну и Поститься, Молиться, и слушать радио Радонеж.

Вот только я ещё не настолько убог для того и другого. А вот ты с ТСом уже на Пути к Просвятлению.

Удачи, братья.

emulek
()
Ответ на: комментарий от avtoritetniy-expert

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

никакого «состояния вычислений» IRL не существует. Это ты просто нафантазировал, что в выражении x*y+z «сначала» умножается, а «потом» складывается. Для самих вычислений нет никаких «сначала» и «потом». Выражение одно, и «состояние» у него ОДНО. А то, что у тебя в AST узел * на другом уровне, нежели +, то это просто условность, не более того. И то, что ты не разумеешь дерево целиком, а только по частям — следствие твоего скудоумия. А то, что CPU тоже по AST ползает — следствие его несовершенства.

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

Нет в ФП переменных с состоянием, с этим никто не спорит.

ну ладно...

emulek
()
Ответ на: комментарий от avtoritetniy-expert

Мы просто говорим, что есть некая машина, которая транслирует текст, написвнный на ЯП.

Ну, ради бога, говори, но сам ЯП тут тебе не виноват.

Если процесс вычислений для тебя — детали реализации

Понятие «процесс вычислений» - тоже внешнее по отношению в ФП.

Miguel ★★★★★
()
Ответ на: комментарий от emulek

Но в итоге у тебя получается какая-то фигня %)

ФП и ИП какие-то.

В С или C++ санк чтоли не сделать? Или о чём ты — на хаскеле я тоже могу пойти сделать себе сегфолт (ах да, и лимит на стек, кучу поставить :)).

И что сабж в ФП невозможен в принципе. А если возможен, то значит это уже НЕ ФП.

Ну так рассказывай, что за «ФП», почему хаскель не «ФП», где нарушаются его принципы, чего не хватает — 1) unsafePerformIO на ссылки под IO, 2) просто ссылки в IO, 3) ST, 4) State monad.

ТСу

Он про возможность выбора абстрактной машины для языка.

quasimoto ★★★★
()
Последнее исправление: quasimoto (всего исправлений: 2)
Ответ на: комментарий от quasimoto

Ну на самом деле ты можешь делать

Я: делить на ноль нельзя!
Ты: можно!
Я: ну подели…
Ты: вот смотри, я беру калькулятор, набираю 1/0, получаю результат "devision by zero". Значит можно!
Я: это не результат. И ты его не получил.
Ты: вод код, который написал результат, вот сам результат!
Я: ты написал какую-то хрень нелепую своему калькулятору, и он тебе выдал в ответ тоже самое. Ты ничего не доказал.
Ты: Я всё тебе доказал, вот вход, вот выход, вот код который вычисляет.
Я: ладно. Тебе — можно.

внешний редекс это применение применения (+), его начинаем редуцировать первым, потом он вызывет редукцию левого (например) применения f

«первым», «потом», «вызывает» — это всё условности, для выражения своих мыслей. Не более того.

На самом деле, ленивость вычислений очевидна любому ещё здесь:

     @
    / \
   /   \
  @     @
 / \   / \
+   @ f   0
   / \    
  f   0

А твоё описание — просто твоя фантазия о том, как работает твой воображаемый вычислитель. Что он делает сначала, а что — потом. Но даже твой мозг работает иначе, и ты сразу видишь, что в данном случае одного обхода

 \
  @
 / \
f   0
достаточно. А все твои объяснения — наивная попытка реализации.

Или с разделением:

просто картинка другая. Всё тоже самое.

А суть в том, что ДОСТАТОЧНО этой картинки. Все твои редукции и обходы — перевод данного (картинкой) алгоритма в ЯП твоего любимого воображаемого вычислителя.

emulek
()
Ответ на: комментарий от quasimoto

А у Barendregt и всех остальных тогда что?

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

anonymous
()
Ответ на: комментарий от quasimoto

Ну на самом деле ты можешь делать

в своей любимой сишечке я могу больше. Т.ч. ты своим ударом апстену головой меня не удивил.

emulek
()
Ответ на: комментарий от Miguel

Понятие «процесс вычислений» - тоже внешнее по отношению в ФП.

+1

emulek
()
Ответ на: комментарий от emulek

делить на ноль нельзя!

Объясняй почему это деление на ноль.

это всё условности, для выражения своих мыслей

Это _конкретно_ выбранная стратегия редукций.

На самом деле, ленивость вычислений очевидна любому ещё здесь:

Нет, http://en.wikipedia.org/wiki/Lambda_calculus#Reduction_strategies — на этом дереве ты можешь начать делать энергичное вычисление от innermost redex.

А твоё описание — просто твоя фантазия о том, как работает твой воображаемый вычислитель.

Объясняй почему это фантазия, то есть показывай, что «The Implementation of Functional Programming Languages» описывает что-то иное и что GHC работает иначе — там-то можно взять и проверить, никаких фантазий и наивных попыток — trace начинается снаружи и идёт внутрь как я описал (-O0 / -01 с разделением).

Всё тоже самое.

Ну нет — два раза вычислять или один.

в своей любимой сишечке я могу больше

Ну ты говорил что вообще НЕТ чего-то.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

В С или C++ санк чтоли не сделать? Или о чём ты — на хаскеле я тоже могу пойти сделать себе сегфолт (ах да, и лимит на стек, кучу поставить :)).

ох... Да какая разница, что ты _можешь_? Я не говорю «не можешь», я говорю «не нужно». А сделать ты можешь, да.

Ну так рассказывай, что за «ФП», почему хаскель не «ФП», где нарушаются его принципы, чего не хватает — 1) unsafePerformIO на ссылки под IO, 2) просто ссылки в IO, 3) ST, 4) State monad.

1. нарушает ФП

4. Как я понял, не нарушает ФП, но выглядит так, как будто это не ФП, а обычное императивное программирование(ИП).

про 2,3 не знаю.

Что до ТСа, то он, судя по этому:

У самого вычислителя, есть глобальное состояние, он в каждый момент времени находится в состоянии одной из редукций выражения, подобно тому, как машина Тьюринга в каждый момент вычисления «обозревает» строго определенную ячейку, на которой находится головка? Из этого следует, что ФП вычислитель относится к классу «Global State Machine» и у него, разумеется, ЕСТЬ глобальное состояние?

Просто не понимает того простого факта, что хотя каждое действие входного ЯП транслируется в набор действий выходного (у него МТ), это вообще не говорит о том, что трансляция непрерывная и однозначная. И что в любой момент состояние МТ может быть интерпретировано в «состояние» ФП-ЯП. Это не так. Простейший пример я привёл на примере вычисления x*y+z старинным процессором. Состояние процессора есть и однозначно, но оно указывает СРАЗУ НА ДВА оператора входного ЯП.

emulek
()
Ответ на: комментарий от emulek

1. нарушает ФП

Не нарушает.

4. Как я понял, не нарушает ФП, но выглядит так, как будто это не ФП, а обычное императивное программирование(ИП).

С протаскиванием значений которые выглядят как состояния, то есть ты формулируешь вычисление в терминах чистых функций (State -> Result, NewState) они композиционно составляются, во всём стеке всегда можно читать этот общий для него State, потом весь стек запускается с начальным состоянием и выполняется (до конечного). 3 оптимизирует это прибивая «якобы» состояния к настоящим — конкретной памяти, оставляя возможность явно их вытаскивать сохраняя ссылочную прозрачность, 2 добавляет эффектов (вытаскивать или нет и будет это что-то ломать — на усмотрение, в 1 не ломает).

quasimoto ★★★★
()
Последнее исправление: quasimoto (всего исправлений: 2)
Ответ на: комментарий от quasimoto

делить на ноль нельзя!

Объясняй почему это деление на ноль.

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

В случае ТСа, из того факта, что в МТ есть однозначные состояния, вовсе НЕ следует, что эти состояния есть в исходнике. В частности в ФП никаких состояний нет. Точно также, как нет решений уравнения x*0=1. Но реальность жестока: мы можем сказать, что 0 это не 0, а что-то малое. Ну так и с твоим хаскелем — это почти идеальная модель ФП.

это всё условности, для выражения своих мыслей

Это _конкретно_ выбранная стратегия редукций.

согласен, конкретная. Но всё равно она условна и не единственна.

На самом деле, ленивость вычислений очевидна любому ещё здесь:

Нет, http://en.wikipedia.org/wiki/Lambda_calculus#Reduction_strategies — на этом дереве ты можешь начать делать энергичное вычисление от innermost redex.

Ну я о том и говорю: могу, причём очевидно, разными стратегиями. Вот только там они у тебя все всё равно завязаны на разное воображаемое ВРЕМЯ.

Однако в изначальном дереве времени нет.

Объясняй почему это фантазия, то есть показывай, что «The Implementation of Functional Programming Languages» описывает что-то иное и что GHC работает иначе — там-то можно взять и проверить, никаких фантазий и наивных попыток — trace начинается снаружи и идёт внутрь как я описал (-O0 / -01 с разделением).

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

Ну нет — два раза вычислять или один.

а... Ты забыл примечание: «на первом AST нужно вон ту хрен считать ровно два раза, и пофиг на то, что дебилу ясно, что это одно и тоже».

Ну ты говорил что вообще НЕТ чего-то.

Это не баг, а фича. Например напиши на своём говнохаскеле вот это: x-- - --x. Это говно эквивалентно сразу трём различным AST, и ещё одной хрени, которая AST не является, и которая никак не называется(что не помешало gcc скомпилировать из этого говна именно то говно).

А НЕТ тут только одного: смысла ☺

emulek
()
Ответ на: комментарий от quasimoto

1. нарушает ФП

Не нарушает.

как учит нас SICP, в ФП есть только одна сущность: функция, которая принимает аргументы, и возвращает результат. Причём результат детерминирован, если сегодня аргумент 17, а результат 42, то так будет всегда.

Согласен?

А что будет, если результат зависит от глобальной переменной, которая равна 0, а я её инкрементирую?

С протаскиванием значений которые выглядят как состояния, то есть ты формулируешь вычисление в терминах чистых функций (State -> Result, NewState) они композиционно составляются, во всём стеке всегда можно читать этот общий для него State, потом весь стек запускается с начальным состоянием и выполняется (до конечного). 3 оптимизирует это прибивая «якобы» состояния к настоящим — конкретной памяти, оставляя возможность явно их вытаскивать сохраняя ссылочную прозрачность, 2 добавляет эффектов (вытаскивать или нет и будет это что-то ломать — на усмотрение, в 1 не ломает).

если честно — я не знаю.

emulek
()
Ответ на: комментарий от emulek

Объясняй почему это деление на ноль.

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

Но всё равно она условна и не единственна.

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

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

int sum(int x, int y) {
    puts("sum");
    return x + y;
}

int i = 0;

int f(int x) {
    printf("f [%d]\n", ++i);
    return x * x;
}

template <typename R>
using Thunk = std::function<R()>;

#define MkThunk(EXPR) [=](){ return EXPR; }

Thunk<int> lazy_sum(Thunk<int> x, Thunk<int> y) {
    puts("lazy_sum");
    return MkThunk(x() + y());
}

Thunk<int> lazy_sum_share(Thunk<int> x) {
    puts("lazy_sum_share");
    int z = x();
    return MkThunk(z + z);
}

int main() {
    printf("result = %d\n\n", sum(f(7), f(7)));
    i = 0;
    printf("result = %d\n\n", lazy_sum(MkThunk(f(7)), MkThunk(f(7)))());
    i = 0;
    printf("result = %d\n\n", lazy_sum_share(MkThunk(f(7)))());
}
/*
f [1]
f [2]
sum
result = 98

lazy_sum
f [1]
f [2]
result = 98

lazy_sum_share
f [1]
result = 98

*/

http://www.cplusplus.com/reference/future/ тоже в тему.

Однако в изначальном дереве времени нет.

Да ради бога, нет — сделаем :)

Согласен?

Да.

А что будет, если результат зависит от глобальной переменной, которая равна 0, а я её инкрементирую?

count = unsafePerformIO $ newIORef 0 возвращает ссылку (переменную, адрес — оно одно и то же, меняются значения по нему), она глобальна и мутабельна (то есть значения по ней, а не сам адрес ссылки), только больше unsafePerformIO использовать не надо (можно TH обвёртку defineGlobalVar вообще сделать), тогда изменяющие значение переменной операции будут всё равно в IO — глобальная переменная есть (один и тот же адрес который мы вытащили из IO, изменяемые данные по нему всё ещё инкапсулированы в слое IO), нарушений ссылочной прозрачности и ФП нет.

quasimoto ★★★★
()
Последнее исправление: quasimoto (всего исправлений: 1)
Ответ на: комментарий от quasimoto

мне не очень интересно обсуждать какие-то там состояния без контекста

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

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

ну вот а ТС обобщает свойство реализации низкого уровня на реализацию высокого.

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

ты тут совсем не тем занимаешься. Костыль std::function<> это совсем другое. Тут тебе надо полноценный разбор AST делать, с нуля.

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

http://www.cplusplus.com/reference/future/ тоже в тему.

давай ты сначала свой аналог с нуля напишешь? Просто что-бы понять, на кой ляд нужно то, на что ты ссылаешься.

Однако в изначальном дереве времени нет.

Да ради бога, нет — сделаем :)

вот ты и делаешь время, делая реализацию.

А что будет, если результат зависит от глобальной переменной, которая равна 0, а я её инкрементирую?

count = unsafePerformIO $ newIORef 0 возвращает ссылку (переменную, адрес — оно одно и то же, меняются значения по нему), она глобальна<...> изменяемые данные по нему всё ещё инкапсулированы в слое IO), нарушений ссылочной прозрачности и ФП нет.

ты так и не ответил на вопрос.

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

emulek
()
Ответ на: комментарий от emulek

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

GHC-то?

Костыль std::function<> это совсем другое.

Лямбда это простейший способ сделать thunk, так что именно то. А std::async умеет в deferred (возвращает future, вместе с promise).

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

Я написал типичные отложенные вычисления в строгом языке.

http://www.schemers.org/Documents/Standards/R5RS/r5rs.pdf

(define-syntax delay
  (syntax-rules ()
    ((delay expression)
    (make-promise (lambda () expression)))))

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

ты так и не ответил на вопрос.

Я ответил. Глобальные переменные есть, ФП не ломают. counter :: Ref Int, inc :: Ref Int -> IO (), inc counter :: IO (), если так будет понятнее.

quasimoto ★★★★
()
Ответ на: комментарий от emulek

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

Ну ещё бы! Ведь ни один из разрабов GHC ещё не набил себе на лбу тату - Это же я, тот самый долбоёб дермишко!

anonymous
()
Ответ на: комментарий от emulek

в общем случае в ФП каждая функция выполняется в своём контексте, и имеет своё состояние

что значит имеет свое состояние? Функции с состоянием — это не ФП. С точки зрения семантики функция не имеет состояния.

anonymous
()
Ответ на: комментарий от anonymous

что значит имеет свое состояние? Функции с состоянием — это не ФП. С точки зрения семантики функция не имеет состояния.

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

Например:

 (defun factorial (n)
   (if (= n 0)
       1
       (* (factorial (- n 1)) n)))
тут можно выделить состояния проверки if, состояние возврата 1, состояние умножения, состояние вычисления факториала (это уже другой контекст, другие состояния, другие переменные, другие значения), состояние декремента, и состояние возврата результата умножения.

Но это всё только внутри. Снаружи есть ОДНО состояние.

emulek
()
Ответ на: комментарий от quasimoto

Я ответил. Глобальные переменные есть, ФП не ломают. counter :: Ref Int, inc :: Ref Int -> IO (), inc counter :: IO (), если так будет понятнее.

так вообще непонятно. Можно пример, как глобальные переменные НЕ ломают ФП? Не на хаскеле.

emulek
()
Ответ на: комментарий от emulek

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

phill
()
Ответ на: комментарий от phill

Это у тебя свои личные определения.

может и так. Я SICP читал, может ступил/недопонял.

Принято считать, что функция имеет состояние, когда она при разных вызовах (из разных мест кода), с одинаковыми аргументами, возвращает разные значения.

а вот это уже интереснее. Пример можно?

И ссылку на твоё «принято считать». Кем принято? Когда принято?

А то что ты описал — это состояния вычисления, а не функции.

полистай, там выше уже были «состояния вычисления», но совсем другие (не я их вводил).

emulek
()
Ответ на: комментарий от emulek

Глобальные переменные не отменяют ссылочной прозрачности (то, что ты называешь «ФП») в любом языке, где есть аналог хаскельного IO, например, в Идрисе или Скале (scalaz)

anonymous
()
Ответ на: комментарий от emulek

а вот это уже интереснее. Пример можно?

банальный пример


(define counter (let ((start 1)) (lambda() (set! start (+ start 1)))))

(write (counter))
(write (counter))
(write (counter))
(write (counter))
;2345
Вообще, любая функция, использующая глобальные переменные в языке с присваиваниями имеет состояние по определению.

phill
()
Ответ на: комментарий от anonymous

Это функция в смысле — подпрограмма.

Вопрос терминологии. Такие функции называют функциями с состояниями, и, разумеется, это не ФП-функция.

phill
()
Ответ на: комментарий от phill

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

anonymous
()
Ответ на: комментарий от anonymous

Он говорит о состоянии. С точки зрения ФП нет вообще никакого состояния.

phill
()
Ответ на: комментарий от anonymous

Принято считать, что функция имеет состояние, когда она при разных вызовах (из разных мест кода), с одинаковыми аргументами, возвращает разные значения.

Вот это он пытался опровергать, точней, попросил пример функции с состоянием. Что не так?

phill
()
Ответ на: комментарий от anonymous

в общем случае в ФП каждая функция выполняется в своём контексте, и имеет своё состояние

Вот на это его утверждение было возражение анона.

phill
()
Ответ на: комментарий от emulek

может и так. Я SICP читал, может ступил/недопонял.

Да, ты ступил/недопонял, а точней, ты вообще ННП. В SICP ФП рассматривается только как подстановочная модель вычислений. Это не имеет никакого отношения к этому вашему новомодному дрочеву под компилятор, в виде хашкела.

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

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.