spiking the solution @spiking-the-solution-blog - Tumblr Blog

Improving the quality and performance of your code, guided by the tooling in Go

What’s rad about writing Go is how the tooling is really well catered to every day software development concerns.

I recently did a lunch and learn at Springer on why I think Go is great and did a case-study showing how Go makes it easy to create consistent looking, performant and reliable code.

Goal

We are going to write a function which calls two APIs, one is the “Hello” service and the other is a “World” service. Our code will stitch the results together to return the string “Hello, World”.

Iteration 1

To start off we’ll just get the signature of our function together so we can write a failing test against it.

func Stitcher(hello_url string, worldURL string) string { return "" }

Before we get too excited though, let’s run golint https://github.com/golang/lint. Go Lint is a tool which points out style inconsistencies in your code. One of the key goals for the language is that all the code should feel recognisable and consistent, we can see that I have already made some mistakes.

stitcher.go:7:1: exported function Stitcher should have comment or be unexported stitcher.go:7:15: don’t use underscores in Go names; func parameter hello_url should be helloURL

Whether you think comments are good or not, what’s nice about this message is that it makes you think about the public surface of your library. Does every function need to be public? Probably not. However if you do cave in to the linter’s demands, the GoDoc tool will make some lovely documentation for your code; so it’s worth the effort.

// Stitcher calls the Hello and World APIs to create a very useful string func Stitcher(helloURL string, worldURL string) string { return "" }

Admittedly a small improvement in this context, but in larger code bases consistent naming and well documented public methods will help you out. The linter tool, like all Go tools are very fast so there’s little reason not to add it to your build scripts.

Now that our stub code is linted we can write a test.

package main import ( "fmt" "net/http" "net/http/httptest" "testing" ) func Test_it_calls_the_services_and_concatenates_the_results(t *testing.T) { helloAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { fmt.Fprint(w, "Hello") })) worldAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { fmt.Fprint(w, "world") })) result := Stitcher(helloAPI.URL, worldAPI.URL) expected := "Hello, world" if result != expected { t.Errorf("Stitcher failed, expected [%s], got [%s]", expected, result) } }

Calling APIs and creating new functionality is a very common task for many developers and Go makes testing these operations a breeze all within the standard library. This test fails so now we can fill out our function with some real code that we can be reasonably confident will work and is safe to refactor.

package main import ( "fmt" "io/ioutil" "net/http" ) // Stitcher calls the Hello and World APIs to create a very useful string func Stitcher(helloURL string, worldURL string) string { helloResponse, _ := http.Get(helloURL) defer helloResponse.Body.Close() helloContent, _ := ioutil.ReadAll(helloResponse.Body) worldResponse, _ := http.Get(worldURL) defer worldResponse.Body.Close() worldContent, _ := ioutil.ReadAll(worldResponse.Body) return string(helloContent) + ", " + string(worldContent) }

We know we haven’t finished yet as there is some naivety to the code in a number of places, most especially error handling, but we will get on to that later. For now we can celebrate the awesomeness of our first pass.

Iteration 2 - Performance

The cowboys we outsourced the two APIs to have said that the APIs cannot return responses quicker than half a second. As we’re calling both APIs we can assume our awesome function will take at least a second to complete.

Intuitively we know that we could do the HTTP calls concurrently which might halve that time.

We shouldn’t just dive in straight away and use Go’s concurrency tools because like all things we need to validate our assumptions otherwise we could be wasting our time. We must be able to prove the code we write adds value in a repeatable way.

Let’s use Go’s benchmarking tools to simulate this and then fix the problem

func Benchmark_the_stitcher(b *testing.B) { slowHelloAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { time.Sleep(500 * time.Millisecond) fmt.Fprint(w, "Hello") })) slowWorldAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { time.Sleep(500 * time.Millisecond) fmt.Fprint(w, "world") })) b.ResetTimer() for i := 0; i < b.N; i++ { Stitcher(slowHelloAPI.URL, slowWorldAPI.URL) } }

The benchmark tool will run the loop N times until it thinks it has a consistent benchmark time. Running the tool confirmed our assumption, the function takes ~1 second.

// Stitcher calls the Hello and World APIs to create a very useful string func Stitcher(helloURL string, worldURL string) string { helloChannel := make(chan []byte, 1) worldChannel := make(chan []byte, 1) go func() { helloResponse, _ := http.Get(helloURL) defer helloResponse.Body.Close() helloContent, _ := ioutil.ReadAll(helloResponse.Body) helloChannel <- helloContent }() go func() { worldResponse, _ := http.Get(worldURL) defer worldResponse.Body.Close() worldContent, _ := ioutil.ReadAll(worldResponse.Body) worldChannel <- worldContent }() return string(<-helloChannel) + ", " + string(<-worldChannel) }

This code has successfully halved the execution time and I have the code to prove that’s the case and that it still works as intended from the test we had earlier.

That being said, the code is starting to feel a little unwieldy, there is a lot of repetition so lets use the safety net of our tests to refactor the code a bit before moving on.

const wordSeparator = ", " // Stitcher calls the Hello and World APIs to create a very useful string func Stitcher(helloURL string, worldURL string) string { helloChannel := make(chan []byte, 1) worldChannel := make(chan []byte, 1) go getStringFromAPI(helloChannel, helloURL) go getStringFromAPI(worldChannel, worldURL) return string(<-helloChannel) + wordSeparator + string(<-worldChannel) } func getStringFromAPI(ch chan<- []byte, url string) { response, _ := http.Get(url) defer response.Body.Close() content, _ := ioutil.ReadAll(response.Body) ch <- content }

Iteration 3 - Error handling

Now that we have a performant happy path, we should tackle the fact that HTTP calls can and will fail; so let’s write a new test to simulate this scenario and that can help us make the code more robust.

The product owners are a fairly vindictive bunch and have told us that if either API fails we are to default to a string which says “ALL OTHER SOFTWARE TEAMS ARE USELESS, OUTSOURCING IS A SHAM”

Here is our test simulating the hello API returning a 500 which results in our code panicking.

func Test_it_handles_non_ok_from_hello_api(t *testing.T) { helloAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { http.Error(w, "oops", http.StatusInternalServerError) })) worldAPI := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) { fmt.Fprint(w, "world") })) result := Stitcher(helloAPI.URL, worldAPI.URL) if result != errorMsg { t.Errorf("Stitcher didnt fail properly, expected [%s], got [%s]", errorMsg, result) } }

We have a test which proves this problem so we can fix the code and be confident that this particular bug will not come up when we go to production.

const wordSeparator = ", " const errorMsg = "ALL OTHER SOFTWARE TEAMS ARE USELESS, OUTSOURCING IS A SHAM" type apiResult struct { content string err error } // Stitcher calls the Hello and World APIs to create a very useful string func Stitcher(helloURL string, worldURL string) string { helloChannel := make(chan *apiResult, 1) worldChannel := make(chan *apiResult, 1) go getStringFromAPI(helloChannel, helloURL) go getStringFromAPI(worldChannel, worldURL) helloResult := <-helloChannel worldResult := <-worldChannel if helloResult.err != nil || worldResult.err != nil { return errorMsg } return helloResult.content + wordSeparator + worldResult.content } func getStringFromAPI(ch chan<- *apiResult, url string) { response, err := http.Get(url) if err != nil { ch <- &apiResult{"", err} } else { defer response.Body.Close() content, err := ioutil.ReadAll(response.Body) if err != nil { ch <- &apiResult{"", err} } else if response.StatusCode != http.StatusOK { ch <- &apiResult{"", errors.New("Non 200 response from API")} } else { ch <- &apiResult{string(content), nil} } } }

This code makes our new test pass, hooray! Some Go experts might have some better ways to write this and that's fine because we now have a suite of tests to make sure no matter how much someone tinkers with the implementation they can be confident they have not broken existing functionality.

Summary

Even though this is a contrived example I hope this demonstrates how Go’s ecosystem and tooling can really help to create robust, well tested and readable software.

Go makes it really easy to write maintainable open source software, if you are mad enough to want to use something that blindly concatenates two successful HTTP calls, all you need to do is

go get github.com/quii/go-perf-test-example

and then just check the almost entirely auto-generated go doc (https://godoc.org/github.com/quii/go-perf-test-example) to see how to use it.

The final codes are available here: https://github.com/quii/go-perf-test-example

If you have any comments on feedback, please do get in touch with me.

Xuemin's side profile

Better Smoke Tests with Jasmine, CoffeeScript, Q and Cheerio

Problem: We have an unreliable suite of smoke tests for Springer Link, dependent on data, prone to random failures, and taking significant time to compile and execute.

Spiked solution (1 of 4): Write a new suite of tests using CoffeeScript, Jasmine and an assortment of helpful third party libraries with no dependencies on "golden data".

describe 'The abstract page for an article', -> it 'has PDF and full text links', (done) -> searchWith 'facet-content-type': 'Article' .then findResultWith fulltext, pdf .then loadPageWith SearchPage.resultTargetUri .then checkForValidLink '#pdf-link' .then checkForValidLink '#full-text-link' .fin done

Jasmine

Jasmine is a well-known JavaScript test framework, already in use in some of our projects and the spec syntax is familiar to our team from our Scala tests. It also provides support for asynchronous testing (through the done() function), a necessity when your tests involve making HTTP requests.

CoffeeScript

CoffeeScript is a language which "compiles" to JavaScript with the intention of smoothing over some of JavaScript's rougher edges with a terser syntax. The latter makes it an attractive prospect for writing readable tests. Consider the following snippet from the above test translated to JavaScript:

describe('The abstract page for an article', function() { it('has PDF and full text links', function(done) { searchWith({ 'facet-content-type': 'Article' }) .then(findResultWith(fulltext, pdf)) // ... .fin(done()); }); });

Your mileage may vary, but the boilerplate around function definitions and visual noise from dots, brackets and semi-colons (don't forget the semi-colons!) is something I find distracts from the content of the test.

HTTP requests in node are asynchronous and we will be making many of these, often chained (there are two in the example), leading to ugly nesting. One solution is to use the promises implementation provided by Q, hence all the thens above (they are not actually test script syntax, they just nicely dovetail with it). The test might otherwise have looked something like this:

describe 'The abstract page for an article', -> it 'has PDF and full text links', (done) -> searchWith 'facet-content-type': 'Article', (page) -> result = findResultWith(fulltext, pdf)(page) loadPageWith SearchPage.resultTargetUri(result), (page) -> checkForValidLink('#pdf-link')(page) checkForValidLink('#full-text-link')(page) done()

Not only does this deeply nest with just two requests, some boilerplate is back in the form of parameter lists (it will be clear why in the next section). With Q an asynchronous operation can be wrapped in a promise with failure and success handlers for the result, which in turn result in promises that may be chained:

loadPage = (uri, callback) -> // get that page and invoke the callback when you've got it promiseToLoadRobots = -> deferred = Q.defer() loadPage '/robots.txt' , (page) -> deferred.resolve page deferred.promise promiseToLoadRobots().then (robots) -> // do something awesome with robots

A fin function may be invoked at the very end which is analogous to the finally of a try block in some languages - it will always be executed regardless of the success of the promises in the chain. This is important in asynchronous testing as Jasmine's done function tells the test runner when an async test is complete (without it the test will time out).

Currying

Even with CoffeeScript there is scope for reduction of boilerplate. In the example the functions which are passed to the thens of the promises are actually functions which take some parameters and return functions which take the result of the promise to check something on. This uses a concept known as currying. Consider without:

.then (page) -> checkForValidLink page, '#pdf-link' page .then (page) -> checkForValidLink page, '#full-text-link' page

By defining the function checkForValidLink such that instead of taking a page and a CSS selector:

checkForValidLink: (page, cssSelector) -> // check for valid link

it takes a CSS selector and returns a function taking a page, which in turn returns the page so that it can be wrapped in a promise by Q for chaining:

checkForValidLink = (cssSelector) -> (page) -> // check for valid link, then return the page

which is exactly what the then of the promise is expecting:

.then checkForValidLink '#pdf-link' .then checkForValidLink '#full-text-link'

I think it's worth noting here how nice the terse syntax of CoffeeScript is for this technique, which would be considerably uglier and have less clear intent in JavaScript:

function(cssSelector) { return function(page) { // check for valid link, then return the page }; };

Cheerio

For interacting with the DOM of a page the result of the request is loaded using the Cheerio library, a subset of JQuery with the browser API stripped out providing a way of querying HTML familiar to those with web development experience:

$ = cheerio.load response.body // assign to $ for familiarity, not strictly necessary title = $('h1').text()

Requests

Requests are made using the Request library, which provides a nice wrapper around nodejs's native HTTP support. In combination with Q and Cheerio it looks something like this:

loadPage = (url, headers) -> deferred = q.defer() request url: url headers: headers , (error, response) -> if (error or response.statusCode != 200) deferred.reject error or response.statusLine else deferred.resolve cheerio.load response.body deferred.promise

The first argument to request is a JSON object specifying the request, and here showing again how nice the terseness of CoffeeScript can be.

All data considered equal

One problem with our previous smoke test setup was a reliance on "golden data" - data which the tests assumed to be present in the system. There are two problems with this - data can be subject to change, causing tests to fail for reasons which may not be immediately apparent; and it requires that that data be present in all environments you may wish to smoke test.

To work around this the new test uses the site's search functionality to locate pages which match certain base criteria which it can then load and check:

searchWith 'facet-content-type': 'Article' .then findResultWith fulltext, pdf .then loadPageWith SearchPage.resultTargetUri // then check some things about the page

searchWith takes a list of query string parameters which are used by the site search, in this case faceting on content type to retrieve articles.

findResultWith then takes a list of criteria to locate a search result, in this case we want to make sure that it is for an article that has both PDF and HTML representations available.

loadPageWith takes a function which is used to extract a URI from a provided page or page fragment, in this case a search result entry.

Configuration

Given that we want to be able to run these smoke tests in different environments (and now are able to with the data dependency issue largely resolved) we need to be able to provide environment-specific configuration. The library which stood out here was flatiron's nconf:

environment = nconf.env().get 'ENV' nconf.file file: "conf/config.#{environment}.json"

The first line in this snippet gets the environment name from an environment variable that we have defined on our servers and dev machines (or that can be provided in the command line), and uses it to select the file to load.

Configuration in nconf is hierarchical, a nice contrast to the repetitious dot syntax familiar from Java properties:

{ "springer": { "host": "localhost:8080" } }

The host key is then accessible like so:

nconf.get 'springer:host'

Additionally, nconf is wrapped in our own config wrapper and nconf.get assigned to an exported config value. This makes it both less verbose and the code less explicitly dependent on a third party:

// config.coffee: // config initialisation goes here exports.config = nconf.get // other file: {config} = require './config' host = config 'springer:host'

Conclusion

Using a few familiar libraries or libraries which provide familiar interfaces, a boiler-plate reducing language and a useful FP paradigm we succeeded in producing tests which are clean, readable and fast-running (the whole suite presently runs in ~3.5s on a MacBook pro, as opposed to > 2 minutes for the Scala tests).

By Jim Kinsey

#testing #coffeescript #nodejs

Composable web pages with Micro-components and Edge Side Includes using the Play Framework

Maintaining a complex web page full of different components with their own requirements can be challenging. Often you will start with a simple web page but slowly you start adding new components and integrating with other services.

When you have a dynamic, feature-rich page caching becomes more difficult and testing an entire page becomes impractical. Your tests can become difficult to maintain and can become slow.

Micro components

By breaking your page up into separate components you get the following advantages:

Easier to maintain distinct pieces of functionality

Reusability

More flexible caching

Ability to independently deploy components so you can enhance and fix bugs without a "big bang" release.

Inspired by the LinkedIn talk by Yevgeniy Brikman, Rob and I wanted to deliver a proof of concept of this approach for SpringerLink’s abstract/fulltext page. (e.g http://link.springer.com/article/10.1007/s10817-012-9258-1).

We wanted to break up our page into smaller components, pull them in via HTTP asynchronously.

Our proof of concept

The components

We developed 4 simple web pages in the Play framework which represent the main features on an article page.

http://localhost:9000/abstract/{ID} - Displays the HTML abstract for a given ID

http://localhost:9000/fulltext/{ID} - Displays the HTML for the entire document for a given ID

http://localhost:9000/downloads/{ID} - Displays total number of downloads and downloads by country for a given ID

http://localhost:9000/time - Returns the server’s local time

Putting it together

Now that these components are created you can imagine developers being able to work on them without worrying about the rest of the website. They can be tested and deployed completely independently from the big web app.

Now we have the problem that we want to bring all these components to construct a web page

Scala is really great at asynchronous programming, so this is as easy as just making 4 HTTP calls and wrapping them in Future. You can then compose them together, plug it into a template and then you have the page fully rendered.

Play is a great choice for this because it allows you as a developer to have your controllers return Future's and it will handle the rest.

Here is the code for the aggregating controller

https://gist.github.com/quii/a8165f87656c031cf9d6

As you can see, there is no real complexity in breaking up the page into pieces, fetching them asynchronously and then composing it together into a view.

Edge side includes

Edge side includes are server side tags which contain a URL. Proxies like Varnish and Akamai can read and then fetch the HTML from its cache and then output it to the page seamlessly for the user.

High quality diagram

Given our components are now pulled in via HTTP, we wanted it so if you were hitting the website via Varnish the web server would create ESI tags rather than making potentially slow HTTP calls itself.

The simplest way to accomplish this is to edit the getBodyOf function:

https://gist.github.com/quii/e9407898d701d2b0e623

The net result for this is the server can output ESI tags and delegate the hard work to the cache which can store these potentially heavy requests, rather than doing the heavy work itself.

You'll notice that we check for the presence of a Varnish request, the reason for this is we wanted to make sure that development could be done without the need of Varnish running on a local dev box.

By doing this the page remains dynamic, yet highly cacheable. We can serve a cached version of the page depending on your access rights.

What about client side?

You can find plenty of tutorials on bringing in data asynchronously via the client. This approach works fantastically on a number of successful websites, like Facebook and LinkedIn.

However you can face a number of tricky issues around this approach, Twitter famously reverted from a client side approach to moving this complexity back to the server

"To improve the twitter.com experience for everyone, we’ve been working to take back control of our front-end performance by moving the rendering to the server"

I feel client side rendering and pulling of data is great for auxiliary content but it does add complexity to the client which I feel is a bit easier to handle on the server. This post by Karl Seguin goes over some of these problems.

In addition, managing things like SEO and testing are a bit easier on the server side and for the main content on our site we need to make sure these things are bullet-proof.

That said, the micro-component approach doesn’t restrict you using the client side, it actually allows you to be flexible in how you want content to be delivered to your users.

You may prefer in some cases to output a bespoke HTML tag which your client side code knows to look for and then subsequently retrieve the data.

Next steps

The code above is just a proof of concept and as such is a bit messy so it would be nice to encapsulate the behaviour of "Retrieve the contents of this URL by this means" in some kind of re-usable way.

I would like to write a nice declarative way of writing things like

“Fetch the contents of URL-A”

“Output ESI tags for URL-B”

“Output client side include tags for URL-C”

and then be able to compose these calls into a view for rendering.

The code I didn’t show was of the components, which you need to make sure set the appropriate cache headers.

Conclusions

In spite of our page being very dynamic the main bulk of the response can be brought in from a cache, which brings in the benefits of decreased load and faster performance.

This architecture has the happy side-effect that you have to make your components small and independent, which in the long run makes a more maintainable, re-usable platform.

With modern languages the old objections of this approach being too complicated are largely irrelevant. Scala's monadic composition makes this very easy but would be just as doable in other languages such as Javascript with Node.js

You can accomplish all of these things client side too and there is no real right answer as to where this logic should live; but I hope this post gives you a heads up on a different approach which might be more suitable for your needs.

By Chris James

#Scala #play-framework #caching

Simulating the Call Stack

In this post we will write some Scala helper code that allows you to evaluate non-tail recursive functions as if they were tail recursive. This is done behind the scenes using an explicit stack. The benefit of this is that stack overflow is then much less likely to occur for "large" inputs.

Evaluating Recursive Functions

Suppose we define the function $f: \mathbb{N} \rightarrow \mathbb{N}$ as follows:

$$ f(n) = \left\{ \begin{array}{ll} 0 & \text{ if } n = 0 \text{ ,} \\\ n - f(n - 1) & \text { otherwise. } \end{array} \right. $$

It turns out that for any $n$, we have $f(n) = \lceil n / 2 \rceil$ but this is not immediately obvious. This function is not very interesting in itself but we will use it to illustrate some practical aspects of recursion. Here is a straightforward implementation of $f$ in Scala:

def f(n: Int): Int = n match { case 0 => 0 case _ => n - f(n - 1) }

What happens when we evaluate $f(2)$? Tracing all the steps on paper we get

$$ \begin{array}{rcl} f(2) & = & 2 - f(1) \\\ & = & 2 - (1 - f(0)) \\\ & = & 2 - (1 - 0) \\\ & = & 2 - 1 \\\ & = & 1 \text{ .} \end{array} $$

On the other hand, a computer evaluates f(2) essentially as follows.

"Enter" the body of f with parameter n set to the argument 2. The second case applies, so we need to call f recursively and subtract the result from n.

Push a frame on to the call stack. This frame contains a mapping from n to 2, among other things. Let's denote this frame by $F(2)$.

(Re)enter the body of f, this time with n set to 1.

The second case applies again. Push a frame $F(1)$ on to the call stack which maps n to 1.

(Re)enter the body of f, this time with n set to 0.

The first case applies — return 0. At this point the call stack consists of $F(1)$ and $F(2)$. Pop the top frame $F(1)$ off the stack. This frame maps n to 1 and also contains a pointer to the place in the body of f from where the recursive call was made, namely at n - f(n - 1). We can calculate this now: n = 1 and f(n - 1) is the returned value 0. Therefore return 1.

Pop the top frame $F(2)$ off the stack. Now n maps to 2 and we have just determined that f(n - 1) is 1. Therefore return 2 - 1 = 1.

The stack is now empty, so evaluation has finished and 1 is the final result returned by f.

This is very much a simplification of what actually happens but the important point is that the stack grows each time a recursive call is made. We need to push frames on to the stack in order to keep track of the value of n at the time that f calls itself. This is because we later need to subtract the value returned by the recursive invocation from n.

There is a limit on how large the call stack can grow. If this limit is exceeded, stack overflow occurs. When exactly this limit is reached depends on various factors, but on my machine I already get a stack overflow error when $n = 50,000$:

scala> def f(n: Int): Int = n match { | case 0 => 0 | case _ => n - f(n - 1) | } f: (n: Int)Int scala> f(2000) res0: Int = 1000 scala> f(50000) java.lang.StackOverflowError at .f(<console>:9)

Preventing Stack Overflow

As we have just seen, if we need to do anything with the result of a recursive call then we need to push a new frame on to the call stack. If we don't need to do anything (other than simply returning the result) then there is no need for a new stack frame. This is known as tail call optimisation and it is supported by the Scala compiler. A tail call is a recursive call that does not do any additional operations with its result. A tail-recursive function is a recursive function that uses only tail calls.

Below is a tail-recursive implementation of the factorial function:

def factorial(n: Int): Int = { def factorial(n: Int, accumulator: Int): Int = n match { case 0 => accumulator case _ => factorial(n - 1, accumulator * n) } factorial(n, 1) }

Compare this to the direct, recursive implementation:

def factorial(n: Int): Int = n match { case 0 => 1 case _ => n * factorial(n - 1) }

The tail recursive version uses an accumulator which is a standard trick for making recursive functions tail-recursive.

As pointed out in converting recursion to iteration, this trick does not always work. In the case of factorial, for say $n = 3$ the tail-recursive implementation computes $2 \cdot (3 \cdot 1)$ whereas the standard recursive implementation computes $3 \cdot (2 \cdot 1)$. [UPDATE: As $0$ is the base case this should in fact read $1 \cdot (2 \cdot (3 \cdot 1))$ and $3 \cdot (2 \cdot (1 \cdot 1))$.] The end result happens to be the same because multiplication is commutative and associative, but obviously not every operation has those properties. In particular, subtraction is neither commutative nor associative. Moreover, rewriting a function to use an accumulator is usually not straightforward if our original function is multiply recursive instead of singly recursive — that is, if it calls itself more than once. A typical example of this is the Fibonacci function.

A more generally applicable method is to use an explicit stack instead of an accumulator. For example, we can use Scala's built in Stack class (or some other appropriate data structure) and then mimic the way the call stack works when evaluating our function. The rest of this post shows how we can implement this approach.

A Datatype for Recursive Functions

Wikipedia's page on recursion has the following to say about explicit stacks:

Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is tree traversal as in depth-first search; contrast with list traversal and linear search in a list, which is singly recursive and thus naturally iterative. Other examples include divide-and-conquer algorithms such as Quicksort, and functions such as the Ackermann function. All of these algorithms can be implemented iteratively with the help of an explicit stack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.

This seems a bit pessimistic. Maybe we can write a small Scala library that exposes a simple syntax (DSL?) for specifying recursive functions, and implements an explicit stack behind the scenes for evaluating them. First, here is a datatype EvalSpec for expressing the body of a recursive function.

sealed trait EvalSpec[S, T] case class Constant[S, T](t: T) extends EvalSpec[S, T] case class Recurse[S, T](s: S, f: T => EvalSpec[S, T]) extends EvalSpec[S, T]

Here S is the input type of the recursive function and T is its result type. A recursive function either returns a constant t, or it makes a recursive call with an argument s and a function f that does something with the result of this recursive call. We also add a method evaluate that takes a function producing an EvalSpec and applies it to an argument. The implementation of evaluate is left for later, but here is its signature:

def evaluate[S, T](f: S => EvalSpec[S, T])(s: S): T

Now, for example, to re-implement the function $f$ given at the start of this post we write the following (calling the new method g for convenience):

def g: Int => Int = evaluate[Int, Int] { case 0 => Constant(0) case n => Recurse(n - 1, x => Constant(n - x)) }

This says that if the input to g is 0 then 0 should be returned. Otherwise, for an integer n (which is assumed to be positive) we must make a recursive call with n - 1 and then subtract the result x from n.

Evaluating With an Explicit Stack

Here is the implementation of evaluate, along with some auxiliary definitions:

private sealed trait EvalStack[S, T] private case class ConstantFrame[S, T](constant: Constant[S, T], tail: Option[ContinueFrame[S, T]]) extends EvalStack[S, T] private case class RecurseFrame[S, T](recurse: Recurse[S, T], tail: Option[ContinueFrame[S, T]]) extends EvalStack[S, T] private case class ContinueFrame[S, T](f: T => EvalSpec[S, T], tail: Option[ContinueFrame[S, T]]) extends EvalStack[S, T] def evaluate[S, T](f: S => EvalSpec[S, T])(s: S) = { @scala.annotation.tailrec def process(stack: EvalStack[S, T]): T = { stack match { case ConstantFrame(Constant(c), None) => c case ConstantFrame(Constant(c), Some(ContinueFrame(g, tail))) => process(makeStack(g(c), tail)) case RecurseFrame(Recurse(arg, g), tail) => process(makeStack(f(arg), Some(ContinueFrame(g, tail)))) } } process(makeStack(f(s), None)) } private def makeStack[S, T](top: EvalSpec[S, T], tail: Option[ContinueFrame[S, T]]): EvalStack[S, T] = top match { case constant@Constant(_) => ConstantFrame(constant, tail) case recurse@Recurse(_, _) => RecurseFrame(recurse, tail) }

Instead of using Scala's built-in Stack or List datatype we define our own, called EvalStack. This is essentially a linked list whose head can be a Constant, a Recurse, or the "continuation" part of a Recurse. The helper function makeStack simply takes a frame and makes it the new head of given stack tail (whose head is a ContinueFrame).

Calling the function g above with argument 2 results in the following stack progression:

iteration 1: RecurseFrame(Recurse(1, x => 2 - x), // the top of the stack None) iteration 2: RecurseFrame(Recurse(0, x => 1 - x), // the new top of the stack Some(ContinueFrame(x => 2 - x, None))) iteration 3: ConstantFrame(Constant(0), Some(ContinueFrame(x => 1 - x, Some(ContinueFrame(x => 2 - x, None))))) iteration 4: ConstantFrame(Constant(1), // 1 - 0 Some(ContinueFrame(x => 2 - x, None))) iteration 5: ConstantFrame(Constant(1), // 2 - (1 - 0) None)

Moreover, evaluating g(50000) produces 25000 as expected and does not fail due to stack overflow.

In what follows, let's look at a few more examples of what EvalSpec can be used for. We first add an implicit definition that saves us from having to wrap constants in Constant:

implicit def valToConst[S, T](t: T): Constant[S, T] = Constant[S, T](t)

Example: Factorial

Below are recursive and EvalSpec-based implementations of the factorial function:

def factorialRecursive(n: Int): Int = if (n < 2) 1 else n * factorialRecursive(n - 1) def factorial: Int => Int = evaluate[Int, Int] { n => if (n < 2) 1 else Recurse(n - 1, x => n * x) }

In contrast to the tail-recursive version given earlier that used an accumulator, this time the result is calculated in the exact same order as by the normal recursive version. Here is what happens for factorial(4):

iteration 1: RecurseFrame(Recurse(3, x => 4 * x), None) iteration 2: RecurseFrame(Recurse(2, x => 3 * x), Some(ContinueFrame(x => 4 * x, None))) iteration 3: RecurseFrame(Recurse(1, x => 2 * x), Some(ContinueFrame(x => 3 * x, Some(ContinueFrame(x => 4 * x, None))))) iteration 4: ConstantFrame(Constant(1), Some(ContinueFrame(x => 2 * x, Some(ContinueFrame(x => 3 * x, Some(ContinueFrame(x => 4 * x, None))))))) iteration 5: ConstantFrame(Constant(2), // 2 * 1 Some(ContinueFrame(x => 3 * x, Some(ContinueFrame(x => 4 * x, None))))) iteration 6: ConstantFrame(Constant(6), // 3 * (2 * 1) Some(ContinueFrame(x => 4 * x, None))) iteration 7: ConstantFrame(Constant(24), // 4 * (3 * (2 * 1)) None)

Example: Fibonacci

Below are implementations of the Fibonacci function (which uses multiple recursion):

def fibonacciRecursive(n: Int): Int = if (n < 2) n else fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2) def fibonacci: Int => Int = evaluate[Int, Int] { n => if (n < 2) n else Recurse(n - 1, x => Recurse(n - 2, y => x + y)) }

Example: Binary Trees

In this example we define a datatype for binary trees. We then define a function that takes a binary tree whose nodes are labelled by integers, and sums the labels of all the nodes in this tree.

trait BinaryTree[+T] case class Node[+T](value: T, left: BinaryTree[T], right: BinaryTree[T]) extends BinaryTree[T] case object EmptyTree extends BinaryTree[Nothing] def sumRecursive(tree: BinaryTree[Int]): Int = tree match { case EmptyTree => 0 case Node(value, left, right) => value + sumRecursive(left) + sumRecursive(right) } def sum: BinaryTree[Int] => Int = evaluate[BinaryTree[Int], Int] { case EmptyTree => 0 case Node(value, left, right) => Recurse(left, x => Recurse(right, y => value + x + y)) }

Trampolines and Continuations

The helper code above shares some similarities with Rich Dougherty's implementation of trampolines but is more generally applicable. It also seems similar to continuations but I haven't quite understood the relationship yet.

Conclusion

The EvalSpec-based definitions of recursive functions are arguably concise and easy to read. They look (almost) like their non-tail recursive counterparts but get evaluated in a tail-recursive way behind the scenes. This code is just a simple working prototype, if you know of a better way to do this then please let me know (surely I have poorly reinvented some existing technique?). Please see the simulated-call-stack project on GitHub for the full implementation as well as more examples.

UPDATE: Boyd Smith has kindly pointed out that Stackless Scala With Free Monads is far more general than what I have done here. So please consider this blog post as a small step in the right direction :-).

By Hilverd Reker

What is a Type Class and why should you care?

Type systems are great because they protect you from lots of errors at compile time. However, sometimes it feels like it gets in your way and can make your code feel less flexible when you are trying to extend certain types that you may or may not have defined.

In dynamically typed languages this is less of a problem because of duck-typing. However, you get no safety here; if you pass in something that doesn’t quack you will get a runtime error.

Duck typing doesn't fix everything though. A human class might be able to quack with a "say" function; you would need to give your program some help in these instances

If you wish to write a generic function that operates on a variety of types, you may be tempted into writing an interface and ensuring all the types you care about implement them.

But this requires changing potentially lots of code and adding in a commonality that only you care about to solve a particular problem. Ask yourself, is this polymorphism truly useful for other people? Or are you polluting the namespace for your convenience (hint: the latter).

The GoF have a solution to this too, the adapter pattern. But every time someone wants to use your library they will have to take their type and wrap them up in an adapter. This feels clunky to me; and of course there is a better way.

Type classes to the rescue!

A type class T is an interface that defines a set of behaviours that a type Foo must implement in order to be of type T. Great, so what?

If you wish to have a polymorphic function, you can require evidence of a type class for the type which is being passed in. This can be any type because a developer can provide this evidence wherever they like; i.e not within the type itself.

This is a great strength of type classes because it addresses the flaws of the other approaches:

Any arbitrary type can use your library if they implement your typeclass; no need for access to the source code.

No need to pollute namespace of types only for your needs. Clear separation of concerns and still polymorphic

No wrappers needed. Scala's implicit means you can pass in your type to the library function without noisy adapters; makes your code easier to follow.

Type safety.

Example

https://gist.github.com/quii/10475916

Scala provides sugar to make it so your function's type can reflect it's needs, rather than having it as a parameter. You can replace the function from above with the code below and it will continue to work.

https://gist.github.com/quii/10529675

This syntax can provide more flexibility in terms of not having to pass implicit parameters to other sub-functions; your function just requires "evidence" of a type-class.

However, people in your team may be more familiar with an implicit parameter so be sure to explain things whenever you introduce exotic symbols into your code-base.

Conclusion

Type classes are easy to use and an interesting functional design pattern for your tool-belt.

Enables “ad-hoc” polymorphism but with type safety.

Allows users of your useful functions to use them with any type without having to change their own types.

Easier to separate concerns without making lots of types/adapters.

Essential for making your library code re-usable and extensible; a very common approach in the standard Scala libraries and popular open source projects.

By Chris James

Trending Blogs

Recently Viewed Blogs

spiking the solution