[erlang-questions] erlang *****

[Richard A. O'Keefe]

On 18 Mar 2008, at 6:37 pm, Matthew Dempsky wrote:
> I think it's "So what? There are lots of programming constructs that
> when misused can lead to inefficiency."

No, it's much worse than that.  We are talking about a construct
where the programmer CANNOT TELL whether it will be efficient or not.
It isn't hard to come up with examples where matching will be O(n)
if done right to left but O(2**n) if done left to right, for example.
And we are not talking about just any construct:  we are talking
about one of the most fundamental constructs in the language.
> \

> You'd laugh at someone who was concerned about adding recursive
> functions to a language because a naive user might write "fibb(N) =
> fibb(N - 1) + fibb(N - 2)" or that adding general looping constructs
> means we can't ensure arbitrary programs will halt on a given input.

As a matter of fact, no I *wouldn't* laugh at such a  person.  There are
application domains where banning recursion is extremely sensible.  If I
were programming an embedded device, I would definitely want a language
that banned non-tail recursion.  I would also want loops somehow  
restricted
to ensure that the response to an event was certain to arrive in a  
bounded
time.  I even got SPARK for a project that was going to do some embedded
work (but the student decided to get a sex change instead of a Masters).

But your examples are really not in any way comparable.  We are talking
about a change to the programmer's cost model of the language even more
drastic than saying "a[i]" is no longer O(1) but O(lg #a)", and that
change is enough to make a major difference to the kind of algorithm one
uses.

Also, if a naive user has a body recursive fibb/1 function, s/he can  
trace
it and see what's happening.  Are you proposing that there should be  
some
kind of profiling or tracing facility that goes *inside* pattern  
matches?
If not, how is the naive programmer ever to find out why his/her program
is slow?

> I see no reason to worry about similar arguments for disjunctive
> patterns.


Look harder.

This is a huge change to the language, and we don't need it.

I've forgotten who it was who proposed simply allowing multiple  
pattern/guard
pairs on cases:

	case E
	  of P1 when E1 ;
	     P2 when E2 -> B2
	   ; P3 when E3 ;
	     P4 when E4 -> B4
	end

	f(P1...) when E1 ;
	f(P2...) when E2 -> B2;
	f(P3...) when E3 ;
	f(P4...) when E4 -> B4.

The syntax could be better, but this extension *does* satisfy all the  
use-cases
that anyone has actually mentioned wanting in a real program and  
*doesn't* need
major revisions to the compiler or virtual machine and *doesn't* turn  
clause
selection into an exponential-time horror.

There has also been mention of abstract patterns, which solve a lot of  
other
problems as well as this one, without introducing NP or exponential  
costs,
but does require rather more compiler work.