Lambda the Ultimate

Non-determinism in functional languages. Sondergaard and Sestoft. The Computer Journal, Volume 35, Issue 5, pp. 514-523. 1992

The introduction of a non-deterministic operator in even an very simple functional programming language gives rise to a plethora of semantic questions. These questions are not only concerned with the choice operator itself. A surprisingly large number of different parameter passing mechanisms are made possible by the introduction of bounded non-determinism. The diversity of semantic possibilities is examined systematically...

A very useful paper if you are interested in this sort of thing. Thinking of non-determinism helps calrify muddled thinking about properties such as referential transparency.

The version I found online, alas, is a set of tiff image files, one for each page...