[erlang-questions] Ideas for a new Erlang

[Sven-Olof Nystr|m]

Sorry for the delayed response. 

Richard A. O'Keefe writes:
 > On 1 Jul 2008, at 6:51 am, Sven-Olof Nystr|m wrote:
 > >
 > > But an Erlang process is always willing to accept messages. Unlike an
 > > Ada process (say) there is no way an Erlang process can prevent
 > > another process from sending it a message. The process can choose not
 > > to look at it, but that's another matter.
 > 
 > I would say that
 >   - a MAILBOX is always willing to accept any message
 >   - a PROCESS is only willing to accept a message when
 >     it is executing a 'receive' construct that will
 >     match it.

Correct. However, the sending process has no way of telling whether
the receiving process has accepted the message or not. In contrast, in
a language with unbuffered communication (such as Ada), the sending
process is blocked until the receiving process has accepted the
message.

 > By the way, the bounded buffer example can obviously be
 > "rescued" thus:
 > 
 > 	producer(Buffer) ->
 > 	    ....
 > 	    Buffer ! {put,self(),Item},
 > 	    receive {ok,Buffer} -> ok end,
 > 	    producer(Buffer).
 > 
 > 	consumer(Buffer) ->
 > 	    Buffer ! {get,self()},
 > 	    receive {ok,Buffer,Item} -> ok end,
 > 	    ....
 > 
 > 	buffer(Pool, Left) ->
 > 	    receive
 > 		{put,Producer,Item} when Left > 0 ->
 > 		    Producer ! {ok,Buffer},
 > 		    buffer(Pool ++ [Item], Left - 1)
 > 	      ; {get,Consumer} when Pool =/= [] ->
 > 		    Consumer ! {ok,Buffer,hd(Pool)},
 > 		    buffer(tl(Pool), Left + 1)
 > 	    end.
 > 
 > Assuming that this is part of a system where only the
 > producer and consumer can refer to Buffer, this is
 > the traditional bounded buffer.  The argument that the
 > mailbox (but NOT the process) is always willing to
 > accept more messages has no force between the senders
 > won't *send* more messages; the buffer's mailbox will
 > have at most one 'put' and and most one 'get' at any
 > one time.  The substantive point, that the *process*
 > (not the mailbox) is willing to accept different
 > messages at different times remains.

Yes, this is what I had in mind. Here you are in effect simulating
unbuffered communication. 

Using channels, the receive in the functions producer/1 and consumer/1
can easily be rewritten using channels. The function buffer/2 needs a
third parameter containing an explicit queue of unprocessed requests.

 > This is a nice illustration of why mailbox length is
 > often not a problem:  the need for a response means
 > that the mailbox is bounded in size by the number of
 > processes that might send messages.  In effect, the
 > responses are a form of flow control.

Unless a process sends more than one message. (Allright, I agree that
normally there would only be one outstanding message per process.)

 > > So your argument is: Concurrent ML tried something similar.
 > > It did not work out.
 > 
 > It worked out in the sense that the design was implementable,
 > was implemented, was used, and is still available in SML/NJ
 > and Mlton.  It also worked out in the sense that *simple*
 > problems don't look too bad.  The point is that things which
 > would still be pretty straightforward in Erlang with its
 > 'receive' quickly become very complex in CML.

I have not tried writing anything in CML, but I have looked through
the documentation and read parts of Reppy's thesis. The language does
not look very attractive, but it doesn't look *that* bad. It would be
interesting to here more about why CML was hard to use for complex
problems.

 > 
 > Interestingly, the Limbo programming language has CML-like
 > channels, but without all the extra stuff in CML.  (For
 > example, CML has both channels and mailboxes.)

Right. So CML channels are unbuffered, while CML mailboxes are
buffered. Limbo channels are also unbuffered.

 > http://www.vitanuova.com/inferno/papers/limbo.html
 > 4.2.5
 > 	chan of <data-type>		is a type.
 > 	ch <-= msg			is a send.
 > 8.2.9
 > 	<- ch				is a receive
 > 	<- ch_array			is multi-receive
 > For example,
 > 	msg = <- ch
 > receives a message from one channel.
 > 	(ix, msg) = <- ch_array
 > receives an (index, message) pair where the index says
 > which element of the channel array the message came from.
 > 8.4.3
 > 	ch <-= msg
 > blocks if no process is reading from ch.
 > 9.8
 > 	alt {... msg = <- ch => stmt;
 > 	     ... ch <- = msg => stmt;
 > 	}
 > is like an Occam ALT.
 > 
 > Let me quote section 12.4 in full.
 > 
 >      12.4 Buffered channels
 > 
 >      Limbo channels are unbuffered; a sender blocks until there is a
 >      receiver.  This example shows a way to make a buffered channel of
 >      strings from an unbuffered channel.  It is written as a module  
 >      whose
 >      bufchan function takes a chan of string and a size as argument, and
 >      returns a new channel; it creates an asynchronous task that accepts
 >      input from the argument channel and saves up to size strings,
 >      meanwhile trying to send them to its user.
 > 
 >      implement Bufchan;
 > 
 >      Bufchan: module {
 >          bufchan: fn(c: chan of string, size: int): chan of string;
 >      };
 > 
 >      xfer(oldchan, newchan: chan of string, size: int) {
 >          temp := array[size] of string;
 >          fp := 0;    # first string in buffer
 >          n := 0;     # number of strings in buffer
 >          dummy := chan of string;
 >          sendch, recvch: chan of string;
 >          s: string;
 > 
 >          for (;;) {
 >              sendch = recvch = dummy;
 >              if (n > 0)    sendch = newchan;
 >              if (n < size) recvch = oldchan;
 >              alt {
 >                  s = <-recvch =>
 >                      temp[(fp+n)%size] = s;
 >                      n++;
 > 
 >                  sendch <- = temp[fp] =>
 >                      temp[fp++] = nil;
 >                      n--;
 >                      if (fp>=size) fp -= size;
 >              }
 >          }
 >      }
 > 
 >      bufchan(oldchan: chan of string, size: int): chan of string {
 >          newchan := chan of string;
 >          spawn xfer(oldchan, newchan, size);
 >          return newchan;
 >      }
 > 
 >      The module is somewhat specialized, but it illustrates useful
 >      programming techniques.  The most interesting occurs in xfer, which
 >      does the work.  The problem xfer faces is that it doesn't want to
 >      receive input when its buffer is full, nor to try to send when it
 >      has nothing to transmit.  The solution here is to use a dummy
 >      channel on which nothing is ever sent or received; in the alt
 >      statement, that channel substitutes for the real input channel when
 >      the buffer is full, and for the output channel when the buffer is
 >      empty.
 > 
 >      [snipped]
 > 
 > This is "real" bounded buffer.  Note the trick: you need three
 > channels, one of them a dummy that will never be used.  If you
 > don't want a particular alternative to really be there, make
 > that one wait for a communication that can never happen.  To me
 > this is much harder to understand than a guarded 'select' in
 > Ada or 'alt' in Occam, because what's _really_ going on is hidden
 > under a layer of what I can only call obfuscation.


Yes, this is a nice example. Also similar to the Ada example you gave
previously. Naturally, in a language without buffered communication,
one of the first things one needs to implement is buffered
communication :-)


 > > So we agree that it's *not* an implementation of bounded buffers????
 > 
 > Why do you harp on this one note?
 > Idunno, you strip things to the bone to make a point concisely,
 > and someone makes a federal case out of your kindness.
 > 
 >  From now on, please do not refer to the stripped down example,
 > but only to the full producer/buffer/consumer example, which contains
 > material not relevant to the state-dependent-reception POINT.

I asked because it seemed like an important example. I promise, I will
not bring it up again :-)

 > >
 > 
 > > Since I came up with the channel concept, I've been looking for some
 > > convincing example of an Erlang program that could be implemented
 > > using selective receive, but was not possible to implement using
 > > channels (or where the solution with channels was more complex).
 > 
 > Try looking in the Erlang sources.  There are plenty of simple cases
 > there, true.  But there are also plenty of cases where many channels
 > would be needed, making the solution with channels look a lot more
 > complex to me.

I have looked at the POTS solution in the Erlang book and the
gen_server module. See my response to Ulf Wiger's post previously in
this list.

 > 
 > It may be that we have different ideas of what counts as a 'more
 > complex' solution.  If this thread is not to degenerate into something
 > out of Dr Suess (was it the West-going something and the East-going
 > something else or was it North and South?) we really need to see
 > some concrete cases FROM THE PROPOSER.

OK.

 > The proposal in the document I was responding to does not contain
 > any multi-receive, and it's not clear that one can be programmed from
 > the operations that are in the document.  I don't know any message-
 > based language that doesn't have some analogue of an Occam 'ALT'/
 > Limbo 'alt'/Ada 'select', and that document doesn't include one,
 > so it's clearly incomplete that way as well.

Actually, I think unbuffered languages (such as the ones you mention)
are very different from buffered languages, and that it is a mistake
to try to transfer experiences from the unbuffered languages to
Erlang.

 > 
 > So we need to see a functionally complete proposal (in order to
 > judge how complex the proposed replacement for 'receive' is in
 > itself) *AND* some examples of rewritten Erlang code to judge
 > how complex the replacement is in use.

OK.


 > For the statement
 > > I've been looking for some
 > > convincing example of an Erlang program that could be implemented
 > > using selective receive, but was not possible to implement using
 > > channels (or where the solution with channels was more complex).
 > to have any force, there must already BE a number of examples which
 > have been so rewritten.  So let's see them.

I'll get back to you on that.



Sven-Olof