1. Concurrency sparked widespread interest in functional programming. Multithreaded programming, requiring synchronized access to shared, mutable state, is the assembly language of concurrency.

    • Immutable values make synchronization unnecessary.
    Mutating state is never completely avoidable. We will examine two higher-level abstractions that provide “principled” ways to manage mutable state in thread-safe ways:

    1. i. Actors
    2. ii. Software Transactional Memory.


    The Actor Model
    In the Actor model of concurrency, work is coordinated by message passing between “actors.” Each actor has a queue, sometimes called a mailbox, for incoming messages. The actor processes each message, one at a time. Perhaps the best known implementation of actors is found in Erlang, where actors are the core of everything you do in the language.

    This metaphor of passing messages between objects is not only intuitive, it helps clarify boundaries between objects. Have you seen code where one object makes lots of little calls to other objects to get bits of information? How would you change that code if you thought in terms of message passing, instead?

    In an actor system, state mutation is handled one of several ways. For some state, it can be the responsibility of one actor to mutate that state. No other code is permitted to do so. When a mutation is required, a message is sent to the actor, which performs all such changes sequentially, thereby avoiding synchronization problems. A similar model is to allow multiple actors to modify the same state, but only one at a time. A special “semaphore” message is exchanged that tells the receiver that it is safe to modify the state. When finished, the semaphore is sent to another actor.

    Both cases run the risk of creating a bottleneck if the scope of responsibility is too large. It might be necessary to break it down into smaller, “isolated” sections. Good actor libraries are available for most languages. Perhaps the best option for Java is the Akka Java API. Following is an example from akka website:
    1. case class Greeting(who: String)
    2.  
    3. class GreetingActor extends Actor with ActorLogging {
    4. def receive = {
    5. case Greeting(who) ⇒ log.info("Hello " + who)
    6. }
    7. }
    8.  
    9. val system = ActorSystem("MySystem")
    10. val greeter = system.actorOf(Props[GreetingActor], name = "greeter")
    11. greeter ! Greeting("Charlie Parker")
    Software Transactional Memory

     Most of us have worked on “RDBMS”. They support ACID transactions. The goal of ACID transactions is to avoid logical inconsistencies in a given set of related records.  Software Transactional Memory (STM) brings transactions to locations in memory that are referenced by variables). STM can’t provide durability, because memory isn’t durable (e.g., if the power is lost), but STM can provide
    the ACI, atomicity, consistency, and isolation in ACID.

    The model in STM is to separate references to values from the values themselves. In STM, a program has a reference to a value of interest. The STM framework provides a protocol for changing the value to which the reference “points”. However, values themselves are not changed. They remain immutable. Only the references change to point to new values. Persistent Data Structures are exactly what STM needs.


      Figure below shows the state at time “0.” There are two references pointing the same value1 of a persistent data structure.


    Now let’s change ref2 to point to a new, updated value, as shown below:


    By time “1,” an STM transaction in the context of ref2 has been used to move its reference to value2, which was created from value1, as indicated by the dotted line. Creating value2 does not necessary have to occur within the transaction, just the reassignment of ref2.  This behavior allows different clients to acquire references to the same value at a particular time, but each can work with the value without fear that it will change unexpectedly, due to the actions of one of the other clients. A version with no references will be garbage collected.
    There are several STM libraries for Java, many of which are inspired by Clojure’s implementation. Akka integrates with the Multiverse STM. 

     The main intent of these concepts is to provide new and higher level of abstraction to developers. This will enable them to write better concurrent programs.


    Posted by
    Labels: actor akka multi-threading reactive programming
    0

    Add a comment


  2. Functional languages provide a core set of common data structures with combinatory operations that are very powerful for working with data. Functional algorithms emphasize declarative structure, immutable values, and side-effect-free functions. We already think of lists, maps, etc. as “collections,” all with a set of common methods. In functional programming, there are three core operations that are the basis of almost all work you do with collections:

    1. Filter -- Create a new collection, keeping only the elements for which a filter method returns true.

        2. Map –  Create a new collection where each element from the original collection is  transformed into a new value.
       
        3. Fold -- Starting with a “seed” value, traverse through the collection and use each element to build up a new final value where each element from the original collection “contributes” to the final value.

    Together they are the basis for implementing concise and composable behaviors.


                                     Persistent Data Structures

     It seems that if we want immutable values, we have to make a copy whenever we change
    a value. While this may be fine for small objects, it will be too expensive for large objects,
    like long lists and large maps.
    Fortunately, we can have both immutability and acceptable performance if we only allocate memory for what is actually changing and we share the unchanged parts with the original object. This approach is called structure sharing. Tree data structures provide the balance of performance and space efficiency required to do this. The public abstraction might still be a List, a Map, or another data structure.

    Unbalanced binary trees provide average O(log2(N)) search times (unless the tree is really unbalanced). Real persistent data structures often use one of several 16- or 32-way balanced tree variants to further reduce search times and to optimize other performance goals.

    Example: Tree at time “0”, referenced as an object named Value1



    Now imagine a user wants to create a new tree that prunes off nodes a1 and its left branch, node a2, but keep node a3 and its right branch, node a4. All we have to do is create a new root node that points to a3 as its left branch and b1 as its right branch.

    Note that a history of the evolving values is being maintained. We still have value1 and as long as some code has a reference to it, it won’t be garbage collected. This is why these data structures are called persistent.

     Interest in Domain-Specific Languages is another recent, popular trend. DSLs try to capture the idiomatic language used by domain experts directly in the code. You can implement DSLs in both object oriented
    and functional languages. it can be useful to represent a domain with a DSL at the upper levels of abstraction, but questionable to create explicit object representations under this surface. We can have a DSL that says, for example groupUsersByDomain in emailAddresses, but implement it with List<EmailAddresses>.foldLeft(new HashMap<…>(), groupingFunction);

    As I said in my earlier blog post, objects operate at the wrong level of abstraction and they lack a standard set of protocols that are essential for the kind of reuse we want. The core data structures of functional programming and the combinators like filter, map, and fold bring us closer to that ideal.


    Posted by
    0

    Add a comment

Blog Archive
Blog Archive
About Me
About Me
My Photo
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.