[erlang-questions] : documentation of data structures

[Raimo Niskanen]

On Tue, Dec 11, 2007 at 08:56:45AM +0100, Matej Kosik wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Lev Walkin wrote:
> > Matej Kosik wrote:
> >> -----BEGIN PGP SIGNED MESSAGE-----
> >> Hash: SHA1
> >>
> >> Andras Georgy Bekes wrote:
> >>
> >> (snip)
> >>
> >>> -queue: The doc doesn't say anything about the implementation, only:
> >>> "implements FIFO queues in an efficient manner".
> >>> It states that "all operations has an amortised O(1) running time",
> >>> except for some, that are "probably O(n)". This is rather vague.

Sorry about that :-( I will try to improve it if I get the time...

> >>>
> >>
> >> Check the implementation. You will reveal that the operations for
> >> adding/removing elements from/to
> >> the head/tail can have O(1) complexity in some cases but in some cases
> >> they will have O(n) complexity.
> >>

Adding and removing elements from head or tail is as concluded above
that is amortized O(1). queue:len/1 is O(n), queue:reverse/1 is O(1),
queue:join(Q1, Q2) should be O(len(Q1)) by reading the code
and queue:split/2 should be O(n) by reading the code.

Note that these time complexity estimates do not account for
garbage collection effects. Hopefully they are the same O()
so that e.g adding an element in the worst case is O(n) since
it has to reverse one list in one pass creating O(n) new list cells,
but also creating O(n) garbage list cells that later will 
affect a garbage collection with probably not more than O(n)...



> >> It would be particularly attractive, if someone implemented `queue'
> >> (with the same signature and
> >> semantics of operations) where those operations would have always O(1)
> >> complexity. That is, as I
> >> believe, impossible. Of course, queues can be implemented more
> >> efficiently, but in a different
> >> (non-functional-like) way.
> > 
> > 
> > Okasaki shows a way to have a queue with O(1) worst-case complexity.
> > However the constant factor is rather large. The queue ADT has O(1)
> > amortized complexity. In addition to that, it has a rather small
> > constant factor, so it'll be faster overall.
> > 

The erlang module 'queue' originates from an Okasaki queue implementation
that is small, neat, amortized O(1) with low overhead. If he (Okasaki)
has shown an O(1) worst-case that must be another creature.



> 
> In non-functional programming languages (also in Erlang) similar data-structure can be implemented
> with usual O(1) complexity without ``rather large'' constant factor. A different way of doing
> similar thing but it has different properties.
> - - it is more efficient
> - - it is outside functional programming paradigm
>   (no referential transparency, side effects etc.)
> Such implementation can be done in Erlang too.
> 
> I am not sure whether I understand why the above approach was not taken in Erlang. If mutable queues
> would be local to some process, no problems would arise. However, if one process wanted to pass a
> queue to another process, then if they tried to use them concurrently, interference could occur.
> With the original implementation, such interference is excluded. The penalty is that
> - - it is not the most efficient possible implementation
> - - equational reasoning cannot be applied
>   (other, more complicated, proof-techniques are necessary)
> A typical tradeoff.
> 
> However, if a queue would not be shared among processes than its mutable version would OK. Whouldn't it?

Even a mutable queue will have to appear non-mutable to different
function invocations in the same process.

To make a non-functional data type in Erlang would have to mean making
a new data type in the emulator. But every data type in Erlang must
act functional to the programmer, or be a new functional language
construct that the compiler hides all non-functional properties
from the programmer

There has for example been an attemt to make an array-like data type
called vector, wich would be destructive internally but have an
exception list to look functional from the outside. It did not
leave the prototype state due to efficiency problems
(and complexity d.o). Something called "write barrier" was missing
in the garbage collector to make it a bit better but not much...

However, writing a queue from the primitive functional types 
(lists and tuples) in the language is much simpler.
And that is what the module 'queue' is.



> - --
> Matej Kosik
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
> 
> iD8DBQFHXkK8L+CaXfJI/hgRAm42AJ41SmlQGrDmSnTE65g9gzeEiWzIfACgzreG
> 8SEpocgxu2NJHcZm5mQb7H8=
> =cfBQ
> -----END PGP SIGNATURE-----
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB