Lazy values are not guaranteed to be evaluated just once if accessed concurrently

[anfelor]

In a multi-core setting, it is possible for two threads to read the reference of an uninitialized lazy value and execute the action concurrently:

koka/lib/std/core/delayed.kk

Lines 31 to 41 in 19fc79d

	// Force a delayed value; the value is computed only on the first
	// call to `force` and cached afterwards.
	pub fun force( delayed : delayed<e,a> ) : e a
	unsafe-total
	val r = delayed.dref
	match !r
	Right(x) -> x
	Left(action) ->
	val x = mask-st{ mask<div>(action) }()
	r := Right(x)
	x

This implementation is sound for pure computations where duplicate evaluation can not be observed, but not for arbitrary algebraic effects. This mirrors the issue that Haskell had with lazy thunks containing unsafePerformIO. We could solve this problem by using an atomic compare and swap operation instead of the read instruction that puts a special Blackhole value into the reference and blocks if there is already a blackhole value in the thunk. While this is potentially expensive, it is only necessary if the value is thread-shared and we can continue using this faster implementation otherwise.

[TimWhiting]

I know this code was updated on dev since this, but is it fixed or not? It seems like there is still a race condition on setting r as Blocking or is this not the case?

[anfelor]

I agree, this issue still exists. We should write Blocking using a compare-and-swap and then check what to do based on the previous value.

The update on dev fixed a different issue: In line 39 above, the action is not unique which incurs a significant performance penalty. In 0636723 I updated the force function to write Blocking into r to avoid holding on to action while the thunk is evaluated.