fun complexity analysis (Re: non-Erlang Erlang grammars)

Thomas Lindgren <>
Mon Oct 23 13:07:29 CEST 2000

> - no message passing
> - no external function calls
> - no loops
> - no operations that are not known to be O(1)
> These functions could then be used in match filters (perhaps even
> guards!) and action specifications in, e.g., a trace filter
> specification.

Note that there is at least one guard that is not O(1), length/1.
Also nodes/1, I guess.

All of the above properties are straightforward to verify (you need a
table of O()-properties for BIFs). One shouldn't permit use of
apply/spawn/spawn_link/F(X) in all their varieties either.

Put (and get?) are out as well. In short, all side-effect operations.

What about exceptions? For user-defined guards, one could wrap the
operation in an "exception => fail" construct as in Core Erlang.
For other operations (such as ets:foldl()), it might not be a problem.

Thomas Lindgren					
Alteon Websystems Sweden

More information about the erlang-questions mailing list