[erlang-questions] erlang *****

[Richard A. O'Keefe]

I pointed out that allowing even one outermost level of disjunction of
patterns within a function head makes it possible to express clause  
choice
rules that appear to require exponential time to check.  Let me now  
point
out that my proposed fix, "a variable bound inside a disjunction must  
not
be tested in any other pattern" is not enough.
Instead of
	f({X,_}\/{_,X},
	  {Y,X}\/{X,Y},
	  ...
	  {Z,W}\/{W,Z}
	) ->
take
	f({X,_} \/{_,X},
	  {Y,X1}\/{X1,Y},
	  ...
	  {Z,W1}\/{W1,Z}
	) when X == X1, ..., W = W1 ->

On 18 Mar 2008, at 4:02 am, Andras Georgy Bekes wrote:
> So matching this pattern must involve backtracking. Awww.


I am somewhat at a loss to interpret "Awww".  I would like to think
it's "oh dear, now I understand why this is a really bad idea", but
I suspect it's "silly little you for caring about such things."

OK, let's try this.  As noted by the original proposer, '=' in
patterns is conjunction.  So we can write
	({A,_,_,_,_,_,_,_,_} \/
	 {_,A,_,_,_,_,_,_,_} \/
	 {_,_,A,_,_,_,_,_,_} \/
	 ...
	 {_,_,_,_,_,_,_,_,A}
	)
to express "A is an element of this 9-element tuple".
By using
	?E(A)=?E(B)=...=?E(I)
...
	when A /= B, A/= C, ..., A /= I, ..., H /= I
we can express "{A,...,I} is a permutation of this 9-element tuple".
If you're still with me, you now see how to express any 9x9 Sudoku  
problem
as a single clause match in Erlang extended with pattern disjunction.

I respectfully suggest that the Erlang developers have better things  
to do
with their time.
>

> The problem does exist in a single pattern:
>         {{X,_}\/{_,X},
> 	  {Y,X}\/{X,Y},
> 	  ...
> 	  {Z,W}\/{W,Z}}

It was not clear that the original proposal was calling for embedded
disjunctions.
>

> But what are the real problems with the search for the right match  
> with
> backtracking?

First, the current Erlang pattern matching compiler does not have to  
deal
with backtracking of any kind.  So we are not talking about just a tiny
syntactic extension, along the lines of allowing
	A andalso B
as equivalent to
	case A of true -> case B of true -> true ; false -> false end
	        ; false -> false end
On the contrary, we are talking about a tiny syntactic extension with  
major
semantic effect, requiring a major rewrite of a core chunk of any  
compiler.

Second, the current Erlang pattern matching feature currently has  
predictable
costs.  If you have no repeated variables (the "linearity" condition,  
enforced
in Haskell and SML) the cost of pattern matching is linear in the size  
of the
pattern; with repeated variables it may be linear in the size of the  
input.
This lets us think of pattern matching as a glorified 'case'  
statement, and use
it freely.

> If the programmer has written that silly pattern, he/she
> should be aware that it might not be very fast.

This is what's called a "counsel of perfection", not in the historic
or literal sense (http://en.wikipedia.org/wiki/Evangelical_counsels)
but in the vernacular sense (excellent advice which can only be taken
by people who are already perfect), see for example
(http://forum.wordreference.com/showthread.php?t=5096).

I worked at Quintus for quite a while.  There were an amazing number of
customers who simply could not be made to understand that NO programming
language could solve an EXPTIME problem in linear time.  If an algorithm
could be written in a small number of times, then as far as they were
concerned it HAD to run in a short amount of time, and if it didn't,
then our Prolog compiler was no d--- good.

Now some constraint satisfaction problems of the kind that can be  
expressed
using conjunctions and disjunctions of patterns can be solved  
efficiently,
and some can't.  It's really asking too much for the Erlang compiler  
to tell
which are which and use special strategies for the efficiently  
solvable ones.
It is also asking too much to expect J. A. Luser, a typical Erlang  
programmer,
to figure out which ones are going to run fast and which are not,  
because
the speed will NOT depend just on what the conjoined and disjoint  
patterns
are, but on what the Erlang compiler does with them, and poor old Luser
doesn't know that (and cannot know what the next release of the compiler
will do).

This doesn't apply to the present system, where a fairly naive "what  
you see
is what it does" understanding won't mislead you too badly.

> Are there consequences
> other than the match being slow?

Not slow:  *unbelievably* slow.
>
>
>> I note that my abstract pattern proposal *already* gives you
>> disjunctive patterns, BUT in such a way that the disjunctions can't
>> interact like this.
> Could you give some reference?
> I've searched for "abstract pattern" in the archives and found a few
> mail, but not your paper.

A Google search for "abstract patterns Erlang" quickly located
http://www.erlang.org/ml-archive/erlang-questions/200309/msg00309.html