LINUX.ORG.RU

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

 ,


2

3

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

Выводим фапешников на чистую воду?

anonymous ()

Что такое «вычислитель»? Какая-то деталь реализации?

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

Miguel ★★★★★ ()

Нет. Наличие состояния исполнителя ФП-программы никак не влияет на логику ФП.

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

КЭП мне тут подсказывает, что вычислитель — это машина, выполняющая текст программы.

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

Между прочим, про «логику ФП» или ее отсутствие, никто не спрашивал. Было сказано, что ФП-вычисления имеют глобальное состояние.

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

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

Во-вторых — если вычислитель имеет состояние, значит и вычисление (процесс) также имеет состояние.

anonymous ()

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

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

Оно записывается в виде t -> t' и читается «t за один шаг вычисляется в t'». Интуитивно ясно, что если в какой-то момент абстрактная машина находится в состоянии t, то она может произвести шаг вычисления и перейти в состояние t'.

Ещё см. «Abstract Computing Machines: A Lambda Calculus Perspective».

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

Вот это:

Оно записывается в виде t -> t' и читается «t за один шаг вычисляется в t'». Интуитивно ясно, что если в какой-то момент абстрактная машина находится в состоянии t, то она может произвести шаг вычисления и перейти в состояние t'.

подтверждает мое предположение о том, что ФП вычисления производятся посредством Global State Machine. ФП-вычисления имеют глобальное состояние.

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

Нужен какой-то вычислитель или абстрактная машина которая будет производить эти редукции и кодировать эти термы?

Ну а сами то как думаете?:) Вот написали Вы на бумажке 1+2=3. Соотношение эквивалентности, так сказать. Выражение 1+2 не редуцируется в 3 автоматом, определенно, тут чего-то не хватает для вычисления. И явно не «семантики». Семантика тут нужна так же как «эротика»:)

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

подтверждает мое предположение о том, что ФП вычисления производятся посредством Global State Machine. ФП-вычисления имеют глобальное состояние.

Это интуитивное пояснение. С формальной же точки зрения отношение редукции просто указывает, что термы t и t' эквивалентны. И мы даже не знаем направления редукции - может это t делается из t', а может и наоборот.

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

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

anonymous ()

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

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

Знаем мы направление, и вычислитель «знает».

А нету никакого вычислителя. Есть лишь отношение эквивалентности на множестве термов.

Это направление определено правилами.

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

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

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

Что значит «сделайте»? В том и дело что нету никакого «сделайте».

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

В том и дело что нету никакого «сделайте».

Задайте соотношение эквивалентности, такое, чтобы (5 5) редуцировать в 10, а потом обратно. И докажите, почему (5 5) а не (2 8)

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

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

говорят, у лисперов есть лисп-машины.

(если что, мопед не мой)

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

http://www.paultaylor.eu/~pt/prafm

Reduction is the sparsest binary relation which contains reduction of redexes, respects substitution and is reflexive and transitive

«производятся посредством Global State Machine» и «имеют глобальное состояние»?

Попробуй найти djvu и прочитать вот это (http://www.paultaylor.eu/~pt/prafm/html/s12.html) в нормальной вёрстке (ещё можно основные определения из второй и третьей главы «The Lambda Calculus, Its Syntax and Semantics»).

ФП-вычисления имеют глобальное состояние.

Если ты про реализацию, то конечно, например http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729 и её выполнение непосредственно рантаймом на конкретной машине.

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

Задайте соотношение эквивалентности, такое, чтобы (5 5) редуцировать в 10, а потом обратно.

Что значит «редуцировать»? Никакой редукции нету, только отношение эквивалентности. Если терм (5 5) эквивалентен терму 10 - ну так и задавай. И он сразу туда и обратно в силу симметричности.

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

подтверждает мое предположение о том, что ФП вычисления производятся посредством Global State Machine. ФП-вычисления имеют глобальное состояние.

нет. Это «состояние» как раз не глобальное, а локальное, для данного контекста. А твоё «глобальное состояние» просто не имеет смысла в другом контексте. IRL оно конечно есть, но скрыто в реализации, и к нему нет доступа. В теории его может и не быть вовсе, например два компьютера могут одновременно выполнять один и тот же код. Конечно могут быть «перекрёстные точки», но все процессы вовсе не обязаны ждать, когда в эту точку всё стянется.

Подробнее читай SICP, главу про то, как проводятся транзакции в банках. Т.е. что-бы получить твоё «глобальное состояние» нужно синхронизировать транзакции во ВСЕХ филиалах/банках, чего IRL конечно никто не делает. Конечно при этом возможен овердрафт, т.к. клиент может одновременно снять со счёта все свои деньги дважды(при этом конечно банк во первых списывает ещё больше, чем овердрафт(процент по овердрафту), ну и слишком сильный овердрафт естественно невозможен, т.к. крупные транзакции всё равно синхронизируются, т.е. для клиента проходят «долго». Т.е. это фактически легальный способ навязать клиенту ВНЕЗАПНЫЙ кредит). При этом «глобального состояния» тут нет в принципе, две транзакции проходят вместе, и обладают своим контекстом каждое. Транзакции даже не знают друг про друга.

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

Если ты про реализацию

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

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

avtoritetniy-expert ()

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

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

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

необратимость обязана быть только при повышении энтропии, а это вообще говоря не обязательно. Инкремент/декремент ты можешь гонять туда-сюда сколько угодно и как угодно.

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

Задайте соотношение эквивалентности, такое, чтобы (5 5) редуцировать в 10, а потом обратно. И докажите, почему (5 5) а не (2 8)

потому что у нас нет чиске 2 и 8. Есть только 5+5 и 10. Потому из 10 ты сможешь сделать только 5+5. А вот если ты определишь 2 и 8, то получишь увеличение энтропии при прямой индукции размером в 1 бит. И обратная редукция станет невозможной. Потерянный безвозвратно бит невозможно найти.

emulek ()

Как ты вообще функционируешь с таким поносом в голове вместо мозга?!?

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

даже лень тебе что-то объяснять

А ты бы и не смог, видно же по батхерту. Да ты и не понял ничего из того, что написано, и не смог бы.

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

ы написал полный бред. Подумай, почему так, и напиши что-то разумное.

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

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

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

По-сабжу. Данный взгляд на вычисления, внезапно, почти соответствует общепринятому в CS. Особенно, в контексте параллелизма.

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

Я тебе про свертку говорил, ты читай внимательней. Сверни и разверни. А то что у тебя там нет ничего, ни редукций ни вычислений, ни х-я, это ты не мне обьясняй. L-calculus - это пока что calculus.

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

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

запись 1+2=3 не имеет смысла даже с вычислителем. Это просто тривиальная константа true. Тут нет не только состояний, но вообще ничего нет.

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

то просто тривиальная константа true.

Во-первых, само выражение вычисляется 1+2 --> 3. Во-вторых, выражение 1+2=3 ---> true тоже вычисляется, будь она хоть константой хоть жопой. В третих, ты них*я не понел, что хотели этим донести.

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

Сдайся сам на Пряжку! Срочно. А то ведь так и будешь истерить, на тему, почему irl ты дворник. А не великий разработчик :)

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

симметричности

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

Т.е. редукции — (5 + 5) ->R 10, (2 + 8) ->R 10 что значит (5 + 5, 10) \in R \sub T^2, (2 + 8, 10) \in R \sub T^2. Порождённые эквивалентности — (5 + 5) ~R 10 ~R (2 + 8) (10 ->R 10, рефлексивность).

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

Там автор говорил только об эквивалентности.

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

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

Ну и чо? Каждый из них имеет свое глобальное состояние при вычислении? Чему это противоречит? Зачем это здесь?

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

Я смотрю, ты вообще попутал глобальное состояние с разделяемыми ресурсами. Такая каша, просто п*ц.

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

В третих, ты них*я не понел, что хотели этим донести.

ну дык поясни. На нормальном примере, а не на этом говне.

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

Сдайся сам на Пряжку! Срочно. А то ведь так и будешь истерить, на тему, почему irl ты дворник.

кто здесь истерит кроме тебя?

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

Да и ты недалеко ушел. Само-собой, если речь о вычислениях, предполагается что есть вычислитель. Все о чем ты говоришь, это лишь набор правил для абстрактного вычислителя, не более.

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

Каждый из них имеет свое глобальное состояние при вычислении? Чему это противоречит?

ты идиот? Задумайся о выделенном. IRL есть Over9000 вычислителей, и у каждого _своё_ состояние. Ага, «глобальное».

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

Я смотрю, ты вообще попутал глобальное состояние с разделяемыми ресурсами. Такая каша, просто п*ц.

у тебя проблема с восприятием текста. Учись читать, если у тебя слова в кашу сливаются. Или глаза лечи, я не твой доктор. Желаю, что глаза, ибо олигофрения неизлечима.

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

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

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

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

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