A little Tailspin

I was delighted to come across Uncle Bob's blogpost "A little more Clojure" the other day, where he concludes:
Now I want you to think carefully about how we solved this problem. No if statements. No while loops. Instead we envisioned lists of data flowing through filters and mappers. The solution was almost more of a fluid dynamics problem than a software problem. (Ok, that’s a stretch, but you get my meaning.) Instead of imagining a procedural solution, we imagine a data-flow solution.
Think hard on this – it is one of the keys to functional programming.
The way a programming language feels to use, like "fluid dynamics", is the main thing I was trying to get at in my previous article. Do your programming languages feel like molding clay, or building sandcastles or even wrestling bears?

This idea of thinking of data-flow, where streams of values get transformed step by step is the very foundation of the Tailspin programming language I am developing. To give a sampler of Tailspin, I thought I would follow the steps from Uncle Bob's article so please refer back to that as needed. At the end of the day, we should still remember that Clojure is a kick-ass production-ready language while Tailspin is still only a runnable prototype.

We'll begin with a function, called "templates" in Tailspin, that does nothing and an invocation:

templates primes
  !VOID
end primes

10 -> primes -> '$;
' -> !OUT::write

Note that when run, this code will do absolutely nothing. The "10" is sent to the "primes" template where it is sent into the void and nothing goes on to the next step. Tailspin does not have any null or nil values and does not require that a function returns a value each time. If "primes" were to output a value (or several values), the (each) value would be sent on to the string construct. To create a string, simply write something inside apostrophes. This is another foundation of Tailspin, that creation of values should happen in a very literal way. Inside the string, anything that starts with "$" and ends with ";" will be replaced by the value referred to. In this case we refer to the value with no name which is the current value coming through the "assembly line". The created string is then sent on to be written to the standard output. So now let's get the numbers from one to the input:

templates primes
  [1..$] !
end primes

When we run the program we get "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]" output. Note again that to create a list, we simply write the elements inside square brackets. The ".." operator produces a range, so the elements in the list will be 1 to the current value, inclusive. The bang ("!") indicates that the produced value should be output from the templates. Now we have to filter out all the primes:

templates primes
  [1..$ -> ifPrime] !
end primes

In Tailspin, we can just filter directly on the stream of elements and we will make sure that "ifPrime" outputs a value only if it is a prime, otherwise nothing should be output. Of course we start with the do-nothing function:

templates ifPrime
  !VOID
end ifPrime

When we run our "primes" program, all the values get sent into the void, but the list is still created so we get "[]".

To work out if a number is prime we will divide it by all numbers up to the square root of the number, so let's start by calculating that and modifying our program to output the value of "ifPrime" instead:

templates ifPrime
  $ -> sqrt !
end ifPrime

100 -> ifPrime -> '$;
' -> !OUT::write

This gives "10" as a result, so far so good!

Next we want to get a list of the integers between 2 and the square root:

templates ifPrime
  def root: $ -> sqrt;
  [2..$root] !
end ifPrime

What's new here is that we define "root" to be the square root of the input value, and then we use that value as "$root". When we run this we get "[2, 3, 4, 5, 6, 7, 8, 9, 10]" as we should.

Now we want to work out which of those numbers divide the input evenly:

templates ifPrime
  def n: $;
  def root: $ -> sqrt;
  [2..$root -> $n mod $] !
end ifPrime

We have to save the input value by associating it with the name "n" so that we can use it later in a context where the current value has changed. We don't need an anonymous function as in the Clojure solution, or perhaps we can view each step in a chain as an anonymous function. Anyway, we transform each value by taking the remainder when n is divided by it. The output is "[0, 1, 0, 0, 4, 2, 4, 1, 0]".

If there is a zero in the produced list, n is not prime. So how can we check that?

templates ifPrime
  def n: $;
  def root: $ -> sqrt;
  [2..$root -> $n mod $] -> \(<~[<=0>]> $n ! \)!
end ifPrime

A third foundation of Tailspin is to be able to match values through a simple illustrative syntax. A matcher is defined inside angle brackets and the matcher here says that it matches if the current value is not (by "~") a list (by "[" and "]") that contains a zero (by the contained equality matcher "<=0>"). If it matches, the value of "n" will be output to the following step, which is to just output it from "ifPrime". Since there is no further alternative matcher, the output will be nothing if the list contains a zero. The "\(" and "\)" delimit an inline templates definition. This one is anonymous as well, but could have been given a name after "\".

100 -> ifPrime -> '$;
' -> !OUT::write

(No output)

17 -> ifPrime -> '$;
' -> !OUT::write

17

Finally, changing back to running the "primes" program:

100 -> primes -> '$;
' -> !OUT::write

[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

OK, great, except for the "1", but I'm sure you can fix that. I'm not happy there, though, it still seems inefficient to keep dividing by all those numbers all the time. Couldn't we stop as soon as we get a zero?

templates ifPrime
  def n: $;
  def root: $ -> sqrt;
  2 -> \(
     when <?($n mod $ <=0>)> do !VOID
     when <..$root> do $ + 1 -> #
     otherwise $n !
  \)!
end ifPrime

So instead of doing the modulo operation for all potential divisors, we can start with 2 and here our inline templates has a series of matchers. The "?()" construct on the first allows us to compare a calculated value instead of the current value, and here we say that if the remainder is zero, we just stop by going into the void. If that doesn't happen, the next matcher is tried and if the current value is less than or equal to the square root of the input, we try the next number by sending it to be matched (by the "#" operator). If that isn't the case either, the input must be prime and we output it.

The result we get now is "[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]".  We lost the "2" (can you figure out why?), but I'm not concerned with that right now, I'm going to make more changes. So what if we use a similar trick to build the list of primes as we go along, couldn't we then just use that to test division only by the already found smaller primes?

templates primes
  def N: $;
  @: [];
  2 -> \(
    when <..$N> do $ -> ifPrime -> ..|@primes: $;
      $ + 1 -> #
  \) -> !VOID
  $@ !
end primes

Here we have some new constructs. When you "def" a value in Tailspin, it is immutable and can never change. But sometimes it is handy to have a mutable value, so each templates object has a mutable value called "@", which can be anything. Here we initialize it to an empty list. Then in the inline templates, as long as the current value is less than or equal to N we will increment and rematch after first checking if it is prime and, if so, append it to the list, which must be referred to as "@primes" because just "@" would have been the mutable value of the inline templates. Nothing is output from the inline templates, but at the end we output the accumulated list.

Running the program gives "[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]", so all is still good. Now we just need to pass the list we are building to the ifPrime templates and use it there. The final program looks like this:

templates ifPrime&{primes:}
  def n: $;
  1 -> \(
     when <?($n mod $primes($) <=0>)> do !VOID
     when <..~$primes::length> do $ + 1 -> #
     otherwise $n !
  \)!
end ifPrime

templates primes
  def N: $;
  @: [2];
  3 -> \(
    when <..$N> do $ -> ifPrime&{primes: $@primes} -> ..|@primes: $;
      $ + 1 -> #
  \) -> !VOID
  $@ !
end primes

100 -> primes -> '$;
' -> !OUT::write

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Note that we changed ifPrime to loop on indices into the primes list, that indices start from 1 and that the "~" in "<..~$primes::length>" turns it into a "strictly less than" comparison.

EDIT: Stupidly, I now lost the optimization to only divide by numbers less than or equal to the square root of the input number. I'll let you think about how to resurrect that and post the final version at the end of the article.

Since Tailspin is still in a prototype stage, it doesn't have much in the way of libraries, not even a square root function, so I had to write one, but with proper tests this time. You can probably figure out how it works now ("~/" is truncation division):

templates sqrt
  def n: $;
  @: $;
  $n ~/ $@ -> #
  when <$@..> do $@ !
  otherwise @: ($ + $@) ~/ 2;
     $n ~/ $@ -> #
end sqrt

test 'sqrt'
  assert 1 -> sqrt <=1> ''
  assert 2 -> sqrt <=1> ''
  assert 3 -> sqrt <=1> ''
  assert 4 -> sqrt <=2> ''
  assert 100 -> sqrt <=10> ''
  assert 53 -> sqrt <=7> ''
end 'sqrt'

To limit ourselves to only dividing by primes less or equal to the square root, we can rearrange the matchers a bit:

templates ifPrime@{primes:}
  def n: $;
  def root: $ -> sqrt;
  1 -> \(
     when <?($primes($) <$root~..>)> do $n !
     when <?($n mod $primes($) <=0>)> do !VOID
     otherwise $ + 1 -> #
  \)!
end ifPrime

Comments

Popular Posts