[erlang-questions] Ideas for a new Erlang

[Sven-Olof Nystr|m]

Richard A. O'Keefe writes:
 > I spent last night reading "Ideas for a new Erlang".  It's not clear
 > whether it would be better to write all the responses in one message
 > or to split them into several messages, each with its own Subject:.
 > Let's keep it as one to start with.

OK, I'm very interested in hearing your comments.


 > 
 > SELECTIVE RECEIVE VS MAILBOX OBJECTS
 > ====================================
 > 
 > p1. "Consider, for example, selective receive (no other programming
 >       language requires anything similar),"
 > 
 > Untrue.  Ada and Occam should not just spring to mind but jump up
 > and down screaming loudly "pick me, pick ME!"

[quoted material deleted]

 > The quoted material is from the Ada'05 (actually ISO something:2007)
 > reference manual, however the construct was already present in Ada 81.


Aren't we talking about a different type of machinery here? If I'm not
mistaken, Ada uses synchronous communication which means that the
sender of a message will be suspended until the receiver takes
it. Without receive, there would be way to examine a message without
releasing the sender. I assume that this is the main motivation for
Ada's selective accept. 

Suppose we wanted to translate some Erlang application to Ada. One
would probably implement the mailboxes as a separate data
structure. Erlang's selective receive would be replaced by code that
scanned this data structure. You would not translate code that used
Erlang's selective recive to code that uses Ada's.

On the other hand, I agree that there is a strong superficial
similarity between Ada's receive and Erlang's. It is quite likely that
Erlang's designers were influenced by it. (They seem pretty unclear
about this, see for example a thread in this mailing list:
<http://www.erlang.org/pipermail/erlang-questions/2004-June/012645.html>)


 > The placement of the guard *before* the accept tells you something
 > relevant.  In Ada (and Occam), the guards serve only to selectively
 > enable or disable which messages will be looked for *before* they are
 > considered for accepting, not to select or postpone messages based on
 > their content after they arrive as in Erlang.  However, nothing in the
 > Erlang language requires the guards in a 'receive' to depend on the
 > message contents, so the Erlang selective receive can be used to do the
 > Ada (and Occam) thing.
 > 
 > The classic example is a bounded buffer.
 > 
 > 	buffer(Status, Contents) ->
 > 	    receive
 > 	        {put,Msg} when Status /= full ->
 > 		    {Status1, Contents1} = add(Contents, Msg)
 > 	      ; {get,Who} when Status /= empty ->
 > 		    {Status1, Contents1, Msg} = pop(Contents),
 > 		    Who ! Msg
 > 	    end,
 > 	    buffer(Status1, Contents1).
 > 
 > Without selective receive (or in Ada, selective accept), this would
 > require three receives: one for the full case, one for the empty case,
 > and one for the in-between case.  In general, this lets us replace up
 > to 2**n-1 receives with a single receive having n guarded alternatives.

This is a rather interesting example.  I must admit that I have not
seen anything like it in Erlang. On the other hand, I have trouble
understanding the underlying motivation.

When the buffer is full, incoming 'put' messages will be kept in the
mailbox instead of stored in the buffer, so they will still require
approximately the same amount of memory on the heap. For an outside
observer, there will be no difference between this buffer and one that
uses an unbounded data structure, execpt that it is easier to overflow
the mailbox of the bounded buffer. Also, as the 'put' messages start
to accumulate in the mailbox, finding a matching 'get' message will
become more costly.



 > p3. "It is strange that Erlang has a feature that is on one hand so
 >       general and powerful, but yet programmers are not supposed to
 >       take advantage of it!"
 > 
 > It would be strange, IF it were true.  But it isn't.  Erlang programmers
 > ARE supposed to take advantage of selective receive.  Just as selective
 > accept is indispensable in Ada and Occam, it is indispensable in Erlang.
 > There is no other way, in any of these three languages, to wait until
 > one of N things happens.

Actually, there is no way in Erlang to even receive a message without
using selective receive.

 > 
 > Note that "simplifying" Erlang receives would do nothing whatever to
 > address the problem of mailbox overflow.  Supposing Ch to be a channel,
 > 	L = lists:seq(1,1000),
 > 	lists:foreach(fun (X) ->
 > 	    lists:foreach(fun (Y) ->
 > 		lists:foreach(fun (Z) ->
 > 		    Ch ! ok
 > 		end, L)
 > 	    end, L)
 > 	end, L)
 > is going to be trouble even if there is only unconditional-receive-from-
 > channel and no selective receive at all.

Sure. There are many ways to run out of memory.

 > 
 > It would be absurd to cripple the language in order to avoid a problem
 > and then find the problem snickering on your shoulder as lively and as
 > malevolent as ever.

As I say above, I don't find your bounded buffer example very
convincing. Do you have other examples?

 > p3. "To the best of my knowledge, selective receive has only two uses:"
 > 
 > The bounded buffer example above shows that this is not so.
 > 
 > p4. Channels as first class objects.
 > 
 > But they already are.  There are three proposed functions and an  
 > operator.
 > We'll represent a channel as a process.   The only even slightly tricky
 > thing is that we need to distinguish between other messages sent to the
 > current process and replies sent from a channel.  We'll use the rather
 > subtle fact that a reply can only arrive when we've asked for one, and
 > that when we ask for one, we'll wait until we get it, so there never  
 > will
 > be one in the mailbox at other times.
 >
[simple implementation snipped]
 >
 > So anyone who wants to program in this style already may.  In fact it
 > is useful to distinguish between a single-shot channel and a multi-shot
 > channel. 

I have thought about this. In many cases, one would only send a single
message on a channel. Would there be anything to gain from having a
separate type of channel for this case?

Similar ideas have been mentioned elsewhere, for example the logic
variables of concurrent logic languages and I-structures of data flow
languages.

 > I hope that we can rely on Erlang garbage collection to
 > collect any process suspended in a receive construct and not registered
 > and not referenced by any other process.  If we can, the distinction is
 > only useful to people and not really needed by the computer.

Not sure that I follow your reasoning. Garbage collecting processes is
a tricky issue. As you say, channels may help in certain cases.

 > The thing that strikes me forcibly is that I have seen
 > all this before.  John Reppy's Concurrent ML.  It's
 > supported in SML/NJ and Mlton and perhaps other ML
 > implementations.  What Nystrom calls a "channel" is
 > what CML calls a "mailbox".  (What CML calls a "channel"
 > is what Occam calls a "channel".)  And comparing the CML
 > code I've seen to Erlang makes Erlang look stunningly
 > simple *in use*.

True, many languages have a channel concept.

In my opinion, one great advantage of Erlang over other languages that
use channels is that in Erlang, each process has a "standard" channel 
that it normally takes input from. I hope that I was not unclear about
this, but that is a feature of Erlang that I had not intended to change.

The problem with using the single channel for all types of
communication is that the mailbox ends up containing messages that are
not related to the service provided by the process. In your bounded
buffer example, one would normally only expect to see 'put' and 'get'
messages in the mailbox. Any other messages would indicate a bug
somewhere. However, if one inserted some calls to io:format() in the
code, those calls would cause other messages to be sent to the
process.


 > 
 > 
 > GUARDS
 > ======
 > 
 > 
 > p6. "The complex selective receive primitive of old Erlang
 >       has forced the Erlang designers to introduce a more
 >       restricted type of expressions called _guards_."
 > 
 > This is fiction, and it's fiction with a major error in it.

That is terrible.

 > Guards are *NOT* a restricted type of expression.

I meant expression in a general sense. I know that Erlang expressions
and Erlang guards form two different classes of expressions.


 > This was much clearer in old Erlang.
 > Sadly, it has been obscured by the disastrous design bungle
 > of giving guard predicates aliases that can be used in
 > expressions and by allowing 'or' and 'and' -- which should
 > be avoided AT ALL TIMES AND IN ALL PLACES -- in both contexts.

[Interesting comments on guards deleted.] 

 > The whole point of section 3.4 is
 > 	"SINCE guards are restricted expressions,
 > 	 they ought to be unrestricted expressions"
 > but since the assumption is flat-out false, the conclusion is
 > unwarranted.
 > 
 > The limitations of guards have NO intrinsic connection with
 > receive, although they turn out to be very pleasant for receive.
 > Erlang guards have their roots in concurrent logic programming
 > languages such as Strand88, GHC, FCP, and Parlog.

Sure, there is a historical connection. Still, it is hard to see
how selective receive could work if ordinary expressions were allowed
as guards.


 > Whenever I see people demanding that guards should be complexified,

I hope you didn't think that I suggested that?

 > I find myself wondering "do I know something about readability and
 > maintainability that they don't, or is it the other way around?"
 > The way I see it, if your selection process is complex enough that
 > you *want* to write complex guards with user defined functions,
 > then what you *need* is either
 >   - abstract patterns, or
 >   - a rewrite.
 > 
 > Let me offer an example I saw today, in
 > http://www.infoq.com/articles/erlang-dsl

[removed example of how case analysis can be simplified]


 > 
 > 
 > LINKED MODULES
 > ==============
 > 
 > p6. "Erlang's record facility is rather unusual (at least in the
 >       world of functional programming languages)."
 > 
 > If you are willing to count the Lisp family as functional, then
 > this is historically quite untrue.  I've lost count of the number
 > of times I've written Scheme code like
 > 
 > 	(define (make-node Op Left Right)
 > 	    (vector 'node Op Left Right))
 > 	(define (node? Node)
 > 	    (and (vector? Node)
 >                   (= (vector-length Node) 4)
 >                   (eq? (vector-ref Node 0) 'node)))
 > 	(define-macro (node-op Node)
 > 	    `(vector-ref ,Node 1))
 > 	(define-macro (node-left Node))
 > 	    `(vector-ref ,Node 2))
 > 	(define-macro (set-node-left! Node New-Left)
 > 	    `(vector-set! ,Node 2 ,New-Left))
 > 	...
 > 

OK. The difference is of course that Erlang's macros are lexical,
while Lisp's work on the internal representation.

 > The problems of -include have been known for a long time.
 > My "Delenda est preprocessor" paper was written some time
 > in July 1998 (at least, that's the date on the only copy
 > I can find).

Sure. I suspect that many people recognized it as a bad idea almost
immediately.

 > 
 > p7. "the obvious alternative would be to expand a record definition
 >       into a set of function definitions".
 > 
 > Well, no, because you can't use function calls as patterns.
 > That's why abstract patterns are needed.

True. So we we need a mechanism to recognize certain patterns and
replace the pattern match with function calls that test and extracts
subtrees.


 > 
 > The work I did for Fergus O'Brien back in 1998 -- I miss him,
 > and I especially miss getting paid for thinking about Erlang! --
 > included a proposal that I'll now reconstruct for you, with
 > two small changes.
 > 
 > Two new directives replace -import(Mod, Funs).
 > 
 > 	-import(Module, When, Funs).
 > 	-use(Module, When, Funs).
 > 
 > 	Module : an atom
 > 	When : 'early' or 'late'
 > 	Funs : a list of Name/Arity (or #Name/Arity) pairs.
 > 

That could also work.

 > A -use directive creates a dependency (recorded in the .beam
 > file) between this module and Module.  It also notifies the
 > compiler that this module may call any of the functions (and/or
 > abstract patterns) listed in Funs, but if so, a module prefix
 > is required.
 > 
 > If When is 'late', the dependency is a load-time one: before
 > EXECUTING this module, Module should be LOADED.  Cyclic late
 > dependencies are perfectly OK; all the members of a cycle
 > should be loaded before running anything from any of them.
 > This dependency exists even when Funs is empty; you might be
 > using some kind of dynamic call to call functions from Module.
 > The only thing that the compiler may assume about Module is that
 > loading will have ensured that the named functions all exist,
 > even if only as loader-generated stubs that raise an undefined
 > function exception.
 > 
 > If When is 'early', the dependency is a compile-time one:
 > before COMPILING this module, Module should be COMPILED, and
 > so if Module is changed, this module also needs recompiling.
 > Cyclic early dependencies are not allowed.  The compiler may
 > assume about Module anything whatever that it discovers in the
 > .beam file.  (Arguably interface information should be in
 > a separate file, not unlike the .hi files used by GHC.
 > I propose ".ern" (for .ERlang iNfo), in honour of the late
 > Ern Malley.)
 > 
 > The difference between -import and -use is that -import
 > allows (but does not require) the listed functions to be called
 > without a module prefix, provided there is no clash with any
 > other imported function or any function defined in this module.
 > 
 > There may be more than one -use or -import for a Module, and
 > there may be both -import and -use directives for the same
 > Module.  There may be both early and late dependencies on a
 > module, but if so, 'early' wins.
 > 
 > early/late is split out as a separate argument so that it can
 > be determined by a macro.

Looks like a variation of my proposal. (OK, technically my proposal is
a variation of yours :-)

I would be happy to see either implemented.

Still, I'm not certain that this resolves all issues regarding
inlining of function calls across module boundaries.

It would be nice if those who rely on hot-code loading in their work
could say something about which precautions they take to avoid
consistency problems when updating a module. For example, what is done
if a record definition needs to be changed?




 > 
 > 
 > BINDINGS VIA A TYPE SYSTEM
 > ==========================
 > 
 > p8. "If we compare with the equivalent code in ... SML"
 > 
 > But why choose SML as the comparison?  Haskell's
 > 
 > 	y*y where x = 42, y = x+x
 > 
 > requires only one keyword ('where') instead of SML's four.
 > I'm not arguing for adding 'where' to Erlang, just pointing
 > out that comparisons against a limited choice of comparands
 > can be misleading.

Yes. I used SML as I know that language well. Either way, the problem
is really the nesting introduced by let. (I assume where is similar.)


 > 
 > As a matter of fact, I rather like this proposal, and think

Nice to hear.

 > it might be a nice style check to have.  Although it _is_ a
 > bit dodgy that
 > 	X = 1		exports X
 > 	X = 1, ok	does NOT export X
 > and it's a bit of a worry that
 > 	X = Y = f()
 > is a type error in the proposed scheme.  I found another
 > problem last night, but it was 1am and I can't read what I
 > wrote.

Yes. This type of thing need to be tried out in practice before one
can say with certainity that it is practical.

 > 
 > I think this proposal should be finished and written up
 > separately and EEPed as a style check.
 > 
 > 
 > A MINI LANGUAGE
 > ===============
 > 
 > The reference to the CELL is a little inaccurate, not
 > that it matters.  (The heart of a CELL is a two-way
 > CMT version of the PowerPC, with AltiVec.)
OK.

 > This is an interesting idea, but there isn't really a
 > proposal here yet.  It will be very interesting indeed
 > to discover what Apple's OpenCL looks like; in the
 > mean time, there's CUDA.
 > 
 > The trick with something like this is that there really
 > isn't a whole lot of point in it unless you go native.
 > OpenCL, of course, relies on LLVM.

Of course.

 > 
 > I suspect that
 >   - some sort of opaque numeric array values (not unlike
 >     APL)
 >   - calling out to high performance libraries like
 >     ATLAS, the CBLAS, GSL, perflib, &c
 > might be a more effective way to take advantage of
 > the vector processing facilities in modern machines.

A slightly different approach. Are you saying that the APL type arrays
should appear as Erlang data structures?


 > Whoo, wouldn't that be fun!  A hybrid of Erlang and APL2!



 > MACROS
 > ======
 > 
 > p14 "I don't know of any language that combines Lisp-style
 >       macros with a syntax that isn't Lisp-like."
 > 
 > `C (Tick-C), and arguably, Template Haskell.
 > 'forms' in WonderPop (the Pop-2 implementation for TOPS-10
 > that Robert Rae worked on) are closer to Scheme's macros.

Also, there have been attempts to retrofit Lisp with a more
conventional syntax. 

 >  From my experience with Lisp, there are macros that could
 > have been written using Scheme syntax forms, and there are
 > macros that make essential use of assignment.  Using Nystrom's
 > own example, you really _can't_ translate a "def-nt" form into
 > (part of) a LALR parser in isolation; the information has to be
 > set aside until you have seen all of the rules for that grammar.
 > That setting aside involves some sort of data base or other
 > mutable variable.

Yes. The CL-Yacc library requires that the defgrammar form comes after
all rules. The LR library could provide a function that sets up the
grammar and leave it to the developer to decide whether to do this at
runtime or compile-time. Either way, we need a way to store the rules
before processing them.

 > 
 > I note that the closures proposal for Java includes bending
 > Java syntax so that things like
 > 	with_lock (Some_Lock) { statements... }
 > which are traditionally handled in Lisp using macros
 > are in fact procedure calls, so that inlining does practically
 > everything you want.  Here's the trick]
 > 	[for] Primary (FormalParameters : [Expressions]) Statement
 > ==>
 > 	Primary(Expressions, {FormalParameters => Statement});
 > 
 > 	[for] Primary ([Expressions]) Statement
 > ==>
 > 	Primary(Expressons, {=> Statement});
 > 
 > where {formals => statements [expression]} will be Java's syntax
 > for a lambda-expression.


It is true that many of CL's macros could actually be expressed as
higher-order functions, except that the syntax becomes awkward. It
will be interesting to see how this works out.

Thank you for your comments!



Sven-Olof