Sean Foy

Book Review: The House of Wittgenstein

2011-12-31T13:35:00.009-06:00

This is a review of The House of Wittgenstein: A Family at War by Alexander Waugh.

This book traces the lives of four generations from the late nineteenth century to the early twenty-first. During this time: a great fortune was made in trade, real estate, and industry; a pianist lost his right arm but continued to perform at a world-class level of proficiency; a philosopher rose to international prominence; the family evaded Nazi persecution.

Some of the most interesting material for me concerns war time. For example, Paul was taken as a POW by the Russians during The Great War and was held at the krepostnaia katorga at Omsk. He was allowed to send letters home, but his letters do not describe the conditions for which the prison camp was infamous. Waugh notes that the Russians censored outbound letters and anyway many prisoners wanted to avoid worrying their families or felt shame for having been captured. Interestingly, the Austro-Hungarian Kriegsüberwachungsamt was censoring inbound mail:

Letters have been received lately from our prisoners of war in enemy countries. In some of these letters the writers describe life in captivity in a very favorable light. The spreading of such news among the troops and recruits is undesirable. The military censors are therefore to be instructed that such letters of our prisoners of war as may, by their contents, exercise an injurious influence are to be confiscated and not to be delivered to their addressees. [p. 75]

The Austro-Hungarian government funded the war by printing money and consequently there was severe inflation during the twenties; "by August 1922 paper money was virtually worthless as consumer prices rose to a level 14,000 times higher than they had been before the war" [p. 128]. Trade embargoes further hampered commerce with the result that 96% of Austrian children were malnourished [ibid]. For the Wittgensteins, this led to conflicts between siblings about philanthropic and investment decisions.

It is pretty interesting to see how the Wittgenstein's understanding of the Nazis developed during WWII. Initially they supported the Heimwehr austrofascists against the Nazis in opposition of Anschluss, socialism, "exaggerated racial theories," and "a semi-pagan German national religion". When the Germans invaded, the Wittgensteins were frustrated in their attempt to sell some art abroad and annoyed by the new administration's insistence that they fly the Nazi flag over their palais, but they did not fear for their personal safety until later. They seem to have underestimated the sincerity of Nazi leaders with respect to racial rhetoric. In fact, their immense wealth and political connections outside the Reich did save them from the concentration camps even as strategic and tactical disagreements irreparably inflamed tensions among siblings.

This extraordinary group of people during an extraordinary period of time makes for an engaging narrative. It is competently written and my impression is that it is well-researched, but I certainly read it with variable velocity and interest. I recommend this book to those who are interested in the economic and political history of early twentieth century Europe, and curious about seeing those events through the perspective of one prominent family.

Book Review: The Annotated Turing

2011-11-30T14:34:00.004-06:00

This is a review of The Annotated Turing by Charles Petzold.

The heart of the book is Turing's On Computable Numbers, with an Application to the Entscheidungsproblem, segmented and the segments interleaved with commentary and corrections from Petzold and Turing's own erratum. It is prefaced with some background material that will be a good refresher or even introduction for non-mathematicians. The end of the book draws connections between Turing and his/our contemporaries who carried forward his work.

Before this, my exposure to the Church-Turing Thesis had always been indirect, via the later works of Kleene and others. It was interesting to see some of the differences in the original presentation of these ideas. For example, I didn't realize or remember that the Halting Problem was introduced by Martin Davis; Turing himself discussed mainly "circle-free" machines that would never halt. I also liked that Petzold gives a rounder portrait of Turing by the inclusion of material on Turing's personal history.

I believe this book would be accessible to readers with no prior cs background. Check it out if you are interested in either computer science or the philosophy of mathematics.

Book Review: The Power Broker: Robert Moses and the Fall of New York

2011-10-31T23:38:00.006-05:00

Robert Moses was smart and got things done. He showed extraordinary idealism in his early adulthood, and worked hard to apply his wealth, privilege, and considerable talents in hopes of making the world a better place. Over his lifetime, he mastered realpolitik and wielded considerable power; from his relatively modest nominal appointments, he dominated not only mayors of New York City but also the statehouse and in one conflict a sitting President of the United States. The legacy of his most effective decades using billions of dollars to remake the neighborhoods of New York City and establish the pattern of development for Long Island will persist for centuries, to the chagrin of many.

Fittingly, this is a monumental biography with 1162 pages of main matter and followed by 84 pages of notes and references. It is occasionally indulgent, but on the whole I think it was well-edited. Moses was deeply flawed and immensely capable and driven; it is interesting to learn about how he amassed, used, and lost influence over his lifetime.

Book Review: The Time Traveler's Guide to Medieval England

2011-01-02T00:31:00.011-06:00

This is a book review of The Time Traveler's Guide to Medieval England by Ian Mortimer.

History is more fun without the politics

Context is a vital consideration for historical interpretation, but ask a history student to summarize what he's learned and you'll likely hear exclusively about famous people and events. Some of these people were colorful characters, and many of the events make for good stories. But this book focuses on the complement of that history, highlighting the crucial but normally subordinated milieu of an age.

Mortimer's guidebook tells of the customs, etiquette, food, clothing, laws, and economic conditions in which the 14th century English lived their lives. The book is written in a light-hearted style; it's a very entertaining way to cure some of your misconceptions and enrich your understanding of the period. Recommended.

Book Review: The Ghost Map

2011-01-01T01:00:00.019-06:00

This is a review of The Ghost Map by Steven Johnson.

Johnson's account of John Snow, Henry Whitehead, and other key figures in the story of a nineteenth century London cholera epidemic is an engaging narrative with insights about scientific investigation and persuasive argument. Starting with an orientation to London c. 1854, the heart of the book explains how a particularly perspicacious investigator developed and tested hypotheses to reach correct and influential conclusions. Along the way we see how somewhat different approaches led others to different outcomes. Of course, the process of scientific discovery remains relevant to us in the 21st century, as are many of the issues concerning urban design and public policy.

The Broad Street cholera epidemic of 1854 was in large part a consequence of urbanization with inadequate public works infrastructure, at a very early stage in the development of medical science and microbiology. Particularly in the last chapter, "Broad Street Revisited," Johnson discusses the relation between 1854 London and present-day first-world city planning. Citing Jane Jacobs and other contemporary sources, he discusses the architecture of cities, the role of government organizations such as the CDC, and even the War on Terror and nuclear non-proliferation. I think he overreached in this attempt to reinforce the continuing relevance of the Snow/Whitehead collaboration and to advocate for positions on tenuously connected modern issues.

Readers of Tufte's Visual Explanations will recognize this epidemic from several pages in that book (it was also mentioned in The Visual Display of Quantitative Information). While Tufte focuses on an analysis of Snow's compelling maps as designed artifacts, Johnson describes in detail the scientific inquiry that led to the development of those maps. Johnson also offers a short critique of Tufte's treatment. It is disappointing that after describing Snow's second-edition Voronoi-enhanced map (see also) as "Snow's most significant contribution to the field of disease mapping" and calling out Tufte on having overlooked it, Johnson omits the diagram from his own book.

The Ghost Map includes end notes, but the note numbers appear only in the notes and not in the text. The absence of a visual indication that more detail is available makes the end notes less likely to be used and made me less trusting about some of the author's assertions.

I have pointed out some weaknesses in The Ghost Map, but on the whole I think it was well worth reading. If you are interested in Snow's maps, the history of epidemiology, or the process of scientific inquiry, I heartily recommend this book.

Palindromic Pangrams

2010-04-22T16:48:00.032-05:00

This post details a solution to a disused hiring problem. If you are a graph search wiz, you will find yourself skimming; I assume readers either haven't done this before or have forgotten it mostly. Even experts might be interested in the pathology, so hopefully there's something here for everyone to enjoy.

I've been unusually quiet lately because I'm in the midst of a truly marathon interview cycle. The things I'm working on probably aren't interesting to other people, and they're taking up all of my time. But before this began I spent some time working on a hiring puzzle that I think is blog-worthy.

I couldn't share the details of my approach at the time that I was actively working on the problem, because that would hurt the company and other candidates by raising the question of plagiarism. In fact, ITA removed the problem I was working on from their web site, and when I wrote their recruiter to ask why, I found out it was because somebody else wrote about it! Now it seems the rumor that Google is acquiring ITA is confirmed and some people are talking about other hiring problems. So I'm doubly sure it's OK to post this now.

First, the problem specification:

A palindrome is a sequence of words like "lid off a daffodil" or "shallot ayatollahs" that uses the same letters reading backwards as forwards. The words need not form a meaningful or grammatical sentence. A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Find the shortest sequence of words that is both a pangram and a palindrome.

That sounded like something that could occupy me for a few hours. Of course ITA would have chosen the dictionary so that brute-force approach wouldn't be fast enough, but with a reasonable choice of data structures and algorithms, it shouldn't be too hard. Writing up my solution would require lots of care; I imagined it would be carefully code reviewed to see if I was worth talking to, in which case I'd spend most of the interview defending my solution and talking about how it could be improved. Maybe several days to edit for clarity and efficiency and so on. I wound up spending weeks trying with some success to make it run faster. Besides learning some python, some humility and having an excuse to actually do things I'd previously only read about, I learned this lesson: the point of solving a puzzle is to GET A PHONE SCREEN. That's all. It was fun, but I won't repeat the mistake of undertaking substantial work without feedback.

If you want to play along at home, pause reading here and resume when you're happy with your own solution to compare notes.

Enough introduction. Let me show you some code along with commentary based on my notes. I started with a little brainstorming. I'll give you the main points first and then give a more thorough discussion later.

A quick note on optimization terminology: an optimization problem is normally posed with a set of constraints and an objective function. For example, the constraints for this problem specify that we are only interested in pangrams, and we are only interested in palindromes. We call solutions that satisfy the constraints feasible. The objective function grades the goodness of feasible solutions. For example, in this case our objective function is phrase length. An optimal solution is a feasible solution for which no other feasible solution is scored better by the objective function.

First observation: For each letter, some word in our pangram must contain that letter.

First idea: beam stack search word-sets.

Elaboration: Here I'm considering pangram formation as a search problem in the space of words organized by letter inclusion. Each dictionary word is a child of the empty root node. Each node has the complement of dictionary words represented by its (improper) ancestors as children. Assuming a small constant bound c on word length, classifying words will cost |words| * 26 * c = O(n). Among sibling nodes, I can prioritize words containing the rarest letter in order to avoid unfruitful branches. Even so, the six-figure branching factor gives a very big search space.

Second observation: For each prefix p of the letter-sequence of the pangram, the reverse of p must exist in some concatenation of words.

Second idea: use a trie for reversed words to help prune the search for palindromes. The overall search tree has min(n, 26^c)! nodes, so let's only build tries for feasible word-sets.

We need a formal definition of our goal:


def palindromeP(seq):
   """ Characteristic fn for palindromes.

   >>> palindromeP(['a'])
   True

   >>> palindromeP(['a', 'b', 'a'])
   True

   >>> palindromeP(['ab', 'c', 'ba'])
   True

   >>> palindromeP(['ab', 'c', 'ab'])
   False
   """
   return (lambda p: p[:int(len(p)/2)] == (p[int(math.ceil(len(p)/2.0)):])[::-1])(''.join(seq))

For those who don't use python, the triple-quotes delimit a docstring comment, and what looks like a toplevel transcript is a doctest specification showing inputs and expected outputs. The code just says that we are concerned with the concatenation of the given sequence: when the first half matches the reverse of the second half, we have a palindrome.

The definition of pangram depends on the letters that comprise our candidate solution:


class Histogram:
   def __init__(self, seq):
       self.h = collections.defaultdict(set)
       for s in seq:
           for i in s:
               k = i.lower()
               self.h[k].add(s)
   def __len__(self):
       return len(self.h)
   def __getitem__(self, key):
       return self.h[key]
   def __iter__(self):
       if (not hasattr(self, 'ordered_h')):
           self.ordered_h = sorted(self.h.items(), key = lambda xy: -len(xy[1]))
       return self.ordered_h.__iter__()
   def top(self):
       for x in self.__iter__():
           return x[1]
   def __repr__(self):
       return '(Histogram %s)' % self.h.__repr__()

The histogram is a glorified dictionary mapping letters to words. It participates in the python idiomatic iteration scheme by partially ordering its values by overall letter frequency.


def pangramP(seq):
   """
   Characteristic fn for pangrams.
   (assumes the alphabet is limited to A-Za-z)

   >>> pangramP([''])
   False

   >>> pangramP(['a'])
   False

   >>> pangramP([string.ascii_lowercase])
   True

   >>> pangramP(dict((x, x) for x in string.ascii_lowercase))
   True
   """
   if isinstance(seq, collections.KeysView):
       h = seq
   elif isinstance(seq, str):
       h = set(seq)
   elif isinstance(seq, collections.Mapping):
       h = seq.keys()
   elif isinstance(seq, Histogram):
       h = seq
   else:
       h = Histogram(seq)
   return len(h) == 26

Now, let's look at the search implementation. I've characterized the problem in terms of tree search, so I need a representation for nodes:


class WordSetNode:
   def __init__(self, word, parent = None):
       if not hasattr(word, '__iter__'):
           word = str(word)
       self.word = word
       self.parent = parent
       self.covered = dict.fromkeys(word)
       if parent:
           self.covered.update(self.parent.covered)
   def coveredP(self, letter):
       return letter in self.covered
   def pangramP(self):
       return pangramP(self.covered.keys())
   def ancestors(self):
       n = self
       while (n):
           yield n
           n = n.parent
   def phrase(self):
       return reversed([n.word for n in self.ancestors() if n.word])
   def phrase_string_ns(self):
       if not hasattr(self, 'phrase_string_ns_cache'):
           self.phrase_string_ns_cache = ''.join(self.phrase())
       return self.phrase_string_ns_cache
   def __repr__(self):
       if not self.parent:
           return "WordSetNode('%s')" % self.word
       return "WordSetNode('%s', %s)" % (self.word, repr(self.parent))

The first thing you might notice is that I have backlinks from children to parents, and a very odd thing you'll notice is that I have no edges from parents to children! I'm not planning to build a tree and then search it for solutions. I want to build my tree on-demand in order to avoid needless computation and limit my memory footprint. Basically, I move from parents to children by generating nodes rather than by following a path through some pre-existing structure. The backlinks are there for convenience.

As in the sketch above, the tree search is a quest for pangrams having the palindrome property, so nodes are viewed as contributing letter-coverage and paths through the tree represent words in the overall pangram. I cache information about the path to each node along the way.

So, about those pangrams: my idea for pruning infeasible word-sequences involved prefix trees ("tries"). This is the first time I've used them in real life, so I will remind you that prefix trees are all about paths; the element data aren't associated with particular nodes but rather with paths from the root. It's very efficient for queries of the form: which elements have x as a prefix? In this case, my trie nodes will represent letters; the trie itself represents a collection of letter-sequences:


class Trie:
   def __init__(self, seq = []):
       if type(seq) == type(''):
           seq = [seq]
       self.terminus = False
       self.children = {}
       for i in seq:
           self.add(i)
   def emptyP(self):
       return not self.children
   def match(self, word):
       """Find the deepest subtrie representing
       a prefix of word, and the remaining suffix.

       >>> Trie().match('')
       (Trie(), '')

       >>> Trie().match('abc')
       (Trie(), 'abc')

       >>> Trie('abc').match('')
       (Trie(['abc']), '')

       >>> Trie('abc').match('a')
       (Trie(['bc']), '')

       >>> Trie('abc').match('aac')
       (Trie(['bc']), 'ac')

       >>> Trie(['abc', 'aac']).match('achtung')
       (Trie(['ac', 'bc']), 'chtung')

       >>> Trie(['abc', 'aac']).match('aardvark')
       (Trie(['c']), 'rdvark')
       """

       if not word:
           return (self, word)
       if not word[0] in self.children:
           return (self, word)
       return self.children[word[0]].match(word[1:])
   def add(self, word):
       if not word:
           self.terminus = True
           return
       subtree, remainder = self.match(word)
       if not remainder:
           # mark the word if it's not already marked
           return subtree.add('')
       subtree.children[remainder[0]] = Trie([remainder[1:]])
   def search(self, w):
       quarry, remnant = self.match(w)
       if remnant:
           return None
       return quarry
   def traverse(self, preorderVisit, postorderVisit, prefix = ''):
       preorderVisit(self, prefix)
       for c in self.children.items():
           c[1].traverse(preorderVisit, postorderVisit, prefix + c[0])
       postorderVisit(self, prefix)
   def pre_order_nodes(self, ancestry = None):
       if ancestry is None:
           ancestry = []
       yield (self)
       for c in self.children.items():
           for i in c[1].pre_order_nodes():
               yield i
   def words(self, prefix = ''):
       if self.terminus:
           yield prefix
       for c in self.children.items():
           for l in c[1].words(prefix + c[0]):
               yield l
   def __repr__(self):
       W = ', '.join(repr(w) for w in sorted(self.words()))
       if W:
           return "Trie([%s])" % W
       else:
           return 'Trie()'

a trie representing {a, daffodil, lid, lug, off, offset}

As I explore my overall search tree, building up a sequence of words, I want to ensure that that my sequence has palindromic symmetry. I can do this by querying a trie-filled-with-reverse-words for my current search tree path.

The basic idea seems OK, but I haven't addressed word segmentation within the pangram. We disregard whitespace in the problem definition, so we can't limit our search to pangrams with word-length symmetry. We've got to account for "massive … sam" wherein we could reach a terminal node of the prefix trie of reversed words before exhausting letters in the current search path.


def loopyTrieSearch(t):
   """Produce a function that searches
   a trie augmented with backedges from
   each leaf to the root.
   >>> t = Trie()
   >>> s = loopyTrieSearch(t)
   >>> s(t, 'unmatchable')
   >>> t = Trie(['abc', 'aac', 'b'])
   >>> s = loopyTrieSearch(t)
   >>> s(t, '')
   [Trie(['aac', 'abc', 'b'])]

   >>> s(t, 'a')
   [Trie(['ac', 'bc'])]

   >>> s(t, 'ba')
   [Trie(['ac', 'bc'])]

   >>> s(functools.reduce(Trie.merge, s(t, 'b')), 'ab')
   [Trie(['c'])]

   >>> s(t, 'az')
   >>> t = Trie(['ab', 'abc', 'd'])
   >>> s = loopyTrieSearch(t)
   >>> s(t, 'abd')
   [Trie([''])]

   >>> s(t, 'azzz')
   """
   def s(t2, w):
       ctx = t2 if isinstance(t2, collections.MutableSequence) else [t2]
       if w == '':
           return ctx
       for l in w:
           for i in ctx:
               if i.terminus:
                   ctx.append(t)
                   break
           ctx = [j[0] for j in (i.match(l) for i in ctx) if j[1] == '']
       if not ctx:
           return None
       return ctx
   return s

From these ideas, I built a program that ran very nicely on a contrived, tiny, dictionary, but when I ran it on the 200kword ITA dictionary, my cpu fan revved to 100% and stayed there indefinitely. I should show some profiling data here.

How could I build my search tree more cheaply? Initially, to generate a node's children, I would take my letter-coverage dictionary's complement to see what letters I needed. I'd find all the words that could contribute a needed letter. For each word, I'd use my loopyTrieSearch. This tactic does avoid exploring infeasible branches, but it involves a lot of unsuccessful trie queries. What if I started by loopyTrieSearching the prospective parent's path, and then considering the loopy suffixes as possible words containing a needed letter?

Consider a trie pair (A, B) with A containing "awk" and "awkward" and B containing only "awesome." The naive approach requires us to conduct separate trie searches for "awk" and "awkward," both times stopping when we fail to match the ks. The improved approach allows us to simultaneously eliminate both words as soon as we find that "aw" has no child "k." If the average branching factor in the trie over all words (26 at most) is less than the average number of words associated with each letter (200000/26), then the latter could be a superior tactic. This is the purpose of the Trie.filter method:

class Trie: # ... def filter(self, criteria, root = None): """Return the words in this trie that match the augmentation of criteria by the addition of backedges from terminals to the root. >>> sorted(w for w in d if s(T, w)) == [w for w, i in itertools.groupby(sorted(FT.filter(T)))] True """ def f(words, crit, prefix = ''): if words.terminus: yield prefix if words.emptyP(): return backedge = root.children.items() if crit.terminus else () for c in itertools.chain(crit.children.items(), backedge): m = words.match(c[0]) if m[1] != '': continue for w in f(m[0], c[1], prefix + c[0]): yield w if not root: root = criteria for i in f(self, criteria): yield i @staticmethod def merge(a, b): """Merge two tries. >>> Trie.merge(Trie(['a']), Trie(['b'])) Trie(['a', 'b']) >>> Trie.merge(Trie(['abc']), Trie(['bcd'])) Trie(['abc', 'bcd']) >>> Trie.merge(Trie(['abc', 'aac']), Trie(['abe'])) Trie(['aac', 'abc', 'abe']) """ result = Trie() result.children = a.children.copy() for k, v in b.children.items(): if k in result.children: result.children[k] = Trie.merge(v, result.children[k]) else: result.children[k] = v result.terminus = a.terminus or b.terminus return result

For this, I'll use a pair of tries, one reverse and one forward. My search path corresponds to paths in each of those tries; as I query in the trie pair I need never pursue a branch that's available in only one of the tries.


class TriePair:
   def __init__(self, W, Wr = None):
       if not Wr: Wr = W
       self.fwd = W if isinstance(W, Trie) else Trie(W)
       self.rev = Wr if isinstance(Wr, Trie) else Trie(w[::-1] for w in Wr)
       self.s = loopyTrieSearch(self.rev)
   def expand(self, node, advisoryBudget = None, peek = True):
       self.setupContinuation(node)
       if not node.trieContinuation: return
       if peek and node.pangramP() and not node.parent.pangramP():
           # don't peek in the recursive expansion
           for i in self.completePalindrome(node, expand = functools.partial(self.expand, peek = False)):
               yield i
       W = itertools.chain(*(self.fwd.filter(c, self.rev) for c in node.trieContinuation))
       awords = set(a.word for a in node.ancestors())
       for w in set(W):
           if w in awords: continue
           n = WordSetNode(w, node)
           # if pangram and \exists a word matching some trie
           #  path to a leaf -> generate the easy palindrome
           n.setupContinuation = self.setupContinuation
           yield n

I mentioned earlier that the search tree is constructed during the search process. The expand function does that work, producing the child nodes of each parent. I'll explain peeking later. It would be possible to query our search tries for the string corresponding to our path whenever we expand a node, but then each descendent must redo its ancestors' trie search work. So, we copy the parent's search context into a cache (trieContinuation) on each child in order to avoid that extra work:


class TriePair:
# ...
   def setupContinuation(self, n):
       if hasattr(n, 'trieContinuation'):
           return
       elif self == n and hasattr(n, 'setupContinuation'):
           n.setupContinuation(n)
       elif n.parent and hasattr(n.parent, 'trieContinuation'):
           n.trieContinuation = (
               self.s(n.parent.trieContinuation,
                      n.word))
       else:
           n.trieContinuation = (
               self.s(self.rev,
                      n.phrase_string_ns()))

Let's take a closer look at beam-stack search.

Recall that depth-first search always expands the deepest unexplored node, while breadth-first search always expands the shallowest unexplored node. Depth-first search uses memory proportional to the longest path to a leaf; breadth-first search uses memory proportional to the size of the largest layer, O(d^b) where d is the longest path to a leaf and b is the branching factor at each node. For many problems, the better of two feasible solutions is the one closer to the root, and for these problems breadth-first search finds good solutions faster than depth-first search (which can pay an infinite penalty for unlucky early expansions).

Best-first search algorithms take an intermediate course between depth-first and breadth-first search. They choose which node to expand next by applying a heuristic. A* is a well-known such algorithm, and it's the basis for beam-stack search. The exploration order (denoted f(n) = g(n) + h(n)) takes into account both the (known) cost of each node's path from the root (g(n)) and the (estimated) cost of its path to a solution (h(n)). The estimation must be conservative in the sense that it never overestimates a potential solution's cost; this allows admissible pruning: once we've found a solution, we can safely avoid expanding any subtrees with higher cost estimates.

Best-first search can degenerate into breadth-first search in the worst case for memory use; beam-stack search addresses real-world memory constraints by enabling inadmissible pruning without compromising completeness (we will find a solution if one exists) or optimality (no solution is better than the one we find). Beam-stack search does this by keeping metadata proportional to the depth of the search that allows it to backtrack, regenerating and thoroughly exploring inadmissibly pruned nodes after it has explored the more promising portion of the graph.

Note that beam-stack search is an anytime algorithm: it strives to return a feasible solution ASAP and then to return improved solutions as they discovered. It is also complete and optimal, so it will definitely return a solution if any exists and the final solution it returns is guaranteed to be at least as good as any that exist.

The following graphs illustrate the progress of a beam-stack search on a small graph with a simple cost function and heuristic.

Bounds on the f-cost of child nodes are associated with each layer. Initially, we consider all possible children. Whenever we generate a child, we check for solution feasibility.

For each node, we can compute the (certain) g-cost of the partial solution and the (guessed) h-cost of the potential solution descendent of the node. In this example, we assume that g is phrase length (not including spaces) and h is the number of letters we need to add to produce a pangram. These are sensible, if naive, assumptions for the pangramic palindrome problem. But, to keep this example small, we will cheat by using an easier feasibility predicate: we will accept any palindrome; pangrams are not required.

When memory is limited, we inadmissibly discard some children, updating the parent layer upper bound accordingly. If backtracking proves necessary, we can use the upper bound to regenerate only the inadmissibly discarded children, thus avoiding duplicated work. Assuming a beam width of 2 nodes, we partition the set of children by f-cost. In this case, a and lid survive while off and daffodil are pruned.

We are ready to expand the frontier.

The layer exceeds our memory threshold, so it's time to prune again.

We retain the most promising nodes and update the layer bound.

We are ready to expand the frontier.

Our frontier exceeds our memory limit, but I think I've made the point about pruning so let's double the limit to 4. OK then we can expand again.

If the dictionary contains only the words {lid, off, a, daffodil} then we are unable to expand beyond this point without duplicating words. Notice that we have yet to find any palindromes. Because we cannot go forward, we must go backtrack.

We backtrack to the deepest layer at which inadmissible pruning occurred (i.e., where the upper bound is finite). There, we update the bounds to show that we have fully explored the space below the upper bound; now we will consider the space above. We are ready to expand the frontier.

Inadmissible pruning works just the same after backtracking as before. To see this, let's tighten the memory limit back to two.

As ever, we remove the nodes with high f-cost.

We are ready to expand the frontier.

This layer exceeds our memory limit, so we need to prune.

We discard unpromising nodes.

We are ready to expand the frontier.

We find a feasible solution on the frontier: lidoffadaffodil. This is a proof by example of the maximum cost of the optimal solution to our problem. Our heuristic is admissible, meaning that it never underestimates the cost of the best solution that uses a given node. Therefore, from now on, we can admissibly prune nodes whose f-cost exceed the f-cost of our candidate solution. The memory limit might still cause us to do some inadmissible prunings in the future, and in that case we might need to backtrack. But, admissible prunings never create an obligation to backtrack. If we continue from here, we will eventually exhaust the space between 27 (where we inadmissibly pruned some nodes) and 35 (where we have a solution) and determine that in fact we have an optimal solution.

So here are the parts to our cost function f:


def g(n):
   # sort of like
   #   lambda n: sum(len(w.word) for w in n.ancestors())
   # but with caching
   if not hasattr(n, 'g'):
       result = len(n.word)
       if n.parent:
           result += g(n.parent)
       n.g = result
   return n.g
def h(n):
   """Admissible heuristic estimate of cost
   remaining from this node.

   >>> h(WordSetNode('a')) == h(WordSetNode('aa'))
   True

   Though admissible, it's reasonable tight.
   >>> minimalCost = 26 * 2 - 1
   >>> inadmissibleMargin = 1
   >>> n = WordSetNode('a')
   >>> h(n) > minimalCost - inadmissibleMargin - len(''.join(n.phrase()))
   True
   """
   phrase_width = g
   tie_breaker = .01 * len(n.word) + .01 * abs(hash(n.phrase_string_ns()))/float(sys.maxsize)
   covered = len(n.covered)
   completely = len(string.ascii_lowercase)
   # The symmetry of the palindrome guarantees
   # that the first half is a pangram. So,
   # there's no use evaluating palindrome-dness
   # until we have a pangram.
   if covered < completely:
       # descendent nodes must:
       #   cover the missing letters on the left
       #     (just to the right of n)
       #   match the missing letters on the right
       #     (with a possible exception at the pivot)
       #   match what we have so far
       # TODO: improve this estimate by:
       #   (a) looking ahead in the trie for the missing
       #       letters
       #   (b) using the max_missing(min(len(word) | missing \in word))
       #       rather than 1 for the cost component due to
       #       missing letters
       missing = completely - covered
       # strategy b:
       # this doesn't help: when letterCosts
       # wins the max, we lose our ability to
       # distinguish between nodes that help
       # us gain coverage and nodes that do not.
       #needed = max(missing + (missing - 1), max(letterCosts[i] for i in string.ascii_lowercase if not i in n.covered))
       needed = missing + (missing - 1)
       return phrase_width(n) + needed - tie_breaker
   else:
       return palindrome_balance(n) - tie_breaker

And here's how those functions are used, along with parameters for tuning memory use (beam_width), the upper bound on cost for solutions we're willing to accept (U), a predicate to control which intermediate solutions we yield, and a way to inject a stack (which is handy for resuming cancelled searches):


def bss(nodes, expand, g, h, beam_width, U = sys.maxsize, feasibleP = lambda n: False, stack = None):
   """Beam-stack search, a variation on
   breadth-first branch and bound with
   backtracking.

   >>> [i for i in bss([], None, lambda n: 1, lambda n: 1, 10)]
   []

   >>> [i for i in bss([1], lambda n: [], lambda n: 1, lambda n: 1, 10)]
   [1]

   >>> sorted([i for i in bss(range(15), lambda n: [], lambda n: 1, lambda n: 1, 10)])
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

   >>> sorted([i for i in bss(range(5), intexpand, lambda n: 1, lambda n: 0, 3)])
   [1, 2]

   """
   def dedup(frontier):
       # This is a warning rather than an error:
       # some nodes really are equivalent though
       # not identical. For example, spaces don't
       # matter in pangramic palindromes.
       frontier = sorted(frontier, key = lambda p: p[0])
       groupedFrontier = (
           itertools.groupby(
               sorted(frontier,
                      key = lambda p: p[0]),
               lambda p: p[0]))
       frontier = []
       for i in groupedFrontier:
           elts = list(itertools.islice(i[1], 2))
           if (len(elts) <= 1):
               frontier.extend(elts)
           else:
               frontier.append(elts[0])
               print('f needs nuance: these nodes have the same f-cost: %d = f(%s) = f(%s)' % (elts[0][0], ' '.join(elts[0][1].phrase()), ' '.join(elts[1][1].phrase())))
       return sorted(frontier, key = lambda p: p[0])
   def prune(frontier, beam_width):
       if len(frontier) <= beam_width:
           f_max = frontier[-1][0]
           print('pruned nodes, new f_max = %s' % f_max)
           return frontier, f_max
       # We'll never backtrack to the nodes
       # we're pruning, even if these nodes
       # are never admissibly discarded.
       # beam_width may be smaller than the largest
       # equivalence class defined by f.
       # Ideally, these classes should contain
       # one node each; otherwise it's difficult
       # to choose a beam width that will avoid
       # splitting an equivalence class.
       s = dedup(frontier)
       retained, pruned = s[:beam_width], s[beam_width:]
       return prune(retained, beam_width)

   # 63: verbify ma pluck now sh ad go jo zax eta qat ex azo jog dahs wonk culpa my fib rev
   # 65: buckrams donzel ti pyx of vug we jo hm suq us mho jew guv foxy pit lez nods mark cub
   # 65: verbify na ducks to hm we jo zax al pig suq us gip lax azo jew mho tsk cud any fib rev
   # 67: bonked vulgars ti hm oy cap wo jo zax if suq us fix azo jow pac yom hits rag luv de knob
   # 69: verbify locks twang up mho zax ed ma jab suq us ba jam dex azo hm pug naw tsk coly fib rev
   # 71: verbify lock nut spaz we jig am dex eh ta qua sau qat hexed magi jew zap stunk coly fib rev
   # 76: drawknife butyls go hm op ox azo jo we vac suq us suq us cave wo jo zax op om hog sly tube fink ward
   # 86: de but way xi sh on vug la ef pa me re ka jo ah coz om ta qat ta qat mozo chao jake remap feal guv noh six yaw tubed
   # 92: drawknife butyls go hm op ox azo jo we vac suq usherettes setter eh suq us cave wo jo zax opo mho g sly tube fink ward
   # 101: underflow machs ti by xi pe ka jo zag eve suq aimu umiaq use vega zo jake pixy bits h cam wolfr ed nu

   f = lambda n: g(n) + h(n)
   if not stack:
       oldFrontier = [(f(i), i) for i in nodes]
       for i in filter(lambda x: feasibleP(x[1]), oldFrontier):
           U = min(U, g(i[1]))
           yield i[1]
       oldFrontier = [i for i in oldFrontier if i[0] < U]
       stack = [[0, U, oldFrontier]]
   j = 0
   while stack:
       f_min, f_max, oldFrontier = stack[-1]
       print('f_min, f_max, level = %s, %s, %d' % (f_min, f_max, len(stack)))
       if oldFrontier: print('sample phrase: %s' % ' '.join(oldFrontier[0][1].phrase()))
       frontier = []
       for i, o in enumerate(oldFrontier):
           visit(o[1])
           j += 1
           if not j % 32: print('nodes expanded: %d' % j)
           k = 0
           for n in expand(o[1], advisoryBudget = f_max):
               k += 1
#                if not k % 8196: print('progress on frontier: %d' % k)
               if feasibleP(n):
                   gn = g(n)
                   if gn >= U: continue
                   # g-values are integers, and f
                   # is admissible, so all the f-values
                   # above g - 1 have f-cost at least
                   # as high as g (i.e., they're no
                   # better than this solution).
                   U = gn - 1 + (1.0 / sys.maxsize)
                   f_max = U
                   yield n
                   oldFrontier[i + 1:] = filter(lambda p: p[0] < U, oldFrontier[i + 1:])
                   continue
               p = (f(n), n)
               if f_min < p[0] < f_max:
                   frontier.append(p)
                   if len(frontier) > beam_width * 2:
                       frontier, f_max = prune(frontier, beam_width)
       # filter, sort, reduce equivalence classes to class representatives
       prior_frontier = list(frontier)
       frontier = filter(lambda p: p[0] <= f_max, frontier)
       frontier = dedup(frontier)
       if not frontier:
           # backtrack
           print('empty layer -> backtracking from %d to' % len(stack), end=' ')
           while stack and stack[-1][1] >= U:
               stack.pop()
           print(len(stack), end=' ')
           if stack:
               frame = stack[-1]
               frame[0], frame[1] = frame[1], U
               frame[2] = list(filter(lambda n: n[0] < end="'')

Now, a very obvious improvement can be had by noticing that we guarantee palindromes by construction. Once we attain the pangram property, it's entirely straightforward to complete the palindrome. I call that "peeking." Here's a way to take the short-cut at the appropriate moment during bss:


class TriePair:
   # ...
   def pivotH(self, n):
       revCompletions = self.s(self.rev, n.phrase_string_ns())
       completionWords = itertools.chain(*(t.words() for t in revCompletions))
       return min(len(w) for w in completionWords) - (32 - len(n.word)) / 32 - abs(hash(n.phrase_string_ns())) / sys.maxsize / 64
   @staticmethod
   def rightH(n, expected_length):
       return expected_length - sum(len(i) for i in n.phrase()) - abs(hash(n.phrase_string_ns())) / sys.maxsize
   def rightExpand(self, n, match, len_left):
       """Restricted search space for quickly finding
       pangramic palindrome completions.
       >>> left = 'drawknife butyls go hm op ox azo jo we vac suq us'.split()
       >>> right = 'suq us cave wo jo zax op om hog sly tube fink ward'.split()
       >>> extraneous = ['opossum']
       >>> palindrome = left + right
       >>> tries = TriePair(palindrome + extraneous)
       >>> all(tries.fwd.match(i)[1] == '' for i in palindrome)
       True
       >>> n = functools.reduce(lambda a, i: WordSetNode(i, a), left, None)
       >>> match = ''.join(left)[::-1]
       >>> rx = functools.partial(tries.rightExpand, match)
       >>> x = list(rx(n))
       >>> [i.word for i in x]
       ['suq']

       >>> n = functools.reduce(lambda a, i: WordSetNode(i, a), itertools.chain(left, itertools.takewhile(lambda p: p != 'op', right)), None)
       >>> m, r = tries.fwd.match('op')
       >>> r == '' and sum(1 for i in m.words()) > 1
       True

       >>> [i.word for i in list(rx(n))]
       ['op']

       >>> n = functools.reduce(lambda a, i: WordSetNode(i, a), palindrome[:-1], None)
       >>> palindrome[-1] in (i.word for i in list(rx(n)))
       True
       """
       m = match[sum(len(i) for i in n.phrase()) - len_left:]
       r = self.fwd.match(m)[1]
       nextWordSupersequence = m[:-len(r)] if r else m
       for i in self.fwd.filter(Trie([nextWordSupersequence]), Trie()):
           yield WordSetNode(i, n)
   def completePalindrome(self, pangram, expand, f_max = sys.maxsize, match = None, left = None):
       # the pivot of the palindrome can be anywhere
       # left of the last letter needed for the pangram.
       # So it could be in the rightmost word of pangram,
       # or it could be in words yet to be added to our
       # phrase. We'll expand the pangram in the usual
       # way elsewhere, so we don't need to be complete
       # here. We do need to remain feasible, however.
       # Our strategy here is to find a pivot that
       # coincides with a word boundary, so that we can
       # use the reverse of the phrase as the sequence
       # of letters to appear on the right. This will
       # give us a much faster way to complete a
       # palindrome and establish a tighter upper bound
       # for the rest of our search.
       # TODO: also check for more interior pivots by
       # extending keystoneP to enumerate all possible
       # interior pivots rather than just the first one.
       #  ababa -> 1, 2, 3
       if match and left:
           len_match = len(match)
           len_left = len(left)
           rx = functools.partial(self.rightExpand, match = match, len_left = l
           rh = functools.partial(TriePair.rightH, expected_length = len_left + len_match)
           print('building right with match = %s and left = %s' % (match, left))
           for completion in bss([pangram], rx, g, rh, 1, len_left + len_match + 1/sys.maxsize, feasibleP):
               yield completion
           return
       if keystoneP(pangram.word):
           match = pangram.parent.phrase_string_ns() + pangram.word[:keystoneP(pangram.word)]
           for i in self.completePalindrome(pangram, expand, f_max, match = match, left = pangram.phrase_string_ns()):
               f_max = min(f_max, g(completion))
               yield i
       for left in bss([pangram], expand, g, self.pivotH, 1, f_max, lambda n: any(t.terminus for t in self.s(self.rev, n.phrase_string_ns()) + self.s(self.rev, n.phrase_string_ns()[:-1]))):
           match = left.phrase_string_ns()[::-1]
           for m in (match[1:], match):
               for completion in self.completePalindrome(left, expand, f_max, match = m, left = match):
                   yield completion

In essence, it comes down to switching to very well-informed heuristics that can exploit our foreknowledge of the letter sequence we want in the second half of the phrase.

This still tied up my laptop for many hours. I had two ideas for making progress: (1) reduce the dictionary in hopes of lowering the upper bound for the search and (2) experiment with different heuristics in hopes of dynamically finding better solutions more quickly. As an example of (1), I tried excluding words with multiple occurrences of any letter. As an example of (2), I tried using a piecewise heuristic function that penalizes letter repetition early in the search, but also recognizes that the pangram may contain a "keystone" word overlapping its palindromic midpoint.

Here's how I disallowed intraword letter duplication:


def minKeystoneP(w):
   """Determine whether this word's interior
   contains the palindromic pivot of a theoretically
   minimal-sized pangramic palindrome.
   >>> minKeystoneP('abc')
   False

   >>> minKeystoneP('aba')
   True

   >>> minKeystoneP('abaa')
   False

   """
   k = keystoneP(w)
   if not k: return False
   sides = w[:k], w[k:]
   return all(len(s) == len(set(s)) for s in sides)

def mintries(d):
   minKeystones = [w for w in d if minKeystoneP(w)]
   nodups = [w for w in d if len(set(w)) == len(w)]
   return TriePair(minKeystones + nodups)

Here's some profiling data from a run that used a mintries dictionary (stopped at the first feasible solution). I used beam_width = 512, U = 1024:

solution (65): buckrams donzel ti pyx of vug we jo hm suq us mho jew guv foxy pit lez nods mark cub
3063736602 function calls (1650738620 primitive calls) in 15627.224 CPU seconds
Ordered by: standard name
ncalls	tottime	percall	cumtime	percall	filename:lineno(function)
1	0.000	0.000	15627.223	15627.223	<string>:1(<module>)
31125689	67.420	0.000	364.352	0.000	<string>:100(pangramP)
463188677	289.571	0.000	289.571	0.000	<string>:102(ancestors)
31119396	148.473	0.000	562.384	0.000	<string>:107(phrase)
31119396	258.985	0.000	413.911	0.000	<string>:108(<listcomp>)
31119402	137.097	0.000	896.415	0.000	<string>:109(phrase_string_ns)
183/78	0.001	0.000	0.001	0.000	<string>:121(__init__)
285653338	160.594	0.000	160.594	0.000	<string>:129(emptyP)
-495413458/-781144130	3292.676	-0.000	3292.676	-0.000	<string>:131(match)
144/39	0.001	0.000	0.001	0.000	<string>:155(add)
48/8	0.000	0.000	0.000	0.000	<string>:176(words)
1230988464/134840576	8569.205	0.000	12100.459	0.000	<string>:188(_filter_r)
134840576	127.894	0.000	12228.353	0.000	<string>:199(filter)
1910	0.005	0.000	0.043	0.000	<string>:25(palindromeP)
6248	0.159	0.000	0.931	0.000	<string>:260(s)
156545	0.201	0.000	0.528	0.000	<string>:269(<genexpr>)
25939	0.181	0.000	0.709	0.000	<string>:269(<listcomp>)
2	0.000	0.000	0.001	0.001	<string>:303(pivotH)
4	0.000	0.000	0.000	0.000	<string>:305(<genexpr>)
8	0.000	0.000	0.000	0.000	<string>:306(<genexpr>)
51	0.001	0.000	0.007	0.000	<string>:307(rightH)
872	0.001	0.000	0.001	0.000	<string>:309(<genexpr>)
87	0.001	0.000	0.009	0.000	<string>:310(rightExpand)
633	0.001	0.000	0.001	0.000	<string>:337(<genexpr>)
8/3	0.000	0.000	0.391	0.130	<string>:343(completePalindrome)
1910	0.013	0.000	0.016	0.000	<string>:37(<lambda>)
6	0.000	0.000	0.000	0.000	<string>:377(<genexpr>)
2	0.000	0.000	0.002	0.001	<string>:377(<lambda>)
6262	0.049	0.000	1.024	0.000	<string>:383(setupContinuation)
31125244	430.604	0.000	13368.363	0.000	<string>:397(expand)
21700	0.037	0.000	0.037	0.000	<string>:404(<genexpr>)
216034002	221.931	0.000	356.529	0.000	<string>:406(<genexpr>)
6301	0.075	0.000	0.168	0.000	<string>:416(visit)
6301	0.041	0.000	0.078	0.000	<string>:419(<listcomp>)
10	0.000	0.000	0.000	0.000	<string>:424(<listcomp>)
93363173/62244144	198.180	0.000	322.037	0.000	<string>:440(g)
179	0.002	0.000	0.008	0.000	<string>:450(partition)
179	0.004	0.000	0.036	0.000	<string>:458(palindrome_balance)
31118982	306.394	0.000	1302.780	0.000	<string>:521(h)
31119035	48.462	0.000	412.754	0.000	<string>:563(feasibleP)
11/2	203.033	18.458	15627.223	7813.611	<string>:566(bss)
256/128	0.195	0.001	0.298	0.002	<string>:580(prune)
125068	0.044	0.000	0.044	0.000	<string>:585(<lambda>)
31125689	75.291	0.000	286.533	0.000	<string>:60(pangramP)
31119035	71.754	0.000	1642.539	0.000	<string>:615(<lambda>)
7	0.000	0.000	0.002	0.000	<string>:617(<listcomp>)
7	0.000	0.000	0.002	0.000	<string>:618(<lambda>)
7	0.000	0.000	0.000	0.000	<string>:621(<listcomp>)
660	0.000	0.000	0.000	0.000	<string>:648(<lambda>)
7511	0.004	0.000	0.004	0.000	<string>:657(<lambda>)
6931	0.002	0.000	0.002	0.000	<string>:658(<lambda>)
6931	0.002	0.000	0.002	0.000	<string>:659(<lambda>)
45	0.012	0.000	0.016	0.000	<string>:659(<listcomp>)
641	0.000	0.000	0.000	0.000	<string>:669(<lambda>)
1	0.000	0.000	15627.223	15627.223	<string>:677(profileDriver)
2	0.000	0.000	0.000	0.000	<string>:682(keystoneP)
31119030	149.929	0.000	351.339	0.000	<string>:90(__init__)
4	0.000	0.000	0.000	0.000	_abcoll.py:122(__subclasshook__)
2	0.000	0.000	0.000	0.000	_weakrefset.py:10(__init__)
8	0.000	0.000	0.000	0.000	_weakrefset.py:20(__iter__)
31131950	48.803	0.000	48.803	0.000	_weakrefset.py:29(__contains__)
4	0.000	0.000	0.000	0.000	_weakrefset.py:36(add)
31131937	75.111	0.000	123.914	0.000	abc.py:118(__instancecheck__)
4/3	0.000	0.000	0.000	0.000	abc.py:134(__subclasscheck__)
942	0.002	0.000	0.006	0.000	ascii.py:21(encode)
1	0.000	0.000	0.000	0.000	codecs.py:164(__init__)
1	0.000	0.000	0.000	0.000	codecs.py:937(getincrementalencoder)
942	0.010	0.000	0.016	0.000	io.py:1031(write)
447	0.002	0.000	0.364	0.001	io.py:1069(flush)
447	0.004	0.000	0.361	0.001	io.py:1073(_flush_unlocked)
447	0.001	0.000	0.365	0.001	io.py:1454(flush)
942	0.003	0.000	0.004	0.000	io.py:1465(closed)
942	0.012	0.000	0.404	0.000	io.py:1479(write)
1	0.000	0.000	0.000	0.000	io.py:1500(_get_encoder)
2331	0.002	0.000	0.002	0.000	io.py:755(closed)
6301	0.005	0.000	0.005	0.000	{built-in method abs}
2	0.000	0.000	0.000	0.000	{built-in method any}
942	0.004	0.000	0.004	0.000	{built-in method ascii_encode}
1910	0.001	0.000	0.001	0.000	{built-in method ceil}
1	0.001	0.001	15627.224	15627.224	{built-in method exec}
31119030	69.197	0.000	69.197	0.000	{built-in method fromkeys}
4	0.000	0.000	0.000	0.000	{built-in method getattr}
155614108	204.289	0.000	204.289	0.000	{built-in method hasattr}
31118982	17.315	0.000	17.315	0.000	{built-in method hash}
53	0.000	0.000	0.000	0.000	{built-in method id}
31133821	76.905	0.000	200.819	0.000	{built-in method isinstance}
5	0.000	0.000	0.000	0.000	{built-in method issubclass}
155695466	50.374	0.000	50.374	0.000	{built-in method len}
1	0.000	0.000	0.000	0.000	{built-in method lookup}
179	0.000	0.000	0.000	0.000	{built-in method max}
4	0.000	0.000	0.000	0.000	{built-in method min}
6931	0.002	0.000	0.002	0.000	{built-in method next}
447	0.005	0.000	0.408	0.001	{built-in method print}
90	0.001	0.000	0.003	0.000	{built-in method sum}
1389	0.001	0.000	0.001	0.000	{method '__enter__' of '_thread.lock' objects}
2	0.000	0.000	0.000	0.000	{method '__subclasses__' of 'type' objects}
4	0.000	0.000	0.000	0.000	{method 'add' of 'set' objects}
82757	0.034	0.000	0.034	0.000	{method 'append' of 'list' objects}
1	0.000	0.000	0.000	0.000	{method 'disable' of '_lsprof.Profiler' objects}
942	0.001	0.000	0.001	0.000	{method 'extend' of 'bytearray' objects}
263060106	78.312	0.000	78.312	0.000	{method 'items' of 'dict' objects}
31120994	126.532	0.000	126.532	0.000	{method 'join' of 'str' objects}
31131990	10.402	0.000	10.402	0.000	{method 'keys' of 'dict' objects}
31	0.000	0.000	0.000	0.000	{method 'pop' of 'list' objects}
31119029	111.008	0.000	111.008	0.000	{method 'update' of 'dict' objects}
447	0.357	0.001	0.357	0.001	{method 'write' of '_FileIO' objects}

Using the same parameters but substituting a piecewise expand function to reduce the search space, I produced the same solution in 12949.838 CPU seconds (shortly after the 7232nd node expansion):


# this function takes a TriePair to an expand function
# suitable for use with bss:
def budgetExpand(ordinarytries):
   def bex(n, advisoryBudget):
       if n.pangramP():
           for x in ordinarytries.expand(n):
               yield x
           return
       letterAllowance = int((advisoryBudget / 2) - g(n))
       if letterAllowance < 5:
           missing = len(string.ascii_lowercase) - len(n.covered)
           if missing < letterAllowance:
               # we might be able to afford to waste the next word
               for x in ordinarytries.expand(n):
                   yield x
               return
           if missing == 2:
               # find a suitable tp
               for lp, t in raretries:
                   if not any(l in n.covered for l in lp):
                       for x in t.expand(n):
                           yield x
                       return
           if missing <= 4:
               letters = string.ascii_lowercase - n.covered.keys()
               if all(l in lettertries for l in letters):
                   for x in itertools.chain.from_iterable(t.expand(n) for l, t in lettertries.items() if not n.coveredP(l)):
                       yield x
                   return
       for x in ordinarytries.expand(n):
           yield x
   return bex

2481633428 function calls (1172623990 primitive calls) in 12949.838 CPU seconds
Ordered by: standard name
ncalls	tottime	percall	cumtime	percall	filename:lineno(function)
1	0.000	0.000	12949.838	12949.838	<string>:1(<module>)
28221664	56.848	0.000	307.680	0.000	<string>:100(pangramP)
396097158	231.455	0.000	231.455	0.000	<string>:102(ancestors)
28206562	130.097	0.000	464.824	0.000	<string>:107(phrase)
28206562	210.286	0.000	334.727	0.000	<string>:108(<listcomp>)
28207750	120.352	0.000	750.641	0.000	<string>:109(phrase_string_ns)
75/32	0.000	0.000	0.001	0.000	<string>:121(__init__)
265064474	140.758	0.000	140.758	0.000	<string>:129(emptyP)
-776844655/-1041987795	2885.248	-0.000	2885.248	-0.000	<string>:131(match)
59/16	0.000	0.000	0.000	0.000	<string>:155(add)
24/4	0.000	0.000	0.000	0.000	<string>:176(words)
1140618203/124958593	6869.411	0.000	9963.410	0.000	<string>:188(_filter_r)
124958593	113.443	0.000	10076.852	0.000	<string>:199(filter)
394	0.001	0.000	0.145	0.000	<string>:25(palindromeP)
7260	0.162	0.000	0.953	0.000	<string>:260(s)
176364	0.208	0.000	0.545	0.000	<string>:269(<genexpr>)
28381	0.188	0.000	0.733	0.000	<string>:269(<listcomp>)
1	0.000	0.000	0.000	0.000	<string>:303(pivotH)
2	0.000	0.000	0.000	0.000	<string>:305(<genexpr>)
4	0.000	0.000	0.000	0.000	<string>:306(<genexpr>)
21	0.000	0.000	0.002	0.000	<string>:307(rightH)
350	0.000	0.000	0.000	0.000	<string>:309(<genexpr>)
36	0.000	0.000	0.003	0.000	<string>:310(rightExpand)
251	0.000	0.000	0.000	0.000	<string>:337(<genexpr>)
5/2	0.000	0.000	0.233	0.117	<string>:343(completePalindrome)
394	0.002	0.000	0.142	0.000	<string>:37(<lambda>)
3	0.000	0.000	0.000	0.000	<string>:377(<genexpr>)
1	0.000	0.000	0.001	0.001	<string>:377(<lambda>)
9180	0.052	0.000	1.037	0.000	<string>:383(setupContinuation)
28215608	356.822	0.000	11018.065	0.000	<string>:397(expand)
28840	0.049	0.000	0.049	0.000	<string>:404(<genexpr>)
183935843	180.895	0.000	287.857	0.000	<string>:406(<genexpr>)
7287	0.070	0.000	0.174	0.000	<string>:416(visit)
7287	0.045	0.000	0.089	0.000	<string>:419(<listcomp>)
10	0.000	0.000	0.000	0.000	<string>:424(<listcomp>)
84626570/56420123	168.273	0.000	271.354	0.000	<string>:440(g)
29	0.000	0.000	0.002	0.000	<string>:450(partition)
29	0.001	0.000	0.008	0.000	<string>:458(palindrome_balance)
28206428	257.713	0.000	1093.465	0.000	<string>:521(h)
28206451	41.020	0.000	348.655	0.000	<string>:563(feasibleP)
7/2	170.547	24.364	12949.838	6474.919	<string>:566(bss)
252/126	0.193	0.001	0.258	0.002	<string>:580(prune)
127106	0.048	0.000	0.048	0.000	<string>:585(<lambda>)
28221664	63.621	0.000	242.118	0.000	<string>:60(pangramP)
28206450	63.101	0.000	1381.873	0.000	<string>:616(<lambda>)
4	0.000	0.000	0.001	0.000	<string>:618(<listcomp>)
4	0.000	0.000	0.001	0.000	<string>:619(<lambda>)
4	0.000	0.000	0.000	0.000	<string>:622(<listcomp>)
497	0.000	0.000	0.000	0.000	<string>:649(<lambda>)
8533	0.004	0.000	0.004	0.000	<string>:658(<lambda>)
7784	0.002	0.000	0.002	0.000	<string>:659(<lambda>)
7784	0.004	0.000	0.004	0.000	<string>:660(<lambda>)
759	0.000	0.000	0.000	0.000	<string>:670(<lambda>)
1	0.000	0.000	0.000	0.000	<string>:683(keystoneP)
28213699	29.299	0.000	11048.220	0.000	<string>:826(bex)
35164	0.018	0.000	0.018	0.000	<string>:844(<genexpr>)
3779	0.003	0.000	0.003	0.000	<string>:852(<genexpr>)
3731	0.024	0.000	0.032	0.000	<string>:854(<genexpr>)
28206448	126.205	0.000	295.114	0.000	<string>:90(__init__)
14576	0.008	0.000	0.008	0.000	<string>:98(coveredP)
4	0.000	0.000	0.000	0.000	_abcoll.py:122(__subclasshook__)
2	0.000	0.000	0.000	0.000	_weakrefset.py:10(__init__)
8	0.000	0.000	0.000	0.000	_weakrefset.py:20(__iter__)
28228934	40.811	0.000	40.811	0.000	_weakrefset.py:29(__contains__)
4	0.000	0.000	0.000	0.000	_weakrefset.py:36(add)
28228924	63.055	0.000	103.866	0.000	abc.py:118(__instancecheck__)
4/3	0.000	0.000	0.000	0.000	abc.py:134(__subclasscheck__)
6399	0.014	0.000	0.037	0.000	ascii.py:21(encode)
1	0.000	0.000	0.000	0.000	codecs.py:164(__init__)
1	0.000	0.000	0.000	0.000	codecs.py:937(getincrementalencoder)
6399	0.066	0.000	0.103	0.000	io.py:1031(write)
3190	0.014	0.000	0.670	0.000	io.py:1069(flush)
3190	0.026	0.000	0.655	0.000	io.py:1073(_flush_unlocked)
3190	0.009	0.000	0.679	0.000	io.py:1454(flush)
6399	0.013	0.000	0.021	0.000	io.py:1465(closed)
6399	0.075	0.000	0.919	0.000	io.py:1479(write)
1	0.000	0.000	0.000	0.000	io.py:1500(_get_encoder)
15988	0.014	0.000	0.014	0.000	io.py:755(closed)
7287	0.005	0.000	0.005	0.000	{built-in method abs}
923	0.003	0.000	0.005	0.000	{built-in method all}
15357	0.013	0.000	0.024	0.000	{built-in method any}
6399	0.023	0.000	0.023	0.000	{built-in method ascii_encode}
394	0.139	0.000	0.139	0.000	{built-in method ceil}
1	0.000	0.000	12949.838	12949.838	{built-in method exec}
911	0.001	0.000	0.001	0.000	{built-in method from_iterable}
28206448	58.517	0.000	58.517	0.000	{built-in method fromkeys}
4	0.000	0.000	0.000	0.000	{built-in method getattr}
141057204	171.326	0.000	171.326	0.000	{built-in method hasattr}
28206428	14.606	0.000	14.606	0.000	{built-in method hash}
22	0.000	0.000	0.000	0.000	{built-in method id}
28241722	65.730	0.000	169.595	0.000	{built-in method isinstance}
5	0.000	0.000	0.000	0.000	{built-in method issubclass}
141174090	42.904	0.000	42.904	0.000	{built-in method len}
1	0.000	0.000	0.000	0.000	{built-in method lookup}
29	0.000	0.000	0.000	0.000	{built-in method max}
2	0.000	0.000	0.000	0.000	{built-in method min}
7766	0.002	0.000	0.002	0.000	{built-in method next}
3190	0.031	0.000	0.949	0.000	{built-in method print}
37	0.000	0.000	0.001	0.000	{built-in method sum}
9589	0.009	0.000	0.009	0.000	{method '__enter__' of '_thread.lock' objects}
2	0.000	0.000	0.000	0.000	{method '__subclasses__' of 'type' objects}
4	0.000	0.000	0.000	0.000	{method 'add' of 'set' objects}
85797	0.034	0.000	0.034	0.000	{method 'append' of 'list' objects}
1	0.000	0.000	0.000	0.000	{method 'disable' of '_lsprof.Profiler' objects}
6399	0.008	0.000	0.008	0.000	{method 'extend' of 'bytearray' objects}
244196206	68.331	0.000	68.331	0.000	{method 'items' of 'dict' objects}
28206877	105.938	0.000	105.938	0.000	{method 'join' of 'str' objects}
28229874	8.717	0.000	8.717	0.000	{method 'keys' of 'dict' objects}
15	0.000	0.000	0.000	0.000	{method 'pop' of 'list' objects}
28206447	92.287	0.000	92.287	0.000	{method 'update' of 'dict' objects}
3190	0.626	0.000	0.626	0.000	{method 'write' of '_FileIO' objects}

What about that penultimate case, searching up to four overlapping TriePairs each representing the set of words containing a missing letter? How much does it help? The mintriesd superset has 35103 words, and a sample of four-combinations range in size from 11263 to 24428 words. But, the average size lettertrie has 4784 words, so we get a noticeable speedup even though trie search has logarithmic time complexity. Without the lettertries case, we need 2656858411 function calls (1319973770 primitive calls) in 14205.551 CPU seconds.

Finally, I added to the budgetExpand repertoire with lengthtries.

The idea for lengthtries comes from the observation that it would be useful to limit the depth of trie traversals as we approach the current cost bound. With this technique I brought the first solution discovery down to 398442028 function calls in 9485.551 CPU seconds:


def budgetExpand(ordinarytries):
    raretries = [(lp, TriePair([w for w in ordinarytries.fwd.words() if all(l in w for l in lp)])) for lp in 'jm vx jy fx jk gq mq jp qy bq hq pq kz jv wz hj fq qv xz kq jw fj qz wx jz kx qw jx qx jq'.split()]
    hist = Histogram(ordinarytries.fwd.words())
    lettertries = {l : TriePair(hist[l]) for l in [k for k, v in sorted(hist.h.items(), key = lambda i: len(i[1]))][:16]}
    lengthtries = {i : TriePair((w for w in mintriesd.fwd.words() if len(w) <= i or keystoneP(w)), mintriesd.rev.words()) for i in range(1, 8)}
    def bex(n, advisoryBudget):
        if n.pangramP():
            for x in ordinarytries.expand(n):
                yield x
            return
        letterAllowance = int((advisoryBudget / 2) - g(n))
        if letterAllowance < 5:
            missing = len(string.ascii_lowercase) - len(n.covered)
            if missing < letterAllowance:
                # we might be able to afford to waste the next word
                for x in lengthtries[letterAllowance].expand(n):
                    yield x
                return
            if missing == 2:
                # find a suitable tp
                for lp, t in raretries:
                    if not any(l in n.covered for l in lp):
                        for x in t.expand(n):
                            yield x
                        return
            if missing <= 4:
                letters = string.ascii_lowercase - n.covered.keys()
                if all(l in lettertries for l in letters):
                    for x in itertools.chain.from_iterable(t.expand(n) for l, t in lettertries.items() if not n.coveredP(l)):
                        yield x
                    return
        elif letterAllowance in lengthtries:
            for x in lengthtries[letterAllowance].expand(n):
                yield x
            return
        for x in ordinarytries.expand(n):
            yield x
    return bex

One last idea for search space reduction is to exclude words containing covered letters:


def budgetExpand(ordinarytries):
   # least-common 2-combinations of letters in d:
   # [('kx', 53), ('qw', 27), ('jx', 27), ('qx', 26), ('jq', 8)]
   raretries = [(lp, TriePair((w for w in ordinarytries.fwd.words() if all(l in w for l in lp)), ordinarytries.rev)) for lp in 'jm vx jy fx jk gq mq jp qy bq hq pq kz jv wz hj fq qv xz kq jw fj qz wx jz kx qw jx qx jq'.split()]
   hist = Histogram(ordinarytries.fwd.words())
   lettertries = {l : TriePair(hist[l], ordinarytries.rev) for l in [k for k, v in sorted(hist.h.items(), key = lambda i: len(i[1]))][:16]}
   lengthtries = {i : TriePair((w for w in ordinarytries.fwd.words() if len(w) <= i or keystoneP(w)), ordinarytries.rev) for i in range(1, 8)}
   def mfl(k, n):
       """Kth most frequent letter k, n -> (#, a)"""
       if not hasattr(n, 'hist'):
           n.hist = Histogram(n.tp.fwd.words())
       lf = list(itertools.islice(n.hist, k + 1))[-1]
       return (sum(1 for i in lf[1]), lf[0])
   exttltries = Trie()
   exttltries.tp = mintriesd
   # this isn't optimal; there may be unreachable
   # nodes and some of those may be more selective
   # than letter-equivalent reachable nodes. But
   # it won't yield incorrect results and it's
   # an approximation I can build quickly.
   for i in range(32):
       (freq, split_char), parent = max(
           (mfl(len(n.children), n), n) for n in
           exttltries.pre_order_nodes() if len(n.children) <= 4)
       parent.add(split_char)
       subtrie = parent.search(split_char)
       subtrie.tp = TriePair(Trie(w for w in parent.tp.fwd.words() if split_char not in w), parent.tp.rev)
   print([x for x in exttltries.pre_order_nodes()])
   print([sum(1 for y in x.tp.fwd.words()) for x in exttltries.pre_order_nodes()])
   def pickTP(t, n):
       if (len(t.children) == 0): return t.tp
       for l in t.children:
           if not l in n.covered: continue
           return pickTP(t.children[l], n)
       return t.tp
   def bex(n, advisoryBudget):
       if n.pangramP():
           for x in ordinarytries.expand(n):
               yield x
           return
       letterAllowance = int((advisoryBudget / 2) - g(n))
       if letterAllowance < 5:
           missing = len(string.ascii_lowercase) - len(n.covered)
           if missing < letterAllowance:
               # we might be able to afford to waste the next word
               for x in lengthtries[letterAllowance].expand(n):
                   yield x
               return
           if missing == 2:
               # find a suitable tp
               for lp, t in raretries:
                   if not any(l in n.covered for l in lp):
                       for x in t.expand(n):
                           yield x
                       return
           if missing <= 4:
               letters = string.ascii_lowercase - n.covered.keys()
               if all(l in lettertries for l in letters):
                   for x in itertools.chain.from_iterable(t.expand(n) for l, t in lettertries.items() if not n.coveredP(l)):
                       yield x
                   return
       if letterAllowance in lengthtries:
           for x in lengthtries[letterAllowance].expand(n):
               yield x
           return
       for x in pickTP(exttltries, n).expand(n):
           yield x
   return bex

There are unreachable TriePairs in exttltries, and some of those are smaller than letter-equivalent reachable ones. To avoid this, we should maintain the exttltries property that no node's letter should appear in the set of siblings of its ancestors. Together with the greedy order for splitting nodes, this minimizes size and optimizes expected search cost. But we do pretty well even with the quick and dirty experiment: we find a first solution (cost 67) before the 7808 node expansion in under 4562.899 CPU seconds. A 65 solution is found before the 9984 node expansion in under 5141.208 CPU seconds.

I never got around to rewriting variations in search of more beautiful code. I still wonder what other tricks I've overlooked for improving the heuristic function or reducing the search space.

Rumor has it that Common Lisp has been really well-optimized over the years, so I wonder how much faster this could go if rewritten in lisp. Also, I could go twice as fast on my dual-core CPU if python had threads (just partition the input) or if I quit some other apps in order to fit two python instances of this program in my 4GB of RAM.

Many have posted solutions for this problem. Solutions I can recommend reading if this post has piqued your interest include Jim Vellenga's and Keoki Zee's.

Continuation Monad

2010-02-10T17:09:00.005-06:00

Last month I worked on a TopCoder problem that led me to continue my exploration of monads. The problem is to sort a set of elements using comparisons whose cost is a function of the comparands. Solutions comprise a pair of methods, one of which initializes the program with the costs, and the other of which is invoked repeatedly to effect the dialog between the program and the less-than oracle.

Now choose your own adventure. Do you:

Ask how a real computer scientist would solve it
Watch me muddle through comparison-based sorting with variable costs
Follow my continuation monad implementation in Java

Comparison-based sorting with variable costs

Sidebar: true story

I've seen a related problem in real life. Our app iDeal helped salespersons develop contract terms subject to Boolean constraints called guidelines, analogous to the Boolean trees examined in Charikar et al. We didn't actually have to buy our guideline results, but we did care about evaluation speed. There were basically two prices: low (computable on our local app server) and high (computable at a minicomputer reached by at least two SOAP hops and a batch job. Unlike the Charikar model, our cost function was not additive: it behaved like or, giving a result of "expensive" whenever at least one guideline couldn't be computed locally and "cheap" otherwise. Consequently, the real-life challenge was less about algorithm design and more about software engineering: given that guideline evaluation is demanded at many call sites, how can we avoid unnecessarily consulting the minicomputer?

I first thought of divide and conquer approaches to avoid redundant queries (don't ask a < c if it is already known that a < b and b < c). I thought about algorithms for the special case when C(a, b) = 1: mergesort, heapsort, and quicksort. All of these relate to binary trees, and I thought about properties a binary search tree constructed at optimal cost would have in the general case.

Shouldn't the root of the tree be the element for which the sum over pairs of itself with each of its descendants is minimal? Intuitively, we compare every element with the root to locate the element in the tree, and we want to minimize the cost of inserting each element by this recursive process. Not quite: this fails to account for tree shape (consider p < q < r with costs C(p, X) = 1 for all X in {p, q, r}; C(q, r) = 2). And thinking back to the special case of a constant cost function, it's clear that this root selection heuristic has no power. It's also often mentioned in discussions of e.g., quicksort, that it's important to have a balanced tree. But we're not looking just to balance and fill the tree; It's easy to ensure that every left child in an optimal tree is a leaf node by carefully choosing the cost function.

The shape of the tree is determined both by the sequence of queries the program makes and by the order of elements determined by the oracle. The best choice for the root is the median of the elements, so an exact solution is O(n^2) but we could think about approximate selection and average-case performance.

What about a bottom-up approach? Do our trees have optimal substructure? First: in an optimal tree, is every subtree optimal? Suppose not. Then some optimal tree has a subtree that can be rearranged for lower cost. But this doesn't affect the cost to construct the rest of the tree, so after the rearrangement the overall cost is lowered. This contradicts the supposition that our original tree was optimal with a suboptimal subtree. But second: can we efficiently combine optimal subsolutions to derive optimal solutions?

A straightforward mergesort would guarantee a minimal number of comparisons, but not necessarily a minimal-cost set of comparisons. Although a minimal tree implies minimal subtrees, not all combinations of minimal subtrees constitute a (rearrangement of a) minimal tree. To see this, imagine a cost function that does not have the triangle property. In this case, the cheapest way to combine two trees might involve using additional vertices not a part of either original tree.

Let g(t) = sum(C(n, n') for n in t for n' in ~t). Recursively merge the runs with the lowest g.

Pf. g-ordered mergesort yields optimal solutions.

Let A and B represent two C-optimal subsolutions whose g-costs are least among all subsolutions. Claim: the combination S of A and B is C-optimal. Suppose not. Then there is a (sub)solution S' containing all the elements of a and b such that C(S) > C(S'). S' is a proper superset of S, so we can obtain it by adding elements from the complement of S. These missing elements must exist in other optimal subsolutions having higher g-costs than that of S. Also, each of these elements must have edges to each of a and b in the optimal tree of S. Consider any subsolution G hosting one of these missing elements. It's g-cost is \sum_{g \in G}(\sum_{a \in A}(C(g, a)) + \sum_{b \in B}(C(g, b)) + \sum_{c' \in c}(C(g, c'))), where a, b, and c' are drawn from our input sets and the complement of their union respectively. To simplify the notation, I'm going to switch now to using implicit summations: the g-cost of subsolution G is C(g, a) + C(g, b) + C(g, c). The g-cost of S is c(a, c) + c(b, c) + c(s, c). The g-cost of a is c(a, b) + c(a, c). The g-cost of b is c(a, b) + c(b, c). A little algebra and the observation that the complement of the union of a and b includes all the g \in G, we can derive a contradiction from the assumption that there exist elements outside the min-g-cost subsolutions a and b that would improve the C-cost of the combination of a and b:


c(s a) + c(s b) + c(s c) > max(c(a c) + c(a b); c(b c) + c(a b))
> max(c(S) - c(s, c) - c(b, c) + c(a, b);
c(S) - c(s, c) - c(a, c) + c(a, b))
c(s a) + c(s b) + 2c(s c) - c(a b) - c(S) > max(- c(b, c); - c(a c))
- c(s c) - c(a c) - c(b c)
c(s a) + c(s b) + c(s c) - c(a b) - c(a c) - c(b c) > -max(c(b c); c(a c))
c(s a) + c(s b) + c(s c) - c(a b) - c(a c) > 0
c(s a) + c(s b) + c(s c) - c(a b) - c(b c) > 0
c(s a) + c(s b) + c(s c) > c(a b) + c(a c)
c(s a) + c(s b) + c(s c) > c(a b) + c(b c)
c(a c) includes c(a s) so c(a c) > c(a s)
c(s b) + c(s c) > c(a b)
c(s a) + c(s c) > c(a b)
c(s b) - c(s a) > 0
c(s a) - c(s b) > 0
⟶⟵

Sadly, although this heuristic won't mislead us, it may often fail to answer by telling us that more than two trees have the least g-cost.

A more dynamic heuristic could rely on probabilistic estimates of the information gain at each query. Assuming uniform random permutation, initially we should just do the cheapest comparison. As we progress, we'll develop equivalence classes: these elements could be anywhere; those elements could only be in the top 6. Comparisons involving elements in large classes or classes near the min or max yield relatively little information. We could combine estimates of value with the given cost information to get reasonable average-case performance.

I decided not to work harder to prove a tight lower bound on the solution to the problem or to find a better algorithm or heuristic. It's TopCoder after all, and speed is important. I decided instead to move on to implementation and Google for a better answer later.

So in a nutshell my solution is: initially regard every element as a subsolution. Order them by g-cost and merge the two lowest-ranked solutions. Recurse.

Continuation monad

The online interactions between the TopCoder oracle and my solution raises an interesting question. The first thing that occurred to me of course was to write g and merge, arrange to store state in instance variables, and update my instance state incrementally in the two callback functions whose existence is mandated by the oracle. On second thought, I wondered if my code could more closely resemble the nutshell description I gave above, with the state maintenance handled separately. It seemed like a good excuse to get some first-hand experience with continuation-passing style, a canonical form for programs that can be paused and restarted. The continuation monad brings cps into a more general framework, improving modularity.

So I broke out my old favorites Monads for Functional Programming and Comprehending Monads. I also found a couple of new sources: Lecture notes: Continuations and call/cc and The Continuation Monad in Clojure. Continuations are also discussed at some length in the lambda papers, although the idea originated a decade earlier.

First, the monad preliminaries. When I implemented the maybe monad in C#, I had the ambition to support composition of different monads and that led to some difficulty with the type system. Also, I noticed how cumbersome the syntax was and what effect that had on my enthusiasm for explicit and separate expression of an abstraction for monads. And that was with C# 3, which has overtaken Java in its evolution towards greater expressive power. So this time I decided to focus strictly on the continuation monad and the question of whether it could enable me to separate the oracle i/o from the specification of my sort algorithm.

Recall the monad laws:


@Test
// unit a ⋆ λb. n = n[a/b]
public void leftUnit() {
    Func1<String, CMonad<Integer>> f =
        new Func1<String, CMonad<Integer>>() {
            public CMonad<Integer> f(String a) {
                return CMonad.unit(a.length());
            }
        };

    String a = "a";
    CMonad<Integer> expected =
        f.f(a);
    CMonad<Integer> actual =
        CMonad.map(
            f,
            CMonad.unit(a));

    assertMEquals(expected, actual);
}

@Test
// m ⋆ λa. unit a = m
public void rightUnit() {
    CMonad<Integer> m =
        CMonad.unit(42);
    Func1<Integer, CMonad<Integer>> id =
        new Func1<Integer, CMonad<Integer>>() {
            public CMonad<Integer> f(Integer x) {
                return CMonad.unit(x);
            }
        };

    assertMEquals(
        m,
        CMonad.map(id, m));
}

@Test
// m ⋆ (λa. n ⋆ λb. o) = (m ⋆ λa. n) ⋆ λb. o
public void associative() {
    Func1<String, CMonad<Integer>> fa =
        new Func1<String, CMonad<Integer>>() {
            public CMonad<Integer> f(String x) {

                return CMonad.unit(x.length());
            }
        };

    Func1<Integer, CMonad<Integer>> fb =
        new Func1<Integer, CMonad<Integer>>() {
            public CMonad<Integer> f(Integer x) {
                return CMonad.unit(x * 2);
            }
        };

    final CMonad<String> m =
        CMonad.unit("m");

    final CMonad<Integer> n =
        CMonad.unit(5);

    final Func1<Integer, CMonad<Integer>> o =
        new Func1<Integer, CMonad<Integer>>() {
            public CMonad<Integer> f(Integer x) {
                return CMonad.unit(x - 1);
            }
        };

    CMonad<Integer> expected =
        CMonad.map(
            new Func1<String, CMonad<Integer>>() {
                public CMonad<Integer> f(String x) {
                    return
                        CMonad.map(
                            o,
                            n);
                }
            },
            m);

    CMonad<Integer> actual =
        CMonad.map(
            o,
            CMonad.map(
                new Func1<String, CMonad<Integer>>() {
                    public CMonad<Integer> f(String x) {
                        return n;
                    }
                },
                m));

    assertMEquals(expected, actual);
}

(assertMEquals is more or less what you'd expect):


private  void assertMEquals(CMonad expected, CMonad actual) {
    Func1 id =
        new CostlySorting.Func1() {
            public T f(T x) {
                return x;
            }
        };
    T exp = expected.f(id);
    T act = actual.f(id);
    assertEquals(exp, act);
}

My continuation monad satisfies those:


public abstract static class CMonad<X> {
    private CMonad() {}
    public abstract <R> R f(Func1<X, R> k);
    public static <X> CMonad<X> unit(final X x) {
        return
            new CMonad<X>() {
                public <R> R f(Func1<X, R> k) {
                    return k.f(x);
                }
            };
    }

    // aka bind aka ★
    public static <X, R> CMonad<R> map(final Func1<X, CMonad<R>> f, final CMonad<X> mx) {
        return new CMonad<R>() {
            public <S> S f(Func1<R, S> k) {
                return mx.f(f).f(k);
            }
        };
    }
}

call/cc seemed like a useful abstraction, so I implemented that in terms of my monad:


public Integer divideByZeroEg(final int x, final int y) {
    CMonad<Integer> eg =
        CMonad.callcc(
            new Func1<Func1<Integer, CMonad<Integer>>, CMonad<Integer>>() {
                public CMonad<Integer> f(Func1<Integer, CMonad<Integer>> esc) {
                    return
                        CMonad.map(
                            new Func1<Integer, CMonad<Integer>>() {
                                public CMonad<Integer> f(Integer z) {
                                    return CMonad.unit(x / z);
                                }
                            },
                            (y == 0 ? esc.f(42) : CMonad.unit(y)));
                }
            });
    return eg.f(
        new Func1<Integer, Integer>() {
            public Integer f(Integer x) {
                return x;
            }
        });
}

@Test
public void divideByZeroEg() {
    assertEquals((Object)5, divideByZeroEg(20, 4));
    assertEquals((Object)42, divideByZeroEg(20, 0));
}

public static <X, Y> CMonad<X> callcc(final Func1<Func1<X, CMonad<Y>>, CMonad<X>> g) {
    // .\ k -> g(.\x -> .\k' -> kx)k
    // g :: ((X -> MY) -> MX)
    // g :: ((X -> (Y -> R)) -> (X -> R'))
    // k :: X -> R''
    // R'' = R
    // R = X -> R'
    return
        map(
            new Func1<X, CMonad<X>>() {
                public CMonad<X> f(X x) {
                    return unit(x);
                }
            },
            new CMonad<X>() {
                public <R> R f(final Func1<X, R> k) {
                    CMonad<X> gresult =
                        g.f(
                            new Func1<X, CMonad<Y>>() {
                                public CMonad<Y> f(final X x) {
                                    return new CMonad<Y>() {
                                        public <S> S f(Func1<Y, S> kprime) {
                                            return (S)k.f(x);
                                        }
                                    };
                                }
                            });
                    return gresult.f(k);
                }
            });
}

and then I implemented a while loop atop continuation monad and call/cc:


@Test
public void finiteWhile() {
    final int [] countdown = new int [] {3};
    CMonad.cpswhile(
        new Func0<Boolean>() {
            public Boolean f() {
                return countdown[0] > 0;
            }
        },
        new SideEffectful() {
            public void f() {
                countdown[0] -= 1;
            }
        });
    assertEquals(0, countdown[0]);
}

private static <T> CMonad<T> recurse(CMonad<T> m) {
    final WhateverClosure<CMonad<T>> loop =
        new WhateverClosure<CMonad<T>>();
    loop.whatever =
        CMonad.map(
            new Func1<T, CMonad<T>>() {
                public CMonad<T> f(T x) {
                    System.out.println("recurse");
                    return loop.whatever;
                }
            },
            m);
    return loop.whatever;
}

public static void cpswhile(final Func0<Boolean> loopInvariant, final SideEffectful body) {
    callcc(
        new Func1<Func1<Object, CMonad<Object>>, CMonad<Object>>() {
            public CMonad<Object> f(final Func1<Object, CMonad<Object>> esc) {
                return recurse(
                    new CMonad<Object>() {
                        public <R> R f(Func1<Object, R> f) {
                            System.out.println("start.f");
                            if (!loopInvariant.f()) {
                                System.out.println("done");
                                return
                                    esc.f(null).f(f);
                            }
                            System.out.println("body.f");
                            body.f();
                            return f.f(null);
                        }
                    });
            }
        }).f(new Func1<Object, Object>() {
                 public Object f(Object x) {
                     return x;
                 }
             });
}

public interface SideEffectful {
    public void f();
}

Why reimplement the while? Java's while keyword only composes in the predefined ways that Java's language designers cared about. I wouldn't be able to effect oracle I/O between loop iterations, except by resorting to contrived method invocations in the loop body or test. Also, because of the communications mechanism is method invocation, I couldn't actually use while without also using threads. By using composable continuation monads for control flow, I hoped to express my sort algorithm separately from managing the data flow between the program and the TC oracle.

Of course, Lisp and Haskell don't always translate easily to Java:


@Test
// (recipe for stack overflow)
public void infiniteWhile() {
    // customize this value for your stack size/patience
    int approximatelyInfinity = 1;

    final Calendar finish = Calendar.getInstance();
    finish.add(Calendar.SECOND, approximatelyInfinity);
    //CMonad.cpsbounce(
    CMonad.cpsbouncewhile(
        new Func0<Boolean>() {
            public Boolean f() {
                return finish.after(Calendar.getInstance());
            }
        },
        new SideEffectful() {
            public void f() {
            }
        });
}

public static void cpsbouncewhile(final Func0<Boolean> loopInvariant, final SideEffectful body) {
    CMonad<Object> mo =
        callcc(
            new Func1<Func1<Object, CMonad<Object>>, CMonad<Object>>() {
                public CMonad<Object> f(final Func1<Object, CMonad<Object>> esc) {
                    final CMonad<Object> start =
                        new CMonad<Object>() {
                            public <R> R f(Func1<Object, R> f) {
                                System.out.println("start.f");
                                if (!loopInvariant.f()) {
                                    System.out.println("done");
                                    return
                                        esc.f(null).f(f);
                                }
                                System.out.println("body.f");
                                body.f();
                                return f.f(null);
                            }
                        };

                    final WhateverClosure<CMonad<Object>> restartHolder = new WhateverClosure<CMonad<Object>>();
                    restartHolder.whatever =
                        map(
                            new Func1<Object, CMonad<Object>>() {
                                public CMonad<Object> f(Object x) {
                                    System.out.println("restart.f");
                                    return
                                        esc.f(
                                            Bounce.wrap(
                                                restartHolder.whatever));
                                }
                            },
                            start);

                    return restartHolder.whatever;
                }
            });
    for (; mo != null;
        mo =
            (CMonad<Object>)mo.f(new Func1<Object, Object>() {
                public Object f(Object x) {
                    return x;
                }
            })) {
        if (!(mo instanceof Bounce)) continue;
        System.out.println("bouncey");
    }
}

So then how'd I do? Well, the test code for while loops is fairly readable, but my goal was to write something like


// T is a priority queue of sorted runs
while (T.size() > 1) {
    T.add(merge(comparator, T.remove(), T.remove());
}

and have that automatically translated to a continuation monad representing the progress of the loop as a function from Booleans (comparison results) to pairs of its own type and pairs of elements to compare next.

Dealing with the while per se was not bad, but translating the body requires quite a lot of fussiness. We need not only a restartable outer (while) loop, but also a restartable inner (merge) loop and we want these flattened so that the while's client code can be oblivious to the implementation choice to use functional composition in the while body. Looking at things a different way, we would like to encapsulate data flow so that a caller can repeatedly supply data to meet the demands of the callee until the callee finishes.

We could use call/cc whenever we need input to obtain a restart wherever we need input. These restarts are relatively easy to pass around (no need for joins), but they only support one standard operation (escape). Accordingly, each adjacent caller/callee pair have to be tweaked to expect/return restarts (analogously to monads in the above paragraph) and each caller has to branch at each invocation to either pass back a restart or move on with its own computation.

Alternatively, we could add a function to represent function application within the continuation monad framework. We could tweak while so that its body argument has a result type of continuation-monad, and then this new apply function could yield such a monad; while could be responsible for composing that result into its own result (using the join operation from MMA -> MA).

Although we're able to dispense with the repetitive branching at function invocations in the call/cc approach by using monads, we can't escape the need to reimplement Java all along the way. If the body of a while loop includes its own function delegation, we'll have make that monadic. If we need a conditional branch, we'll have to make that monadic. Even to implement merge sort we'd wind up with multiple nested anonymous class instance creation expressions. In between scads of braces, parens, brackets, and repetitions of type names like "Func1," we'd have the names of the functions we used to replace all the Java primitives. Lacking syntactic abstraction, the readability of the resulting DSL doesn't scale beyond the simple examples in this blog post.

TopCoding

2009-12-04T15:09:00.011-06:00

Since Cross Country Coaches Moss and Brandon had us running sprints, I've realized the importance of short-distance running for long-distance training. So I suppose I've always suspected that TopCoder could be worthwhile, even for those of us who don't care about who can implement bubble sort fastest. Still, it lingered at the bottom of my priority queue. I don't strongly enjoy competition so it wouldn't be first-order fun for me, and I never had trouble thinking of more interesting intellectual challenges than speed-writing fizzbuzz.

But, Niniane told me I should use TopCoder, so I updated that priority. I'm not so haughty as to disregard Coach's advice.

Well, it turns out I was wrong about TopCoder. It's not only fizzbuzz: the problems with high point values do require some care with algorithm and datastructure selection. It's also not so much of a race as I'd thought. You get no points for an incorrect solution, and even very late answers (like with 12 hours of padding on a 75 minute problem) still get 30% credit.

I think coding time is just about the least important thing in programming. I'm well aware of the pitfalls of perfectionism and the whole nuanced worse is better concept. But I've very rarely been in a real-world programming situation in which the difference between 15 minutes and 1 hour made any practical difference, aside from labor cost. On the other hand, I've frequently seen that investing a little time in a thoughtful algorithm, test coverage, and an elegant implementation can pay off hugely. Naturally, there are many different assignments to the decision-theoretic parameters here; it's not surprising that TopCoder's scores are so simplistic (and well-suited to their business model).

I'm TopCoding in Java. Of course, I found myself Greenspunning almost immediately. The TopCoder rules explicitly allow code reuse, while penalizing dead code. Still, it feels like cheating to keep a warm Emacs buffer full of map/reduce/foldr/nth/setdefault around. A newbie will have to write and test that code, losing points against the veteran TopCoder for a reason that has nothing to do with skill.

Having attacked the TopCoder measure of programmer performance, I'm ready to praise it. First, the emphasis on speed accords with interview conditions. The high pressure and short duration of an interview is not ideal for sampling anyone's performance, but it's better than any of the alternatives I know. Second, just as in athletic cross-training, I think there's value in practicing against TopCoder's measure. It works against my natural perfectionism and, because it is so different from my daily routine, it helps me to strengthen in areas that may be seldom used and hence relatively inefficient.

TopCoder's FAQs are spartan, and the UI is confusing for me. There lots of sequential number ranges and acronyms, and after some fruitless web browsing/searching, I resorted to trial and error to infer their meanings. There aren't many context menus and the key bindings don't follow my OS standards (⌘-C/⌘-X/⌘-V) or the emacs defaults. Try ctrl-C/ctrl-X/ctrl-V for copy/cut/paste. The code editor is terrible, but for interview prep I'm using it in preference to Emacs; I won't have a kill ring or isearch-forward available at the whiteboard, either.

Nobody is verbally critiquing you as you tap out your TopCoder solutions, so they provide a compiler and a very rudimentary test framework (you can feed your program arbitrary program inputs and see the result along with whatever it wrote to stdout and stderr). If interview prep is your goal, it's probably still a good idea to do some whiteboarding and paper exercises, but I think the TopCoder environment is impoverished enough that you'll have a heightened awareness of your dependence on compiler and test feedback.

TopCoder is organized as a shallow, fixed-depth hierarchy of chat rooms. The leaf nodes are each associated with three problems of varying difficulty and point value. Problem statements give the general form of input and output along with several example i/o pairs and a sentence or two about each. The lowest-valued problem statements give an algorithm in prose. The statements of higher-valued problems give fewer hints. Also, higher-valued problems tend to require more work (compared to a hypothetical lower-valued problem whose hints have been erased).

There are competition rooms and practice rooms; different rules governing your actions apply depending on the context. Specifically, in competitions, there are discrete, synchronized phases for coding, code review, and a final non-interactive test round; these activities are concurrent for practice rooms. The practice rooms are created in anticipation of competitions and disappear later. It's too bad that the number of rooms and hence the number and variety of available practice problems swings so wildly (from hundreds of problems to 3). There is an archive where you can read the problem statements and look at final stats, but solutions (including your own) and the test oracle are unavailable.

Unsurprisingly, TopCoder problems are less overtly mathematical than those of Project Euler. Whereas my main annoyance with Project Euler was tedium associated with thematic repetition (e.g., primality testing), my main annoyance with TopCoder is tedium associated with parsing the regular language of each problem's input. Project Euler emphasizes mathematical insight and your own preferred blend of elegance/efficiency/creativity/..., while TopCoder emphasizes implementation speed. To be clear, "annoyance" is far from a primary adjective I'd use for either site; I recommend them both for pass-times or as interview preparation.

The "summary" button in each chat room shows you the list of everyone's who's been there. For each person, you can see overall experience level, rank w/r/t the room, and status/earned points for each problem. By double-clicking on a score, you can read that person's solution and optionally challenge it by providing an input for which you think it fails; TopCoder will execute the solution against your input and either cancel the other person's points and reward you, or punish you for your false allegation by subtracting points from your score.

My informal survey of submitted solutions shows that most coders leave sloppy mistakes in their final submissions, reflecting the time pressure and lack of incentive for craftsmanship. There are almost no code comments, but the code usually speaks for itself. I usually remove test and debugging code. I don't revise for clarity or efficiency. It is striking to me that apparently I value conceptual focus more highly than most other TopCoders: my solutions tend to explicitly compose well-known algorithms using the modularity features of my chosen language. Being uninterested in competition, I don't plan to destructure my own code, but I wonder if this is a competitive advantage for them? I like to think that under real-world conditions, my approach yields better reusability and code clarity, but I don't really have empirical evidence for that.

If I have inspired you to try TopCoder, beware that opening any problem statement starts its timer, and closing the problem does not pause or stop the timer. I don't exactly regret having sampled problems from various rooms and point levels before starting, but I also don't care about how I rank relative to anyone else.

Version numbers and (D)VCS

2009-10-11T16:04:00.015-05:00

I've spent a lot of time this weekend trying to adapt apply-version.nant, originally written for oopsnet and svn, to ormar and mercurial. It wasn't so easy to find guidance from others with similar goals, so hopefully this post makes the information more accessible.

Definitions

The primary purpose of software version numbers is to identify the code. When we distribute to users, the version number gives them a concise reference for use in communicating about bugs and available features.

A secondary purpose is to define a temporal order on distributions. Versions are normally numeric and monotonically increasing; higher versions are newer and hopefully better than older versions.

Conventionally, there is at least some human involvement in assigning version numbers. In proprietary software, concerns about sales normally are important. Often times, the technical issue of compatibility is difficult to treat formally, but human judgment is used to encode compatibility information in version numbers.

But it's also conventional to let the low-order bits of a version number be determined automatically. Whenever build inputs change, the behavior of the software may change, but nobody wants to be bothered incrementing version numbers for routine small changes.

Besides version numbers, it's common to hear of "build numbers." Sometimes the terms are used interchangeably, but I think it's useful to distinguish between (a) an identifier for the build input and (b) an identifier for the build event. Some people use (b) as a more convenient proxy for (a), and some people apparently really care about (b) itself, although I'm not sure why. Maybe it's because on some teams deployment is part of the build process*, and it's nice to have a formal record of deployments.

Theory and practice

I've used Subversion for nearly my whole career so far. It's a centralized version control system and sensibly enough it identifies historical events with natural numbers; revision 0 is repository creation. So, svn revision numbers are a very convenient basis for version numbers. Just check for consistency of the wc with a revision from the repository and use that revision number for the low-order version bits. Consistency between wc and repository for svn is a question of (a) uncommitted changes and (b) files or directories within the wc at different revisions.

This is a bit harder to do with some other centralized version control systems. In SCCS, revision numbers (SIDs) apply not to repositories but to individual files. Microsoft TFS has SVN-style revision numbers that they call "changeset numbers," but their implementation choices and tools make it difficult and expensive to answer the wc-repository consistency question. But fundamentally, in a cvcs, there's a global clock and that can serve as a basis for version numbering. In every cvcs I've seen, it's practical to use it that way although it might be easier in some cases (svn) and harder in others (tfs).

For distributed version control systems, we have no global clock. Fundamentally, events are temporally ordered only by causal relationships, so you can really only establish the primary property for version numbers: identifying build inputs. There's no general way to establish the secondary property that allows users to compare version numbers and decide which is newer. And yet, the mercurial project itself produces monotonic version numbers! How do they do it? Apparently by manually tagging.

How important is temporal ordering really? Certainly the most important thing is the capability for repeatable builds. Some DVCS projects have concise identifiers for build inputs; in hg and git we have hashcodes. Unfortunately for those of us on the .NET platform, Microsoft provides only 4 * 16 bits of space for version numbers in their assembly metadata specification. This isn't nearly enough for hg 160 bit changeset ids (though it could accommodate the potentially ambiguous 48 bit short form), especially if we want to use one or more of those four fields for encoding compatibility data.

A common special case

There's a very common special case of projects using dvcs for which we can establish an objective order on versions. There's often an official repository, whose event history meets our need.

Well that's fine in theory, but is it practical? Unfortunately for me, hg doesn't allow remote queries of a given repository's local timestamps ("revision numbers"). I hope that's due to an efficiency trade-off and not just a pedantic effort ("these revision numbers aren't guaranteed to match those in your clone; use changeset ids instead!").

The good news is that in hg, revision numbers consistency is preserved under clone and pull operations. If you commit in your repository, you may irreconcilably lose consistency, but as long as you abstain from making changes you and the other repo will agree on the bijective function between revision numbers and changeset ids. So my plan for .NET assembly versioning in my googlecode hg repositories is to use a pristine clone for official builds and at least one separate clone for feature development and bug fixes.

*For the IT web apps I've worked on, we had automated deployment as part of our CI routine, but we were satisfied to have an svn branch per deployment target. Actually, we had one svn branch per deployment target equivalence class representative. Really we had a small number of user communities (e.g., end-users, beta-testers, trainees, programmers), and we had a branch for each of them and the server clusters for each. (back)

What I did on my summer vacation

2009-10-01T17:52:00.021-05:00

I spent the second week of September 2009 in Yellowstone Country. This is my trip report.

My traveling companions were my parents, my brother, and his girlfriend. We met at BZN, where we rented a minivan for the drive to Yellowstone House. It was a rainy afternoon but between showers we caught glimpses of that signature Montana light that plays over the foothills and dramatically highlights the mountain peaks. We ate dinner at the Chico Dining Room, always a safe bet for fine dining. Yellowstone House has wifi and a PowerMac G4.

For the next two days we went flyfishing with Grossenbacher Guides Bill, Bo, Brad Ehrnman, Brett Seng, and Brian Grossenbacher.

The thing to love or hate about flyfishing is that it emphasizes technique. The motion of the fly is determined not by its own weight (as it is in baitfishing) by the weight distributed along your line; there is physical complexity here that corresponds to a high degree of choice in casting. Beyond that, there is a pretty large space of materials and configurations in the flies, and the trout discriminate taking into account the season, time of day, and past experience. I'm a novice, but more experienced flyfishermen explicitly use ecological knowledge in addition to recent observations of insect activity and fish feeding patterns. So, I can recommend flyfishing if you enjoy skill acquisition.

Someone once expressed surprise that I'd participate in an activity that involves cruelty to fish. Well, I've not noticed a strong trend either way among baitfishermen, but every flyfishermen I've encountered has expressed concern for the health and well-being of the fish. They remove barbs from hooks in order to minimize injury during catch-and-release fishing, they take care to handle fish gently without damaging gills, and they release carefully. Those practices satisfy my moral compass.

We were not the only ones enjoying the river those days; we also observed eagles, ospreys, otters, and mergansers fishing.

On Monday we ate at the Pine Creek Lodge, and it was good. I will say though that the cinnamon fajita tastes like it sounds.

On Tuesday we drove to the North entrance of Yellowstone National Park at Gardiner, MT. On the way through Mammoth Hot Springs to Old Faithful Inn we saw elk, mule deer, bison, and a black bear but very sadly no moose. We stopped off to hike up the Mount Washburn Fire Lookout, where we saw many chipmunks, a couple of marmots, and some big horn sheep. Unfortunately Dad stopped about a half mile from the summit due to pain in his knees.

At Old Faithful Inn we had drinks and bar food at the bar and then dinner in the Dining Room. I was disappointed that the Crow's Nest is off-limits, but I did see Old Faithful erupt. Our rooms were in a renovated section (early 1990s), so we had private bathrooms.

On Wednesday we hiked half way to
Artist Point along the Grand Canyon of the Yellowstone. Dad stayed back. The canyonlands supposedly harbor moose, but not surprisingly we didn't see them along the heavily trafficked trail. We drove to view a petrified tree and then we drove on to the Lamar Valley. There we photographed a buffalo at close range and did some fishing in the Lamar River, a tributary of the Yellowstone. At one point I misjudged the depth of the river and waded into chest-high water, drowning my phone.

We tried to eat at Helen's, home of the infamous Hateful Burger, but it was closed and for sale. Instead we ate at Zona Rosa in Livingston, where we had superb Latin American food at very reasonable prices. They were new at that time and did not accept credit cards or serve alcoholic beverages. Nearby landmarks include an enormous Taco John's sign and a car/truck wash.

Thursday we did guided fishing on the Madison River. The fish are generally larger and smarter than those of the Yellowstone. We caught very few whitefish, but a number of large trout. We ate at the Chico Saloon, which is definitely not served by the same kitchen as the dining room, while we observed some sporting event on TV.

Friday we hung around Yellowstone House, doing a little fishing from the bank of the Yellowstone River and reading and puzzle-solving. We had dinner again at Chico Hot Springs Dining Room, and then back to Yellowstone House for our last night in Montana.

We didn't see any grizzly bears this year, and I still have yet to see wild wolves or moose. Maybe next time.

The trust relationship between the primary domain and the trusted domain failed.

2009-09-13T20:39:00.015-05:00

Over the past month, I've spent a couple of hours puzzling over a bug in the implementation of Microsoft's System.Security.Principal.WindowsPrincipal.IsInRole. I want to say something about the general problem and then I'll talk specifically about this problem instance and how I worked around it.

The general form of the problem is something I often cited in code reviews at Anheuser-Busch. Now I believe that Microsoft owes its success much more to salesmanship than engineering ability, but this is a high-profile product with years of history in the field, so I'm surprised the bug has survived so long. I guess it's worth publishing my advice (which I'm sure did not originate with me):

Throw or propagate exceptions at the right level of abstraction. The Java language designers were on to something with checked exceptions: exceptions really can be regarded as part of your API (see also criticism linked at c2). If you have a method String Profile.GetSetting(String) with two implementations, one of which uses ADO.NET for relational database storage while the other uses System.IO.File for filesystem storage, then callers should never see System.Data.Common.DbExceptions. If, as the maintainer of Profile.GetSetting, you anticipate ADO.NET or System.IO exceptions, then you should catch them and throw exceptions of some more appropriate type(s). It's OK and usually a good idea to use what you catch to initialize the InnerException property of what you throw: that's useful diagnostic information. But, you should make the effort to wrap the exceptions you propagate when doing so mitigates a leaky abstraction.

Use distinct exception types for distinct equivalence classes of conditions you think callers might reasonably treat in different ways. I think it's helpful to think about Lisp conditions, which generalize exceptions, when you make design decisions involving errors.

Document the exceptions you throw.

And without further ado, the specifics:

Bug 4541

Summary:

The trust relationship between the primary domain and the trusted domain failed.

Product:

REDACTED

Reporter:

Foy, Sean

Component:

triage

Assignee:

Foy, Sean

Status:

ASSIGNED

Severity:

blocker

CC:

michael.jorgensen@REDACTED

Priority:

Version:

unspecified

Hardware:

All

OS:

All

URL:

http://tahaze-ww07.REDACTED/REDACTED/requests/19791117T120000?requestor=sean.foy@REDACTED

Whiteboard:

Time tracking:

Orig. Est.	Actual Hours	Hours Worked	Hours Left	%Complete	Gain
8.0	1.1	1.0	0.1	90	6.9

Deadline:

Description Foy, Sean 2009-09-13 19:08:54 CDT

Steps to reproduce:
0. logout if you're not using Windows Authentication.
1. create a request
2. follow the link to the request from the assignment page
3. authenticate (implicitly or otherwise) using Windows Authentication
Expected results: request edit page
Actual results: authorization (IsInRole predicate evaluation on a
WindowsPrincipal) fails.

System.SystemException: The trust relationship between the primary domain and the trusted domain failed.

at
System.Security.Principal.NTAccount.TranslateToSids(IdentityReferenceCollection
sourceAccounts, Boolean& someFailed)
at System.Security.Principal.NTAccount.Translate(IdentityReferenceCollection
sourceAccounts, Type targetType, Boolean& someFailed)
at System.Security.Principal.NTAccount.Translate(IdentityReferenceCollection
sourceAccounts, Type targetType, Boolean forceSuccess)
at System.Security.Principal.WindowsPrincipal.IsInRole(String role)
at MVCUtils.IsInRole(String role) in
c:\documents-and-settings\sean.foy\my-documents\REDACTED\MvcUtils.cs:line 218
at REDACTED.REDACTED.IsInRole(String rolename) in
c:\documents-and-settings\sean.foy\my-documents\REDACTED\REDACTED.cs:line 284
at REDACTED.Viewee03e5938d284b4d944019fc1e9c8130.RenderViewLevel0() in
c:\documents-and-settings\sean.foy\my-documents\REDACTED\Views\Request\requestform.spark:line
20
at REDACTED.Viewee03e5938d284b4d944019fc1e9c8130.RenderView(TextWriter writer) in
c:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\Temporary ASP.NET
Files\REDACTED\930b9661\fd62837e49004099a1fddf1e5288ae22-1.cs:line 1240
at Spark.Web.Mvc.SparkView.Render(ViewContext viewContext, TextWriter
writer)
at System.Web.Mvc.ViewResultBase.ExecuteResult(ControllerContext context)
at
System.Web.Mvc.ControllerActionInvoker.InvokeActionResult(ControllerContext
controllerContext, ActionResult actionResult)
at
System.Web.Mvc.ControllerActionInvoker.<>c__DisplayClass11.<invokeactionresultwithfilters>b__e()
at
System.Web.Mvc.ControllerActionInvoker.InvokeActionResultFilter(IResultFilter
filter, ResultExecutingContext preContext, Func`1 continuation)
at
System.Web.Mvc.ControllerActionInvoker.<>c__DisplayClass11.<>c__DisplayClass13.<invokeactionresultwithfilters>b__10()
at
System.Web.Mvc.ControllerActionInvoker.InvokeActionResultWithFilters(ControllerContext
controllerContext, IList`1 filters, ActionResult actionResult)
at System.Web.Mvc.ControllerActionInvoker.InvokeAction(ControllerContext
controllerContext, String actionName)
at System.Web.Mvc.Controller.ExecuteCore()
at System.Web.Mvc.ControllerBase.Execute(RequestContext requestContext)
at
System.Web.Mvc.ControllerBase.System.Web.Mvc.IController.Execute(RequestContext
requestContext)
at System.Web.Mvc.MvcHandler.ProcessRequest(HttpContextBase httpContext)
at System.Web.Mvc.MvcHandler.ProcessRequest(HttpContext httpContext)
at
System.Web.Mvc.MvcHandler.System.Web.IHttpHandler.ProcessRequest(HttpContext
httpContext)
at
System.Web.HttpApplication.CallHandlerExecutionStep.System.Web.HttpApplication.IExecutionStep.Execute()
at System.Web.HttpApplication.ExecuteStep(IExecutionStep step, Boolean&
completedSynchronously)

REDACTED, Version=1.0.4835.11, Culture=neutral, PublicKeyToken=null version
1.0.4835.11

Comment 1 Foy, Sean 2009-09-13 20:08:54 CDT

Additional hours worked: 1.0 There are no documented exceptions for WindowsPrincipal.IsInRole and although Google finds many reports of this exception, the most promising resolutions are vaguely described patches from Microsoft for SharePoint. But empirically I've found that I get reasonable answers for queries of the form
p.IsInRole(@"domain\group") and
p.IsInRole(@"group@domain")
where the domain name can be any non-empty string. But I get this exception for queries of the form
p.IsInRole(@"group").
Evidently IsInRole expects a domain name and throws this exception when none is present.

And here's the patch:


Index: MvcUtils.cs
===================================================================
--- MvcUtils.cs    (revision 4851)
+++ MvcUtils.cs    (working copy)
@@ -1,6 +1,7 @@
 using System;
 using System.Collections.Generic;
 using System.Linq;
+using System.Security.Principal;
 using System.Text;
 using System.Text.RegularExpressions;
 using System.Web;
@@ -214,8 +215,22 @@
         return result.ToString();
     }
 
+    public static Boolean IsInRole(IPrincipal p, String role) {
+        try {
+            return p.Identity.IsAuthenticated &amp;&amp; p.IsInRole(role);
+        }
+        catch (SystemException e) {
+            // see bug 4541
+            if (!e.Message.StartsWith("The trust relationship between the primary domain and the trusted domain failed.")) {
+                throw;
+            }
+            
+            return false;
+        }
+    }
+
     public static Boolean IsInRole(String role) {
-        return HttpContext.Current.User.Identity.IsAuthenticated &amp;&amp; HttpContext.Current.User.IsInRole(role);
+        return IsInRole(HttpContext.Current.User, role);
     }
 }
 
Index: TestMvcUtils.cs
===================================================================
--- TestMvcUtils.cs    (revision 4851)
+++ TestMvcUtils.cs    (working copy)
@@ -175,6 +175,32 @@
                 r => authorized.IsInRole(r)));
     }
 
+    private System.Security.Principal.WindowsPrincipal getWindowsPrincipal() {
+        return
+            new System.Security.Principal.WindowsPrincipal(
+                System.Security.Principal.WindowsIdentity.GetCurrent());
+
+    }
+
+    [Test]
+    public void WindowsPrincipalIsInRoleExpectsDomain() {
+        var p = getWindowsPrincipal();
+        try {
+            p.IsInRole("whatever");
+            Assert.Fail("maybe we can simplify MvcUtils.IsInRole after all");
+        }
+        catch (SystemException) {
+            //expected
+        }
+    }
+
+    [Test]
+    public void IsInRoleToleratesAbsenceOfDomains() {
+        var p = getWindowsPrincipal();
+        MVCUtils.IsInRole(p, @"domain\whatever");
+        MVCUtils.IsInRole(p, "whatever@domain");
+    }
+
     public Mock<httpcontextbase> mockContext(String applicationRoot, String requestUrl) {</httpcontextbase>
         var appRoot = new Uri(applicationRoot);
         var ctx = new Mock<httpcontextbase>();</httpcontextbase>
Index: Web.config
===================================================================
--- Web.config    (revision 4851)
+++ Web.config    (working copy)
@@ -12,8 +12,8 @@
     <add key="ActiveDirectoryForestName" value="REDACTED"></add>
     <add key="ActiveDirectoryUserName" value="REDACTED\svc.tahaze.websql"></add>
     <add key="ActiveDirectoryPassword" value="REDACTED"></add>
-    <add key="map-to-role-msl" value="REDACTED_Form_Editors"></add>
-    <add key="map-to-role-admin" value="REDACTED_Admins"></add>
+    <add key="map-to-role-msl" value="REDACTED\REDACTED_Form_Editors"></add>
+    <add key="map-to-role-admin" value="REDACTED\REDACTED_Admins"></add>
     <add key="MVCAuthnz.CookieAuthenticationHttpModule.signingKey" value="REDACTED"></add>
     <add key="seanfoy.oopsnet.assemblyQualifiedName" value="seanfoy.oopsnet.ASPNetErrorHandler,seanfoy.oopsnet"></add>
     <add key="seanfoy.oopsnet.handlerName" value="handleError"></add>
@@ -84,7 +84,6 @@
     
   
   -->
-
   <system.web></system.web>
     <httpmodules></httpmodules>
       <add name="UrlRoutingModule" type="System.Web.Routing.UrlRoutingModule, System.Web.Routing"></add>

Paging for Mutable Data

2009-08-02T20:43:00.021-05:00

Many web applications provide segmented result sets in response to queries. This approach can conserve server-side effort when users decide to reformulate a query or use partial results rather than actually attending to all the results. Even if a user will eventually demand the complete set of results, paging can smooth the demand/time graph, lowering the peaks.

It's easy to find library support for paging, but it's rare to find good support for paging mutable data. Typically the library provides a set of results given an integer offset and page size. Another way to characterize this functionality is to say that the library does integer arithmetic. I don't object to procedural abstraction, but it seems to me that this is not only simple but simplistic.

We can always enumerate our datasets, but I think that users don't normally care about specific offsets. I for one normally care about the whole set of results that satisfy my query. Or at least I think I do, until I see from the results that my query spec wasn't quite right. Anyway, I think we users normally formulate queries in terms of the problem domain, not in terms of sequences of integers. I don't normally care about the eleventh or the twenty sixth result because of its ordinal rank; I just want the next element of my dataset.

So where's the problem? We know that we can setup a one-to-one correspondence between integers and countable data sets, so why not use convenient integers to specify pages? As long as the data are immutable, or users are tolerant of certain inaccuracies, we can use integers to identify pages.

But, in general the data might be changing even as users peruse the results. Suppose I specify a query q, which predicate is satisfied by the following ordered result elements at time 0: <A, C, E, G, I, J>. At time 1, F begins to satisfy q so the result set becomes <A, C, E, F, G, I, J>. If my page size is 2 and I was looking at the second page at time 0, what should I see when I proceed to the third page at time 2? Do I see G and I because results_t2[(page - 1) * size] = results_t2[4] identifies G? Would the apparent duplicate result in that case be confusing or just annoying? Should I see I and J because I started viewing at t_0 and therefore my page request should be interpreted as results_t0[4] = I?

Suppose an item I've already seen is deleted as I page through results. Will I see the item that would have been first on the next page at all?

If we're going to avoid anomalous disappearances and false duplicates, we can't rely on naively recomputing the function from integers to results on-demand. Perhaps we can store history and use an (page-number, timestamp) pair to index our pages.

If the cost of storing history is too great, there are compromises available aside from allowing both false apparent duplicates and omissions of elements that have existed throughout. We can allow repetition in order to avoid erroneous omission, or we can allow omission to avoid false repetition. Finally, if we disallow duplicates, we can use observable properties of the elements themselves as page indices. Often, (apparent) duplicates are undesirable anyway:

Summaries are often preferred over raw data
A	B
pepperoni	pepperoni: 4
mushroom	mushroom: 2
pepperoni	cheese: 1
mushroom
pepperoni
cheese
pepperoni

In my experience, the most common scenario involves concurrent usage, mutable underlying data, and two laws of user expectation: (1) if an item satisfied the query predicate continuously from before the query was issued to after the user reached the last page of results, the user should see the item and (2) one unchanging item should appear at most once in the pages.

Where these requirements are satisfiable, we'd like to encapsulate and reuse the implementation details. The interface should work in domain terms: given a data element, total order relation, and window size as input, it could provide the next n elements.

The main idea here is pretty simple, both in conception and in implementation. Part of the motivation for this blog post though was to discuss the details of client interface design and testing.

Here's my first test design for the core functionality:


[Test]
public void paging() {
    const int count =
        (int)(
              // first page: stable + deleted
              (pageSize + 1.0) * 3.0 / (1 + 1 + 0) +
              // second page: stable + deleted + ins
              (pageSize + 1.0) * 3.0 / (1 + 1 + 0) +
              // third page: stable + ins
              (pageSize + 1.0) * 3.0 / (1 + 1 + 0));
    var items = Enumerable.Range(0, count).ToList();
    var stable =
        Enumerable.Where(
            items,
            x => x % 3 == 0).ToList();
    var inserting =
        Enumerable.Where(
            items,
            x => x % 3 == 1).ToList();
    var deleting =
        Enumerable.Where(
            items,
            x => x % 3 == 2).ToList();
    var attendance =
        Enumerable.ToDictionary(
            items,
            x => x,
            x => 0);
    try {
        foreach (var i in stable) {
            persist(i);
        }
        foreach (var i in deleting) {
            persist(i);
        }
        int timer = 0;
        foreach (var p in getPages()) {
            foreach (var i in p) {
                ++attendance[i];
            }
            if (timer == 1) {
                foreach (var ins in inserting) {
                    persist(ins);
                }
            }
            else if (timer == 2) {
                foreach (var del in deleting) {
                    delete(del);
                }
            }
            ++timer;
        }
        Assert.IsTrue(timer > 3, "There were too few pages in this test to see both kinds of concurrency anomaly.");
        Assert.IsTrue(
            Enumerable.All(
                stable,
                x => attendance[x] == 1),
            "Every item that is present throughout the process should be seen exactly once.");
        Assert.IsTrue(
            Enumerable.Any(
                deleting,
                x => attendance[x] == 0),
            "Some item deleted during this test should not have been seen. This may indicate eager retrieval of pages, which is isn't feasible in general (for large datasets).");
        Assert.IsFalse(
            Enumerable.Any(
                items,
                x => attendance[x] > 1),
            "No item should be seen twice.");
        // it's OK if items inserted during the test are seen
    }
    finally {
        foreach (var i in items) {
            delete(i);
        }
    }
}

For me, the best thing about this code is its strong focus on two key axioms. I partition all possible inputs in such a way as to demonstrate those, and then I arrange to draw samples from those partitions in what I hope is pretty unobtrusive way. I check that I've covered the necessary cases and then I show that the axioms are true for my sample data. getPages simulates sequential uses of the paging abstraction by a client:


protected override IEnumerable<IEnumerable<int>> getPages() {
    const int pageSize = 10;
    LocalItem memento = null;
    IEnumerable<LocalItem> p;
    do {
        var slicedCriteria =
            Potpourri.Page<LocalItem>.page(
                DetachedCriteria.For(typeof(LocalItem)),
                new [] {"itemNumber"},
                memento);
        p = LocalItem.SlicedFindAll(0, pageSize + 1, slicedCriteria);
        memento =
            Enumerable.LastOrDefault(p);
        yield return
            Potpourri.slice(
                Enumerable.Select(
                    p,
                    i => elementToInt(i)),
                0,
                pageSize);
    } while (Enumerable.Count(p) > pageSize);
}

Details: in real life this code runs against shared relational database instances, but for testing purposes I execute against SQLite for isolation. This test occurs in an abstract TestFixture with two concrete subclasses, one of whose getPages method is shown above.

The other uses the raw NHibernate windowing primitives in the naive way; that test class is marked with the IgnoreAttribute because that approach is doomed. I actually started by writing that test case as an executable demonstration of the motivation for the less obvious technique.

Here's my second test design. I think on balance it's actually less readable than the first attempt. I wonder how many people would agree?


[Test]
public void insertionSansDuplicates() {
    insertion(fetchPageByValueEquality);
}

[Test]
[ExpectedException(typeof(DuplicateDetectedException))]
public void insertionAnomalies() {
    insertion(fetchPageByOffset);
}

[Test]
public void deletionSansSkips() {
    deletion(fetchPageByValueEquality);
}

[Test]
[ExpectedException(typeof(AnomalyDetectedException))]
public void deletionAnomalies() {
    deletion(fetchPageByOffset);
}

Again, I wrote working test code for both straightforward, broken use of primitives and for the approach that suits my needs.

Here's how I address the two kinds of trouble that can result from trying to use offsets for paging in the face of concurrent modification:


private class AnomalyDetectedException : Exception {}
private class DuplicateDetectedException : AnomalyDetectedException {}
private void insertion(FetchPage fetchPage) {
    var q = DetachedCriteria.For<Beer>();
    var O = new [] {"ABV", "BrewDate", "Variety"};
    Paging.AddOrder(q, O);
    var seenit = new HashSet<Beer>();
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var page =
                fetchPage(
                    s,
                    q,
                    O,
                    null,
                    pageSize + 1);
            foreach (Beer i in Enumerable.TakeWhile(page, (elt, i) => i < pageSize)) {
                if (seenit.Contains(i)) throw new DuplicateDetectedException();
                seenit.Add(i);
            }
            var first = (Beer)page[0];
            var nouveau =
                new Beer {
                    Variety = "not" + first.Variety,
                    BrewDate = first.BrewDate,
                    ABV = first.ABV / 2};
            s.Save(nouveau);
            s.Flush();
            page =
                fetchPage(s, q, O, Enumerable.Last(page), pageSize);
            foreach (Beer i in page) {
                if (seenit.Contains(i)) throw new DuplicateDetectedException();
                seenit.Add(i);
            }
        }
    }
}

private void deletion(FetchPage fetchPage) {
    var q = DetachedCriteria.For<Beer>();
    var O = new [] {"ABV", "BrewDate", "Variety"};
    Paging.AddOrder(q, O);
    var expected = new HashSet<Object>();
    var actual = new HashSet<Object>();
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var page = fetchPage(s, q, O, null, pageSize);
            foreach (var i in page) expected.Add(i);
            foreach (var i in page) actual.Add(i);
            foreach (var i in fetchPage(s, q, O, Enumerable.Last(page), pageSize)) {
                expected.Add(i);
            }
            s.Delete(page[0]);
            s.Flush();
            foreach (var i in fetchPage(s, q, O, Enumerable.Last(page), pageSize)) {
                actual.Add(i);
            }

            actual.SymmetricExceptWith(expected);
            if (0 != actual.Count) throw new AnomalyDetectedException();
        }
    }
}

The test data are much less carefully prepared:


[TestFixtureSetUp]
public void setup() {
    Persistence.rebuildDB();
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            Assert.That(s.Linq<Bottle>().Count(), Is.GreaterThan(pageSize));
            Assert.That(s.Linq<Beer>().Count(), Is.GreaterThan(pageSize));
        }
    }
}

That rebuildDB method isn't particularly geared towards the paging problem. It's really intended for use with a broader class of NHibernate-related addons.

I also have boundary test cases:


[Test]
public void empty() {
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var max =
                Queryable.Max(
                    s.Linq<Bottle>(),
                    i => i.Serial);
            var source =
                DetachedCriteria.For(
                    typeof(Bottle));
            Assert.IsFalse(
                Enumerable.Any(
                    Paging.Page(
                        s,
                        source,
                        new [] {"Serial"},
                        new Bottle { Serial = max + 1 },
                        pageSize)));
        }
    }
}

[Test]
public void singleton() {
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var max =
                Queryable.Max(
                    s.Linq<Bottle>(),
                    i => i.Serial);
            var source =
                DetachedCriteria.For(
                    typeof(Bottle)).
                AddOrder(Order.Asc("Serial"));
            Assert.AreEqual(
                1,
                Enumerable.Count(
                    Paging.Page(
                        s,
                        source,
                        new [] {"Serial"},
                        new Bottle { Serial = max },
                        pageSize)));
        }
    }
}

When there's no concurrent data modification, we get equivalent results with the simpler, direct use of NHibernate primitives as with the more complicated use of my paging abstraction:


[Test]
public void naturals() {
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var Q =
                Enumerable.Select(
                    Enumerable.Range(0, 2),
                    x => DetachedCriteria.For<Bottle>().AddOrder(Order.Asc("Serial"))).ToArray();
            Assert.AreEqual(
                Q[0].GetExecutableCriteria(s).SetMaxResults(pageSize).List<Bottle>(),
                Paging.Page<Bottle>(s, Q[1], new [] {"Serial"}, null, pageSize));
        }
    }
}

[Test]
public void beers() {
    using (var factory = Persistence.makeSessionFactory()) {
        using (var s = factory.OpenSession()) {
            var O = new [] {"ABV", "BrewDate", "Variety"};
            // ICriterion instances are mutable and don't
            // expose a copy constructor or clone method,
            // so we must make two criteria, just alike.
            var Q =
                Enumerable.Select(
                    Enumerable.Range(0, 2),
                    x => DetachedCriteria.For<Beer>()).ToArray();
            foreach (var q in Q) {
                Paging.AddOrder(q, O);
            }
            Assert.AreEqual(
                Q[0].GetExecutableCriteria(s).SetMaxResults(pageSize).List<Beer>(),
                Paging.Page(s, Q[1], O, null, pageSize));
        }
    }
}

I welcome your comments and criticism. Please see ormar for details or to publish your own code review.

vogon fodder

2009-08-02T13:12:00.025-05:00

In this post, I show-and-tell about automated paper-pushing.

I spent considerable effort at work last week building something that is minimally useful. I am preoccupied by the conflict between the demands of professionalism and the idiotic/cynical mockery of professionalism that is usual (though not universal) in large organizations. But I've got to eat and I should focus on problems I can realistically solve. For now, let's accept the demands of management without question and focus on how to satisfy the demands at minimum cost to human life. In the words of Steve Jobs:

Well, let's say you can shave 10 seconds off of the boot time. Multiply that by five million users and thats 50 million seconds, every single day. Over a year, that's probably dozens of lifetimes. So if you make it boot ten seconds faster, you've saved a dozen lives. That's really worth it, don't you think?

Your manager emails you an MSWord document and asks you fill it out once per software deployment. It should list every affected "object" and indicate when if ever "User" has been notified, when and who if ever "BAM" has approved, and it should reference the other paperwork associated with the project. What do you do?

Clearly, the right answer involves CI and LaTeX. In my case: svn, ccnet, Bugzilla, python, xslt, ruby, LaTeX, perl, and pdf.

We've been using CI with SVN to do deployments since 2004. There's a branch for each deployment target, and a CI project associated with each of those branches. The CI builds usually correspond to a single commit, but we don't insist on that; when commits come fast enough we go for speed over precision in who's "on the hook" for breaking changes. So the first problem is to find the union of affected "objects" over the set of svn commits in the deployment.

The term "object" is taken from the argot of the RPGers, who are the oldest and largest group of software people at our company. For them, "object" often refers to a printed tabular summary of data but more generally can refer to a program for any purpose. The usual custom outside the RPG tribe is to list as "objects" ui elements, but sometimes instead OO classes or source files are listed. It's not worth being too careful about this, because the real goal is pro forma compliance with a vague demand for documentation. Users basically want release notes, and engineers already get precise, accurate, and efficient answers to technical questions from svn and Bugzilla. The form really just needs to exist and, at a glance, to appear normal.

Our CI system CruiseControl.NET has a feature called modification writer that renders metadata about a build to XML. This provides a list of added, deleted, and textually-modified files for each commit that's new since the last build:

<?xml version="1.0" encoding="utf-8"?>
<ArrayOfModification xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<Modification>
  <Type>Modified</Type>
  <FileName>ccnet-self.config</FileName>
  <FolderName>/ccnet</FolderName>
  <ModifiedTime>2009-07-24T10:23:08.162158-05:00</ModifiedTime>
  <UserName>sean.foy</UserName>
  <ChangeNumber>4413</ChangeNumber>
  <Version />
  <Comment>whitespace
[Bug 50,51,3783]</Comment>
  <IssueUrl>https://bugzilla.thcg.net/buglist.cgi?bug_id=50,51,3783</IssueUrl>
</Modification>
</ArrayOfModification>

We integrated SVN and Bugzilla in 2004, and so since that time we've been able to correlate commits with bugs. This gives us informal commentary about the motivations and the design considerations for each commit, plus metadata including who was involved in the process, how much time each of us spent, whether we paired or got code review, whether dbas got involved, who approved deployment, etc. Well, at least in principle. Actually, only one or two projects have ever really taken advantage of these capabilities. But the point is that this metadata fits the purported goal of our paperwork, and it's useful and easily accessible, and it exists for at least one project. It's the best we can do, and it's pretty good. So we've got to use it.

Python is a fairly pleasant language to work in and nobody's terrified by its syntax. It also has great libraries for screen-scraping. Accordingly, we used a python program to augment ccnet's modifications xml. We read the ccnet xml and use the bugtraq standard to write back the set of relevant bugs:

<ArrayOfModification>
<Modification>
  <Type>Modified</Type>
  <FileName>ccnet-self.config</FileName>
  <FolderName>/ccnet</FolderName>
  <ModifiedTime>2009-07-24T10:23:08.162158-05:00</ModifiedTime>
  <UserName>sean.foy</UserName>
  <ChangeNumber>4413</ChangeNumber>
  <Version />
  <Comment>whitespace
[Bug 50,51,3783]</Comment>
  <IssueUrl>https://bugzilla.thcg.net/buglist.cgi?bug_id=50,51,3783</IssueUrl>
  <database />
  <flags>
    <flag id="1882" name="QCApproved" setter="michael.jorgensen@covidien.com" status="+" />
  </flags>
</Modification>
</ArrayOfModification>

Now we have all the answers we need to fill out our worksheet in XML. We just need to produce MSWord output (good luck). Well, MSWord probably isn't really necessary. That's what's expected, but also we should keep in mind that the goal is pro forma compliance. This document's real use is to ward off auditors, so it just needs to exist and not look unusual. So, we want to typeset XML? Obviously we should consider DocBook, XSL-FO, and LaTeX. I looked into XSL-FO c. 2001 and DocBook c. 2002, but I know LaTeX best. I wanted to spend less than 4 hours on this little project, so I was satisfied to use LaTeX.

For processing XML, you could do worse than XSLT. It can be particularly nice as a declarative template specification: "make my input look like this". So, I used xslt to process the bz-augmented ccnet modifications xml into LaTeX:

<?xml version="1.0"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0" xmlns:fn="http://www.w3.org/2005/xpath-functions" xmlns:smf="http://seanfoy.thcg.net/xslt">
<xsl:output method="text" />

<xsl:param name="asr">application service request number</xsl:param>
<xsl:param name="builddate">the date these changes became effective</xsl:param>
<xsl:param name="trunkdeploymenttarget">unc path</xsl:param>
<xsl:param name="trunkdbserver">hostname</xsl:param>
<xsl:param name="trunkdbname">dbname</xsl:param>
<xsl:param name="productiondeploymenttarget">unc path</xsl:param>
<xsl:param name="productiondbserver">hostname</xsl:param>
<xsl:param name="productiondbname">dbname</xsl:param>

<xsl:function name="smf:latexlit">
  <xsl:param name="raw" />
  <xsl:value-of select="fn:replace(fn:replace($raw, '([$&amp;%#_{}~^\\])', '\\$1'), '\\\\', '\$\\backslash\$')" />
</xsl:function>

<xsl:template match="@*|node()">
</xsl:template>
<xsl:template match="/">
  <xsl:text>
\documentclass{article}

\usepackage{hyperref}
\usepackage{longtable}
\usepackage{latexsym}

\usepackage[document]{ragged2e}
\usepackage{wordlike}
\renewcommand{\familydefault}{phv} % Arial
\sloppy
\makeatletter
\renewcommand{\subsection}{\@startsection%
{subsection}%
{1}
{0em}
{-\baselineskip}%
{0.5\baselineskip}%
{\bfseries\LARGE\sffamily}}
\makeatother

\author{Sean Foy}
\title{Sample}

\begin{document}
\section*{Internet/Intranet Production Move Request}
\textbf{ASR /Track-it WO\#:} </xsl:text><xsl:value-of select="smf:latexlit($asr)" /><xsl:text>\hfill\textbf{Move Date:}

\textbf{Requestor/ User Notification Sent:} $\Box$ \textbf{Dated:}

\subsection*{Object(s): $\Box$Web \qquad $\Box$WebMethods (WM)}
\begin{longtable}{|l|l|}\hline
  </xsl:text>
  <xsl:for-each select="ArrayOfModification/Modification">
    <xsl:value-of select="smf:latexlit(FileName)" />
    <xsl:text>&amp; -r</xsl:text><xsl:value-of select="smf:latexlit(ChangeNumber)" />
    <xsl:if test="fn:not(fn:empty(IssueUrl))">
      <xsl:text> (</xsl:text><xsl:value-of select="smf:latexlit(IssueUrl)" /><xsl:text>)</xsl:text>
    </xsl:if>
    <xsl:text> \\</xsl:text>
  </xsl:for-each>
  <xsl:text>\hline
\end{longtable}

\subsection*{DB Object(s):}
\begin{longtable}{|l|l|}\hline
  </xsl:text>
  <xsl:for-each select="ArrayOfModification/Modification[database]">
    <xsl:value-of select="smf:latexlit(FileName)" />
    <xsl:text>&amp; -r</xsl:text><xsl:value-of select="smf:latexlit(ChangeNumber)" />
    <xsl:if test="fn:not(fn:empty(IssueUrl))">
      <xsl:text> (</xsl:text><xsl:value-of select="smf:latexlit(IssueUrl)" /><xsl:text>)</xsl:text>
    </xsl:if>
    <xsl:text> \\</xsl:text>
  </xsl:for-each>
  <xsl:text>
    \hline
\end{longtable}

\subsection*{Deployment Servers:}
\begin{tabular}{|l|l|l|}\hline
     &amp;
     Development&amp;
     Production\\\hline
     Web:&amp;
     \textbf{UNC:} </xsl:text><xsl:value-of select="smf:latexlit($trunkdeploymenttarget)" /><xsl:text>&amp;
     \textbf{UNC:} </xsl:text><xsl:value-of select="smf:latexlit($productiondeploymenttarget)" /><xsl:text>\\\hline
     DB:&amp;
     \textbf{Server:} </xsl:text><xsl:value-of select="smf:latexlit($trunkdbserver)" /><xsl:text> \textbf{Database:} </xsl:text><xsl:value-of select="smf:latexlit($trunkdbname)" /><xsl:text>&amp;
     \textbf{Server:} </xsl:text><xsl:value-of select="smf:latexlit($productiondbserver)" /><xsl:text> \textbf{Database:} </xsl:text><xsl:value-of select="smf:latexlit($productiondbname)" /><xsl:text>\\\hline
     WM:&amp;
     \textbf{UNC:}            &amp;
     \textbf{UNC:}            \\\hline
\end{tabular}

\rule{\textwidth}{0.25em}

\textbf{Move Approved by BAM}:

Signature: \underline{\makebox[2in][l]{}}

Date: \underline{\makebox[1in][l]{}}

\end{document}
  </xsl:text>
</xsl:template>
</xsl:stylesheet>

LaTeX is based on Don Knuth's TeX typesetting system. It's serious business: Turing-complete and designed specifically for the needs of the world's most demanding typographical experts.

For a while I thought about merging the bug and svn data here in LaTeX. My TeX-hacking skills are very weak now so I had in mind the python package. As I escaped for XSL the escape for LaTeX of the escape for Python of the LaTeX output I wanted, I thought I was probably making a mistake. LaTeX is great for typesetting, and capable of general computation, but it's awkward to express the heavy-lifting there (even in an embedded language). The python package is probably better used tactically, for simple comprehensions and the like -- not for elaborating significantly on the structure of the LaTeX markup.

We must compile LaTeX to obtain our output (normally PostScript or PDF). I use a perl script, latexmk, to manage the multi-phase compilation process and keep track of cleaning up the intermediate products.

So we want to combine (((xml and Buzilla) by python to xml) and xsl) by xslt to LaTeX by latexmk to PDF). We need to process our inputs and intermediate products in topological order; this is a build process. I've used make before, but it's a bit crufty. I prefer NAnt, whose XML syntax is more explicit and discoverable. From what I've seen of rake, I like it better than NAnt. NAnt's a priori boundary between its implementation and your build specification is confining. Rake draws no distinction between itself and your build specification.

# -*- mode: ruby -*-
# Render modifications as beautiful
# (or hideous!) PDF
#
# sample invocation:
# rake latexmk=vendor/latexmk/latexmk.pl modifications.pdf

require 'rake/clean'
require 'rexml/document'
require 'rexml/xpath'

transform = "#{ENV['transform'] || 'vendor/saxonb9-1-0-7n/bin/Transform.exe'}"
latexmk = "#{ENV['latexmk'] || 'vendor/latexmk/latexmk.pl'}"

modifications_xml = "#{ENV['modifications_xml'] || '../Artifacts/modifications.xml'}"

task :default => 'modifications.pdf'

task :clean => ['clobberhelper'] do
end

task :clobber => ['clobberhelper'] do
end

def contains_clobber(ts)
ts.each { |i|
  return true if (i == 'clobber') || contains_clobber(Rake::Task[i].prerequisites)
}
return false
end

task :clobberhelper do |t|
if contains_clobber(Rake::application().top_level())
  sh latexmk, '-C'
else
  sh latexmk, '-c'
end
end

file 'modifications.tex' => [modifications_xml, 'modifications.xsl'] do |t|
xsl_params = {}
begin
  f = File.new('modifications.xsl')
  doc = REXML::Document.new(f)
  REXML::XPath.each(doc.root, 'xsl:param', {'xsl' => 'http://www.w3.org/1999/XSL/Transform'}) do |elt|
    xsl_params[elt.attributes['name']] = ENV[elt.attributes['name']] || elt.text
  end
ensure
  f.close unless f.nil?
end
xsl_args = xsl_params.inject([]){ |accum, (key, value)|
  accum << "#{key}=#{value}"
}
sh transform, "-s:#{modifications_xml}", '-xsl:modifications.xsl', '-o:modifications.tex', *xsl_args
end
CLEAN.include('modifications.tex')

file 'modifications.pdf' => ['modifications.tex'] do |t|
sh latexmk, '-pdf', 'modifications.tex'
end

If you don't know about rake, one point of confusion is that rake clean conventionally means "remove intermediates" while rake clobber means "remove intermediate and final outputs".

With my use of latexmk, I encountered a technical problem in the implementation of the standard clean and clobber rake tasks: latexmk needs the .tex file to decide what to clean up, but rake wants to clean (removing the .tex) before it clobbers. I needed to let latexmk do its job before clean, and latexmk needs to know whether to clean up the PDF or just the intermediates. My solution was to add a dependency clobberhelper for the clean task to call latexmk's cleanup routine. clobberhelper searches rake's dependency graph for clobber in order to decide how to call latexmk.

Finally, we have a corporate commitment to .NET and so most of our projects benefit from NAnt's understanding of .NET. We want an easy way to use this motley assortment of tools with our existing NAnt build files:

<?xml version="1.0" encoding="utf-8"?>
<project name="sdim" default="move-worksheet">
<property name="artifacts_dir" value="." overwrite="false" />
<!-- nant for Windows doesn't use the cygwin path so
     you need to chdir to %cygwin_home%\bin and then
     run %cygwin_home%\path\to\python or
     install Windows python and do e.g.,
     C:\Python31\python.exe -->
<property name="python" value="C:\Python31\python.exe" overwrite="false" />
<property name="rake" value="C:\Ruby\bin\rake.bat" overwrite="false" />
<property name="modifications_xml" value="modifications.xml" overwrite="false" />

<target name="move-worksheet">
  <exec program="${python}">
    <arg line="bzaugment.py ${path::combine(artifacts_dir, modifications_xml)} -o ${path::combine(artifacts_dir, 'modifications.augmented.xml')}" />
  </exec>
  <exec program="${rake}">
    <arg line="modifications_xml=${path::combine(artifacts_dir, 'modifications.augmented.xml')}" />
  </exec>
</target>

<target name="clean">
  <exec program="${rake}">
    <arg line="clobber" />
  </exec>
  <delete file="${path::combine(artifacts_dir, 'modifications.augmented.xml')}" />
</target>
</project>

I still have some reservations about the morality of this. On the one hand, no human should waste even 30 minutes of precious life preparing ambiguous, incomplete, inaccessible and uninsightful summaries of data that's already available, accurate, complete, and easily-accessible. On the other hand, you can lead a manager to water but you can't make him drink. This solution seems to balance those two forces, but by reducing the cost of useless redundancy, am I encouraging further bureaucratic malignancy?

Viola:

Anyway, I hope you enjoyed the tour of this motley assemblage of languages and tools.

Thanks to Josh Buedel for comments and suggestions during the preparation of this post.

23.1: new .emacs

2009-08-02T09:32:00.003-05:00


(setq ns-command-modifier 'meta)
(if (functionp 'tool-bar-mode)
   (tool-bar-mode -1))

(setq default-buffer-file-coding-system 'utf-8-unix)
(setq-default indent-tabs-mode nil)
(put 'erase-buffer 'disabled nil)

(cond
((file-exists-p "/sw/bin")
 ;; MacOS X + fink
 (setenv "PATH" (concat (getenv "PATH") ":/sw/bin"))
 (setq exec-path (append exec-path '("/sw/bin"))))
((file-exists-p "c:/")
 ;; Windows
 (setenv "PATH" (concat (getenv "PATH") ";c:\\cygwin-1.7\\bin"))
 (setq exec-path (append exec-path '("c:\\cygwin-1.7\\bin")))
 (if (require 'cygwin-mount nil t)
     (progn
       (cygwin-mount-activate)
       (setq shell-file-name "bash")
       (setenv "SHELL" shell-file-name)
       (setq w32-quote-process-args ?\")
       ;; for subprocesses invoked via the shell
       ;; (e.g., "shell -c command")
       (setq explicit-shell-file-name shell-file-name)
       (setq explicit-sh-args '("-login" "-i"))))
 ; (if I'm using Windows, I must be at work!)
 (setq bug-reference-url-format
       "https://bugzilla.thcg.net/show_bug.cgi?id=%s")
 (setq bug-reference-bug-regexp
       "\\(?:[Bb]ug ?#?\\|PR [a-z-+]+/\\)\\([0-9]+\\)")))

(dolist (
        prog-mode-hook
        '(python-mode java-mode ruby-mode js2-mode nxml-mode))
 (add-hook
  (car (read-from-string (concat (symbol-name prog-mode-hook) "-hook")))
  (lambda ()
    (setq indent-tabs-mode nil))))

(autoload 'python-mode "python-mode" "Python editing mode." t)
(add-to-list 'auto-mode-alist '("\\.py$" . python-mode))
(add-to-list 'interpreter-mode-alist '("python" . python-mode))
(add-hook 'python-mode-hook
         (if (null (getenv "LC_CTYPE"))
             (setenv "LC_CTYPE" "C")))

(add-to-list 'auto-mode-alist '("\\.cs$" . java-mode))

(autoload 'js2-mode "js2" nil t)
(add-to-list 'auto-mode-alist '("\\.js$" . js2-mode))

(autoload 'ruby-mode "ruby-mode" "Ruby editing mode." t)
(add-to-list 'auto-mode-alist '("\\.rb$" . ruby-mode))

(setq auto-mode-alist
     (cons '("\\.\\(xml\\|xsl\\|rng\\|xhtml\\)'" . nxml-mode)
           auto-mode-alist))
(add-to-list 'magic-mode-alist '("<\\?xml " . nxml-mode))

(if (load "auctex.el" t t t)
   (load "preview-latex.el" nil t t))
(setq ispell-program-name "aspell")
(setq ispell-extra-args '("--sug-mode=ultra"))

Andand.NET via monads

2009-06-06T16:50:00.029-05:00

In my previous post, I discussed a direct implementation of andand in C#. This time, I'll show a monadic implementation.

As Justin Wick pointed out on Reg Braithwaite's blog announcing Object#andand, andand can be viewed as a special case of the Maybe Monad. I've been hearing about how useful monads are for a few years, but until recently I hadn't occasion to use them directly. Would a monad formulation of andand be simpler and clearer to read? Would it be easier to understand, if not for everyone then at least for readers who are already familiar with the monad formalism? Here was an opportunity to find out.

For those who are totally unfamiliar with monads: they're a means of accommodating side-effects within the functional paradigm. By structuring input, output, exceptions, etc. with monads, you can restore referential transparency to functions that make use of these kinds of features. Monads are surprisingly versatile. You can build lists and arrays from monads, and in the case of arrays the use of monads makes it easy to use the type system to guarantee that client code fulfills a contract on which an efficient implementation of arrays depends. The famous applications of all the functional goodies in LINQ, such as data access and data-parallel computation, are organized around monads.

So, I refreshed my memory with Monads for Functional Programming and Confessions of a Used Programming Language Salesman followed some of their references: Comprehending Monads, Guarded Recursive Datatype Constructors, and Generalized Algebraic Data Types and Object-Oriented Programming. Thus fortified, I was ready to write some tests:


public class TestMonad<M> where M : MonadImpl<M>, new() {
    [Test]
    public void leftUnit() {
        var a = new Object();
        Assert.AreEqual(a, Monad.Star(Monad.Unit<Object, M>(() => a), b => Monad.Unit<Object, M>(() => b)).Just());
    }

    [Test]
    public void rightUnit() {
        var a = new Object();
        var m = Monad.Unit<Object, M>(() => a);
        Assert.AreEqual(
            Monad.Just(m),
            Monad.Just(
                Monad.Star(m, b => Monad.Unit<Object, M>(() => b))));
    }

    public Monad<String, M> an(Object o) {
        return Monad.Unit<String, M>(() => o.ToString());
    }

    public Monad<Int32, M> bo(Object o) {
        return Monad.Unit<Int32, M>(() => o.GetHashCode());
    }

    [Test]
    public void associative() {
        var m = Monad.Unit<Object, M>(() => new Object());
        Assert.AreEqual(
            Monad.Just(
                Monad.Star(
                    m,
                    a => Monad.Star(an(a), b => bo((String)b)))),
            Monad.Just(
                Monad.Star(
                    Monad.Star(m, a => an(a)),
                    b => bo(b))));
    }
}

I'm following the definitions from Monads for Functional Programming here: a Monad is a triple <M, Unit, ★> where M is a type constructor (generic type), Unit is a function from computations of type a to M a, and ★ applies a function to a monad.

My use of the name "Just" here is regrettable. The Maybe monad's type constructor is conventionally defined as a simple union:

Maybe a = Nothing | Just a

. So, by convention,

Just a

takes a computation of arbitrary type

to a monad representing that computation. My function "Just" is the inverse, taking a Monad to the computation it represents. I gather that the primitive monad operators are normally encapsulated so that control of side-effects is well localized/modularized. Usually, function composition on monad values is accomplished by ★, so it's not often necessary to explicitly extract raw computations from monads. Finally, monads seem to be most popular within the Haskell community, and pattern-matching is a pretty ubiquitous in Haskell programs. I think these reasons explain why (as far as I know) there's not much use and no standard name for the operation I call "Just" in my code.

Having translated the mathematical and Haskell definitions of monad into C#, I was ready to check that my translation could extend to an example application shown elsewhere:


[TestFixture]
public class TestMaybeMonad : TestMonad<MaybeMonadImpl> {
    private Monad<String, MaybeMonadImpl> lookup(string name, Dictionary<String, Monad<String, MaybeMonadImpl>> db) {
        Monad<String, MaybeMonadImpl> result;
        db.TryGetValue(name, out result);
        return result;
    }
        
    [Test]
    public void MailSystem() {
        //based very loosely on haskell.org's example
        // (I don't understand why their mplus is relevant)
        var fullnamedb = new Dictionary<String, Monad<String, MaybeMonadImpl>>();
        var nicknamedb = new Dictionary<String, Monad<String, MaybeMonadImpl>>();
        fullnamedb.Add("nicholas", Monad.Unit<String, MaybeMonadImpl>("n@m.com"));
        nicknamedb.Add("nick", Monad.Unit<String, MaybeMonadImpl>("nicholas"));
        var mnick = Monad.Unit<String, MaybeMonadImpl>("nick");
        Assert.AreEqual(
            "n@m.com",
            Monad.Star(
                Monad.Star(mnick, nick => lookup(nick, nicknamedb)),
                name => lookup(name, fullnamedb)).Just());
    }

And finally, I can restate andand in terms of monads:


private class D {}
private class C {
    public D d;
}
private class B {
    public C c;
}
private class A {
    public B b;
}
[Test]
public void andand() {
    A nil = null;
    A a = new A();
    A ab = new A() { b = new B() };
    Assert.IsNull(MaybeMonad<D>.Andand<A>(() => null));
    Assert.IsNull(MaybeMonad<D>.Andand(() => (A)null));
    Assert.AreEqual(a, MaybeMonad<D>.Andand(() => a));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b));
    Assert.AreEqual(ab.b, MaybeMonad<D>.Andand(() => ab.b));
    Assert.IsNull(MaybeMonad<D>.Andand(() => ab.b.c));
    Func<Object> x = null;
    Func<Func<Object>> y = null;
    y = () => null;
    Assert.IsNull(MaybeMonad<D>.Andand(() => y()()));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b.c));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b.c.d));
}

OK then, let's see how this is implemented:


public class MonadImpl<M> where M : MonadImpl<M>, new() {
    public virtual Monad<B, M> Star<A, B>(Monad<A, M> ma, Func<A, Monad<B, M>> f) {
        return f(ma.Just());
    }
}
public class Monad<T, M> where M : MonadImpl<M>, new() {
    public M impl = new M();
    public T Just() {
        return a();
    }
    internal protected Func<T> a;
    public Monad<B, M> Star<B>(Func<T, Monad<B, M>> f) {
        return impl.Star<T, B>(this, f);
    }
    public static Monad<A, M> Unit<A>(A a) {
        return new Monad<A, M>() { a = () => a };
    }        
}

A monad represents a computation of arbitrary type and some sort of side-effect whose control motivates the use of monads. Wrapping and unwrapping the computation associated with the monad is a straightforward example of parametric polymorphism. Slightly more interesting is recursive nature of the Monad type, whose method signatures involve the type on which they are defined. Simple parametric polymorphism permits us to define methods that behave uniformly on values of any type. If we want to make use of non-universal structure on those values we can restrict the values to a range of types that share the structure we need. Often, in a recursively-defined type, we want this range of types to itself involve a type parameter. For example, in this case we want Star to take a Monad and to return a Monad of a similar type. This requires f-bounded polymorphism, which is supported in .NET's generics; c#'s where clause not only binds type parameters, but can (re)use those parameters in the bounds.

Managing the side-effects is less straightforward. Here we want uniform packing/unpacking behavior across all computations, but side-effect management behavior that is peculiar to the kind of side-effect captured by the monad. We've had some support for behavioral refinement that follows subtyping relationships since the beginning of .NET, with virtual methods. But the Star function takes a monad (with behavior b and computation c) and a function from c to d and returns a monad with behavior b and computation d. It builds a value whose type is merely related and not identical to any of its type arguments. This is characteristic of Guarded Recursive Datatype Constructors. These g.r. datatypes, also known as Generalized Algebraic Data Types (GADTs), are not yet well-supported in .NET. Fortunately, the work-around shown above is sufficient for seeing the connection between monads and andand.

The Maybe Monad represents "just" a computation, or "nothing." The monad structure makes it easy and convenient to treat Maybes in a uniform way, regardless of whether a particular Maybe represents "nothing" or a non-nothing computation. If you're familiar with the Null Object pattern, you'll recognize the benefit of this uniformity and you'll see that Maybe monad is a more general alternative to Null Object in many contexts.

So finally we're ready to see andand, implemented in terms of the MaybeMonad:


public class MaybeMonadImpl : MaybeMonadImpl<MaybeMonadImpl> {}
public class MaybeMonad<T> : Monad<T, MaybeMonadImpl> {
    private static Expression andandifyme(MemberExpression me) {
        var objectParameter = Expression.Parameter(me.Expression.Type, "target");
        var parameters = new ParameterExpression [] {objectParameter};
        //TODO: simplify by using the parameter f rather than by duplicating
        // the subexpression: andandify(me.Expression) in slotValue and
        // in the Just of Star of Unit below (the subexpression could occur
        // solely in slotValue, and then its value could be used by
        // dereferencing f in the Just of Star of Unit.
        var slotValue =
            andandifyinr(
                Expression.Invoke(
                    Expression.Lambda(
                        Expression.MakeMemberAccess(
                            objectParameter,
                            me.Member),
                        parameters),
                    andandify(me.Expression)));
        var f = Expression.Parameter(me.Expression.Type, "f");
        return
            Expression.Call(
                typeof(Monad),
                "Just",
                new Type [] { me.Type, typeof(MaybeMonadImpl) },
                Expression.Call(
                    typeof(Monad),
                    "Star",
                    new Type [] { me.Expression.Type, me.Type, typeof(MaybeMonadImpl) },
                    Expression.Call(
                        typeof(Monad),
                        "Unit",
                        new Type [] { me.Expression.Type, typeof(MaybeMonadImpl) },
                        andandify(me.Expression)),
                    Expression.Lambda(
                        Expression.Call(
                            typeof(Monad),
                            "Unit",
                            new Type [] { me.Type, typeof(MaybeMonadImpl) },
                            slotValue),
                        f)));
    }
    private static Expression andandifyi(InvocationExpression i) {
        return
            andandifyinr(
                Expression.Invoke(
                    andandify(i.Expression),
                    i.Arguments));
    }
    private static Expression andandifyinr(InvocationExpression i) {
        var l = i.Expression;
        var f = Expression.Parameter(l.Type, "f");
        return
            Expression.Call(
                typeof(Monad),
                "Just",
                new Type [] { i.Type, typeof(MaybeMonadImpl) },
                Expression.Call(
                    typeof(Monad),
                    "Star",
                    new Type [] { l.Type, i.Type, typeof(MaybeMonadImpl) },
                    Expression.Call(
                        typeof(Monad),
                        "Unit",
                        new Type [] { l.Type, typeof(MaybeMonadImpl) },
                        l),
                    Expression.Lambda(
                        Expression.Call(
                            typeof(Monad),
                            "Unit",
                            new Type [] { i.Type, typeof(MaybeMonadImpl) },
                            i),
                        f)));
    }
    private static LambdaExpression andandifyl(LambdaExpression l) {
        return
            Expression.Lambda(
                andandify(l.Body),
                Enumerable.Select(
                    l.Parameters,
                    p => (ParameterExpression)andandify(p)).ToArray());
    }
    private static Expression andandify(Expression expr) {
        var me = expr as MemberExpression;
        if (me != null) {
            return andandifyme(me);
        }
        var i = expr as InvocationExpression;
        if (i != null) {
            return andandifyi(i);
        }
        var l = expr as LambdaExpression;
        if (l != null) {
            return andandifyl(l);
        }
        return expr;
    }
    public static U Andand<U>(Expression<Func<U>> expr) {
        var aexpr = (Expression<Func<U>>)andandify(expr);
        try {
            return (U)aexpr.Compile().DynamicInvoke();
        }
        catch (Exception e) {
            throw new Exception(
                          String.Format(
                               "trouble evaluating {0}", 
                               aexpr),
                          e);
        }
    }
}

By conflating null and Maybe's Nothing, we preserve the simple approach Identity monad can use for Star: just unwrap the computation from the input monad and wrap it in the output monad. This approach doesn't work in general, because there might be state associated with the monads that we'd need to migrate.

Now, comparing the direct implementation to the monadic implementation, you might be ready to decide that monads might be theoretically interesting but are impractical. I think that on one hand, the more stateful monads benefit more fully from the paradigm than the Maybe monad; on the other hand, C# exaggerates the ceremony of monad implementation relative to Haskell. Microsoft hasn't highlighted their use of monads in LINQ or EF or PLINQ, and they haven't exposed any analog to my Monad<T, M> type, so I couldn't share that implementation for andand. In summary, I don't think the monadic implementation of andand carries its weight, but if I saw an opportunity to benefit from other kinds of monads in my program, the benefits might easily outweigh the amortized costs of monads.

Andand.NET sans monads

2009-06-04T20:25:00.015-05:00

I motivated this material in my previous post.

One way to view andand is as a syntactic transformation of the code: the effect we want is to write


a.b.c.d

and have that automatically translated to


(a != null && b != null && c != null) ? a.b.c.d : null

C# doesn't support syntactic abstraction in the style of Lisp macros, but later in this post we'll see that recent versions of C# give us much more flexibility than we had in 2.0 and earlier.

Before we look at the techniques in detail, I want to acknowledge that syntactic regularity is a key motivation for Ruby Object#andand. Ruby Object#andand uses infix "andand" in imitation of the built-in guarded assignment operator &&=. We have no such operator in C#, and I am a prefix sympathizer anyway, so neither of my andand implementations share this emphasis with the Ruby inspiration.

So, my first implementation of andand for C# used LINQ expression tree transformation. The first step is to gain the ability to manipulate the program defined by the source code whose meaning I want to reinterpret (e.g., the compound member access expression a.b.c.d shown above):


public static T Andand<T>(Expression<Func<T>> f) {
    try {
        f = (Expression<Func<T>>)aar(f);
        return f.Compile()();
    }
    catch (Exception e) {
        throw new Exception(String.Format("trouble with {0}", f), e);
    }
}

One of the main ideas in LINQ is type-directed expression quoting. Here, I've written a function that takes an Expression tree as an argument. If I apply this function to a lambda expression, the compiler will translate the lambda to a value representing the abstract syntax tree of the lambda rather than generating an anonymous delegate. So, a typical call site for Andand looks like this:


private class D {}
private class C {
    public D d;
}
private class B {
    public C c;
}
private class A {
    public B b;
}

A ab = new A();
ab.b = new B();
Assert.AreEqual(ab.b, Andand(() => ab.b));
Assert.IsNull(Andand(() => ab.b.c.d));

Once I have my expression tree, I'm ready for a transformation. Clearly from my starting example, member access expressions constitute an important case. I'd like to be able to handle some other cases though, like method chaining. I'll give you a taste of tree inspection and construction here; for complete details see andand-sans-monads at googlecode.


private static Expression aar(Expression e) {
    var me = e as MemberExpression;
    if (me != null) {
        return
            guard(me.Expression, me);
    }
    var l = e as LambdaExpression;
    if (l != null) {
        return
            Expression.Lambda(
                guard(
                    l.Body,
                    l.Body),
                Enumerable.Select(
                    l.Parameters,
                    p => p).ToArray());
    }
    var ie = e as InvocationExpression;
    if (ie != null) {
        var args =               
            Enumerable.Select(
                ie.Arguments,
                (arg, i) => Expression.Parameter(arg.Type, String.Format("arg{0}", i))).ToArray();
       return
            Expression.Invoke(
                guard(
                    ie.Expression,
                    Expression.Lambda(
                        nullExpr(ie.Expression.Type),
                        args),
                    Expression.Lambda(
                        ie.Expression,
                        args)),
                Enumerable.Select(
                    ie.Arguments,
                    arg => aar(arg)));
    }
    return e;
}

It sure is a lot of work to construct expression trees "by hand" as opposed to using the type-directed quoting facility. I could be a lot more concise with Lisp quasiquote. Maybe later we'll experiment with using type-directed quotation of expression tree transformations, but for now I was more interested in exploring the connection between andand and monads.

But I have to work tomorrow morning and I'd like you to be able to read this now, so I'll save the monad and GADT discussion for my next post in this series.

motivation for Andand.NET

2009-05-31T20:32:00.008-05:00

Some of my followers on twitter encouraged me to post about my andand implementation, so here is the first in a series.

In brief: I wanted to replace


if (a != null && a.b != null && a.b.c != null) {
    return a.b.c.d;
}
else {
    return null;
}


return andand(a.b.c.d);

and I manged to learn a little bit about monads, generalized algebraic data types, and .NET on the way to achieving


return andand(() => a.b.c.d)

About a month ago I was working with an instance of a generic type:


var page = Potpourri.Page.getPage(s, count.Value);
ViewData["reverse-memento"] = page.reverseMemento.itemNumber;

This code obtains a range of rows from a database given a starting position and a window size. Simple integer offsets don't work for the general case of concurrent access by lay users to a mutable table. My approach requires getPage to know an equivalence relation on elements, but it doesn't require that getPage know about itemNumber specifically or even that there be just one field/property that's sufficient to determine equality.

So, AFAICT, there's no good way to avoid violating Demeter here.

Certainly there remains a practical problem that the next and previous page references could be undefined for any given page. In this case, reverseMemento could be null.

The awkward conditional needed to avoid NullReferenceException here brought to mind Object#andand. Informally, andand provides short-circuit behavior for chained accesses. The Ruby andand relies on Ruby metaprogramming features. The closest thing we have to a macro facility in c# is Linq expression trees, and I hadn't had an excuse to use System.Linq.Expressions yet, so this seemed like a good opportunity.

My first implementation directly transformed expression trees, replacing member accesses by conditional member accesses that return null whenever a is null in a.b.

My second implementation was inspired by a question about the relation between andand and the Maybe monad. I thought it would be a good idea to (re)read some papers about monads and test my understanding by implementing a few, including Maybe Monad. I also thought it would be instructive to implement Maybe monad in terms of andand, and andand in terms of Maybe monad.

I'll discuss the code in detail in my next post. For now, you can download a snapshot. I guess I'll migrate my existing hg repo to googlecode in time for the next post to make browsing easier.

.emacs

2009-05-18T10:06:00.004-05:00

; Some people I know have asked about my .emacs. Voila:

(custom-set-faces
;; custom-set-faces was added by Custom.
;; If you edit it by hand, you could mess it up, so be careful.
;; Your init file should contain only one such instance.
;; If there is more than one, they won't work right.
)

(setq default-buffer-file-coding-system 'unix)

(setenv "PATH" (concat "c:/cygwin-1.7/bin;" (getenv "PATH")))
(setq exec-path (cons "c:/cygwin-1.7/bin/" exec-path))

(require 'cygwin-mount)
(cygwin-mount-activate)

(add-to-list 'load-path "/cygdrive/c/program-files/emacs-22.3/site-lisp")

(add-to-list 'auto-mode-alist '("\\.cs$" . java-mode))
(add-hook 'java-mode-hook
(lambda ()
(setq indent-tabs-mode nil)))

(autoload 'js2-mode "js2" nil t)
(add-to-list 'auto-mode-alist '("\\.js$" . js2-mode))
(add-hook 'js2-mode-hook
(lambda ()
(setq indent-tabs-mode nil)))

(autoload 'python-mode "python-mode" "Python Mode." t)
(add-to-list 'auto-mode-alist '("\\.py\\'" . python-mode))
(add-to-list 'interpreter-mode-alist '("python" . python-mode))
(add-hook 'python-mode-hook
(lambda ()
(set (make-variable-buffer-local 'beginning-of-defun-function)
'py-beginning-of-def-or-class)
(setq outline-regexp "def\\|class ")
(setq indent-tabs-mode nil)))

(load (concat "/cygdrive/c/program-files/emacs-22.3/site-lisp/" "nxml-mode-20041004/rng-auto.el"))
(add-to-list 'auto-mode-alist '("\\.\$xml\\|xsl\\|rng\\|xhtml\$\\'" . nxml-mode))
(add-hook 'nxml-mode-hook
(lambda ()
(setq indent-tabs-mode nil)))
(setq magic-mode-alist
(cons '("<\\?xml" . nxml-mode)
magic-mode-alist))

(setq binary-process-input t)
(setq w32-quote-process-args ?\")
(setq shell-file-name "bash") ;; or sh if you rename your bash executable to sh.
(setenv "SHELL" shell-file-name)
;; For subprocesses invoked via the shell
;; (e.g., "shell -c command")
(setq explicit-shell-file-name shell-file-name)
(setq explicit-sh-args '("-login" "-i"))

(put 'erase-buffer 'disabled nil)

API refs no longer fashionable

2009-04-23T17:05:00.004-05:00

Recently it seems that API references have gone out of fashion. I'm guessing VS.NET IntelliSense might explain the lack of interest? Well, IntelliSense is no good for lengthy explanations. And so far nobody has cared enough about IntelliSense to implement it for C# and Emacs.

So I'm going to keep on publishing API ref pages for the free software I write.

BTW, I eventually found an NHibernate API ref.

Oops.NET

2009-04-05T22:30:00.005-05:00

I think the world needs another error-handling module for .NET applications.

My experience working in the IT departments of big companies suggests that most .NET applications do not behave well under exceptional circumstances. Sometimes programmers ignore exceptions and allow their programs to corrupt data. More often, our apps lose valuable diagnostic information during crashes. Occasionally, while attempting to preserve diagnostic details, our programs cause cascading failures that overshadow the original!

So, contrary to my first impression, even very simple error-handling code in thoroughly mundane programs is not too trivial share.

Before writing yet-another error handling module, I searched for something to reuse.

Microsoft's Enterprise Library has an exception handling module. In the old days, one reason to avoid it was because of its restrictive license; these days it is offered under the permissive MS-PL. But, it's still not right for most of the (small) apps I encounter, because its purpose is to provide high-level abstractions for conditions throughout an application.

ELMAH is aimed at ASP.NET specifically, but it wants to do data access and logging on its own. I do recognize the irony in launching competition for ELMAH due to ELMAH's tendency to reinvent the wheel, but I strongly value small sharp tools.

So I'm making something new.

It's conceptually based on the "oops page" I wrote for Tyco Healthcare iDeal many years ago. iDeal was an ASP.NET app that helped salespersons develop contracts; the Oops page gave our users an easy way to file bugs so that we wouldn't have to decipher vague phone messages and partial screenshots of ASP.NET default backtraces any more.

At Anheuser-Busch, our Enterprise Architecture group used to hand out sample code to illustrate our policies about how .NET apps (ASP.NET apps in particular) should crash. The sample could only be obtained by asking for it, which effectively encouraged teams to guess about its contents. The sample tried to show a few variations on its theme, but its presentation confused many teams, who either copied redundant code or omitted crucial details. We needed production-quality reusable code rather than sketches that wound up being reused by copy-and-paste. Because iDeal Oops was proprietary, and because it didn't address console apps, WinForms, Web Services, etc., I had to rewrite it for A-B.

Now I find myself back at the company formerly known as Tyco Healthcare, and I see apps that would benefit from Oops. I could extract Oops from iDeal, package it as nicely as the code I wrote for A-B... But I'm afraid I might wind up working on .NET at some other company, and I never want to have to rewrite this code again. And, it's clearly worth sharing.

So, I'm finally publishing Oops.NET. Coming soon: log4net integration demo, bugzilla integration demo, and support for WinForms, System.Web.Services, System.ServiceModel, and WPF.

underrated: Class Library Projects

2009-02-13T12:09:00.001-06:00

This is the preface for vsweb.

My first job after college was programming and sysadmin at BigCo, mostly working on the ASP.NET framework. Early on, I was basically working alone as an programmer although I had a mentor/partner for the sysadmin role. Later, I joined a team that was just beginning to function in fact, although in the tradition of BigCo it had been called a "team" for years before that. There was little development infrastructure in place, and what we had was disfunctional -- think Visual SourceSafe, with MS Office documents and SharePoint lists for defect tracking and planning. I suggested we switch to SVN, my teammate Mike pushed for draco.net (CI), I setup a Bugzilla instance, we held an NUnit tutorial, and a couple of years later we had some some experience with organizing a team software development effort and supporting it with various tools. Things eventually stabilized and the main challenge at work shifted from learning to explaining.

My second job was coaching and mentoring for another BigCo. My new employer had not a dozen but hundreds of programmers, hence the ability specialize full-time on reflective work. In this role, I was exposed to a much larger and broader set of projects than I would have been as an ordinary programmer. I had the opportunity to revisit the lessons I'd learned before, see how they fit with new evidence, and articulate them for the benefit of others.

So, that's how I came to write vsweb: why web application developers should use Class Library Projects rather than project templates whose names include the word "web." Enjoy.