2
$\begingroup$

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)?

$\endgroup$
  • 3
    $\begingroup$ I'm not sure both definitions are the same in terms of the running time. In terms of semantics, whenever you have mutually exclusive cases, the order of branches doesn't matter. This is even the case in non-functional programming languages. $\endgroup$ – Yuval Filmus Feb 15 '16 at 18:51
  • $\begingroup$ Wait ... are you asking for a "(can) do in parallel" operator? $\endgroup$ – Raphael Feb 16 '16 at 23:47
  • $\begingroup$ @Raphael Sort of. What actually motivated this question is SQL and declarative programming. I was reading array DBMS en.wikipedia.org/wiki/Array_DBMS, and an array query language should be declarative and safe in evaluation... avoiding general loops and recursion is a way of achieving this. It seems to me that order is the problem with "general loops and recursion". But this is a vague thought. I think the above also has to do parallel processing of arrays. $\endgroup$ – tinlyx Feb 17 '16 at 2:20
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "And, there are, of course, a bunch of ways to define this: you could ... " - ... execute all matching branches. $\endgroup$ – Raphael Feb 16 '16 at 23:36
  • 1
    $\begingroup$ A typical case where the compiler knows the branches are mutually exclusive (and exhaustive) is pattern matching. Depending on which constructors exist for integers, the example from the question may even work out. $\endgroup$ – Raphael Feb 16 '16 at 23:38
  • 1
    $\begingroup$ Pattern matching isn't necessarily mutually exclusive, for example, since a wildcard pattern _ will always overlap with any other pattern. But it's certainly an area where checking for overlap is decidable, and allows for lots of optimization. $\endgroup$ – jmite Feb 16 '16 at 23:47
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.