[erlang-questions] Lack of warning for overlapping clauses with

Wed Jul 21 01:43:59 CEST 2010

On Jul 21, 2010, at 10:24 AM, Torben Hoffmann wrote:
>
>
> Well, I actually ran into a problem with this in a real program and  
> it was by sheer coincidence that I noticed the overlapping clauses,  
> so I would have liked the compiler to spot this.

It would be really really good to see the actual code, if possible.
>
> Given the Haskel evidence it seems that the problem is even harder  
> than I imagined at first, so maybe I am expecting too much...  
> expecting too much becomes so natural when you work with Erlang.
>
> This means that there are two or more actions to be taken on this:
> 1. Ask a bright person who is into type checking to look at this in  
> his thesis project.

There is no type problem here; everything is well typed.

Let's take a really abstract look at this.
We have two clauses
	...
	f(<patterns 1>) when <guard 1> -> <body 1>
	...
	f(<patterns 2>) when <guard 2> -> <body 2>
	...
and the question is whether there exist <arguments>
such that
	(<patterns 1> = <arguments> and then <guard 1>)
and
	(<patterns 2> = <arguments> and then <guard 2>)
has a solution.  A program to solve this problem would
presumably be able to display such <arguments>, at least
schematically.

Now, it's clear that *both* clauses have a match only if
at least one of them has a match.  So the problem of
checking for an overlap is at least as hard as the problem
of determining whether *one* clause can reach its ->

Let X1,...,Xn be variables.
Let P(X1,...,Xn) be a polynomial in X1,...,Xn with
integer coefficients.  That is, it involves integers,
head variables, add, subtract, and multiply, and is
clearly a legal guard expression.
Consider the clause

	f(X1, ..., Xn)
	  when is_integer(X1), ..., is_integer(Xn),
	       P(X1, ..., Xn) =:= 0 ->
	    <body>

The general problem of detecting whether two clauses
has to be AT LEAST as hard as detecting whether THIS
clause can start executing its body.

Matiyasevich showed in 1970 that there is NO algorithm
that can decide this.  (Hilbert's tenth problem: find
an algorithm to decide whether any Diophantine equation
has a solution; the answer is sorry, can't do that.)

Thus we have a typical "Full employment theorem" for
writers of Erlang (or Haskell) checkers: it will
always be possible to find overlap examples that cannot
be detected by the current algorithm, so it will always
be possible to improve the current algorithm.

And note that this applies with very limited guards:
there is no disjunction here, no reaching into data
structures, in fact no data structures other than integers.

> 2. Change my style of programming so that it stays within the bounds  
> of what the compiler will warn me about.

I have a bad feeling about the solvability of "do these two
binary patterns have a common instance", so you had better
avoid binary patterns.  (:-)

You can't expect a compiler to warn you about every conceivable
problem.  As a trivial example,

	f() -> m:g(1).

If m:g/1 is not available to the compiler, who knows what it might
do?  How could the compiler warn you "this function will always
crash" when it hasn't seen that function?  Worse, suppose the
compiler *can* see a definition of m:g/1, but at run time it is
replaced by a different one.  Is the compiler to warn you about
every remote call
	Warning: you are calling a function that might be
	replaced at run time by another definition that might
	do all sorts of horrible things.

I suppose we could call this a full employment theorem for
testers and debuggers:  in any nontrivial programming language
there will be bugs expressible that no algorithm can
infallibly detect.  (Note: the Dialyzer does NOT claim to
infallibly detect bugs.  It makes the weaker claim that the
things it detects are bugs; it will certainly miss some.)

Keep your style as clear as you can so that other people can
understand it.  Write specifications and test cases.  (Ulrich
Neumerkel -- hope I've spelled that right -- has worked on a
teaching environment for Prolog called GUPU that requires
students to write test cases first, and tests the tests.  A
neat idea.)  When you find something that the compiler didn't,
ask if the compiler can be improved to detect it.  It's an
economic trade-off:  how likely is the bug, what are the
expected consequences of not finding it, how costly will it
be to improve the compiler to that level.

> 3. [Optional] Put some explanations/warnings in the Erlang  
> documentation so that people are not led astray like me.

It's not clear precisely what you want people to be warned
against.  "Expect the compiler to be right but dumb" is about
all I can think of here.