Arc Forum | Parallel programming in Arc

Arc Forum

8 points by dido 6338 days ago | 5 comments

I wonder if anyone has given a great deal of thought to this. I myself lean towards doing things the way languages such as Limbo and Erlang do it, in the style of C.A.R. Hoare's CSP. I would propose adding a communication channel data type, along with operators for reading and writing to them.

(newchan)

creates a new communication channel. Any value can be sent across it.

(<- channel)

returns the value that has been put on the channel, or blocks the thread that does it until some other thread writes to the channel.

(<-= value channel)

writes the value to the channel. The writer will block unless there is some other thread reading on that channel.

To allow a thread to read or write to multiple channels, and to perform non-blocking communication, alt can be used:

(alt (<- channel) (...) (<-= value channel) (...) (...))

It's sort of like an if, with the even-numbered expressions restricted to being channel expressions that either read from or write to channels. The alt operator will choose one of the channel expressions and execute the first one that it sees that will not block. It then executes the expression immediately following. Channel reads will bind the result of the read to it. For example

(alt (<- chan) (prn "read " it " from channel") (<-= 2 chan2) (prn "wrote 2 to chan2 successfully") (prn "no channels available for non-blocking read or write"))

If we had instead written:

(alt (<- chan) (prn "read " it " from channel") (<-= 2 chan2) (prn "wrote 2 to chan2 successfully"))

Without the "else" expression, the alt operator would block the current thread until chan became readable or chan2 became writable.

The spawn operator evaluates its argument in a new thread of control. Its value is a thread object, which can be manipulated in various ways, e.g. with functions such as threadkill (which forces the thread to stop immediately) and threadjoin (which waits for the thread to finish executing; its value then becomes the value of the thread argument).

These operators and conventions are mostly borrowed from the Limbo programming language under Inferno. Any suggestions for how to improve these idioms are very much welcome.

For more on the Limbo language: http://www.vitanuova.com/inferno/papers/limbo.html

2 points by almkglor 6338 days ago | link

The framework looks good. Let's break it down to things we need:

1. Channels. arc0/arc.arc currently has "queue" which creates an abstract queue (currently implemented as a list). Possibly this is what we would like to use for channels, but note that queues will never block.

Alternatively we may have to reimplement this, since queues never block; arc0/arc.arc's 'atomic may give a hint on how to properly block on channels.

2. alt. To implement this we need to have access to something like select(), except necessary only on our channels. Basically, alt would extract the channel functions and determine which channels it should block on, and in which direction; our underlying channel-select code should then accept a list of channels and directions, and return which one it passes.

-----

1 point by almkglor 6338 days ago | link

Just a question, is anyone working on this already? What I really need is a reasonably good discussion of locks in Arc - if there aren't any locking semantics yet, how to implement them from underlying Scheme.

-----

3 points by shiro 6337 days ago | link

check out atomic-invoke. also search atomic in arc.arc.

-----

1 point by almkglor 6337 days ago | link

So... that's it? atomic? If so, does the fact that (= ...) are done (atomic ...) mean that I can just, well, write to a variable and automatically expect locking?

-----

2 points by shiro 6337 days ago | link

For the first question: Yes, to me it appears atomic-invoke is the locking primitive and everything else is built on top of it.

For the second question: note that (= ...) only expands to atwith when the generalzed location appears in the place to be set. The simple assignment

    (= a (f x) b (f y))

isn't protected. (That is, some thread may see a state where a is updated but b isn't yet, for example).

    (++ a)

is also unsafe if a is shared between threads, since it expands to

    ((fn () (set a (+ a 1))))

OTOH,

    (++ (car a))

becomes

    (atomic-invoke 
      (fn nil (withs (gs1430 a gs1429 1) 
                ((fn (val) (scar gs1430 val)) 
                 (+ (car gs1430) gs1429)))))

so it seems safe.

-----