Wednesday, February 27, 2013

Adding Concurrency to Frege (part I)

Inspired by a reddit post this week, I wondered what it would take to add concurrency to Frege, so that one could program a few simple examples from the concurrency chapters of Simon Marlows upcoming book in Frege.

For this we would need Threads, MVars and the operation forkIO that is supposed to execute some IO actions in a new thread concurrently with the main thread. The Haskell type signature of forkIO is:

forkIO :: IO () -> IO ThreadID

Let us first deal with Threads. We can import the functionality we need from Java:

data Thread = mutable native java.lang.Thread where
    --- Create a 'Thread' that runs a 'Runnable'
    native new   :: MutableIO Runnable -> IO Thread
    --- Actually start execution of a 'Thread'
    native start :: Thread -> IO ()

A few explanations for those who are not familiar with Frege: The code above first tells the compiler, that there is a Java type java.lang.Thread that we want to use as abstract data type under the name Thread.
It then puts two native function definitions (in Haskell terminology this would be foreign imports) in the name space that is associated with each type constructor. By convention, the name new designates the Java constructor of some class, while start is just an ordinary instance method. (Note that new could never mean an actual Java method, as new is a keyword in Java.)

Observe that native definitions never create anything new at the native (i.e. Java) level, they are merely telling the Frege compiler what already exists in Java and how we want to use it. From the definition for start, for example, the compiler deduces that there must be an instance method start in the class java.lang.Thread with a declared return type of void. It will then generate some wrapper code that allows us to use the Frege function Thread.start like any other, non native function.

By the way, we don't have to put those native definitions in the Thread namespace. We could give the definitions on the top level like so:

native newThread   new   :: MutableIO Runnable -> IO Thread
native startThread start :: Thread -> IO ()

Obviuosly, though, in a program that deals with several Java classes (say A, B and C), we would then have to come up with different names like newA, newB and newC for their constructors and for other methods with the same name. We also could not use type directed name resolution, which allows us to write t.start and resolves it as (T.start t) if t is of type T.

The class java.lang.Thread has many different constructors,
but we want to use the one that takes a Runnable as argument.
The type Runnable is defined in frege.java.Lang,
this module is imported by default, so Runnable is normally in scope.

Interface Runnable is Javas way to pass around effectful computations.
The Frege runtime provides a function Runnable.new that
takes an IO action and constructs a Runnable instance that will execute
that action as soon as the Runnable.run method is called from within the depths
of Java. This is just what we need for our purposes.

We are now ready to write the Frege version of forkIO:

forkIO :: IO () -> IO Thread
forkIO action = do
    r <- Runnable.new action
    t <- Thread.new r
    t.start
    return t

This simply wraps the IO action passed as argument in an instance of Runnable
and creates a new thread with it. It then starts the thread
(which, in turn, causes invokation of Thread.run, which, in turn, invokes
Runnable.run and this, as said before, starts our IO action) and returns the Thread, unlike in Haskell, where it is a ThreadID.

But because a native type in Frege is just an abstract data type that can
ultimately only get manipulated through native functions,
the Thread reference we get from Java serves us very well as "handle" or "id",
so we need not distinguish between a thread and a handle to manipulate a thread.

What we have so far allows us to implement Simon Marlows first example, a simple program to demonstrate the interleaving of effects:

main args = do
    forkIO (replicateM_ 100000 (putChar 'a'))
    replicateM_ 100000 (putChar 'b')

And indeed, when we run this, we get something like:

ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
babababababababababababababababababababababababababab

Most of the time, the scheduling of the threads seems to be fair;
however, there are also long strokes of only 'a's or 'b's inbetween.
(Example was run on Ubuntu 12 on a PC with i3 processor with 2 cores with "hyperthreading".)



In the next part we will implement MVars and turn to more involved examples, so stay tuned.

No comments:

Post a Comment

Comments will be censored by me as I see fit, most likely if they contain insults or propaganda for ideologies I do not like. Comments that are on topic will not be censored. If I leave a comment uncensored this does not imply that I agree with the opinions expressed therein.