Last time, I wrote about the high-level ideas behind the Scala libraries akka and spray, namely the concept of reactive programming in order to meet the demands of modern applications. I finally got the chance to play around a bit with spray in order to get a feel for how the theory of event-driven, asynchronous programming manifests itself in code. I started with a very simple web application that takes a stock ticker symbol and uses the Yahoo Query Language (YQL) to look up basic quote information for the company (using this endpoint). Here's some code for a trait that uses spray-http and spray-client to execute a request against the Yahoo API:
You'll notice that I included all of the necessary imports in the example (I normally leave them out), and this is because a lot of things look nicer once imported (e.g. GET vs HttpMethods.GET) and spray uses implicits quite extensively to expose a nice domain-specific language (DSL). So knowing what the imports are is actually pretty important for figuring out why the code actually compiles and works properly. Now let's break down the code. The request method is the simplest part, and all it does is take in the YQL query and construct an HTTP request with the appropriate URL and parameters. Spray has some convenient methods for making this easy, but there's nothing too special involved.
The executeQuery method is where all the magic happens. To understand it, we'll need to revisit two concepts: futures and actors. Futures are the Scala way of expressing a value that is computed asynchronously. In this case, executeQuery returns a future because, per the reactive programming principles, we do not want to block the thread while waiting for the request to be sent and the response to be received over the network. This means that when the method returns, it is most likely that the response has not come back, so whoever consumes the result of the future will need to wait for it (e.g. using Await). Actors are an abstraction for handling asynchronous computations using a messaging model; you send messages to an actor, which does some computation based on the contents of the message and potentially returns a result. In this case, we have an implicit ActorSystem that is used by spray-client to run an actor which receives the HttpRequest and returns an HttpResponse. The sendReceive method conveniently encapsulates all of this functionality.
Here is our YQL client in action:
Since this is a test, we define a test ActorSystem to use and then use Await to get the response from the future, but when integrated with spray-can (the HTTP server) it becomes much nicer. In contrast to the Java servlet model where we would have many threads all probably blocked on the network, spray encourages everything to be asynchronous and utilizes a small pool of threads. To that end, the "controllers" you define in spray-can allow futures to be returned and automatically map them to HTTP responses, so any request that requires asynchronous processing will naturally result in a future that is handled entirely by the underlying abstraction. Next time, we'll see how to layer other pieces such as JSON and error handling on top of futures in spray.
Showing posts with label scala. Show all posts
Showing posts with label scala. Show all posts
Thursday, November 28, 2013
Sunday, November 17, 2013
Reactive Programming
There's an interesting idea being pushed forward by the Scala community about the way systems should be built, and it's called reactive programming. The reactive manifesto gives a nice summary of their views on the future of distributed applications and how the way we programmed ten years ago is inadequate in this future. Because of the changing landscape of latency expectations, data scale, and hardware improvements, going forward, systems must be event-driven, scalable, resilient, and responsive in order to meet user needs. There is a significant amount of ongoing Scala development in order to build tools that allow programmers to achieve these properties easily. This is the goal of the akka and spray projects.
The reactive programming model being adopted is based on actors. Given that I am a huge fan of the actor model for how it deals with the problems of concurrency, it is great to see an entirely new ecosystem developing around actors. The Scala community has really invested in actors as the new way in which communication between systems (or even within them) will be done in the future. From some slides for a recent talk on akka and spray, actors are part of a different programming paradigm that is "well-suited for building reactive systems" because they inherently shun the root of all concurrency evil, shared mutable state. Specifically, using actors versus the old model of managing threads in servlets gets around the high overhead of such management as well as the difficulties of synchronizing state. In some ways, we can view this as the next step in lightweight request handling: it was once (and still sometimes is) the case that each HTTP request would spawn a process, but that was greatly improved upon by having many threads within a single process handle requests. With actors, a single thread can handle many requests at the same time, allowing the resources to be much more efficiently utilized (this is the premise behind Node.js as well).
Spray is what you would expect the HTTP stack to look like on top of akka. While I haven't played with it myself, the code examples show that requests are mapped directly to actor messages, so everything is under the unified model of message handling. Judging from this, they have done a pretty good job from a performance standpoint as well, indicating just how lightweight request handling is in spray. Akka and spray together form a solid foundation on which you can build an application that conforms to the principles behind reactive programming. It is exciting to see technology evolving to meet the needs of users, programmers, and applications, and I'm sure that in a few years we'll see how far this paradigm can take us.
The reactive programming model being adopted is based on actors. Given that I am a huge fan of the actor model for how it deals with the problems of concurrency, it is great to see an entirely new ecosystem developing around actors. The Scala community has really invested in actors as the new way in which communication between systems (or even within them) will be done in the future. From some slides for a recent talk on akka and spray, actors are part of a different programming paradigm that is "well-suited for building reactive systems" because they inherently shun the root of all concurrency evil, shared mutable state. Specifically, using actors versus the old model of managing threads in servlets gets around the high overhead of such management as well as the difficulties of synchronizing state. In some ways, we can view this as the next step in lightweight request handling: it was once (and still sometimes is) the case that each HTTP request would spawn a process, but that was greatly improved upon by having many threads within a single process handle requests. With actors, a single thread can handle many requests at the same time, allowing the resources to be much more efficiently utilized (this is the premise behind Node.js as well).
Spray is what you would expect the HTTP stack to look like on top of akka. While I haven't played with it myself, the code examples show that requests are mapped directly to actor messages, so everything is under the unified model of message handling. Judging from this, they have done a pretty good job from a performance standpoint as well, indicating just how lightweight request handling is in spray. Akka and spray together form a solid foundation on which you can build an application that conforms to the principles behind reactive programming. It is exciting to see technology evolving to meet the needs of users, programmers, and applications, and I'm sure that in a few years we'll see how far this paradigm can take us.
Sunday, November 10, 2013
For Comprehensions
In Scala, the concept of a "for loop" doesn't really exist. Instead, we get "for comprehensions," which cover for loops, foreach loops, and more as we will see. Suppose you have the following line of Scala:
for (i <- 0 until 10) yield i
It looks roughly like a for loop with some syntactic sugar. But as I mentioned, Scala doesn't have for loops, and this code actually gets translated by the compiler into
(0 until 10).map(i => i)
The until method is part of the RichInt class, and an implicit conversion from Int to RichInt is available by default in Scala. (0 until 10) produces a Range, and the result of the entire expression is an IndexedSeq[Int]. But what's so interesting about the fact that Scala translates for loops into map calls? It turns out that this translation is generic, i.e. not specific to a certain set of classes like collections. So we can write our own class that exposes a map method and leverage the syntactic sugar of for comprehensions. Here's an example based on a Sequence trait that represents an infinite sequence of integers:
A Sequence only knows how to do two things: get the element at some index and map to a new sequence using a function. We have two simple types of sequences, namely the ArithmeticSequence (whose name should be self-descriptive), and the MappedSequence that takes another sequence and applies a function to each element. The implementations of the two should be straightforward to understand. Now comes the interesting part: because we have implemented the map method, we can use the for comprehension syntax on our Sequence classes.
We start out with a simple ArithmeticSequence, but then we create a new sequence (using a for comprehension) in which every element is squared. And then we create a third sequence which replaces all of the odd elements of the second sequence with 0. All three of these are infinite sequences that we can access random elements of, as demonstrated in the final line.
What I've shown here is a primitive example of how for comprehensions can be leveraged by custom classes in Scala. This functionality was brought to my attention in the first week of the reactive programming class on Coursera, which is taught by some of the most knowledgeable Scala folks (including the designer of the language!). It turns out that the map method lets you do simple thing like what I did, but if you implement flatMap and filter, you can do arbitrarily complex for comprehensions with multiple variables and conditionals just like you would with collections. This is a good example of an aspect I like about Scala's philosophy, which is to generalize concepts as much as possible. While many languages treat for loops as their own special construct, Scala simply makes them syntactic sugar for a much richer class of functionality.
for (i <- 0 until 10) yield i
It looks roughly like a for loop with some syntactic sugar. But as I mentioned, Scala doesn't have for loops, and this code actually gets translated by the compiler into
(0 until 10).map(i => i)
The until method is part of the RichInt class, and an implicit conversion from Int to RichInt is available by default in Scala. (0 until 10) produces a Range, and the result of the entire expression is an IndexedSeq[Int]. But what's so interesting about the fact that Scala translates for loops into map calls? It turns out that this translation is generic, i.e. not specific to a certain set of classes like collections. So we can write our own class that exposes a map method and leverage the syntactic sugar of for comprehensions. Here's an example based on a Sequence trait that represents an infinite sequence of integers:
A Sequence only knows how to do two things: get the element at some index and map to a new sequence using a function. We have two simple types of sequences, namely the ArithmeticSequence (whose name should be self-descriptive), and the MappedSequence that takes another sequence and applies a function to each element. The implementations of the two should be straightforward to understand. Now comes the interesting part: because we have implemented the map method, we can use the for comprehension syntax on our Sequence classes.
We start out with a simple ArithmeticSequence, but then we create a new sequence (using a for comprehension) in which every element is squared. And then we create a third sequence which replaces all of the odd elements of the second sequence with 0. All three of these are infinite sequences that we can access random elements of, as demonstrated in the final line.
What I've shown here is a primitive example of how for comprehensions can be leveraged by custom classes in Scala. This functionality was brought to my attention in the first week of the reactive programming class on Coursera, which is taught by some of the most knowledgeable Scala folks (including the designer of the language!). It turns out that the map method lets you do simple thing like what I did, but if you implement flatMap and filter, you can do arbitrarily complex for comprehensions with multiple variables and conditionals just like you would with collections. This is a good example of an aspect I like about Scala's philosophy, which is to generalize concepts as much as possible. While many languages treat for loops as their own special construct, Scala simply makes them syntactic sugar for a much richer class of functionality.
Sunday, September 8, 2013
Actors and Error Handling
In addition to the basic model of actors, Erlang has another core language construct that is intended to help programmers build reliable systems. It has built-in support for various forms of error handling in the context of Erlang processes. For example, a single process will often rely on the assumption that various other processes that it depends on are available and will stop functioning properly if any of those processes fail. In many other languages, because the concept of disjoint processes is not fundamental, handling such failures is generally ad-hoc and often ignored by programmers until something unexpected happens. But in the actor model and especially when blurring the line between local and remote processes, it is necessary to treat external process failures as an expected outcome that can ideally be recovered from. As such, Erlang provides three primitives with which to build robust systems of processes: links, traps, and monitors.
Links are a way of specifying a hard dependency between two processes: if one of them dies, the other cannot function and thus should die as well. They can be used to set up groups of processes which correspond to some meaningful entity in the system that requires each of the individual processes to be running properly. When processes are linked and one dies, it sends a specific 'EXIT' message to the other that isn't received or caught by the normal messaging and exception handling constructs (instead killing the receiving process) unless some specific measures are taken. This leads us to the concept of traps, which are a method by which you can explicitly handle an exit message from a linked process. If two processes are linked without either of them trapping the exit messages, they will die together. But if, for example, you have a process which is dedicated to monitoring a group of other processes, this process can decide to receive exit messages and act accordingly when they are received, e.g. restarting the entire group of processes. Links and traps allow programmers to specify entities in a system that continue operate after failures.
The final piece of Erlang error handling is the ability to monitor other processes. This is similar to links except that monitors are unidirectional and stackable, meaning that you can compose them more easily and that they work better with libraries. Moreover, you do not need to trap the 'DOWN' messages that the monitored process sends; they are received as normal messages since there is no implicit process kill involved (unidirectional means there is no tight coupling between the processes). Monitors are a more flexible way for processes to communicate their errors to each other without linking their fates together. Between these three simple primitives for error handling, it is possible to construct systems that respond well to failure and can self-recover, leading to claims such as Joe Armstrong's (the creator of Erlang) nine 9's of reliability in the Ericsson AXD301.
As with the actor model, Scala's Akka library provides some similar functionality to Erlang's error handling, which is the concept of supervision. In some sense, Akka supervision is a stricter version of links and monitors, where every actor must be supervised by some other actor, its parent, so that the set of all actors forms a hierarchy (the root actor is provided by the library). The supervising actor can employ different strategies for monitoring the lifecycle of each of its child actors, which often involves restarting failed actors. While not quite as flexible as Erlang error handling, the way Akka enforces the actor hierarchy leads programmers to naturally structure their systems as a hierarchical tree of components that can either function independently of failures in other parts of the hierarchy or propagate/handle errors as necessary. Building concurrent and distributed systems requires serious consideration of errors and failures, but it's often the case that there are no good tools for doing so. Erlang's ideas and Akka's adaptation of them are examples of how this problem can be tackled at a first-class level.
Links are a way of specifying a hard dependency between two processes: if one of them dies, the other cannot function and thus should die as well. They can be used to set up groups of processes which correspond to some meaningful entity in the system that requires each of the individual processes to be running properly. When processes are linked and one dies, it sends a specific 'EXIT' message to the other that isn't received or caught by the normal messaging and exception handling constructs (instead killing the receiving process) unless some specific measures are taken. This leads us to the concept of traps, which are a method by which you can explicitly handle an exit message from a linked process. If two processes are linked without either of them trapping the exit messages, they will die together. But if, for example, you have a process which is dedicated to monitoring a group of other processes, this process can decide to receive exit messages and act accordingly when they are received, e.g. restarting the entire group of processes. Links and traps allow programmers to specify entities in a system that continue operate after failures.
The final piece of Erlang error handling is the ability to monitor other processes. This is similar to links except that monitors are unidirectional and stackable, meaning that you can compose them more easily and that they work better with libraries. Moreover, you do not need to trap the 'DOWN' messages that the monitored process sends; they are received as normal messages since there is no implicit process kill involved (unidirectional means there is no tight coupling between the processes). Monitors are a more flexible way for processes to communicate their errors to each other without linking their fates together. Between these three simple primitives for error handling, it is possible to construct systems that respond well to failure and can self-recover, leading to claims such as Joe Armstrong's (the creator of Erlang) nine 9's of reliability in the Ericsson AXD301.
As with the actor model, Scala's Akka library provides some similar functionality to Erlang's error handling, which is the concept of supervision. In some sense, Akka supervision is a stricter version of links and monitors, where every actor must be supervised by some other actor, its parent, so that the set of all actors forms a hierarchy (the root actor is provided by the library). The supervising actor can employ different strategies for monitoring the lifecycle of each of its child actors, which often involves restarting failed actors. While not quite as flexible as Erlang error handling, the way Akka enforces the actor hierarchy leads programmers to naturally structure their systems as a hierarchical tree of components that can either function independently of failures in other parts of the hierarchy or propagate/handle errors as necessary. Building concurrent and distributed systems requires serious consideration of errors and failures, but it's often the case that there are no good tools for doing so. Erlang's ideas and Akka's adaptation of them are examples of how this problem can be tackled at a first-class level.
Monday, August 5, 2013
Local vs Remote
While reading through the Akka documentation (the actor and remoting library for Scala), I once again came across a reference to the classic distributed systems paper from Sun discussing the difficulty of unifying local and remote programming models. I briefly touched on the content of the paper in a previous post, but it's worth revisiting in the context of concurrent programming and understanding how the actor model works in a distributed system. With Akka actors, like in Erlang, the programming model revolves entirely around message passing and asynchronous processing even for actors running within the same Java Virtual Machine (JVM). This blurs the line between whether you are sending messages to a local actor and a remote actor, but it is arguably done in the "correct" way. So it is interesting to understand what the difference is between the actor model and other attempts at such unification, e.g. remote procedure calls (RPC), which are generally considered to be less than ideal (although still widely used).
Firstly, we need to recap the four points brought up in the paper that supposedly doom a unified local and remote object-oriented model. They are latency, memory access, partial failure, and concurrency. Latency and memory access are fairly straightforward; because the object on which a method is called lives in a different address space on a remote machine, the method call is going to be much slower and memory accesses have to be managed in some meaningful way across multiple machines. Partial failure refers to the fact that there are multiple components that can fail independently of each other (e.g. the network and the remote entity), which can cause the method call to be in an unknown or perhaps even inconsistent state. Lastly, the issue of concurrency arises because there is no shared synchronization system which can mange the order of method calls on an object, so the programmer must be aware of the fact that an object can receive multiple method calls simultaneously. These points can typically be alleviated by a well-designed RPC library and being diligent in distinguishing local and remote invocations, but that is essentially the argument being made, that in practice they are not truly unified.
So then the question is how the actor model is different and why interacting with local and remote actors can be done in a mostly unified way. The problems of latency and concurrency are non-issues in the actor model because of the asynchronous design and the fact that each actor is processing a single message at a time. And assuming that actors have no shared state and communicate exclusively through the immutable messages passed between them, we can avoid confusing memory access semantics as well. Partial failure is, again, the most complex of the issues, and the actor model itself does not prescribe specific guarantees about message processing, such as idempotence, so it is still left to the programmer to figure out how to keep the system consistent. Regardless, we can see that actors, by design, are better suited for a unified local and remote model since they greatly reduce the space of potential problems to worry about. The corollary, however, is that local operations are more complex due to the way in which communicating between actors and sharing state is restricted, but I am not entirely convinced that this is a bad thing in light of the difficulty of multithreaded programming.
The more I learn about actors, the more optimistic I become about their potential to make concurrent programming less of a disaster. The Akka project is really interesting and gives Scala one more feature that is very much lacking in Java; the mere possibility that synchronized blocks and semaphores can be avoided altogether is enough to motivate me to pursue understanding Akka. Given that the future only holds more concurrent and distributed programming, I feel like programmers should be much better educated about the alternatives to traditional, error-prone multithreading.
Firstly, we need to recap the four points brought up in the paper that supposedly doom a unified local and remote object-oriented model. They are latency, memory access, partial failure, and concurrency. Latency and memory access are fairly straightforward; because the object on which a method is called lives in a different address space on a remote machine, the method call is going to be much slower and memory accesses have to be managed in some meaningful way across multiple machines. Partial failure refers to the fact that there are multiple components that can fail independently of each other (e.g. the network and the remote entity), which can cause the method call to be in an unknown or perhaps even inconsistent state. Lastly, the issue of concurrency arises because there is no shared synchronization system which can mange the order of method calls on an object, so the programmer must be aware of the fact that an object can receive multiple method calls simultaneously. These points can typically be alleviated by a well-designed RPC library and being diligent in distinguishing local and remote invocations, but that is essentially the argument being made, that in practice they are not truly unified.
So then the question is how the actor model is different and why interacting with local and remote actors can be done in a mostly unified way. The problems of latency and concurrency are non-issues in the actor model because of the asynchronous design and the fact that each actor is processing a single message at a time. And assuming that actors have no shared state and communicate exclusively through the immutable messages passed between them, we can avoid confusing memory access semantics as well. Partial failure is, again, the most complex of the issues, and the actor model itself does not prescribe specific guarantees about message processing, such as idempotence, so it is still left to the programmer to figure out how to keep the system consistent. Regardless, we can see that actors, by design, are better suited for a unified local and remote model since they greatly reduce the space of potential problems to worry about. The corollary, however, is that local operations are more complex due to the way in which communicating between actors and sharing state is restricted, but I am not entirely convinced that this is a bad thing in light of the difficulty of multithreaded programming.
The more I learn about actors, the more optimistic I become about their potential to make concurrent programming less of a disaster. The Akka project is really interesting and gives Scala one more feature that is very much lacking in Java; the mere possibility that synchronized blocks and semaphores can be avoided altogether is enough to motivate me to pursue understanding Akka. Given that the future only holds more concurrent and distributed programming, I feel like programmers should be much better educated about the alternatives to traditional, error-prone multithreading.
Sunday, June 23, 2013
HashCode "Randomness"
The basis of this post is a very confusing bug I ran into recently involving what appeared to be nondeterministic behavior in a program that has no explicit randomness. Consider the following example:
It looks innocent enough, but when you run it there is a very good chance it will not print out the same number all three times. Set data structures generally do not give you any guarantees as to the ordering of the elements, but Scala's HashSet also does not have any randomness, so the question remains as to why the head of the set would be different each time. Java veterans should be cringing by now at the fact that we are putting an object that does not override the equals() and hashCode() methods into a hash data structure, one of the basic rules of Java collections. And that is indeed the reason for the "nondeterministic" behavior we observe; the JVM's default hash code implementation can return basically anything (but tries to return unique numbers), so depending on the values of the hash codes for each instance of Foo that we create, the set may (and does) order them differently.
As it does with many confusing things in Java, Scala has ways of helping you out here. In the above code example, if we turn Foo into a case class, the same value will be printed every time. This is because case classes automatically have equals() and hashCode() implemented so you do not have to worry about doing it yourself, which is a good argument for making simple value wrapper classes always be case classes (not to mention the nice pattern matching functionality you get). For reference, the automatically generated hash code for case classes can be found here; it is an implementation of the MurmurHash algorithm using the hash codes for each of the fields in the class. So the hash code of the Foo case class is stable across different instances of the JVM as long as Scala does not change the implementation (which they could very well do).
In the end, this turned out to be just a lesson in Java basics brought to light by some old, convoluted code that I came across. It does make me wonder whether the Java and/or Scala compilers could emit a warning when they detect objects being put into a hash data structure without overriding equals() and hashCode() because I am sure that would save a lot of headaches. There is definitely a limit to how much can be done through static analysis, but perhaps a combination of that and runtime checks could do the trick.
It looks innocent enough, but when you run it there is a very good chance it will not print out the same number all three times. Set data structures generally do not give you any guarantees as to the ordering of the elements, but Scala's HashSet also does not have any randomness, so the question remains as to why the head of the set would be different each time. Java veterans should be cringing by now at the fact that we are putting an object that does not override the equals() and hashCode() methods into a hash data structure, one of the basic rules of Java collections. And that is indeed the reason for the "nondeterministic" behavior we observe; the JVM's default hash code implementation can return basically anything (but tries to return unique numbers), so depending on the values of the hash codes for each instance of Foo that we create, the set may (and does) order them differently.
As it does with many confusing things in Java, Scala has ways of helping you out here. In the above code example, if we turn Foo into a case class, the same value will be printed every time. This is because case classes automatically have equals() and hashCode() implemented so you do not have to worry about doing it yourself, which is a good argument for making simple value wrapper classes always be case classes (not to mention the nice pattern matching functionality you get). For reference, the automatically generated hash code for case classes can be found here; it is an implementation of the MurmurHash algorithm using the hash codes for each of the fields in the class. So the hash code of the Foo case class is stable across different instances of the JVM as long as Scala does not change the implementation (which they could very well do).
In the end, this turned out to be just a lesson in Java basics brought to light by some old, convoluted code that I came across. It does make me wonder whether the Java and/or Scala compilers could emit a warning when they detect objects being put into a hash data structure without overriding equals() and hashCode() because I am sure that would save a lot of headaches. There is definitely a limit to how much can be done through static analysis, but perhaps a combination of that and runtime checks could do the trick.
Thursday, June 13, 2013
Scala Closures and Vars
One of the interesting choices that the designers of Scala made is how to deal with accessing mutable local variables from closures. For example, considering the following snippet:
The code is straightforward, and it is easy to see that the value 1 will be printed. What is interesting is that the foo method has a mutable local variable (var) i which is referenced from the closure f. For those of you familiar with Java, you'll know that the equivalent is prohibited; if you create an anonymous inner class in a method (what closures are in Scala) you can only refer to final variables (vals in Scala) from the local scope. That is because any such class you create has unknown scope as it lives on the heap, which means you cannot assume that the locally scoped variable will be around for the lifetime of the class. While it may be a sensible restriction, it is also the source of much confusion for beginning Java programmers who are creating classes local to the current scope and cannot understand the error. As such, Scala lifts this restriction in order to simplify things for developers.
The problem that Java avoids is still there, though. Scala has to do something under the hood to ensure that running the closure always works even if the variable has gone out of scope. The solution is to move the variable to the heap and put it in a mutable wrapper, which in the case of integers is the IntRef class. So instead of creating an integer on the stack, the line var i = 0 actually creates an IntRef on the heap which closures then capture references to. All direct references to the variable (both reads and writes) are replaced with indirect references through the wrapper, which ensures that the local method as well as closures will all see each others' modifications. Easy enough, right?
Well, the designers of Java were probably smart enough to figure something like this out themselves, yet they did not choose to. One good reason is that shared mutable state is a very tricky thing in concurrent environments. Consider the following variation on the above code:
Now instead of running f inline we spawn a thread that runs it. All sorts of alarms and warning bells should be going off in your head when you see this code, as there are now two threads potentially accessing an unsynchronized variable. And there is no way to determine whether 0 or 1 will be printed when you call foo since you have a race condition due to unsafe accessing of the variable i. Now you might think this example is contrived, but it could be that you pass the closure to some other method which, deep in the internals of its implementation, runs the closure on some other thread. Allowing references to local variables in closures throws away the invariant that you never need to synchronize access to local variables and essentially makes them as "dangerous" as instance variables. So while Scala simplifies some natural use cases it has also potentially opened up a can of worms with the types of subtle concurrent access bugs that can now affect local variables.
The code is straightforward, and it is easy to see that the value 1 will be printed. What is interesting is that the foo method has a mutable local variable (var) i which is referenced from the closure f. For those of you familiar with Java, you'll know that the equivalent is prohibited; if you create an anonymous inner class in a method (what closures are in Scala) you can only refer to final variables (vals in Scala) from the local scope. That is because any such class you create has unknown scope as it lives on the heap, which means you cannot assume that the locally scoped variable will be around for the lifetime of the class. While it may be a sensible restriction, it is also the source of much confusion for beginning Java programmers who are creating classes local to the current scope and cannot understand the error. As such, Scala lifts this restriction in order to simplify things for developers.
The problem that Java avoids is still there, though. Scala has to do something under the hood to ensure that running the closure always works even if the variable has gone out of scope. The solution is to move the variable to the heap and put it in a mutable wrapper, which in the case of integers is the IntRef class. So instead of creating an integer on the stack, the line var i = 0 actually creates an IntRef on the heap which closures then capture references to. All direct references to the variable (both reads and writes) are replaced with indirect references through the wrapper, which ensures that the local method as well as closures will all see each others' modifications. Easy enough, right?
Well, the designers of Java were probably smart enough to figure something like this out themselves, yet they did not choose to. One good reason is that shared mutable state is a very tricky thing in concurrent environments. Consider the following variation on the above code:
Now instead of running f inline we spawn a thread that runs it. All sorts of alarms and warning bells should be going off in your head when you see this code, as there are now two threads potentially accessing an unsynchronized variable. And there is no way to determine whether 0 or 1 will be printed when you call foo since you have a race condition due to unsafe accessing of the variable i. Now you might think this example is contrived, but it could be that you pass the closure to some other method which, deep in the internals of its implementation, runs the closure on some other thread. Allowing references to local variables in closures throws away the invariant that you never need to synchronize access to local variables and essentially makes them as "dangerous" as instance variables. So while Scala simplifies some natural use cases it has also potentially opened up a can of worms with the types of subtle concurrent access bugs that can now affect local variables.
Thursday, May 23, 2013
Structural Typing
Scala tries very hard to feel like a dynamic language despite the fact that it is rooted in the statically-typed Java Virtual Machine (JVM). One of the ways in which it does so is through a language feature called structural typing. If you have ever used Python, Ruby, JavaScript, or a number of other languages, you are probably familiar with duck typing; that is, "[if it] walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck." Because these languages are dynamically-typed, you can write code that calls any method on an object, and at run-time the code can potentially crash if it turns out that the object does not have that method (i.e. it is not a duck). The beauty of the statically-typed world is that this is (nearly) impossible because the compiler will ensure that everything checks out before allowing you to continue. The drawback, then, is that even if you know an object has a particular method, unless its type at compile-time has that method you cannot call it. Structural typing is a way of alleviating this restriction.
Let's look at a quick example with two Java classes: PrintStream and PrintWriter. As it turns out, they both have the methods println(String s) and flush(). Unfortunately, they share no common superclass or interface that has these methods, so if we wanted to write a method that relies only on an object's ability to print and flush, we would need two separate such methods, one for PrintStream and one for PrintWriter. The pure Java solution is to add an interface with println(String s) and flush() and make both PrintWriter and PrintStream implement them; that would work if you owned both classes or could modify the core Java libraries, but for most people that is not an option. Structural typing is essentially a way to emulate that behavior without actually modifying the classes. Let's see how this looks:
So we define a new "type" called Printer, which has exactly those two methods on it. Then we can write the printAndFlush() method that takes in a Printer and knows at compile-time that both the print and flush methods must exist on any object that is passed in. At the end we call printAndFlush() once with a PrintStream and once with a PrintWriter, achieving our goal. Again, the important thing to realize is that type safety is still guaranteed at compile-time, i.e. that any type passed in does indeed have those two methods, so it impossible for printAndFlush() to throw an exception saying that one of the methods does not exist.
An interesting question is how Scala manages to make structural types work in the JVM, which is based on a purely nominal type system (like Java itself). The method signature must have a named type for its parameter where no such type exists, so what do you do? The answer is a little underwhelming: it turns out that the Scala compiler throws away the structural type information after verifying type safety and the method signature in the bytecode takes in an Object. That means that the actual method call is dispatched via reflection and thus has a number of problems ranging from performance to reliability, which is quite disappointing. Fortunately, Java 7 has a new feature known as invokedynamic which is designed to help with dynamic method invocations much like those introduced by structural types, so we can hope that in the future reflection will no longer be needed to support this feature. Scala and other JVM-based languages really push the limits of what the JVM can do, and it's great to see that it is evolving to meet these challenges; one can imagine that someday a language which is not Java becomes the primary interface to the JVM, leveraging the decades of hard work that have gone into it.
Let's look at a quick example with two Java classes: PrintStream and PrintWriter. As it turns out, they both have the methods println(String s) and flush(). Unfortunately, they share no common superclass or interface that has these methods, so if we wanted to write a method that relies only on an object's ability to print and flush, we would need two separate such methods, one for PrintStream and one for PrintWriter. The pure Java solution is to add an interface with println(String s) and flush() and make both PrintWriter and PrintStream implement them; that would work if you owned both classes or could modify the core Java libraries, but for most people that is not an option. Structural typing is essentially a way to emulate that behavior without actually modifying the classes. Let's see how this looks:
So we define a new "type" called Printer, which has exactly those two methods on it. Then we can write the printAndFlush() method that takes in a Printer and knows at compile-time that both the print and flush methods must exist on any object that is passed in. At the end we call printAndFlush() once with a PrintStream and once with a PrintWriter, achieving our goal. Again, the important thing to realize is that type safety is still guaranteed at compile-time, i.e. that any type passed in does indeed have those two methods, so it impossible for printAndFlush() to throw an exception saying that one of the methods does not exist.
An interesting question is how Scala manages to make structural types work in the JVM, which is based on a purely nominal type system (like Java itself). The method signature must have a named type for its parameter where no such type exists, so what do you do? The answer is a little underwhelming: it turns out that the Scala compiler throws away the structural type information after verifying type safety and the method signature in the bytecode takes in an Object. That means that the actual method call is dispatched via reflection and thus has a number of problems ranging from performance to reliability, which is quite disappointing. Fortunately, Java 7 has a new feature known as invokedynamic which is designed to help with dynamic method invocations much like those introduced by structural types, so we can hope that in the future reflection will no longer be needed to support this feature. Scala and other JVM-based languages really push the limits of what the JVM can do, and it's great to see that it is evolving to meet these challenges; one can imagine that someday a language which is not Java becomes the primary interface to the JVM, leveraging the decades of hard work that have gone into it.
Sunday, March 31, 2013
REPL Fun
A major complaint about Java in the context of today's programming languages is that you need to go through the full process of writing a class with a main method, compiling it, and then executing it just to run a single line of code. As such, one of the most useful features of Scala is the REPL (read-eval-print loop) because it gives you that scripting language feel and allows for very quick experimentation. I decided to play around a bit with the innards of the Scala REPL, whose implementation lives in the scala-compiler jar. Because the classes used to build the REPL are exposed, there are some interesting possibilities for programmatically examining and altering the environment.
The main class that the REPL uses is ILoop, which I imagine stands for "interpreter loop" or something to that effect. It is quite simple to embed the normal REPL into our own program, like this:
If you run this code, you'll be presented with the standard prompt that you see when you launch the REPL (note that without the jline library you won't get command history, tab completion, etc, but the compile-and-run functionality is there). It is running with the same classpath as your program, so any classes you have defined are available in the interpreter. Let's do something a bit more complex; what if we want to programmtically initialize the interpreter environment, e.g. to have certain variables pre-defined or classes pre-imported? We can extend the ILoop class and override the postInitialization() method where we can handle the newly created IMain object, which is the actual interpreter:
Here, we bind the variable SomeConstant to have value 42, pre-import the Foo class, and print out the list of symbols defined by the interpreter. Because we have access to the interpreter object, it is easy to see how you could set up the proper environment with the interpreter and make Domain-Specific Languages (DSLs) even more natural. When you start the custom ILoop from above, we see the following output:
So our constant is defined, the Foo class is imported, and we see that the two defined symbols in the interpreter environment are SomeConstant and this special $intp variable. It turns out that this is a reference to the actual interpreter object that we had earlier, which lets us do crazy meta things like interpret a line of code which interprets a line of code. Here's a transcript from the interpreter environment:
So we see that the implementation of the Scala REPL is quite extensible in terms of altering the environment from code. I think there are a lot of applications of this, especially when using Scala outside of the traditional software engineering environment.
The main class that the REPL uses is ILoop, which I imagine stands for "interpreter loop" or something to that effect. It is quite simple to embed the normal REPL into our own program, like this:
If you run this code, you'll be presented with the standard prompt that you see when you launch the REPL (note that without the jline library you won't get command history, tab completion, etc, but the compile-and-run functionality is there). It is running with the same classpath as your program, so any classes you have defined are available in the interpreter. Let's do something a bit more complex; what if we want to programmtically initialize the interpreter environment, e.g. to have certain variables pre-defined or classes pre-imported? We can extend the ILoop class and override the postInitialization() method where we can handle the newly created IMain object, which is the actual interpreter:
Here, we bind the variable SomeConstant to have value 42, pre-import the Foo class, and print out the list of symbols defined by the interpreter. Because we have access to the interpreter object, it is easy to see how you could set up the proper environment with the interpreter and make Domain-Specific Languages (DSLs) even more natural. When you start the custom ILoop from above, we see the following output:
So our constant is defined, the Foo class is imported, and we see that the two defined symbols in the interpreter environment are SomeConstant and this special $intp variable. It turns out that this is a reference to the actual interpreter object that we had earlier, which lets us do crazy meta things like interpret a line of code which interprets a line of code. Here's a transcript from the interpreter environment:
So we see that the implementation of the Scala REPL is quite extensible in terms of altering the environment from code. I think there are a lot of applications of this, especially when using Scala outside of the traditional software engineering environment.
Sunday, March 24, 2013
Memory-Mapped Binary Search
Following up on my last post, I looked into implementing a simple proof-of-concept application using FileChannels. I settled on the following use case: suppose you have a very large file which is a sorted list of strings and you want to perform binary search on it. As mentioned last time, the Sorted String Table data structure, which is roughly a generalization of this, is often manipulated through memory-mapped files. The reason why its convenient to do so is because, regardless of how large the file is, we can map its contents to (virtual) memory and treat it as a big in-memory array, letting the OS take care of paging. Then we can easily perform binary search to test membership in the list.
Let's start by formalizing the data structure. We have two files, the index file and the data file with the actual strings. The former is a list of offsets where strings start (and correspondingly end) in the data file, while the latter is a concatenation of all the strings in sorted order. We will assume we can read the entire index into memory, but we could just as easily memory-map that file as well. When doing the binary search, the index will tell us where in the data file to read strings from to do the comparisons. Here's the code in Scala:
We start off by mapping the data file into memory, from which we obtain a MappedByteBuffer that operates as our in-memory array. The bulk of the work happens in the findString() method which does the binary search; to read from the memory-mapped file, we position the buffer at the location specified by the index and read the string from that position. From there, it is as if we just had a String in memory, and we do the necessary comparisons for the binary search logic.
Again, the biggest win is that we can manipulate very large files without doing any complex memory management to make sure we do not exceed our heap size or the machine's memory. You may notice that there are a few limitations of the above code due to the Java ByteBuffer API. A single ByteBuffer can only represent up to 2GB because it uses integers everywhere instead of longs, so the code will only work for files less than 2GB in size (in which case you often do not exceed the machine's memory). Fortunately, it is not too hard to chunk the file into 2GB blocks and map each chunk to its own ByteBuffer; the code changes slightly, but mostly in additional implementation details.
This proof-of-concept binary search shows how FileChannels and MappedByteBuffers can be leveraged to efficiently solve problems in which your data exceeds your memory limit without adding enormous amounts of complexity to your code.
Let's start by formalizing the data structure. We have two files, the index file and the data file with the actual strings. The former is a list of offsets where strings start (and correspondingly end) in the data file, while the latter is a concatenation of all the strings in sorted order. We will assume we can read the entire index into memory, but we could just as easily memory-map that file as well. When doing the binary search, the index will tell us where in the data file to read strings from to do the comparisons. Here's the code in Scala:
We start off by mapping the data file into memory, from which we obtain a MappedByteBuffer that operates as our in-memory array. The bulk of the work happens in the findString() method which does the binary search; to read from the memory-mapped file, we position the buffer at the location specified by the index and read the string from that position. From there, it is as if we just had a String in memory, and we do the necessary comparisons for the binary search logic.
Again, the biggest win is that we can manipulate very large files without doing any complex memory management to make sure we do not exceed our heap size or the machine's memory. You may notice that there are a few limitations of the above code due to the Java ByteBuffer API. A single ByteBuffer can only represent up to 2GB because it uses integers everywhere instead of longs, so the code will only work for files less than 2GB in size (in which case you often do not exceed the machine's memory). Fortunately, it is not too hard to chunk the file into 2GB blocks and map each chunk to its own ByteBuffer; the code changes slightly, but mostly in additional implementation details.
This proof-of-concept binary search shows how FileChannels and MappedByteBuffers can be leveraged to efficiently solve problems in which your data exceeds your memory limit without adding enormous amounts of complexity to your code.
Wednesday, March 13, 2013
Scalding
A couple of days ago, I went to a talk hosted by the Bay Area Scala Enthusiasts on the topic of "Scalable and Flexible Machine Learning with Scala." The talk primarily focused on using Scala with Hadoop to very easily run machine learning algorithms like PageRank, k-means clustering, and decision trees. It was interesting to hear about how the speakers (from LinkedIn and eBay) used machine learning in practice and why they feel Scala is particularly suitable for the task in the context of today's libraries and frameworks. In particular, they showed an impressive library called Scalding that came out of Twitter which is designed to make writing Hadoop workflows in Scala very natural.
Let's start with a quick code snippet taken from the Scalding website.
This piece of code is the implementation of word count, the prototypical MapReduce example, on Hadoop. Besides being impressively short, it is very close to Scala Collections syntax which means it comes naturally to anyone who has programmed in Scala extensively. The idea is to be able to take code the operates on collections and easily translate it into a MapReduce job that can run on Hadoop, which makes a lot of sense since MapReduce is essentially based on the functional programming paradigm.
Of course, it's important that the resulting MapReduce job be efficient. The first two method calls, flatMap and groupBy, don't actually do any work themselves; instead, they simply create flows, an abstraction from the Cascading library which Scalding is built on top of. Much like other languages which attempt to hide the details of MapReduce, Cascading and Scalding construct job/execution flows which are only optimized and executed when you decide to write some output. This is essential because any sort of on-demand execution of map and reduce steps would necessarily lead to inefficiencies in the overall job (e.g. multiple map steps in a row would not be combined and executed on the input all at once).
So why Scalding over something like Pig, which is a dedicated language for Hadoop? One major reason is that it is a huge pain to use custom methods in Pig because you have to write them outside of the language as it is not expressive enough. If you integrate Hadoop into Scala, then you get all of Scala and whatever dependencies you want for free. Furthermore, Pig does not have a compilation step, so it is very easy to get type errors somewhere in the middle of your MapReduce job, whereas with Scalding you would catch them before running the job. In practice, this is a big deal because MapReduce jobs take nontrivial amounts of time and compute resources. Pig has its uses, but Scalding brings a lot to the table in the areas where Pig is lacking.
Running Hadoop jobs is becoming very easy, and Scalding is a great example of how you can implement moderately complex machine learning algorithms that run on clusters with just a handful of lines of code. If there exists a Java library that does most of the hard work, even better; you can integrate it right into your Scalding code. While you probably still have to understand Hadoop pretty well to get the optimal performance out of your cluster, people who are less concerned about resource utilization or who don't have absurdly large datasets benefit greatly from abstractions on top of Hadoop. And everyone wins when it is easy to write testable, robust code even when you are not an expert. This is certainly the direction for many distributed computing and machine learning use cases going forward, and it will be really cool to see what new technologies are developed to meet the demand.
The slides for the talk can be found here.
Let's start with a quick code snippet taken from the Scalding website.
This piece of code is the implementation of word count, the prototypical MapReduce example, on Hadoop. Besides being impressively short, it is very close to Scala Collections syntax which means it comes naturally to anyone who has programmed in Scala extensively. The idea is to be able to take code the operates on collections and easily translate it into a MapReduce job that can run on Hadoop, which makes a lot of sense since MapReduce is essentially based on the functional programming paradigm.
Of course, it's important that the resulting MapReduce job be efficient. The first two method calls, flatMap and groupBy, don't actually do any work themselves; instead, they simply create flows, an abstraction from the Cascading library which Scalding is built on top of. Much like other languages which attempt to hide the details of MapReduce, Cascading and Scalding construct job/execution flows which are only optimized and executed when you decide to write some output. This is essential because any sort of on-demand execution of map and reduce steps would necessarily lead to inefficiencies in the overall job (e.g. multiple map steps in a row would not be combined and executed on the input all at once).
So why Scalding over something like Pig, which is a dedicated language for Hadoop? One major reason is that it is a huge pain to use custom methods in Pig because you have to write them outside of the language as it is not expressive enough. If you integrate Hadoop into Scala, then you get all of Scala and whatever dependencies you want for free. Furthermore, Pig does not have a compilation step, so it is very easy to get type errors somewhere in the middle of your MapReduce job, whereas with Scalding you would catch them before running the job. In practice, this is a big deal because MapReduce jobs take nontrivial amounts of time and compute resources. Pig has its uses, but Scalding brings a lot to the table in the areas where Pig is lacking.
Running Hadoop jobs is becoming very easy, and Scalding is a great example of how you can implement moderately complex machine learning algorithms that run on clusters with just a handful of lines of code. If there exists a Java library that does most of the hard work, even better; you can integrate it right into your Scalding code. While you probably still have to understand Hadoop pretty well to get the optimal performance out of your cluster, people who are less concerned about resource utilization or who don't have absurdly large datasets benefit greatly from abstractions on top of Hadoop. And everyone wins when it is easy to write testable, robust code even when you are not an expert. This is certainly the direction for many distributed computing and machine learning use cases going forward, and it will be really cool to see what new technologies are developed to meet the demand.
The slides for the talk can be found here.
Thursday, March 7, 2013
Dependency Management
Managing dependencies properly in software is a problem that I've run into time and time again regardless of what project I'm working on. By dependency management, I mean specifying which internal and third-party dependencies your code needs. There are many systems for doing this, such as Ivy and Maven in the Java world and SBT in the Scala world (I'm sure other languages have equivalent facilities). These work pretty well in general; for example, if I'm using Maven as my build tool and I need to depend on Google's Guava library, I can find it in Maven Central, add it to my configuration file, and be done with it. The existence of such repositories is one of the greatest developments in software engineering and has probably reduced the amount of code that you need to write by a few orders of magnitude. Inevitably, however, I always encounter situations in which dependency management causes major headaches, in particular due to inconsistent version requirements.
For example, suppose you are working on a project that requires third-party libraries A and B. Both of them are on Maven Central, so you happily put them into your build configuration and are on your way. Well, not quite. Maven is smart in that it recursively pulls dependencies so that you actually have all of the JARs that you need to run your application. But it turns out that library B was last updated five years ago while library A is brand new, and they both depend on a third library C which has had several releases over the last five years. So B specifies version 1.1 of C as a dependency while A uses the latest-and-greatest version 2.0-alpha. To make things even better, the authors of library C decided to break backwards-compatibility with the major version change from 1.x to 2.x, so now you're stuck with two incompatible versions of the same library on your classpath. Maven will most likely complain because of this, but even if you can coerce it to compile your application (which technically will work), upon running the code you will see scary things like NoSuchMethodErrors and IllegalAccessErrors.
So if you find yourself in such a situation, what can you do? One course of action is to decide on either version 1.1 or 2.0-alpha of library C, find the source of A or B, and build your own version of it after changing the dependency on C. This is quite error-prone because you are not familiar with the third-party code and consequently don't have a full understanding of the scope of the dependency on C. It is also time-consuming to dive into the details of implementations that are supposed to be abstracted away from you and mess with bits and pieces of the internals. I have gone through this process a couple of times (when dealing with ubiquitous libraries like Apache HttpClient and Apache Commons), and it's never been fun.
The problem is that there is nobody who is at fault here; the authors of the libraries are all handling their releases in reasonable ways, and you may very well be the first one who has wanted both libraries A and B in the same application. When nobody does anything wrong and you end up with such a nasty situation, something seems wrong. I recently came across a practice that somewhat mitigates the pain: the authors of the Apache Commons Math library used unique package names when they went from version 2 to 3 (org.apache.commons.math vs org.apache.commons.math3) which means that you can safely have them both on your classpath and think of them as completely separate libraries. But it's not clear whether the generic problem of dependency management is actually "solvable" without having all developers adhere to some rigorous backwards-compatibility standard -- certainly an impossible task.
P.S. There are a few other things that I may as well complain about while I'm on this topic. If you run your own continuous integration system and your code is modular to any degree, you'll most likely run into incompatible versions of your own JARs when certain builds break. This is very annoying and a big killer of developer productivity. Additionally, Scala takes dependency management to a whole new level by having libraries be associated with a specific version of the language, so Maven will complain if you have some dependencies built against Scala 2.10.0 while others are built against Scala 2.9.2. Since people don't always update their libraries in a timely fashion, the process of upgrading your own version of Scala can be painful.
For example, suppose you are working on a project that requires third-party libraries A and B. Both of them are on Maven Central, so you happily put them into your build configuration and are on your way. Well, not quite. Maven is smart in that it recursively pulls dependencies so that you actually have all of the JARs that you need to run your application. But it turns out that library B was last updated five years ago while library A is brand new, and they both depend on a third library C which has had several releases over the last five years. So B specifies version 1.1 of C as a dependency while A uses the latest-and-greatest version 2.0-alpha. To make things even better, the authors of library C decided to break backwards-compatibility with the major version change from 1.x to 2.x, so now you're stuck with two incompatible versions of the same library on your classpath. Maven will most likely complain because of this, but even if you can coerce it to compile your application (which technically will work), upon running the code you will see scary things like NoSuchMethodErrors and IllegalAccessErrors.
So if you find yourself in such a situation, what can you do? One course of action is to decide on either version 1.1 or 2.0-alpha of library C, find the source of A or B, and build your own version of it after changing the dependency on C. This is quite error-prone because you are not familiar with the third-party code and consequently don't have a full understanding of the scope of the dependency on C. It is also time-consuming to dive into the details of implementations that are supposed to be abstracted away from you and mess with bits and pieces of the internals. I have gone through this process a couple of times (when dealing with ubiquitous libraries like Apache HttpClient and Apache Commons), and it's never been fun.
The problem is that there is nobody who is at fault here; the authors of the libraries are all handling their releases in reasonable ways, and you may very well be the first one who has wanted both libraries A and B in the same application. When nobody does anything wrong and you end up with such a nasty situation, something seems wrong. I recently came across a practice that somewhat mitigates the pain: the authors of the Apache Commons Math library used unique package names when they went from version 2 to 3 (org.apache.commons.math vs org.apache.commons.math3) which means that you can safely have them both on your classpath and think of them as completely separate libraries. But it's not clear whether the generic problem of dependency management is actually "solvable" without having all developers adhere to some rigorous backwards-compatibility standard -- certainly an impossible task.
P.S. There are a few other things that I may as well complain about while I'm on this topic. If you run your own continuous integration system and your code is modular to any degree, you'll most likely run into incompatible versions of your own JARs when certain builds break. This is very annoying and a big killer of developer productivity. Additionally, Scala takes dependency management to a whole new level by having libraries be associated with a specific version of the language, so Maven will complain if you have some dependencies built against Scala 2.10.0 while others are built against Scala 2.9.2. Since people don't always update their libraries in a timely fashion, the process of upgrading your own version of Scala can be painful.
Sunday, February 24, 2013
Implicit Values
Scala implicits are an interesting feature that could certainly fill up multiple blog posts, but in this one I'm just going to touch on how implicit values work at a high level and why you might use them. In the context of values and parameters, the implicit keyword can mean two things:
- the value or parameter is implicit in the current scope; or
- the parameter list is implicit and can be omitted provided there are corresponding implicit values in the scope of the method call.
For example, consider the following methods:
Here, foo is an example of a method whose parameter list (just one parameter in this case) is implicit. That means we can call it without any parameters if we have an implicit String in scope. The bar and baz methods show two ways of doing this: bar declares its parameter implicit just like foo, which causes it to be implicit in the current scope, while baz declares an additional implicit value that lives in the scope. Lastly, the qux method demonstrates that you can still pass the parameter explicitly.
Depending on your background and preferences, this might seem like either one of the most useful language constructs or one of the scariest. Implicits are very powerful for building frameworks like Play (more on this later) but at the same time can result in code that is very hard to understand due to the difficulty of tracing the usages of state through the code. Because Scala is a type-safe language, however, you at the very least get static type checking so that you don't accidentally end up in a complete mess of improperly typed implicits. For example, these two methods will not compile (thankfully):
The foobar method pretty clearly does not have an implicit String in the current scope which means foo cannot be called. The second case with fubar is a little more subtle, both in syntax and in semantics. The implicit keyword is applied to a parameter list rather than a parameter (the reasons for this are not clear to me), so both String parameters are implicit in the scope of the method. The result, however, is that the implicit String passed to foo is now ambiguous; the Scala compiler won't do anything crazy like arbitrarily choose one, but instead give you an error saying that you tried to do something very dangerous. So implicits are Scala's type-safe way of pretending like the language is more dynamic than it really is.
In general, I don't really advocate using implicits because it's quite easy to get yourself into trouble doing so, but there are cases in which it makes sense. As I mentioned earlier, the Play framework for building web applications is one instance where the use of implicits is convenient. When handling a web request, there are some things which are conceptually always in scope, such as the actual HTTP request or the currently authenticated user (as an option, of course). It can be burdensome to pass these values around constantly, especially between views, and the pain is noticeable if you're coming from something like Django. By leveraging implicits, you can just declare the variables you expect to be in scope at the top of the view and use them freely; as long as they are always declared implicit, the compiler will do the rest for you.
To summarize, implicits allow Scala programmers to have the illusion of working with a more dynamic language. They are powerful but can be dangerous, and as such should be used sparingly.
The foobar method pretty clearly does not have an implicit String in the current scope which means foo cannot be called. The second case with fubar is a little more subtle, both in syntax and in semantics. The implicit keyword is applied to a parameter list rather than a parameter (the reasons for this are not clear to me), so both String parameters are implicit in the scope of the method. The result, however, is that the implicit String passed to foo is now ambiguous; the Scala compiler won't do anything crazy like arbitrarily choose one, but instead give you an error saying that you tried to do something very dangerous. So implicits are Scala's type-safe way of pretending like the language is more dynamic than it really is.
In general, I don't really advocate using implicits because it's quite easy to get yourself into trouble doing so, but there are cases in which it makes sense. As I mentioned earlier, the Play framework for building web applications is one instance where the use of implicits is convenient. When handling a web request, there are some things which are conceptually always in scope, such as the actual HTTP request or the currently authenticated user (as an option, of course). It can be burdensome to pass these values around constantly, especially between views, and the pain is noticeable if you're coming from something like Django. By leveraging implicits, you can just declare the variables you expect to be in scope at the top of the view and use them freely; as long as they are always declared implicit, the compiler will do the rest for you.
To summarize, implicits allow Scala programmers to have the illusion of working with a more dynamic language. They are powerful but can be dangerous, and as such should be used sparingly.
Wednesday, January 30, 2013
Scala Options
One of the most interesting and unfamiliar features of Scala for Java programmers is the Option. The easiest way to think about it is as an explicit representation of an object that may be null. For example, let's say you have a method getString() which returns a String that may be null. In Java you would do:
while in Scala you would do:
where we are leveraging pattern matching. The Option() apply method takes an object and turns it into either a Some (which is generic on the type) or a None depending on whether the object is null. So by using Options you are enforcing an actual type distinction between null and non-null instances of the object. This might not seem like a big deal, but if done thoroughly, you could end up with code in which you are guaranteed that an object not wrapped by an option is non-null. That means you could get rid of NullPointerExceptions! Anyone who has programmed long enough in Java knows how much of a win that would be. Unfortunately, because Scala projects typically have to integrate with a lot of existing Java code, we can't quite reach that ideal state. But if you're diligent in wrapping the return values of third-party libraries in options when the result may be null, you can enforce this checking in your own code.
Besides compile-time distinction between null and non-null instances, options are designed in such a way that they play very nicely with the functional side of Scala. In fact, options are treated as a collection where there is either zero or one element. That means you can do all sorts of interesting things such as:
In each of these cases you would have to do an annoying null check before doing what you actually wanted to do. Scala's functional constructs for operating on collections provide concise ways of handling options without you ever having to mention null or None.
while in Scala you would do:
where we are leveraging pattern matching. The Option() apply method takes an object and turns it into either a Some (which is generic on the type) or a None depending on whether the object is null. So by using Options you are enforcing an actual type distinction between null and non-null instances of the object. This might not seem like a big deal, but if done thoroughly, you could end up with code in which you are guaranteed that an object not wrapped by an option is non-null. That means you could get rid of NullPointerExceptions! Anyone who has programmed long enough in Java knows how much of a win that would be. Unfortunately, because Scala projects typically have to integrate with a lot of existing Java code, we can't quite reach that ideal state. But if you're diligent in wrapping the return values of third-party libraries in options when the result may be null, you can enforce this checking in your own code.
Besides compile-time distinction between null and non-null instances, options are designed in such a way that they play very nicely with the functional side of Scala. In fact, options are treated as a collection where there is either zero or one element. That means you can do all sorts of interesting things such as:
In each of these cases you would have to do an annoying null check before doing what you actually wanted to do. Scala's functional constructs for operating on collections provide concise ways of handling options without you ever having to mention null or None.
Sunday, January 6, 2013
Mockito (Part 2)
Last time, I briefly introduced Mockito, which is a Java/Scala mocking framework that uses a bytecode generation library cglib to create a very simple and natural way of describing mocking behavior. We saw that we could use cglib to create dynamic subclasses and intercept their methods in ways that seemed to be close to how something like Mockito might work. This time I'll provide a full implementation of what I am calling MiniMockito, which allows straightforward when/thenReturn mocking behavior seen here (same example as last time):
Let's take a look at a few method interceptors we'll use to get there (apologies for the large chunk of code):
Here, the MockIntercepted trait is what we'll mix in to the return of methods, e.g. the value of someClass.foo, the first time they are called (or until a stub return value is provided). Because this trait is mixed into a dynamically-generated class, the methods don't actually have implementations anywhere. That's where the StubInterceptor comes in; for the two methods on the MockIntercepted trait, we have predefined return values that give context about which MockInterceptor we're using and which method was stubbed out. These two pieces of information are necessary for thenReturn to set the stub return value.
Lastly, the most important piece is the MockInterceptor itself, which is the method interceptor for the actual mock object. When there is no stub return value set yet, the MockInterceptor will dynamically generate a subclass which mixes in MockIntercepted and uses the StubInterceptor. The subclass carries the context of the method call so we know which method to stub later. The one piece remaining is when the methodReturns map is updated with the stub return values; once it is populated, future calls to the method will always return the stored value! So here's the rest:
The Stubbing object is what actually takes the method and the stub return value and puts them in the methodReturns map. It is returned by the call to when and has context about the mock interceptor and stubbed method because of the MockIntercepted trait we mixed in earlier. The remaining pieces of the implementation are relatively straightforward and included for completeness.
So, to summarize, what does all this code do?
Let's take a look at a few method interceptors we'll use to get there (apologies for the large chunk of code):
Here, the MockIntercepted trait is what we'll mix in to the return of methods, e.g. the value of someClass.foo, the first time they are called (or until a stub return value is provided). Because this trait is mixed into a dynamically-generated class, the methods don't actually have implementations anywhere. That's where the StubInterceptor comes in; for the two methods on the MockIntercepted trait, we have predefined return values that give context about which MockInterceptor we're using and which method was stubbed out. These two pieces of information are necessary for thenReturn to set the stub return value.
Lastly, the most important piece is the MockInterceptor itself, which is the method interceptor for the actual mock object. When there is no stub return value set yet, the MockInterceptor will dynamically generate a subclass which mixes in MockIntercepted and uses the StubInterceptor. The subclass carries the context of the method call so we know which method to stub later. The one piece remaining is when the methodReturns map is updated with the stub return values; once it is populated, future calls to the method will always return the stored value! So here's the rest:
The Stubbing object is what actually takes the method and the stub return value and puts them in the methodReturns map. It is returned by the call to when and has context about the mock interceptor and stubbed method because of the MockIntercepted trait we mixed in earlier. The remaining pieces of the implementation are relatively straightforward and included for completeness.
So, to summarize, what does all this code do?
- The mock method dynamically generates a subclass of the mocked class (SomeClass) which uses the MockInterceptor.
- The MockInterceptor dynamically generates a subclass of the return class (StringInt) that mixes in the MockIntercepted trait and uses the StubInterceptor to implement those methods.
- A call to when uses the MockIntercepted trait that was mixed in to create a Stubbing that knows about the corresponding MockInterceptor and the method that was stubbed (foo).
- Calling thenReturn on the Stubbing populates the map maintained by the MockInterceptor to intercept future calls to the method and return the stub value.
As a final note, this implementation is naturally really hacked together in order to keep it short (sort of, anyway). There are numerous details left out and assumptions made that Mockito naturally does a much better job of handling (e.g. I didn't really figure out a robust way to deal with the lack of no-arg constructors in the mocked class), but it touches upon the basic building blocks offered by cglib that Mockito leverages to achieve its magical behavior. Hope this provided some insight into how this awesome library works!
Friday, January 4, 2013
Mockito (Part 1)
Mockito is a really neat Java/Scala mocking framework that I recently came across. I'm familiar with mocking frameworks that use dynamic proxies to mock interfaces, which are already pretty magical in their use of reflection to intercept method calls. They also have many uses beyond testing and are a good tool to understand. Mockito goes beyond that in its magic, in ways that I previously thought impossible in the Java language. Consider the following example:
This code outputs "bar 2" as you might expect from reading it (it's not quite the same semantics as Mockito, but very close). The interesting things to note here are the fact that SomeClass is just a normal class, not an interface, and the when/thenReturn paradigm (these are static methods in Mockito, along with mock). Looking at the code, it's clear that the call to foo is intercepted/overridden to return something more than just a StringInt object. Otherwise, calling when on it would not be able to accomplish what this code does.
But we are in a type-safe language, so mock needs to return an object which is a subclass of SomeClass that intercepts the foo method call to return an object which is a subclass of StringInt that contains enough information to mock out future calls to foo (e.g. which method was called and what the mocked return value should be). In other words, to not break type safety, we need to create subclasses of these classes that can add on the extra required functionality. Because these subclasses don't exist at compile-time, their bytecode needs to be generated at run-time, which turns out to be possible. The dynamic nature in which this happens is the reason that we can take (almost) any class and create a mock for it with very few assumptions about the original class.
cglib is a bytecode manipulation library whose purpose is to "extend Java classes and implement interfaces at run-time." The Enhancer in particular allows you to create an instance of a dynamically-generated class which can:
This code outputs "bar 2" as you might expect from reading it (it's not quite the same semantics as Mockito, but very close). The interesting things to note here are the fact that SomeClass is just a normal class, not an interface, and the when/thenReturn paradigm (these are static methods in Mockito, along with mock). Looking at the code, it's clear that the call to foo is intercepted/overridden to return something more than just a StringInt object. Otherwise, calling when on it would not be able to accomplish what this code does.
But we are in a type-safe language, so mock needs to return an object which is a subclass of SomeClass that intercepts the foo method call to return an object which is a subclass of StringInt that contains enough information to mock out future calls to foo (e.g. which method was called and what the mocked return value should be). In other words, to not break type safety, we need to create subclasses of these classes that can add on the extra required functionality. Because these subclasses don't exist at compile-time, their bytecode needs to be generated at run-time, which turns out to be possible. The dynamic nature in which this happens is the reason that we can take (almost) any class and create a mock for it with very few assumptions about the original class.
cglib is a bytecode manipulation library whose purpose is to "extend Java classes and implement interfaces at run-time." The Enhancer in particular allows you to create an instance of a dynamically-generated class which can:
- subclass any non-final class,
- have callbacks for method interception, and
- implement additional interfaces.
For example:
Using SomeClass from the previous example, we dynamically generate a subclass for it that uses a method interceptor to return a different object. This code also outputs "bar 2" and gives us a little bit of insight into how these dynamically-generated subclasses can be used to get the mocking behavior in Mockito. If we can create a method interceptor that somehow keeps track of the when/thenReturn calls, we should be able to substitute the return value in place of invoking the actual method.
Stay tuned for part 2 which will demonstrate how this is done and a very minimal implementation of Mockito functionality.
Edit: Part 2 is here.
Edit: Part 2 is here.
Saturday, December 29, 2012
Static Initializers and HotSpot Optimization
HotSpot optimization is one of the core features of the Java Virtual Machine (JVM) that allows JVM-based languages like Java and Scala to have great performance even in comparison to languages that compile directly to machine code. It enables dynamic, run-time optimization of bytecode in various ways, including "true" compilation into machine code, called just-in-time (JIT) compilation. As a result, writing code that is more conducive to HotSpot optimization can lead to huge performance gains; conversely, not doing so can produce unexpectedly slow code. Consider the following two simple Java programs:
They are almost identical, except that the former has the body in the main method while the latter has it in a static initialization block. Running the two programs produces the same result. The key difference, however, is performance: executing the first program takes about 5 ms, while executing the second takes over 40 seconds. With a performance gap of over 1000 times for two pieces of nearly identical code, this is surely worth investigating a bit.
Thanks to this blog post, I discovered two interesting flags you can pass to the JVM called -XX:+PrintCompilation and -XX:+LogCompilation which will cause it to print out all sorts of information regarding the JIT compiler, such as when methods are JIT compiled and when they are recompiled. Here is a snippet of the output for the second program (from log compilation):
I verified that in both cases the JVM tried to JIT compile the main method and the static initializer in the two examples, respectively. Furthermore, in both cases, the compiler performed the key optimization of inlining the call to run(). The discrepancy lies in the snippet, which is repeated in the log for the second program's execution many times. In short, it says that it successfully compiled the static initializer and then hit a trap because the class had not yet been initialized, which forced it to reinterpret the method rather than using the compiled version. This means that the call to run() is not inlined, leading to significantly worse performance.
Since the static initializer is executed at classloading time, it is indeed true that a class has not yet been initialized before static initialization happens. Why this means you have to reinterpret the method is unclear to me, but I'm sure the JVM writers have a good reason for it. So where does this leave us? It seems that in general static initializers cannot be JIT compiled since by definition the enclosing class has not been initialized yet. This, among other reasons, is why you should never perform expensive operations in static initializers.
Finally, I'll provide a Scala example of why this is not a completely trivial case to worry about.
Scala makes it look very natural to put code into the body of an object. Unfortunately, these examples compile into bytecode that closely resembles that of the Java examples above. The for-comprehension is not implemented by a simple for loop but rather by a call to foreach, which takes a closure and calls a method on it (like the Runnable). Most importantly, the body of the second example is run in a static initializer, which causes the same problem that we discussed and the same abysmal performance.
They are almost identical, except that the former has the body in the main method while the latter has it in a static initialization block. Running the two programs produces the same result. The key difference, however, is performance: executing the first program takes about 5 ms, while executing the second takes over 40 seconds. With a performance gap of over 1000 times for two pieces of nearly identical code, this is surely worth investigating a bit.
Thanks to this blog post, I discovered two interesting flags you can pass to the JVM called -XX:+PrintCompilation and -XX:+LogCompilation which will cause it to print out all sorts of information regarding the JIT compiler, such as when methods are JIT compiled and when they are recompiled. Here is a snippet of the output for the second program (from log compilation):
I verified that in both cases the JVM tried to JIT compile the main method and the static initializer in the two examples, respectively. Furthermore, in both cases, the compiler performed the key optimization of inlining the call to run(). The discrepancy lies in the snippet, which is repeated in the log for the second program's execution many times. In short, it says that it successfully compiled the static initializer and then hit a trap because the class had not yet been initialized, which forced it to reinterpret the method rather than using the compiled version. This means that the call to run() is not inlined, leading to significantly worse performance.
Since the static initializer is executed at classloading time, it is indeed true that a class has not yet been initialized before static initialization happens. Why this means you have to reinterpret the method is unclear to me, but I'm sure the JVM writers have a good reason for it. So where does this leave us? It seems that in general static initializers cannot be JIT compiled since by definition the enclosing class has not been initialized yet. This, among other reasons, is why you should never perform expensive operations in static initializers.
Finally, I'll provide a Scala example of why this is not a completely trivial case to worry about.
Scala makes it look very natural to put code into the body of an object. Unfortunately, these examples compile into bytecode that closely resembles that of the Java examples above. The for-comprehension is not implemented by a simple for loop but rather by a call to foreach, which takes a closure and calls a method on it (like the Runnable). Most importantly, the body of the second example is run in a static initializer, which causes the same problem that we discussed and the same abysmal performance.
Monday, December 24, 2012
Mixin Ordering
Mixins are a feature of Scala that allow for more complex class composition than what you see in Java (essentially multiple inheritance with better rules to avoid ambiguity). In Scala, "classes" that you mix in are called traits. They let you do some nice things such as mix in utilities that a lot of classes use, e.g. a Logging trait which has a method that lets you print to the console with the class name.
Creating an instance of the Foo class prints the following:
While in this case we could have just made Logging a class and had Foo extend it, when you have a real class hierarchy and Foo has a real superclass, it's not easy to have this logging functionality in a single place. Allowing us to mix in the Logging trait into any class gives us a much better way to reuse code.
As with many features of Scala, mixins are both powerful and potentially dangerous. In particular, the ordering of mixins has an effect on the behavior of the program beyond the standard "later traits override methods of earlier traits" contract. Consider the following example which is intended to print out a fact about a meter.
It turns out that the output of this program is not what you would expect, but rather
So why is this? Because this example is relatively simple, it's pretty easy to see that the getFact method is being called when the PrintFact trait is initialized, which you might guess happens before the ConversionConstants trait is initialized (and you'd be right). So the value read is 0 instead of the expected 100. It should also be clear that reversing the order of the traits will actually fix the problem since ConversionConstants doesn't have a (indirect) dependency on PrintFact. Moreover, omitting the PrintFact trait and putting the print statement in the body of PrintFactAboutAMeter also fixes the problem because the class constructor is called after all of the traits are initialized.
While the particular example described here might seem contrived, I ran into this problem recently while working on a real project, and it led to a very strange debugging session. So it is important to be careful when using mixins, specifically when doing anything in the initialization of a trait (as well as in a superclass constructor), because you might inadvertently add a dependency going in the wrong direction along the mixin ordering. This is a bit reminiscent of circular dependencies in static initializers in Java.
Creating an instance of the Foo class prints the following:
While in this case we could have just made Logging a class and had Foo extend it, when you have a real class hierarchy and Foo has a real superclass, it's not easy to have this logging functionality in a single place. Allowing us to mix in the Logging trait into any class gives us a much better way to reuse code.
As with many features of Scala, mixins are both powerful and potentially dangerous. In particular, the ordering of mixins has an effect on the behavior of the program beyond the standard "later traits override methods of earlier traits" contract. Consider the following example which is intended to print out a fact about a meter.
It turns out that the output of this program is not what you would expect, but rather
So why is this? Because this example is relatively simple, it's pretty easy to see that the getFact method is being called when the PrintFact trait is initialized, which you might guess happens before the ConversionConstants trait is initialized (and you'd be right). So the value read is 0 instead of the expected 100. It should also be clear that reversing the order of the traits will actually fix the problem since ConversionConstants doesn't have a (indirect) dependency on PrintFact. Moreover, omitting the PrintFact trait and putting the print statement in the body of PrintFactAboutAMeter also fixes the problem because the class constructor is called after all of the traits are initialized.
While the particular example described here might seem contrived, I ran into this problem recently while working on a real project, and it led to a very strange debugging session. So it is important to be careful when using mixins, specifically when doing anything in the initialization of a trait (as well as in a superclass constructor), because you might inadvertently add a dependency going in the wrong direction along the mixin ordering. This is a bit reminiscent of circular dependencies in static initializers in Java.
Sunday, December 23, 2012
Sieve of Eratosthenes in Scala
The Sieve of Eratosthenes is one of the most efficient ways to find all of the primes numbers below some limit (e.g. 100 million) and an essential tool for any programmer interested in various algorithms contests. Recently, I decided to start doing some Project Euler problems in Scala (my new favorite language) and before long I had to write the sieve.
One tricky thing about working with Scala for those of us coming from Java/C++ backgrounds is that some of the nice constructs can lead to pretty bad performance. More details on Scala performance will be saved for another day, but in this case I was able to come up with a pretty concise and "idiomatic" (quotes because I'm still a Scala newbie) way of implementing the sieve which has quite good performance.
Here, we take advantage of Scala's Stream and Range classes for our implementation of the sieve. The outer Stream foreach does the job of picking every prime that we should check divisibility against, basically combining a while construct (takeWhile) with a conditional (filter). The inner Range foreach is a simple replacement for a for loop, marking the multiples as composite. Note that Streams in Scala are lazily evaluated, which means that the filter actually takes into account the current state of the prime array at each step rather than filtering uselessly upfront.
The foreach construct is one example of a language feature that can sometimes give you unexpectedly bad performance, but the developers of the language/compiler have done a good job to make sure that foreach on a Range is very fast (the overhead on Stream is nontrivial, though, as far as I can tell) which means that our inner loop still performs adequately. All in all, this example runs about 50% slower than a Java implementation using for loops, clocking in at about 1.5 seconds on my laptop, which is not bad at all.
This is probably the first of many posts about Scala since it's a really interesting and expressive language that I also happen to use for my job, so look forward to more interesting discussions on the language!
One tricky thing about working with Scala for those of us coming from Java/C++ backgrounds is that some of the nice constructs can lead to pretty bad performance. More details on Scala performance will be saved for another day, but in this case I was able to come up with a pretty concise and "idiomatic" (quotes because I'm still a Scala newbie) way of implementing the sieve which has quite good performance.
Here, we take advantage of Scala's Stream and Range classes for our implementation of the sieve. The outer Stream foreach does the job of picking every prime that we should check divisibility against, basically combining a while construct (takeWhile) with a conditional (filter). The inner Range foreach is a simple replacement for a for loop, marking the multiples as composite. Note that Streams in Scala are lazily evaluated, which means that the filter actually takes into account the current state of the prime array at each step rather than filtering uselessly upfront.
The foreach construct is one example of a language feature that can sometimes give you unexpectedly bad performance, but the developers of the language/compiler have done a good job to make sure that foreach on a Range is very fast (the overhead on Stream is nontrivial, though, as far as I can tell) which means that our inner loop still performs adequately. All in all, this example runs about 50% slower than a Java implementation using for loops, clocking in at about 1.5 seconds on my laptop, which is not bad at all.
This is probably the first of many posts about Scala since it's a really interesting and expressive language that I also happen to use for my job, so look forward to more interesting discussions on the language!
Subscribe to:
Posts (Atom)