Ленивость и многопоточность

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

Я подписался на этот бред, вечером почитаю смешные коменты.

А что thread-local?

Тебе ссылки на статьи или тут на потроллить?

http://www.amazon.com/Parallel-Concurrent-Programming-Haskell-Multithreaded/d...

Не, тут нужно SPJ и SM статьи, по поводу того как все устроено и все эти наши gray/black holes. Заодно про unsafe/unsafeDupablePerformIO и прочих друзей.

Всего этого не происходит. Он работает тупо в лоб

Чтобы знать, вычислен thunk или нет, надо хранить состояние. А к состоянию могут быть data race'ы.

Это настолько же неверное утверждение как и предположение ТС.

Lazyness есть, а куча остальной магии - отсебятина ТСа

Отсебятина ТС'а это что-то странное, но для работы с линивыми значениями в многопоточной среде всеж используются действия позволяющие обрабатывать случаи если двое тредов решили одновременно вычислить значение (что безопасно, но хочется избежать если вычисления большие). К сожалению я забыл название конкретной статьи, где это было хорошо расписано. А с телефона быстро пересмотреть похожие статьи чтобы найт и неудобно.

В Хаскеле, емнип, используется STM.
В Эрланге эта проблема зарыта достаточно глубоко в недра BEAM, чтобы о ней париться разработчику. Для него у каждого процесса существует своё собственное «состояние», изолированное от других.

Главный ключевой термин для гугления qnikst уже назвал: black holes (есть и другие, но это самое важное). Когда один тред обёртку форсирует, он ставит на неё пометку, чтобы другой тред ждал его (если этому другому треду вдруг помеченное замыкание понадобится). Возможные при этом состояния гонки роли не играют, поскольку они на результат выполнения программы в целом влияния не оказывают.

STM к обсуждаемой теме отношения не имеет, скорее всего.

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

Для чистой функции?

http://ezyang.com/jfp-ghc-rts-draft.pdf, а именно:

4.2 Synchronization

We now turn our attention to how thunks are updated. Updating a thunk with its new value constitutes mutation on shared state, thus, thunks up date is an important obstacle on the way to thread-safety.

A naıve approach is to synchronize all of the updates. This is extremely costly: Haskell programs do a lot of thunk updates! Once again, our saving grace is purity: as thunks represent p ure computation, evaluating a thunk twice has no observable effect: both evaluations are guaranteed to come up with the same result. Thus, we should be able to keep updates to thu nk unsynchronized, at the cost of occasional duplication of work when two threads race to evaluate the same thunk

[...]

4.3 Black holes

Some thunks take a long time to evaluate: we’d like to avoid du plicating their work. What we would like is for threads to notice when someone is working on a thunk, and wait for the result to become available. The mechanism by which this is implemented is a black hole , which represents a thunk that is currently being evaluated. A thunk can be claimed by overwriting it with a black hole. Black holes were originally proposed as a solution for a space leak that occured in some cases of tail calls (Jones, 2008), but they have found th eir utility in a multithreaded setting. Recall that a thread wishing to evaluate a thunk jum ps to the entry code; the entry code of a black hole places a thread on the blocked queue of the owner the black hole, to be woken up when the thunk has been evaluated.

There are two times when a black hole can be written: it can be eagerly written as soon as a thunk is evaluated, or it can be lazily deferred for when a thread has gotten descheduled (and thus the thunk was taking a long time to evaluate.) If a bl ack hole is written eagerly, it is on the fast path of thunk updates, and we cannot use synch ronization. We call these eager black holes (also known as grey holes ), which do not guarantee exclusivity. Lazy blackholing is done more infrequently, and thus we can affor d to use a CAS to implement them.

The upshot is that GHC is able to implement lazy evaluation wi thout any synchroniza- tion for most thunk updates, applying synchronization only when it is specifically neces- sary. The cost of this scheme is low: a single extra field in thu nk and a (rare) duplication of work upon a race [...]

нужны какие-то механизмы синхронизации. А механизмы синхронизации это уже состояние

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

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

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

Всё так. Конкретно по твоему вопросу: когда тред начинает вычислять санк, infoPtr санка перезаписывается и при повторном заходе в него из другого треда, тред лочится. На самом деле немного хитрее, но суть примерно такая.

А почему не написано, когда происходит это «specifically necessary» в

applying synchronization only when it is specifically neces- sary

?

Ссылочная прозрачность. Ну, вычислишь ты один и тот же thunk дважды или трижды. Разве от этого результат изменится, хотя как тут подсказывают, существует некий механизм от повторных вычислений. Это уровень thunk'ов.

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

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

Чего? Такой тупизны ни разу еще не слышал, ты реально чемпион.

Хотел сперва тебя отправить в статьи СПЖ, СМ или хотя бы в бложек к Янгу. Но потом подумал, а чем ты такое снисхождение заслужил?