You are viewing lukego

Luke's Weblog - The small matter of errors [entries|archive|friends|userinfo]
Luke Gorrie

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

The small matter of errors [Jun. 3rd, 2007|10:17 am]
Previous Entry Share Next Entry
[Tags|, ]

I originally wrote this as an email to Bill Clementson but I decided to post it here too.

Lately there are some Erlang implementations of parallel-map floating around the internet and I just noticed that they don't exhibit satisfactory behaviour in the presence of errors. To see why let's start with an example of the right way for such a function to treat errors:

  lists:map(fun(N) -> 1/N end, [3,2,1,0]).
.. which will neatly raise a division-by-zero exception from the lists:map/2 call. I'd say that it's a bug for a parallel version of map to behave any different.

The version in Joe Armstrong's new book has the bug of using an implicit catch (defensive programming!) to sweep errors under the rug by converting them into return values:

  > pmap(fun(N) -> 1/N end, [3,2,1,0]).
  [0.333333,
   0.500000,
   1.00000,
   {'EXIT',{badarith,[{erl_eval,eval_op,3},{parmap,do_f,4}]}}]

And my own concise implementation:

  pmap(F, L) ->
      Parent = self(),
      [receive {Pid, Result} -> Result end
       || Pid <- [spawn(fun() -> Parent ! {self(), F(X)} end) || X <- L]].
.. is worse because it will hang forever: the child terminates without sending the result and the parent never detects this. (Unfortunately we can't just change spawn to spawn_link because it won't help when the parent is trapping exits.)

I wouldn't say that either is very suitable for use in real programs.

So let's put things right and try to write a proper production-quality implementation of parallel-map that follows lists:map/2 as closely as possible. Here is my new version:

  pmap(F,List) ->
      [wait_result(Worker) || Worker <- [spawn_worker(self(),F,E) || E <- List]].

  spawn_worker(Parent, F, E) ->
      erlang:spawn_monitor(fun() -> Parent ! {self(), F(E)} end).

  wait_result({Pid,Ref}) ->
      receive
	  {'DOWN', Ref, _, _, normal} -> receive {Pid,Result} -> Result end;
	  {'DOWN', Ref, _, _, Reason} -> exit(Reason)
      end.
Now let's go forth and write parallel programs!
LinkReply

Comments:
From: (Anonymous)
2007-06-03 08:12 pm (UTC)

Armstrong Book

(Link)

Hello,

Have you read the PDF of Armstrong's new book and reported any bugs or made other recommendations that might make it into the final published version?

I'm just curious, because I'm hoping to learn Erlang from the book and I'm scared of picking up bad habits without knowing that I'm doing so...and I know how easy it is to overlook your own mistakes (even if you are Joe Armstrong.)

Thanks,

devmail@runbox.com
[User Picture]From: lukego
2007-06-03 08:48 pm (UTC)

(Link)

My advice is not to worry too much! I learned Erlang from Joe too and I don't reckon you can find a better teacher. Just remember that sometimes the code presented in books and weblogs has been oversimplified a bit to make it more presentable. :-)
From: (Anonymous)
2007-06-04 04:12 am (UTC)

spawn_monitor

(Link)

Might be worthwhile to note that spawn_monitor is only available on a recent release of Erlang. I'm not sure if any releases before R11B-4 have it. - Bill
[User Picture]From: darius
2007-06-04 04:37 pm (UTC)

(Link)

If just the last of the calls crashes, this waits on all the preceding results before ignoring them and propagating the error, I think. (Assuming the list comprehension with the wait_result's is evaluated left-to-right.) Would it be worthwhile to propagate it immediately? Seems like arranging that would complicate this nice pretty code with an intermediate table that'd have to get sorted back into a result list if there was no error.

BTW examining this made me realize that even the self() BIF breaks capability discipline, at least from one point of view. (It's of course OK if you only treat whole processes as the units of analysis.)
[User Picture]From: lukego
2007-06-04 06:13 pm (UTC)

(Link)

Good catch! This makes me reflect that the ideal is for the whole pmap process tree to be linked but without getting messed up if the caller trapping exits. This can be arranged by adding a new intermediary/coordinator process that links with all the workers and is monitored by the caller. How about this for a generic utility for such cases:
%% Evaluate F in a new process and return the result / exception.
spawn_eval(F) ->
    Parent = self(),
    {Pid,Ref} = erlang:spawn_monitor(fun() -> Parent ! {self(), F()} end),
    receive
        {'DOWN', Ref, _, _, normal} -> receive {Pid,Result} -> Result end;
        {'DOWN', Ref, _, _, Reason} -> exit(Reason)
    end.
and for a happy ending we can now reinstate Bill's favourite brainfucking list comprehension :-)
pmap(F, L) ->
    spawn_eval(fun() -> pmap_link(F, L) end).

pmap_link(F, L) ->
    Parent = self(),
    [receive {Pid, Result} -> Result end
     || Pid <- [spawn_link(fun() -> Parent ! {self(), F(X)} end) || X <- L]].
Hurray!

P.S. One day you'll have to make me see why you're so interested in capability security. To me it seems like such fine granularity is only interesting for programs don't grow into some kind of confusing tangled web - but that seems to be exactly what most programs do.

[User Picture]From: darius
2007-06-04 07:56 pm (UTC)

(Link)

Nice! I'll have to try this out.

I'll post something on capabilities here sometime. Maybe I'm not qualified to answer -- I hate programs that do that.
[User Picture]From: lukego
2007-06-04 08:24 pm (UTC)

(Link)

Or perhaps my real concern is that perfectly reasonable programs will feel confusing and tangled if you add in such fine-grained concerns as capabilities. Like the way I can printf at will unless we throw in Monads and then it suddenly becomes an unfortunately big deal. Or maybe I just don't feel the motivation strongly enough. Or..
From: (Anonymous)
2008-08-07 09:21 pm (UTC)

Re: capabilities

(Link)

good questions. i don't have the answer, but i've been lurking on the captalk mailing list trying to slowly learn through osmosis. you might ask there or similar places, i would also be very interested in the answers you might get :-)

http://www.nabble.com/Capability-System-f581.html
From: (Anonymous)
2007-06-05 05:47 am (UTC)

(Link)

> and for a happy ending we can now reinstate Bill's favourite brainfucking
> list comprehension :-)

Yay!!

- Bill