Evaluating the Tailspin language after Advent of Code

My very short (and very biased) opinion is that Tailspin is an excellent language, at least for Advent of Code.

Consider day 5 which consisted of parsing a diagram of a stack of crates and then some instructions for moving them. Generally this problem was considered a parsing nightmare, but I had virtually no trouble in the Tailspin solution. Parsing is one of Tailspin's strong points, just look at line 22-24 which is how you convert an instruction text line such as "move 5 from 1 to 3" into structured data:

composer parseInstruction
  {move: (<='move '>) <INT"crates">, from: (<=' from '>) <stack´INT>, to: (<=' to '>) <stack´INT>}
end parseInstruction

Parsing the crate diagram is only slightly more complex, I explain it in more detail in the video of me solving the problem.

Then, on line 30, the "by" operator is used to spawn several single crate moves from each instruction, which are then easily executed by appending to the "to" stack the deleted last value of the "from" stack. Finally, make a string containing the last value from each stack. The solution for part 2 is even easier, just moving the whole chunk at once:

source solutionPart1
  @: $stackState;
  $instructions... -> {from: $.from, to: $.to, by 1"crates"..$.move -> (move:1"crates")}
    -> ..|@($.to):^@($.from;last);
  '$@(first..last;last)...;'!
end solutionPart1

source solutionPart2
  @: $stackState;
  $instructions...
    -> ..|@($.to):^@($.from;last-$.move::raw+1..last)...;
  '$@(first..last;last)...;'!
end solutionPart2

But anecdotes like this are a little random, can the evaluation be more systematic?

Evaluating usability of a language

The goal of any programming language is to be usable. Since "usable" might mean slightly different things for different languages and for different contexts, it can be hard to come up with objective measures and comparisons. Instead, it can be worth looking at different aspects of usability and evaluating those aspects in the context of doing the activitity the language is meant for. One framework for doing this is the "Cognitive Dimensions of Notations", which you can learn more about in this article on the cognitive dimensions applied to user interfaces.

Caveats

Trying to be a little scientific, I have to consider threats to the validity of this "study":

• I am the only one evaluating and on top of that, I am surely very biased because I created Tailspin. On the other hand, the dimensions aren't necessarily always about "good" or "bad", it depends on the context.
• Advent of Code is very different from the usual "data shovelling" that constitutes most professional programming, which is probably why it is so appreciated as a distraction. The suitability of Tailspin for Advent of Code might not imply much about suitability for more serious use. In particular, the Advent of Code solutions comprise very little code, all in one file, as opposed to hundreds of files with dozens of callers of a function.

Quick description of Tailspin

The first thing to note about Tailspin is that it looks very different from any other programming language. Surprisingly there is no cognitive dimension relating to applicability of prior knowledge. With usability of user interfaces, there certainly is a benefit to having your interface work similarly to everyone else's interface. For programming languages there is the notion of a "strangeness budget" where the idea is that the more your language looks like C, the easier it will be accepted. Tailspin really blows the strangeness budget, but that is intentional, to not get stuck in the same old rut. There is a proposed addition to the cognitive dimensions of "Useful awkwardness", where you are forced to step back and think about the task before proceeding. So let's say that's what Tailspin has. There are also features that I've designed to be "helpfully annoying".

Another thing to note about Tailspin is that it is slow, about 1000 times slower than Java, so you can't brute-force your way out of things, you need to come up with a decent algorithm. The interpreter could be made much faster if anyone had the time and the inclination. It could perhaps be adapted to the Truffle framework on Graal VM for another performance boost. Even better might be to make a dedicated VM.

The fundamental idea in Tailspin is that program structure follows data structure. Mostly you describe the different cases for the input data and choose your actions based on that, but sometimes you want to define the output structure and create actions for determining the contents. And yet other times you need to do a bit of both and meet in the middle.

The basic construct in Tailspin is an "assembly line" where each value in a stream of values is transformed at each stage until the final result is achieved. Along the way, a value can expand into several separate values, or it can just disappear so that no further stages are applied on its account. Stages are separated by arrows "->".

Creating values is mostly familiar, "[" and "]" creates a list of values, while "{" and "}" create a structure with values named by keys, e.g. "my_key:". Numbers are mostly just numbers, although they could be identifiers, "my_id´5", or have units/dimensions "3"x"". Ranges (streams of numbers) are created by a start and end value (possibly excluded) with an optional stride, e.g. "1..5:2" to give "1 3 5".

Accessing data is also mostly familiar, with dots for accessing keys in structures and array/list indices after the variable accessor (but with parentheses, not square brackets), although more interesting projections are possible. The use of the "$" prefix to get the value of a variable is a little more strange, although not entirely uncommon. A little more strange might be the use of a bare "$", which simply means the current value to be transformed (in Kotlin it would be called "it"). The "@" sigil is even more unusual and refers to the one mutable variable you can have in a block. When you see an "!", that is where the assembly line ends and the value either gets emitted into the calling context or gets swallowed by the sink specified.

"templates" is the name for a complex transform, essentially a function with one input. The basic structure of templates is a series of matchers, each within angle brackets, "<" and ">". The first matching block is executed. The symbol "#" means that a value gets sent to be matched. A "composer" is a type of templates for parsing strings into structured data and a "processor" is essentially an object containing mutable state. For more details and tutorials, look at the main Tailspin site.

Evaluating the dimensions

Viscosity

Viscosity is about how difficult it is to make changes, particularly if a change requires a number of subsequent actions that distract you from what you were trying to achieve.

The Advent of Code challenges are perfect showcases for this dimension with part 2 usually introducing a small modification to the part 1 requirements. This has gone very smoothly and has generally been very easy to do. That may mostly be due to lucky choices informed by experience, but when it keeps happening it seems likely the language has some part in it.

Consider the day 14 solution where there is sand dripping down and coming to rest. In part 1, sand disappears at the bottom, while in part 2, sand collects on an infinitely wide floor at the bottom. The part 2 solution is basically a copy-paste of the part 1 solution, with addition of a line of space and a line of rock (on lines 35 and 36), adding matching rules that extend the grid horizontally when needed and then retries (lines 39-44), removing the rule dealing with falling into the void (line 26), and finally adding a rule to plug up the hole at the top when the time comes (line 48).

Even simpler was the day 11 solution where monkeys were playing with the items from your pack. To support part 2, I just had to add a "then:" parameter to the operations (lines 38-52) and inject the appropriate function during monkey object creation in each part.

Even when you change your mind about the fundamental solution style to use, the code still needs to follow the data (in and out). I implemented day 7 in three coding styles by just copy-pasting and adapting. The basic structure is the same.

Perhaps the most viscosity experienced concerns accessing the mutable state associated with each templates or processor. In the day 20 solution, I took the original "solutionPart1" templates and renamed it to "mix", with a "file:" parameter (the "input" on line 5 was originally named "file"). Since Tailspin mandates that you need to specify the name of the templates owning the mutable state when accessing it from a nested templates, the "@mix" references on lines 24 and 25 had to simultaneously be renamed from "@solutionPart1". This viscosity could be reduced by introducing a more relaxed naming of mutable state, but that would decrease visibility, increase hidden dependencies and perhaps increase error proneness for multi-threading (when that is enabled).

Another viscosity frequently encountered concerns when a number or string becomes autotyped. Tailspin allows you to use plain (untyped, raw) strings or numbers to a certain extent. But as soon as a string or number is assigned to a structure field, it is required to become typed, either as a tagged identifier, or, for numbers, a measure with a unit or dimension. Since Tailspin conservatively considers it an error to compare values of different types, changes have to be made to most places where the value is used. This viscosity is somewhat deliberately chosen to allow quick-and-dirty usage in the small, while generally discouraging use of plain strings and numbers, as well as forcing type conversions or union types to be explicit.

Hidden dependencies

This concerns the cost of finding things that affect each other, particularly if coordinated changes are needed. It particularly identifies one-way dependencies, e.g. you don't know the callers of a function, and local dependencies, i.e. you know the next step but may need to follow a long dependency chain.

Tailspin tries to make dependencies visible by:

• The above-mentioned requirement to name the context of the mutable state accessed from nested contexts.
• Requiring that symbols from another module must be prefixed with a module identifier when accessed.
  
• Requiring that the main program file specifies all modules used, and all modules that it allows other modules to use.

Otherwise Tailspin is probably just as prone to hidden dependencies as other languages, although note that the Cognitive Dimensions tutorial mentions that the remedies for hidden dependencies can sometimes be worse than the dependencies themselves.

Being a fairly dynamic language, I suppose the input and output types to a function should be considered a hidden dependency. In the future, I intend to add contracts to the language. It might be possible to create type inference mechanisms as well.

Dynamic types, or, rather, undeclared types, in general could perhaps be considered to be hidden dependencies. If you have to declare types, it increases the viscosity when types are changed, encourages premature commitment and counteracts provisionality, to an extent depending on how complex type declarations are. Tailspin attempts to find a balance by allowing dynamic types but requiring that field names consistently apply to the same type. This can have a viscosity impact as discussed above, but allows more provisionality.

Premature Commitment and Enforced Lookahead

This concerns constraints on the order of doing things that force the user to make a decision before the proper information is available.

I can't at the moment think of anything that forces a premature commitment or undue lookahead.

Abstractions, abstraction hunger and the abstraction barrier

In the cognitive dimensions framework, the definition of an abstraction is a class of entities, or a grouping of elements to be treated as one entity, either to lower the viscosity or to make the notation more like the user’s conceptual structure. (Side note: The cognitive dimensions framework clearly defines "abstraction" in this context to mean simply a grouping of components. Otherwise, this article tries to clarify the confusion surrounding abstraction.)

The abstraction barrier is determined by the minimum number of new abstractions that must be mastered before using the system; if the system allows one user to add new abstractions that must then be understood by subsequent users, that will further raise the abstraction barrier.

Abstraction-hungry systems can only be used by deploying user-defined abstractions. Abstraction-tolerant systems permit but do not require user-defined abstractions. Abstraction-hating systems do not allow users to define new abstractions (and typically contain few built-in abstractions).

Tailspin is somewhat abstraction-hungry. You have to create a templates (function)  instance for any of the following reasons:

• Conditional evaluation. A series of matchers can only exist as part of a templates instance.
• Mutable state can only exist within a templates instance during an invocation, or, more persistently, as part of a processor (object) instance.
• Recursion (obviously) or looping, which is an inner recursion on the matchers. Simple iteration can be accomplished by streaming values from a list or a range, although arguably these are other abstractions.
  
• Performing more than one statement/pipeline from the same value. This can alternatively be achieved by lists or structures, with a pipeline for each element or field.
• Combine a sequence of transforms into one unit. This could make a difference if effects (mutable state or input/output) are involved, since Tailspin guarantees every value passes through the current transform before any value passes through the next.

Note that templates can be anonymous and defined inline in the pipeline.

The abstractions that need to be learned before efficiently using the language are statements/pipelines, ranges, lists, structures and templates. Useful additional abstractions are processors (objects) and relations (data tables for relational algebra). It is unclear whether a composer counts as an abstraction, but it does contain a number of matchers to be treated as a unit and it is the only reasonable way to deconstruct text data.

Secondary notation

Secondary notation is about providing additional information by other means than the official syntax needed to make things work.

Tailspin allows addition of comments by a "//" that initiates a comment until the end of the line.

Tailspin does not depend upon whitespace so that can be used to convey additional information by line breaks and indentation.

Tests could possibly also be considered a secondary notation that conveys information about the program. Tests can in Tailspin be written within test blocks in the same file as the program.

On the drawing board for Tailspin is the ability to annotate data with metadata, although it's still being evaluated. Beyond code being allowed to ignore metadata, what is really the difference between data and metadata? If it does get ignored and lost in processing, what is its use? How should it carry to derived or transformed data?

Visibility & juxtaposibility

Visibility concerns the ability to view and find components easily, while juxtaposability concerns the ability to place components side-by-side to compare them.

Juxtaposibility is not provided within the language and has to be achieved by, for example, split editor windows.

In Tailspin the syntax is designed to show the start and end of components clearly, intended to help visibility:

•  Templates definitions start with "templates", "source" or "sink" followed by a name, and end with "end" also followed by the name. Repeating the name increases visibility at the cost of diffuseness. Similarly, processor and composer definitions end with "end" and the name repeated.
• Test blocks start with "test" followed by a descriptive string and end with "end" followed by the same description.
• Inline templates start with "\(" and end with "\)". They can be anonymous or have a name after the "\", repeated both at start and end.
  
• Value definitions, state assignments and string interpolations end with ";". Definitions start with "def", state assignments start with "@" and string interpolations start with "$".
  
• A pipeline usually ends with a "!", either alone as "emit into calling context", or before an identifier that "swallows" the current value. A pipeline could end with a "#", which is not an end but initiates conditional processing over the matchers. Pipelines used to create values in lists, structures and assignments will end in the way corresponding to that component.
• Lists start with "[" and end with "]", list items end with "," except at the end of the list. Structures start with "{" and end with "}", fields start with an identifier followed by a ":" and a value production ending in a ",", except at the end of the structure. Relations start with "{|" and end with "|}", with comma-separated structures or value productions.
  
• Matcher expressions start with "<" and end with ">". Additional conditions start with "?(" and end with ")".

As previously mentioned, accessing mutable state outside the current templates needs to be done with the name of the outer templates where the state is declared.

Using a symbol from a module is required to be prefixed with an identifier associated with the module.

Closeness of mapping

This dimension concerns how closely the notation represents the original problem.

No matter how declarative a language is, there always seem to crop up situations where the mechanics of executing the program overshadow the description of the problem. In some or most languages it is possible to create abstractions that fit more closely to the problem description, even to the point of creating a domain specific language, but abstractions can come with their own problems, sometimes creating barriers to learning and maintainability.

To examine this dimension, I will present a few examples of Tailspin code, describe it in prose and see how that corresponds to the problem description.

We have already seen at the beginning of this article that composer parsing of strings is very declarative and that the day 5 code corresponded well to the problem description.

For another example, consider the following code from lines 11-26 the day 13 solution:

operator (left inOrder right)
  0 -> #
  when <?($left <..>)?($right <´´ ..~$left>)> do 1!
  when <?($left <..>)?($right <´´ $left~..>)> do -1!
  when <?($left <..>)?($right <´´ =$left>)> do 0!
  when <?($left <..>)?($right <[]>)> do $ -> ([$left] inOrder $right)!
  when <?($left <[]>)?($right <..>)> do $ -> ($left inOrder [$right])!
  when <?($left <[](1..)>)?($right <[](0)>)> do 1!
  when <?($left <[](0)>)?($right <[](1..)>)> do -1!
  when <?($left <[](0)>)?($right <[](0)>)> do 0!
  when <?($left <[]>)?($right <[]>)> do
    ($left(first) inOrder $right(first)) -> \(
      when <´´ =-1|=1> do $!
      otherwise ($left(first~..last) inOrder $right(first~..last))!
    \)!
end inOrder

The operator "inOrder" with a left and a right argument is evaluated as follows (of course, you need to learn the vocabulary of the language):

1.  When the left value is a number and the right value, which can be anything, is a number less than the left, emit 1
2. Otherwise when the left value is a number and the right value, which can be anything, is a number greater than the left, emit -1
3. Otherwise when the left value is a number and the right value, which can be anything, is a number equal to the left, emit 0
4. If the left value is a number and the right value is a list, wrap the left value in a list and apply the operator to the new left and the right
5. If instead it is the right value that is the number and the left value the list, wrap the right value in a list and apply the operator again.
6. If both values are lists, and only the right is empty, emit a 1
7. If instead only the left list is empty, emit -1
8. If both lists are empty, emit 0
9. If both values are (implicitly non-empty) lists, apply the operator to the first elements of both lists, and emit a 1 or -1 result, else apply the operator to the remainder of both lists.

Compare with the day 13 problem description:

When comparing two values, the first value is called left and the second value is called right. Then:

• If both values are integers, the lower integer should come first. If the left integer is lower than the right integer, the inputs are in the right order. If the left integer is higher than the right integer, the inputs are not in the right order. Otherwise, the inputs are the same integer; continue checking the next part of the input.
• If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.
• If exactly one value is an integer, convert the integer to a list which contains that integer as its only value, then retry the comparison. For example, if comparing [0,0,0] and 2, convert the right value to [2] (a list containing 2); the result is then found by instead comparing [0,0,0] and [2].

This is very similar, although you still need to infer the encoding of "-1" meaning "the right order", "1" meaning "not the right order" and "0" meaning "no decision is made".

Matcher arrays generally tend to correspond quite closely to the requirements, so is a good feature to have. Let's look at yet another example from the Tailspin solution to day 3:

source solutionPart1
  ($table({elf:,item:,compartment:})
      divide&{over: $table({elf:, item:})}
      $table({compartment:, elf:}))...
    -> $.item -> toPrio -> ..=Sum&{of::()}!
end solutionPart1

source solutionPart2
  ($table({elf:,item:,group:})
      divide&{over: $table({group:, item:})}
      $table({group:, elf:}))...
    -> $.item -> toPrio -> ..=Sum&{of::()}!
end solutionPart2

Explanation (again, knowing the language):

For part 1, consider the relation between elves, items and compartments, and return the elf-item combinations that exist for all compartments related to the elf. Take the item of each value of the result, transform by the "toPrio" templates and sum those values.

For part 2, consider the relation between elves, items and groups, and return the group-item combinations that exist for all elves in the group. Take the item of each value of the result, transform by the "toPrio" templates and sum those values.

Here's how the problem was stated for part 1:

Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?

And the description for part 2:

...within each group of three Elves, the badge is the only item type carried by all three Elves... Find the item type that corresponds to the badges of each three-Elf group. What is the sum of the priorities of those item types?

Relational algebra is also a handy feature which often corresponds well to the requirements. Of course, I am cherry picking a bit. It might not be entirely clear that the following line from the tailspin solution to day 17:

$(1)::length + 3 -> \(<$@Funnel.top::raw..> $ - $@Funnel.top::raw + 1 !\)
  -> ..|@Funnel: { pipe: [x (1..$ -> [x 80 x]) ($@Funnel.pipe) x],
        top: $ + $@Funnel.top::raw};

which reads: Take the length of the first element of the input array, add 3. If it is greater than the "top" field of the "Funnel" state, take the excess plus one, then append to the "Funnel" state a "pipe" field that contains a byte array which prepends the calculated value amount of "80" bytes to the previous "pipe" value and increments the "top" field by the calculated value.

corresponds to the description:

Each rock appears so that ... its bottom edge is three units above the highest rock in the room (or the floor, if there isn't one).

Consistency

In a consistent notation, similar semantics are expressed in similar syntactic forms.

Tailspin is designed with consistency in mind:

• All kinds of abstractions (as defined for cognitive notations framework) are defined starting with the abstraction type followed by the name and ended with the word "end".

• Angle brackets "<>" signify a matcher, checking if a value matches the expression, even if it is the whole value in a regular matcher and the beginning of the remaining string in a composer.

• Square brackets "[]" signify creation of a list/array. If it has an x, "[x" and "x]", it is a byte array. A possible inconsistency is the use of "\[i]( \)" which is an element-wise transform of an array where the square brackets surround a holder variable for the index of the element. It would perhaps be more consistent as "\[i ( )\]"?

• Curly braces signify a set, "{" and "}" for a set of keys with attached values (a.k.a. a structure), "{|" and "|}" for a set of structures with the same keys (a.k.a. a relation).

• ".." means numeric values above the left bound and below the right bound, or just any numeric value if no bounds are given. This applies both when generating ranges and when testing conditions. 

Parentheses "()" are used for a number of purposes. Mainly it is used for grouping: in arithmetic, in part sequences of a byte array, when creating a "free" key-value pair and in the form "\(" and "\)" as an inline templates (grouping statements and matchers). The other use of parentheses is to enclose an indexing operation (or more generally, a projection) into a compound data structure. A third use of parentheses is to enclose an additional condition in a matcher, as "?(   )". It is not clear if this inconsistency is confusing or not.

Another inconsistency is perhaps that both "$struct.field" and "$struct(field:)" yield the same value. On the other hand, "$struct({field:})" gives a structure containing the field, which is consistent with "$arr([5])" giving an array consisting of the fifth element while "$arr(5)" gives just the fifth element. Could it be confusing that "$arr(5..5)" gives an empty array if there is no fifth element while the other forms would error? And there is currently no form for optional field access.

Diffuseness

The verbosity of the language.

Although the effect of over-verbosity is often slight, it can take up more slots in the brain's working memory. On the other hand, terseness can be a problem because it can increase error-proneness and reduce visibility.

Comparing with Advent of Code solutions written in other languages, the Tailspin solutions tend to be fairly concise even when written to be clear (close mapping).

Tailspin can sometimes perhaps be too terse. Matchers can be written just as they are, but there is an option to surround a matcher with the words "when" and "do", which seems to increase readability.

Another example of the syntax being too terse is possibly "<5..>" vs "<..5>" meaning greater than or equal to 5 and less than or equal to 5 respectively. A mistake choosing the wrong one can be hard to spot.

Error-proneness

This concerns whether the notation itself invites certain types of systematic mistakes.

I can't think of any particular errors that the language would invite one to make. Tailspin has a philosophy of erroring on anything that can be discovered that might be a programmer error.

Hard mental operations

Does the language sometimes put a high demand on cognitive resources?

I don't think Tailspin requires more hard mental operations than other languages. Perhaps rather the opposite, since pipelines focus on one step at a time and matchers encourage specifying one case at a time.

Progressive evaluation

This dimension explores whether it is possible to evaluate incomplete work.

I have written an article that demonstrates progressive evaluation in Tailspin. It is very easy and a favourite technique of mine.

Another little trick is to insert "\($ -> !OUT::write $! \)" as an extra stage in a pipeline to see what the current value is at that point.

Tests can also be used to evaluate parts of programs.

Provisionality

How committed are you to things already written?

In Tailspin it is quite easy to put in provisional values along the way and perfect the details later. For example, if you know that the current value is to be transformed to a different structure before being processed in the next stage, but you don't quite know yet how or what to do in the first transformation, you can just inject a constant, e.g. "$ -> {foo: 1, bar: 'qux'} -> my_current_focus" and change it later.

Role-expressiveness

Can the purpose of a component (or an action or a symbol) be readily inferred?

Most of the things mentioned under "visibility" perhaps belong here instead. Also the things mentioned under "consistency".

I'd like to highlight the use of sigils in Tailspin. A "$" always means a value is being brought into play, while a "!" means a value is being sent out of scope and lack of a sigil means a transform is applied. Also, an "@" always means mutable state, while the lack of it means immutable values, except in the case of processors. Communication with processors is done through messages which are "sent" by "::".

Final thoughts

It would obviously be more useful if other people did this evaluation, but even doing it on my own forced me to look at Tailspin from a few different angles, which I think is ultimately worthwhile. It will now also be easier to reflect back along these dimensions as I use or develop Tailspin going forward.