[erlang-questions] erlang *****

[Richard A. O'Keefe]

On 18 Mar 2008, at 11:26 pm, Alpár Jüttner wrote:
>
> The current pattern matching is also NP, so it wouldn't be a problem.
> (Contrary to a common misconception, the meaning of NP is _not_
> non-polynomial!)

NP means "non-deterministic polynomial" and is most simply thought of
as "answers can be checked in polynomial time but not necessarily
found in polynomial time".  NP includes P.

I expect we all know that.  NP is often used in a "vernacular" sense,
meaning (real NP) \ P.

> However, if pattern matchings are done one-by-one

  why should they be?

> and left-to-right,

  why on earth should they be?
>
> then there is no performance problem.

That is, you are proposing that
	f(P1 \/ P2, P3 \/ P4) -> B
should be treated like this Prolog version:
	f(X, Y, Ans) :-
	    (X = P1, ! ; X = P2, !),
	    (Y = P3, ! ; Y = P4, !),
	    B'(Ans)
rather than like this Prolog version:
	f(X, Y, Ans) :-
	    (X = P1 ; X = P2),
	    (Y = P3 ; Y = P4),
	    !,
	    B'(Ans).


> The union operator becomes less
> flexible in this case, but it is still quite useful.

It may be slightly useful on rare occasions, but it would be
*extremely* confusing.  The interaction with guards is really
quite nasty.  Take an example:

	f({X,_}\/{_,X}, {Y,_}\/{_,Y}) when X > 0, Y > 0 -> {X,Y}.

with the call
	T = {-1,2}, f(T)

It's obvious that f(T) should return {2,2}.  Under the "backtracking"
translation, where the "->" of Erlang corresponds to the "!" of Prolog,
it's even true.  But under the "choice always cuts" model, it fails.
Try explaining *that* to an Erlang novice.

It is OK for programming language constructs to be clumsy and limited
in power.  It is not OK for them to be stark raving mad.

The only time that the local commit model makes sense is when the
disjunctive pattern binds no variables.  An extension of Erlang to
allow P1\/P2 precisely when P1 and P2 contain no variables other
than wild-cards *would* be reasonably trouble-free, except that we
would have a continuing stream of people proposing that it be  
generalised.


>
>
> Actually, if we want the pattern matching to be deterministic, we  
> _must_
> do such a restriction. For example using the patter {X,_} V {_X}, the
> value of X could be either element of the tuple. Using the left-to- 
> right
> rule, X will always be the first element.
>
> Regards,
> Alpar
>
>

--
Te Reo Engarihi is a taonga of Te Iwi Pakeha,
ergo we should keep it pure, sans mélange, ruat caelum.