Generic Merge Sort In Scala

Many software engineers may not need to explicitly deal with type parameterization or generic types in their day-to-day job, but it’s very likely that the libraries and frameworks that they’re heavily using have already done their duty to ensuring static type-safety via such parametric polymorphism feature.

In a static-typing functional programming language like Scala, such feature would often need to be used first-hand in order to create useful functions that ensure type-safety while keeping the code lean and versatile. Generics is apparently taken seriously in Scala’s inherent language design. That, coupled with Scala’s implicit conversion, constitutes a signature feature of Scala’s. Given Scala’s love of “smileys”, a few of them are designated for the relevant functionalities.

Merge Sort

Merge Sort is a popular text-book sorting algorithm that I think also serves a great brain-teasing programming exercise. I have an old blog post about implementing Merge Sort using Java Generics. In this post, I’m going to use Merge Sort again to illustrate Scala’s type parameterization.

By means of a merge function which recursively merge-sorts the left and right halves of a partitioned list, a basic Merge Sort function for integer sorting might be something similar to the following:

A quick test …

Contrary to Java Generics’ MyClass<T> notation, Scala’s generic types are in the form of MyClass[T]. Let’s generalize the integer Merge Sort as follows:

The compiler immediately complains about the ‘<' comparison, since T might not be a type that supports ordering for '<' to make any sense. To generalize the Merge Sort function for any list type that supports ordering, we can supply a parameter in a curried form as follows:

Another quick test ...

That works well, but it's cumbersome that one needs to supply the corresponding Ordering[T] for the list type. That's where implicit parameter can help:

Testing again ...

Note that the 'if (lHead < rHead)' condition is now replaced with 'if (order.lt(lHead, rHead))'. That's because math.Ordering defines its own less-than method for generic types.

Let's dig a little deeper into how it works. Scala's math.Ordering extends Java’s Comparator interface and implements method compare(x: T, y: T) for all the common types, Int, Long, Float, Double, String, etc. It then provides all these lt(x: T, y: T), gt(x: T, y: T), …, methods that know how to perform all the less-than, greater-than comparisons for various types.

The following are highlights of math.Ordering’s partial source code:

Scala’s math.Ordered versus math.Ordering

Note that math.Ordering does not overload comparison operators ‘<', '>‘, etc, which is why method lt(x: T, y: T) must be used instead in mergeSort for the ‘<' operator.

Scala's math.Ordered extends Java’s Comparable interface (instead of Comparator) and implements method compareTo(y: T), derived from math.Ordering’s compare(x: T, y: T) via implicit parameter. One nice thing about math.Ordered is that it consists of overloaded comparison operators.

The following highlights partial source code of math.Ordered:

Using math.Ordered, an implicit method, implicit orderer: T => Ordered[T], (as opposed to an implicit value when using math.Ordering) is passed to the mergeSort function as a curried parameter. As illustrated in a previous blog post, it’s an implicit conversion rule for the compiler to fall back to when encountering problem associated with type T.

Below is a version of generic Merge Sort using math.Ordered:

View Bound

A couple of notes:

  1. The implicit method ‘implicit orderer: T => Ordered[T]‘ is passed into the mergeSort function also as an implicit parameter.
  2. Function mergeSort has a signature of the following common form:

Such pattern of implicit method passed in as implicit paramter is so common that it’s given the term called View Bound and awarded a designated smiley ‘<%'. Using view bound, it can be expressed as:

Applying to the mergeSort function, it gives a slightly more lean and mean look:

As a side note, while the view bound looks like the other smiley '<:' (Upper Bound), they represent very different things. An upper bound is commonly seen in the following form:

This means someFunction takes only input parameter of type T that is a sub-type of (or the same as) type S. While at it, a Lower Bound represented by the '>:’ smiley in the form of [T >: S] means the input parameter can only be a super-type of (or the same as) type S.

Implicit Conversion In Scala

These days, software engineers with knowledge of robust frameworks/libraries are abundant, but those who fully command the core basics of a language platform remain scarce. When required to come up with coding solutions to perform, scale or resolve tricky bugs, a good understanding of the programming language’s core features is often the real deal.

Scala’s signature strengths

Having immersed in a couple of R&D projects using Scala (along with Akka actors) over the past 6 months, I’ve come to appreciate quite a few things it offers. Aside from an obvious signature strength of being a good hybrid of functional programming and object-oriented programming, others include implicit conversion, type parametrization and futures/promises. In addition, Akka actors coupled with Scala make a highly scalable concurrency solution applicable to many distributed systems including IoT systems.

In this blog post, I’m going to talk about Scala’s implicit conversion which I think is part of the language’s core basics. For illustration purpose, simple arithmetics of complex numbers will be implemented using the very feature.

A basic complex-number class would probably look something like the following:

Since a complex number can have zero imaginary component leaving only the real component, it’s handy to have an auxiliary constructor for those real-only cases as follows:

Just a side note, an auxiliary constructor must invoke another constructor of the class as its first action and cannot invoke a superclass constructor.

Next, let’s override method toString to cover various cases of how a x + yi complex number would look:

Let’s also fill out the section for the basic arithmetic operations:

Testing it out …

So far so good. But what about this?

The compiler complains because it does not know how to handle arithmetic operations between a Complex and a Double. With the auxiliary constructor, ‘a + new Complex(1.0)’ will compile fine, but it’s cumbersome to have to represent every real-only complex number that way. We could resolve the problem by adding methods like the following for the ‘+’ method:

But then what about this?

The compiler interprets ‘a + 1.0′ as a.+(1.0). Since a is a Complex, the proposed new ‘+’ method in the Complex class can handle it. But ’2.0 + b’ will fail because there isn’t a ‘+’ method in Double that can handle Complex. This is where implicit conversion shines.

The implicit method realToComplex hints the compiler to fall back to using the method when it encounters a compilation problem associated with type Double. In many cases, the implicit methods would never be explicitly called thus their name can be pretty much arbitrary. For instance, renaming realToComplex to foobar in this case would get the same job done.

As a bonus, arithmetic operations between Complex and Integer (or Long, Float) would work too. That’s because Scala already got, for instance, integer-to-double covered internally using implicit conversion in its abstract class Int, and in version 2.9.x or older, object Predef:

Testing again …

Implicit conversion scope

To ensure the implicit conversion rule to be effective when you use the Complex class, we need to keep it in scope. By defining the implicit method or importing a snippet containing the method in the current scope, it’ll certainly serve us well. An alternative is to define it in a companion object as follows:

As a final note, in case factory method is preferred thus removing the need for the ‘new’ keyword in instantiation, we could slightly modify the companion object/class as follows:

Another quick test …

Self-contained Node.js Deployment

While setting up a Node.js environment on an individual developer’s machine can be done in a casual manner and oftentimes can be tailored to the developer’s own taste, deploying Node.js applications on shared or production servers requires a little more planning in advance.

To install Node.js on a server, a straight forward approach is to just follow some quick-start instructions from an official source. For instance, assuming latest v.4.x of Node.js is the target version and CentOS Linux is the OS on the target server, the installation can be as simple as follows:

Software version: Latest versus Same

However, the above installation option leaves the version of the installed Node.js out of your own control. Although the major release would stick to v.4, the latest update to Node available at the time of the command execution will be installed.

There are debates about always-getting-the-latest versus keeping-the-same-version when it comes to software installation. My take is that on individual developer’s machine, you’re at liberty to go for ‘latest’ or ‘same’ to suit your own need (for exploring experimental features versus getting ready for production support). But on servers for staging, QA, or production, I would stick to ‘same’.

Some advocates of ‘latest’ even for production servers argue that not doing so could compromise security on the servers. It’s a valid concern but stability is also a critical factor. My recommendation is to keep version on critical servers consistent while making version update for security a separate and independently duty, preferably handled by a separate operations staff.

Onto keeping a fixed Node.js version

As of this writing, the latest LTS (long-term-support) release of Node.js is v.4.4.7. The next LTS (v.6.x) is scheduled to be out in the next quarter of the year. There are a couple of options. Again, let’s assume we’re on CentOS, and that it’s CentOS 7 64-bit. There are a couple of options.

Option 1: Build from source

As a side note, if you’re on CentOS 6 or older, you’ll need to update gcc and Python.

Option 2: Use pre-built binary

Note that both the above two options install a system-wide Node.js (which comes with the default package manager NPM) accessible to all legitimate users on the server host.

Node process manager

Next, install a process manager to manage processes of the Node app, providing features such as auto-restart. Two of the most prominent ones are forever and pm2. Let’s go with the slightly more robust one, pm2. Check for the latest version from the pm2 website and specify it in the npm install command:

Deploying self-contained Node.js

Depending on specific deployment requirements, one might prefer having Node confined to a local file structure that belongs to a designated user on the server host. Contrary to having a system-wide Node.js, this approach would equip each of your Node projects with its own Node.js binary and modules.

Docker, as briefly touched on in a previous blog, would be a good tool in such use case, but one can also handle it without introducing an OS-level virtualization layer. Here’s how Node.js can be installed underneath a local Node.js project directory:

Next, create simple scripts to start/stop the local Node.js app (assuming main Node app is app.js):

Script: $PROJDIR/bin/njsenv.sh (sourced by start/stop scripts)

Script: $PROJDIR/bin/start.sh

Script: $PROJDIR/bin/stop.sh

It would make sense to organize such scripts in, say, a top-level bin/ subdirectory. Along with the typical file structure of your Node app such as controllers, routes, configurations, etc, your Node.js project directory might now look like the following:

Packaging/Bundling your Node.js app

Now that the key Node.js software modules are in place all within a local $PROJDIR subdirectory, next in line is to shift the focus to your own Node app and create some simple scripts for bundling the app.

This blog post is aimed to cover relatively simple deployment cases in which there isn’t need for environment-specific code build. Should such need arise, chances are that you might already be using a build automation tool such as gulp, which was heavily used by a Node app in a recent startup I cofounded. In addition, if the deployment requirements are complex enough, configuration management/automation tools like Puppet, SaltStack or Chef might also be used.

For simple Node.js deployment that the app modules can be pre-built prior to deployment, one can simply come up with simple scripts to pre-package the app in a tar ball, which then gets expanded in the target server environments.

To better manage files for the packaging/bundling task, it’s a good practice to maintain a list of files/directories to be included in a text file, say, include.files. For instance, if there is no need for environment-specific code build, package.json doesn’t need to be included when packaging in the QA/production environment. While at it, keep also a file, exclude.files that list all the files/directories to be excluded. For example:

Below is a simple shell script which does the packaging/bundling of a localized Node.js project:

Run bundling scripts from within package.json

An alternative to doing the packaging/bundling with external scripts is to make use of npm’s features. The popular Node package manager comes with file exclusion rules based on files listed in .npmignore and .gitignore. It also comes with scripting capability that to handle much of what’s just described. For example, one could define custom file inclusion variable within package.json and executable scripts to do the packaging/bundling using the variables in the form of $npm_package_{var} like the following:

Here comes another side note: In the dependencies section, a version with prefix ~ qualifies any version with patch-level update (e.g. ~1.2.3 allows any 1.2.x update), whereas prefix ^ qualifies minor-level update (e.g. ^1.2.3 allows any 1.x.y update).

To deploy the Node app on a server host, simply scp the bundled tar ball to the designated user on the host (e.g. scp $NAME-$VERSION.tgz njsapp@:package/) use a simple script similar to the following to extract the bundled tar ball on the host and start/stop the Node app:

Deployment requirements can be very different for individual engineering operations. All that has been suggested should be taken as simplified use cases. The main objective is to come up with a self-contained Node.js application so that the developers can autonomously package their code with version-consistent Node binary and dependencies. A big advantage of such approach is separation of concern, so that the OPS team does not need to worry about Node installation and versioning.

A Brief Encounter With Docker

Docker, an application-container distribution automation software using Linux-based virtualization, has gained a lot of momentum since it was released in 2013. I never had a chance to try it out but a current project has prompted me to bubble it up my ever-growing To-Do list. Below is a re-cap of my first two hours of experimenting with Docker.

First thing first, get a quick grasp of Docker’s basics. I was going to test it on a MacBook and decided to go for its beta version of Docker for Mac. It’s essentially a native app version of Docker Toolbox with a little trade-off of being limited to a single VM, which can be overcome if one uses it along side with Docker ToolBox. The key differences between the two apps are nicely illustrated at Docker’s website.

Downloading and installing Docker for Mac was straight forward. Below is some configuration info about the installed software:

Next, it’s almost illegal not to run something with a name by hello-world when installing a new software. While at it, test run a couple of less trivial apps to get a feel of running Docker-based apps, including an Nginx and a Ubuntu Bash shell.

While running hello-world or Ubuntu shell is a one-time deal (e.g. the Ubuntu shell once exit is gone), the -d (for detach) run command option for Nginx would leave the server running in the background. To identify all actively running Docker containers and stop them, below is one quick way:

It’s also almost illegal to let any hello-world apps sitting around forever, so it’s a perfect candidate for testing image removal. You’ll have to remove all associated containers before removing the image. Here’s one option:

Note that the above method only remove those containers with description matching the image name. In case an associated container lacking the matching name, you’ll need to remove it manually (docker rm ).

Adapted from Linux’s Cowsay game, Docker provides a Whalesay game and illustrates how to combine it with another Linux game Fortune to create a custom image. This requires composing the DockerFile with proper instructions to create the image as shown below:

Next, to manage your Docker images in the cloud, sign up for an account at Docker Hub. Similar to GitHub, Docker Hub allows you to maintain public image repos for free. To push Docker images to your Docker Hub account, you’ll need to name your images with namespace matching your user account’s. The easiest way would be to have the prefix of your image name match your account name.

For instance, to push the fortune-whalesay image to Docker Hub with account name leocc, rename it to leocc/fortune-whalesay:

Finally, it’s time to try actually dockerize an app of my own and push it to Docker Hub. A Java app of a simple NIO-based Reactor server is being used here:

The Dockerized Java app is now at Docker Hub. Now that it’s in the cloud, you may remove the the local image and associated containers as described earlier. When you want to download and run it later, simply issue the docker run command.

My brief experience of exploring Docker’s basics has been positive. If you’re familiar with Linux and GitHub, picking up the commands for various tasks in Docker comes natural. As to the native Docker for Mac app, even though it’s still in beta it executes every command reliably as advertised.