Hivemind Blog

Ah, yes. Erlang. The language that lets you do:
perms([]) -> [[]];
perms(L) -> [[H|T] || H < - L, T <- perms(L--[H])].

I spent most of my weekend going through Joe Armstrongs Programming Erlang which as an excercise contains the following:

Write a ring benchmark. Create N processes in a ring. Send a mes-
sage round the ring M times so that a total of N * M messages get
sent. Time how long this takes for different values of N and M.

I actually had the biggest problems with creating the ring. See, you can easily set up a ring datastructure, but each node should be a process and so each node should point to the pid of the next node. I could set the pid when creating the node, but I was always one pid short. Like that magic trick that, oh never mind.

The first light came when I realized that you didn't need to set the pid when creating the node, but you can send the process a message that contains the pid to connect to (by changing its state, not setting a variable). This led to the first solution, where I create a list of processes, and after that, loop through the list to connect the processes.

-module(ring).
-export([start/2, loop/0]). 

ring(N, N) -> [link()];
ring(N, M) -> [link()|ring(N+1,M)].

connect([F], H) ->
  F ! {gate, H};
connect([F|[S|T]], H) ->
  F ! {connect, S},
  connect([S|T], H).

link() -> spawn(ring, loop, []).

loop() ->
  receive
    {connect, Next} -> loop(Next);
    {gate, Next} -> gate(Next)
  end.

loop(Next) ->
  receive
    Msg ->
      io:format("~p... ", [self()]),
      Next ! Msg,
      loop(Next)
  end.

gate(Next) ->
  receive
    {1, Msg} ->
      io:format("Done with ~p~n", [Msg]);
    {N, Msg} ->
      io:format("Passed gate, ~p more rounds to go~n", [N-1]),
      Next ! {N-1, Msg},
      gate(Next)
  end.

start(N,M) ->
  Ring = ring(1,N),
  [H|_] = Ring,
  connect(Ring, H),
  H ! {M, "Hello, world"}.

I needed two more things after this: I wanted to make the main process part of the ring, instead of spawning the whole ring, because I felt this would allow me to control the number of loops that were made more easily. And in trying this I discovered a more elegant way of setting up the ring: one node spawns another node that sends a message with it's pid back to the original node.

-module(ring2).
-export([start/2, loop/1, ring/3]). 

ring(1, Pid, Main) ->
  Pid ! {connect, self()},
  loop(Main);

ring(N, Pid, Main) ->
  spawn(ring2, ring, [N-1, self(), Main]),
  receive
    {connect, To} ->
      Pid ! {connect, self()},
      loop(To)
  end.  

loop(Pid) ->
  receive
    Msg ->
      io:format("~p... ", [self()]),
      Pid ! Msg,
      loop(Pid)
  end.

gate(Pid) ->
  receive
    {1, Msg} ->
      io:format("Done with ~p~n", [Msg]);
    {N, Msg} ->
      io:format("Passed gate, ~p more rounds to go~n", [N-1]),
      Pid ! {N-1, Msg},
      gate(Pid)
  end.

start(N, M) ->
  spawn(ring2, ring, [N-1, self(), self()]),
  receive
    {connect, To} ->
      To ! {M, "Hello, world"},
      gate(To)
  end.
  

I didn't get round to doing the actual benchmarking, but it was a great puzzle and I can't wait to delve deeper into erlang.