Gotta love lazy infinite loops :-D Sounds like something out of a Douglas Adams novel. Ok, this post is totally off-topic... On 9/22/07, Pasqualino 'Titto' Assini wrote:

...

...

The funny thing is that, while it is stuck in an infinite loop, GHCi doesn't seem to use any CPU time at all.

Peter Verswyvelen wrote:

http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.html http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.htmlseems to confirm that?

Oops, sorry, these seems to be docs for Concurrent Haskell... But maybe the experts can confirm if the principle still stands?

I guess you entered a black hole! :-)

The problem is that don't understand black holes myself, I just got introduced with the same thing yesterday :-) I confused me a lot too.

The only explanation I could give you intuitively is that GHCi is running in multi threaded execution mode, and that two or more execution threads are waiting for each other forever, creating a "deadlock".

http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.html http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.htmlseems to confirm that?

If you try the same using (Win)HUGS, you'll get 100% CPU time usage.

Cheers, Peter Verswyvelen

Pasqualino 'Titto' Assini wrote:

...

Hi,

if I define:

f = f

and then try to evaluate 'f' in GHCi, as one would expect, the interpreter never returns an answer.

The funny thing is that, while it is stuck in an infinite loop, GHCi doesn't seem to use any CPU time at all.

How is this possible?

Thanks

titto

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

------------------------------------------------------------------------

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Peter Verswyvelen wrote:

http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.html http://www.haskell.org/ghc/docs/2.10/users_guide/user_146.htmlseems to confirm that?

Ouch. Would it be possible to somehow prevent this behavious? (E.g., by somehow annotating each black hole with *which* thread is evaluating it, so that if a thread reaches one of the black holes that it created itself, it can throw an error..?)

Hi

I'm not sure, but since it would require the detection of an evaluation that does not terminate, it comes down to the halting problem, which is not generally solvable. Maybe the experts can confirm my intuition?

I think your intuition is off. This isn't the problem of detecting that a computation might not halt, its a question of detecting after the fact a very restricted case of non-termination has occurred. I think it should be possible to assign threads etc to these things, but may make the code run slower in the common case. Thanks Neil

Hello Lennart, Sunday, September 23, 2007, 2:05:46 PM, you wrote: i bet that general case contains too much conditions to check. program may be unblocked by other thread, by OS signal, by I/O operation completion, by C thread. how for example RTS can check that we have started I/O operation with completion callback which will call abort() function?

I agree.  This situation is totally detectable.

On 9/23/07, Neil Mitchell wrote: Hi

...

I'm not sure, but since it would require the detection of an evaluation that does not terminate,  it comes down to the halting problem, which is not generally solvable. Maybe the experts can confirm my intuition?

I think your intuition is off. This isn't the problem of detecting that a computation might not halt, its a question of detecting after the fact a very restricted case of non-termination has occurred. I think it should be possible to assign threads etc to these things, but may make the code run slower in the common case.

Thanks

Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Lennart, Sunday, September 23, 2007, 8:30:43 PM, you wrote: and GHC stops executing this thread - wise solution. but it can't decide whether some signal handlers/backcalls are established and so whther are program definitely will never finish or not

But this was a very particular case when a thread starts evaluating a node and then comes back to the same node again. The general case is (of course) undecidable.

On 9/23/07, Bulat Ziganshin wrote: Hello Lennart,

Sunday, September 23, 2007, 2:05:46 PM, you wrote:

i bet that general case contains too much conditions to check. program may be unblocked by other thread, by OS signal, by I/O operation completion, by C thread. how for example RTS can check that we have started I/O operation with completion callback which will call abort() function?

...

I agree. This situation is totally detectable.

...

On 9/23/07, Neil Mitchell wrote: Hi

...

...

I'm not sure, but since it would require the detection of an evaluation that does not terminate,it comes down to the halting problem, which is not generally solvable. Maybe the experts can confirm my intuition?

...

I think your intuition is off. This isn't the problem of detecting that a computation might not halt, its a question of detecting after the fact a very restricted case of non-termination has occurred. I think it should be possible to assign threads etc to these things, but may make the code run slower in the common case.

...

Thanks

...

Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org    http://www.haskell.org/mailman/listinfo/haskell-cafe

...

-- Best regards, Bulat                            mailto:Bulat.Ziganshin@gmail.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Peter Verswyvelen wrote:

I though it was impossible to detect a deadlock (and a black hole is something like a deadlock no?) *before* it occurred, but in this case, we're talking about detecting it *when* it occurs, no? And then raising an error instead of just blocking?

Generally, it's not possible to prevent a deadlock before it occurs; it's actually equivalent to the halting problem. When a deadlock is about to occur, it /is/ possible, is principle, to detect the condition and raise an error. What you would need to do is keep track, for each thread, of everything that thread may depend on. Whenever a thread tries to allocate a resource, you need to scan the dependency graph and determine whether or not the new allocation is safe. Sometimes you might raise a false alarm, though. Once a deadlock has /already/ occurred, it becomes easier to detect, but detection still depends on being able to determine everything a thread might depend on. Now in GHC, apparently, when a thread needs a value that hasn't been calculated yet, the thread blocks, waiting for that value to be calculated. If the Haskell code creates an infinite loop, then a thread may block waiting for itself. The example given is f = f. Well, before we ask for self-blocking detection, lets try a bigger loop like (f = g ; g = f) and suppose that the computations of f and g get assigned to different threads. Self-blocking detection won't help you here. You need some kind of loop-blocking detection. At this point, I would assume that as we take more things into account, the problem of detecting deadlock becomes increasingly complicated and the detection algorithms consume more and more resources. That's why many major operating systems don't have deadlock detection. On the other hand, perhaps deadlock detection is the wrong way to look at this. I think we are casting a net that's too big for the problem that we're really trying to solve. A deadlock happens whenever two (or more) threads are blocked on each other. Deadlocks can be extremely hard to detect, especially if they occur intermittently. On the other hand, we as programmers can detect, at design-time, that f = f is an algebraic loop. We know that some loops are just "tying the knot" and they're perfectly fine, while other loops involve self-dependency and evaluate to bottom. fib = 1 : 1 : zipWith (+) fib (tail fib) -- tying the knot foo = 1 : zipWith (+) foo (tail foo) -- algebraic loop Looking closer at foo, if we let x = (foo !! 1), then we have the equation x = 1 + x. The result is that x = bottom. To detect an algebraic loop, we would need to express a computation as a dependency graph and then look for any loops in the graph. As long as we are looking at a /pure/ computation, my intuition tells me that in many cases it should be possible, through static analysis, to build the dependency graph and check for any loops. Moreover, my intuition tells me that the static analysis involved in building these dependency graphs might already be available as part of an existing optimizer. Even if we don't detect an algebraic loop at compile-time, I think we could definitely detect it at run-time if we have enough computational resources. -- Ron