LINUX.ORG.RU

Порядок вычислений в ФП

 


0

2

Допустим, у нас есть объект(актор), который отвечает на 2 сообщения — foo и bar, возвращая, соответственно, 1 и 2. Далее, мы пишем функцию, которая асинхронно отсылает оба сообщения объекту, и возвращает фьючер, который связывается с переменной. Пусть будет такой псевдокод:

test = function(){returnFirstReceivedFutureOf(object.asyncSend(foo), object.asyncSend(bar))}
aFuture1 = test()
aFuture2 = test()
aFuture3 = test()
Каковы будут значения aFuture1, aFuture2, aFuture3? Любые, в диапазоне 111-222. Мы сколько угодно можем вызывать test, и всегда будем непредсказуемый результат, возможно всегда один и тот же, возможно, всегда разный.

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

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

BY CONTRAST

В функциональном программировании, функция всегда возвращает одно и то же. Значит, такая программа, как написана выше, там невозможна. Тогда о каком отсутствии порядка вычислений может идти речь? Ведь многие утверждают, что в ФП он отсутствует. Если порядок вычислений отсутствует, то почему же возвращается всегда одно и то же?



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

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

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

В случае же нормального порядка - мы знаем, что у терма есть нормальная форма (если есть), знаем, какая она (без всяких редукций, просто нормализованный терм из данного класса эквивалентности) - этого нам достаточно, чтобы делать выводы об этой программе. А какими именно редукциями терм будет приведен к этой нормальной форме (каков актуальный порядок редукций) нам неизвестно, это выбор компилятора. Мы только знаем, что _как-то_ он приведет. Гарантированно. К тому что надо.

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

Это да (если все функции чистые), но опять же, далеко не все ФП-языки исповедуют нормальный порядок редукций.

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

нам неизвестно, это выбор компилятора

Финты компилятора никакого отношения к семантике не имеют.

javaQest
() автор топика

Обратите внимание, тут нет никаких сайд-эффектов.

Ну ни**я себе. Ты сам свой код читал? Или он из тебя после обеда выходит и прям в ЛОР отправляется?

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

Финты компилятора никакого отношения к семантике не имеют.

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

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

Порядок обработки сообщений зависит от внешнего по отношению к самой ф-и воздействия. Это и есть определение сайд-эффекта.

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

function(){returnFirstReceivedFutureOf(object.asyncSend(foo), object.asyncSend(bar))}

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

Aswed ★★★★★
()

Обратите внимание, тут нет никаких сайд-эффектов
сообщений придет
никаких сайд-эффектов
придет

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

Очевидно, что он серьезно болен^W^Wобычная вниманиешлюшка, и его мотивация для обывателя может некоторое время оставаться загадкой.

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

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

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

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

Твой код явно меняет состояние эвентлупа или чего там. Это — глобальное состояние и ты смеешь заявлять, что он без сайд-эффектов.

Вызов чистой функции — не сайд-эффект. Но во многих языках нет чёткого разделения на чистые и грязные функции и все функции считаются грязными.

В чистых функциях никаких asyncSend быть не может, поскольку это — мутация очереди async-сообщений.

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

И да, если бы ты написал то же самое на том же JS вместо изобретения псевдокодов — ты бы гораздо чётче увидел, где именно у тебя сайд-эффект.

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

Это — глобальное состояние

Данный код реализует семантику акторов. Модель Акторов — это модель без глобального сотояния (вычислений).

мутация очереди async-сообщений.

В нашей модели нет никакой очереди.

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

Модель Акторов — это модель без глобального сотояния (вычислений).

В смысле «явного глобального состояния, к которому можно лезть грязными лапами». А неявного — хоть попой ешь.

И ты его меняешь.

В нашей модели нет никакой очереди.

А запускается она на квантовом компьютере?

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

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

javaQest
() автор топика
Ответ на: комментарий от x3al

Конечно, не значит.

не совсем понятно. Если в нашей семантике отсутствует асинхронность, то как возможна конкурентность?

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

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

О теоретической, не говоря о практической, полезности такой модели нужно говорить?

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

В смысле «явного глобального состояния, к которому можно лезть грязными лапами». А неявного — хоть попой ешь.

Мы все еще о семантике? Я поясню. В глобал-стейт-машинз есть четкое понятие шага. В МТ — есть четкое состояние перехода, в один момент времени машина обозревает одну ячейку. В LC — один шаг — одна редукция. В модели акторов этого ограничения нет. Нет понятия шага.

javaQest
() автор топика
Ответ на: комментарий от x3al

Асинхронность никак не связана с конкуррентностью.

Связана. Без асинхронности конкуретность невозможна.

javaQest
() автор топика
Ответ на: комментарий от x3al

И у тебя серьёзные проблемы с синхронизацией

С синхронизацией проблем нет, так как никто не запрещает ее реализацию поверх.

О теоретической, не говоря о практической, полезности такой модели нужно говорить?

Думаю не стоит, так как это единственная модель, которая реализует конкурентность, как в теории, так и на практике.

javaQest
() автор топика
Ответ на: комментарий от x3al

В таком случае твоё состояние == состоянию твоих сообщений

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

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

Связана. Без асинхронности конкуретность невозможна.

http://rosettacode.org/wiki/Synchronous_Concurrency

Мы все еще о семантике? Я поясню. В глобал-стейт-машинз есть четкое понятие шага. В МТ — есть четкое состояние перехода, в один момент времени машина обозревает одну ячейку. В LC — один шаг — одна редукция. В модели акторов этого ограничения нет. Нет понятия шага.

И? Из этого ничерта не следует.

Ты в ОП-посте утвеждаешь, что сайд-эффектов нет. Их нет в модели акторов, но они есть снаружи неё. Дошло?

Думаю не стоит, так как это единственная модель, которая реализует конкурентность, как в теории, так и на практике.

Офигенно смелое утверждение.

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

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

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

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

Офигенно смелое утверждение.

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

Помимо Actor Model, конкурентность реализуется в семантике CSP и PI-calculus, но обе модели испытали влияние Actors, и были переработаны, в свое время.

javaQest
() автор топика
Ответ на: комментарий от x3al

Synchronous_Concurrency

точней говоря, возможна, но это будет кривая и ограниченная реализация. В частности:

The subsections above have articulated the following three issues concerned with the use of synchronous channels for process calculi:

Starvation. The use of sychronous channels can cause starvation when a process attempts to get messages from multiple channels in a guarded choice command. Livelock. The use of synchronous channels can cause a process to be caught in livelock when it attempts to get messages from multiple channels in a guarded choice command. Efficiency. The use of synchronous channels can require a large number of communications in order to get messages from multiple channels in a guarded choice command. It is notable that in all of the above, issues arise from the use of a guarded choice command to get messages from multiple channels.

javaQest
() автор топика

мань превычесление vs по_обращению(ленивое)

последней твой абзац вообще про чистату

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

Расскажи как должна быть устроена returnFirstReceivedFutureOf, если у нас всё на сообщениях. Вот прям псевдокодом покажи.

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

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

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

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

Только ты начал говорить про практику. А неограниченный индетерминизм на практике сложно и зачастую не нужно реализовывать.

Ну и гарантировать, что клиент будет обслужен в ближайшие 2e300 лет на практике не сильно отличается от отсутствия гарантий.

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

Допустим, так


RFRFO=function(msg1,msg2){
  untill(return new FutureWith(msg1 or msg2)) yield
}

какая, собственно разница, как он реализован?

javaQest
() автор топика

Сначала ответь на простые вопросы:

  1. Является ли в твоем языке функция, работающая с сообщениями, чистой?
  2. Как используемый тобой язык обрабатывает асинхронные сообщения от акторов и влияет на порядок их обработки?
blexey ★★★★★
()
Ответ на: комментарий от javaQest

спс за напоминание норм терминов(норм и энергичный порядки)

там отсутствует порядок в части «допустим любой в редукции аргументов»

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

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

спс за напоминание норм терминов

ну, если вообще по букве, правильно нормальный VS аппликативный, ЕМНИП, :)

ам отсутствует порядок в части «допустим любой в редукции аргументов»

Ну да, я из этого треда уже сам начал догадываться об этом:)

javaQest
() автор топика
Ответ на: комментарий от blexey

Является ли в твоем языке функция, работающая с сообщениями, чистой?

Тут мнения разделяются. Полагаю, таки да, потому что ссылочная прозрачность тут сохраняется.

Как используемый тобой язык обрабатывает асинхронные сообщения от акторов и влияет на порядок их обработки?

Io. Алсо, я видел реализацию на JS где-то.

javaQest
() автор топика

Посылка сообщения эктору и есть функция с сайд-эффектом, наркоман ты хренов!

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

Так в почти любой модели это очевидно функция с сайд-эффектом. А в актор-модели не определено понятие сайд-эффектов. Какие тут пруфы нужны?

Тем более что пруфать нужно обратное: что твоя FirstReceivedFutureOf без сайд-эффектов.

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

Вот что сам Карл Хьюитт пишет

Sending message to an actor is entirelly free of side-effects, such as thouse in the message mechanisms of the current SMALL TALK machine of Alan Kay and the port mechanism of Krutat and Balzer. Being free of side effects allows us a maximum of parallelism and allows an actor to be engaged in several conversations at the same time without becoming confused

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

Они имеют отношение к тому, что мы не знаем какой будет порядок редукций (семантика языка его не определяет, его нет).

семантика языка не может его не определять, поскольку любой ФП-язык базируется все на том же LC, где порядок определяется.

javaQest
() автор топика
Ответ на: комментарий от Aswed

Тут, очевидно, задействуется состояние объекта object.

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

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