A little Tailspin
I was delighted to come across Uncle Bob's blogpost "A little more Clojure" the other day, where he concludes:
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:
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:
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:
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:
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:
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:
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:
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?
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 "\".
Finally, changing back to running the "primes" program:
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?
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?
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:
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):
To limit ourselves to only dividing by primes less or equal to the square root, we can rearrange the matchers a bit:
Now I want you to think carefully about how we solved this problem. NoThe 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?ifstatements. Nowhileloops. 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.
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