Tag Archives: functional programming

Tail call optimisation in Scala

This is just a quick note. I couldn’t seem to find any good information on what sorts of tail call optimisations were performed by Scala so I ran a few quick tests. Disappointingly, the answer seems to be not much. A simple tail recursion was turned into a loop, but the following code got no love:

object Main extends Application{ def foo (x : Int){ if (x == Integer.MAX_VALUE) Console.println("Hello world!"); else bar(x + 1); }

def bar (x : Int){ if (x == Integer.MAX_VALUE) Console.println("Hello world!"); else foo(x + 1); } foo(0); }

This isn’t really surprising, although it’s a bit sad. Eliminating general tail calls seems to be quite hard without just converting everything into CPS and making everything work that way (at least so I’m lead to believe. My expertise on the subject is basically nonexistent), which is probably not a great idea on the JVM.

Curiously, if you enabled optimisations with -XO, foo was inlined into bar but the resulting tail recursion was not eliminated. That’s probably a bug.

Update: It’s been pointed out to me that I’ve gotten myself completely confused on the relationship between continuations and tail call elimination. Please ignore any mumbling to that effect. :-) The issue is apparently that TCO is easy when compiling to assembly and hard when compiling to something like JVM byte code which is higher level and doesn’t already support it.

Beating StringBuilder? Hell no.

So, it turns out that StringBuilder is almost insultingly fast. It’s very well written, does almost no allocation, and is almost certainly getting special help from the VM and JIT under the covers. Appending a medium sized string to it appears to be faster (when averaged over about 11000 appends) than allocating new objects!

I’m almost tempted to try writing a mutable JumpRopeBuilder which does the same job to see if I can beat it (and I probably will anyway, but use it to generate balanced JumpRopes rather than optimise it for appends), but I think I’ll restrain myself. I must remember that hte goal is to have a String replacement rather than a StringBuilder replacement, and as that this does pretty well – the appends are very fast compared to String append (the actual conversion to a string is a little slow admittedly – it takes 100-200 ms for a approximately 100k characters, and about half of that is the overhead of iterating over an unbalanced binary tree). And, unlike StringBuilder, this is totally thread safe by virtue of being immutable.

Which reminds me, I should compare it against StringBuffer.

Anyway, I should really start adding some actual functionality now. :-)

Lazy strings for Java

I’ve started yet another open source project, motivated by the fact that Java Strings suck. The aim is to have an efficient string implementation for Java which is optimised for a more sensible set of operations. It draws on ideas from Haskell and purely functional data structures, aiming to take advantage of the fact that the JVM’s garbage collection and allocation are now ludicrously well optimised.

At the moment it has a basic set of working operations. Unfortunately the performance for one of the crucial operation blows goats. It’s very very slow for appending to the right of large strings, and causes outrageous memory overflows. smallString.append(largeString) is pretty fast (I measured it at about 50% slower than appending to the end of a StringBuilder when averaged over a medium large file).

I know what the problem is though: A stupid list implementation. I tried to stick too closely to Haskell laziness and failed miserably because the JVM doesn’t handle things like that well. I’m going to rewrite it in more idiomatic Java and with more careful attention to detail, and I hope to get the desired O(1) append in every case.

I’m debating giving Nice another try and rewriting parts of this in it, particularly the list implementation – because of how I intend to handle it, it’s the sort of thing multiple dispatch and functional programming would be *really* handy for.

Update: Ok, maybe I don’t know how to solve it. I’ll put more thought into it and see if I come up with something. As an alternative plan, someone I know pointed me towards Ropes, which is an implementation of a very similar thing for C++ / C. Very likely worth my looking at for inspiration / porting.

Functional programming lies

I like functional programming. A lot. I find it an extremely natural mode of thinking in many respects, and even in imperative programming a sprinkling of functional support helps a lot. There are many practical advantages to it as a discipline.

So why are some of the main reasons advocated by people who don’t know what they’re talking about (a category in which I do find myself grouped more often than I’d like) complete lies?

In particular:

“Because Haskell is a pure language the compiler can automatically memoize functions for you”.

No it can’t. It would be nice if it could magically infer when it was able to do so, but it doesn’t. Lazy evaluation causes enough memory issues without automatically memoizing things. I’m not aware of any Haskell compiler which does this, and GHC certainly doesn’t. (As an added annoyance, there’s no nice way of memoizing a function at all).

A related lie is common subexpression elimination. Haskell doesn’t have side effects, so you don’t need to worry about that aspect of CSE, but it does have lazy evaluation. Partially evaluating a term has the ‘side effect’ of increasing its memory footprint significantly, so CSE can result in some very large space leaks if you’re not careful.

Other more minor lies include implicit parallelisation – it’s not there yet, there are some suggestions (which I’ve not personally evaluated so cannot comment on the veracity of) that it’s not nearly as plausible as we’d like it to be.

Advocacy isn’t a bad thing, but please stick to the facts.

Tail call optimisation in Javascript

I just happend across this old link

Basically it’s a (surprisingly elegant) way of creating tail call optimised functions in javascript.

There’s a slight subtlety with it unfortunately – you can’t simultaneously have a function call itself in a non-tail recursive manner. If you do it will break things.

It claims to support mutually recursive functions, and I think this is true, but I bet you’ll find there are some finicky details which can cause the stack to grow unboundedly before the optimisation kicks in, and I think you might have trouble properly optimising mutally recursive calls in this manner.

Still, very cool.