Wednesday, 24 October 2012

The future of .NET lies in Mono. The future of F# lies in MonoDevelop.

It's been a year since I last wrote about F# and Mono. What's happened since then?

F# 3.0 has recently been released, bundled in with the new all-grey, ALL-CAPS Visual Studio 2012. The biggest new feature is type providers, bringing some of the benefits of dynamic languages into type safe world. Innovations like type providers deserve more industry attention. I really hope these ideas will spread and hopefully languages like Scala will pick them up pretty soon so more developers (including me) can enjoy the benefits.

OK, that's cool, but how is good old F# doing? Well, about the same. It lumbers on in obscurity under the massive shadow of Microsoft and whatever crazy idea the company is currently peddling (Win8 metro UI, touch-screen laptops, WinRT, $100 surface covers, pretending Silverlight never happened, etc...) F# is still awesome and deserves a lot more attention and adoption.

Take a look at ThoughWorks latest Tech Radar. F# distant relatives (as in fairly new "functional-first" languages) Scala and Clojure are steaming ahead and have both reached "Adopt" status. F# is stuck in "assess" never-land. I don't see many signs of that changing anytime soon.

F# has limited credibility because of Microsoft. Even though F# is actually open source, it has a very small open source community. The development is completely driven from Microsoft, and there is very little "open source buzz" about it, typical for any Microsoft products. F# moves with the same slow cadence as Visual Studio, which is software terms are eons between releases. Any big and open F# frameworks are sorely lacking. Microsoft's completely r******d (there, I said it) messaging regarding F# and .NET is also to blame.

On messaging; firstly, there is the total confusion about .NET. Where is that going? Windows8 is all about HTML5. Anders is doing Typescript now, silverlight is dead. There's a lot of frustrated .NET developer out there. I've predicted that Mono is future home and legacy for .NET, and it looks more likely every day. As a die-hard MSDN developer you might frown upon this fact, but really it's not a bad thing. Open-source and Mono has a lot to offer, for instance OS independence. This is absolutely critical to continue to drive adoption.

Secondly, F# has always been the odd one out in the .NET space (compared to headline technologies such as C#, VB, ASP). If Microsofts messaging on the future of .NET is confusing, their messaging on what F# is and supposed to be used for is crazy; "Use C# for everything, and if you're an academic do some data analysis check out F#". Screw that, F# is superior to C# in every single way, for any application. Microsoft should promote the hell out of it and stop pussyfooting about. However, I have very little faith that this will ever improve, and F# is (and always has been) dancing close to the edge of oblivion.

There is a big F# shaped hole in the language space currently, on the JVM and elsewhere. Like I stated a year ago, if F# did run on the JVM the story would be completely different, it would have massive adoption. It beats Scala on every single point, and is a perfect candidate for "the static typed language of choice" in your language toolbox. Today people are seriously looking into Haskell when they get fed up with their gnarly python/ruby projects. That's completely nuts if you ask me, I don't believe Haskell is the answer for any real-world problems, but let's keep that for a future blog post. F# should be what comes to mind first!

So what about Mono and open source then? Don Syme spoke at the recent MonkeySpace conference, and generated a lot of buzz. .NET has never been sexy technology in the hands of Microsoft, but the Xamarin guys are turning Mono into just that. MonoTouch, MonoGame, Unity are some really good products. Mr Don Syme, this is where you and your language belong, this is how you take F# to the next level. Forget about all the in-fighting and bickering at Microsoft and focus on what's good for F#. That is to embrace Mono fully, it's your number one platform.

The culture shift for developers who's been living inside the Microsoft/MSDN bubble moving to Mono is drastic. Mono is an all-out open source community with all it's up and downsides. Say goodbye to stable, supported releases every 3/4 years and hello to nightly builds and pull requests. That certainly won't fit all current .NET developers, like lemmings they'll just move along to whatever Microsoft is feeding them next. Could that be the native renaissance perhaps? :) Real .NET enthusiast should free themselves from the Microsoft shackles and embrace Mono, they'd be much better for it. Join the community, contribute improvements to the garbage collector. Go to awesome conferences in Boston, have fun!

To summarise, how do we save this gem of a language? F# must break out of the Microsoft prison. Ideally I'd like to see a couple of key members of the team to actually leave Microsoft, get some funding and set up a independent F# foundation (or maybe join Xamarin). This foundation could pursue important issues like sponsoring key libraries like web frameworks, making sure the F# MonoDevelop integration is top notch etc. So while Microsoft is committing corporate suicide with Windows8, the .NET and F# community needs to move on.

The future of .NET lies in Mono. The future of F# lies in MonoDevelop.

Monday, 27 August 2012

Some more Datalog

I've written about datalog and Datomic a bit recently. To conclude here's another post comparing execution speed with the contrib.datalog library, by Jeffrey Straszheim. Clojure1.4 ready source can be found here.

The example I'm using in my benchmark is a simple join between two relations, in datomic/datalog it would look like this; In contrib.datalog the same query requires a bit more ceremony, you can write it like this; In my previous posts I described a number of different way to use core.logic, unify+clojure.set/join to replicate the same query. How does the execution times compare? I use the same benchmark as in the previous post (the same query, with 5000 joins between the 2 'tables').

Datomic/datalog is fastest by far needing ~11ms to complete. Second fastest is the unify + clojure.set/join solution described here about an order of magnitude slower at ~150ms. The core.logic defrel/fact and contrib.datalog is about equal in speed at ~320ms, ie. 2x slower than unify+join and ~30x slower than datomic/datalog.

Conclusion

My recent datalog posts focused on querying in-memoy data structures (like log rings etc). This is not exactly what Datomic was designed to do, still it's query engine performs really well. An added bonus is that it's low on ceremony. The recently announced Datomic free edition eradicates some of my initial fear of using it in my projects. The main drawback is that Datomic is closed sourced, even the free edition. Another detail that's annoying is that even if you're just after the datalog/query machinery -- by adding datomic-free, you pull in all of datomics 27 jar dependencies weighing in at 19Mb. That's quite a heavy tax on your uberjar.

There are certainly alternatives, like core.logic and contrib.datalog. But the order of magnitude worse execution time can be hard to live with if your datasets are big. By using datomic/datalog queries you also have the flexibility to move into disk-based databases if your datasets explodes. More on this in upcoming blog posts.

For completeness, here's the join-test function I used for the contrib.datalog benchmark;

Sunday, 12 August 2012

cKanren time!

Mr David Nolen recently published core.logic 0.8.alpha2, with added cKanren (c for constraints) support. To celebrate this glorious event I'm writing up some core.logic/cKanren stuff I've been looking at recently.

Enter the Queens 

If you've followed this blog, you've perhaps seen my previous posts on solving N-Queens in core.logic (part1, part2). How will this look and perform using the new shiny cKanren extensions in core.logic 0.8? Obviously there are many (new) ways to solve this problem, here's a core.logic-irized version of the solution described in the cKanren paper (please read paragraph 4.2 for an in-depth explanation); distinctfd (with infd) is a really nice addition to core.logic, they really help me personally write logic programs. How does this code perform? It's very similar in speed compared to the (non-fd) core.logic solution described in my previous posting, not bad, all extra cKanren expressive power without any performance drop!

Sudoku time

How would you use core.logic to solve sudoku? Let's start by looking at a simple all-Clojure functional solution; A few things are worth mentioning. First, this code finds all (potential) solutions of a given board layout. This is a bit strange since a true sudoku board should only have one solution! This does make it a bit more similar to logic programs (which typically looks for many solutions), and gives you some nice perks; you can use this code to check if a given puzzle is indeed a true puzzle. Secondly, in order to terminate faster, this snippet uses a quite common sudoku heuristic called "most constrained". At each level of the backtracking search it will consider the open squares in order, sorted after the least possible numbers (i.e. most constrained first). This helps to "fail fast" and minimise the dead alleys we recursively search.

How would we do this in cKanren? As we'd expect the code comes very close the the definition of the rules; We have 9*9 squares, each square can contain a number from 1-9, the numbers in each row, column and 3*3 sub-square must be unique.

In this example I will use a 4*4 sudoku for simplicity. That's it, exactly how the rules for sudoku was written, logic programming really is magical!

Writing it this way is good for understanding the solution, but not very practical for a real 9*9 board. Fortunately we can write some more helpers to make this compact, here's an example from Mr Nolen himself; This solution uses a "pseudo" goal call everyg with is similar to all-distincto in the previous example.

So how fast is this then? How does it stack up against the hand-rolled implementation above? Well, on an empty board (all squares open) the hand-rolled code finds 5 solutions in 400ms, while this code above get's into a (>5min) loop. For for more realistic "hard" boards the core.logic solution is on average 20x faster than the hand rolled code (much less temporary objects I recon). Finally, on really evil boards like this one, discovered by Peter Norvig; the core.logic code terminates in ~6 seconds where as the hand rolled code loops forever (well, I gave up after 20 minutes).

Conclusion

In most cases where "searching" is involved, I warmly recommend using core.logic. The expressive power makes for easy to read code, and the performance cost over hand rolled code is either not very significant or reverse (i.e. core.logic is faster). The new constraints primitives (cKanren) in core.logic-0.8 is a great addition to an already impressive library.

Some other stuff
  • The excellent cKanren paper is getting a bit obsolete. It's still a very good read, but for the latest innovation check out it's github page, and ofcourse core.logic.
  • If you can't get enough of logic programming, the next step is to dip into the ocean of Prolog, there are plenty of awesome (and practical) books written over many years. Here's a good list of books to get you started

Monday, 23 July 2012

Untying the Recursive Knot

Here I present a couple of examples of the functional design pattern "untying the recursive knot". I've found this useful in a couple of occasions, for instance when breaking apart mutually recursive functions. Material inspired by Jon Harrop's excellent Visual F# to Technical Computing.

First, let's look at a simple factorial implementation using direct recursion; We can break the direct recursive dependency by replacing the recursive calls with calls to a function argument; We have now broken the recursive knot! The functionality can be recovered by tying the recursive knot using the following y combinator;For example;This has given us extra power, we may for instance inject new functionality into every invocation without touching the original definition;Now for a more practical example when we have mutually recursive functions;We can break these functions apart using the same strategy as with fact' above;Please note that the (declare ...) form is no longer required. The functions are now entirely independent and could live in different namespaces.

Using the same y combinator above, we can get back to the original functionalty;A handy pattern to add to your functional toolbox.

Tuesday, 17 July 2012

Replicating Datomic/Datalog queries with core.logic, take 2

This is a follow-up to my previous post on datalog-equivalent queries in core.logic.

Here I present an alternate way to do the unification and join inside core.logic (without having to use clojure.set/join). It uses the the relationships / facts API in core logic, described here. First let's consider this datomic query; In core.logic we start by defining the relationships between our 2 datasets; This mirrors the layout of the data above. The actual datapoints are defined as facts, and once we have those we can do a core.logic run* using goals with the same name as our defrels; The join is accomplished by using the same lvar (email) is both defrel goals.

Now consider a slightly more complicated query; Applying the same technique (with some more defrels) we get; Hmm, this looks suspiciously like a victim-of-a-macro(tm), maybe something like this; The two examples above can now be written like so; An important point here is that we have separated the definition of the relationships, definition (loading) of the facts, and the actual running of the query.

So how does this perform for larger datasets compared to the unification / clojure.set/join described in the previous post? If we look at the time for running the query it's ~33% faster and about 12x slower than the optimal datomic/datalog query. Follow this link for some more datalog-y queries in core.logic.

Monday, 16 July 2012

Replicating Datomic/Datalog queries with core.logic

I've been toying with Datomic recently, and I particularly like the power of it's query language (~Datalog). Mr Halloway showed a couple of months ago how the query engine is generic enough to be run on standard Clojure collections, gist here. Here is an example from that page of a simple join; A question you might ask yourself is how can I use core.logic to do the same kind of queries? It turns out that it's pretty straight forward, and also very fast. Core.logic provides some convenient helper functions for unification, that we are going to use. Here's an example of how to get a binding map for some logical variables over a collection; Let's write a little helper function that maps binding-map over all elements of a seq (of tuples) (I'm using binding-map* so I only need to prep the rule once) We can use clojure.set/join to perform the natural join of 2 sets of binding maps like so; Note that I also pick out just the first/height lvars here, this corresponds to the :find clause in the datomic query. That's it really, not as generic (and data driven) as the datomic query, but working; Here's the kicker, for this join query the datomic.api/q's time complexity estimates to O[n2] (actually 22n2-50n) where as the time complexity for core.logic/unify + clojure.set/join solution is O[n] (10n). That means that for a run over a modest dataset of size 5000 the difference is 50x!

Edit: The Datomic query used in the benchmark is not optimal as it turns out. In the example below you'll see a more optimal version that's infact ~18x faster than the core.logic + clojure.set/join solution. Obviously this little example doesn't convey the true power of either datomic/datalog or core.logic/unifier. Be careful writing your Datomic queries, the running time can be vastly different!

Here some more of the datomic queries converted in a similar fashion.

Wednesday, 11 July 2012

N-Queens with core.logic, take 2

This post is a follow-up to my previous post on NQueens and core.logic, in which I tried to find the solutions using "pure" logic (without arithmetic goals) and basic minKanren / Reasoner Schemer building blocks.

After some excellent feedback and hints from Mr David Nolen (big thanks), I here present a greatly simplified (and faster) way of using core.logic to find all solutions. Credit also goes to good old Bratko.

First, let's fix the safeo function (and def-subo macro). In miniKanren, you can use arithmetic goals given 2 prerequisites; the fresh variable must be bound to a finite (number) space and we much use project to bind the values. This means we can get rid of subo altogether.

Project is mentioned in passing in the Reasoned Schemer book, it says "project is syntactically like fresh, but it binds different values to the lexical variables. project binds walk*ed values, whereas fresh binds variables using var". What that means in this case is that we can perform arithmetic operations of the projected variables. Here's our new safeo; This works if the x's as bound to number range with membero (remember that the y's are never fresh), this is done in a updated queens-run macro; As you can see, we got rid of subo (and all it's associations). That improves performance on a 6-queens run with ~5x

Next, we want to get rid of the big macro above and replace it with some readable looping constructs. To replicate the block of safeos generated by this macro (the gen-safeos fn), we are going to need 2 loops, one outer loop that goes over all N queens q, and one inner loop that for every q checks that it's safe against all other queens. Its time for some core.logic pattern matching magic!

Let's change safeo again. Instead of checking if 2 queens are not attacking each other, it checks if a given queen is not attacking any other queen in a given list (this is our inner loop); There's a couple of things going on here. defne is a convenience macro to build conde functions (which you end up doing all the time), secondly there are some clever destructing / pattern matching going on to pick the head / tail of a list and recur.

Now for the outer loop, let's introduce another recursive "conde function" called nqueenso, this function should loop over all queens in a list, check that they are all safe against each other (using safeo). It also needs to bind the x variables to a finite number space using membero; We're almost done now, we just to need rewrite the (run* ...) form. We can actually do without the (fresh ...) expression by creating core.logic logical variables (lvar) directly, this also eliminates the need for a macro to generate n symbols. Here's the whole thing; As you can see, with looping we are generating drastically less associations for core.logic to consider, that's good for performance.

Now it's ~70x faster than the original solution in the previous post. For a 8-queens run, this is ~50x slower than the hand-rolled functional backtracking solution in the very first posting. That's still pretty good for a generic prolog machinery with all the extra expression power that it packs.

Next part in this series will use cKanren functionality that is being worked on at the moment in core.logic. That might be even faster! 

Saturday, 7 July 2012

N-Queens with core.logic, take 1

I've been "hammock-reading" the excellent Reasoned Schemer book the last couple of months, on my quest trying to develop a gut feel for when logic programming, as defined by miniKanren/core.logic, is applicable.

My first attempt is to apply it to a problem where (as it turns out) miniKanren isn't a good fit, n-queens. What you really need for this, in logical programming world, for this problem is something called contraint logic programming (CLP) which is implemented (for example) in cKanren. The good people over at core.logic are working on integrating CLP and cKanren in core.logic as we speak, so I intend to revisit this problem as that work progresses.

Let's have a crack at this problem anyway shall we? I've previously posted a functional implementation on n-queens in Clojure, and it's both nice to read and fast. What would this look like using core.logic? 


Here's the core function (in Clojure) which determines if 2 queens are threatening each other.
The main problem in core.logic is the subtraction operator, which cannot be applied to fresh variables. We need a goal that has all the subtraction algebra "mapped out" as associations, let's call it subo. If we had that, our safeo function could look like this;
With subo (for a (range 2) subtraction) like this; Fortunately this isn't too bad, since in the classic case we only need to subtract numbers in (range 8). We can write a macro that generates a subo for any range our heart desires.

Next up the associations for queen pieces. We can brute force this as well by writing safeo associations for each queen piece against each other and finally constraining each queen to a unique row. Typing it out for 4-queens would look something like this; Please note that the y variables doesn't have to be fresh since they can only take one value (each queen is determined by an unique y variable).

Here's a complete listing to the whole thing, with an example of a 7-queens run; So how does it perform? Well, you guessed it, terribly. My previous functional Clojure implementation finds all 4 solutions for 6-queens in ~7ms. The core.logic one above does it in ~6.5 seconds, 3 orders of magnitude, ouch!

It's quite possible that this brute force approach is a very inefficient way of solving n-queens using miniKanren. Maybe building / removing queens from solution lists are a better approach? Also, cKanren in core.logic promises much faster and cleaner solutions. Either way, I'll keep you posted...

Tuesday, 3 July 2012

Some thoughts on logging

Have you ever tried to log from multi threaded program? Have you tried to make sense of the log output which multiple subsystems were logging to? Have you tried to do average latency calculations based on that log file?

If you reading this blog, I am guessing you answered yes to a couple of the questions above.

There are multiple problems here; multiple producers (race conditions), out-of-order logs, conflated subsystem in the same logs etc. You gotta put a lot of effort into you log post-processor to make any sense at all of the data, decorating it with various metadata to make it at all possible.

In this post I point out a few ways you can use Clojure (both the language and it's general ethos) to overcome these problems. The solutions here are primarily tailored to "pipeline systems" where you want to find time consuming bottle-necks and produce latency reports etc. For simplicity, this is in-process logging, where all the parts (threads) can share a log resource and tick timer etc.

TL;DR the complete code snippet

Agents

First off, the race conditions; if the log is simply a file, or a in-memory data structure, you have to somehow serialise the "emit" calls. Conventional wisdom would have you put the emit call in a critical section, but this is a) ugly b) can introduce deadlocks c) can effect the system under stress. We want to post a log entry using a lock free, asynchronous mechanism, that's why we have agents in Clojure;
Please note that when emitting with timestamps, we take a snapshot of the time instantly (in the context of the calling thread), not in the agent-thread context later on.

Tree Logging

How do we apply structure to the log data? One idea is to put the log data into a tree instead of a flat vector (or file).  Then log entries from different subsystems can be separated (for easier post-processing), and we can express dependancy between log events for latency calculations.

Lets say each log entry is associated with one id and multiple correlation ids. The id is typically an UUID which you assign to a request, operation, instruction that "travels" through multiple parts of your system. The correlation ids can be used a splitting your logs into categories of arbitrary depth, yield possibly more meaningful reports etc.

Here's how such a tree structure can be built using Clojure's maps and the mighty assoc-in function; The logger handles the timestamping for you, it also gives you functionality such as extracting chronological logs for ids, and timing/latency reports.
Ok, this looks like it might perhaps work, but there are some drawbacks; we must keep the tree in memory for processing, which can be hard for huge logs, also serialisation to disk is trickier (but no really if you have a reader). We're also forcing a structure upon the log data, that feels awkward. Supplying the id, and corr-ids is not as clean as it could be.

Metadata

Let's get back to a simple flat log and more metadata in the events. We use the metadata to express the categories and other dependancies between the events that we used the tree for in the previous example. In a sense, we are still using a tree (or maybe even graph) data structure, but the branching is described with metadata in sequence of events. Using the emit function describes under the "Agents" paragraph above, here and example of some "connected" log events;
The helper functions also becomes much cleaner this way;
Please note that these functions take a (de-referenced) log rather than using @log directly. This helps testing, but is also very important for more complicated (looping) functions which should work on a stable snapshot of the log events.

Conclusion

The flat log file, with simple events described as Clojure maps worked out really well, and it's certainly more idiomatic. The log is easier to serialise, we only need parts of it in memory for meaningful analysis, we can treat it as a continuos stream. The analysis functions that we write can leverage the power of Clojure's library directly and compose beautifully. Also, we are not forcing any structure (or schema) on the log events (more than any analysis functions expect) which make it very flexible and future proof. The only price we are paying is additional (redundant) metadata to that can be more cheaply expressed in a tree data structure.

Here's a complete listing of a event logger, using metadata, with statistical reporting.

More reading

Thursday, 17 May 2012

Distributed Actors in Clojure

Here's another post on a topic that have been discussed since the dawn-of-time, is there is nice and idiomatic way to write Erlang/Actor style distributed programs in Clojure? There has certainly been a few attempts, but Rich's post (above) still holds true today.

First some clarification; I am not primarily thinking about number-crunching, map/reduce-y stuff, where Clojure has a pretty good story;

Akka and the Erlang legacy

I am trying to write programs that solve problems in the areas where Erlang typically excels such as;
  • Event-driven, asynchronous, non-blocking programming model
  • Scalability (location transparency etc)
  • Fault tolerance (supervisors, "let it crash")
The closest we've got on the JVM is Akka, which claims to have all features (and more) listed above. Akka is the "killer app" for Clojure's sister-language Scala, and is very feature rich and performant. Levering it's power in a safe and idiomatic way is certainly appealing.

However, interfacing to Akka from Clojure is not nice, and certainly not idiomatic. Some work is clearly needed in order to improve Akka/Clojure interrop. The bigger question is if it's worth pursuing? Even if the interrop is made as pain-free as possible, how badly will it clash with Clojure's underlaying design and philosophy? For instance; Akka comes with a STM, how nasty will that be when used in conjunction with Clojure's own?

Update 2 Akka/Clojure libraries has emerged since this article was written, which solves some of the problems I was facing; akka-clojure and okku. Perfomance compared to Scala/Akka is yet to be determined.

Wishful thinking

Ideally, Clojure should support distributed actors in it's core, that looks, behaves and interrops nicely with it's other concurrency primitives. It's pretty easy to create a ideal-world straw-man for how this might look from a code/syntax perspective; Termite is a good place to start. Here is a cleaned-up version of the hello-world examples in the gist above.

Many problem arises, serialisation is a big one. Since Clojure's data structures can contain "anything", like Java objects, some limitations needs to be applied to strike a good usability / performance balance. Limiting the stuff you can distribute amongst actors to mimic Erlangs atoms/lists/tuples are probably a fair trade off (all you need is a hashmap right?), and maybe baking in Google Protobuf for efficiency.

For data transport / socket stuff, I'd vote for using a message queue such as 0MQ or maybe even RabbitMQ, this would simplify and empower matters greatly.

With all that in place, it would be possible to build Clojure equivalents of Erlang's OTP, Mnesia etc, now that's a world I want to live in! :)

More reading

  • Learn you some Erlang for Great Good
    Quickly get into the Erlang frame of mind
  • A vision for Erlang-style actors in clojure-py
    Part1 and Part2
  • Exlir
    ErlangVM language with support for Lisp-style macros
  • Joxa
    Clojure-style Lisp for the ErlangVM
  • Avout
    Distributed STM for Clojure, for synchronously updating of shared state.
  • Jobim
    An attempt to mimic the Erlang programming model in Clojure

Tuesday, 10 April 2012

What is a software company?

Software is different from most other things humans build, hence companies creating/selling/licensing software must be different from other 'production' companies as well? Some definitely are but the vast majority are still trying to apply old civil engineering practices to software development. Why are they wasting so much time and money on upfront sizing, planning and tracking when all empirical evidence tells us it maps so badly to the actual process of developing software? Why haven't most software companies learnt the hard lessons and started to operate like Valve?

The financial costs of developing, deploying and having software in production is one big factor of software development being kept in the shackles of dusty old engineering practices. If we are spending all this money on development, we instinctively want to know exactly when it's going to be ready, with what functionality and quality. If the plan is detailed and rigid enough, surely the car factory website will open in exactly 6 months and 12 days from now! This belief is so infested in management that it seems impossible to argue against, and what's worse; it constantly gets in the way of developers actually writing code and innovating new features. It's my experience that successful software projects deliver on time despite all planning, not because of it.

However, the times are a-changin'. SaaS, PaaS, IaaS provides are challenging some of the old financial truths about developing and having software in production. The cost of data centres is completely removed, and the costs of production scales with usage and popularity of the product. A new breed of software companies are emerging.

The "half life" of software is very short, and it's getting shorter. A software product is in practice worthless (from a technical standpoint) the moment it's shipped, it's very easy for competitors to copy and improve. What's is true this quarter is not necessarily true the next. New languages and frameworks come along all the time, and can drastically change the landscape of possible solutions to a given problem. A company that starts coasting on existing technologies and investments becomes obsolete very quickly.

So what is the true value of a software company? It's the rapport built up with its customers. It's the products that's currently being worked on. It's the awesome demos of new features/products. It's the ideas in the heads of its employees. It's the company's ability to change / alter / transform the existing products. Already shipped products are easy to clone, but the ideas and innovation are much harder for competitors to keep up with.

Also, good software companies create high quality and simple products. While it's easy to copy a program's functionality, it's harder to copy a program that is very well written. Why? The well written, and simpler original, can more easily be changed and altered to meet new requirements. Any poorly written copy will suffer from alot of accidental complexity and will not be able to keep up with a constantly evolving original.

Most companies in the software space will from time to time ask themselves if they should start a big re-write project versus keep on tweaking the existing stuff. My view is that a well functioning software company is constantly re-writing it's products. It's constantly looking at what's happening in the language/framework space and trying to apply them to its own problem space. They are on a never ending quest to find the simplest, cleanest, most agile implementation of the particular problem.

So what about the developer community? Rich Hickey speaks about the self-obsessed meta culture that has sprung up amongst developers, where the convenience and ease of the developers is paramount. To the detriment of what really matters, the functionality and quality of the software produced. This culture is wide spread up the management hierarchy. The language / framework cargo cult that is so strong in the software developer community is an symptom of this culture. Middle management is obsessed about using industry standards and "we can't possibly use technology X, because we can't hire cheap grads with that knowledge" is very limiting on their company's capability to produce new and exiting products.

In conclusion, companies in the software space have to make up their minds. Are they software companies? If yes, are they - in order to be truly successful - ready to break the shackles of conventional wisdom and set their developer talent free? Or, are they a service providers? Licensing and outsourcing their software needs in order to bring a appealing product / brand together. If they are service providers, they are most likely wasting a lot of money on in-house (frustrated) developers when they should just realize that kind of business they are actually running, and act accordingly. Both are perfectly valid business models, but are too often mixed up.

Wednesday, 14 March 2012

Adding Live Unit Feeds to Frinj

A couple of weeks has passed since I've pushed Frinj to github and blogged/tweeted about it. The response have been pretty awesome, one highlight being when @stuarthalloway showed me a frinj+datomic example gist on the #datomic IRC channel. In short, the Clojure community is #badass.

Frinj comes with a big database of units and conversion factors, and while as many conversion factors are "eternal", others aren't. Exchange rates for instance has to be kept up to date to be relevant. The Frinj unit database was designed to be updatable, both for usability when doing various calculations, but also for rates that constantly change. This is the reason the frinj.calc namespace exposes the (frinj-init!) function to reset the unit database to a know baseline (in case you write over some factors etc). Clojure's support for atomically updating state is ideal for this purpose, the calculator's state is kept in a number of refs and thanks to the STM always kept consistent.

Frinj now supports live currency exchange rates, precious & industrial metals and agrarian commodities, by adding the concept of unit feeds. This is handled by the new frinj.feeds namespace, and the basic idea is to have multiple feeds sharing one ScheduledThreadPoolExecutor for periodically updating Frinj's state. The generic feed utility functions (start-feed, stop-feed, update-units!) are separated from the feed specific ones. For more information see the wiki and source. As you can imagine, these live units rates are just a couple of many potential feeds.

Currencies use the 3 letter (ISO 4217) currency acronym (uppercase), and the metals and commodities use capitalised names, see below for examples.

I've also added an new convenience namespace called frinj.repl that will initialise the built-in units, start the feeds and immigrate the rest of the frinj vars.


Next time, I'll explain how to use Frinj in ClojureScript.

Saturday, 3 March 2012

Announcing Frinj, a practical unit-of-measure calculator DSL for Clojure

I am proud to announce a new Clojure project called "Frinj".

 Frinj is a practical unit-of-measure calculator DSL for Clojure.

 Key features;
  • Tracks units of measure through all calculations allowing you to mix units of measure transparently
  • Comes with a huge database of units and conversion factors 
  • Inspired by the Frink project
  • Tries to combine Frink's fluent calculation style with idiomatic Clojure

Full source code available on github.

To wet your apatite head straight over to the sample calculations page to see what Frinj can do!

I also want to explain that despite it's name, Frinj was never intended to be a clone of Fink, and thus does not support the entire Frink language. But since it's a Clojure DSL, it doesn't have to!

There was a couple of reasons I decided to create frinj;
  • I wanted the power of frink but with Clojure idioms. 
  • I love Frink, and wanted to learn more about it.
  • Frink isn't open source. 
  • I wanted to have some fun.

So please take it for a spin, it's damn fun! 

Tuesday, 21 February 2012

Saturday, 18 February 2012

Some thoughts on Clojure performance

Edit: This post recently re-surfaced on hacker news and caused a bit of a stir, mainly because of a slightly sensational/misleading title (was "Why is Clojure so slow?"). I wrote this before Rich Hickey's Clojure/Conj 2011 keynote was published, in which he talks about most of my concerns (and outlines possible solutions).

Clojure is great in many ways, but one thing it can't be accused of is being particularly fast. What I mean by fast here is the speed in which Clojure programs execute. This is a well known issue in the Clojure community and have been discussed on the mailing list and stack overflow. I am not intending to troll or fuel any fires here, just jotting down some of my findings when looking into the matter.

Measuring the speed of code is quite tricky, because there are many parts to a program. This is especially true for Clojure programs where the JVM, Clojure bootstrapping and dynamic compilation is part of the puzzle. But the fact remains, running tools like Leiningen (lein) or "jack-in" is annoyingly slow, mainly because Clojure programs takes a long time to "spin up". Further more, even when Clojure is up and running, it's not particularly fast compared to it's JVM cousins, see The Computer Language Benchmarks Game.

Getting going...
The slow startup time is probably what you will notice first when starting to code in Clojure. Anything from running your first "hello worlds" to starting the REPL is painful. Here's some average numbers for a simple "Hello world" program taken on a 2.5GHz Core2Duo MacBook Pro;

Language Total running time OSX Relative Total running time Ubuntu Relative
C (printf) 0.011s 1 0.001s 1
C# (mono) 0.085s 7.7 0.027s 27
F# (mono) 0.105s 9.5 0.036s 36
Java 0.350s 32 0.038s 38
Scala 0.710s 64.5 0.228s 228
Groovy 0.740s 67.4 0.335s 335
JRuby (non-compiled) 0.820s 74.5
Clojure (uberjar) 1.250s 113.5 0.652s 652

What we can see it that Java itself accounts for 0.35s of the startup time, but unfortunately Clojure adds another second(!) on top of that. This 1.3s pause before main gets called is why Clojure is unsuitable for "terminal scripts". The running time of any scripts (like lein or starting the REPL) will be totally dominated by the startup time. Most Clojure developers will not notice this too much to, since they spend almost all their time in the REPL itself, but users of those Clojure programs will!

The CLR (mono) is about 4x faster getting going than the JVM. This is a big plus for the "#-py" languages. Also note that the difference between F# and C# is much smaller than Clojure and Java, so there isn't any excuse/president for more functional/declarative languages to start slower then their "bare" counterparts.

So why don't we use the Clojure/CLR on mono for stuff like lein then? Well, as it currently stands, the Clojure startup times are even worse on the CLR. The same hello world example as above clocks in a 1.8s! (using the debug Clojure/CLR assembly) - the difference between ClojureCLR and C# is an order of magnitude worse than Clojure and Java, some work left to be done in the ClojureCLR project...

What's taking so long?
Daniel Solano gave a talk on conj/2011 about Clojure and Android (slides), the performance part of that talk gives some valuable insights into Clojure internals and what happens when it starts up. My summary is that it spends 95% of the startup-time loading the clojure.core namespace (the clojure.lang.RT class in particular) and filling out all the metadata/docstrings etc for the methods. This process stresses the GC quite a bit, some 130k objects are allocated and 90k free-d during multiple invokes of the GC (3-6 times), the building up of meta data is one big source of this massive object churn.

Edit: By using the "-verbose:gc" flag when running the clojure test above, I notice a single collection, taking some 0.018s. This is different to Daniel's findings, but hardly surprising since he measured performance on the Dalvik VM.

Daniel mentions a few ideas to improve the situation, and some of those ideas sounds pretty good to me;
  • Having a separate jar for development (when you want all the docstring etc in the REPL) and a slim one with all that stuff removed to "runtime" jar (not to be confused with the existing clojure-slim jar file)
  • Serialising the clojure.core initialisation so it can be dumped into memory from disk when starting up
ClojureScript to the rescue
ClojureScript and Google's blistering fast javascript engine V8 is another way to go. When using the ClojureScript compiler on a hello word example with advanced optimisation, we end up with some 100kb of Javascript. The V8 engine runs this is in 0.140s, which is 2.5x faster than the "bare" Java version and 9x faster than the Clojure/JVM version! The Google Closure compiler certainly helps here by removing lots of unused code, and the resulting Javascript file is indeed free from all docstrings etc.

Also, Rich Hickey did mention ClojureScript as "Clojure's script story" when he unveiled ClojureScript last year - one of the main benefits is the much improved startup time.

Up and running...
How fast is Clojure at running your code once it finally has got going? A look around the The Computer Language Benchmarks Game gives you a good idea. Clojure is on average 4x slower than Java and 2x slower than Scala. There are a couple of reasons, and the biggest factor is Clojure's immutable data structures. The fact is that immutable data structures will always be slower then their mutable counterparts. The promise of Clojure's persistant data structures is that they have the same time complexity as the mutable equivalents, but they are not as fast - constant time factors do play a big role in running times. Most of the benchmarks above run for 50-200 seconds, so Clojure's startup time will be a factor in the results as well. Finally, dynamic languages a generally slower than static ones, because of the extra boxing overheads etc.

Conclusion
Where does all this leave us? Clojure is a beautiful, powerful and very useful language, but (in it's current incarnation) not great for small script-y programs. The problems with startup time can be solved, either by changes to Clojure itself or by exploring the ClojureScript route. I personally like the javascript track; Javascript has lower processor and space overhead than the JVM, so by making ClojureScript-scripting better, Clojure can be more widely used, reaching embedded systems etc.

However, in order to make ClojureScript a viable option for non-browser programs, there are certainly more work to be done. Some Node.js integration exist today, but a ":bare" compilation target would be a good addition. Then comes the small task of building up good out-of-browser APIs.

Saturday, 28 January 2012

Scheme as an External DSL in Clojure

This is a follow-up post to my previous "Scheme in Clojure" post.

This time we implement a Scheme interpreter as an external DSL. This means that we consider the DSL as completely foreign to the host language, so we need to write our own parser (or reader as it's called in Clojure) and interpreter. I have to admit that this is a bit of an academic exercise because the internal DSL version I wrote about previously is both smaller (less code) and faster (as fast as any other Clojure code). However, this can serve as an example of how to write parsers in Clojure and it also highlights how elegant and succinct such a parser/interpreter can be. And of course, it's pretty darn fun :-)

All source code is available on github.

Parsing

The reader is made up of two parts; a tokenizer and a parser.

The tokenizer reads a string and produces a list of tokens. I use a "tagged list" as described by Abelson / Sussman in SICP to distinguish between the types of tokens. This is a flexible technique for dynamic languages where we can't express token types like we can in a typed language like F#. Here is an example;
Next up is the parser which takes the list of tokens as input and produces a list of expressions (or combinations as they are called in SICP). Please note that the parse functions in this example first calls tokenize on the provided string.
One big benefit of parsing a "simple" language like a Lisp is how clean and simple the parser becomes. The whole thing is about 50 lines of code, and very elegantly expressed in Clojure (if you ask me :-).

Both the parser and interpreter relies heavily on Clojure's "destructing" feature to pick elements out of strings, lists etc. This is loosely related to pattern matching found in other languages (or in Clojure via core.match for instance). In my F# implementation of the Scheme interpreter, it's indeed this destructing feature of it's pattern matching I rely most on. Here is an example of extracting the head and tail (which happens to be the operator and it's arguments!) of a combination returned by the parser;

Eval-ing
Now that we have our list of expressions we can evaluate it (or run it). I use the mutually recursive eval/apply as described in SICP. Everytime I write this I am amazed by how simple yet powerful this is, here it is in all it's glory;
One trick I use is to store all built-in functions (as closures) in an environment map. So when we evaluate a combination like [:+ 1 1] the head of that vector (:+) is looked up in the environment and a fn is returned and punted over to apply. User defined functions are represented by lists in the environment and become a separate cond-case in the code above.

In the interpreter then environment is a stack of maps, with "roots" at the bottom containing all the built-in functions. When evaluating a let statement for instance, the locals are added to a new environment map at the top of the stack, in this way bindings can be overloaded in the local context. This is also how the arguments to functional calls are bound (and how recursion can terminate).

The bulk of the interpreter code is the implementations of the built-in functions, but then again none of them are especially large. All in all the interpreter clocks in at about 200 lines, giving us an entire solution (parser, interpreter and all) in about 300 lines!

Conclusion
Even though we wrote an entire tokenizer/parser/evaluator it ended up a small and readable. It's quite a bit smaller than the F# implementation, mainly because of the lack of any type declarations. How fast is it though? The embedded DSL implementation runs (fact 10) about 1.5 times faster than the external one. The F# version runs roughly as fast as the Clojure embedded one although is doing much more work (running interpreted).