Yet more CAL/Java questions

[Tom Davies]

I've been having some success with 'Parallel CAL'. Parallel Haskell
has the property that once a thread starts to calculate the value of a
thunk, other threads evaluating the thunk are blocked until the value
is available. I don't think CAL does that.

I'm now trying to implement:

tryTakeMVar ::MVar a -> Maybe a;

What I'd like to do on the Java side is:

public MaybeValue tryTakeMVar()
{
return MaybeValue.makeMaybe(queue.poll());
}

queue.poll() returns a CalValue.

Unfortunately the above doesn't work -- MaybeValue needs to be
converted to a Maybe with input, and the CalValue inside it isn't
Inputable, as far as I can tell -- when I use it on an MVar Int I get
a classcast exception in Cast, here:

public static int objectToInt(Object object) {
return ((Integer) object).intValue();
}

object is actually an RTData$CAL_int. What's the best technique here?

I've successfully implemented a (deadlock prone) version of the dining
philosophers -- the code below uses my pseudo-Haskell random number
and IO modules:

module Extension.Philosophers;

import Cal.Core.Prelude using
typeConstructor = String;
function = seq, upFromTo;
;

import Cal.Collections.List using
function = map, last, init, zip3;
;

import Extension.Random using
function = getStdRandom, randomR;
;

import Extension.STM using
typeConstructor = MVar;
function = threadDelay, newMVar, takeMVar, putMVar, forkIO;
;

import Extension.IO using
function = putStrLn;
;

philosopher :: MVar () -> MVar () -> String -> ();
public philosopher left right name =
(putStrLn $ name ++ " is thinking.")
`seq`
(threadDelay $ getStdRandom $ randomR (1, 1000000))
`seq`
(putStrLn $ name ++ " is hungry.")
`seq`
(takeMVar left)
`seq`
(putStrLn $ name ++ " picked up his left fork.")
`seq`
(threadDelay $ getStdRandom $ randomR (1, 1000000)) // the
probability of deadlock depends on the length of this wait. The
probability is never zero.
`seq`
(takeMVar right)
`seq`
(putStrLn $ name ++ " picked up his right fork.")
`seq`
(threadDelay $ getStdRandom $ randomR (1, 1000000))
`seq`
(putStrLn $ name ++ " has finished eating.")
`seq`
(putMVar left ())
`seq`
(putMVar right ())
`seq`
(philosopher left right name);

doPhilosophers =
let names = ["Aristotle", "Kant", "Heidegger", "Sartre", "Hume"];
leftForks = map (\x -> newMVar ()) names;
rightForks = [last leftForks] ++ (init leftForks);
startPhilosopher left right name = forkIO (philosopher left
right name);
in
map (\triple -> startPhilosopher triple.#1 triple.#2
triple.#3) (zip3 leftForks rightForks names);

[bilic]

Hi Tom,

In implementing "tryTakeMVar ::MVar a -> Maybe a" you can do something
like "(unsafeCoerce (Prelude.input x :: Maybe CalValue))"
where "x :: JObject" is the returned value from the tryTakeMVar
foreign function and the unsafeCoerce is placed so that it will type
infer to the "Maybe a" return type of the CAL tryTakeMVar.

The problem with the deadlocks in your dining philosopher's
implementation is likely because it is sharing an execution context
and CAL values across concurrently running threads, which is not
supported in Open Quark 1.4.0. In the future, we would like to reduce
this restriction; even currently in some circumstances this sort of
sharing partially works, but we will be able to give more precise
rules at some point as to when it is guaranteed to work.

Here is a summary of the current multi-threading support in Open Quark
1.4.0 and explains more precisely what we mean when we say that CAL
has a multi-threaded compiler and runtime.

The org.openquark.cal.machine.ExecutionContext class is used for
identifying cached constant applicative form (CAF) results, halting
execution, and statistics collection. You can't have multiple threads
simultaneously using the same execution context, though you can have
different threads use the same execution context serially i.e. thread
1 uses it and finishes, then thread 2 uses it, etc.

CAL values created using one thread cannot be concurrently evaluated
using multiple threads.

Compilation is multi-threaded in the sense that if a program consists
of module A, then it is possible to dynamically create and compile a
module B that imports A while concurrently running functions in A and
other modules, or indeed concurrently compiling some other independent
module.

Effectively, concurrent programming in CAL involves using Java for
thread initialization and synchronization, where each CAL computation
has its own execution context. The "CAL and the Computer Language
Shootout Benchmarks" discusses this pattern and sources for the 2
multi-threaded Shootout benchmarks are included in the distribution as
samples.

[Tom Davies]

Thanks for the information.

The deadlocks are inherent in the algorithm that sample uses -- it's
easy to get into the state where each philosopher has their left fork
(which is someone elses right fork) and is blocked trying to get their
right fork. It isn't a bug, certainly not in CAL.

The only threading problem I have seen so far is in this code:

public testmvar =
let m = newEmptyMVar :: MVar Int;
putMany :: (MVar Int) -> Int -> ();
putMany !m n = seq (putMVar m n) (putMany m (n+1));
getMany :: MVar Int -> ();
getMany !m = seq (trace (show (tryTakeMVar m) ++ "\n") ())
(getMany m);
in
seq (forkIO (getMany m)) (putMany m 1);

before I made the arguments to putMany and getMany strict, the two
evaluations of 'm' would return different MVars, instead of sharing
the same one.

Tom

[Tom Davies]

That works -- the function:

tryTakeMVar :: MVar a -> Maybe a;
public tryTakeMVar mvar =
let MVar jmvar = mvar;
in (unsafeCoerce (input $ (jTryTakeMVar jmvar) :: Maybe
CalValue));

I understand how the unsafe coerce allows CAL to accept that a Maybe
CalValue is a Maybe a, but I'm not sure how specifying the result of
input as Maybe CalValue affects what input does? Does it mean that
input won't process the contents of the MaybeValue?

Tom

[bilic]

Thanks for the details. Yes, this sort of thing can happen because the
local variable 'm' probably didn't get updated in time for the second
concurrent thread to get its reduced value. This sort of thing can
happen.

[bilic]

Hi Tom,

To see what Prelude.input on a Maybe CalValue means, you can look at
the definition of the Inputable Maybe instance and the Inputable
CalValue instance.

The Inputable Maybe instance is a constrained instance:
Inputable a => Inputable (Maybe a)
which is defined as converting an
org.openquark.cal.foreignsupport.module.Prelude.MaybeValue to a
Prelude.Maybe value. In the case of a value created by
MaybeValue.makeJust(Object value), then the value field is input via a
call to Prelude.input, so because the type is declared as Maybe
CalValue, the input on the value field will be Prelude.input ::
JObject -> CalValue, which, by the definition of the Inputable
CalValue instance, is the identity function.

In a sense the CalValue type can be thought of as a way to marshal CAL
values to and from Java in such a way as to leave them "untouched".

Another example of this pattern is in Prelude_Tests.reverseExternal,
where a CAL list of values of type [a] is output to a Java list of
CalValues, reversed in place, and then input back to get a CAL list of
values. We want the list elements to be untouched by the container
Java algorithm, and so they are input and output as CalValues.

Bo

[Tom Davies]

Hi Bo,

Thanks for all your help -- now my next question!

I want to define the function:

atomically :: a -> a;

This takes a fully-bound function returning a and runs it (via Java)
as a transaction.

What I have so far is:

foreign unsafe import jvm "static method
CAL.Extension.JTVar.atomically"
public jAtomically :: CalFunction -> CalValue;

public atomically f =
let
fn :: CalFunction;
fn = makeCalFunction ((\x -> (unsafeCoerce f) :: JObject ) ::
(JObject -> JObject));
in
unsafeCoerce (jAtomically fn) :: a;

The Java side looks like this (it doesn't actually create a
transaction yet)

public static CalValue atomically(CalFunction f)
{
CalValue result =
((RTCalFunction)f).evaluateReturningCalValue("ignored");
return result;
}

You won't remember evaluateReturningCalValue -- I added it to
RTCalFunction because otherwise functions returning Int wouldn't work,
because getOpaqueValue() isn't defined on them.

So we now have:
public Object evaluate(Object argument) {

//evaluate (calFunction argument).

return evaluateReturningCalValue(argument).getOpaqueValue();
}
public RTValue evaluateReturningCalValue(Object argument) {

//evaluate (calFunction argument).

try {

return
calFunction.apply(CAL_Opaque.make(argument)).evaluate(executionContext);

} catch (CALExecutorException executorException) {
//wrap the exception up in a non-checked exception and
rethrow.
throw new RuntimeException(executorException);
}
}

Was there a better way?

(my goal is to implement the STM library using Sun's dstm2. It doesn't
do nested transactions or deliberate retries, but it is a start. I'm
doing this for mental exercise.)

Thanks,
Tom

[bilic]

Hi Tom,

Earlier I mentioned that Prelude.input for CalValue's is just the
identity. More precisely though, it is a downcast from a
java.lang.Object to the CalValue implementation Java class. The
runtime errors you bumped into below may be because some of the
unsafeCoercing is not right. I don't think you need to change the Java
implementation of CalFunction.

In your implementation of atomically, how about defining the local fn
as:
fn = makeCalFunction ((\x -> (output ((unsafeCoerce f) ::
CalValue) ) ::
(JObject -> JObject));
instead?

The problem with the previous
(unsafeCoerce f) :: JObject
is that it is not actually true e.g. if f has type Int, so you'll
eventually get a runtime error, as you mentioned below.

Cheers,
Bo