[erlang-questions] per function/process locals

[ok]

On 2 May 2007, at 11:21 pm, Ulf Wiger (TN/EAB) wrote
[that instead of doing]
> init_state(L) ->
>   lists:foldl(
>     fun({a, A}, S) -> S#st{a = A};
>        ({b, B}, S) -> S#st{b = B};
>        ...
>     end, #st{}, L).
[he tends to do]
>   [A, B, C, D] =
>     [proplists:get_value(K,L) ||
>       K <- [a, b, c, d]],
>   #st{a = A, b = B, c = C, d = D}

This is a rather interesting example, because it shows a clear trade- 
off.
Suppose there are V "variables".  We expect that the list will contain
each at most once; the worst case is when they all appear.

The first algorithm does one pass -- O(V) work for traversal -- building
a new record (memory size V+2 words at least) on each iteration, for a
total of O(V**2) time and O(V**2) space turned over.
The second algorithm does V passes -- O(V**2) work for traversal -- but
each pass builds only a single cons cell -- O(V) space --.  For large V,
it is better to sort the list L -- O(V.lg V) time and space -- and then
do a merge -- O(V) time and space --.  This is basically what
list_to_frame/1 does in my "frames" proposal (which is not entirely
unlike Joe Armstrong's "proper structs").  See
http://www.cs.otago.ac.nz/staffpriv/ok/frames.pdf
for details.

It would be interesting to see more examples where people want "many"
"variables" in a loop, to discover whether they could be handled in the
source language by multiple loops each working with fewer variables.
If so, compiler support for loop fusion (which would be a very nice
thing to have anyway) might do more for us than special syntax.