[erlang-questions] erlang *****

Richard A. O'Keefe ok@REDACTED
Tue Mar 18 01:25:32 CET 2008

I pointed out that allowing even one outermost level of disjunction of
patterns within a function head makes it possible to express clause  
rules that appear to require exponential time to check.  Let me now  
out that my proposed fix, "a variable bound inside a disjunction must  
be tested in any other pattern" is not enough.
Instead of
	) ->
	f({X,_} \/{_,X},
	) 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,_,_,_,_,_,_} \/
to express "A is an element of this 9-element tuple".
By using
	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  
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

> 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  
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  
semantic effect, requiring a major rewrite of a core chunk of any  

Second, the current Erlang pattern matching feature currently has  
costs.  If you have no repeated variables (the "linearity" condition,  
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  
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

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  
using conjunctions and disjunctions of patterns can be solved  
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  
to figure out which ones are going to run fast and which are not,  
the speed will NOT depend just on what the conjoined and disjoint  
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

More information about the erlang-questions mailing list