tag:blogger.com,1999:blog-76770218873633641822024-02-20T00:34:28.544-08:00Tobe expressedtobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-7677021887363364182.post-34722726043384559612024-01-20T12:34:00.000-08:002024-01-20T12:34:13.698-08:00Usability in programming language concept implementations<p>Why does it feel easier and more joyful to write in one programming language than another? Most of the work is coming up with the algorithm, without considering language. Then translating that to a programming language is not usually the biggest problem (unless doing it in J 😉). Puzzling out how to make it work in PostScript (or J) can even be a reward in itself. But then there are those times when you just want to get an answer.<br /></p><h2 style="text-align: left;">Prequel <br /></h2><p>As usual I have been doing <a href="https://adventofcode.com/2023">adventofcode</a> both because it is fun and it is an opportunity to use my <a href="https://github.com/tobega/tailspin-v0">Tailspin programming language</a>. I also take the opportunity to try out a new language (or several) and as the mood takes me I might use an old favourite.</p><p>In <a href="https://github.com/tobega/aoc2017">2017</a> I wanted to improve my javascript and also ended up learning SequenceL, in <a href="https://github.com/tobega/aoc2018">2018</a> I wanted to see how SQL could work for programming and also started designing Tailspin as "how would I want to write this code", in <a href="https://github.com/tobega/aoc2019">2019</a> I had just developed Tailspin so that was it, in <a href="https://github.com/tobega/aoc2020">2020</a> I wanted to learn Julia, in <a href="https://github.com/tobega/aoc2021">2021</a> F#, in <a href="https://github.com/tobega/aoc2022">2022</a> Smalltalk (although admittedly I should probably do more with that. I really want to give Newspeak a try). Now and then I give Dart or Java a whirl. I've tried more languages, but you really need to do more than a couple of programs to get a good feel for it.</p><p><a href="https://github.com/tobega/aoc2023">This year</a> I wanted to see how Pyret worked, as it is designed to be a good beginner language. Some things I particularly liked was the way currying is done and the example tests for functions. Also the table data structure was very nice, even if I only used it once. Pyret is quite pleasant to work with, so this is no criticism of Pyret, but as I went along it just felt a little easier and more pleasant to reach for Tailspin than Pyret, particularly on the days I felt I was a little stressed or short of time.</p><p>I realized that the same thing had happened previous years. One thing that struck me is that being able to emit an arbitrary amount of result values from a transform/function is really a superpower. I have previously written about the <a href="https://tobega.blogspot.com/2021/05/the-power-of-nothing.html">power of emitting nothing at all</a>, but emitting many values is just as liberating. While that is a nice insight in itself, is there a more general way to analyze this?</p><h2 style="text-align: left;">What is "better"?</h2><p style="text-align: left;">Obviously what is "better" can depend on your purpose, so I should start by defining what I think is better for this analysis:</p><ol style="text-align: left;"><li style="text-align: left;">Clearly (and, secondarily, concisely) showing what is being done (rather than how)<br /></li><li style="text-align: left;">Allowing easy restructuring and recombination to fit a slightly altered purpose</li><li style="text-align: left;">Helping to avoid errors (or at least making sources of errors easy to find)</li><li style="text-align: left;">Making it easier to follow best practice and harder to be "clever" </li></ol>These are the principles I applied when designing Tailspin, so it should come out looking good in this analysis.<br /> <h2 style="text-align: left;">Looking at underlying concepts</h2><p style="text-align: left;">Last year, I evaluated <a href="https://tobega.blogspot.com/2022/12/evaluating-tailspin-language-after.html">Tailspin on the Cognitive dimensions of notation</a> and one way of trying to find usability differences would be to evaluate some other languages the same way. I think that would be useful, but I don't really want to go into so much depth on each language. So I had the idea of looking at <a href="https://essenceofsoftware.com/tutorials/concept-basics/sw-as-concepts/">concepts, Daniel Jackson style</a>.</p><p style="text-align: left;">I think all programming languages mostly have to implement the same concepts, but the way they are implemented and exposed to the programmer may result in big differences in usability (and certainly I could keep the cognitive dimensions in mind here). Also, muddling and overloading of concepts, forced synchronizations between concepts, or a proneness to erroneous expression, could explain arising resistances.</p><p style="text-align: left;">I propose the following concepts:</p><ul style="text-align: left;"><li style="text-align: left;">Repetition - <i>Purpose</i>: Allows repeating similar operations with slight variation. <i>Operational Principle</i>: If you provide the parts that vary, the algorithm is repeated with those variations.</li><li style="text-align: left;">Aggregation - <i>Purpose</i>: Collects separate related units into one unit. <i>Operational Principle</i>: If you provide the parts and specify how they relate to each other, an aggregate unit is created.</li><li style="text-align: left;">Projection - <i>Purpose</i>: Creates a view of parts of an aggregate. <i>Operational Principle</i>: If you specify the location(s) within the aggregate you want to access, those parts are extracted into a smaller aggregate (or single value)<br /></li><li style="text-align: left;">Selection - <i>Purpose</i>: Allows a choice of which units to process and which to ignore. <i>Operational Principle</i>: If you specify the selection criteria, the matching units will be processed.<br /></li><li style="text-align: left;">Verification - <i>Purpose</i>: Allows checking correctness criteria of the program. <i>Operational Principle</i>: If you specify a criterion and run the verification procedure (which may be built in), a warning/failure is issued if the program does not fulfil the criterion.<br /></li><li style="text-align: left;">Documentation - <i>Purpose</i>: Allows communicating aspects of the design and purpose to a future reader of the program. <i>Operational Principle</i>: If you specify the relevant information, a future reader will receive it when needed.<br /></li></ul><h2 style="text-align: left;">Repetition</h2><p>I suppose the most primitive expression of this concept would be the <code style="color: #cc0000;">GOTO</code>. The biggest problem with the <code style="color: #cc0000;">GOTO</code> is that it becomes very easy to create complicated execution trees, as we know Dijkstra pointed out. Enforcing and clearly showing more structured repetition like loops and procedure calls is advantageous. It is possible that there exists some algorithm that is most clearly represented by <code style="color: #cc0000;">GOTO</code>, but I don't remember any convincing example.<br /></p><h3 style="text-align: left;">Loops</h3><p style="text-align: left;">The classic here is the integer count from a start to an end <code style="color: #cc0000;">FOR i=1 TO 10</code>. This is often used to do something a specific number of times, but despite the beautiful clarity of something like <code style="color: #cc0000;">10 times: [...]</code>, I think that it perhaps doesn't improve enough over the <code style="color: #cc0000;">FOR</code> to be worth it and there is still a need to start at an arbitrary point and perhaps use a different increment. On the other hand, the C-style loop with arbitrary initialization, test and "increment" clauses is far too flexible to be easily understood at a glance, at least in the more exotic cases.<br /></p><p style="text-align: left;">Mostly the for loop is used to get an index into an array to process each element. The <code style="color: #cc0000;">for each</code> construct, e.g. <code style="color: #cc0000;">for value in values</code>, is a clear improvement both readability-wise and for avoiding indexing errors. It also allows processing each element of an unordered collection. When we combine the <code style="color: #cc0000;">for each</code> with a way to construct a collection of index values, e.g. <code style="color: #cc0000;">for i in range(1,10)</code>, we can do away with the old counting loop. With good constructors of index iterators we can even get back some of the flexibility of the C version in a more readable way, e.g. <code style="color: #cc0000;">for i in powersOfTwo()</code>. A possible downside of the <code style="color: #cc0000;">for each</code> is that it often relies on mutation (see below) to construct the result.<br /></p>Functional languages popularized the higher-order <code style="color: #cc0000;">map</code>, <code style="color: #cc0000;">filter</code> and <code style="color: #cc0000;">flatMap</code> functions to abstract away the iteration itself, applying the repetition concept again to re-use the iteration with a modified operation to be done at each step. Unfortunately this means that the simple iteration code is redefined with innumerable variations, each with a different name and parameter list in order to handle different types of operations. Consider the following tortuous code to map to an optional value: <code style="color: #cc0000;">values |> map maybeInt |> filter somes |> map unwrapSome</code>. Since it is fairly common, F# defines yet another variation to handle it, <code style="color: #cc0000;">values |> choose maybeInt</code>. The small differences in exactly which type of processing is being done hardly seems relevant for the cognitive load investment needed to keep track of all the variations and the <code style="color: #cc0000;">for each</code> covers all of them much more clearly in a single construct.<p style="text-align: left;">Tailspin simplifies the <code style="color: #cc0000;">for each</code> further by simply streaming values into a pipeline, <code style="color: #cc0000;">values...</code>, or a counted range <code style="color: #cc0000;">1..10</code>. This isn't really recognizable as a loop any longer even though it works exactly the same. The operations or transforms to be performed are placed along the pipeline without higher-order function wrappers. To enable filtering, transforms can withhold emitting a value and to enable flatMap, transforms can emit more than one value. This ends up being extremely composable and refactorable.<br /></p><p style="text-align: left;">It might be worth considering a special construct for getting a value and its index, like Go's <code style="color: #cc0000;">for index, element := range someSlice</code>, even though the "range" keyword there doesn't sound quite right to me. Tailspin has such a construct as well, adding an "array deconstructor" to an inline transform, <code style="color: #cc0000;">someSlice -> \[index](...\)</code>. This is effective but a bit of a syntax oddity. Perhaps a better approach would be to just have an iterator constructor that combines an index with the value and use the standard "for each"<br /></p><p style="text-align: left;">The <code style="color: #cc0000;">while</code> loop is a really wild beast and I'll get back to that later.</p><h3 style="text-align: left;">Recursion</h3><p style="text-align: left;">Any function or procedure call is also an application of the repetition concept. Recursion calls the same function repeatedly with slight modification, which ends up being equivalent to an iterative loop. The advantage of recursion is that it forces the mutation of the iteration index, the current value and the mutation of the result to happen at the same logical point in the code, which simplies the logical structure.</p><p style="text-align: left;">A typical recursion implementation will have an entry function with a recursive helper function that must contain a test for whether to recurse more or return a result. The helper function is most clearly implemented as a <code style="color: #cc0000;">match</code> (or <code style="color: #cc0000;">switch</code>) statement listing the different possible conditions and what should be done for each. It may be worth noting that in the <a href="https://en.wikipedia.org/wiki/Guarded_Command_Language">Guarded Command Language (GCL)</a>, which is intended to be easier to prove correctness for, a loop contains exactly a <code style="color: #cc0000;">switch/match</code> which is essentially randomly ordered.<br /></p><p style="text-align: left;">In Tailspin, each templates (function) is by default expected to be an array of <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#matchers">matchers</a> (guards), no match keyword, it just is. A value can be sent back to be matched by a <code style="color: #cc0000;">#</code>. An optional prelude can set things up before recursing internally on the matchers. <a href="https://github.com/tobega/tailspin-v0/blob/master/samples/FlattenList.tt">Example of how to flatten a list</a>. While this doesn't enforce good practice, it guides it and makes it easier to follow.</p><h3 style="text-align: left;">Mutation</h3><p style="text-align: left;">Mutating a variable is equivalent to calling a function at that point with a parameter holding the new value. Erlang does mutation of state that way. So mutation is also an implementation of repetition. Like the <code style="color: #cc0000;">GOTO</code>, rampant mutation can make it very difficult to unravel the execution tree.</p><p style="text-align: left;">It is in the light of mutation that we can examine the <code style="color: #cc0000;">while</code> loop because it is completely dependent on mutation to change the condition needed to break the loop. With that in mind, it should be clear that recursion is much preferable to <code style="color: #cc0000;">while</code> loops.</p><p style="text-align: left;">Despite the possibility of complications, mutation makes the expression of some algorithms, like folds or aggregations, much simpler. Mutation is also quite easy to understand in a local context. Even mutation affecting code in another part of the program can be extremely useful to relay information, but needs to be packaged and shared in a way to make the intent clear, <code style="color: #cc0000;">channel</code> in Go being a good example. But that starts digressing into other concepts that I haven't analyzed.</p><p style="text-align: left;">Tailspin allows one mutable variable inside a function, but it can be an aggregate (see the Aggregation concept below). Since functions can be defined inside functions, this can get complex but it can't escape its confines, unless you work hard at it by storing a closure in an object.</p><p style="text-align: left;">Tailspin also provides object constructs (called processors just to try and free the mind). These allow holding of mutable state between accesses.</p><h3 style="text-align: left;">Vector operations and other repetitions<br /></h3><p style="text-align: left;">Fortran90 introduced vector operations, where whole arrays could be used in arithmetic for elementwise evaluation. Hugely convenient, but also performant if you had a machine with pipelined circuits.</p><p style="text-align: left;">In Julia, a <code style="color: #cc0000;">.</code> can be used to turn any function into a <a href="https://docs.julialang.org/en/v1/manual/functions/#man-vectorized">vector function</a>.</p><p style="text-align: left;">The <a href="https://en.wikipedia.org/wiki/SequenceL#Normalize%E2%80%93transpose">Normalize-transpose mechanism</a> of SequenceL automatically vectorizes any function call.</p><p style="text-align: left;">I haven't felt comfortable adding something like this to Tailspin yet, but there is one Projection that has a somewhat magical repetition (perhaps too magical). A call like <code style="color: #cc0000;">$({z: §.x + §.y})</code> will repeat through any level of array nesting and transform each record at the bottom as specified.</p><p style="text-align: left;">Tailspin also has a built-in construct for producing cartesian products: <code style="color: #cc0000;">[by 1..3, by 1..3]</code> will produce all 9 pairs in a stream.<br /></p><h3 style="text-align: left;">Inline-defined functions (lambdas)</h3><p style="text-align: left;">Theoretically there is no difference between a function defined inline or a function defined separately, but there is a curious effect I have observed. This is not really about the repetition concept but rather asynchronous programming, which I am not currently analyzing.</p><p style="text-align: left;">Using small inline-defined functions to modify behaviour in immediately-executing code like <code style="color: #cc0000;">map</code> and <code style="color: #cc0000;">filter</code> is handy and doesn't cause any problems. But when an inline-defined function is passed as a callback, it can cause temporal confusion.</p><p style="text-align: left;">The observation came from writing Java code with callbacks defined as separate task objects, which was a great way to write asynchronous code. The object provided a clear bound and signalled that the execution context was different. When Java got lambdas, some callbacks got defined as lambdas and a few curious and difficult-to-analyze bugs started appearing. Those bugs all were because the brain too easily assumed that the code it was reading inline also got executed in the same time and context.</p><p style="text-align: left;">I'm a little on the fence here, but Tailspin currently does not allow inline-defined functions in a parameter, only in pipeline stages. There is less need because Tailspin doesn't need <code style="color: #cc0000;">map</code>, <code style="color: #cc0000;">filter</code> and friends. A function being passed as a parameter is obviously a crucial component of your algorithm, maybe it is worth giving it a name? In Tailspin, parameters are also named, so this could result in a function call like <code style="color: #cc0000;">sort&{by: nameAscending}</code></p><h2 style="text-align: left;">Aggregation</h2><p style="text-align: left;">The simplest form of aggregation is probably addition. If I were splitting hairs, I would then also argue that subtraction is a form of projection, which is the inverse of aggregation. Anyway, I think we can agree that arithmetic is most clearly represented in the normal infix way as <code style="color: #cc0000;">5 * (3 + 1)</code> rather than something like <code style="color: #cc0000;">5 3 1 add mul</code>. This, I think, sets the tone for this section.</p><h3 style="text-align: left;">Lists/arrays<br /></h3><p style="text-align: left;">The most fundamental and flexible way of providing aggregation is undoubtedly <code style="color: #cc0000;">cons</code>. This might be a little too flexible, though, and definitely a bit onerous when constructing longer list values. On the other side of the room, old languages closer to the metal require that you allocate arrays to a fixed length before you start filling them with data. If you ever worked in a language where you had to allocate space for strings you know the pain.</p><p style="text-align: left;">On a point of order, I suppose there is a distinction between lists, being ordered, iterable and variable length, and arrays, being indexable and usually fixed in size. I want all those properties at once and tend to be a little loose in which term I use. In Java, I don't know if there exist any cases where you would use a <code style="color: #cc0000;">LinkedList</code> instead of an <code style="color: #cc0000;">ArrayList</code> (although I could find uses for a <code style="color: #cc0000;">Node</code> class with pointers to next).</p><p style="text-align: left;">Modern languages provide a more direct and declarative array literal syntax, like <code style="color: #cc0000;">['apple', 'pear', 'orange']</code>. For calculated values, list comprehensions are the way to go, e.g. <code style="color: #cc0000;">[[i + j for j in 1:3] for i in 1:3]</code>, re-using the <code style="color: #cc0000;">for each</code> construct. The only thing to object to is the reversal of the repeated clause and the <code style="color: #cc0000;">for</code>.</p><p style="text-align: left;">Tailspin provides the literal list constructor, but since the square brackets just capture a stream of values, the list comprehensions read just like normal code, <code style="color: #cc0000;">[1..3 -> \(def i: $; [1..3 -> $i + $]! \)]</code>, where an inline-defined function is used to capture the <code style="color: #cc0000;">i</code> for use in the nested pipeline. All types of expressions can just be combined inside the list literal, e.g. <code style="color: #cc0000;">[5, 9, 1..3, 17, 4..6 -> 3 * $, 79]</code>. This composability means there is no need for a concatenation operator, just do <code style="color: #cc0000;">[a1..., a2...]</code><br /></p><h3 style="text-align: left;">Text (strings)<br /></h3><p style="text-align: left;">In this multi-cultural world which is also full of emojis, text can no longer be considered to be an array of anything, except perhaps glyphs. Since glyphs can be made up of several concatenated unicode codepoints, a glyph array is probably not suitable as a basic representation.<br /></p><p style="text-align: left;">Computer programs don't need to be interpreted by lines like some remnant of punch cards, so text should be multiline.</p><p style="text-align: left;">String templates are a good idea, but positional parameters to them are not, because word order often needs to change when translated to another language. String interpolation is a good idea, and perhaps an interpolated template should be easy to capture as a function. With string interpolation, no concatenation operator is needed. It should probably be possible to enter unicode codepoints numerically and be able to transform to and from byte or integer encodings.<br /></p><p style="text-align: left;">Tailspin treats text strings as immutable entities produced by string literals with interpolated expressions. As a result of this ananlysis, Tailspin will be getting first-class string templates, perhaps <code style="color: #cc0000;">:'Hello §.name;'</code> would fit syntax-wise.<br /></p><h3 style="text-align: left;">Structures/records (and function parameters)<br /></h3><p style="text-align: left;">While lists can be used generally to associate different pieces of data, it is often not a great idea, <a href="https://www.codeproject.com/Articles/1186940/Lisps-Mysterious-Tuple-Problem">even if you call it a tuple</a>. Having a type name constructor and typed values is a little better, but not much. What is a <code style="color: #cc0000;">Rectangle(1, 3, 5, 9)</code>? Is it a <code style="color: #cc0000;">Rectangle(Point(1, 3), Point(5, 9))</code> or a <code style="color: #cc0000;">Rectangle(Point(1, 3), Dimension(5, 9))</code>? Even then, the structure of <code style="color: #cc0000;">Point</code> isn't entirely clear, nor how the <code style="color: #cc0000;">Point</code> relates to the <code style="color: #cc0000;">Rectangle</code>.<br /></p><p style="text-align: left;">Again, a more literal declarative approach is superior. A literal <code style="color: #cc0000;">{left: 1, top: 3, width:5, height:9}</code> or named function parameters, <code style="color: #cc0000;">Rectangle(left=1, top=3, width=5, height=9)</code> may feel like too much to type sometimes, but it wins in the long run. This gets even better when considering the Communication concept below, but even taking the cognitive load off constructing the aggregation should be beneficial. Anyone who has switched between Java and C# has run into the following: What does <code style="color: #cc0000;">"abcdefg".[sS]ubstring(2, 4)</code> give? In Java, it is <code style="color: #cc0000;">"cd"</code>, in C# it is <code style="color: #cc0000;">"cdef"</code>.<br /></p><p style="text-align: left;">Needless to say, Tailspin supports the literal structure syntax and requires named parameters (in fact, a set of parameters is represented as a literal structure).</p><h3 style="text-align: left;">Other datastructures</h3><p style="text-align: left;">Whether as built-ins or libraries, it is useful to have Maps (Dictionaries) and Sets available. Some languages (I know of Pyret and Ballerina) also have a Table construct that is a bag or set of records, with record fields treated as columns. Tables allow for interesting projections and relational operators like <code style="color: #cc0000;">join</code>.</p><p style="text-align: left;">Tailspin does not have Maps or Sets, but it has Relations, which are sets of records with relational algebra operators, like Tables. They can be used as Maps or Sets, but are more flexible because every column could be considered a key (although Tailspin's relations currently aren't very performantly implemented and replacing a value entails removing and adding)</p><h2 style="text-align: left;">Projection</h2><p style="text-align: left;">Most fundamentally, a Projection is the inverse of Aggregation, so for <code style="color: #cc0000;">cons</code> that means <code style="color: #cc0000;">car</code> and <code style="color: #cc0000;">cdr</code> (or <code style="color: #cc0000;">head</code> and <code style="color: #cc0000;">tail</code>), but projections can be so much more. Array slices were introduced already in Fortran90 and are now happily present in more and more languages. One might argue that slices are an Aggregation of a Repetition of a simple Projection, but I feel that a Projection could be anything showing a smaller or transformed view of the aggregate object. Keeping the substructure in the projection rather than just streaming out the values is probably a good idea because it can be difficult to reconstruct, while it is still easy to add a separate streaming step when needed.<br /></p><p style="text-align: left;">Fields of a record are usually accessed by name, often with the dot-syntax <code style="color: #cc0000;">record.field</code>. Record deconstruction by patterns whereby record fields can be projected onto local variables is very handy and now even <a href="https://gavinray97.github.io/blog/what-good-are-record-patterns">available in Java</a>.</p><p style="text-align: left;"><a href="https://learn.microsoft.com/en-us/dotnet/csharp/linq/">LINQ</a> is a great way to create projections, by selecting subsets of records, filtering, aggregating, grouping and ordering. Languages with Tables provide similar operations on those.<br /></p><p style="text-align: left;">On a side-note, projection specifications can be first-class values: Haskell has lenses, which essentially are values that specify which part of an aggregation to return (i.e. which projection to apply).</p><p style="text-align: left;">Tailspin has many ways to project data:</p><ul style="text-align: left;"><li style="text-align: left;">arrays can be sliced by ranges but also be selected by index arrays, so <code style="color: #cc0000;">['e', 'h', 'l', 'o'] -> $([2,1,3,3,4])</code> gives <code style="color: #cc0000;">['h','e','l','l','o']</code>.</li><li style="text-align: left;">Individual fields can be selected by dot-syntax, <code style="color: #cc0000;">$.field</code>, or by key-projection, <code style="color: #cc0000;">$(field:)</code>.</li><li style="text-align: left;">Records can be transformed, e.g. <code style="color: #cc0000;">$.from({x:,y:,z: §.z - $drop})</code>, which copies the <code style="color: #cc0000;">x</code> and <code style="color: #cc0000;">y</code> fields of the <code style="color: #cc0000;">from</code> record and subtracts <code style="color: #cc0000;">drop</code> from the <code style="color: #cc0000;">z</code> field.</li><li style="text-align: left;">Array slicing and key-projection can be performed in several "dimensions", digging ever deeper, e.g. <code style="color: #cc0000;">$@.space($.from.z; $.from.y..$.to.y; $.from.x..$.to.x)</code> (dimensions separated by semi-colon).</li><li style="text-align: left;">Tailspin projections can be captured as lenses, e.g. <code style="color: #cc0000;">:(to:;x:)</code>, which selects the <code style="color: #cc0000;">x</code> field of the record in the <code style="color: #cc0000;">to</code> field when applied.</li></ul><p>Many of these things, as well as use of Relations and the <code style="color: #cc0000;">matching</code> (semi-join) operator occur in <a href="https://github.com/tobega/aoc2023/blob/main/day22tt/app.tt">my solution</a> to <a href="https://adventofcode.com/2023/day/22">day 22 adventofcode 2023</a>.</p><p>Tailspin also has a group-aggregation projection, e.g. <code style="color: #cc0000;">$(collect {total: Sum&{of: :(score:)}} by {player:})</code></p><h3 style="text-align: left;">Text</h3><p style="text-align: left;">When the idea of text being an array of characters is discarded, the question arises of how to project parts of text strings. Transforming to UTF-8 bytes or an integer codepoint array should be supported, but it doesn't help in proper unicode text manipulation, as seen in the rosettacode exercises for <a href="https://rosettacode.org/wiki/Reverse_a_string">reversing a string</a> or <a href="https://rosettacode.org/wiki/XXXX_redacted">redacting words</a>. Splitting into an array of glyphs that are themselves text objects works for these, but glyphs vary in size so there may be issues with that approach as a general solution.<br /></p><p>Regular expressions are pretty standard and ubiquitous now, so I think we should just embrace them for extracting and replacing parts of text. It might be beneficial to have some form of parsing syntax to project text data into structured data, with bonus points if they can work reversibly as output formatters.</p><p>Tailspin does allow splitting into glyphs by streaming a string, e.g. <code style="color: #cc0000;">['abcde'...]</code> gives <code style="color: #cc0000;">['a','b','c','d','e']</code>. It also allows getting the text as UTF-8 bytes or a codepoint array. Most useful is the parser syntax that allows declarative specification of a data structure to parse the string into, e.g. <code style="color: #cc0000;">{ hand: <'\w+'>, (<WS>) bid: <INT"d"> }</code> to parse <code style="color: #cc0000;">'32T3K 765'</code> into <code style="color: #cc0000;">{ hand: '32T3K', bid: 765"d" }</code> ("d" is the unit). I haven't tried to make them reversible yet, but suspect that will only be possible with some restrictions to the current functionality.<br /></p><h2 style="text-align: left;">Selection</h2>One of the first selection mechanisms in higher-level languages was the arithmetic <code style="color: #cc0000;">IF</code> which redirected execution to one of three different locations depending on whether the argument was negative, zero or positive. Nowadays, the boolean <code style="color: #cc0000;">IF</code> has taken over.<p style="text-align: left;">Most of the time, the real state space contains more than just two cases. While it makes perfect logical sense to create a decision tree, and sets of boolean flags are easily represented in binary computers, nested <code style="color: #cc0000;">if</code> statements/expressions are not so easy for the human brain to grapple with, because each level down means more to keep in mind.</p><p style="text-align: left;">Flattening the cases to <code style="color: #cc0000;">if...else if...else if...else...</code>, more nicely represented as <code style="color: #cc0000;">match</code> (or <code style="color: #cc0000;">switch</code> or <code style="color: #cc0000;">CASE</code>), helps. Even then, since evaluation of cases is top to bottom, a human reader must keep in mind the implicit "and not any of the above". Perhaps the <a href="https://en.wikipedia.org/wiki/Guarded_Command_Language">GCL</a> is correct in (essentially) evaluating the cases in random order, enabling a human to consider each case on its own, and being more robust to code reordering.</p><p style="text-align: left;">On
some level there really is no distinction between a Selection and a
Projection, both being choices made according to specifications. A <code style="color: #cc0000;">map</code> operation is a projection of each value of a list, while a <code style="color: #cc0000;">filter</code> is a selection of values in a list. But <code style="color: #cc0000;">filter</code> could equally be considered a projection of the list itself.</p><p style="text-align: left;">Perceptually, perhaps a Projection selects data while a Selection selects code paths, but this gets muddied because a code path can simply result in data. Are null-conditional access operators (<code style="color: #cc0000;">?.</code> and <code style="color: #cc0000;">?[]</code>) or the elvis operator (<code style="color: #cc0000;">?:</code>) Projections or Selections? What about <code style="color: #cc0000;">if</code>-expressions?<br /></p><p style="text-align: left;">In Tailspin, templates (functions) by default just consist of a list of <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#matchers">matchers</a> (guard conditions) with a corresponding block to execute for each. Matchers are evaluated top to bottom and the block of the first true condition is executed. Matchers do not nest, although inline-defined templates can contain their own matchers.</p><h3 style="text-align: left;">Subtype polymorphism and typestates</h3><p style="text-align: left;">In OO programming, code can become much simpler by utilizing the dynamic dispatch of subtype polymorphism instead of explicitly performing a Selection based on the type or state of the object. An object itself can be organized according to the State pattern to delegate to an internal state object, with different state subtypes, rather than checking state variables in each method. This also organizes the different behaviours of a particular state together, which is how humans tend to think about the world.<br /></p><p style="text-align: left;">Typestates is a similar idea, but the interface is allowed to change with the state so as to only expose methods valid in that state.</p><p style="text-align: left;">Function overloading similarly uses the dispatch mechanism to choose the implementation based on the argument type(s). The difference lies in where the functionality is defined. Overloaded functions are usually all defined together for all different types, which mostly doesn't make sense because the implementations are unrelated except for having the same interface description (relation between input and output).</p><p style="text-align: left;">Some languages allow overloads to be defined anywhere, presumably where it makes most sense to the programmer. This ends up being even worse because it becomes almost impossible to find the implementations or even to know which of them have actually been defined and included in the program.<br /></p><p style="text-align: left;">Tailspin allows to organize objects (called processors) into <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#typestates">internal states</a>. There is currently no way to find out which state is active, unless explicit query methods are added by the programmer.<br /></p><h2 style="text-align: left;">Verification</h2><p style="text-align: left;">How can you feel confident that the program works as expected (at least most of the time)? <br /></p><h3 style="text-align: left;">Tests</h3><p style="text-align: left;">The simplest way to try to gain some confidence in the program's correctness is to run it on a known case, or several. Unfortunately, tests only guarantee that a correct program will pass, but many incorrect ones may pass as well. More tests only help if they <a href="https://hpmor.com/chapter/8">eliminate a hypothesis</a>.</p><p style="text-align: left;">In days gone by, testing was only done manually, even if test-first methodologies were already being applied here and there. Then testing became more automated by special test runner programs and tests are defined using a test harness library.</p><p style="text-align: left;">More modern languages realize that tests are important enough to be built-in to the language and that they should be written next to the code they test. I really appreciated Pyret's <code style="color: #cc0000;">where</code> clause at the end of a function to specify examples (tests, really). Pyret has additional ability to specify tests not directly related to a specific function.<br /></p><p style="text-align: left;">In Pyret, the tests are run every time the file is interpreted. I think this is probably the right thing to do, tests are useless if they aren't run.</p><p style="text-align: left;">In Tailspin, <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#testing">tests are defined with the code</a>, and it is easy to replace (mock, stub, fake) resource-demanding parts of the program. No automatic running, but probably something to consider.<br /></p><h3 style="text-align: left;">Contracts</h3><p style="text-align: left;">A contract means that if you do your part, I will do mine. In programming contracts, the preconditions required by a function or method can be specified and they are checked on every call. Preconditions check that functions are called correctly. On the other side of the bargain, the postconditions that are guaranteed by the function can be specified and are also checked on every call. Postcondition checks are like tests that are run on the actual input used, to verify that the function is implemented correctly.</p><p style="text-align: left;">Related
to contracts is also the ability to specify class invariants and loop
variants and invariants. It seems a little too much work, but maybe
those are things you have to think about anyway, in which case having to
think clearly enough to specify them and having them checked at runtime
could be beneficial.<br /></p><p style="text-align: left;">Contracts are central to the Eiffel programming language and rumour has it that it produces stable and reliable software, but evidently this has mostly not resulted in purchases of Eiffel developer seats. I haven't found any hard research proof, but contracts may be <a href="https://www.infoq.com/presentations/clojure-contracts/">the sweet spot between types and tests</a>. The tl;dr; is that preconditions allow more precise definitions than types do and postconditions are fantastic as the built-in asserts for property-based testing.<br /></p><p>Kotlin contracts seem to be something entirely different, not contributing to verification, but are rather ways of working around the compiler and type-checker.</p><p>Tailspin does not have contracts yet, but it is on the roadmap.<br /></p><h3 style="text-align: left;">Types</h3><p style="text-align: left;">There is actually no consensus on what types are or what they are for. On a practical level, it is useful to keep track of fixed-point and floating-point numbers so the correct machine operation is applied. On a theoretical level there is a similarly-named but different thing in logic and mathematics, and then there is the Curry-Howard correspondence whereby programs are proofs of their type signatures.</p><p style="text-align: left;">One purpose of types is to serve as really anemic contracts to verify that your program was put together sensibly. By limiting what can be expressed, it becomes easier to check the types than to run the program, so it can run as a sanity check during development. Also, type inference can be used to make this mostly automatic, although explicitly writing the types serves as an even better sanity check.<br /></p><p style="text-align: left;">A proven benefit of types is to serve as lightweight documentation, but clearly contracts could do that better. Only explicit typing will do for this, type inference doesn't help at all. As discussed under Aggregation, names probably beat types here, but a combination might be even better. This was a digression into the Communication concept, though.</p><p style="text-align: left;">Types can be given interesting properties to help verify and enforce correctness, like <a href="https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html">Rust's ownership</a> rules. <a href="https://austral-lang.org/linear-types">Linear types</a> that must be used exactly once are another example, as are <a href="https://blog.janestreet.com/oxidizing-ocaml-locality/">modes in OCaml</a>. Instead of putting all these things in the same type system, they could be separate orthogonal mini type systems.</p><p style="text-align: left;">In Tailspin, types are currently checked at runtime, and they can be defined to have any property expressible in the language. Tailspin enforces that record fields with the same name have the same type, as per domain-driven design principles. Tailspin will also <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#autotyping">automatically create tagged types</a> from strings or numbers, so that <code style="color: #cc0000;">country´'Georgia</code> is different from <code style="color: #cc0000;">first_name´'Georgia'</code> or <code style="color: #cc0000;">state´'Georgia'</code>, and <code style="color: #cc0000;">part_id´9</code> is different from <code style="color: #cc0000;">shoe_size´9</code>.<br /></p><h3 style="text-align: left;">Proofs</h3><p style="text-align: left;">Formal proofs of correctness are a bit of a Holy Grail in programming. From my limited understanding, it is possible to some extent but rapidly becomes harder as the program increases in complexity. Anecdotally I have heard that working with a prover can suck up aeons of time.</p><p style="text-align: left;">Having integrated specifications in the language, like <a href="https://dafny.org/">Dafny</a>, is probably helpful. The question is if it feels worth the effort.<br /></p><h2 style="text-align: left;">Communication</h2><p style="text-align: left;">Since communication was also my main "goodness" criterium, I have already touched on it under the other sections, so I won't repeat those details here. I have also previously written some thoughts about <a href="https://tobega.blogspot.com/2023/09/using-programming-structures-to.html">how programming structures can be used in communication</a>.</p><p style="text-align: left;">It may seem plausible that having many different ways of expressing code would be helpful to communicate nuances, but more ways of writing means that readers need more knowledge. Scala is infamous for teams not being able to understand each other's preferred subsets of the language. In contrast, Go is designed with the goal of having only one way of expressing a particular algorithm.</p><p style="text-align: left;">In the Repetition section, I questioned whether the <code style="color: #cc0000;">map</code>, <code style="color: #cc0000;">filter</code> et al. functions conveyed any meaningful difference or were simply "mechanics". An example of this is perhaps the <a href="https://adventofcode.com/2023/day/9">day 9 adventofcode</a> solutions I wrote in <a href="https://github.com/tobega/aoc2023/blob/main/day09/app.arr">Pyret</a> and <a href="https://github.com/tobega/aoc2023/blob/main/day09tt/app.tt">Tailspin</a>. Despite being the identical algorithm, the Pyret solution just seems to be more obscured by "mechanics".<br /></p><p style="text-align: left;">On the other hand, being able to choose whether to express the algorithm in terms of the input (e.g. by matchers in Tailspin) or the output (by literal constructor) can make a huge difference in understandability. See the roman numerals example in section 8 of Jeremy Gibbon's "<a href="https://www.cs.ox.ac.uk/jeremy.gibbons/publications/copro.pdf">How to design co-programs</a>". In Tailspin, <a href="https://rosettacode.org/wiki/Roman_numerals/Encode#Tailspin">encoding roman numerals</a> is naturally expressed in terms of the output, while <a href="https://rosettacode.org/wiki/Roman_numerals/Decode#Tailspin">decoding them</a> naturally becomes a repeated projection of the input.</p><h2 style="text-align: left;">Final thoughts</h2><p style="text-align: left;">It turned out to be easier than I first thought to come up with concepts to analyze. I think it was definitely worth doing and I'll have to try do this for error handling and concurrency as well. For my choice of "good", I think my design choices for Tailspin are supported by this concept analysis.</p><p style="text-align: left;"> <br /></p><p style="text-align: left;"></p>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-76032946223778287402023-09-03T12:15:00.003-07:002023-09-03T20:44:17.554-07:00Using programming structures to communicate<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
<p> When we first learn to code, we struggle with the basic use of the programming language and just getting the program to work. As we gain more practice, we can start to explore "better" ways to write the code while it still does the same thing.</p><p>"Better" code is really all about communication with other humans, yourself in a little while, yourself later, or some other human who needs to work with the code.</p><p>When the communication is clear and efficient we get maintainable code that is a joy to work with. When the communication is obscured or missing, the code turns into an unintelligible mess.</p><p>So what means of communication can we use?<br /></p><h2 style="text-align: left;">Comments</h2><p style="text-align: left;">The first communication technique we tend to learn is the use of comments, to communicate hints to ourselves how the code works so we can understand it later. Since we are initially still struggling with basic syntax, the comments might tend to be something like the below (I have actually seen this in production code!):<br /></p>
<pre class="prettyprint" style="border: 1px solid black; font-size: 0.98em; padding: 0.1em;"><code>// Add 1 to i
i = i + 1;</code></pre>
<p>A few years down the line, the code might look something like this:</p>
<pre class="prettyprint" style="border: 1px solid black; font-size: 0.98em; padding: 0.1em;"><code>// Add 1 to i
i = i + 2;</code></pre>
<p>An incorrect comment is worse than no comment. In this case, easy to ignore, but when the comment is more usefully explaining the algorithm it becomes downright devastating if it no longer applies and may send you on an hours-long goose chase.</p><p>So we learn the hard way that comments are untrustworthy and we need to find other ways to explain the code.</p><p>Comments can still be very useful to describe things that are NOT in the code. A todo-note, for example, explains what code has not been written even though it might need to be written in the future. <br /></p><h2 style="text-align: left;">Code disposition</h2><p style="text-align: left;">The order the code is written in can make a huge difference to ease of understanding. If the steps to achieve each important part of the algorithm are grouped together, the code can be understood piecemeal. Even better when a group of connected parts can be extracted into its own named procedure (method, function) or assigned as a named value explaining what it represents.<br /></p><p style="text-align: left;">The optimal way to order the code is the one that minimizes the amount of things the reader needs to keep in mind at each point.<br /></p><h3 style="text-align: left;">Layers of abstraction</h3><p style="text-align: left;">Essentially, we create a new language when we create named procedures and values. If we start with the programming language itself as language L0, then we form language L1 from the values and procedures defined in L0. After that, we can form language L2 by combining things from L1 into more complex procedures. And so on. Finally, the program itself is expressed in the top level language we created, which serves as an explanation of what the program does without getting bogged down in too many details. </p><p style="text-align: left;">More loosely speaking, it is often said that you should break out a named entity when the "level of abstraction" changes, which happens when "the code goes from explaining what it is doing to how to do it". That's not a very clear explanation, but rephrased in the layered languages above, it means that when you dip down into concepts from a lower layer of language, you should probably create a new concept on the language layer you are using.</p><p style="text-align: left;">Of course things are never that ideal. A more practical way might be to consider what things need to be kept in mind at each point in the program. If the reader needs to remember more than about 4 things at any one
time, there is a risk of cognitive overload, which makes it
substantially more difficult to understand. Grouping some concepts together into new richer concepts may help. Another way to look at it
might be that <a href="https://www.codesimplicity.com/post/readability-and-naming-things/" target="_blank">code should take up space in proportion to its importance</a>.</p><h3 style="text-align: left;">Data structures</h3><p style="text-align: left;">Layering concepts obviously also apply to data so that at one level it might make sense to talk about an x-coordinate and a y-coordinate, while at a higher level we would talk about a point and at higher levels still we might work with lines and rectangles. This is related to types, but types have larger implications and will be discussed separately.<br /></p><p style="text-align: left;">Beyond pure representation of data, there is another aspect of structuring data in a way to both simplify and explain the program. In fact, the easiest way to understand any code is to start looking at the data structures. This was expressed in 1975 as:<br /></p><blockquote><p style="text-align: left;">Show me your flowchart and conceal your tables, and I shall continue to
be mystified. Show me your tables, and I won't usually need your
flowchart; it'll be obvious. - Fred Brooks, <i>The Mythical Man-month</i></p></blockquote><p> And repeated in more modern form in 1997:</p><blockquote><p>Show me your code and conceal your data structures, and I shall continue
to be mystified. Show me your data structures, and I won't usually need
your code; it'll be obvious. - Eric S. Raymond, <i>The Cathedral and the Bazaar</i></p></blockquote><p>When designing an algorithm, you need to make decisions about how you will represent relationships between the data and how you will traverse the data elements. If there is an ordering between the elements and there can be duplicates, use a list. If there should not be duplicates, use a set. Duplicates without order, a bag. A queue implies elements on the same level, a stack implies a hierarchy. A tree can be arranged in ways to enable efficient searching. If elements can be associated with a consecutive numeric index, an array affords immediate access, for other associations a map is your friend, while for checking existence, we're back to a set.</p><p>Whether to recurse or iterate is related to data structures and can give similar distinctions as queue versus stack, although they are equivalent and iteration can be mechanically transformed to recursion and vice versa.</p><p>One important aspect of datastructures is whether they are immutable or not. An immutable data structure is just one thing to keep in mind. Otherwise all the separate things that can be changed in the data structure are things that need to be kept in mind. Mutability effects can be mitigated by clear ownership of the data.</p><h3 style="text-align: left;">Data ownership</h3><p style="text-align: left;">Which part of the code that is responsible for the data is important to communicate in order to keep track of when the data might be changed (if mutable) and when the data is no longer needed (so that memory can be reclaimed), and if the memory has been reclaimed to know that the data is no longer accessible.</p><p style="text-align: left;">Some languages side-step the memory reclamation issue by automatically reclaiming it when it is no longer used, either through garbage-collectors or reference-counters.</p><p style="text-align: left;">Rust has mechanisms to specifically track and express ownership in the code. In other languages you should probably document it.<br /></p><h3 style="text-align: left;">Naming</h3><p style="text-align: left;">Picking accurate names is critical to correct communication. <a href="https://buttondown.email/hillelwayne/archive/naming-things-is-a-poor-name-for-naming-things/" target="_blank">It can also be quite difficult.</a><br /></p><p style="text-align: left;">In one review of code that was supposed to compare images by comparing pixel values, I saw on closer inspection that the values named "pixel" actually turned out to be indexes into the image and the program was just comparing that indexes were equal, which would always be true.</p><p style="text-align: left;">Names are known by the computer so references to names will in most languages be checked and provide you with a clear error when you reference an undefined name. Often this check will even happen before the code actually starts running. This checkability can be used when you need to revise every usage of a particular value, just change the name and the computer will remind you of all the references you haven't revised yet. This property also applies to types, to be discussed later.</p><h3 style="text-align: left;">Language differences</h3><p style="text-align: left;">There are of course differences in exactly how things are expressed in different languages, especially between different programming paradigms, but by and large the same kind of things will be communicated in similar ways.</p><p style="text-align: left;">In a procedural language, you have both nouns (data) and verbs (procedures) and you could say that to calculate the variance of a collection of numbers you could add together the square of every element, count the number of elements and then divide the sum by the count of the elements.</p><p style="text-align: left;">In an object-oriented language, an object has state and can respond to requests, so you would ask the numbers to square themselves, then ask the collection to add up all the elements, ask the collection how many elements there are and then ask the resulting sum to divide itself by the count.<br /></p><p style="text-align: left;">In functional languages, even functions are things, so there are no verbs. You would have to say that the variance is the quotient between the sum of the squares of the elements and the count of the elements. That can be a bit of a mouthful so a more understandable grouping and ordering is
often achieved by let-statements, to for example define the squares, their sum and the count separately before obtaining the quotient. Another option is by a pipeline (or a threading
macro) of transforms to turn the list into a list of squares, then into a sum and a count and then divide them.</p><h4 style="text-align: left;"> A note on "declarative"</h4><p style="text-align: left;">A program is said to be "declarative" when it specifies what is to be done, rather than how to do it. That's exactly the idea of the "levels of abstraction" mentioned above! Every level of the program should be as declarative as possible for most efficient communication.<br /></p><p style="text-align: left;">Languages such as SQL and HTML are considered to be declarative. Some people want to claim that functional languages are generally more declarative and it is indeed difficult to explain how to do something when you only have nouns at your disposal. But with more than a few "of the" in a row, it really looks a lot more like a list of instructions (or, I suppose, how to define things). On the other hand, no "declarative" claims are made about OO, even though objects were created to be the most declarative way of modelling things in the real world.</p><h4 style="text-align: left;">Choosing a paradigm</h4><p style="text-align: left;">In most modern languages you can choose between procedural, functional and object-oriented modes of expression. The trick is to determine which way the separate aspects of your program are best described.</p><p class="_1qeIAgB0cPwnLhDF9XSiJM">As a guide, I like to think of a triangle of code styles as follows:</p><ol class="_1eJr7K139jnMstd4HajqYP" style="text-align: left;"><li class="_3gqTEjt4x9UIIpWiro7YXz"><p class="_1qeIAgB0cPwnLhDF9XSiJM">At
the top of the triangle you are working procedurally with general (possibly
abstract) datatypes imperatively and finally arrive at a result that you
can interpret satisfactorily.</p></li><li class="_3gqTEjt4x9UIIpWiro7YXz"><p class="_1qeIAgB0cPwnLhDF9XSiJM">When
you focus on what your data IS, and create datatypes that are more and
more specific to your program, you move down the left side into
functional programming, with a clearly-defined specific input and a
function call that produces a clearly-defined specific output.</p></li><li class="_3gqTEjt4x9UIIpWiro7YXz"><p class="_1qeIAgB0cPwnLhDF9XSiJM">If
you instead focus on what your objects DO, and create objects that do
things more and more specific to your program, you move down the right
side into OOP. Messages/calls produce actions and reactions until you
get your answer (part of which may be encoded in the state of the
system)</p></li></ol><p style="text-align: left;"></p><p style="text-align: left;"> Which of these styles correspond best to the way the desired functionality is most naturally described?<br /></p><h2 style="text-align: left;">Automated tests</h2><p style="text-align: left;">Fundamentally, a test, when run, communicates whether the specified conditions still hold or not. A breaking test is, or rather should be, an <i>alarm bell</i> that the code no longer does what it is supposed to.</p><p style="text-align: left;">Unfortunately, many tests "cry wolf" and merely signal that the code changed, which you probably already knew because you changed it.</p><p style="text-align: left;">Requirements can be communicated through tests, even when they are not run, if the tests are written as describing the requirements.</p><p style="text-align: left;">If you write the test before you write the code, the test is more likely to reflect requirements and can communicate to you when your code is done. Just formulating the test can help clearly communicate to yourself what needs to be done. You already should have an idea of that, so why not try to make it clearer?<br /></p><p style="text-align: left;">In the layered language view, tests are one layer above your code and can therefore be used for communication about the code. Thinking about the layers might also be helpful to avoid digging too deep when making assertions.</p><p style="text-align: left;">One thing to consider is that writing and maintaining tests is an extra cost and it may not be worth it for trivially analyzable code.<br /></p><p style="text-align: left;">For further thoughts about tests, I wrote an article on <a href="https://cygni.se/write-meaningful-unit-tests/" target="_blank">writing meaningful unit tests</a>.</p><h2 style="text-align: left;">Contracts</h2><p style="text-align: left;">Essentially, a contract is about the guarantees made by the code.</p><p style="text-align: left;">If you hold up your end of the deal when calling a procedure (method, function) by obeying the preconditions stipulated, the procedure will gurantee to hold up its end of the deal and fulfil all the postconditions. If, on the other hand, the preconditions are not obeyed, <i>anything</i> can happen.</p><p style="text-align: left;">Other types of contracts concern "invariants", things that are guaranteed to always be true both before a call is made (or a loop iteration entered) and after the call (or loop iteration) is completed.</p><p style="text-align: left;">Thinking about contracts can be very beneficial to making your code correct. According to the <a href="https://en.wikipedia.org/wiki/Design_by_contract" target="_blank">Design by Contract</a> method you should do so before you start writing the actual code. As with tests, you probably have an idea about it already and formalizing the contracts can clarify thinking, as well as communicating that to a future maintainer.<br /></p><p style="text-align: left;">The documentation (that you, like me, probably didn't write) for every piece of the program should contain information about the contracts, that is really the whole point of documentation. But documentation is like comments, something other than the code and must be kept in mind, so it would be preferable to enforce contracts in code for automaic reminders. A very successful example is runtime bounds checking on array access which helps catch large amounts of bugs and prevent malicious attacks.</p><p style="text-align: left;">Some languages have built-in support for specifying contracts, but it is quite possible to write contract-checking code yourself. Most important is to check preconditions because otherwise you have no clue what might happen. Postconditions are more easily spotted as bugs and they tend to be partly covered by tests. Postconditions also tend to be more expensive to compute. A common strategy is to turn off contract checking in production with the rationalisation that the most common problems will have been discovered in staging and development environments.</p><p style="text-align: left;">A failing contract is a serious condition signifying that you don't really know what's going on. The safest way to handle it is to just exit the program as quickly as possible. If you need to keep other things working, having a monitor process automatically restart your program is useful. Don't forget to make sure some human becomes painfully aware of what happens if you want it to ever be fixed.<br /></p><h2 style="text-align: left;">Types</h2><p style="text-align: left;">Types in programming languages can generate almost religious discussions. Type systems also have deep connections to mathematical and logic theory. In practice, the use of types in programming languages is all about communication.</p><p style="text-align: left;">A piece of data can be classified as belonging to a type. Different pieces of data of the same type are interchangeable because they have the same characteristics, whatever that means. Data of different types should not be confused with each other. Naming and typing can be used in somewhat overlapping ways for this information, depending on what's available in the language.</p><p style="text-align: left;">The use of types can help to show which pieces of a program are related to each other and how the data flows. This information can then be reported back to you by the computer when you make changes that don't match up. <a href="https://www.reaktor.com/articles/refactoring-30000-lines-js-types" target="_blank">Here's an article about using types to help refactor a large program</a>.</p><p style="text-align: left;">Specifying types on input parameters and return values has been <a href="https://www.researchgate.net/publication/259634489_An_empirical_study_on_the_impact_of_static_typing_on_software_maintainability" target="_blank">shown to be beneficial as a form of documentation</a>. These specified types also capture aspects of the pre- and postconditions for the procedure/function/method.</p><p>Typescript contains interesting transforms that can be performed on types to show how a related type corresponds to it.</p><p style="text-align: left;">Type inference is useful for some of these things, but not as effective for documentation and contract specification.<br /></p><p style="text-align: left;">A <a href="https://www.electronicdesign.com/technologies/embedded/article/21805823/assessing-the-ada-language-for-audio-applications" target="_blank">case study comparing an algorithm in Ada vs C</a> shows the effectiveness both of being able to specify many different types and having a language that applies strong typing. But as the article points out, you have to actually do some work to gain the benefits:</p><p style="text-align: left;"></p><blockquote>"<i>During the design of the software system, the developer must select
types that best model the data in the system and that are appropriate
for the algorithms to be used. If a program is written with every
variable declared as Integer, Float or Character, it will not be taking
advantage of the capabilities of Ada."</i></blockquote><p>While types written in comments, or in a language that mostly ignores or automatically converts types, do communicate some things, the biggest value comes in having them strongly enforced by the computer. </p><p>Since it is often easier to determine the resulting type from an operation than actually performing the operation, types can to some extent be statically checked before the program runs, in less time than it takes to run the program, which can be helpful.</p>Unfortunately, the definition and manipulation of types forms a separate language from your programming language and it can become very complex, which can impede communication. Once the type-specification language becomes Turing complete, which happens all too easily, it is no longer possible to generally guarantee or predict that the type-check ever finishes.<p>Some things like array bounds checking are generally impossible to do at compile time.<br /></p><p>Like with contracts, a failing type check is a serious condition where the program is not doing what you think it is. Some languages gratuitously try to convert types for you, which might make sense in some contexts or to some degree, but can make bugs very difficult to find. Note that the idea of truthiness is an automatic type conversion, as is allowing equality comparisons of different types of values.<br /></p><p>Like with tests, it is possible that having a type system that is too complex or prescriptive may not be worth the overhead in comparison to the benefit received. </p><p>An example of a very successful use of types to ease usability of an API is IMO <a href="https://assertj.github.io/doc/" target="_blank">AssertJ</a>. The <code>assertThat</code> function returns an object type with only the assertion methods relevant to the input type.<br /></p><h2 style="text-align: left;">Modularity and information hiding<br /></h2><p style="text-align: left;">What you don't say is sometimes more important than what you say. Modularity is the ability to hide complex "machinery" of how things are done and only expose the ability to use what it does. As long as the exposed interface and contract remains the same, you can change whatever you like inside or even replace the whole thing with an equivalent that also obeys the same interface and contract. For tests, it doesn't even need to obey the contract fully, just emulate it well enough for the particular test.</p><p style="text-align: left;">Information hiding comes in many forms. The one that's most commonly mentioned is OO encapsulation in objects/classes. Exposing a property via getters and setters hides the fact that it's a field. Not even having getters and setters and just performing services for the caller hides even more information. Another way to hide information is to define helper functions inside the function that uses them (in java you can even define a class inside a method).</p><h2 style="text-align: left;">Miscommunication</h2><p style="text-align: left;">The clearer the communication, the easier the code will be to maintain. There is a tension between code that is easy to read and code that is easy to write and unfortunately there is often too much focus on the writing.<br /></p><h3 style="text-align: left;">Overspecification</h3><p style="text-align: left;">Tests often suffer from specifying how the code works rather than what it is supposed to do. Faced with a test breakage it is difficult to know whether to fix the test or the code.</p><p style="text-align: left;">Passing in a large compound data structure (or "entity") into a function that only uses one or two fields definitely makes the function harder to reuse. Code reuse is generally somewhat overrated, however, so the question is what communicates the intent best? Should that function know about the structure of the entity or is it the surrounding code's job to deconstruct it first?</p><p style="text-align: left;">ORMs really make a mess by working with huge entities. Most of the time you're just interested in getting a few pieces of information like a list of friends' names, you don't need the whole social graph. Treating the database as representing relations between facts rather than representing entities will make things much more manageable. Embrace SQL and why not 6NF along with it?</p><h3 style="text-align: left;">Opaque languages</h3><p style="text-align: left;">Decorators and annotations may certainly be declarative ways of adding functionality, but there is no practical way to find out what they do without learning their language. Unfortunately, that language is often missing functionality as well as being underdocumented. Frameworks fall in a similar category, making easy things trivial and difficult things impossible, because you have to fight with the framework.</p><p style="text-align: left;">Domain specific languages are sometimes created with the idea that the domain experts should be able to use them. Again they tend to be underpowered and underdocumented and, what's worse, too difficult for the domain experts anyway, so the programmers now end up coding in the DSL as well as maintaining it.</p><p style="text-align: left;">Note the difference with the layered languages formed by your code, where you can easily go down a level to understand exactly how each layer works and you can easily refactor and reshape it as needed.</p><p style="text-align: left;">A related difficulty can arise when a section of code has too many dependencies, perhaps only using a small part of each. The "lower-level" language formed is just too large and unwieldy. A solution could be to organize a module that exports only what you need and encapsulates the other dependencies.<br /></p><h3 style="text-align: left;">Hidden dependencies and unknown assumptions<br /></h3><p style="text-align: left;">Hidden dependencies arise when two different pieces of code depend on the same knowledge, for example an assumption that all files are in a specific directory. The remedy is to make sure there is a single source of truth for every fact needed by the program.</p><p style="text-align: left;">The assumptions made in a module may not always be explicitly stated (and the programmer may even be unaware that an assumption was made), which causes problems when the user of the module has a different set of assumptions (or facts) to deal with. <br /></p><p style="text-align: left;">An example of insufficient communication of assumptions occured in the Julia language, where functionality can often be <a href="https://www.youtube.com/watch?v=kc9HwsxE1OY" target="_blank">magically shared</a> between packages unknown to each other. Unfortunately, this can also cause <a href="https://yuri.is/not-julia/" target="_blank">obscure bugs and problems</a> when there are unknown assuptions to deal with. In particular, arrays used to be indexed from 1 to the length of the array, until someone figured out how to make offset arrays that could start anywhere, which broke the assumptions of most other packages. (I still think Julia is worth trying, BTW)</p><h3 style="text-align: left;">Implementation reuse and pre-emptive generalization</h3><p style="text-align: left;">Sometimes two pieces of code can be identical and you feel the urge to merge them together. Unless they are meant to do exactly the same thing in all future versions of the program, resist the urge. A guide may be if it is difficult to provide a name that sounds great for all usages, resist the urge, because then they are logically different things and they will evolve in separate directions. Communicate that logical difference, don't make a future maintainer try to guess which usage was which when trying to tear them apart.</p><p style="text-align: left;">Related to that is when you think a particular functionality you are writing could be much more generally applicable. Resist the urge, because the generalized expression is likely to be more complex and less obviously applicable to the current use. Also, it could be that the code in future needs to be generalized in a slightly different direction. Don't make a future maintainer have to try to understand that your generalization is not generally used and that they can undo it (and must undo it). <br /></p><h3 style="text-align: left;">Inconsistent usage</h3><p style="text-align: left;">A concrete example is the use of the word <code>final</code> on java classes which prevents creation of subclasses. The standard <code>String</code> class is marked <code>final</code> so that it can be used for secure credentials without risk of sneaky subclasses stealing the data. In that context <code>final</code> means "do not override, bad things will happen if you do".<br /></p><p style="text-align: left;">Some people feel that you should defensively mark a class <code>final</code> if you haven't given any thought to how it can be subclassed. This is a much weaker and less useful communication and you are also removing the user's right to replace your class with a different implementation.</p><p style="text-align: left;">The worst case is when you have programmers of both schools in a codebase, so the word <code>final</code> (or the absence of the word <code>final</code>) carries no discernible meaning at all.</p><p style="text-align: left;">Consistency is key to maximizing communication. <br /></p><h3 style="text-align: left;">Prescriptive practices</h3><p style="text-align: left;">Any practice that is mandated obviously has no communicative value.</p><p style="text-align: left;">Common mandates are to create interfaces corresponding to every class, or to always organize the code in specific layers or groups of files.</p><p style="text-align: left;">It needs to be carefully considered if the practice itself has enough value to outweigh the loss of communication.</p><h2 style="text-align: left;">Conclusion</h2><p style="text-align: left;">There are many ways to use the code to communicate things about the code beyond it merely working. Things you would want to communicate are the requirements and assumptions, preferably set for automatic reminders. I hope it's an interesting and useful perspective and I think that code will be better if it is written deliberately for the purpose of communicating.<br /></p><p></p>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-31388043556074309762022-12-31T07:46:00.002-08:002023-09-11T06:19:43.168-07:00Evaluating the Tailspin language after Advent of Code<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
<p>My very short (and very biased) opinion is that Tailspin is an excellent language, at least for Advent of Code.</p><p>Consider <a href="https://adventofcode.com/2022/day/5" target="_blank">day 5</a> 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 <a href="https://github.com/tobega/aoc2022/blob/main/day05/app.tt" target="_blank">the Tailspin solution</a>. 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:</p>
<pre class="prettyprint" style="border: 1px solid black; font-size: 0.88em; padding: 0.1em;"><code>composer parseInstruction
{move: (<='move '>) <INT"crates">, from: (<=' from '>) <stack´INT>, to: (<=' to '>) <stack´INT>}
end parseInstruction</code></pre>
<p>Parsing the crate diagram is only slightly more complex, I explain it in more detail in <a href="https://www.youtube.com/watch?v=Rj45_HF0d8s" target="_blank">the video of me solving the problem</a>.</p><p>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:</p>
<pre class="prettyprint" style="border: 1px solid black; font-size: 0.98em; padding: 0.1em;"><code>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</code></pre>
<p>But anecdotes like this are a little random, can the evaluation be more systematic?<br /></p><h2 style="text-align: left;">Evaluating usability of a language <br /></h2><p>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 <a href="https://www.uxbooth.com/articles/a-usable-guide-to-cognitive-dimensions/" target="_blank">this article on the cognitive dimensions applied to user interfaces</a>.</p><h2 style="text-align: left;">Caveats</h2><p style="text-align: left;">Trying to be a little scientific, I have to consider threats to the validity of this "study":</p><ul style="text-align: left;"><li>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.</li><li>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.</li></ul><h2 style="text-align: left;">Quick description of Tailspin</h2><p style="text-align: left;">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".</p><p style="text-align: left;">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.<br /></p><p style="text-align: left;">The fundamental idea in Tailspin is that <a href="https://patternsinfp.wordpress.com/2018/11/21/how-to-design-co-programs/" target="_blank">program structure follows data structure</a>. 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.<br /></p><p style="text-align: left;">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 "<span style="font-family: courier;">-></span>".</p><p style="text-align: left;">Creating values is mostly familiar, "<span style="font-family: courier;">[</span>" and "<span style="font-family: courier;">]</span>" creates a list of values, while "<span style="font-family: courier;">{</span>" and "<span style="font-family: courier;">}</span>" create a structure with values named by keys, e.g. "<span style="font-family: courier;">my_key:</span>". Numbers are mostly just numbers, although they could be identifiers, "<span style="font-family: courier;">my_id´5</span>", or have units/dimensions "<span style="font-family: courier;">3"x"</span>". Ranges (streams of numbers) are created by a start and end value (possibly excluded) with an optional stride, e.g. "<span style="font-family: courier;">1..5:2</span>" to give "1 3 5".</p><p style="text-align: left;">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 <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#projections-and-lenses" target="_blank">more interesting projections</a> are possible. The use of the "<span style="font-family: courier;">$</span>" 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 "<span style="font-family: courier;">$</span>", which simply means the current value to be transformed (in Kotlin it would be called "<span style="font-family: courier;">it</span>"). 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.</p><p style="text-align: left;">"<span style="font-family: courier;">templates</span>" 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, "<span style="font-family: courier;"><</span>" and "<span style="font-family: courier;">></span>". The first matching block is executed. The symbol "<span style="font-family: courier;">#</span>" means that a value gets sent to be matched. A "<span style="font-family: courier;">composer</span>" is a type of templates for parsing strings into structured data and a "<span style="font-family: courier;">processor</span>" is essentially an object containing mutable state. For more details and tutorials, <a href="https://github.com/tobega/tailspin-v0" target="_blank">look at the main Tailspin site</a>.</p><h2 style="text-align: left;">Evaluating the dimensions</h2><h3 style="text-align: left;">Viscosity</h3><p style="text-align: left;">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.</p><p style="text-align: left;">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.</p><p style="text-align: left;">Consider <a href="https://github.com/tobega/aoc2022/blob/main/day14/app.tt" target="_blank">the day 14 solution</a> 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).</p><p style="text-align: left;">Even simpler was <a href="https://github.com/tobega/aoc2022/blob/main/day11/app.tt" target="_blank">the day 11 solution</a> where monkeys were playing with the items from your pack. To support part 2, I just had to add a "<span style="font-family: courier;">then:</span>" parameter to the operations (lines 38-52) and inject the appropriate function during monkey object creation in each part.</p><p style="text-align: left;">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 <a href="https://github.com/tobega/aoc2022/tree/main/day07edu" target="_blank">day 7 in three coding styles</a> by just copy-pasting and adapting. The basic structure is the same.</p><p style="text-align: left;">Perhaps the most viscosity experienced concerns accessing the mutable state associated with each templates or processor. In <a href="https://github.com/tobega/aoc2022/blob/main/day20/app.tt" target="_blank">the day 20 solution</a>, I took the original "<span style="font-family: courier;">solutionPart1</span>" templates and renamed it to "<span style="font-family: courier;">mix</span>", with a "<span style="font-family: courier;">file:</span>" parameter (the "<span style="font-family: courier;">input</span>" on line 5 was originally named "<span style="font-family: courier;">file</span>"). 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 "<span style="font-family: courier;">@mix</span>" references on lines 24 and 25 had to simultaneously be renamed from "<span style="font-family: courier;">@solutionPart1</span>". 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).</p><p style="text-align: left;">Another viscosity frequently encountered concerns when a number or string becomes <a href="https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#autotyping">autotyped</a>. 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.<br /></p><h3 style="text-align: left;">Hidden dependencies</h3><p style="text-align: left;">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.</p><p style="text-align: left;">Tailspin tries to make dependencies visible by:</p><ul style="text-align: left;"><li>The above-mentioned requirement to name the context of the mutable state accessed from nested contexts.</li><li>Requiring that symbols from another module must be prefixed with a module identifier when accessed.<br /></li><li>Requiring that the main program file specifies all modules used, and all modules that it allows other modules to use.</li></ul><p>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.</p><p>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.</p><p>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.</p><h3 style="text-align: left;">Premature Commitment and Enforced Lookahead</h3><p style="text-align: left;">This concerns constraints on the order of doing things that force the user to make a decision before the proper information is available.</p><p style="text-align: left;">I can't at the moment think of anything that forces a premature commitment or undue lookahead.</p><h3 style="text-align: left;">Abstractions, abstraction hunger and the abstraction barrier</h3><p style="text-align: left;">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, <a href="https://www.pathsensitive.com/2022/03/abstraction-not-what-you-think-it-is.html" target="_blank">this article tries to clarify the confusion surrounding abstraction</a>.)<br /></p><p style="text-align: left;">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.</p><p style="text-align: left;">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).</p><p style="text-align: left;">Tailspin is somewhat abstraction-hungry. You have to create a templates (function) instance for any of the following reasons:</p><ul style="text-align: left;"><li>Conditional evaluation. A series of matchers can only exist as part of a templates instance.</li><li>Mutable state can only exist within a templates instance during an invocation, or, more persistently, as part of a processor (object) instance.</li><li>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.<br /></li><li>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.</li><li>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.</li></ul><p>Note that templates can be anonymous and defined inline in the pipeline.</p><p>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.</p><h3 style="text-align: left;">Secondary notation</h3><p style="text-align: left;">Secondary notation is about providing additional information by other means than the official syntax needed to make things work.</p><p style="text-align: left;">Tailspin allows addition of comments by a "<span style="font-family: courier;">//</span>" that initiates a comment until the end of the line.</p><p style="text-align: left;">Tailspin does not depend upon whitespace so that can be used to convey additional information by line breaks and indentation. <br /></p><p style="text-align: left;">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.</p><p style="text-align: left;">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?<br /></p><h3 style="text-align: left;">Visibility & juxtaposibility</h3><p style="text-align: left;">Visibility concerns the ability to view and find components easily, while juxtaposability concerns the ability to place components side-by-side to compare them.</p><p style="text-align: left;">Juxtaposibility is not provided within the language and has to be achieved by, for example, split editor windows.</p><p style="text-align: left;">In Tailspin the syntax is designed to show the start and end of components clearly, intended to help visibility:</p><ul style="text-align: left;"><li> Templates definitions start with "<span style="font-family: courier;">templates</span>", "<span style="font-family: courier;">source</span>" or "<span style="font-family: courier;">sink</span>" followed by a name, and end with "<span style="font-family: courier;">end</span>" also followed by the name. Repeating the name increases visibility at the cost of diffuseness. Similarly, processor and composer definitions end with "<span style="font-family: courier;">end</span>" and the name repeated.</li><li>Test blocks start with "<span style="font-family: courier;">test</span>" followed by a descriptive string and end with "<span style="font-family: courier;">end</span>" followed by the same description.</li><li>Inline templates start with "<span style="font-family: courier;">\(</span>" and end with "<span style="font-family: courier;">\)</span>". They can be anonymous or have a name after the "<span style="font-family: courier;">\</span>", repeated both at start and end.<br /></li><li>Value definitions, state assignments and string interpolations end with "<span style="font-family: courier;">;</span>". Definitions start with "<span style="font-family: courier;">def</span>", state assignments start with "<span style="font-family: courier;">@</span>" and string interpolations start with "<span style="font-family: courier;">$</span>".<br /></li><li>A pipeline usually ends with a "<span style="font-family: courier;">!</span>", either alone as "emit into calling context", or before an identifier that "swallows" the current value. A pipeline could end with a "<span style="font-family: courier;">#</span>", 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.</li><li>Lists start with "<span style="font-family: courier;">[</span>" and end with "<span style="font-family: courier;">]</span>", list items end with "<span style="font-family: courier;">,</span>" except at the end of the list. Structures start with "<span style="font-family: courier;">{</span>" and end with "<span style="font-family: courier;">}</span>", fields start with an identifier followed by a "<span style="font-family: courier;">:</span>" and a value production ending in a "<span style="font-family: courier;">,</span>", except at the end of the structure. Relations start with "<span style="font-family: courier;">{|</span>" and end with "<span style="font-family: courier;">|}</span>", with comma-separated structures or value productions.<br /></li><li>Matcher expressions start with "<span style="font-family: courier;"><</span>" and end with "<span style="font-family: courier;">></span>". Additional conditions start with "<span style="font-family: courier;">?(</span>" and end with "<span style="font-family: courier;">)</span>".</li></ul><p>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.</p><p>Using a symbol from a module is required to be prefixed with an identifier associated with the module.<br /></p><h3 style="text-align: left;">Closeness of mapping</h3><p style="text-align: left;">This dimension concerns how closely the notation represents the original problem. <br /></p><p style="text-align: left;">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.<br /></p><p style="text-align: left;">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.</p><p style="text-align: left;">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.<br /></p><p style="text-align: left;">For another example, consider the following code from lines 11-26 the <a href="https://github.com/tobega/aoc2022/blob/main/day13/app.tt" target="_blank">day 13 solution</a>:</p>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>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</code></pre>
<p style="text-align: left;">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):</p><ol style="text-align: left;"><li> When the left value is a number and the right value, which can be anything, is a number less than the left, emit 1</li><li>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</li><li>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</li><li>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</li><li>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.</li><li>If both values are lists, and only the right is empty, emit a 1</li><li>If instead only the left list is empty, emit -1</li><li>If both lists are empty, emit 0</li><li>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.</li></ol><p>Compare with the day 13 problem description:</p><p>When comparing two values, the first value is called <i>left</i> and the second value is called <i>right</i>. Then:</p>
<ul><li>If <i>both values are integers</i>, the <i>lower integer</i>
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.</li><li>If <i>both values are lists</i>, 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.</li><li>If <i>exactly one value is an integer</i>, convert the integer to a
list which contains that integer as its only value, then retry the
comparison. For example, if comparing <code>[0,0,0]</code> and <code>2</code>, convert the right value to <code>[2]</code> (a list containing <code>2</code>); the result is then found by instead comparing <code>[0,0,0]</code> and <code>[2]</code>.</li></ul><p>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".</p><p>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 <a href="https://github.com/tobega/aoc2022/blob/main/day03/app.tt" target="_blank">the Tailspin solution</a> to <a href="https://adventofcode.com/2022/day/3" target="_blank">day 3</a>:<br /></p>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>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</code></pre>
<p>Explanation (again, knowing the language):</p><p>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.</p><p>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.</p><p>Here's how the problem was stated for part 1:</p><p>Find the item type that appears in both compartments of each rucksack. <i>What is the sum of the priorities of those item types?</i></p><p>And the description for part 2:</p><p>...within each group of three Elves, the badge is the <i>only item type carried by all three Elves</i>... Find the item type that corresponds to the badges of each three-Elf group. <i>What is the sum of the priorities of those item types?</i></p><p>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 <a href="https://github.com/tobega/aoc2022/blob/main/day17/app.tt" target="_blank">the tailspin solution</a> to <a href="https://adventofcode.com/2022/day/17" target="_blank">day 17</a>:</p>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>$(1)::length + 3 -> \(<$@Funnel.top::raw..> $ - $@Funnel.top::raw + 1 !\)
-> ..|@Funnel: { pipe: [x (1..$ -> [x 80 x]) ($@Funnel.pipe) x],
top: $ + $@Funnel.top::raw};
</code></pre>
<p>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.<br /></p><p>corresponds to the description:</p><p>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).</p><h3 style="text-align: left;">Consistency</h3><p style="text-align: left;">In a consistent notation, similar semantics are expressed in similar syntactic forms. <br /></p><div style="text-align: left;"><p>Tailspin is designed with consistency in mind:</p></div><div style="text-align: left;"><ul style="text-align: left;"><li><p>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 "<span style="font-family: courier;">end</span>".</p></li><li><p>Angle brackets "<span style="font-family: courier;"><></span>" 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.</p></li><li><p>Square brackets "<span style="font-family: courier;">[]</span>" signify creation of a list/array. If it has an x, "<span style="font-family: courier;">[x</span>" and "<span style="font-family: courier;">x]</span>", it is a byte array. A possible inconsistency is the use of "<span style="font-family: courier;">\[i]( \)</span>" 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 "<span style="font-family: courier;">\[i ( )\]</span>"?</p></li><li><p>Curly braces signify a set, "<span style="font-family: courier;">{</span>" and "<span style="font-family: courier;">}</span>" for a set of keys with attached values (a.k.a. a structure), "<span style="font-family: courier;">{|</span>" and "<span style="font-family: courier;">|}</span>" for a set of structures with the same keys (a.k.a. a relation).</p></li><li><p>"<span style="font-family: courier;">..</span>" 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. </p></li></ul><p>Parentheses "<span style="font-family: courier;">()</span>" 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 "<span style="font-family: courier;">\(</span>" and "<span style="font-family: courier;">\)</span>" 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 "<span style="font-family: courier;">?( )</span>". It is not clear if this inconsistency is confusing or not.</p></div><div style="text-align: left;"><p>Another inconsistency is perhaps that both "<span style="font-family: courier;">$struct.field</span>" and "<span style="font-family: courier;">$struct(field:)</span>" yield the same value. On the other hand, "<span style="font-family: courier;">$struct({field:})</span>" gives a structure containing the field, which is consistent with "<span style="font-family: courier;">$arr([5])</span>" giving an array consisting of the fifth element while "<span style="font-family: courier;">$arr(5)</span>" gives just the fifth element. Could it be confusing that "<span style="font-family: courier;">$arr(5..5)</span>" 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.</p><h3 style="text-align: left;">Diffuseness</h3><p style="text-align: left;">The verbosity of the language.</p><p style="text-align: left;">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.</p><p style="text-align: left;">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).</p><p style="text-align: left;">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 "<span style="font-family: courier;">when</span>" and "<span style="font-family: courier;">do</span>", which seems to increase readability.</p><p style="text-align: left;">Another example of the syntax being too terse is possibly "<span style="font-family: courier;"><5..></span>" vs "<span style="font-family: courier;"><..5></span>" 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.</p><h3 style="text-align: left;">Error-proneness</h3><p style="text-align: left;">This concerns whether the notation itself invites certain types of systematic mistakes. <br /></p><p style="text-align: left;">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.</p><h3 style="text-align: left;">Hard mental operations</h3><p style="text-align: left;">Does the language sometimes put a high demand on cognitive resources?<br /></p><p style="text-align: left;">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.</p><h3 style="text-align: left;">Progressive evaluation</h3><p style="text-align: left;">This dimension explores whether it is possible to evaluate incomplete work.</p><p style="text-align: left;">I have written an <a href="http://tobega.blogspot.com/2020/05/a-little-tailspin.html" target="_blank">article that demonstrates progressive evaluation in Tailspin</a>. It is very easy and a favourite technique of mine.</p><p style="text-align: left;">Another little trick is to insert "<span style="font-family: courier;">\($ -> !OUT::write $! \)</span>" as an extra stage in a pipeline to see what the current value is at that point.</p><p style="text-align: left;">Tests can also be used to evaluate parts of programs.</p><h3 style="text-align: left;">Provisionality</h3><p style="text-align: left;">How committed are you to things already written?</p><p style="text-align: left;">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. "<span style="font-family: courier;">$ -> {foo: 1, bar: 'qux'} -> my_current_focus</span>" and change it later.</p><h3 style="text-align: left;">Role-expressiveness</h3><p style="text-align: left;">Can the purpose of a component (or an action or a symbol) be readily inferred?</p><p style="text-align: left;">Most of the things mentioned under "visibility" perhaps belong here instead. Also the things mentioned under "consistency".</p><p style="text-align: left;">I'd like to highlight the use of sigils in Tailspin. A "<span style="font-family: courier;">$</span>" always means a value is being brought into play, while a "<span style="font-family: courier;">!</span>" means a value is being sent out of scope and lack of a sigil means a transform is applied. Also, an "<span style="font-family: courier;">@</span>" 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 "<span style="font-family: courier;">::</span>".</p><h2 style="text-align: left;">Final thoughts</h2><p style="text-align: left;">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.</p><p style="text-align: left;"><br /></p></div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-86027958314266167152021-08-21T06:13:00.002-07:002021-10-05T02:13:54.180-07:00Write meaningful unit tests<div><p><a href="https://cygni.se/write-meaningful-unit-tests/">This article has moved</a></p></div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-50408064793770850552021-05-28T12:44:00.000-07:002021-05-28T12:44:51.016-07:00The power of nothing<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
<p>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.</p>
<p>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, <a href="https://justabloginthepark.com/2015/10/28/f-sharp-vs-clojure-toy-problem-shootout/">F Sharp vs Clojure Toy Problem Shootout</a>.</p>
<p>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.</p>
<p>The <a href="https://github.com/tobega/tailspin-v0">Tailspin programming language</a> 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:</p>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
templates findAllTreasurePaths
when <='dailyprogrammer'> do [] !
when <[]> do $ -> \[i]($ -> findAllTreasurePaths -> [$i - 1, $...] ! \)... !
when <{}> do $... -> \(def key: $::key; $::value -> findAllTreasurePaths -> [$key, $...] ! \)!
end findAllTreasurePaths
</code></pre>
<p>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.</p>
<p> 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.</p>
<p>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:</p>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
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
</code></pre>
<p>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.</p>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com3tag:blogger.com,1999:blog-7677021887363364182.post-5946146480695712712021-05-02T02:33:00.016-07:002022-03-04T00:33:30.071-08:00Learning Tailspin by comparing to Javascript<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
<p>Since the <a href="https://github.com/tobega/tailspin-v0" target="_blank">Tailspin programming language</a> is a little different syntaxwise from most programming languages, I recently got a suggestion to put Tailspin code examples next to some well-known language. So with some help from <a href="https://rosettacode.org/wiki/Rosetta_Code" target="_blank">Rosettacode</a>, here goes, Javascript on the left vs Tailspin on the right, with logic as similar as is reasonable. Note that the syntax-highlighting algorithm doesn't really know Tailspin so sometimes it may mislead.</p>
<p><i>To begin with, you should probably try to forget everything you think you know about programming language syntax, Tailspin is very different.</i></p>
<h3 style="text-align: left;">Hello World</h3>
<p><i>Tailspin uses an arrow -> to denote that the value created on the left is input to the transform on the right. This is similar to the "pipe" operation in shell-script programming. You can also think that the arrow corresponds to something like ".map" or ".forEach" in javascript. Note also that the bang ('!') in Tailspin shows where a value disappears, so the chain stops after the value has been sent with the write-message to OUT.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
console.log("Hello world!")
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
'Hello world!' -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Simple math</h3>
<p><i>Tailspin uses a dollar-sign to denote when you source a value, e.g. from a defined symbol. Note also the round parentheses used for array indexing and that indexes start at 1.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
const a = 2;
const b = 3;
const c = [1, 6];
console.log(a + b + c[0] - c[1])
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
def a: 2;
def b: 3;
def c: [1, 6];
$a + $b + $c(1) - $c(2) -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">A+B</h3>
<p>Add two numbers given on an input line. Note that the javascript version would handle more than two numbers on the line.</p>
<p><i>Tailspin comes with a built-in PEG-like parser syntax, used inside a "composer". Things within angle brackets, '<' and '>', are matchers, here the built-in WS for whitespace and INT that produces an integer. So here we match a string with two integers, discarding whitespace around them, and output as an array (of two integers). After parsing, we add the first and second elements of the array together. The $ without a name refers to the current value being handled (here first as the array produced by nums, and in the next step it is the produced sum that is interpolated into the string to append a line break).
Note also the $ in front of IN, the $ denotes a source, a place where a value (or several values) appears, here as a result of sending the readline-message to IN.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
process.stdin.on("data", buffer => {
console.log(
(buffer + "").trim().split(" ").map(Number)
.reduce((a, v) => a + v, 0)
);
});
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
composer nums
[ (<WS>?) <INT> (<WS>) <INT> (<WS>?) ]
end nums
$IN::readline -> nums -> $(1) + $(2) -> '$;
' -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">FizzBuzz</h3>
<p><i>In Tailspin, "templates" corresponds fairly well to "function", except that templates only take one input value (and can produce zero or more output values). The "when .. do" checks if the current value matches the expression inside the angle brackets and if so, executes the following code up to the next when case (remember, angle brackets are always around matchers, although these matchers are slightly different from matchers in a composer in that they can match other things than strings). The "otherwise" statement is executed if no "when" matches. To emit a value (similar to a "return", but processing can continue afterwards), you use a lone bang ('!') which also ends that value stream by "disappearing" the value into the calling context. The "\(" to "\)" section is an anonymous inline templates (a lambda, essentially, the backslash looks a bit like a lambda-sign if you squint). There is no for-loop in Tailspin, we simply create a stream of the integers 1 to 100, inclusive. Note how the string interpolation of a value starts with a $ and ends with a semi-colon (';') and remember that a lone $ refers to the current value.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
var fizzBuzz = function (i) {
function fizz(i) {
return !(i % 3) ? 'Fizz' : '';
};
function buzz(i) {
return !(i % 5) ? 'Buzz' : '';
};
return `${fizz(i)}${buzz(i)}` || i;
};
for (var i = 1; i < 101; i += 1) {
console.log(fizzBuzz(i));
}
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
templates fizzBuzz
templates fizz
when <?($ mod 3 <=0>)> do 'Fizz'!
end fizz
templates buzz
when <?($ mod 5 <=0>)> do 'Buzz'!
end buzz
def i: $;
'$->fizz;$->buzz;'
-> \(when <=''> do $i! otherwise $! \) !
end fizzBuzz
1..100 -> '$->fizzBuzz;
' -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Fibonacci</h3>
<p>Return the nth fibonacci number.</p>
<p><i>In Tailspin, the only values that can be modified are the @-values that live inside a templates. The pound sign ('#') denotes that the value should be matched against the matchers (the when-statements). To repeat, we send a new value back to be matched. Note that the "<0~..>" matcher matches a value strictly greater than zero.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
function fib(n) {
var a = 0, b = 1, t;
while (n-- > 0) {
t = a;
a = b;
b += t;
}
return a;
}
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
templates nthFibonacci
@: {a: 0, b: 1};
$ -> #
when <0~..> do
@: {a: $@.b, b: $@.a + $@.b};
$ - 1 -> #
otherwise $@.a!
end nthFibonacci
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Matrix multiplication</h3>
<p>The Javascript version has been written to mirror the Tailspin version, though it would probably naturally be written slightly differently. The A-matrix is used as a template for the rows of the output, while the first row of the B-matrix is used as a template for the columns of the output.</p>
<p><i>We can define binary (two-argument) operators in Tailspin. Note also the "\[i](" construct where backslash is the start of an inline function definition (a lambda), which ends at "\)". The i inside the square brackets says that the lambda should apply to each element of an array and that the index should be provided as the defined symbol 'i'. The result is still an array, but with each element replaced with the result of the lambda.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
matmul = function(A, B) {
return A.map((_r, i) => {
return B[0].map(_c, j) => {
var cell = 0;
for (var k = 0; k < B.length; k++) {
cell += A[i][k] * B[k][j];
}
return cell;
});
});
}
const a = [[1,2],[3,4]];
const b = [[-3,-8,3],[-2,1,4]];
print(matmul(a,b));
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
operator (A matmul B)
$A -> \[i](
$B(1) -> \[j](
@: 0;
1..$B::length -> @: $@ + $A($i;$) * $B($;$j);
$@ !
\) !
\) !
end matmul
def a: [[1,2],[3,4]];
def b: [[-3,-8,3],[-2,1,4]];
($a matmul $b) -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Reverse words in a string</h3>
<p>In the Tailspin version we keep the whitespace between the words while the Javascript removes it and replaces it.
The Tailspin input is also already divided into lines.</p>
<p><i>The ellipsis ('...') streams out the individual elements of the array. The tilde ('~') denotes inverse, or "not", in Tailspin. The composer produces an array of word-productions, where the word rule in turn produces a sequence of non-whitespace characters followed by an optional sequence of whitespace characters. The two sequences (strings) produced are just separate strings in the resulting array on the same level as the other strings.
Note also how we can select a sequence of elements from an array, with an optional stride, in this case we take all elements in reverse order, by "$(last..first:-1)".</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
const input =
"---------- Ice and Fire ------------\n\
\n\
fire, in end will world the say Some\n\
ice. in say Some\n\
desire of tasted I've what From\n\
fire. favor who those with hold I\n\
\n\
... elided paragraph last ...\n\
\n\
Frost Robert -----------------------";
function reverseString(s) {
return s.split('\n').map(
function (line) {
return line.split(/\s/).reverse().join(' ');
}
).join('\n');
}
console.log(
reverseString(input)
);
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
def input: ['---------- Ice and Fire ------------',
'',
'fire, in end will world the say Some',
'ice. in say Some',
'desire of tasted I''ve what From',
'fire. favor who those with hold I',
'',
'... elided paragraph last ...',
'',
'Frost Robert -----------------------']
;
composer words
[ <word>* ]
rule word: <~WS> <WS>?
end words
$input... -> '$ -> words -> $(last..first:-1)...;
' -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Water collected between towers</h3>
<p>Fill a "skyline" with water, so the input [1, 5, 3, 7, 2] will result in a total of two units of water held above the 3. For a better description and interesting links, <a href="https://rosettacode.org/wiki/Water_collected_between_towers" target="_blank">see the rosetta code page for this problem</a>.</p>
<p>The chosen algorithm goes first from left to right to find the height of the left containing wall, then from right to left to see how high the water level can be at that point. The Javascript is written to match the Tailspin as closely as possible.</p>
<p><i>Here we mostly put stuff together into a more complex algorithm. The matchers with the dots in are range matchers, so "<$val..>" matches a value greater than or equal to "val", while a tilde acts to exclude the value, so "<$val~..>" matches a value strictly greater than "val". The array is reversed as we did in the previous example and then we stream the elements out individually (by '...') and send them to the matchers (by '#').</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
function histogramWater(a) {
var leftMax = 0;
return a.map((h) => {
if (h > leftMax) {
leftMax = h;
}
return { leftMax: leftMax, value: h };
}).reduceRight((acc, point) => {
if (point.value >= acc.rightMax) {
acc.rightMax = point.value;
} else if (point.value >= point.leftMax) {
// do nothing
} else if (point.leftMax <= acc.rightMax) {
acc.sum += point.leftMax - point.value;
} else {
acc.sum += acc.rightMax - point.value;
}
return acc;
}, {rightMax: 0, sum: 0}).sum;
}
console.log(histogramWater([1, 5, 3, 7, 2]));
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
templates histogramWater
$ -> \( @: 0;
[$... -> { leftMax: $ -> #, value: $ } ] !
when <$@~..> do @: $; $ !
otherwise $@ !
\) -> \( @: { rightMax: 0, sum: 0 };
$(last..1:-1)... -> #
$@.sum !
when <{ value: <$@.rightMax..> }> do @.rightMax: $.value;
when <{ value: <$.leftMax..> }> do !VOID
when <{ leftMax: <..$@.rightMax>}> do
@.sum: $@.sum + $.leftMax - $.value;
otherwise
@.sum: $@.sum + $@.rightMax - $.value;
\) !
end histogramWater
[1, 5, 3, 7, 2] -> histogramWater -> !OUT::write
</code></pre>
</div>
</div>
<h3 style="text-align: left;">Range expansion</h3>
<p>A string with compressed ranges is to be expanded into a list of integers, e.g. "-6,-3-1,3-5,7-11,14,15,17-20" will expand to [-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]
</p><p>Tailspin has a built-in PEG-like parser syntax which is THE way to do string manipulation. You could use a PEG library in Javascript, but normally you soldier on with primitive string handling.</p>
<p><i>Here we produce an array of zero or more elements. The element rule will either be a range or an integer, optionally followed by a comma that is ignored. If it is a range, it will be an integer that is captured into the definition of the "start" symbol, followed by a dash that is ignored, then another integer which is sent on to produce a stream of integers from start to the current value, inclusive.</i></p>
<div style="display: flex; justify-content: space-evenly;">
<div><h4>Javascript</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
function rangeExpand(rangeExpr) {
function getFactors(term) {
var matches = term.match(/(-?[0-9]+)-(-?[0-9]+)/);
if (!matches) return {first:Number(term)};
return {first:Number(matches[1]), last:Number(matches[2])};
}
function expandTerm(term) {
var factors = getFactors(term);
if (factors.length < 2) return [factors.first];
var range = [];
for (var n = factors.first; n <= factors.last; n++) {
range.push(n);
}
return range;
}
var result = [];
var terms = rangeExpr.split(/,/);
for (var t in terms) {
result = result.concat(expandTerm(terms[t]));
}
return result;
}
console.log(rangeExpand('-6,-3--1,3-5,7-11,14,15,17-20'));
</code></pre>
</div>
<div><h4>Tailspin</h4>
<pre class="prettyprint" style="border: 1px solid black; padding: 2em;"><code>
composer expand
[<element>*]
rule element: <range|INT> (<=','>?)
rule range: (def start: <INT>; <='-'>) <INT> -> $start..$
end expand
'-6,-3--1,3-5,7-11,14,15,17-20' -> expand -> !OUT::write
</code></pre>
</div>
</div>
Hopefully you now have a sense for how the basic syntax of Tailspin works so that you can better understand more complex code examples.
<p></p>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-72162606190172215802020-05-17T11:03:00.009-07:002022-05-29T23:27:33.728-07:00Creating an algorithm (Dart code)<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
<br />
<div>
NOTE: This article is exactly the same as my <a href="http://tobega.blogspot.com/2020/05/creating-algorithm.html">previous article</a> except the code example here is in Dart instead of Tailspin and therefore I also made some different implementation choices and the TDD flow ended up being a bit different. If you just want to see the code or TDD-process in this article, <a href="https://cygnigroup.com/creating-an-algorithm/#thecode">skip to it</a>.</div>
<div class="post-content inner">
<!--kg-card-begin: markdown--><p>"How do you create an algorithm?" is a question i saw on Quora recently and it started me thinking. What are the steps I follow and could there be something that someone could learn from that? Since I've been wanting to write a sudoku solver just for fun, I decided to write up the process.</p>
<p>Interestingly, the task of writing a sudoku solver has been the subject of <a href="https://web.archive.org/web/20210615182756/http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html">debate previously</a>. That debate was about the limitations of TDD and might be well worth reading. I am a big fan of TDD and would add my vote to those who claim that it helps you develop faster and more fearlessly, when done right. But when done wrong, it probably can slow you down and prevent you from doing the right thing.</p>
<p>Now I don't want to get into a long discussion about TDD, but there is one thing I want to point out: tests are mainly about verifying your assumptions. A failing test verifies your assumption about what was wrong with the code. A failing test that starts passing verifies that the code you just wrote fixes the problem. An automated unit test that you run regularly verifies your assumption that "this change couldn't possibly affect that code". I've previously written about how assumptions slowed me down <a href="https://web.archive.org/web/20210615182756/https://tobega.blogspot.com/2011/01/your-assumptions-are-dangerous-you-know.html">here</a> and <a href="https://web.archive.org/web/20210615182756/https://tobega.blogspot.com/2011/01/prove-your-assumptions-but-remember.html">here</a>. So for effective testing, make sure your tests verify assumptions about the code. If you're only verifying that the code was written in a specific way (easy to do with mocks), you should probably re-assess the usefulness of the test. Even with tests, don't forget to <a href="https://web.archive.org/web/20210615182756/https://tobega.blogspot.com/2009/08/clarity-of-code-is-clarity-of-thought.html">make the code readable</a>, and do code reviews, pair programming or mob programming according to your preference. (If you do want to read a longer recent post on TDD, I suggest <a href="https://web.archive.org/web/20210615182756/https://ronjeffries.com/articles/020-01ff/what-tdd-is-like/">this one</a>).</p>
<p>OK, when creating an algorithm we must first make sure we understand the problem and the requirements, so if you don't know sudoku, <a href="https://web.archive.org/web/20210615182756/https://en.wikipedia.org/wiki/Sudoku">go read up on it</a>.</p>
<p>Now we can start thinking about how we would go about solving it. The easiest solution would be to just type up the rules in some constraint solver software or programming language <a href="https://web.archive.org/web/20210615182756/https://www.metalevel.at/sudoku/">like Prolog</a>. But that kind of programming is a very different mindset and it might be hard to switch to even if using a language like <a href="https://web.archive.org/web/20210615182756/http://shenlanguage.org/">Shen</a> or <a href="https://web.archive.org/web/20210615182756/https://en.wikipedia.org/wiki/Curry_(programming_language)">Curry</a> that has it built-in, so I'm not doing that.</p>
<p>What else do we know or can decide? I'm pretty sure I want to input the problem as text something like this:</p>
<pre><code>534|678|912
672|195|348
198|342|567
-----------
859|761|423
426|853|791
713|924|856
-----------
961|537|284
287|419|635
345|286|179
</code></pre>
<p>with '.' for unknowns, and output it the same way. Maybe I'll allow more versions for the input, adding whitespace, ignoring lines, zeroes instead of dots. I don't think I need to explore any variations here. I can think of at least wanting to test one known sudoku puzzle as an acceptance test that I am done. I might also want to test edge cases like inputting an already solved puzzle and inputting a puzzle with all unknowns. So should I go ahead and write these tests? The problem is that I cannot make them pass immediately, so running them all the time is going to introduce noise into the process with these expected failing tests. On the other hand, I am thinking about it now, so it would be good to capture that thinking. I'm pretty sure that my assumption is correct that my code won't work right now, I don't need a failing test, so I'll just write a TODO for now.</p>
<p>So what about writing the input and output code? No! One of the biggest problems in the software industry, even inside Google, is that programmers are too quick to start writing code, which means there's just more and more code solving the wrong problem or solving it the wrong way and then you leave it to someone else to clean up. We are not ready to make a quick decision on what the internal data structure is going to be as that is directly interacting with our algorithm. A premature bad choice is going to throw a big spanner in the works.</p>
<p>What ideas do we have for how we will find the solution?</p>
<ul>
<li>We could try to do it like humans do, with different heuristics like "if two positions both need one of the same two values, then either of those values cannot be assigned to a third position". This seems like it might be complicated and we can't be sure we have all the needed heuristics. Also unclear what data structure would best support the algorithm.</li>
<li>We could just store the placed digits and open spaces in a mutable array, much like our input format, and try each value in each open position and check for validity. The good thing about this is that we can easily try the states in order because we can reverse each decision easily, just replace the last placed digit with a '.' and backtrack. The bad thing is that we probably won't finish until the end of the universe, with about 9^50 possibilities (with 31 givens). We might still be ok if we check for consistency after placing each digit, but it seems likely we won't be reducing the search space fast enough, with too many high multipliers at the beginning of the search.</li>
<li>What if we kept track of the remaining possibilities in each open position and always selected the one with the fewest alternatives to try? That should keep the multiplicative combinatorial explosion down. This sounds promising and there are some data structure options, but before exploring those, let's see if we have any more ideas about how to solve the problem.</li>
<li>Another idea could be to try and fill out all occurrences of a digit before moving on to the next, but that just seems like a variation of the previous with unclear benefits. It's a possible extension if needed. I can't think of any way to generate look-up tables or otherwise speed things up. No other approaches come to mind right now.</li>
</ul>
<p>OK, so, keeping track of remaining possibilities we could store the state as an array with each cell containing either a placed digit or a list of possibilities. Since we want to search for the open position with fewest options, it might be more efficient to keep a list of just the open positions separate from a list or array of placed digits. For faster access to each open position we could even key them into a map/dict. But do we need it?</p>
<p>Thinking more about how we will move forward and backtrack (undoing choices that didn't work) through potential solutions, it seems easiest to just copy the new state for the next step. If we're copying all the state anyway, we may as well just go with the simpler array option.</p>
<p>Almost ready to code! What shall we do about the initial input state? Shall we represent the given digits as already placed and work out what the remaining options for the open positions are? Or shall we represent the given digits as open positions with one remaining possibility, setting the open positions to have all possibilities remaining, and then just run it through the same algorithm all the way? The second option seems to be a slam-dunk so we don't get two pieces of code interpreting the same rules.</p>
<p>If this code has to be part of a large code base, we would also have to study the structure of the code base so we can add the code in a good place. Don't just add code at the first place it could work, that will just start to accumulate a mess, usually at the edge of the system.</p>
<p>Now we need to choose how we want to drive the tests, either through the text input described above or with the internal representation. Since it isn't too hard to create an internal representation in my chosen language and I think it might be easier to verify properties of the internal output, I will drive it internally, then separately drive the text conversion and add an integration test at the end.</p>
<h2 id="thecode">The code</h2>
<p>Right, let's code! I will be using Dart for this example. If you know Java or Javascript or anything similar you should be able to follow along. If you feel you want an intro to Dart, <a href="https://web.archive.org/web/20210615182756/https://codelabs.developers.google.com/codelabs/from-java-to-dart/">try this</a>.</p>
<p>I first want to add a test for when the puzzle is complete, or when there are no more choices to be made. Since I'm not entirely thrilled about working too much with two-dimensional arrays (or lists of lists) in Dart, I think I will use a list of open positions as my internal input format and return a two-dimensional array with the solution.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/8b28992f4958c794f0a4955392d0136b.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/5fe1634b24c609b6e702c372fa9eaeb5.js"></script>
<p>The minimal implementation passes and I add a test that the last remaining digit gets placed, with the minimal code to make it compile (failing to compile is a failing test, but that has a bit quicker turnaround):</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/81c7d9cd300157b06de8e1570330136c.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/d53f085487faf36193f5472736af8dcf.js"></script>
<p>Which fails, as expected:</p>
<pre>
00:03 +1 -1: internal solver last digit gets placed [E]
Expected: satisfies function
Actual: [
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
...
</pre>
<p>The following code makes the test pass:</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/47c3b14886d4ec71db5a1b77c6aaf80c.js"></script>
<p>You may have noticed that my code is flawed. I should have made a deep copy of "remaining" before passing it on, as should become clear soon. Today I think of it, but other days I might not, that's how it goes when values are mutable. I deliberately choose not to fix this now because my tests should force me to do it (let's see if they do!).</p>
<p>Another thing you may notice is that I do more than the test requires by selecting the position with least options. On a day when I'm the best version of myself, I might play a game of trying to outsmart the tests to force myself to specify things better, e.g. by just selecting the first open position. Not today.</p>
<p>Still oblivious and proceeding in a good rhythm, I add tests for propagating constraints in rows, columns and blocks, one at a time with the corresponding code that makes them pass.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/098bdcea26ca8d7e310b1dad3fdd1a69.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/32a829e9387b76ffb5ff21e982429ecc.js"></script>
<p>One thing you may have noticed is that my test data would never come up in a real run of the program because there would be more constraints working together. The test depends on the knowledge that my algorithm doesn't care about those other constraints. It could be a risk to depend on knowledge about the algorithm in the tests, but it's worth it for having tests that are much simpler and easier to understand. I've carefully chosen to make the middle digit be alone (first pick) in the test cases to reduce my knowledge of the inner workings, so that whether the code picks the first or the last option of many I should discover whether the constraints are propagated or not.</p>
<p>The next test depends even more on knowledge of the inner workings, but again I prefer that the test is simpler. I add a comment about it because my reasoning is perhaps not immediately obvious. At least I am still mostly testing assumptions about results of the code and not how the code is written. Just note that it's a slippery slope.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/287770035dfada21262330d612f8f099.js"></script>
<p>The test fails with an exception "Bad state: No element" and I realize that I haven't handled the simple case where there are no options for an open position, so I comment out the failing test and deal with that first.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/8742099d8c639566d92c1a77639c8039.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/bfbdaefd1f9ddc3217f67b95483d2824.js"></script>
<p>Going back to the backtracking test, it now returns null and fails, as expected since we hit the contradiction and don't make another choice. I decide I need to restructure the code quite a bit, still just mutating objects.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/b8b3ad4edfbdfbced15c29823610c1a2.js"></script>
<p>Running the test gives a very strange result that I'm not sure I understand.</p>
<pre>
00:02 +6 -1: internal solver contradiction is backtracked [E]
Expected: (satisfies function and satisfies function and satisfies function and satisfies function)
Actual: [
['3', '6', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
...
</pre>
<p>Thinking really hard, I realize it is because I remove the best open positions from the same "remaining" array, so when we backtracked and try to place '3' and then '6', the "remaining" array is empty and the algorithm returns a solution. I obviously need to copy the remaining array before the recursive call.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/acf0d1f5243a13d7156885501898a037.js"></script>
<p>Well, that did something, we're back to failing with a null (no solution found). Of course, I need to copy the OpenPosition objects as well so that each backtrack has the right options available!</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/2ed3fd396786d75aa0be6e91da6daa9a.js"></script>
<p>Great, that works! Now I am quite confident that this will solve a sudoku. We just have to transform the input into internal form. Adding a new function to parse the input and the corresponding test for it (run the failing test first, of course!).</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/52ce47916244e617fb6e87917d367ca5.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/5151858c08d4f5e9afd8ec7a27ae8d94.js"></script>
<p>I was sure that would work, but I only get 77 elements, I'll have to re-examine my assumptions. When I check the "digits" list, I see that it contains '0'-'8', not '1'-'9'. Doh! There are 4 nines in the input, so that should cover it.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/02bf797f610c6181d8d87cfa65f7e44c.js"></script>
<p>I add a few more assertions to verify the parsed input, which all pass.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/26d8e42cb3e8b9e63ba5046eb03cad97.js"></script>
<p>Excellent! Now we just need to put it all together and I write the test I deferred at the beginning of this article. The printing code takes a bit of thought but I decide that I can easily distinguish errors in printing from errors in solving so I don't need a separate test right now.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/f80a3173edb5e0f9fb3c2454b602e900.js"></script>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/671803a01f5f7de2b24b68eb5000cf4a.js"></script>
<p>Surprisingly, I get 'No solution found'. What is going wrong here? I take a look at the code and have the idea that perhaps "choices.toList()" does not create a new list. So I add a check and run again.</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/bc97376a864d74ae08a7532114a03ba3.js"></script>
<p>That doesn't seem to be the problem though, I have to go deeper. I add a test to see what happens if I input an already solved sudoku. That also fails to find a solution. I double-check that it is a valid sudoku. WAT? I'm about to start extending the tests for rows, columns and blocks, when it jumps out at me from the constraint propagation code:</p>
<script src="https://web.archive.org/web/20210615182756js_/https://gist.github.com/wassgren/d79bc1507848f6d8d3050bd42599dac9.js"></script>
<p>I remove that line and verify that the block-filling test fails. It does, but I see from the test output that I had placed the block in the top left corner, which has the same x and y coordinates, a bad choice for a test that depends on both x and y. So I change that test to be three rows further down, verify it still fails and that putting back the removed code line still fails until I correct it.</p>
<p>That does the trick, but now I get a type error on my full solution " type 'MappedListIterable<List<string>, String>' is not a subtype of type 'List<string>'". I have to do a websearch for that and it seems that the error is that the compile-time type-checking isn't quite working here. When I create the "rows" variable I just do a "map" operation, but that does not return a List, so I have to append ".toList()".</p>
<p>That was a bit sweaty, but now it works, apart from a newline missing from the end. I correct that, and I look over my code to see if I can clean it up a bit, e.g. some names need changing or code can be rephrased clearer. You can see the final result <a href="https://web.archive.org/web/20210615182756/https://github.com/tobega/aoc2018/tree/master/sudoku-example">here</a>.</p>
<!--kg-card-end: markdown--><!--kg-card-begin: markdown--><h2 id="summaryoftheprocess">Summary of the process</h2>
<ol>
<li>Don't start coding until you understand the problem.</li>
<li>Don't start coding until you understand well enough how you are going to solve it
<ul>
<li>Explore various possibilities and evaluate</li>
<li>Choose the simplest solution that is good enough</li>
<li>If you cannot decide, ask yourself what information will help you decide and go find that out.</li>
<li>Don't get stuck, flip a coin if you have to. If it turns out bad you will have learned something along the way.</li>
</ul>
</li>
<li>Don't start coding until you know how the new code will fit into existing code, don't just add it the first place you think it might work. Refactor existing code to create a good fit, if needed.</li>
<li>Use tests to validate (or disprove) your assumptions.
<ul>
<li>A failing test validates your assumption about what your code does not yet do correctly.</li>
<li>A failing test that starts to pass validates your assumption that the code you wrote actually does something useful.</li>
<li>An automated unit test that is kept and run periodically tests your assumption that "this code couldn't possibly break that code".</li>
</ul>
</li>
<li>When you don't fully understand how your tools work, you need to explore, observe and test your assumptions about them. Just don't confuse exploratory coding with production coding, you still need to validate that you can't simplify the experimental code.</li>
<li>When everything works, make sure your code is easy to read and understand and clean up whatever can be cleaned up. Another pair of eyes is good here, do code reviews or pair or mob programming.</li>
</ol></div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-27090327884928495632020-05-15T01:41:00.006-07:002020-09-01T06:20:32.017-07:00Creating an algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>UPDATE: This article has been re-published with a code example in Dart instead of Tailspin <a href="http://tobega.blogspot.com/2020/05/creating-algorithm-dart-code.html">here</a>. The choices made and the TDD process ended up somewhat different so it may be worth looking at both. If you just want to see the code or the TDD process in this post, you can <a href="http://tobega.blogspot.com/2020/05/creating-algorithm.html#code">skip to it</a>.<br />
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<div dir="ltr" style="text-align: left;" trbidi="on">
"How do you create an algorithm?" is a question i saw on Quora recently and it started me thinking. What are the steps I follow and could there be something that someone could learn from that? Since I've been wanting to write a sudoku solver just for fun, I decided to write up the process.<br />
<div>
<br /></div>
<div>
If you're in a hurry, jump to the <a href="http://tobega.blogspot.com/2020/05/creating-algorithm.html#summary">summary at the end</a>.<br />
<div>
<br /></div>
<div>
Interestingly, the task of writing a sudoku solver has been the subject of <a href="http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html">debate previously</a>. That debate was about the limitations of TDD and might be well worth reading. I am a big fan of TDD and would add my vote to those who claim that it helps you develop faster and more fearlessly, when done right. But when done wrong, it probably can slow you down and prevent you from doing the right thing.</div>
<div>
<br /></div>
<div>
Now I don't want to get into a long discussion about TDD, but there is one thing I want to point out: tests are mainly about verifying your assumptions. A failing test verifies your assumption about what was wrong with the code. A failing test that starts passing verifies that the code you just wrote fixes the problem. An automated unit test that you run regularly verifies your assumption that "this change couldn't possibly affect that code". I've previously written about how assumptions slowed me down <a href="https://tobega.blogspot.com/2011/01/your-assumptions-are-dangerous-you-know.html">here</a> and <a href="https://tobega.blogspot.com/2011/01/prove-your-assumptions-but-remember.html">here</a>. So for effective testing, make sure your tests verify assumptions about the code. If you're only verifying that the code was written in a specific way (easy to do with mocks), you should probably re-assess the usefulness of the test. Even with tests, don't forget to <a href="https://tobega.blogspot.com/2009/08/clarity-of-code-is-clarity-of-thought.html">make the code readable</a>, and do code reviews, pair programming or mob programming according to your preference. (If you do want to read a longer recent post on TDD, I suggest <a href="https://ronjeffries.com/articles/020-01ff/what-tdd-is-like/">this one</a>).</div>
<div>
<br /></div>
<div>
OK, when creating an algorithm we must first make sure we understand the problem and the requirements, so if you don't know sudoku, <a href="https://en.wikipedia.org/wiki/Sudoku">go read up on it</a>.</div>
<div>
<br /></div>
<div>
Now we can start thinking about how we would go about solving it. The easiest solution would be to just type up the rules in some constraint solver software or programming language <a href="https://www.metalevel.at/sudoku/">like Prolog</a>. But that kind of programming is a very different mindset and it might be hard to switch to even if using a language like <a href="http://shenlanguage.org/">Shen</a> or <a href="https://en.wikipedia.org/wiki/Curry_(programming_language)">Curry</a> that has it built-in, so I'm not doing that.</div>
<div>
<br /></div>
<div>
What else do we know or can decide? I'm pretty sure I want to input the problem as text something like this:</div>
<pre class="prettyprint"><code>534|678|912
672|195|348
198|342|567
-----------
859|761|423
426|853|791
713|924|856
-----------
961|537|284
287|419|635
345|286|179
</code></pre>
<div>
with '.' for unknowns, and output it the same way. Maybe I'll allow more versions for the input, adding whitespace, ignoring lines, zeroes instead of dots. I don't think I need to explore any variations here. I can think of at least wanting to test one known sudoku puzzle as an acceptance test that I am done. I might also want to test edge cases like inputting an already solved puzzle and inputting a puzzle with all unknowns. So should I go ahead and write these tests? The problem is that I cannot make them pass immediately, so running them all the time is going to introduce noise into the process with these expected failing tests. On the other hand, I am thinking about it now, so it would be good to capture that thinking. I'm pretty sure that my assumption is correct that my code won't work right now, I don't need a failing test, so I'll just write a TODO for now.</div>
<div>
<br /></div>
<div>
So what about writing the input and output code? No! One of the biggest problems in the software industry, even inside Google, is that programmers are too quick to start writing code, which means there's just more and more code solving the wrong problem or solving it the wrong way and then you leave it to someone else to clean up. We are not ready to make a quick decision on what the internal data structure is going to be as that is directly interacting with our algorithm. A premature bad choice is going to throw a big spanner in the works.</div>
<div>
<br /></div>
<div>
What ideas do we have for how we will find the solution?</div>
<div>
<ul style="text-align: left;">
<li>We could try to do it like humans do, with different heuristics like "if two positions both need one of the same two values, then either of those values cannot be assigned to a third position". This seems like it might be complicated and we can't be sure we have all the needed heuristics. Also unclear what data structure would best support the algorithm.</li>
<li>We could just store the placed digits and open spaces in a mutable array, much like our input format, and try each value in each open position and check for validity. The good thing about this is that we can easily try the states in order because we can reverse each decision easily, just replace the last placed digit with a '.' and backtrack. The bad thing is that we probably won't finish until the end of the universe, with about 9<sup>50</sup> possibilities (with 31 givens). We might still be ok if we check for consistency after placing each digit, but it seems likely we won't be reducing the search space fast enough, with too many high multipliers at the beginning of the search.</li>
<li>What if we kept track of the remaining possibilities in each open position and always selected the one with the fewest alternatives to try? That should keep the multiplicative combinatorial explosion down. This sounds promising and there are some data structure options, but before exploring those, let's see if we have any more ideas about how to solve the problem.</li>
<li>Another idea could be to try and fill out all occurrences of a digit before moving on to the next, but that just seems like a variation of the previous with unclear benefits. It's a possible extension if needed. I can't think of any way to generate look-up tables or otherwise speed things up. No other approaches come to mind right now.</li>
</ul>
OK, so, keeping track of remaining possibilities we could store the state as an array with each cell containing either a placed digit or a list of possibilities. Since we want to search for the open position with fewest options, it might be more efficient to keep a list of just the open positions separate from a list or array of placed digits. For faster access to each open position we could even key them into a map/dict. But do we need it?</div>
<div>
<br /></div>
<div>
Thinking more about how we will move forward and backtrack (undoing choices that didn't work) through potential solutions, it seems easiest to just copy the new state for the next step. If we're copying all the state anyway, we may as well just go with the simpler array option.</div>
<div>
<br /></div>
<div>
Almost ready to code! What shall we do about the initial input state? Shall we represent the given digits as already placed and work out what the remaining options for the open positions are? Or shall we represent the given digits as open positions with one remaining possibility, just setting the open positions to have all possibilities remaining, and then just run it through the same algorithm all the way? The second option seems to be a slam-dunk so we don't get two pieces of code interpreting the same rules.</div>
<div>
<br /></div>
<div>
If this code has to be part of a large code base, we would also have to study the structure of the code base so we can add the code in a good place. Don't just add code at the first place it could work, that will just start to accumulate a mess, usually at the edge of the system.</div>
<div>
<br /></div>
<div>
Now we just need to choose how we want to drive the tests, either through the text input described above or with the internal representation. Since it isn't too hard to create an internal representation in my chosen language and I think it might be easier to verify properties of the internal output, I will drive it internally, then separately drive the text conversion and add an integration test at the end.</div>
<div>
<br /></div>
<h2 style="text-align: left;">
<a href="https://www.blogger.com/null" id="code">The code</a></h2>
<div>
Right, let's code! I will be using my own programming language, Tailspin. If you want an intro to Tailspin, <a href="https://tobega.blogspot.com/2020/05/a-little-tailspin.html">read this</a>. First I set up a test that verifies that an already solved sudoku stays solved.</div>
<pre class="prettyprint"><code>templates placeDigit
$ !
end placeDigit
test 'internal solver'
def sample: [
[5,3,4,6,7,8,9,1,2],
[6,7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,9]
];
assert $sample -> placeDigit <=$sample> 'completed puzzle unchanged'
end 'internal solver'</code></pre>
<div>
That passes and I add a test that the last remaining digit gets placed:</div>
<pre class="prettyprint"><code>test 'internal solver'
...
assert [
[[5],3,4,6,7,8,9,1,2],
$sample(2..last)...] -> placeDigit <=$sample> 'final digit gets placed'
end 'internal solver'</code></pre>
<div>
Which fails, as expected:</div>
<pre class="prettyprint"><code>internal solver failed:
assertion that final digit gets placed failed with value [[[5], 3, 4, 6, 7, 8, 9, 1, 2], ...</code></pre>
<div>
I add a fairly large amount of code to try to pass this test, which makes me wonder if that code is fully tested. It is usually fun to play a game of trying to outsmart the tests by writing simpler code than you need, e.g. I should look for the first open position instead of the best to begin with. But I'll leave that for a day when I'm a better person.</div>
<pre class="prettyprint"><code>templates placeDigit
templates nextDigit
@:{options: 10};
$ -> \[i;j](when <[](..~$@nextDigit.options)> do @nextDigit: {row: $i, col: $j, options: $::length}; \) -> !VOID
$@ !
end nextDigit
templates set&{pos:}
$ -> \[i;j](
when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
otherwise $ !
\) !
end set
$ -> set&{pos: $ -> nextDigit} !
end placeDigit</code></pre>
<div>
Surprisingly, I get an error (I need to file a bug report to get a better diagnostic here).</div>
<pre class="prettyprint"><code>Exception in thread "main" java.lang.NullPointerException: No value defined for $pos.row</code></pre>
<div>
It turns out that I no longer handle the first case, so I have to add a check for that.</div>
<pre class="prettyprint"><code>templates placeDigit
templates nextDigit
@:{options: 10};
$ -> \[i;j](when <[](..~$@nextDigit.options)> do @nextDigit: {row: $i, col: $j, options: $::length}; \) -> !VOID
$@ !
end nextDigit
templates set&{pos:}
$ -> \[i;j](
when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
otherwise $ !
\) !
end set
<b>def given: $;
$ -> nextDigit -> #
when <{options: <=10>}> do $given !
otherwise def next: $; $given -> set&{pos: $next} !</b>
end placeDigit</code></pre>
<div>
The tests pass and I add an assert for an unsolvable puzzle that fails and then code to make it pass:</div>
<pre class="prettyprint"><code>templates placeDigit
...
def given: $;
$ -> nextDigit -> #
<b>when <{options: <=0>}> do [] !</b>
when <{options: <=10>}> do $given !
otherwise def next: $; $given -> set&{pos: $next} !
end placeDigit
test 'internal solver'
...
<b>assert [
[[],3,4,6,7,8,9,1,2],
$sample(2..last)...] -> placeDigit <=[]> 'no remaining options returns empty'</b>
end 'internal solver'</code></pre>
<div>
Proceeding in a good rhythm, I add tests for propagating constraints in rows, columns and blocks, one at a time with the corresponding code that makes them pass. I also have to make a recursive call at the end to keep solving all remaining digits.</div>
<pre class="prettyprint"><code>templates placeDigit
...
templates set&{pos:}
def digit: $($pos.row;$pos.col) -> $(1);
$ -> \[i;j](
when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
<b>when <[]?($i <=$pos.row>)> do [$... -> \(<~=$digit> $! \)] !
when <[]?($j <=$pos.col>)> do [$... -> \(<~=$digit> $! \)] !
when <[]?(($i-1)~/3 <=($pos.row-1)~/3>)?(($j-1)~/3 <=($pos.col-1)~/3>)> do [$... -> \(<~=$digit> $! \)] !</b>
otherwise $ !
\) !
end set
...
otherwise def next: $; $given -> set&{pos: $next}<b> -> placeDigit</b> !
end placeDigit
test 'internal solver'
...
assert [
[[5],3,4,6,[2,5,7],8,9,1,[2,5]],
$sample(2..last)...] -> placeDigit <=$sample> 'solves 3 digits on row'
assert [
[5,3,4,6,7,8,9,1,2],
[[6,7,9],7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[[7],1,3,9,2,4,8,5,6],
[[7,9],6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,9]
] -> placeDigit <=$sample> 'solves 3 digits on column'
assert [
[5,3,[4,6],6,7,8,9,1,2],
[[6],7,2,1,9,5,3,4,8],
[1,[4,6,9],8,3,4,2,5,6,7],
$sample(4..last)...
] -> placeDigit <=$sample> 'solves 3 digits in block'
end 'internal solver'</code></pre>
<div>
One thing you may have noticed is that my test data would never come up in a real run of the program. The test depends on the knowledge that my algorithm doesn't care about the already placed digits. It could be a risk to depend on knowledge about the algorithm in the tests, but it's worth it for having tests that are much simpler and easier to understand. I've carefully chosen to make the middle digit be alone (first pick) in the test cases to reduce my knowledge of the inner workings, so that whether the code picks the first or the last option of many I should discover whether the constraints are propagated or not.</div>
<div>
<br /></div>
<div>
The next test depends even more on knowledge of the inner workings, but again I prefer that the test is simpler. I add a comment about it because my reasoning is perhaps not immediately obvious. At least I am still mostly testing assumptions about results of the code and not how the code is written. Just note that it's a slippery slope.</div>
<pre class="prettyprint"><code> // This gives a contradiction if 3 gets chosen out of [3,5]
assert [
[[3,5],[3,4,6],[3,4,6],[3,4,6],7,8,9,1,2],
$sample(2..last)...] -> placeDigit <=$sample> 'contradiction is backtracked'
</code></pre>
<div>
The test fails, as expected.</div>
<pre class="prettyprint"><code>internal solver failed:
assertion that contradiction is backtracked failed with value []</code></pre>
<div>
Now we can't just output the result of the recursive call, we have to see if it resulted in a contradiction and, if so, remove the guess we made and make another.</div>
<pre class="prettyprint"><code>templates placeDigit
templates nextDigit
...
end nextDigit
templates set&{pos:}
...
end set
@: $;
$ -> nextDigit -> #
when <{options: <=0>}> do [] !
when <{options: <=10>}> do $@ !
<b>otherwise def next: $;
def result: $@ -> set&{pos: $next} -> placeDigit;
$result -> \(<~=[]> $! \) !
$result -> \(<=[]> $! \) -> ^@($next.row;$next.col;1) -> $@ -> nextDigit -> #</b>
end placeDigit
</code></pre>
<div>
Great, that works! Now I am quite confident that this will solve a sudoku. We just have to transform the input into internal form. Adding a new function to parse the input and the corresponding test for it (test first, of course!).
Tailspin has a special syntax called a composer for specifying the result you want with regex-matchers for snippets of the input string. So we want an array that has three sections, each consisting of three rows and optionally ended with a line of dashes that we ignore, where each row has groups of three digits optionally separated by an ignored pipe-character.</div>
<pre class="prettyprint"><code>composer parseSudoku
[<section>=3]
rule section: <row>=3 (<'-+'>? <WS>?)
rule row: [<triple>=3] (<WS>?)
rule triple: <digit|dot>=3 (<'|'>?)
rule digit: [<'\d'>]
rule dot: <'\.'> -> [1..9]
end parseSudoku
test 'input sudoku'
def parsed:
'53.|.7.|...
6..|195|...
.98|...|.67
-----------
8..|.6.|..3
4..|8.3|..1
7..|.2.|..6
-----------
.6.|...|28.
...|419|..5
...|.8.|.79' -> parseSudoku;
assert $parsed <[<[<[]>=9](9)>=9](9)> 'parsed sudoku has 9 rows containing 9 columns of lists'
end 'input sudoku'
</code></pre>
<div>
I was confident that would work, but it doesn't:</div>
<pre class="prettyprint"><code>Exception in thread "main" java.lang.IllegalStateException: No composer match at '53.|.7.|...</code></pre>
<div>
This is turning out to be more educational than I intended! Obviously I don't fully understand how this works (or I just made a mistake), but now I have to back up and check some underlying assumptions. First I'll check that the digit and dot rules are correct.</div>
<pre class="prettyprint"><code>composer parseSudoku
<digit|dot>
rule digit: [<'\d'>]
rule dot: <'\.'> -> [1..9]
end parseSudoku
test 'input sudoku'
assert '9' -> parseSudoku <=[9]> ''
assert '.' -> parseSudoku <=[1..9]> ''
end 'input sudoku'
out:
input sudoku failed:
assertion that failed with value [9]
</code></pre>
<div>
That's a surprise, the output looks like what I expect. It turns out, though, that the string '9' gets displayed like the integer 9 (filing an issue for better test output). It doesn't actually matter whether I use character strings or integers, the internal solver handles either, as long as we use the same type throughout. I will use characters (chosen by coin-flip), but that wasn't really the problem because the parsing actually works. So I extend the experiment a bit:</div>
<pre class="prettyprint"><code>composer parseSudoku
<digit|dot>=3 (<'|'>?)
rule digit: [<'\d'>]
rule dot: <'\.'> -> [1..9 -> '$;']
end parseSudoku
test 'input sudoku'
assert ['139' -> parseSudoku] <=[['1'],['3'],['9']]> 'plain'
assert ['139|' -> parseSudoku] <=[['1'],['3'],['9']]> 'with |'
end 'input sudoku'
out:
Exception in thread "main" java.lang.IllegalStateException: Composer did not use entire string. Remaining:'|'
</code></pre>
<div>
So there we have it, my rule to match <'|'> doesn't match a '|' because it's a special character in regex syntax. I have to escape it with a backslash. I correct the issues, reinstate the original test and the test passes. I add two more assertions which pass immediately.</div>
<pre class="prettyprint"><code> assert $parsed(1;1) <=['5']> 'a digit'
assert $parsed(1;3) <=['1','2','3','4','5','6','7','8','9']> 'a dot'</code></pre>
<div>
Excellent! Now we just need to put it all together and I write the test I deferred at the beginning of this article. The printing code takes a bit of thought but I decide that I can easily distinguish errors in printing from errors in solving so I don't need a separate test right now.</div>
<pre class="prettyprint"><code>templates solveSudoku
$ -> parseSudoku -> placeDigit -> #
when <=[]> do 'No result found' !
otherwise def result: $;
[1..7:3 -> $result($..$+2) -> \section('$:1..11 -> '-';$#10;' ! $... ->
\row( def r: $;
[1..7:3 -> $r($..$+2) -> \triple('|' ! $... ! \triple)] -> '$(2..last)...;$#10;' !
\row)
!\section)] -> '$(2..last)...;' !
end solveSudoku
test 'sudoku solver'
assert
'53.|.7.|...
6..|195|...
.98|...|.67
-----------
8..|.6.|..3
4..|8.3|..1
7..|.2.|..6
-----------
.6.|...|28.
...|419|..5
...|.8.|.79'
-> solveSudoku <=
'534|678|912
672|195|348
198|342|567
-----------
859|761|423
426|853|791
713|924|856
-----------
961|537|284
287|419|635
345|286|179'> 'solves sudoku and outputs pretty solution'
end 'sudoku solver'</code></pre>
<div>
And there we have it! Apart from some whitespace errors it works like a charm. I correct those and look over the code. I don't like the names I have assigned to the templates. I can also consolidate the code for updating remaining possibilities and simplify the backtracking a bit because I will never find another position to continue from. The finished code is <a href="https://github.com/tobega/tailspin-v0/blob/master/samples/Sudoku.tt">here</a>.</div>
<div>
<br /></div>
<h2 style="text-align: left;">
<a href="https://www.blogger.com/blogger.g?blogID=7677021887363364182#" id="summary">Summary of the process</a></h2>
<div>
<ol style="text-align: left;">
<li>Don't start coding until you understand the problem.</li>
<li>Don't start coding until you understand well enough how you are going to solve it</li>
<ul>
<li>Explore various possibilities and evaluate</li>
<li>Choose the simplest solution that is good enough</li>
<li>If you cannot decide, ask yourself what information will help you decide and go find that out.</li>
<li>Don't get stuck, flip a coin if you have to. If it turns out bad you will have learned something along the way.</li>
</ul>
<li>Don't start coding until you know how the new code will fit into existing code, don't just add it the first place you think it might work. Refactor existing code to create a good fit, if needed.</li>
<li>Use tests to validate (or disprove) your assumptions.</li>
<ul>
<li>A failing test validates your assumption about what your code does not yet do correctly.</li>
<li>A failing test that starts to pass validates your assumption that the code you wrote actually does something useful.</li>
<li>An automated unit test that is kept and run periodically tests your assumption that "this code couldn't possibly break that code".</li>
</ul>
<li>When you don't fully understand how your tools work, you need to explore, observe and test your assumptions about them. Just don't confuse exploratory coding with production coding, you still need to validate that you can't simplify the experimental code.</li>
<li>When everything works, make sure your code is easy to read and understand and clean up whatever can be cleaned up. Another pair of eyes is good here, do code reviews or pair or mob programming.</li>
</ol>
<br /></div>
</div>
</div>
</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-20503003672204785932020-05-04T14:33:00.002-07:002020-08-08T06:33:39.053-07:00A little Tailspin<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
I was delighted to come across Uncle Bob's blogpost <a href="https://blog.cleancoder.com/uncle-bob/2020/04/09/ALittleMoreClojure.html">"A little more Clojure"</a> the other day, where he concludes:<br />
<blockquote class="tr_bq" style="background-color: #f8fff8; box-sizing: border-box; color: #29323c; font-family: "frescoplusnormal", "georgia", serif; font-size: 17.92px; margin-bottom: 0.8em;">
Now I want you to think carefully about how we solved this problem. No <code class="language-plaintext highlighter-rouge" style="box-sizing: border-box; font-family: monospace, serif; font-size: 0.9em; line-height: normal;">if</code> statements. No <code class="language-plaintext highlighter-rouge" style="box-sizing: border-box; font-family: monospace, serif; font-size: 0.9em; line-height: normal;">while</code> 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.<br />
<span face="" style="background-color: #f8fff8; color: #29323c; font-family: "frescoplusnormal", "georgia", serif; font-size: 17.92px;">Think hard on this – it is one of the keys to functional programming.</span></blockquote>
The way a programming language feels to use, like "fluid dynamics", is the main thing I was trying to get at in my <a href="https://cygni.se/is-your-programming-language-made-of-multidimensional-plasma/">previous article</a>. Do your programming languages feel like molding clay, or building sandcastles or even wrestling bears?<br />
<br />
This idea of thinking of data-flow, where streams of values get transformed step by step is the very foundation of the <a href="https://github.com/tobega/tailspin-v0">Tailspin programming language</a> 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.<br />
<br />
We'll begin with a function, called "templates" in Tailspin, that does nothing and an invocation:
<br />
<pre class="prettyprint"><code>
templates primes
!VOID
end primes
10 -> primes -> '$;
' -> !OUT::write
</code></pre>
<br />
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:
<br />
<pre class="prettyprint"><code>
templates primes
[1..$] !
end primes
</code></pre>
<br />
When we run the program we get "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</span>" 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:<br />
<pre class="prettyprint"><code>
templates primes
[1..$ -> ifPrime] !
end primes
</code></pre>
<br />
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:<br />
<pre class="prettyprint"><code>
templates ifPrime
!VOID
end ifPrime
</code></pre>
<br />
When we run our "primes" program, all the values get sent into the void, but the list is still created so we get "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[]</span>".<br />
<br />
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:<br />
<pre class="prettyprint"><code>
templates ifPrime
$ -> sqrt !
end ifPrime
100 -> ifPrime -> '$;
' -> !OUT::write
</code></pre>
<br />
This gives "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">10</span>" as a result, so far so good!<br />
<br />
Next we want to get a list of the integers between 2 and the square root:<br />
<pre class="prettyprint"><code>
templates ifPrime
def root: $ -> sqrt;
[2..$root] !
end ifPrime
</code></pre>
<br />
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 "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[2, 3, 4, 5, 6, 7, 8, 9, 10]</span>" as we should.<br />
<br />
Now we want to work out which of those numbers divide the input evenly:<br />
<pre class="prettyprint"><code>
templates ifPrime
def n: $;
def root: $ -> sqrt;
[2..$root -> $n mod $] !
end ifPrime
</code></pre>
<br />
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 "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[0, 1, 0, 0, 4, 2, 4, 1, 0]</span>".<br />
<br />
If there is a zero in the produced list, n is not prime. So how can we check that?<br />
<pre class="prettyprint"><code>
templates ifPrime
def n: $;
def root: $ -> sqrt;
[2..$root -> $n mod $] -> \(<~[<=0>]> $n ! \)!
end ifPrime
</code></pre>
<br />
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 "\".<br />
<pre class="prettyprint"><code>
100 -> ifPrime -> '$;
' -> !OUT::write
(No output)
17 -> ifPrime -> '$;
' -> !OUT::write
17
</code></pre>
<br />
Finally, changing back to running the "primes" program:<br />
<pre class="prettyprint"><code>
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]
</code></pre>
<br />
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?<br />
<pre class="prettyprint"><code>
templates ifPrime
def n: $;
def root: $ -> sqrt;
2 -> \(
when <?($n mod $ <=0>)> do !VOID
when <..$root> do $ + 1 -> #
otherwise $n !
\)!
end ifPrime
</code></pre>
<br />
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.<br />
<br />
The result we get now is "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]</span>". 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?<br />
<pre class="prettyprint"><code>
templates primes
def N: $;
@: [];
2 -> \(
when <..$N> do $ -> ifPrime -> ..|@primes: $;
$ + 1 -> #
\) -> !VOID
$@ !
end primes
</code></pre>
<br />
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.<br />
<br />
Running the program gives "<span face="" style="font-family: "helvetica neue"; font-size: 12px;">[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]</span>", 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:<br />
<pre class="prettyprint"><code>
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]
</code></pre>
<br />
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.<br />
<br />
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.<br />
<br />
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):<br />
<pre class="prettyprint"><code>
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'
</code></pre>
<br />
To limit ourselves to only dividing by primes less or equal to the square root, we can rearrange the matchers a bit:<br />
<pre class="prettyprint"><code>
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
</code></pre>
<br /></div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-32986030020374389492019-11-06T13:01:00.000-08:002020-02-14T05:32:26.038-08:00Is your programming language made of multidimensional plasma?<div dir="ltr" style="text-align: left;" trbidi="on">
Published on <a href="https://cygni.se/is-your-programming-language-made-of-multidimensional-plasma/">Cygni website</a></div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-44793400566496742322019-10-13T12:15:00.002-07:002021-04-23T00:16:32.053-07:00The perfect programming language<div dir="ltr" style="text-align: left;" trbidi="on">
This post has moved to <a href="https://cygni.se/the-perfect-programming-language/">https://cygni.se/the-perfect-programming-language/</a>
<br />
<br /></div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-85312376309190439522018-07-28T05:32:00.001-07:002019-10-12T08:40:27.862-07:00Java enums are not constants<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
Every now and then I come across a person who points out that my enum values should be written as all upper case with underscores because in their minds an enum is a constant. I find myself disagreeing but haven't previously managed to explain why.<br />
<br />
Historically in java we would use constants where we in other languages would have used an enum, so it doesn't seem unreasonable to consider enums to be constants. And yet they are not.<br />
<br />
Consider the following code where we have tacos on a Friday as we like to do in Sweden:<br />
<br />
<pre class="prettyprint"><code class="language-java">
class DinnerPlanner {
...
Menu createMenu() {
...
if (today.equals(DayOfWeek.FRIDAY)) {
menu.add("tacos");
}
...
}
...
void buyIngredients() {
...
if (today.equals(DayOfWeek.FRIDAY)) {
buy("taco shells", "tomatoes", ...);
}
...
}
...
void cook() {
...
if (today.equals(DayOfWeek.FRIDAY)) {
oven.put("taco shells");
fryingPan.put("mince").put("taco spices");
}
...
}
}
</code></pre>
<br />
After some time we get more and more influences from the US and we want to make tacos on Tuesday instead.<br />
<br />
And now it should be evident: DayOfWeek.FRIDAY is not a constant, it is a hard-coded value. We could introduce a constant:<br />
<pre class="prettyprint"><code class="language-java">
static final DayOfWeek TACO_DAY = DayOfWeek.FRIDAY;
</code></pre>
<br />
Now we can just reassign the <b>constant</b> TACO_DAY to the <b>value</b> DayOfWeek.TUESDAY.<br />
<br />
In many other languages, it is possible to say that an enum <b>has a value</b>, e.g. DayOfWeek.FRIDAY might correspond to the integer value 5 and we can use FRIDAY or 5 as we see fit, but not so in java where FRIDAY <b>is the value</b> in the APIs and we are actively discouraged from thinking about its ordinal value in the list.<br />
<br />
Consider also my <a href="https://tobega.blogspot.com/2008/05/beautiful-enums.html">previous post</a> where instead of switching on an enum value to determine the code, we can actually implement the code in the enum.<br />
<br />
Still think a java enum is a constant?</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-34153287554250251352018-03-18T12:28:00.001-07:002018-09-26T23:35:08.841-07:00WTF-debugging: the case of the unfortunate design choices fooling perception<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js"></script>
A few of my former colleagues at Google really love golang so I decided to start playing with it. I highly recommend the interactive tour <a href="https://tour.golang.org/">https://tour.golang.org</a> to get a quick sense of it. It's a fairly nice language, simple but with the parts you really need, feels nice and "javascripty" in object creation but still structured and typed strictly enough.<br />
<br />
However, there is at least one case where the desire to avoid too prescriptive syntax results in an unfortunate combination of design choices leading to WTF-debugging.<br />
<br />
Consider <a href="https://play.golang.org/p/yUlFI3aqYSS">https://play.golang.org/p/yUlFI3aqYSS</a> (run it, it prints 1,2,3,4). Now change line 12 (which could have been defined much further away, even in another file) by adding an asterisk in position 8 before Payload, to read:<br />
<pre class="prettyprint"><code class="language-go">
func (p *Payload) UploadToS3() error {
</code></pre>
<br />
Run it again and observe 4,4,4,4! Note that the loop where this happens is unchanged, but the loop variable "payload" has magically been changed from a value to a pointer. Spooky action at a distance now causes a different part of your program to be wrong. Keep staring at the loop and you will never figure it out.
<br />
<pre class="prettyprint"><code class="language-go">
for _,payload := range payloads {
go payload.UploadToS3()
}
</code></pre>
<br />
In java we would always know what is a value and what is a reference and we are of course also saved by the fact that variables used in closures have to be final (or effectively final). And in a functional language the variables would be immutable so this would never happen there either.
In javascript, though, we deal with this all the time, so a javascript programmer might be more confused that the first version actually worked. One of the problems in go is that we can have either values or pointers, but we don't have to be explicit about it because the compiler is too helpful.
Another problem is that it is unclear what code is executed now and what code is executed later. The word "go" is (at least not yet) a strong signal to my mind that the code after it is actually executed later. I have to go into deep analysis mode before I have a chance to perceive that. Consider the difference if we had been forced to write a little more, would it have been clearer?
<br />
<pre class="prettyprint"><code class="language-go">
for _,payload := range payloads {
go func() {
payload.UploadToS3()
}()
}
</code></pre>
<br />
I think that is slightly clearer, but I think it still indicates the problem with inline closures for asynchronous computing. In java I would tend to recommend to never use anonymous inner classes, but take the time to make it a named inner class, defined elsewhere, so you have a better chance of realizing that the code will execute at another time. I have seen otherwise excellent coders stumble on this temporal misperception.<br />
<br />
Interestingly, the perceptual difficulty of when code executes can also go the other way. When using Mockito, the below code doesn't immediately signal your brain that the bar() method actually gets called.<br />
<pre class="prettyprint"><code class="language-java">
when(foo.bar()).thenReturn(5);
</code></pre>
<br /></div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-37171363020397669502018-02-23T11:44:00.000-08:002018-03-18T11:38:51.622-07:00WTF-debugging: the case of the obscure configuration<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js"></script>
<br />
<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
Ever stared at a piece of code without understanding why in the world it does not work? Or why it actually works at all? I'd like to call this phenomenon WTF-debugging and I've been remarkably free of it since I've been doing framework-free backend java. But now I have a new job and we use all the popular frameworks, for better and for worse. Well, really only for worse, IMO, but I
will write more on that when I understand my aversion better. So far, I have discovered that the tendency to want to write frameworks is very strong because it is the ultimate intellectual masturbation. The tendency to want to use frameworks is more puzzling, but I think we are all attracted to magic to some degree and there is a powerful illusion that frameworks provide a lot of value, automagically.<br />
<br />
We are working with JSON in Java and using Jackson, and I had a little problem where one of the
fields of the main object could be a different type depending on what the object represented, as indicated by a type name in another field. So I had to work out how to configure Jackson to handle it, which turned out to be a little challenging. After an hour or so I hit upon a fruitful phrasing of the search terms and found a solution.<br />
<br />
<br /></div>
<pre class="prettyprint"><code class="language-java">
@JsonDeserialize(builder = Attachment.AttachmentBuilder.class)
public class Attachment {
private final long id;
private final String attachmentType;
...
public interface ExcelSheets extends List<ExcelSheet> {}
private static class ExcelSheetsImpl extends ArrayList<ExcelSheet> implements ExcelSheets {}
@JsonTypeInfo(use = Id.NAME, property = "attachmentType")
@JsonSubTypes(value = {
@JsonSubTypes.Type(value = ExcelSheetsImpl.class, name ="excel")
})
private final Object typeSpecificData;
Attachment(long id, String attachmentType, long reportId, String filename, Object typeSpecificData) {
this.id = id;
this.attachmentType = attachmentType;
...
this.typeSpecificData = typeSpecificData;
}
public long getId() { return id; }
public String getAttachmentType() { return attachmentType; }
...
public Object getTypeSpecificData() { return typeSpecificData; }
@Override
public AttachmentBuilder builder() { return new AttachmentBuilder(this); }
public static class AttachmentBuilder implements Builder<attachment> {
private long id;
private String attachmentType;
private Object typeSpecificData;
...
public AttachmentBuilder() {}
AttachmentBuilder(Attachment attachment) {
this.id = attachment.id;
this.attachmentType = attachment.attachmentType;
...
}
@Override
public AttachmentBuilder withId(long id) {
this.id = id;
return this;
}
public AttachmentBuilder withAttachmentType(String attachmentType) {
this.attachmentType = attachmentType;
return this;
}
public AttachmentBuilder withTypeSpecificData(Object typeSpecificData) {
this.typeSpecificData = typeSpecificData;
return this;
}
...
@Override
public Attachment build() {
return new Attachment(id, attachmentType, reportId, filename, typeSpecificData);
}
}
}
</attachment></code></pre>
<br />
Now I could be happy with that and sing the praises of Jackson and "look how elegantly it got configured". But should I?<br />
<br />
Even when I have this solution before me, I still can't quite figure it out from the documentation (WTF?), so what will happen in six months time when I have to modify this code?<br />
<br />
And here comes an even bigger WTF: change the type "Object" for typeSpecificData to "ExcelSheets" and deserialization no longer works! (What I really wanted to do was to introduce a marker interface, TypeSpecificData, but, as you can surmise, that didn't work either.)
<br />
<br />
Even though Jackson is (sadly) perhaps the easiest way to handle JSON in Java, I think there may be good reasons besides the above to avoid using it. I won't go into that in detail in this post, but I will leave with this thought: Jackson or any other automagic data-binding framework entices you to create Java objects that match the serialized JSON, but your serialization format is not your internal model, at least not forever, because the two have different reasons to change. So even after you get a deserialized object from Jackson, you <i>should</i> probably write lots of code to transfer the data into your internal representation. Then what did you gain?</div>
</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-29211991825526301862011-01-05T21:49:00.000-08:002011-01-05T22:58:28.700-08:00Prove your assumptions, but remember Murphy was an optimistContinuing on my unremarkable coding task, having gotten it to work, it was now time to clean up the code.<div><br /></div><div>Given the large load expected, I couldn't allocate a new direct ByteBuffer for every piece of data I wanted to handle. But code that accepts a ByteBuffer is equivalent to code that accepts a byte array, a starting offset and a length (or a limit), right? So I just set the position and the limit on the boundaries of the data and I'm good to go.</div><div><br /></div><div>Now I ran into some of my own previous assumptions. Luckily, the failure resulted in a log message that made it clear where something was going wrong. It was one of those places where a deviation from the happy path either cannot happen, should not happen or we didn't really care too much. A place where I used to code an empty block "<span class="Apple-style-span" style="font-family:'courier new';">{}</span>", or when I was feeling diligent, with a comment "<span class="Apple-style-span" style="font-family:'courier new';">{/*cannot happen*/}</span>". Now I'll code it as "<span class="Apple-style-span" style="font-family:'courier new';">{throw new AssertionError("Cannot happen.");}</span>" or at least "<span class="Apple-style-span" style="font-family:'courier new';">{LOG.fine("Don't care.");}</span>".</div><div><br /></div><div>Anyway, a quick analysis showed a likely cause. I say likely, because it's an assumption until proven. I wrote a quick unit test that failed, fixed the code and the test passed. But the program still failed, with the same log message as before. Imagine what I might have been doing if I hadn't proven the failure and the fix with the unit test, I'd still be staring at the same place and possibly ripping my code to shreds in desperation. Now I could immediately move on and fix the second error.</div><div><br /></div><div>OK, on a roll now, all assumptions proven by assertions, I'm just about done. Except that the code still doesn't work and no sign of why. Murphy's law in full action.</div><div><br /></div><div>Finally I find it. There's a trap in ExecutorService. What's the difference between calling "<span class="Apple-style-span" style="font-family:'courier new';">execute(Runnable)</span>" versus "<span class="Apple-style-span" style="font-family:'courier new';">submit(Runnable)</span>"? Nothing much, when the code works. But "<span class="Apple-style-span" style="font-family:'courier new';">submit(Runnable)</span>" should have a big red warning sticker. It returns a Future, with no result. You don't bother to "<span class="Apple-style-span" style="font-family:'courier new';">get()</span>" nothing. The devastating side-effect is that all exceptions get preserved until "<span class="Apple-style-span" style="font-family:'courier new';">get()</span>" is called, so this is a hidden equivalent of "<span class="Apple-style-span" style="font-family:'courier new';">catch(Exception e){}</span>". Next task: change this everywhere and add a rule to FindBugs.</div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-19303812242713357622011-01-01T11:06:00.001-08:002011-01-02T04:10:52.925-08:00Your assumptions are dangerous, you know too much.I have just completed a rather unremarkable piece of code. The system was designed to allow this type of addition, so it just took a couple of hours or three to write the code and touch up the parts to selectively enable the functionality by user.<div><br /></div><div>Then a colleague and I spent two days debugging. We hacked around issue after issue, just to prove basic workability before trying to solve the issues.</div><div><br /></div><div>The final obstacle was that our socket channel was not being selected for reading on the selector. So I hacked around that by creating a new thread to loop infinitely around reading the channel. Which made things work fine up to the point where actual data was coming in and the server blew up with a segmentation fault.</div><div><br /></div><div>After reflecting while travelling on the bus home, I remembered that perhaps our JNI code needed a direct byte buffer, with data starting at position 0 and the whole backing array available for use. Inconvenient in this case, but another little hack and everything worked like a charm.</div><div><br /></div><div>Back to the previous question: why no reads? Perhaps my server socket in non-blocking mode actually returned a socket configured for blocking mode instead of for non-blocking mode? It did, and explicitly setting it to non-blocking fixed it.</div><div><br /></div><div>As I backtracked through the issues, it struck me that every single problem we'd run into had to do with assumptions.</div><div><br /></div><div>I could of course have checked my assumption about the blocking mode. But I also have another assumption, which is more valid: incorrect usage of an API should not fail silently. This turns out to be correct, because a SelectableChannel throws an IllegalBlockingModeException. </div><div><br /></div><div>Unfortunately, the "helper" framework that we have in place inadvertently masked that by running the register call in a FutureTask that had a boolean "success" return value that nobody had found the need to check, because "true" was the only possibility. Well, that is, assuming no exceptions are thrown.</div><div><br /></div><div>Perhaps there is also a flaw in the assumption that a helper framework that obscures the standard API is actually helpful.</div><div><br /></div><div><div>Certainly, the direct byte buffer assumption mentioned above should probably have been asserted somewhere, it's easy enough to throw an IllegalArgumentException if buffer.isDirect() returns false. Obviously, the programmer who created the JNI call was not assuming we had a direct byte buffer, he knew we had one. But that's the trick of maintainable and re-usable object oriented code: you cannot rely on any knowledge outside the class you are currently in. From the point of view of the class, such knowledge is an assumption.</div></div><div><br /></div><div>Another issue I had hit on the way concerned the UserIdentifier class. It is really just a wrapper around a string, but because it has a specific semantic meaning it was correctly exposed as a separate value class. To limit the new functionality by groups of users, I found it convenient to construct the user identifier slightly differently. The code did not work as expected.</div><div><br /></div><div>At another point in the code, a programmer had used his knowledge of how the user identifier was constructed, which introduced a hidden assumption about the structure of the user identifier. The correct code would have been to obtain the user identifier from a single authoritative place.</div><div><br /></div><div>The root cause of the user identifier hack was a design assumption that two things were independent. When they were not, a co-dependency web was created. In a sense, this is also a case of classes having too much knowledge: they knew about too many different other classes that they needed to collaborate with. To keep your code clean and honest, such things need to be refactored (re-designed).</div><div><br /></div><div>Consider the small amount of care and time it would have taken to avoid the assumptions in the first place and compare it to the four man-days of lost productivity that was caused. We are always under time pressure, but that will be the case next week, month or year as well. If you don't pay the price now, you pay it with interest later.</div><div><br /></div><div>The more things your classes know about your system, the harder it is to change or re-use the code. Make sure that the knowledge you put into a class is appropriate and doesn't create a dangerous web of assumptions.</div><div><br /></div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-4009572078552048562009-08-28T11:43:00.000-07:002009-08-28T13:26:26.758-07:00Clarity of code is clarity of thoughtI remember at my first job when we introduced the concept of code reviews. I don't think anybody really looked at anybody else's code before pressing the "approve" button, I know I didn't. Reading code is boring and it can be hard and it felt like a waste of time. I had my own code to write and why shouldn't the author of the code have written it right in the first place?<div><br /></div><div>When I moved to another job, they talked about how, in theory, code reviews was the number one most effective way to increase code quality. But they had given up on it, because they felt it came down to a discussion of where to put the dots and commas (or, rather, semi-colons and parentheses).</div><div><br /></div><div>Quite aside from the issue of code reviews, I had come to realize that I spent much more time reading my code than I spent writing it. Every debugging session is spent reading code over and over. Every time you have to add a feature or change some functionality you have to read the code, and re-read it to avoid breaking stuff. Don't tell me tests will do it for you. Now don't get me wrong, tests are great and I strongly advocate test-first coding, it's a great way to achieve focus and clarity of thought. But when a test fails, you're thrown into debugging mode, which means reading code.</div><div><br /></div><div>So I concluded it was worth spending a little extra time typing longer variable names, and taking the time to find descriptive names. It was worth spending a little more time breaking down those long methods and simplifying those complex structures. Whenever I was reading code that made me stop and think, I would usually refactor it to be clearer (although the term refactoring hadn't been invented yet). I would also change existing code to make a new feature fit in better, in a more readable and more logical way.</div><div><br /></div><div>In "The Pragmatic Programmer" the distinction is made between "programming by coincidence" and "programming by intention". We all have to do it occasionally, a little trial-and-error programming, because we're not quite sure how things work. That's "programming by coincidence". Before you check your code in, you want to make sure you understand what each statement does and that all unnecessary statements are removed. Then you've transformed the code from coincidental to intentional.</div><div><br /></div><div>But that's not enough. Your very functional and intentional code is going to lose you valuable time unless you also transform it to readable code, which clearly displays your intent.</div><div><br /></div><div>A much-touted wisdom is that you should document and comment your code. Fair enough, that works, but it has many weaknesses. Your energy is far better spent making the code explain itself. Comments often lie, but the code is always pure truth, so prove it in code. Only comment on "why" you are doing something, and that only if you cannot make it evident in the code.</div><div><br /></div><div>I like the following sound-bite from "Refactoring": "Any fool can write code that a machine can understand, it takes a good programmer to write code that a human can understand."</div><div><br /></div><div>Test-first "anything" is efficient and focused because it sets up the criteria for success and the means to measure it up front. So what's the best way to test if your code is readable? Get another person to read it, i.e. a code review.</div><div><br /></div><div><div>I'm very grateful to those who review my code carefully and pick on every detail, it makes the code better and it helps assert that my thinking was clear. That gratitude gives me the energy to return the favour by reviewing their code equally mercilessly.</div><div><br /></div></div><div>You will sometimes, but rarely, find bugs by just reading code (only because everybody has a brain-fart now and then). But the real value of the reviews is in the "dot and comma" discussions and especially in picking good names. In addition to making sure that the code is easy to read, it will sometimes bring a real little nasty bug to the surface.</div><div><br /></div><div>An example: An index into an array of values is stored into a variable called "value". When the reviewer makes you change the name to "valueIndex" instead, some parts of your code may start to look weird (the bug was exposed).</div><div><br /></div><div>Clarity of code really is clarity of thought.</div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-12385705203507196512008-12-25T14:22:00.000-08:002008-12-25T15:27:12.954-08:00Using Java concurrency utilitiesThe inspiration for this post comes from <a href="http://weblogs.java.net/blog/jhook/archive/2008/12/accelerating_ap_1.html">Jacob Hookom's blog</a> and I can only second the recommendations he gives. Although, as always, I would caution to test any such implementation properly, that it works well and <a href="http://smallwig.blogspot.com/2008/04/smallwig-theory-of-optimization.html">actually provides a benefit</a>. There are lots of pitfalls and concurrency is tricky even with the excellent utilities provided in Java.<div><br /></div><div>To summarize the interesting problem: parallelize the execution of lengthy tasks in a web request, without creating many threads for each request, but also ensuring that the thread pool is not starved by one request. The idea is to have a reasonably sized thread pool and to limit the number of tasks executing in parallel to a number small enough to allow the expected amount of concurrent requests to share the pooled threads.</div><div><br /></div><div>Essentially, limiting the number of tasks executing in parallel can be done in two ways: limit the number of tasks submitted at one time or limit the number of workers that execute a set of tasks. Jacob takes the first approach, I will take the second approach, which seems to make it simpler to manage time-out issues.</div><div><br /></div><div>Here's some code:</div><pre><br /><V> Queue<Future><V>> submit(int numberOfWorkers, Queue<Callable><V>> tasks,<br /> long timeout, TimeUnit unit)<br /> throws InterruptedException, TimeoutException {<br />Queue<Future><V>> result = new ConcurrentLinkedQueue<Future><V>>();<br />List<WorkerTask><V>> workers = new ArrayList<WorkerTask><V>>(numberOfWorkers);<br />for (int i = 0; i < numberOfWorkers; i++) {<br /> workers.add(new WorkerTask<V>(result, tasks));<br />}<br />List<Future><Object>> deadWorkers<br /> = executor.invokeAll(workers, timeout, unit);<br />for (Future<Object> obituary : deadWorkers) {<br /> if (obituary.isCancelled()) {<br /> throw new TimeoutException();<br /> }<br />}<br />return result;<br />}<br /></pre><br /><br /><div>And the code for a WorkerTask:</div><pre><br />private static class WorkerTask<V> implements Callable<Object> {<br /><br />private Queue<Callable><V>> tasks;<br />private Queue<Future><V>> result;<br /><br />public WorkerTask(Queue<Future><V>> result, Queue<Callable><V>> tasks) {<br /> this.result = result;<br /> this.tasks = tasks;<br />}<br /><br />public Object call() {<br /> for (Callable<V> task = tasks.poll(); task != null; task = tasks.poll()) {<br /> FutureTask<V> future = new FutureTask<V>(task);<br /> future.run();<br /> if (Thread.interrupted()) {<br /> Thread.currentThread().interrupt(); // Restore interrupt.<br /> break;<br /> }<br /> result.add(future);<br /> }<br /> return null;<br />}<br />}<br /></pre><br /><div>Note that it is important to have thread-safe collections for tasks and result, we should actually make sure that the tasks are in a thread-safe collection, but I'll ignore that for now. Note also the check if the thread has been interrupted in the call() method of WorkerTask. That is vital to be able to cancel the task when you don't want to wait for it any longer (i.e. on time-out). If possible, the submitted tasks should also handle interrupts. Note the careful restoration of the interrupt status so that the caller of the method may also be notified.<br /></div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com2tag:blogger.com,1999:blog-7677021887363364182.post-12929458359612229772008-11-24T12:55:00.000-08:002008-11-24T14:24:29.739-08:00GC is for Goodstuff CollectorI have over the past few months noticed that there is a fairly common fear of creating objects in Java. When I query the authors, it always seems to boil down to an attempt to create more performant code through avoiding garbage collection.<div><br /></div><div>So why would one want to create more objects, anyway? Well, one good reason would be to get more readable code, e.g. through <a href="'http://www.refactoring.com/catalog/replaceMethodWithMethodObject.html'">encapsulating an algorithm</a> or using appropriate helper objects to express an algorithm more clearly.</div><div><br /></div><div>Even when the code does get put into a helper object, there seems to be a tendency to keep that instance around and reuse it, to avoid garbage collection so that the code performs better. My first comment is always "You should measure that". If I wanted to put it more sharply I should say "If you can't prove it's a performance benefit, then it probably isn't". I have worked with enough optimization to know that what's true for one language will not be true for another. Even using the same language, something that gives a performance benefit on one machine may be a detriment on another kind of machine (or even the same kind of machine with different "tweaks" like page sizes and such).</div><div><br /></div><div>If you create a temporary object that lives only as long as you need it you gain the following benefits:</div><div><ol><li>Your object is always in a pristine state when you want to use it.</li><li>Your code is a big step closer to being thread safe.</li><li>Your code is more readable and easier to analyze.</li><li>Your garbage collector gets to do less work.</li></ol>"What?", you say, "The garbage collector does less work by collecting more garbage?".</div><div><br /></div><div>Indeed it does. When we hear "garbage collector" we tend to think of the work involved in clearing out an overfilled store room, all that work to haul all the garbage out. But the garbage collector doesn't even know the garbage exists, the very definition of garbage is that it can no longer be reached from anywhere. What the garbage collector really does is create a whole new store room and move the stuff you want to keep over to it and then it lets the old store room and all the garbage disappear in a puff of smoke. So all the work done by the garbage collector is really done to keep objects alive, i.e. the GC is really the "goodstuff" collector.</div><div><br /></div><div>This is obviously a somewhat simplified view and I don't think it holds completely for objects with finalizers (which is probably why finalizers are really bad for performance). Every single measurement and microbenchmark I've done confirms that creating and destroying objects is never worse and often much better than trying to keep objects around. I've done a few, first because I didn't trust it, then because others were so convinced of the opposite that I had to research it. That isn't an absolute proof that it will be true for all scenarios, but I think it's a pretty good indication of where you should be pointing when shooting from the hip.</div><div><br /></div><div>From <a href="'http://www.ibm.com/developerworks/java/library/j-jtp09275.html'">an IBM developer works article</a>, we get the numbers that allocating an object in Java takes about 10 machine instructions (an order of magnitude better than the best C/C++ allocation) and that throwing an object away costs, you guessed it, absolutely zero. So just remember that GC stands for "Goodstuff Collector" and you'll be on the right track.</div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-78874206794476492752008-08-16T11:39:00.000-07:002008-08-18T15:17:31.039-07:00The legacy of inheritanceIs inheritance really useful or is it a feature that causes more problems than it solves? Certainly I can't think of a case where I've been really grateful that I've been able to inherit from a superclass but I can think of several instances where it has caused friction and where the extension mechanism of inheritance tended to lead the programmer the wrong way.<div><br /></div><div>Consider the following code (public fields for brevity):</div><div><pre><br />public class Square {<br /> public int base;<br /> public int getArea() {<br /> return base * base;<br /> }<br />}<br /><br />public class Rectangle extends Square {<br /> public int height;<br /> @Override public int getArea() {<br /> return base * height;<br /> }<br />}<br /><br />public class Parallelogram extends Rectangle {<br /> public double angle;<br />}<br /></pre><br /></div><div>Now how do we implement a Rhombus? Is it a Square extended with an angle (and overridden area calculation) or a Parallelogram with conditions on setting the properties so that the invariant is preserved (which is why we should have accessors, by the way)?</div><div><br /></div><div>Well, the correct answer is neither, even though we have a nice sequence of extensions. The problem is that we have been led astray by the extension mechanism and violated the "is a" rule for subclassing and ended up with a corrupt type system. Clearly a Parallelogram is not a Rectangle which equally clearly is not a Square so a subclass instance may not safely be used in place of a superclass instance. Reversing the class hierarchy solves the issue, however it creates subclasses that are restrictions of the superclass rather than extensions.</div><div><br /></div><div>An acquaintance of mine who is highly experienced in creating standardized components for information interchange once claimed that it only works to inherit properties by restriction. This is well worth considering, although I'm not entirely convinced because it causes a different set of problems when restriction means "that particular property is not used", as it so often does in information interchange scenarios. In that case it is usually not interesting nor useful to know what the superclass is. In our case at hand it will work because the subclasses actually have a meaningful and useful value of the property but it is restricted by an invariant, so it is also useful to be able to view them as instances of the superclass.</div><div><br /></div><div>Let's try coding again:</div><div><br /><pre>public class Parallelogram {<br /> protected int base;<br /> protected int height;<br /> protected double angle;<br /><br /> public void setAngle(double angle) {<br /> this.angle = angle;<br /> }<br />}<br /><br />public class Rectangle extends Parallelogram {<br /> @Override public void setAngle(double angle) {<br /> <b>// What should we do here?</b><br /> }<br />}<br />...<br /></pre></div><div><br /></div><div>Oops, this doesn't seem to work well, either. Obviously we can't just inherit the setAngle method or we could end up with a corrupt Rectangle, nor is there any reasonable action we can take. We can get out of our pickle, however, because constructors are <span class="Apple-style-span" style="font-weight: bold;">not</span> inherited! Simply make our instances immutable:</div><div><pre>public class Parallelogram {<br /> public final int base;<br /> public final int height;<br /> public final int angle;<br /><br /> public Parallelogram(int base, int height, double angle) {<br /> this.base = base;<br /> this.height = height;<br /> this.angle = angle;<br /> }<br /><br /> public int getArea() {<br /> return base * height;<br /> }<br />}<br /><br />public class Rectangle extends Parallelogram {<br /> public Rectangle(int base, int height) {<br /> super(base, height, Math.PI/2);<br /> }<br />}<br /><br />public class Square extends Rectangle {<br /> public Square(int side) {<br /> super(side, side);<br /> }<br />}</pre></div><div><br /></div><div>That seems to work, and the implementation of getArea() is actually profitably inherited. But we still have a problem in Java with a Rhombus, since a Square is both a Rectangle and a Rhombus but a Rhombus is not a Rectangle. To solve that would require defining the types as interfaces and have separate implementation classes (now I understand why that is often recommended :-) ).</div><div><br /></div><div>If we had chosen to implement Parallelogram with a field for the length of the side instead of the height, the formula for the area would have been base*Math.sin(angle)*side. Even if this would have worked for our Rectangle, it would have been inefficient (although when the fields are immutable it could probably be optimized by the compiler and/or JVM).</div><div><br /></div><div>On the whole, I believe it is seldom profitable to inherit the implementation of a method, if you have a good example to the contrary, please share it.</div><div><br /></div><div>I think that overriding all public methods would be preferable, even if you just decide to call super's version, at least it would show that you gave some thought to whether it was correct or not. Without having done an exhaustive study, I believe this is especially true for interfaces that indicate that a class "is" something rather than that it "is a" something, i.e. those interfaces whose name usually end in "able". Try Cloneable, Externalizable, Runnable and Printable.</div>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com2tag:blogger.com,1999:blog-7677021887363364182.post-76040360302073588782008-07-21T15:01:00.000-07:002008-07-21T16:12:31.554-07:00Cedric's coding challengeAlthough I came late to the party at <a href="http://beust.com/weblog/archives/000491.html">Cedric's coding challenge</a>, this is the kind of problem I just can't resist taking at least a little dip into. The idea is to generate all numbers up to a maximum that do not have any repeated digits.<br /><br />My initial thought was that the pattern of digits for an n-digit number should be the same, you just need to recode the values. I.e. given 3 digits a, b and c from which you should generate all 3-digit sequences without repeated digits, then generating the 2-digit suffixes ac and ca after choosing b as the first digit is the same as choosing a as the first digit, generating bc and cb and then recoding a->b, b->a and c->c.<br /><br />Anyway, I soon realized that I couldn't come up with an efficient recoding algorithm and also that generating the suffixes didn't cost much more than an iteration over a pre-generated suffix list. So I basically ended up with the same algorithm as <a href="http://crazybob.org/FastBeustSequence.java.html">crazybob</a> and <a href="http://code.google.com/p/blogcode/source/browse/trunk/BeustChallenge0708/src/beust/ModifiedBeustSequence.java?r=8">Jonathan Hawkes improvement</a>. Happily, my implementation was a bit faster still than both of theirs, 30% faster than Bob's and 20% faster than Jonathan's in Bob's way of counting and when measured like Jonathn does it, mine is 65% faster than Bob's and 30% faster than Jonathan's. Here it is:<br /><pre><br /><span class="s0">/** <br /> * Finds base 10 numbers whose digits don't repeat. Solution to Cedric's coding <br /> * challenge: http://beust.com/weblog/archives/000491.html <br /> * <br /> * </span><span class="s1">@author </span><span class="s0">Torbjorn Gannholm <br /> */</span><span class="s2"> <br /></span><span class="s3">public class </span><span class="s2">NonRepeatingDigits { <br /> </span><span class="s3">private final long </span><span class="s2">max; <br /> </span><span class="s3">private final int </span><span class="s2">base; <br /> </span><span class="s3">private final </span><span class="s2">Listener listener; <br /> </span><span class="s3">private final </span><span class="s2">Digit head; <br /> <br /> </span><span class="s0">/** <br /> * Finds all numbers with non-repeating digits in the supplied base up to max. <br /> * </span><span class="s1">@param </span><span class="s0">base The base, e.g. octal (8), decimal (10), hexadecimal (16). <br /> * </span><span class="s1">@param </span><span class="s0">max Upper bound for returned values. <br /> * </span><span class="s1">@param </span><span class="s0">listener Listener to receive valid numbers. <br /> */</span><span class="s2"> <br /> </span><span class="s3">public </span><span class="s2">NonRepeatingDigits(</span><span class="s3">int </span><span class="s2">base, </span><span class="s3">long </span><span class="s2">max, Listener listener) { <br /> </span><span class="s3">this</span><span class="s2">.base = base; <br /> </span><span class="s3">this</span><span class="s2">.max = max; <br /> </span><span class="s3">this</span><span class="s2">.listener = listener; <br /> head = </span><span class="s3">new </span><span class="s2">Digit(base); <br /> } <br /> <br /> </span><span class="s3">public void </span><span class="s2">run() { <br /> </span><span class="s0">// One digit numbers.</span><span class="s2"> <br /> </span><span class="s3">for </span><span class="s2">(Digit current = head.next.next; <br /> current != </span><span class="s3">null</span><span class="s2">; <br /> current = current.next) { <br /> </span><span class="s3">int </span><span class="s2">value = current.value; <br /> </span><span class="s3">if </span><span class="s2">(value > max) </span><span class="s3">return</span><span class="s2">; <br /> listener.hear(value); <br /> } <br /> </span><span class="s0">// Pick first digit (non-zero), then find the rest of the number.</span><span class="s2"> <br /> </span><span class="s3">for </span><span class="s2">(</span><span class="s3">int </span><span class="s2">digitsAfterFirst = </span><span class="s4">1</span><span class="s2">; <br /> digitsAfterFirst < base; <br /> digitsAfterFirst++) { <br /> </span><span class="s3">for </span><span class="s2">(Digit previous = head.next, current = head.next.next; <br /> current != </span><span class="s3">null</span><span class="s2">; <br /> </span><span class="s0">// Restore removed digit to sequence.</span><span class="s2"> <br /> previous.next = current, previous = current, current = current.next) { <br /> </span><span class="s0">// Remove chosen digit from sequence.</span><span class="s2"> <br /> previous.next = current.next; <br /> </span><span class="s3">if </span><span class="s2">(followingDigits(digitsAfterFirst, current.value * base)) </span><span class="s3">return</span><span class="s2">; <br /> } <br /> } <br /> } <br /> <br /> </span><span class="s0">/** A digit, part of a linked list of all digits in a base. <br /> * (Shamelessly paraphrased from crazybob) */</span><span class="s2"> <br /> </span><span class="s3">private static class </span><span class="s2">Digit { <br /> </span><span class="s3">private </span><span class="s2">Digit next; <br /> </span><span class="s3">private final int </span><span class="s2">value; <br /> <br /> </span><span class="s0">/** Constructs a non-digit that acts as the head for the list, and the <br /> * digits in the list. */</span><span class="s2"> <br /> Digit(</span><span class="s3">int </span><span class="s2">base) { <br /> value = -</span><span class="s4">1</span><span class="s2">; <br /> next = </span><span class="s3">new </span><span class="s2">Digit(base, </span><span class="s4">0</span><span class="s2">); <br /> } <br /> <br /> </span><span class="s0">/** Constructs the real sequence of digits */</span><span class="s2"> <br /> </span><span class="s3">private </span><span class="s2">Digit(</span><span class="s3">int </span><span class="s2">base, </span><span class="s3">int </span><span class="s2">value) { <br /> </span><span class="s3">this</span><span class="s2">.value = value; <br /> </span><span class="s3">if </span><span class="s2">(++value < base) { <br /> next = </span><span class="s3">new </span><span class="s2">Digit(base, value); <br /> } <br /> } <br /> } <br /> <br /> </span><span class="s0">/** <br /> * Recursively generates digits after the first of a valid number. <br /> * </span><span class="s1">@param </span><span class="s0">remaining Number of digits left to generate. <br /> * </span><span class="s1">@param </span><span class="s0">prefixValue Value of previous digits. <br /> * </span><span class="s1">@return </span><span class="s0">true when values generated are greater than max. <br /> */</span><span class="s2"> <br /> </span><span class="s3">private boolean </span><span class="s2">followingDigits(</span><span class="s3">int </span><span class="s2">remaining, </span><span class="s3">int </span><span class="s2">prefixValue) { <br /> </span><span class="s3">if </span><span class="s2">(remaining > </span><span class="s4">1</span><span class="s2">) { <br /> </span><span class="s3">for </span><span class="s2">(Digit prev = head , current = head.next; <br /> current != </span><span class="s3">null</span><span class="s2">; <br /> </span><span class="s0">// Restore removed digit to sequence.</span><span class="s2"> <br /> prev.next = current, prev = current, current = current.next) { <br /> </span><span class="s0">// Remove chosen digit from allowable digits.</span><span class="s2"> <br /> prev.next = current.next; <br /> </span><span class="s3">if</span><span class="s2">(followingDigits(remaining - </span><span class="s4">1</span><span class="s2">, <br /> (prefixValue + current.value) * base)) </span><span class="s3">return true</span><span class="s2">; <br /> } <br /> } </span><span class="s3">else </span><span class="s2">{ <br /> </span><span class="s3">for </span><span class="s2">(Digit current = head.next; current != </span><span class="s3">null</span><span class="s2">; current = current.next) { <br /> </span><span class="s3">int </span><span class="s2">value = prefixValue + current.value; <br /> </span><span class="s3">if </span><span class="s2">(value > max) </span><span class="s3">return true</span><span class="s2">; <br /> listener.hear(value); <br /> } <br /> } <br /> </span><span class="s3">return false</span><span class="s2">; <br /> } <br />} <br /></span></pre>tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-55410130387859295352008-05-04T04:37:00.001-07:002021-09-27T01:01:29.856-07:00Beautiful enums<div dir="ltr" style="text-align: left;" trbidi="on">
Whatever complaints you may have against java, I think you have to grant that at least enums are a thing of beauty. Consider this code line:<br />
<pre>Collections.sort(myChildren, Child.Order.ByAge.descending());</pre>
<br />
The best part is that this started to appear as a side effect of another rational structuring of code, creating a synergy effect of two positive drives together. This kind of synergy always appeals to my aesthetic sense. Here's the Child class:<br />
<pre>public final class Child {
private final Integer age;
private final String name;
...
public static enum Order implements Comparator<Child> {
ByAge() {
public int compare(Child lhs, Child rhs) {
return lhs.age.compareTo(rhs.age);
}
},
ByName() {
public int compare(Child lhs, Child rhs) {
// TODO: Should really use a collator.
return lhs.name.compareTo(rhs.name);
}
};
public abstract int compare(Child lhs, Child rhs);
public Comparator<Child> ascending() {
return this;
}
public Comparator<Child> descending() {
return Collections.reverseOrder(this);
}
}
}</pre>
<br />
Lovely! Other examples of the synergy effect I've seen recently are my earlier posted thread safe state pattern and <a href="http://weblogs.java.net/blog/giovanisalvador/archive/2008/04/refactoring_for.html">this blog entry</a>. In both those cases the synergy was better code structure and better performance.</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com7tag:blogger.com,1999:blog-7677021887363364182.post-29596864307088323092008-03-31T13:13:00.000-07:002017-04-24T12:32:54.713-07:00Java Thread-safe State Design Pattern<div dir="ltr" style="text-align: left;" trbidi="on">
<h2>
Thread-safe State</h2>
<br />
Apart from the things mentioned here, this pattern also conveys the intent and benefits of the GoF State pattern, being an extension thereof. The term "behaviour" is interpreted more strictly so that an object is always considered to change its behaviour when its state changes.<br />
<h3>
Intent</h3>
<br />
Make sure that an object is observable only in a valid consistent state and that transitions between valid consistent states are atomic and side-effects occur if and only if the associated transition occurs validly.<br />
<h3>
Motivation</h3>
<br />
Consider a class where behaviour depends on more than one field and/or side-effects occur as a result of certain state-changes. Such behaviour can be very difficult to analyze for thread-safety and the safe classic approach is to synchronize all methods. Such behaviour can also be difficult to analyze for logical correctness, bringing the motivation for the state pattern into play.<br />
<br />
The key idea is to leverage the state pattern and store the current state in an AtomicReference. Current state should be represented by an immutable object. State transitions are performed by a compareAndSet (CAS) operation and a retry on failure. For transitions with side-effects, the CAS is performed to a boilerplate blocking state, the side effects performed, the resultant state set and the blocking state released, whereby each thread released from the blocking state retries the attempted operation on the resulting state. The CAS always compares with the "this" reference of the state instance being transitioned from and can only succeed for one thread, all other threads attempting a simultaneous transition have to retry on the new state.<br />
<h3>
Applicability</h3>
<br />
Any object that has a method that has a more complex interaction with the object state than one of either a simple get or a simple set (in which case just marking the field volatile is simpler and more performant).<br />
<h3>
Structure (given as implementation examples)</h3>
<br />
Delegate all calls to an immutable state instance:<br />
<pre>
class Implementation implements Interface {
private final AtomicReference<interface> state;
public ... doSomething(...) {
return state.get().doSomething(...);
}
private class StateA implements Interface {
private final ... valueX;
private final ... valueY;
public ... doSomething(...) {
.... valueX ... valueY ...
}
}
}</interface></pre>
<br />
Simple state changes performed by CAS or retry:<br />
<pre>
class Implementation implements Interface {
private final AtomicReference<interface> state;
public void setX(y) {
state.get().setX(y);
}
private class StateA implements Interface {
private final ... x;
public void setX(y) {
if (!state.compareAndSet(this, new StateA(y))) {
state.get().setX(y);
}
}
}
}</interface></pre>
<br />
State changes with side-effects CAS to a blocking state first:<br />
<pre>
class Implementation implements Interface {
private final AtomicReference<interface> state;
public void printAndSetX(y) {
state.get().printAndSetX(y);
}
private class StateA implements Interface {
private final ... x;
public void printAndSetX(y) {
BlockingState guard = new BlockingState();
if (state.compareAndSet(this, guard)) {
try {
print(x);
state.set(new StateA(y));
} finally {
guard.release();
}
} else {</interface></pre>
<pre><interface> state.get().printAndSetX(y);</interface></pre>
<pre><interface> }
}
}
private class BlockingState implements Interface {
private final CountDownLatch latch = new CountDownLatch(1);
public void printAndSetX(y) {
try {
latch.await();
} catch (InterruptedException e) {
// Don't care.
}
state.get().printAndSetX(y);
}
private void release() {
latch.countDown();
}
}
}</interface></pre>
<br />
<h3>
Participants</h3>
<br />
<ul><br />
<li>Interface - defines the public interface.</li>
<br />
<li>Implementation - maintains an AtomicReference to current StateImplementation, implements the public interface.</li>
<br />
<li>StateImplementation - the implementation of the public interface for a particular state.</li>
<br />
<li>BlockingState - specialized boilerplate StateImplementation that blocks all calls until released and then delegates to the current state.</li>
</ul>
<br />
<h3>
Collaborations</h3>
<br />
<ul><br />
<li>Implementation delegates relevant (usually all) calls to the current StateImplementation.</li>
<br />
<li>StateImplementation performs state transitions by a state.compareAndSet(this, nextState) or retry the transition on the current state (which is different from "this" since CAS failed) so that each state object can only be transitioned from once.</li>
<br />
<li>BlockingState blocks all calls until released, thereupon retries on new current StateImplementation.</li>
</ul>
<br />
<h3>
Consequences</h3>
<br />
<ol><br />
<li>Interactions with the object always occur with a consistent state of the object, the immutability of the state delegate guaranteeing a consistent result of the interaction and each separate interaction is therefore in effect atomic.</li>
<br />
<li>State transitions are explicit and atomic.</li>
<br />
<li>Performance seems to be as good as or better than a straightforward non-thread-safe implementatin with mutable fields. Performance is better than that of synchronization (compare "optimistic locking" versus "read/write locking") for applicable objects if some interactions do not entail state changes, especially when the object is reachable from more than one thread (even if access is never contended).</li>
</ol>
</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com12tag:blogger.com,1999:blog-7677021887363364182.post-55304196847391247502008-03-23T23:23:00.000-07:002008-03-28T16:12:46.445-07:00Performance and thread-safe state handlingIn my <a href='http://tobega.blogspot.com/2008/03/thread-safe-state-handling.html'>previous post</a> I introduced using the state pattern and an AtomicReference to help maintain thread safety. My reason for starting to play with the pattern was really to make it easier to analyze the code and prove correctness, but obviously the question of performance inevitably comes up and it is interesting to know the trade-offs.<br /><br />I set up a benchmark where ten threads would simultaneously try to execute the same code and each thread would just hammer away for an obscenely large number of times. First up for the test was the simple lamp:<pre><br />public interface Lamp {<br /> boolean isOn();<br /> void setOn(boolean on);<br />}<br /></pre><br />The code to execute was:<pre><br /> b = lamp.isOn();<br /> lamp.setOn(!b);<br /></pre><br />I had an implementation with just a volatile field, an implementation with both methods synchronized, a hybrid implementation where the field was volatile and only the setter synchronized and an implementation using the state pattern. I also ran the bad non-thread-safe implementation. The results with the average time for one run through the code: volatile (669 ns), bad (697 ns), state (985 ns), hybrid (1570 ns), synchronized (2535 ns). Interestingly enough, the state pattern kicks butt. Actually the state pattern was even faster than volatile in the first tests I ran, but that is probably because I ran too few iterations to pay the full cost of garbage collection.<br /><br />So how about a predicted worst case, the CoffeeMachine where the state changes on every method call?<pre><br />public interface CoffeeMachine {<br /> void fillBeans(int beans);<br /> void fillWater(int water);<br /> Coffee makeCoffee(int water, int beans) throws OutOfWaterException, OutOfBeansException;<br />}<br /></pre><br />And the test code, same rules as above, ten threads whacking away:<pre><br /> Random r = new Random();<br />....<br /> int w = r.nextInt(5);<br /> cm.fillWater(w);<br /> int b = r.nextInt(3);<br /> cm.fillBeans(b);<br /> try {<br /> cm.makeCoffee(w,b);<br /> } catch (OutOfWaterException e) {<br /> oow.getAndIncrement();<br /> } catch (OutOfBeansException e) {<br /> oob.getAndIncrement();<br /> }<br /></pre><br />This was a straight shoot-out between a synchronized implementation and a state pattern implementation. Result: synchronized (5021 ns), state (5333 ns). A slight victory for synchronization, yeah!<br /><br />So how about adding some getters into the CoffeeMachine, how does that change things? The test code was changed to:<pre><br /> Random r = new Random();<br />....<br /> int w = r.nextInt(5);<br /> if(cm.checkWater() < w*10) cm.fillWater(w*100);<br /> int b = r.nextInt(3);<br /> if (cm.checkBeans() < b*10) cm.fillBeans(b*100);<br /> try {<br /> cm.makeCoffee(w,b);<br /> } catch (OutOfWaterException e) {<br /> ons.getAndIncrement();<br /> } catch (OutOfBeansException e) {<br /> offs.getAndIncrement();<br /> }<br /></pre><br />With the getters present it makes sense to try a hybrid approach again. Result: state (2547 ns), hybrid (3675 ns), synchronized (4930 ns).<br /><br /><b>Conclusion:</b> not only does the state pattern with an AtomicReference to an immutable internal state representation make it easier to manage code complexity, it is also beneficial from a performance point of view, being just slightly slower than synchronization in the worst case and twice as fast in normal cases.<br /><br /><b>Addendum:</b> My keen colleague, the informed sceptic, pointed out to me that perhaps some more testing is needed before it can be generally said that the state pattern is better performing. He claimed that normal usage is that threads do something else and then hit the shared resource, which results in the locks being mostly uncontended. I suppose he has a point. But how to test it?<br /><br />First attempt, just run my Lamp benchmark single-threaded: volatile (10 ns), synchronized (10 ns), bad (19 ns), hybrid (22 ns), state (42 ns). Oops! State pattern is 4 times slower than synchronized. Interesting also that plain old non-thread-safe code is slower than volatile and synchronized. The hybrid approach is twice as slow as synchronized. But what is going on here? We've run a long warm-up and then we're just whacking away at our Lamp from a single thread. Obviously HotSpot is able to do some nice things with the synchronized methods in this case (good to know).<br /><br />Next attempt, run a minimal warmup and a short time: volatile (10 ns), bad (18 ns), state (44 ns), hybrid (63 ns), synchronized (87 ns). So now we're not hitting it hard enough for HotSpot to do all its magic synchronized is dog slow again.<br /><br />Third attempt, hit the class hard from just two threads: bad (120 ns), volatile (121 ns), state (187 ns), hybrid (338 ns), synchronized (752 ns). But we're still hitting it hard. We need to figure out how to simulate the non-contention scenario with many threads.<br /><br />Fourth attempt, put in a sleep in each loop. No good, there's too much noise coming in from the calls to sleep(). For what its worth, the numbers are very similar, differences are less than 1% (duh!). We need another angle of attack.<br /><br />Just for a change of pace I decided to run the CoffeeMachine benchmark in one thread: state (114 ns), hybrid (160 ns) and synchronized (212 ns). Hmm, I realize I didn't really run single-threaded because there were two threads that had access to the CoffeeMachine object. One thread was just waiting for the other to finish, though, so all locks were uncontended. Trying that with Lamp I get: volatile (13 ns), bad (20 ns), state (42 ns), hybrid (65 ns) and synchronized (89 ns). It seems that uncontended locks are just as expensive as contended locks and HotSpot was able to do some powerful magic when the object was only accessible from one thread. Sanity check on CoffeeMachine running truly single-threaded: state (110 ns), hybrid (113 ns), synchronized (208 ns). Surprise! HotSpot couldn't do so much this time! I just have to check the performance against a standard non-thread-safe implementation: standard (123 ns) versus state (110 ns)!!!!<br /><br /><b>Conclusion 2:</b> The thread-safe state pattern is excellent to use as a standard pattern. As my eager colleague points out so often, the important thing is to be able to analyze the correctness of the code and performance is usually not so important. Well, the state pattern was originally evolved to make it easier to handle varying behaviour depending on state and transitions between these behavioural states, so that requirement is solidly fulfilled. For anything but the simplest of classes, the thread-safe state pattern also seems to be most performant way of achieving thread safety and actually performs better than an ordinary non-thread-safe implementation in at least the one case tested here.tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com0tag:blogger.com,1999:blog-7677021887363364182.post-82754627794148060602008-03-17T03:06:00.000-07:002018-11-19T05:00:10.762-08:00Thread-safe state handling<div dir="ltr" style="text-align: left;" trbidi="on">
In my <a href="http://tobega.blogspot.com/2008/03/is-synchronisation-expensive-is-that.html">previous post</a> I noted that handling mutable state in multi-threaded programs is a problem that should preferably be avoided. Sometimes it may be too complicated to avoid mutate state and I will in this post look into some ways of handling it, including how the classic State design pattern can help, with a little twist. A good, if old, introduction to threading issues in Java <a href="http://www.javaworld.com/jw-08-1998/jw-08-techniques.html">can be found here</a>.<br />
<br />
Consider the following code:<br />
<pre>
public class Lamp {
private boolean on;
public boolean isOn() {return on;}
public void setOn(boolean on) {this.on = on;}
}</pre>
<br />
No threading problems, right?<br />
<br />
Wrong! I had read about it but learnt it again the hard way when one of my unit tests started failing spuriously. I could tell from other measuring points that there was no way that assert could fail, yet it did, sometimes. The issue is that, especially on a multi-core machine, there is no guarantee that other threads will ever get to see changes. To guarantee that, either the same synchronization monitor must be used for both reads and writes, or the variable needs to be volatile.<br />
<br />
With that lesson in mind, let's look at another example:<br />
<pre>
public class WaterDispenser {
private volatile int water;
public void fill(int amount) { water += amount; }
public void get(int amount) throws InsufficientWaterException {
if (water >= amount) water -= amount;
else throw new InsufficientWaterException();
}
}</pre>
<br />
Unfortunately, += and -= are not atomic operations so two threads filling up at the same time may result in only the one fill being effective. Also there is a gap between the check and the decrement so the class may end up in an invalid state if two threads get water at the same time.<br />
<br />
It is always an option just to synchronize the methods and it may well be the best option in this case. It is when you have frequently used methods that just query the state that you want to avoid synchronization because it will give an overhead on every query.<br />
<br />
Just for illustration, let's use an AtomicInteger here, which has the same memory consistency guarantees as volatile and a bit of extra functionality. The addition in fill is now atomic, but in the get we also check that we have enough water so it's not good enough to just do an atomic subtraction after the check since that precondition may not be valid when we get to the subtraction, we have to atomically check that the value didn't change with a compareAndSet or redo.<br />
<pre>
public class WaterDispenser {
private AtomicInteger water;
public void fill(int amount) { water.addAndGet(amount); }
public void get(int amount) throws InsufficientWaterException {
int currentWater;
int nextWater;
do {
currentWater = water.get();
nextWater = currentWater - amount;
if (nextWater < 0) throw new InsufficientWaterException();
} while (!water.compareAndSet(currentWater, nextWater));
}</pre>
<br />
It becomes more and more complex to analyze and avoid race conditions the more you need to do, consider for example extending the WaterDispenser to become a CoffeeMachine, when you have to use coffee beans as well as water.<br />
<br />
The <a href="http://userpages.umbc.edu/~tarr/dp/lectures/StateStrategy.pdf">State pattern</a> is used to make it easier to analyze and express state-dependent behaviour. Not surprisingly, I suppose, it can also be used to simplify concurrent state-handling, although perhaps with a stricter interpretation of "state-dependent behaviour".<br />
<pre>
public class CoffeeMachine {
private AtomicReference<CoffeeMachineState> state = new AtomicReference<CoffeeMachineState>(new CoffeeMachineState(0,0));
public void fillBeans(int beans) {
state.get().fillBeans(beans);
}
public void fillWater(int water) {
state.get().fillWater(water);
}
public Coffee makeCoffee(int water, int beans) throws OutOfWaterException, OutOfBeansException {
return state.get().makeCoffee();
}
private class CoffeeMachineState {
private final int water;
private final int beans;
CoffeeMachineState(w, b) {
water = w;
beans = b;
}
void fillBeans(int moreBeans) {
if (!state.compareAndSet(this, new CoffeeMachineState(water, beans+moreBeans)) {
state.get().fillBeans(moreBeans);
}
}
void fillWater(int moreWater) {
if (!state.compareAndSet(this, new CoffeeMachineState(water+moreWater, beans)) {
state.get().fillWater(moreWater);
}
}
Coffee makeCoffee(int w, int b) throws OutOfWaterException, OutOfBeansException {
if (water < w) throw new OutOfWaterException();
if (beans < b) throw new OutOfBeansException();
if (!state.compareAndSet(this, new CoffeeMachineState(water-w, beans-b)) {
return state.get().makeCoffee(w,b);
}
return new Coffee(w,b);
}
}
}</pre>
Again it would probably be better to just sychronize the methods in this case, but it serves to illustrate the pattern: delegate calls to the current state, which either manages to change the state or delegates to the new state if another thread got in first.<br />
<br />
Back to the lamp example, which is a classic for the state pattern, but we'll add some functionality. The lamp is placed in a room and when we turn it on we should illuminate the room and when we turn it off we should darken the room. Now we have a gap between the state change and the room operation, a gap where another thread can come in and wreak havoc. The solution is to introduce a transitional state that holds other threads at bay while you complete the transition.<br />
<pre>
class Lamp {
private AtomicReference<Lamp> state = new AtomicReference<Lamp>(new Off());
private final Room room;
public Lamp(Room room) {this.room = room;}
public boolean isOn() {return state.get().isOn();}
public void setOn(boolean on) {state.get().setOn(on);}
private class On extends Lamp {
public boolean isOn() {return true;}
public void setOn(boolean on) {
if (on) return;
synchronized (Lamp.this) {
TransitionGuard guard = new TransitionGuard();
if (state.compareAndSet(this, guard) {
room.darken();
state.set(new Off());
} else {
state.get().setOn(on);
}
}
}
}
private class Off extends Lamp {
public boolean isOn() {return false;}
public void setOn(boolean on) {
if (!on) return;
synchronized (Lamp.this) {
TransitionGuard guard = new TransitionGuard();
if (state.compareAndSet(this, guard) {
room.illuminate();
state.set(new On());
} else {
state.get().setOn(on);
}
}
}
}
private class TransitionGuard extends Lamp {
public boolean isOn() {
synchronized (Lamp.this) {
return state.get().isOn();
}
}
public void setOn(boolean on) {
synchronized (Lamp.this) {
state.get().setOn(on);
}
}
}
}</pre>
<br />
Synchronizing would be easier, but with this pattern we only pay the synchronization cost during complex state transitions, although we do get a certain cost for object creations, but this is generally very low.<br />
<br />
One final word of caution: if using an object involves querying more than one of its stateful values, that is also a potential race and you should consider returning an immutable object representing a snapshot of all the queryable state instead.</div>
tobehttp://www.blogger.com/profile/00792674914237130365noreply@blogger.com9