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

[Ulf Wiger]

On Mon, 23 Oct 2000, Ulf Wiger wrote:

>Also, when speaking of foldl-type operations on ets tables, it would
>be really nice if one could write a fun in Erlang which i guaranteed
>to be O(1), and thus could be executed efficiently by the VM in an
>ets:foldl().

Not being a compiler writer, perhaps I don't realise the problems
associated with this, but shouldn't it be rather straightforward to
verify that a fun has the following properties:

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

(Lifting the message passing restriction, it would also be nice to be
able to require that event handlers have these characteristics - and
subsequently, I would be able to call a fun in a way that I get an
exception if the fun is not _known_ to be an O(1) fun. This could
perhaps be done using the "annotation" syntax in Core Erlang?)

/Uffe
-- 
Ulf Wiger                                    tfn: +46  8 719 81 95
Strategic Product & System Management        mob: +46 70 519 81 95
Ericsson Telecom AB,              Datacom Networks and IP Services
Varuvägen 9, Älvsjö,                    S-126 25 Stockholm, Sweden