Reactive Actors

I've been meaning to revisit reactive programming and the actor model for a while now. I first learned about them in the Principles of Reactive Programming Coursera class and then actors came up again in the Seven Concurrency Models in Seven Weeks book. The Scala I picked up is quickly being forgotten and I haven't done a post with code in a while, so here I'll get back into that and create a simple application using Akka and RxScala.

Actor model

The developerWorks article JVM Concurrency: Acting asynchronously with Akka gives a good introduction to the actor model:

The actor model for concurrent computations builds up systems based on primitives called actors. Actors take actions in response to inputs called messages. Actions can include changing the actor's own internal state as well as sending off other messages and even creating other actors. All messages are delivered asynchronously, thereby decoupling message senders from receivers. Because of this decoupling, actor systems are inherently concurrent: Any actors that have input messages available can be executed in parallel, without restriction.

Then JVM Concurrency: Building actor applications with Akka goes on to explain the advantages of this approach:

If you compose your actors and messages correctly, you end up with a system in which most things happen asynchronously. Asynchronous operation is harder to understand than a linear approach, but it pays off in scalability. Highly asynchronous programs are better able to use increased system resources (for example, memory and processors) either to accomplish a particular task more quickly or to handle more instances of the task in parallel. With Akka, you can even extend this scalability across multiple systems, by using remoting to work with distributed actors.

At first the actor model may sound the same as what I described in my Communicating Sequential Processes post because both involve message passing, but the two concurrency models have several differences:

• Actors have identities while CSPs are anonymous
• Actors transmit messages to named actors while CSPs transmit messages using channels
• Actors transmit messages asynchronously while CSPs can't transmit a message until the sender is ready to receive it

My impression, and I could be wrong, is that actors more naturally extend beyond a single machine to a distributed system since the sending and receiving of messages is decoupled. A quick search does turn up distributed channels in pycsp, though, so it seems that both can be distributed.

Reactive applications

The Reactive Manifesto details four qualities of reactive applications:

• responsive - the system responds in a timely manner if at all possible
• resilient - the system stays responsive in the face of failure
• elastic - the system stays responsive under varying workloads
• message driven - the system relies on asynchronous message passing between components

Where Akka describes itself as a toolkit and runtime, RxScala only claims to be a library for composing asynchronous and event-based programs using observable sequences. To me it's not clear how it helps us achieve all four qualities (or if it even intends to).  Nevertheless, the ReactiveX introduction explains their advantages:

The ReactiveX Observable model allows you to treat streams of asynchronous events with the same sort of simple, composable operations that you use for collections of data items like arrays. It frees you from tangled webs of callbacks, and thereby makes your code more readable and less prone to bugs.

This means is that the methods returning Observables can be implemented using thread pools, non-blocking I/O, actors, or anything else. This is how ReactiveX and Akka will be used together: Actors are the concurrency implementation for services communicating with asynchronous messages.

Combining Akka and RxScala

I came up with the following short example. First I wrote a couple of methods returning an Observable to get a feel for it, then added the stockQuote() method which also uses an actor in it's implementation:


Running it produces the expected output, something like:

6

8

broken service

GOOG: 253.22

I can really see the potential in the Observable model, especially after reading more about it at The Netflix Tech Blog. If you were already using actors maybe combining them like this could make sense. I also need to checkout Akka Streams which seems like a similar idea.

UPDATE

Ray is a framework for parallelizing ML workloads. They use the actor model as a way of coordinating work and maintaining state.

Software Transactional Memory: Dining Philosophers

Software transactional memory (STM) is a concurrency alternative to lock-based synchronization. It is similar to database transactions except instead of modifying database records, you are modifying variables in shared memory. STM transactions are atomic (a transaction is all or nothing), consistent (all changes made from a transaction must preserve invariants), and isolated (concurrent transactions result in the same system state as transactions executed serially). Since they are in-memory they are not durable.

With STM you are separating identity from state with persistent data structures. While state is constantly changing, the current state for an identity is immutable. Changes made by one thread will not affect another with a reference to the same data structure.¹

Without locks multiple threads can also modify different parts of a data structure that would normally share the same lock. Optimistic concurrency control assumes multiple transactions can run in parallel and if wrong, they will be retried.²

Example Code

Motivated by the book Seven Concurrency Models In Seven Weeks, I have implemented the dining philosophers problem in Scala. The book uses Clojure, but ScalaSTM is inspired by the STMs in Haskell and Clojure and I am trying to get better with Scala, so this seemed like a good way to reinforce what I was reading. It turns out that a dining philosophers solution is in the ScalaSTM documentation, but nonetheless it was a worthwhile exercise.

Conclusion

Atomic variables are enough for a lot of problems and functional programming discourages mutable data anyway, but if it is simpler to use multiple mutable variables then STM might be the way to go. As always, you need to compare performance of both though.

1 http://clojure.org/state
2 https://nbronson.github.io/scala-stm/intro.html

Scala Asynchronous IO Echo Server

In previous posts Asynchronous Non-blocking I/O Java Echo Server and Fixing My Asynchronous Non-blocking IO Callback Hell With Monads, I compared using callbacks and futures/promises as concurrency alternatives to creating using a thread pool in a basic echo server. I have now decided to rewrite the server from the second post in Scala since it has better support for futures and promises than Java 8.

Tthe idiomatic way to write an echo server in Scala would be to use the actor model, but that is a topic for another day. My implementation using futures and promises still turned out to be faster than the similar Java 8 implementation (in fact roughly as fast as the true asynchronous NIO implementation) and the code is more concise.

There is still the need to block on accept, read, and write, but I also still think that is unavoidable with the AsynchronousSocketChannel API.

Memoization: Fibonacci Sequence

Memoization is an optimization technique that caches computationally expensive function calls. I first learned of it in Stanford's Algorithms class on Coursera.¹ It is more common in functional programming than object oriented programming because the function being cached can not have any side-effects, and that is, of course, often the case in functional programming. It is also commonly used by lazy data structures. The downside of memoization is that more memory will be used, but for some functions, as you will see below, it is well worth it.

A function that returns the nth Fibonacci number is the quintessential recursive function. I still remember that was the example used when I first learned of recursion. It is actually often implemented inefficiently, though, the standard recursive implementation being O(fib(n)) = 2ⁿ.

Python

Python makes memoization easy because you can decorate any function with a memoization function.

Scala

Scala does not make it that simple. Hopefully it will be built into the language in the future. This naive implementation only caches the original function call. The recursive calls do not know to use the memoized wrapper.


This blog correctly points out this problem with memoizing a recursive function and has a great technical explanation of the solution. In summary, you have to use something called a Y combinator to correctly implement the memoized wrapper function in Scala. It is basically a high-order function that returns a recursive version of a non-recursive function. I will defer to these other resources for a proper definition.


Notes

In Scala, for example, I could get up to n=45 in about 20 seconds with the standard un-memoized Fibonacci implementation. With the correctly memoized version I can run n=1000 in under 1 second because the memoized recursive implementation is O(fib(n)) = n.

The recursive Fibonacci implementation is not tail-recursive (which I covered in a previous blog), so you pretty quickly will hit a stack overflow error. In my Python implementation I even had to explicitly set the recursion limit higher than the default.

Also note the use of currying (which I also covered in a previous blog) in the nonRecursiveFibonacci Scala function.


1 I would highly recommend this class. It is better than the algorithms class I paid for to get my CS degree.

Generators: Fibonacci Sequence

A generator returns a sequence of values, but unlike with a function the values are returned one at a time. This requires less memory for representing large (possibly infinite) sequences because the entire sequence is never stored in-memory at once. The sequence is computed, one value at a time, as needed.

Python


Scala

Exploring Tail Recursion

A tail-recursive function does not require a new stack frame for each call. All the recursive calls will execute in a single frame. This is benefiitial because you do not have to worry about recursing too deeply and getting a StackOverflowError, or the overhead of the many function calls.

What makes a function tail-recursive, and not just recursive, is that the call to itself is the last operation in the function. When this happens the compiler can generate bytecodes that are the same as if the function were written with a while-loop. These two examples from Programming in Scala are not only functionally equivalent, but would be optimized to have the same bytecode:


In Scala use the @tailrec annotation so you will get a compiler error if the function's recursion can not be optimized away.

Exploring Partial Functions, Partially Applied Functions, and Currying

I'm trying to learn more about functional programming. This is the third in a series of posts about functional programming concepts with examples in Scala (and in some cases other languages too).

Partial Functions

A partial function is a function only valid over a specific range. Some functions are not valid for all input values, like asymptotic functions or those only applicable to natural numbers.


Partially Applied Functions

A partially applied function is an expression in which you don’t supply all of the arguments needed by the function.


Currying

A curried function is applied to multiple argument lists. The results are chained together. In this simple example, the 2 would be applied to x + y resulting in 2 + y. Then the 3 is applied resulting in 5.

This technique can be used to make method calls look more like native-language support. Here is a non-trivial example from Programming in Scala:

Notes

Partial functions and partially applied functions are not related, except the names are almost the same. I was confused about this when I started to research this post.

The call to partially applied functions returns immediately. Curried functions return another function in the currying chain.

Exploring Immutability

In Java theory and practice: To mutate or not to mutate?, Brian Goetz says immutable objects simplify programming. One of the reasons is that they can be shared and cached without needing to be cloned, which means they are thread-safe if written correctly, which means you can more easily take advantage of multiple cores. In Scala you could write something like List(1, 2, 3).par.map(_ * 2) and map function is applied to the list elements in parallel. That would not work if someone else was changing the contents of the list at the same time.

Thread-safety, parallelization, it all sounds great, but one of the first things I think of is that if you had large immutable collections would there not be a lot of copying going on? There would be if every time you added or deleted an element the entire collection was recreated. It turns out that does not need to happen, though, because the collection implementation can exploit the similar (immutable) structure between the old and new versions. This might mean sharing a sub-tree or sharing the tail of a list.^1,2 Compilers can potentially do additional optimizations with immutable objects as well.³

Like with anything else immutable objects do not solve all problems and can be used incorrectly. At the end of the day I see it as another tool in the toolbox. To look at how (un)natural it is to work with immutable collections, below are some Scala examples.


1 http://en.wikipedia.org/wiki/Persistent_data_structure
2 http://pragprog.com/magazines/2012-01/scala-for-the-intrigued
3 http://www.drdobbs.com/architecture-and-design/optimizing-immutable-and-purity/228700592

Closure Examples

A closure is a function plus a referencing environment that is remembered from when it was created. Below I created a simple example in three different languages for comparison. It adds two numbers where the sum is capped at a certain max value. The function adds x and y, and the referencing environment contains the max value.

Python

Scala

JavaScript


In Scala and Python closures are probably seen more often when a lambda uses values from outside its scope. In JavaScript closures are commonly used to make private-like variables and functions that do not pollute the global namespace.