[erlang-questions] erlang *****

Andras Georgy Bekes bekesa@REDACTED
Tue Mar 18 12:59:16 CET 2008


> > 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."
I meant: "Oh, sh** there is some real problem with this idea I failed to 
think about. It probably needs radical changes in the compiler/vm with 
consequences I surely can't foresee."

> 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. 
Wow, THAT would be a great advertisement for Erlang ;-)

> 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

Back to the real world: I worked with Prolog much, and wouldn't expect 
anything better than a depth-first search for the first match. I think 
I'd use it quite happily without having too much trouble with 
unexpected match times.

I think the simple backtracking wouldn't be hard to implement, however, 
it certainly needs radical changes in the compiler/vm, and has 
unforeseen consequences.

> Second, the current Erlang pattern matching feature currently has  
> predictable costs.
Consequences like this: I might be wrong, but I think a pattern match is 
an atomic operation in the VM, I mean, the scheduler won't switch to 
another process in the middle of a pattern match. If this is true, a 
long pattern match halts the whole Erlang VM. With careful work, you 
can forge a long-running pattern match in Erlang (as you said: "it may 
be linear in the size of the input") but with the 
backtracking-pattern-union match it is just so much easier. I think I 
am convinced, it is a really-really bad idea.

However, if a pattern match is not atomic in the above sense, it can't 
cause such big trouble. I mean, at least the above problem does not 
exist. There might be other serious issues I failed to think about.

> It was not clear that the original proposal was calling for embedded
> disjunctions.
It was. Basically I suggested '\/' as a
pattern*pattern -> pattern "function", which can be used anywhere.

However, what Robert suggests is a nice compromise:
> foo(Pat11, ...) when Guard1 ;
> foo(Pat12, ...) when Guard2 ;
> foo(Pat13, ...) when Guard3 ->
>     ...;
and
> case ... of
>     Pat1 when Guard1 ;
>     Pat2 when Guard2 -> ...;
>     ...
> end

This doesn't need any radical change in the compiler/vm. You simply act 
as if the only clause body was used for all the patterns.

I'd be happy with this solution: it would solve >90% of the cases I'd 
use pattern union for. But only together with the pattern-match-test 
guard BIF. I'd still need it :-)

However, I don't think the above syntax is a good enough: after the ';' 
token either a guard can follow (guard expressions separated by ','s) 
or a new pattern. There should be a new keyword I think.

	Georgy



More information about the erlang-questions mailing list