erlang sucks

[Ulf Wiger (TN/EAB)]

Alpár Jüttner skrev:
>> This is very different from allowing a subtle change in a complex
>> pattern match to shift evaluation from constant-time or linear
>> to NP - especially when programmers have learned to expect
>> and appreciate that pattern-matching is predictable in cost.
>
> Once again, please: NP does _not_ mean non-polynomial, but something
> very-very different. If you want to say "worse than polynomial" you can
> say "superpolynomial" or "exponential" (if the running time is indeed
> something like O(2^n)).

Oh, I thought it stood for Non-deterministic Polynomial Time.
Where was it claimed that it means non-polynomial?

BR,
Ulf W
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

> However, if pattern matchings are done one-by-one and left-to-right,
> then there is no performance problem. The union operator becomes less
> flexible in this case, but it is still quite useful.

> 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.

No.

My proposed pattern match -- with union -- is always deterministic. It
uses the first matching pattern found by a left-to-right
depth-first-search.

In the above example, {X,_} \/ {_,X} always matches X with the first
element. But matching {{a,b},b} with { {X,_} \/ {_,X}, X} matches the
second. It tries {X,_} first, succeeds, then tries matching b with a.
It fails, so backtracks and tries {_,X}.

Your proposed "one-by-one and left-to-right" method would fail when
matching {{a,b},b} with { {X,_} \/ {_,X}, X}.

They're completely different.

        Georgy
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Alpár Jüttner-2]

> Your proposed "one-by-one and left-to-right" method would fail when
> matching {{a,b},b} with { {X,_} \/ {_,X}, X}.

Exactly. But then the pattern matching would be fast and still useful in
many cases.

Alpar

>
> They're completely different.
>
> Georgy
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@...
> http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

> Oh, I thought it stood for Non-deterministic Polynomial Time.
> Where was it claimed that it means non-polynomial?
It was used in that sense.

If you think about it: X is (in) NP means a "good" thing: it means that
for solving X we have an algorithm that runs in exponential time,
however, there might be better algorithms.

In this thread, it was constantly used as something "bad". It was used
instead of NP-hard, which means it is very unlikely to find an algoritm
that runs in polynomial time.

The problem is probably NP complete, which means "is in NP" AND "is NP
hard".

        Georgy
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Alpár Jüttner-2]

On Tue, 2008-03-18 at 13:43 +0100, Ulf Wiger (TN/EAB) wrote:
> Alpár Jüttner skrev:
> >> This is very different from allowing a subtle change in a complex
> >> pattern match to shift evaluation from constant-time or linear
> >> to NP - especially when programmers have learned to expect
> >> and appreciate that pattern-matching is predictable in cost.
> > .
>
> Oh, I thought it stood for Non-deterministic Polynomial Time.
> Where was it claimed that it means non-polynomial?

You used it above in that sense. When you say that something is NP, it
does _not_ mean it is slow or difficult to solve. Easy problems (i.e.
those are solvable in constant or in linear time) are also in NP.

Also note that NP is an attribute of (decision) problems, not
algorithms. You cannot say that an algorithm is in NP. More exactly,
there are non-deterministic polynomial time algorithms, but they run on
an unrealistic abstract machine (called non-deterministic Turing
machine), thus they are not "algorithms" in the common sense.

Regards,
Alpar

>
> BR,
> Ulf W

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Alpár Jüttner-2]

> The problem is probably NP complete, which means "is in NP" AND "is NP
> hard".

Strictly speaking, an NP (and therefore an NP-complete) problem must be
a decision problem. So, if you want to check if a pattern matches (yes
or no answer), then your problem is NP-complete. If you want to find the
actual binding of the variables, then your problem is NP-hard. Anyway,
this doesn't matter too much: NP-hard is a good notation for everything,
and it expresses the fact, that it is _hopeless_ (but not proved to be
impossible!) to find a provable fast (i.e. polynomial) algorithm for the
problem.

Regards,
Alpar


> Georgy
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@...
> http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Ulf Wiger (TN/EAB)]

Andras Georgy Bekes skrev:
>> Oh, I thought it stood for Non-deterministic Polynomial Time.
>> Where was it claimed that it means non-polynomial?
> It was used in that sense.
>
> If you think about it: X is (in) NP means a "good" thing: it means that
> for solving X we have an algorithm that runs in exponential time,
> however, there might be better algorithms.
>
> In this thread, it was constantly used as something "bad".

In the context of pattern-matching, I thought exponential
time was pretty bad. The "there might be better algorithms"
part might be reason enough to keep the discussion going.  (:

It was mentioned in another post that pattern-matching is
atomic in the VM. That's correct - the VM will not schedule
another process while inside a pattern match (except, of
course, in the SMP version, where other schedulers might).

BR,
Ulf W
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

> 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.
Tested and seems true.

Check matchtest:test(50000).

So you can easily hang the whole Erlang VM by carefully building a huge
pattern match :-(
it doesn't even need much memory to do it.

        Georgy

-module(matchtest).

-export([test/1]).

tickloop()->
    io:format("Tick\n",[]),
    receive
        stop->
            ok
    after 500 ->
            tickloop()
    end.

test(N)->
    Tick=spawn_link(fun()->
                            tickloop()
                    end),
   
    AList=lists:duplicate(N,lists:seq(1,N)),
    BList=lists:duplicate(N,lists:seq(1,N)),
 
    io:format("Waiting for a while to see if tick works...\n",[]),
    receive
    after 3000 -> ok
    end,
    io:format("Matching...\n",[]),
    AList=BList,
   
    Tick ! stop,
    ok.

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Richard 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.


_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Richard 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.



_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Benjamin Tolputt]

I was going to stay out of this one (it being about Erlang internals
rather than Erlang distribution methods - my current interest); but I
have to pipe up on this one.

Any language that provides me with syntax/semantics (as opposed to
library functions) that I cannot estimate a time for is most definitely
a "Bad Thing". As Richard rightly points out, I can look at the
Fibonacci example you provided and SEE the issue there.

However, as I understand it, the pattern-matching change being asked for
(i.e. the one with backtracking) is a nasty idea as I cannot tell
anything about it's performance without know which one of the many
possible matching methods the current Erlang VM uses to establish it.
Combined with fact that there is an alternate proposal that satisfies
the requirements (as I see them) with known performance metrics and that
pattern-matching is atomic (meaning long matches stall other processes)
and I would rather this NOT be implemented.

Oh, and the prize for most eye-catching statement of the day goes to....

Richard A. O'Keefe wrote:
> but the student decided to get a sex change instead of a Masters.
>  


Regards,
B.J.Tolputt
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Robert Virding]

On 19/03/2008, Richard A. O'Keefe <ok@...> wrote:

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.

Those were the reasons that I suggested it, plus that guards are a part of pattern matching and should be directly connected to the patterns to which they refer. Also, it was an off the top of my head minimal syntax change so there is no doubt the syntax can be improved but I wouldn't make it to different or it could cloud the meaning.

Robert

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Alpár Jüttner-2]

> 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.

Hopefully not, because this is a wrong definition.

NP is a class of decision problems (yes or no answer). (A "problem" is
typically given as the set of problem instances for which the answer is
yes.)  For example, the graphs containing Hamiltonian cycles is in NP.
But if I tell you that "yes, the a graph contains a Hamiltonian cycle,
will you be able to check it? Probably not.

On the other hand: contrary to your definition, NP is not symmetric. If
a problem is NP, its negated version is not necessarily in NP. If fact,
if you can proof that both are NP, you can suspect that your problem is
actually in P.

The right (still intuitive) definition is this:
A problem is NP if for all 'yes' problem instance there exists a
certificate the help of which we can check/proof (in polynomial time),
that the answer is 'yes'.

A bit more precisely, the problem is in NP if there is a polynomial time
algorithm A that requires a problem instances I, and a certificate C as
input and
      * if the answer is 'yes' for I, there exists a certificate C for
        which A(I,C) answers 'yes', but
      * (we cannot be cheated) if the answer is 'no', then there cannot
        exists such an C.

This certificate is sometime very straightforward, sometimes it is not.
Two examples:
      * Hamiltonian cycles
              * It is in NP: if you give an H-cycles in the graph, it is
                a good certificate.
              * Is it in co-NP? We don't know, but probably not. Nobody
                knows a certificate that would prove that a graph has no
                Hamiltonian cycle.
      * Prime numbers
              * It is in co-NP: if you give a divisor of a number, than
                it will proof that the number is not prime (we can check
                in P that it is a real divisor).
              * Is it in NP? YES, but here the good certificate is not
                straightforward at all, it was invented in 1975 by
                Vaughan Pratt.
              * In fact, there exists a deterministic polynomial
                primality test algorithm called AKS-test, but it was
                invented only 2002.

>   NP is often used in a "vernacular" sense,
> meaning (real NP) \ P.

Never by those are familiar with the Complexity theory.

If you show me a single problem in (real NP) \ P, I shut up immediately.
But up to my knowledge, nobody could show such a problem, so it is more
than useless to use NP in this sense.

I still believe that this kind of misuse of NP is rooted in the
misconception that NP means non-polynomial. This kind of mistake is
typically taken quite seriously in an undergraduate course in Complexity
theory. It is something similar as if "I had six heads in line, so the
next one must be a tail because of the _theory_of_large_numbers_" were
said on an oral exam in Probabilistic theory.

To sum up:
      * If you want to say that a problem is not in P, say that. Non-P
        is not really longer that NP and it is correct.
      * If you want to say that "it is hopeless to find a polynomial
        time algorithm for solving is, because it is at least as hard to
        solve that any other NP problem", say that it is NP-hard (or
        NP-complete).

Best regards,
Alpar

>
> > 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.
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@...
> http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Kevin Scaldeferri]

Is it possible we can all agree this debate has reached a sufficient  
level of pedantry that those who really want to debate can take it off-
list?  It feels like people area being argumentative just for the sake  
of it.


On Mar 19, 2008, at 4:41 AM, Alpár Jüttner wrote:

>
>> 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.
>
> Hopefully not, because this is a wrong definition.
>
> ...
>
> The right (still intuitive) definition is this:
> A problem is NP if for all 'yes' problem instance there exists a
> certificate the help of which we can check/proof (in polynomial time),
> that the answer is 'yes'.

This, I believe, is precisely what was meant by the above.


>
>
>>  NP is often used in a "vernacular" sense,
>> meaning (real NP) \ P.
>
> Never by those are familiar with the Complexity theory.

The use of the term "vernacular" strongly suggests that he understands  
there is additional subtlety.


-kevin

PS - It seems to me that no-one has actually tried to debate the  
original assertion that such-and-such extension to pattern matching  
would turn it into an NP (hard) problem.  Instead everyone seems to  
have jumped on whether the OP understood what NP means or not.


_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Alpár Jüttner-2]

> Is it possible we can all agree this debate has reached a sufficient  
> level of pedantry that those who really want to debate can take it off-
> list?  It feels like people area being argumentative just for the sake  
> of it.

I didn't debate on anything.

I'm not an expert in Erlang, not even a professional software developer.
If I say something stupid about it or do a wrong assumption, the list
members kindly fix my error and I'm happy with it.

What happened now, is that someone who is not expert in the complexity
theory used a terminus technicus in a very wrong way, and I fixed it.

I apologize if it was too boring or annoying for you or for others.

Best regards,
Alpar

P.S. For me, it is at least a strange way of communication to comment a
post publicly and ask to continue it off-list at the same time.

>
>
> On Mar 19, 2008, at 4:41 AM, Alpár Jüttner wrote:
>
> >
> >> 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.
> >
> > Hopefully not, because this is a wrong definition.
> >
> > ...
> >
> > The right (still intuitive) definition is this:
> > A problem is NP if for all 'yes' problem instance there exists a
> > certificate the help of which we can check/proof (in polynomial time),
> > that the answer is 'yes'.
>
> This, I believe, is precisely what was meant by the above.
>
>
> >
> >
> >>  NP is often used in a "vernacular" sense,
> >> meaning (real NP) \ P.
> >
> > Never by those are familiar with the Complexity theory.
>
> The use of the term "vernacular" strongly suggests that he understands  
> there is additional subtlety.
>
>
> -kevin
>
> PS - It seems to me that no-one has actually tried to debate the  
> original assertion that such-and-such extension to pattern matching  
> would turn it into an NP (hard) problem.  Instead everyone seems to  
> have jumped on whether the OP understood what NP means or not.
>
>

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Richard O'Keefe]

I had a lengthy response to this, but sat on it for half an hour.
Alpár Jüttner is treating normally sloppy use of language (well,
not that normal for me, I blame it on the painkillers) as if it
were intended to be mathematically precise.  I don't feel that
any further debate on the subject is going to help anyone, so I'm
pulling out of the thread.

However, I would like to say that I have found a very neat way
to cast any instance of 3-sat as a pattern matching problem with
disjunctions.  Each clause turns into a disjunction of 7 tuple
patterns, each with the three variables and three wild-cards,
so the translation is not just polynomial, it's linear.

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[David-Sarah Hopwood]

Benjamin Tolputt wrote:
> Oh, and the prize for most eye-catching statement of the day goes to....
>
> Richard A. O'Keefe wrote:
>> but the student decided to get a sex change instead of a Masters.

Probably a lot more useful.

--
David-Sarah Hopwood
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Anders Dahlin]

The attached will help identifying those "bugs". The majority of the
code is about a decade old. During the years I've only added new
expressions as I have happened to use them. It may not cover all the
additions, but using the verbose flag will tell if it ignores an
expression.

Usage:
seqvar:check().
seqvar:check(DoFs).
seqvar:check(Options).
seqvar:check(DoFs, Options).

Where:
DoFs = Directory or File | List of Directories and/or Files

Options = [Option]

Option =
recurse - seqvar will recurse through sub directories.
verbose - seqvar will report if it ignores any expressions.
{incl, Fun()} - Include a file only if Fun(File) = true.
{excl, Fun()} - Exclude a file if Fun(File) = true.
{incldir, Fun()} - Include a directory only if Fun(Dir) = true.
{excldir, Fun()} - Exclude a directory if Fun(Dir) = true.
{inclvar, Fun()} - Include a variable only if Fun(Var) = true. Var is an
atom.
{exclvar, Fun()} - Exclude a variable if Fun(Var) = true. Var is an atom.

If DoFs is omitted, the current directory will be used.


Examples:

  4> seqvar:check("foo.erl", [verbose]).
Checking file "foo.erl"
Line 25: Usage of 'T2', expected 'T4'
Line 32: Usage of 'B1', expected 'B3'
Line 46: Usage of 'Foo1', expected 'Foo2'
Line 47: Usage of 'Baz1', expected 'Baz2'


%% Exclude all variables starting with T
5> F = fun (V) -> case atom_to_list(V) of "T" ++ _ -> true; _ -> false
end end.

6> seqvar:check("foo.erl", [{exclvar, F}, verbose]).
Checking file "foo.erl"
Line 32: Usage of 'B1', expected 'B3'
Line 46: Usage of 'Foo1', expected 'Foo2'
Line 47: Usage of 'Baz1', expected 'Baz2'


Happy checking - no warranties!
/Anders


attila.rajmund.nohl@... wrote:

> On Mon, 17 Mar 2008, Kevin Scaldeferri wrote:
>
>> On Mar 17, 2008, at 6:31 AM, Jani Hakala wrote:
>>
>>> attila.rajmund.nohl@... writes:
>>>
>>>> I don't think that immutable variables make it easier to write less
>>>> buggier code. On the contrary, I often see code like this:
>>>>
>>>> HR1=f(HugeRecord),
>>>> ...
>>>> g(HR1).
>>>>
>>>> Then someone adds a line to modify the HugeRecord and forgets to
>>>> update
>>>> the call to 'g':
>>>>
>>>> HR1=f(HugeRecord),
>>>> HR2=f2(HR1),
>>>> ...
>>>> g(HR1).
>>>>
>>>> Now we have a stupid bug.
>>>>
>>> The compiler would warn about that
>>>    Warning: variable 'HR2' is unused
>> These examples always feel like people are insisting on writing
>> imperative code in a functional language.  Why not:
>>
>> HR1 = f2(f(HugeRecord)),
>> ...
>> g(HR1)
>
> Because this is a mock-example, the real code looks more like
>
> HR1=HugeRecord#hugeRecordType{someField=SomeValue}
> ... code uses HR1
> HR2=HR1#hugeRecordType{someOtherField=SomeOtherValue}
> ...
> g(HR1), % forgot to update variable name
> h(HR2). % didn't forget to update variable name
>
> In this case the compiler won't save my a**. I see this kind of code
> change all the time. Every week I see a checkin which only fixes a
> variable name that wasn't updated, so this is not exactly a rare bug.
>
>   Bye,NAR

%%%----------------------------------------------------------------------------
%%% File    : seqvar.erl
%%% Author  : Anders Dahlin
%%% Purpose : Check to see if variables is handled in sequence
%%% Created : 28 Mar 2008 by Anders Dahlin
%%%----------------------------------------------------------------------------

-module(seqvar).
-author('Anders Dahlin').
-vsn("1.1").

-export([check/0, check/1, check/2]).

-include_lib("kernel/include/file.hrl").

-record(opts, {incl     = nil,
               excl     = nil,
               incldir  = nil,
               excldir  = nil,
               inclvar  = nil,
               exclvar  = nil,
               recurse  = false,
               verbose  = false
              }).

-define(default_dirs, []).


%%------------------------------------------------------------------------------
%% Func    : check/0, 1, 2
%%
%% Purpose : Main function. Initiates what should be checked
%%
%% Args    : Arg         : DoFs or Options, see below
%%           DoFs        : Path()
%%                         Path to current file (might be header file)
%%           Options     : List()
%%                         Option list, will be handled by fix_opts
%%
%% Returns : void()
%%------------------------------------------------------------------------------

check() ->
    check([]).

check(Arg) ->
    case Arg of
        [X| _Rest] when atom(X); tuple(X) -> % Arg = options
            {ok, Cwd} = file:get_cwd(),
            check(Cwd, Arg);
        _Other ->
            check(Arg, []) % Arg = dir|file
    end.

check(DoFs, Options)->
    Opts       = fix_opts(Options),
    Files      = get_files(DoFs, Opts),
    OrgPath    = code:get_path(),
    OtpSrcPath = ebin_to_src(OrgPath),
    Includes   = ?default_dirs ++ OtpSrcPath,
    check_files(Files, Opts, Includes).


%%------------------------------------------------------------------------------
%% Func    : check_files/3
%%
%% Purpose : Main function. Initiates what should be checked
%%
%% Args    : Files       : [Path()]
%%                         List of files to be checked
%%           Opts        : #opts{}
%%           Includes    : Files to include in the check
%%
%% Returns : void()
%%------------------------------------------------------------------------------

check_files([File| Rest], Opts, Includes) ->
    io:format("Checking file ~p\n", [File]),
    case epp:open(File, [filename:dirname(File)| Includes], []) of
        {ok, Epp} ->
            parse_file(Epp, File, Opts),
            epp:close(Epp);
        Error ->
            io:format("Unable to open ~s due to ~p", [File, Error])
    end,
    io:nl(),
    check_files(Rest, Opts, Includes);
check_files([], _Opts, _Includes) ->
    done.
   

%%------------------------------------------------------------------------------
%% Func    : parse_file/2
%%
%% Purpose : Parse the module abstract form by abstract form
%%
%% Args    : Epp         : File descriptor of a file opened for parsing
%%           CF          : Path()
%%                         Path to current file (might be header file)
%%           Opts        : #opts{}
%%
%% Returns : void()
%%------------------------------------------------------------------------------

parse_file(Epp, CF, Opts) ->
    case epp:parse_erl_form(Epp) of
        {ok, AbsForm} ->
            NewCF = parse_abs_form(AbsForm, CF, Opts),
            parse_file(Epp, NewCF, Opts);
        {eof, _} ->
            ok;
        {error, Error} ->
            io:format("Unable to parse ~s due to ~p", [CF, Error]),
            parse_file(Epp, CF, Opts) % correct?
    end.


%%------------------------------------------------------------------------------
%% Func    : parse_abs_form/2
%%
%% Purpose : Parse an absolute erlang form
%%
%% Args    : AbsForm     : Absolute form returned by epp:parse_erl_form
%%           CF          : see parse_file/2
%%           Opts        : see parse_file/2
%%
%% Returns : Path()
%%------------------------------------------------------------------------------

parse_abs_form({attribute, _L, Attribute, Value}, CF, _Opts) ->
    attribute(Attribute, Value, CF);

parse_abs_form({function, _L, F, A, Clauses}, CF, Opts) ->
    func(F, A, Clauses, Opts),
    CF;

parse_abs_form(_AbsForm, CF, _Opts) -> % ignoring others
    CF.


%%------------------------------------------------------------------------------
%% Func    : attribute/3
%%
%% Purpose : Parse an attribute. Only file attributes are handled.
%%           All others are disregarded.
%% Args    : Attribute   : Atom()
%%                         file | export | import | compile | Atom()
%%           Value       : Term()
%%           CF          : see parse_file/2
%%
%% Returns : Path()
%%------------------------------------------------------------------------------

%% Handle the file attribute
attribute(file, {NewCF, _L}, _CF) ->
    filename:absname(NewCF);

%% Disregard all other attributes
attribute(_Attribute, _Value, CF) ->
    CF.


%%------------------------------------------------------------------------------
%% Func    : func/4
%%
%% Purpose : Parse a function
%%
%% Args    : F           : Atom() - function
%%           A           : Int() - arity
%%           Clauses     : List()
%%           Opts        : see parse_file/2
%%
%% Returns : void
%%------------------------------------------------------------------------------

func(_F, _A, Clauses, Opts) ->
    clauses(Clauses, Opts).


%%------------------------------------------------------------------------------
%% Func    : clauses/2
%%
%% Purpose : Parse a list of function clauses.
%%
%% Args    : Clauses     : List()
%%                         [{clause, Line, Parameters, Guards, Body},...]
%%           Opts        : see parse_file/2
%%
%% Returns : void()
%%------------------------------------------------------------------------------

%% function clauses
clauses([{clause, _L, _P, _G, B} | Clauses], Opts) ->
    %% Not needed to check the head or the guards?
    %% Vars = sequence(P, [], Opts), % check parameters (head)
    sequence(B, [], Opts), % check body
    clauses(Clauses, Opts);
       
clauses([], _Opts) ->
    void.

%%------------------------------------------------------------------------------
%% Func    : sequence/3
%%
%% Purpose : Parse a sequence of expressions
%%
%% Args    : Sequence    : List()
%%                         [Expression, ...]
%%           Vars        : List() - [{Var1, Seq1}, ..., {VarN, SeqN}]
%%           Opts        : see parse_file/2
%%
%% Returns : Vars
%%------------------------------------------------------------------------------

sequence([Expressions | Rest], Vars, Opts) when list(Expressions) ->
    NewVars = sequence(Expressions, Vars, Opts),
    sequence(Rest, NewVars, Opts);

sequence([Expression | Rest], Vars, Opts) ->
    NewVars = expression(Expression, Vars, Opts),
    sequence(Rest, NewVars, Opts);

sequence([], Vars, _Opts) ->
    Vars.


%%------------------------------------------------------------------------------
%% Func    : fric_clauses/3
%%
%% Purpose : Parse a list of fun/receive/if/case/try clauses.
%%
%% Args    : Clauses     : List()
%%                         [{clause, Line, Parameters, Guards, Body},...]
%%           Vars        : see sequence/3
%%           Opts        : see parse_file/2
%%
%% Returns : Vars
%%------------------------------------------------------------------------------

fric_clauses(Clauses, Vars, Opts) ->
    fric_clauses(Clauses, Vars, Opts, []).
                                         
fric_clauses([{clause, _L, P, G, B} | Clauses], Vars, Opts, AllVars) ->
    NewVars1 = sequence(P, Vars, Opts), % check parameters
    guards(G, NewVars1, Opts), % check guards
    NewVars2 = sequence(B, NewVars1, Opts), % check body
    fric_clauses(Clauses, Vars, Opts, [NewVars2| AllVars]);
fric_clauses([], _Vars, _Opts, AllVars) ->
    comm(AllVars). % get vars common to all clauses


%%------------------------------------------------------------------------------
%% Func    : guards/3
%%
%% Purpose : Parse a list of guard expressions
%%
%% Args    : Guards      : List()
%%                         [Expression, ...]
%%           Vars        : see sequence/3
%%           Opts        : see parse_file/2
%%
%% Returns : Vars
%%------------------------------------------------------------------------------

guards([Expressions | Rest], Vars, Opts) when list(Expressions) ->
    guards(Expressions, Vars, Opts),
    guards(Rest, Vars, Opts);

guards([Expression | Rest], Vars, Opts) ->
    expression(Expression, Vars, Opts),
    guards(Rest, Vars, Opts);

guards([], Vars, _Opts) ->
    Vars.


%%------------------------------------------------------------------------------
%% Func    : expression/3
%%
%% Purpose : Parse an expression
%%
%% Args    : Expression  : Tuple()
%%           Vars        : see sequence/3
%%           Opts        : see parse_file/2
%%
%% Returns : Vars
%%------------------------------------------------------------------------------

expression({call, _Line, Call, Parameters}, Vars, Opts) ->
    NewVars = expression(Call, Vars, Opts),
    sequence(Parameters, NewVars, Opts);
   
expression({cons, _Line, Head, Tail}, Vars, Opts) ->
    NewVars = expression(Head, Vars, Opts),
    expression(Tail, NewVars, Opts);
   
expression({tuple, _Line, Expressions}, Vars, Opts) ->
    sequence(Expressions, Vars, Opts);
   
expression({'if', _Line, Clauses}, Vars, Opts) ->
    fric_clauses(Clauses, Vars, Opts);
   
expression({'case', _Line, Expression, Clauses}, Vars, Opts) ->
    NewVars = expression(Expression, Vars, Opts),
    fric_clauses(Clauses, NewVars, Opts);

expression({'receive', _Line, Clauses}, Vars, Opts) ->
    fric_clauses(Clauses, Vars, Opts);

expression({'receive', _Line, Clauses, T1, T2}, Vars, Opts) ->
    Vars1 = expression(T1, Vars, Opts),
    Vars2 = sequence(T2, Vars1, Opts),
    fric_clauses(Clauses, Vars2, Opts);

expression({arith, _, _Operator, Left, Right}, Vars, Opts) ->
    Vars1 = expression(Left, Vars, Opts),
    expression(Right, Vars1, Opts);
expression({arith, _, _Operator, Expression}, Vars, Opts) ->
    expression(Expression, Vars, Opts);

expression({match, _, Left, Right}, Vars, Opts) ->
    Vars1 = expression(Right, Vars, Opts),
    expression(Left, Vars1, Opts); % will this work?

expression({block, _, Expression}, Vars, Opts) ->
    expression(Expression, Vars, Opts);

expression({'catch', _, Expression}, Vars, Opts) ->
    expression(Expression, Vars, Opts);

expression({send, _, Receiver, Message}, Vars, Opts) ->
    Vars1 = expression(Receiver, Vars, Opts),
    expression(Message, Vars1, Opts);

%% This is where the actual checking starts!
expression({var, L, Var}, Vars, Opts) ->
    parameter(Var, L, Vars, Opts);

expression({record, _, _, Record}, Vars, Opts) when list(Record) ->
    sequence(Record, Vars, Opts);
expression({record, _, Expression, _, Record}, Vars, Opts) when list(Record) ->
    Vars1 = expression(Expression, Vars, Opts),
    sequence(Record, Vars1, Opts);

expression({record_field, _L, _, Expression}, Vars, Opts) ->
    expression(Expression, Vars, Opts);

expression({record_field, _L, Var, _F, Expression}, Vars, Opts) ->
    Vars1 = expression(Var, Vars, Opts),
    expression(Expression, Vars1, Opts);

expression({record_index, _L, _, _}, Vars, _Opts) ->
    Vars;

expression({op, _L, _Op, Expr1, Expr2}, Vars, Opts) ->
    Vars1 = expression(Expr1, Vars, Opts),
    expression(Expr2, Vars1, Opts);

expression({op, _L, _Op, Expr}, Vars, Opts) ->
    expression(Expr, Vars, Opts);

expression({lc, _, Expr1, Expr2}, Vars, Opts) ->
    Vars1 = expression(Expr1, Vars, Opts),
    sequence(Expr2, Vars1, Opts);
   
expression({generate, _, Expr1, Expr2}, Vars, Opts) ->
    Vars1 = expression(Expr1, Vars, Opts),
    expression(Expr2, Vars1, Opts);
   
expression({remote, _, Expr1, Expr2}, Vars, Opts) ->
    Vars1 = expression(Expr1, Vars, Opts),
    expression(Expr2, Vars1, Opts);

expression({'fun', _, {clauses, Clauses}}, Vars, Opts) ->
    fric_clauses(Clauses, Vars, Opts);

expression({'fun', _L, _}, Vars, _Opts) ->
    Vars;

expression({'query', _, Expr}, Vars, Opts) ->
    expression(Expr, Vars, Opts);

expression({atom, _L, _Atom}, Vars, _Opts) ->
    Vars;

expression({integer, _L, _Int}, Vars, _Opts) ->
    Vars;

expression({float, _L, _Float}, Vars, _Opts) ->
    Vars;

expression({string, _L, _String}, Vars, _Opts) ->
    Vars;

expression({char, _L, _Char}, Vars, _Opts) ->
    Vars;

expression({bin, _L, _Bin}, Vars, _Opts) ->
    Vars;

expression({nil, _L}, Vars, _Opts) ->
    Vars;

expression({'try', _L, Call, Clauses, Exceptions, After}, Vars, Opts) ->
    Vars1 = sequence(Call, Vars, Opts),
    Vars2 = fric_clauses(Clauses, Vars1, Opts),
    Vars3 = fric_clauses(Exceptions, Vars1, Opts),
    Vars4 = comm([Vars2, Vars3]),
    sequence(After, Vars4, Opts),
    Vars4;

expression(BeginEnd, Vars, Opts) when is_list(BeginEnd) ->
    sequence(BeginEnd, Vars, Opts);

expression(Expr, Vars, Opts) ->
    case Opts#opts.verbose of
        true when is_tuple(Expr) ->
            io:format("Line ~w: unhandled expression ~p~n", [element(2, Expr), Expr]);
        true ->
            io:format("unhandled expression ~p~n", [Expr]);
        _ ->
            ok
    end,
    Vars.


%%------------------------------------------------------------------------------
%% Func    : parameter/4
%%
%% Purpose : Check a variable and report if it's used out of sequence
%%
%% Args    : Var         : Atom()
%%                         The variable
%%           L           : Integer()
%%                         Line number
%%           Vars        : see sequence/3
%%           Opts        : see parse_file/2
%%
%% Returns : Vars
%%------------------------------------------------------------------------------
parameter(Var, L, Vars, Opts) ->
    case include(Var, {Opts#opts.inclvar, Opts#opts.exclvar}) of
        true ->
            {V, NewS} = parse_var(Var),
            case lists:keysearch(V, 1, Vars) of
                {value, {_, NewS}} ->
                    Vars;
                {value, {_, -1}} ->
                    lists:keyreplace(V, 1, Vars, {V, NewS});
                {value, {_, OldS}} when NewS > OldS ->
                    lists:keyreplace(V, 1, Vars, {V, NewS});
                {value, {_, OldS}} -> % using old var
                    io:format("Line ~p: Usage of ~p, expected ~p~n",
                              [L, frmt_var({V, NewS}), frmt_var({V, OldS})]),
                    Vars;
                false ->
                    [{V, NewS}| Vars]
            end;
        false ->
            Vars
    end.

parse_var(VarIn) ->
    parse_var(lists:reverse(atom_to_list(VarIn)), []).

parse_var([H| T], Seq) when H >= 48, H =< 57 ->
    parse_var(T, [H| Seq]);
parse_var(RevVar, []) ->
    {lists:reverse(RevVar), -1};
parse_var([], Seq) ->
    {Seq, -1};
parse_var(RevVar, Seq) ->
    {lists:reverse(RevVar), list_to_integer(Seq)}.
                             

frmt_var({Var, -1}) ->
    list_to_atom(Var);
frmt_var({Var, Seq}) ->
    list_to_atom(lists:concat([Var, Seq])).


%%------------------------------------------------------------------------------
%% Utility functions
%%------------------------------------------------------------------------------

%% Convert paths which ends in ebin to src
ebin_to_src(PathList) ->
     F = fun(P) ->
                 case filename:basename(P) of
                     "ebin" ->
                         filename:join(filename:dirname(P), "src");
                     _ ->
                         P
                 end
         end,
    lists:map(F, PathList).


%%% get_files(DoFs, Opts) where DoFs is a list of directories and files
%%% or a directory or file. get_files will list all files in the specified
%%% directories and also traverse sub directories if the recurse option is set.
%%% Include only .erl files for which Incl(File) returns true
%%% and Excl(File) returns false. If the recurse option is set
%%% get_files will traverse all sub directories.

get_files([DoF| Rest], Opts) when list(DoF); atom(DoF) ->
    get_files(DoF, Opts) ++ get_files(Rest, Opts);
get_files(InDoF, Opts) ->
    DoF = coerce2list(InDoF),
    #opts{incl    = Incl,
          excl    = Excl,
          incldir = InclDir,
          excldir = ExclDir,
          recurse = Recurse} = Opts,
    FileFuns = {Incl, Excl},
    DirFuns  = {InclDir, ExclDir},
    case type(DoF) of
        file ->
            case include(DoF, FileFuns) of
                true ->
                    [DoF];
                false ->
                    []
            end;
        dir ->
            case include(DoF, DirFuns) of
                true ->
                    list_dir(DoF, {FileFuns, DirFuns}, Recurse, []);
                false ->
                    []
            end;
        _Other ->
            []
    end.


list_dir(Dir, IEFuns, Recurse, AllFiles) ->
    {Dirs, Files} = list_dir(Dir, IEFuns),
    case Recurse of
        true ->
            list_dirs(Dirs, IEFuns, Recurse, AllFiles ++ Files);
        false ->
            AllFiles ++ Files
    end.

list_dirs([Dir | Dirs], IEFuns, Recurse, AllFiles) ->
    NewAllFiles = list_dir(Dir, IEFuns, Recurse, AllFiles),
    list_dirs(Dirs, IEFuns, Recurse, NewAllFiles);
list_dirs([], _IEFuns, _Recurse, AllFiles) ->
    AllFiles.


list_dir(Dir, IEFuns) ->
    {ok, Content} = file:list_dir(Dir),
    extract(Content, Dir, IEFuns, [], []).


extract([DoF | Content], Dir, Funs, Files, Dirs) ->
    case include(DoF, Dir, Funs) of
        {dir, PathDoF} ->
            extract(Content, Dir, Funs, Files, [PathDoF| Dirs]);
        {file, PathDoF} ->
            extract(Content, Dir, Funs, [PathDoF| Files], Dirs);
        false ->
            extract(Content, Dir, Funs, Files, Dirs)
    end;
extract([], _Dir, _Funs, Files, Dirs) ->
    {lists:reverse(Dirs), lists:reverse(Files)}.

include(DoF, Dir, {FileFuns, DirFuns}) ->
    PathDoF = filename:join(Dir, DoF),
    case type(PathDoF) of
        file ->
            case filename:extension(DoF) of
                ".erl" ->
                    case include(PathDoF, FileFuns) of
                        true ->
                            {file, PathDoF};
                        false ->
                            false
                    end;
                _SomethingElse ->
                    false
            end;
        dir ->
            case include(PathDoF, DirFuns) of
                true ->
                    {dir, PathDoF};
                false ->
                    false
            end;
        _Other ->
            false
    end.


type(#file_info{type=directory}) -> dir;
type(#file_info{type=regular})   -> file;
type(#file_info{type=Type})      -> Type;
type(DoF) when list(DoF); atom(DoF) ->
    case file:read_file_info(DoF) of
        {ok, FileInfo} ->
            type(FileInfo);
        Error ->
            Error
    end;
type(Error) -> {error, Error}.

coerce2list(X) when atom(X) ->
    atom_to_list(X);
coerce2list(X) ->
    X.


%%% fix_opts will scan a list of options and set the appropriate
%%% fields in the opts record which will be used later in the
%%% code. Options appearing before others in the list has precedence

fix_opts(Options) when record(Options, opts) ->
    Options;
fix_opts(Options) ->
    fix_opts(lists:reverse(Options), #opts{}).


fix_opts([Option| Options], Opts) ->
    NewOpts =
        case Option of
            rec            -> Opts#opts{recurse = true};
            recurse        -> Opts#opts{recurse = true};
            recursive      -> Opts#opts{recurse = true};
            {incl,    Fun} -> Opts#opts{incl    = Fun};
            {excl,    Fun} -> Opts#opts{excl    = Fun};
            {incldir, Fun} -> Opts#opts{incldir = Fun};
            {excldir, Fun} -> Opts#opts{excldir = Fun};
            {inclvar, Fun} -> Opts#opts{inclvar = Fun};
            {exclvar, Fun} -> Opts#opts{exclvar = Fun};
            verbose        -> Opts#opts{verbose = true};
            Option         -> Opts
        end,
   
    fix_opts(Options, NewOpts);
fix_opts([], Opts) ->
    Opts.


%% default excludes
%% exclude(AbsDir) ->
%%     Dir = filename:basename(AbsDir),
%%     case Dir of
%% "lost+found" ->
%%    true;
%% Dir ->
%%    case string:to_upper(lists:reverse(Dir)) of
%% "KAB." ++ _ -> % ends with .BAK
%%    true;
%% "DLO." ++ _ -> % ends with .OLD
%%    true;
%% _Other ->
%%    false
%%    end
%%     end.

%% include or exclude something
include(_Cand, {nil, nil}) ->
    true;
include(Cand, {Incl, nil}) ->
    Incl(Cand);
include(Cand, {nil, Excl}) ->
    not(Excl(Cand));
include(Cand, {Incl, Excl}) ->
    Incl(Cand) and not(Excl(Cand)).


%% comm returns the intersection of a list of lists
comm([L1, L2| Lists]) ->
    Comm = common(lists:sort(L1), lists:sort(L2)),
    comm([lists:sort(L) || L <- Lists], Comm);
comm(Lists) ->
    Lists.

comm([L1| Lists], Comm) ->
    comm(Lists, common(L1, Comm));
comm([], Comm) ->
    Comm.

%% assumes sorted lists
common(L1, L2) ->
    common(L1, L2, []).
common([E| L1], [E| L2], Res) ->
    common(L1, L2, [E| Res]);
common([E1| L1], [E2| L2], Res) when E1 < E2 ->
    common(L1, [E2| L2], Res);
common([E1| L1], [_E2| L2], Res) ->
    common([E1| L1] , L2, Res);
common(_, _, Res) ->
    lists:reverse(Res).

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions