The power of nothing

I came across an article comparing F# and Clojure on a toy problem, a json treasure hunt to find a certain value in a large json document and print the path to it. Both are very nice in their own way. Personally I have a slight preference for the F# syntax and think I might want to try some serious coding with it.

Both basically pattern match over json types, and recurse for lists and objects. In F# you declare a union type and match over that, while in Clojure you declare a protocol and implement the protocol for the built-in types. Take a look at the article, F Sharp vs Clojure Toy Problem Shootout.

Now think about the return values in each case. In F#, the return value is declared as a union type with either a list of crumbs or a value named HuntResult.Null, while in Clojure, being dynamic, either the list of crumbs or the boolean value false is returned. This seems pretty standard, similar to what you'd do in pretty much any language, you're probably even wondering why I'm pointing it out. But look at how many lines are concerned with handling HuntResult.Null and false, respectively.

The Tailspin programming language handles things a little differently. Since Tailspin doesn't require that you return a value at all, you can just ignore all the failure cases and not emit a value at all. Not a value called nothing, literally nothing. This turns out to be a pretty powerful concept, drastically reducing the need for conditional statements and the returning of empty values. Here's the Tailspin code:

templates findAllTreasurePaths
  when <='dailyprogrammer'> do [] !
  when <[]> do $ -> \[i]($ -> findAllTreasurePaths -> [$i - 1, $...] ! \)... !
  when <{}> do $... -> \(def key: $::key; $::value -> findAllTreasurePaths -> [$key, $...] ! \)!
end findAllTreasurePaths

It's built pretty much the same way as the other solutions, pattern match on the json values, recurse on lists and objects and start building a result when the value is found. But all the code to handle dead ends is gone, if a dead end is hit, nothing further happens.

There is another difference here, though. The Tailspin code returns all treasures if there is more than one, while the F# and Clojure solutions only returns the first one found. Actually, "returns" is not an accurate description of what happens in Tailspin, rather zero or more values may be emitted.

Maybe we really did need to return only the first value found, then you will have to do a little more work in Tailspin to halt your search when a value is found. You also need to detect the failure case where nothing at all is returned and you need to check the next element of a list or object. To do that you need to wrap the recursive call in a list constructor so that you get an empty list for failure and match on the alternatives. You also need to track the current index into the candidate list:

templates findFirstTreasurePath
  when <='dailyprogrammer'> do [] !
  when <[]> do
    def list: $;
    [0] -> \(
      when <[](2)> do [$(1) - 1, $(2)...] !
      when <[<..~$list::length>](1)> do def next: $(1) + 1; [$next, $list($next) -> findFirstTreasurePath] -> #
    \) !
  when <{}> do
    def attrs: [$...];
    [0] -> \(
      when <[](2)> do [$attrs($(1))::key, $(2)...] !
      when <[<..~$attrs::length>](1)> do def next: $(1) + 1; [$next, $attrs($next)::value -> findFirstTreasurePath] -> #
    \) !
end findFirstTreasurePath

It takes a little mind-shift to get used to, but I'm still amazed at how well it works to program a flow where only things you care about proceed to the next processing step.