Functional programming with branches that have no order?

Question

I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for things like optimization or parallelization. Using the functional language Haskell as an example:

f x
 | x < 0 = -1
 | x > 0 = 1
 | otherwise = 0

is the same as:

f' x
 | x > 0 = 1
 | x < 0 = -1
 | otherwise = 0

Is it possible in some languages or paradigms to make the semantics of the function not dependent on the order in which the branches are defined (probably with special treatment of the otherwise case)?

Answer 1

Here's the problem:

1. You always need some way to resolve ambiguity when there are overlapping clauses
2. There is no easy syntactic way to ensure that clauses don't overlap.

So, if you can think of a way for the behavior of if to be well defined when there are overlapping clauses, that doesn't depend on the ordering of the clauses, then you can do what you're asking for.

And, there are, of course, a bunch of ways to define this: you could always default to the simplest matching condition (with the shortest code), you could attach an integer at runtime to each case and use the one with the highest number, etc.

But at their core, the process of looking at overlapping cases and choosing one, basically involves ordering the cases in some way. Requiring the user to specify the ordering, and having the order in the source code match the "priority" of each clause, seems like the simplest option.

There is likely a way to ensure that ordering doesn't matter in a dependently-typed language, when you can actually construct a proof that all your clauses are mutually exclusive. Or, you can re-order clauses in an optimizer, if a static analyzer identifies a place where all the clauses are mutually exclusive.

Or, if you're in a non-deterministic language like Prolog, you can just explore all the branches that succeed, and have an if expression return multiple answers. But for most languages, this isn't compatible with their deterministic semantics.

In general, you can't just ignore the order.

Answer 2

If you restrict yourself to using constructors of datatypes, the compiler knows what can happen during pattern matching. For instance, assume your integer type is defined by this:

datatype integer = Zero | Positive of natural | Negative of natural

Then, the example from your question translates to:

fun f Zero        = 0
|   f Positive(n) = 1
|   f Negative(n) = -1

Now, the compiler knows that the alternatives are

1. exhaustive and
2. mutually exclusive

and it can optimize away.

Be aware that this is likely a micro-optimization of the premature denomination. Especially in functional languages -- where you program at high levels ob abstraction -- I would not worry about such details. Unless you have made very sure that this is a performance hotspot.