Functional Java 2.8 contains a concurrency API that implements Actors as seen in Erlang and Scala. This allows a user to take advantage of multiple core machines in their Java code.
Runar has written articles explain how to use the API — it’s pretty darn easy for a client — just don’t look under the hood 
- Higher-Order Java Parallelism, Part 1: Parallel Strategies and the Callable Monad
- Higher-Order Java Parallelism, Part 2: Parallel List Transformations
Here is an example of a parallel fibonacci that uses a few hundred virtual threads (unlike the ping/pong example that uses… wait for it… millions of virtual threads!). On my quad-core machine, the fibonacci computation speeds up by about 6 times (45 seconds serially to about 7 seconds when using actors).
The example uses Java 7 BGGA syntax (imports ommited) and after compilation, runs fine on any 1.5 JVM. This example is also available with Java 1.5 source code in the Functional Java release.
/**
* Parallel Fibonacci numbers.
* Based on a Haskell example by Don Stewart.
* Author: Runar
*/
public class Fibs {
private static final int CUTOFF = 35;
public static void main(final String[] args) throws Exception {
if (args.length < 1)
throw error("This program takes an argument: number_of_threads");
final int threads = Integer.parseInt(args[0]);
final ExecutorService pool = Executors.newFixedThreadPool(threads);
final Strategy su = Strategy.executorStrategy(pool);
final Strategy<promise> spi = Strategy.executorStrategy(pool);
final Actor<list> out = actor(su, { List fs => {
int i = 0;
for (List ns = fs; ns.isNotEmpty(); ns = ns.tail()) {
System.out.println(MessageFormat.format("n={0}=>{1}", i, ns.head()));
i++;
}
pool.shutdown();
}});
System.out.println("Calculating Fibonacci sequence in parallel...");
final F<integer, Promise> fib = { Integer n => (n { int b => a + b }} ) };
join(su, fmap(Promise.sequence(su)).f(spi.parMap(fib).f(range(0, 46)))).to(out);
}
public static int serialFib(final int n) {
if (n < 2)
return n;
else return serialFib(n - 1) + serialFib(n - 2);
}
}
The example you present looks more like pipeline concurrency than an Actor Model. Unless I am reading it wrong there is only one actor in the example that seems to be responsible for printing messages.
I am an experienced Java developer and I find the example very difficult to understand. It showcases a proposed closure syntax and what appear to be new built-in methods of Object (like promise and fmap). There is a lot of cruft in the way of any obvious demonstration that Functional Java allows Actor-style concurrent programming.
I will place my bets on Kilim as a way to address Java’s concurrent scalability problems while avoiding changes to the syntax of Java. Kilim also addresses the well-known issues with shared-memory concurrency.
Just out of curiosity, what would the timing be for the serial case using the normal trivial optimisation, e.g. in Groovy but you will get the idea:
cache = new HashMap()
def smartFib(n) {
if (n
Just out of curiosity, what would the timing be for the serial case using the normal trivial optimisation, e.g. in Groovy but you will get the idea:
cache = new HashMap()
def smartFib(n) {
if (n < 2) return n
if (!cache.containsKey(n)) cache[n] = smartFib(n – 1) + smartFib(n – 2)
cache[n]
}
for me smartFib(2000G) averages 15-50 milliseconds on my aging laptop (note: 2000G is a BigInt in Groovy).
I am not asking this from a language religion perspective but wondering whether the parMap is acting a little like a cache and hence we have changed the algorithm somewhat. I haven’t tried to fully analyse it yet, just a little suspicious.
Not knocking the example which is certainly nice and I am certainly happy in general to favor throwing computing power rather than mental energy at certain kinds of problems but we just have to be careful about generalising perceived performance benefits.
Alain: The example shows only one explicit use of the Actor class, the rest are abstracted away. Each instance of the Promise class is backed by an Actor under the hood. The number of Actor objects actually involved is something like 93. The fact that it looks like pipelining is that this is what’s being modelled. You are very observant.
You might find the plain Java 5 version of this example easier to follow: https://projects.workingmouse.com/public/functionaljava/trunk/etc/demo/1.5/concurrent/Fibs.java
That will also show you all the imports, many of which are imported static. What looks to you like new methods on Object are probably just static imports. That’s just a coding style that you’re probably not used to.
Cruft is difficult to avoid in Java, but we do try. Functional Java is in fact an attempt to minimise the cruft. I’m continually pleased by the amount of boilerplate code that it lets me delete.
Kilim looks interesting, but I’d rather not do bytecode manipulation. I’m sure I’ll be tempted to try it out though
Paul: No optimisation is used. The demo uses the naive recursive algorithm for calculating all the numbers simultaneously. There is no sharing at all between virtual threads, so for example the thread that calculates the 45th number has to spawn new virtual threads for computing all the numbers before it while the one that calculates the 44th number spawns its own separate threads for calculating those same numbers.
The parMap function simply applies the fib function to all the numbers simultaneously. This starts 46 instances of the parallel recursive fib function yielding a list of “messages” that then get sent to individual actors by the Promise.sequence function.
This algorithm just happens to respond well to parallelisation. I agree that we have to be careful to not assume that every algorithm will be as cooperative, but I think it’s safe to say that this method will apply well to folding trees in general. Somebody should try it one some large amount of XML and see how they get on
Ignore “the number of Actor objects actually involved is something like 93″. I don’t know how many there are, but it’s somewhere between a few hundred to a couple of thousand. It doesn’t really matter.
@Alain: if you are happy using a language with optional static typing rather than enforced static typing, you can check out the following equivalent example using Groovy but done with just the raw concurrency primitives:
http://groovy.codehaus.org/Using+concurrency+primitives+from+Groovy
Hi Paul, there is no caching (memoisation) going on here.
Hi Tony, yes I worked that out upon further examination. Thanks.
Paul,
Groovy does not have any static typing at all. You’ve been bait-and-switched. In this case, the definition of “static typing” diverges from that used by type theorists and armchair logicians like myself. Groovy has “something else that is not static typing but masquerades as such”. Of course type theory is a very deep topic, so it is easy to appeal to mysticism to describe these concepts to the unsuspecting layperson. It turns out that what masquerades as static typing (that something else) has nothing at all to do with static typing (as in nothing, not a thing). It is actually quite diluted and useless in those terms.
I strongly advise anyone considering the use of Groovy, that it does not have any such notion as static typing in the true and meaningful (in any way whatsoever) sense.
Paul: The Groovy example captures the spirit of it, but it looks like you will run into thread starvation if you start it with fewer threads than the number of recursions. Does it work if THREADS = 1?
Runar: That is correct. To avoid that you would need to add lazy closure evaluation into the solution. This is conceptually easy to do. I’ll have a go at adding that when I get some more time.
Tony: It is certainly an interesting debate. With pragmatic glasses on, I would have to disagree with “in any way whatsoever” as being patently false. If you take one implication of “static typing” as being that the compiler will complain when you are trying to do things which are incompatible with defined types then clearly Groovy does that in certain scenarios.
However, there are many cases in Groovy where you might think you are using static typing when really you are using some kind of declarative dynamic checking of typing. I haven’t tried to think about this form of typing in classical type theory as in practice I don’t have any issue with reasoning about my Groovy code, so I haven’t so far had the need. It is debatable though about the merits of this form of typing compared to static typing but I feel it is certainly a step up from languages without this mechanism (e.g. Ruby) and in practice it appears to provide an additional basis by which good tool support can be provided.
Just out of interest. Where do these things fall in your spectrum of ranking type systems:
* Java’s type system (with and without generics)?
* Languages like F# which are statically typed but allow open classes?
* Languages like Boo which are statically typed but allow AST manipulations to alter the language, define macros and have an opt-out form of duck-typing?
Paul, could you give an example of somewhere where the groovy compiler complains at compile time (and ideally forces something not to compile) because of a type error?
e.g. adding type annotations to things doesn’t
int i = “fish”
compiles and fails at run time. This seems like a pretty conclusive example of not having static type checking to me, but I don’t know groovy much at all so it’s possible I’m missing something.
David: Yes, it is tricky. Groovy can’t throw a compile error for the example you gave because metaprogramming allows me to do some realy wierd things if I want. Extremely bad style but I could do:
Thread.metaClass.constructor = { new Date() }
Date d = new Thread()
But certainly any decent Groovy IDE/code style checking tool will give you a warning for this case. Certainly IntelliJ does. And the reality is that these wierd edge cases almost never show up in practice.
That doesn’t mean everything is dynamic. One example: I have static type checking available to me while defining my class hierarchies:
interface X { def foo() }
class Y implements X {}
This won’t compile even though in a pure dynamicaly typed language you would allow this because I could add the foo() method dynamically later. Groovy takes the stance that if you are using interface-oriented programming you actually want the static type checking.
I’m afraid I don’t consider assigning something of the wrong type to a variable, passing the wrong type as a method argument, etc. to be a “weird edge case” in terms of whether I’d consider something statically typed. There may be reasons for supporting this – I’m not making a value judgement of the feature – but those reasons don’t make it any more statically typed!
Also there are plenty of static analyzers for dynamic languages, so the fact that IDEs can add an additional layer of static analysis that the language doesn’t isn’t really an argument in favour of the language supporting static typing.
The interface checking is interesting. That does indeed seem to be an instance of Groovy supporting some degree of static typing. But given the sheer amount of stuff the compiler *doesn’t* check, I’m extremely skeptical of any description of groovy as statically typed.
Like I say. I’m not making a value judgement. “Not statically typed” is not necessarily a bad thing. But equally because it’s not a value judgement it has much more objective criteria and groovy just doesn’t seem to meet them.
David: I mostly agree with your sentiments. I never claimed that the assignment example demonstrated static typing in any form. I guess we need richer nomenclature. Even though Groovy has some static typing it is mostly dynamic typing. So what Tony said is mostly true just not the “never ever ever” part. And while static vs dynamic is an interesting academic debate, I guess for me it would be more interesting if we also considered within the dynamic languages the relative merits for when explicit declarative checking is performed vs inference or implicit typing.
In any case, I don’t see this as a black and white issue. I can certainly write a Java or Scala program that creates some source code, calls the compiler and invokes the result. At some level therefore, there are times when type errors with languages traditionally thought to be static are only known at runtime.
I added a Groovy example using fj to the page mentioned earlier.
Can I take a terminating subset of Groovy and prove anything remotely interesting? If there is just one example, I’ll reconsider my position.
Can you point me to an example of what you are trying to do?
Prove forall P Q. P -> Q -> P
Prove forall P Q R. (P -> Q -> R) -> (P -> Q) -> P -> R
testing
Why not apply local reasoning, e.g.:
h t t p://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-654.pdf
I’m not sure how that’s going to help me prove any interesting property with “Groovy’s cough static type system”. Maybe it is patently true that its type system (Dyn) is useless or something like that anyway?
If I am trying to prove e.g. a liveness theorem about a fragment of code (Groovy, Java, Scala or otherwise), then whether I need to infer types versus having them explicitly static only loosely impacts the approaches I might use. The functional vs imperative style can change how I might go about it, but the static vs dynamic debate impacts just a part of the interesting areas one might want to reason about. Certainly limiting yourself to a simplified domain can help with proving things provided you don’t limit yourself so far as to be living in a totally artificial world.
The “static versus dynamic debate” is as useful as the “Creationism versus Evolution debate”. Biologists merely attempt to educate scientifically illiterate people who are hungry to inadvertently demonstrate a gross failure of understanding of the natural world. This is not a debate in any useful form. I abhor pseudo-science in all its forms.
Similarly there is no such thing as “functional versus imperative style”. Although I have already spent enormous effort trying to dispel this myth (a tear drops), I will attempt to do away with it using a profound, yet absolutely true statement: Haskell is one of the most powerful imperative languages on the planet. Interestingly, I have long considered writing about anti-concepts or propositions that are “not even false” and the proliferation of these non-ideas in computer programming. This would be a perfect example that I might consider using.
I am not proving a theorem about code. Code is proving a theorem — see Curry-Howard Isomorphism.
I wonder if imagining dualities that subvert computational theory so as to not even exist limits oneself to living in a totally artificial world. Whatever the case, those Creationists at least seem to enjoy their own ignorance
It is easy to prove the halting problem. I look forward to your code.
I’m not sure what you’re saying here, but there is a very common mistake, “I cannot prove the general program, therefore, I should concede to proving correctness about any program”. Since this mistake is common (often a result of misunderstanding both the halting problem and proof writing in my anecdotes), I will assume this is what is happening. I asked earlier to prove an extremely simple program (the components of the SKI combinator calculus), which is even possible in such a useless language as Java (a subset).
Alternatively you might be saying that writing code is not proving a theorem, in which case, I advise you to prepare yourself for your Nobel Prize
I suspect this is not happening mostly due to the audaciousness of the claim.
Please clarify the misunderstanding. Like I said, I am not going to debate because there is no debate to be had (admittedly, this is slightly a lie, but I’m taking a Socratic Midwife approach here).
I have no problem with a desire to prove correctness about a program. Just a little bemused why anyone would want to always limit themselves to one style of formal theory.
“One style of formal theory”? You mean, that which is founded on decades of computing science research? I’m glad I limit myself to one reality as well. Can you imagine if all of us jumped aboard hype bubbles and starting repeating mythological nonsense to perpetuate our double-think through sheer ignorance?
Let me make something very clear; all programmers fall into one of two distinct camps:
1) Those who write logical theorems and know it
2) Those who write logical theorems and do not know it (and suffer significant adverse consequences).
This is an objective irrefutable fact that cannot be false no matter how hard you and I wish it to be so.
I’m well aware of many other logically consistent ways of observing programming and I use them all very effectively. I am also aware of the many pseudo-scientific memes that perpetuate in our industry, especially in dynamic languages (yes, even one as desperately lacking as Groovy). Indeed, I am more than capable of degenerating into a mindset that is perpetuated by these non-ideas, however, I elect not to, not out of fundamentalism, but simply because it would not be useful.
It is remarkable that my earlier analogy to Creationism (out of the many possible) was followed by an argument that is often used by Creationists! Your comment boils down to “why limit oneself to an understanding of reality, when there are so many delusions of grandeur available to indulge?”. It is as if you are advocating that I accept some alternative to reality, on the assumption that I do not understand that alternative. Let me also make this clear, I can use your dynamic language as effectively as you can, which is not very effective at all. I simply elect not to, because it offers nothing in my interest (or yours for that matter, but you don’t know that) at a significant disadvantage.
I don’t wish to sound mean and I hesitated before deciding to say what clearly needs to be said, but it would really pay for you to know what you are talking about. I say this simply because there is quite possibly a learning opportunity available. Also, it would allow this discussion to continue without silly remarks being made.
I am not bemused by your desire to limit yourself to wilful ignorance, simply because my armchair cognitive science knowledge explains why it is so, but this is another matter (George Orwell calls it double-think; I call it Cognitive Dissonance). I think discussion is going nowhere due to silly remarks (Creationists, take note), but to turn it into something meaningful, it might pay to start down a path of education. This would require an admission by yourself, even if only to yourself.
Are you aware that the untyped lambda calculus is an instance of the typed lambda calculi? Are you aware that with sufficient utilisation of a type system and for some programs, the need for unit tests disappears completely (in that, it is not only not desirable to write a unit test, but impossible because there is nothing more to say)?
Well, all I can base my comments on are a PhD in formal specification techniques and 30+ related refereed publications. That definitely doesn’t make me the world expert on lambda calculus but I certainly have bumped into it shall we say … many times. I do believe it has many uses and I use it in places myself where I find it fruitful, but my preferred weapon of choice for reasoning based exercises would have to be techniques based on Zermelo-Fränkel set theory, e.g. Z or Object-Z. I don’t see any point in debating over whether one reasoning technique is better than another – to each his own – and if the truth be known many of these techniques are but two sides of, if not the same coin, two very similar ones.
What I can say is that I have much less angst over reasoning about dynamically typed languages than you appear to have. I respect your right to your preferences but don’t really see the big deal. All the same types are still there, you may just have to infer them or apply higher order reasoning. I really don’t see what the problem is.
For me the really hard systems to reason about are the large complex ones. Functional flavoured langages and techniques give me one set of tools for finding ways to reason about smaller parts of larger systems. Imperative and constraint-based languages give me other sets of useful tools and I don’t claim that the best tools for reasoning about such languages are lambda calculus based – indeed if I tried to do that I would probably be dismayed at such languages – so I don’t.
I do agree with your comments about unit tests being theoretically undesirable in some scenarios but exemplar driven steps within your development approach are sometimes the most crucial ones as they allow you to validate your theorems and code with your customers conceptual models of your theorems and code.
Very interesting debate…. and beyond my understanding mostly
But I liked the example of “Creationism versus Evolution debate”.
I had used it in a one of my arguments but in a different context. I was just trying to draw parallel between a line of reasoning I came across and how as soon as Creationism proponents run out of their ammunition of rehearsed bullet point pseudo logics, they declare certain things are the way they are because god intended it to be so.
But that’s another story.
I followed a few FJ tutorials and found them very impressive.
But being a mere application developer with just enough understanding of Java to make it work mostly, I found the examples a little hard to grasp and replicate them in a meaningful way for me.
I build a Java TCP server for a vehicle tracking system and I was pleased with my work as it was my first attempt at socket programming as well as multi-threading and Its been working quite well apart from GC problems. But due to a new business prospect at our company I need to quickly come up with a better solution than the one I have currently, as the number of connections to the server is likely to increase by anything between a few hundred to 1-2 thousands per month.
So my current challange is to find a good vertical scaling solution before horizontal scaling so the hardware cost and maintenance/operation complexity is kept at mimimum.
I have looked at few alternatives, learn Erlang, learn Scala or other dynamic languages that run on JVM that allows me to write Actor style application, or find a solution within Java.
Since I like the third option for obvious reasons, I have looked at a couple of options.
Kilim was the first one I looked at besides others.
I like the idea behind Kilim but I’m not very comfortable with the idea of byte-code manipulation.
I’m a big fan of unobtrusive drop-in-libraries and FunctionalJava is very appealing to me in that matter.
But I find the examples a bit hard to grasp.
So, is there any chance that you could write up a quick and dirty Echo Server like example that utilises Actors to do some trivial tasks?
It would me immensely appreciated and I’m sure it will be beneficial to other people looking for alternatives to the current shared-memory thread programming.
Hello anzaan,
The aforementioned debate is far from interesting. Pseudo-intellectuals and, in this case, an inability to maintain a coherent discussion (note the original objection and the subsequent slippery slope into fallacy e.g. argument from authority) bores me to tears, hence the abandonment — some are willingly stupid, oh well!.
I’ll see what I can do regarding echo server. Keep an eye out
@tony
Thanks for the response.
I had great pleasure reading your comments and was a bit disappointed when it came to an end though
And also I was a bit disappointed to realise that out of the two programmers camps you mentioned, I unfortunately fall into the second one.
Although you mentioned that its an objective refutable fact – and I take your words for it,
I’m keeping my chins up with the help of my assumption that no empirical evidence has yet been found that says the ones from the second camp cannot cross-over to first one over time.
I’ll keep my eyes peeled on your blog due to learning opportunity available here
.
Hi anzaan,
What you are seeking is called the Curry-Howard Isomorphism. Here is an excellent introduction http://en.wikibooks.org/wiki/Haskell/The_Curry-Howard_isomorphism
Hi Tony,
Thanks for the response.
The article you pointed is a bit complex for me as I lack knowledge of ‘formal logic’ and I’ll have to gain significant knowledge in ‘type theory’ and other things the article is based on or referenes, before I’ll be able to understand and appreciate the concept fully and be able to actually put it to use. My background is IT and not Computer Science.
I got exposed to functional programming through one of your java’s ‘throws’ Monad article.
It got me interested enough to research about Monad.
And now I want more
Since you got me in this confusion in the first place, I would like you to to help me out a little
IT would be very helpful for me and newbies like me if you could write up an article on how to use FJ to create an actor-based server application with some example code.
Armed with an example I understand, it would help me explore more into functional programming and use it to solve problems better if it permits.