Home

Demonic Nondeterminacy: A Tribute to Edsger Wybe Dijkstra

Jayadev Misra's tribute to EWD at Europar-2003.

A short essay that may be relevant to the question whether language designers should make their languages more forgiving as regards programmer errors, or more stringent.

By Ehud Lamm at 2004-08-30 15:01 | General | other blogs | 6827 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Huh?

My general response to that one was, "Huh?"

Anyone have a clearer reference to what he was talking about?

By John Carter at Tue, 2004-08-31 01:46 | login or register to post comments

What exactly?

Are you asking about Dijkstra's work, or about the general claims made by the author?

By Ehud Lamm at Tue, 2004-08-31 08:36 | login or register to post comments

angelic?

"Let us call this angelic nondeterminacy,
for obvious reasons."
I missed the point why it was 'angelic' for obvious reasons? There has to be a pun somewhere here I'm not catching.

nicely written though, and I liked the observation of algorithmic variability of implementation on different platforms as being a reason for embracing nondeterminancy.

By pantagruel at Tue, 2004-08-31 08:40 | login or register to post comments

Another reason it's angelic

When I read it, I thought the "obvious" reason it was angelic was that it required clairvoyance.

I like the conclusion, though; it reminds me of a line from The Vor Game: "The key of strategy, little Vor, is not to choose a path to victory, but to choose so that all paths lead to a victory."

By John Stracke at Thu, 2004-09-02 01:27 | login or register to post comments

non deteminism

See here for the the defintions (under non-blind backtracking), or here.

The control operator is angelic if, in some sense, it takes you to the best possible result (like an angel).

When we use amb, we can build up from the assumption that amb will return a result such that the entire computation doesn't result in failure. The implementation may use backtracking to achieve this result, but from the programmer's point of view amb simply guarantees to return a good result, i.e., it is angelic.

This is one possible interpretation of determinism. This is quite similar to the way we think about non-deterministic finite automata (NFAs) for example.

By Ehud Lamm at Tue, 2004-08-31 08:54 | login or register to post comments

the theology of programming

I think actually I would like to see more theology oriented posts :)
I see now you are correct that the control operator is angelic, but it seems a very low level type of angel, what about the other ranks?

we should focus some on them.

I am also very interested in the diabolical, demonic nondeterminancy is good, but what about when satan comes to dinner?

By pantagruel at Tue, 2004-08-31 09:08 | login or register to post comments

:-)

:-)

By Ehud Lamm at Tue, 2004-08-31 10:05 | login or register to post comments

non-determinism

Isn't this the difference between "probabilistic" and "non-deterministic" evolution? The first one means that we throw the dice and choose one step (angelic = we hope we are lucky) at each point in time while the second one means that we are actually observing all possible steps at all times (which doesn't preclude us to consider some steps more "probable" - i.e. something like Markov chains).

By rgrig at Tue, 2004-08-31 11:03 | login or register to post comments

hoping we are lucky

couldn't resist

By pantagruel at Tue, 2004-08-31 11:55 | login or register to post comments