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

Вообще, ты так любишь вести разговоры с этим шизиком

А ведь ты, говоришь, по сути, то же что и он, (в отличии от других участников, за исключением qulinxao) Странно.

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

Кто «он»?

кого ты назвал шизиком

По какой сути?

По-поводу наличия порядка вычислений в ФП.

Я молчал.

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

anonymous
()

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

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

Вот! Наконец-то говорим по делу.

Опустим детали про создание актора на каждое сообщение по ссылке на этот раз.

Sending message to an actor is entirelly free of side-effects

Твоя функция не только отправляет сообщение. Она с сайд-эффектами. Следовательно, вопрос в ОП-посте можно переформулировать в вкусовщину вроде того, «что лучше для хранения состояния — монады или акторы». И чистыми моделями как LC, так и actor model, тут даже не пахнет. Ты хочешь сравнить unlambda со, скажем, Io (в рамках которого, кстати, код в ОП-посте будет выдавать постоянный результат поскольку там есть очередь сообщений и нет тредов) или какой-нибудь Erlang?

И да, всё, что ты описал в ОП-посте, можно сделать хоть в рамках lambda calculus, но это будет жутко неудобно.

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

Твоя функция не только отправляет сообщение

ну да, она кроме отправки сообщений возвращает фьючер. То есть, возвращать что либо — это сайд-эффект?

поскольку там есть очередь сообщений и нет тредов

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

Erlang

В эрланге, насколько я помню, fog-cutter акторы, они не соответствуют общей модели.

можно сделать хоть в рамках lambda calculus

сомневаюсь.

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

можно сделать хоть в рамках lambda calculus

Это невозможно, потому что LC не может обладать свойством неограниченного нондетерминизма.

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

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

Ты врёшь. Там заявляется конкурентность на основе акторов. Объяснить разницу? И да, реализация соответствует заявленному.

сомневаюсь.

Напомнить о том, что всё, происходящее на любом ПК, можно смоделировать на машине Тьюринга? И о том, что из этого следует?

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

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

Тем более что в данном случае неограниченный индетерминизм нафиг не нужен.

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

Там заявляется конкурентность на основе акторов. Объяснить разницу?

Разница в том, что конкурентность обеспечивает абстрагирование от реального количества процессоров. Параллелизм же — это то что мы имеем либо поверх этой абстракции. Как-то так.

Напомнить о том, что всё, происходящее на любом ПК, можно смоделировать на машине Тьюринга? И о том, что из этого следует?

Это спорно. ПК имеет в своем арсенале прерывания, конкурентность, интерактивность, имеет доступ к модификации кода программ(код не отличается от данных, данные не имеют полной изоляции от кода). Этого всего МТ лишена

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

поскольку неограниченного индетерминизма у нас и нет

почему это у нас его нет?

Тем более что в данном случае неограниченный индетерминизм нафиг не нужен.

Где он не нужен? Если его не будет, в данном примере, наша функция test будет либо возвращать всегда одно и то же, либо, в лучшем случае, ограниченное количество вариаций.

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

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

Omfg, лавры sleepsort не дают тебе покоя и ты изобрёл генератор случайных чисел на акторах, который требует либо открытую модель, либо квантового компьютера для запуска. Алсо, man probabilistic Turing machine.

Это спорно. ПК имеет в своем арсенале прерывания, конкурентность, интерактивность, имеет доступ к модификации кода программ(код не отличается от данных, данные не имеют полной изоляции от кода). Этого всего МТ лишена

Модификация кода программ как аргумент? Серьёзно? Чёрт, анонiмус запретил моделировать JIT на МТ.

Конкурентность туда же, поскольку конкурентность можно эмулировать и одним потоком (если ты про параллелизм — смотри выше про вероятностная если ты опять про RNG-over-actors, для прочих же алгоритмов вероятностная нафиг не нужна).

Интерактивность — всего лишь способ ввода данных. МТ определена над данными. Ничерта нового. Да, вероятностная машина Тьюринга в общем случае.

Прерывания общую картину не меняют.

почему это у нас его нет?

Потому, что его невозможно реализовать, можно лишь эмулировать с достаточной точностью. Не понимаешь, почему? Прочитай определение.

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

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

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

можно лишь эмулировать с достаточной точностью. Не понимаешь, почему? Прочитай определение.

А это не важно, эмулируешь ты или на самом деле имеешь.

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

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

В таком случае он не может принимать сообщения

ты бред какой-то несешь. Муттабельность объекта никакого отношения к приему сообщений не имеет. Если уж несешь этот бред, прилагай пруфы, хотя бы. Только не на бложек Васи.

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

Интерактивность — всего лишь способ ввода данных. МТ определена над данными. Ничерта нового. Да, вероятностная машина Тьюринга в общем случае.

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

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

Конкурентность туда же, поскольку конкурентность можно эмулировать и одним потоком

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

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

Кстати, пруф или не было.

неопределенность в квантовой механике.

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

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

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

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

Собственно целей я своих добился, я уже давно отметил тему как решенную:)

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

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

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

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

Очень тупой тред, надеюсь, тебе забанили всю подсеть.

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

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

У акторов есть стейт. У функции - стейта нет. наличие стейта - сайд-эффект.

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

Чистая ф-я - такая ф-я, которая возвращает одинаковый результат на одинаковых входных данных. Это определение.

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

В модели акторов этого ограничения нет. Нет понятия шага.

Пруфы можно? Где можно увидеть формальное описание модели акторов и убедиться, что там никаких шагов нету?

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

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

В хаскеле не используется. Ни тот, ни другой.

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

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

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

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

Это невозможно, потому что LC не может обладать свойством неограниченного нондетерминизма.

А зачем им обладать? Это свойство никак не повышает вычислительные воможности системы, так что его наличием можно смело пренебречь.

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

В какой именно семантике?

У LC нету никакой семантики. Это просто язык (набор термов построенных по определенным правилам), отношение эквивалентности на них и выделенное множество нормализованных термов.

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

В естественной

Это что-то новенькое.

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

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

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

у чистой функции стейта быть не может. у актора - может значит актор не обязательно является чистой функцией

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

а бета-эквивалентность (и еще ряд других эквивалентностей)

а факториал 5 эквивалентен факториал 4?

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

у чистой функции стейта быть не может. у актора - может значит актор не обязательно является чистой функцией

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

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

рандом, его реализацию, причем реализацию на чистом ФП

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

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

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