Don't forget to fly

I saw this comic a while ago and it occurred to me during today's HUG. I think the analogy is obvious, but I'm going to spell it out anyway because I feel the need to rant about it. (As a side note, I know I've occasionally been guilty of what I'm ranting about. Hopefully I've stopped...) You like functional programming. That's great. You write C#/Java/C++/Brainfuck/PL-SQL/Malbolge during your day job. That's a shame, but oh well. You and everyone else. I bet you really wish you could use folds/lazy evaluation/lightweight threading/COMEFROM statements in your work code. Great. Me too. There's a lot of neat stuff in functional programming (and in the better OO languages. And in logic programming. And in a wide variety of other things). So, use it. Go wild. Write code. DON'T waste time posting endless blog posts about how closures are awesome and wonderful and here's an example of how they might work in Java. "Here's a nice bit of code I wrote" is one thing. "Here's how to implement a for loop. Isn't it awesome!!!"? Not so much. If you're interested in something, use it. Don't waste time thinking about how to shoehorn its features into a language you know far too well. You can fly. Stop thinking about how great it would be to do so and go out and do it.

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.

What's in a syntax?

I was looking at JGA earlier. Basically yet another instance of the JGreenspun pattern. I have my own implementation of the same sort of thing - JGA looks significantly better than mine frankly. But, even with a nice terse syntax, the kind of shenanigans one has to go through to make it work are pretty horrible. Take a look at some of my code snippets if you don't believe me (granted the snippets I had are not very terse, but due to heavy use of anonymous inner classes one is pretty stuck with using constructors, which with abundant generics quickly leads to some really horrible lines). Although you can get most (well, about 75%) of the functionality of a functional language like ML or Haskell into Java if you hammer enough, the result is fairly mindly blastingly horrible. Shorter syntax for declaration of anonymous inner classes would certainly help a bit, but I don't think it's really going to be enough. I think that until closures come along to Java (and I mean proper BGGA style closures. Anonymous inner classes just aren't going to cut it) I'm going to have to revert to the way of doing things that doesn't involve too much greenspun. And/or defect to Scala completely.