Maniagnosis

The Anti-Meeting Theory of Time

2012-02-13T19:42:00.000-06:00

Meetings occupy time.
Meeting cancellations free up time.
Scheduling a meeting, then canceling it results in the original amount of free time.
What happens when you schedule a meeting, then cancel it more than once?
Time is created!

Link o' the day: Java and memory

2012-02-09T21:30:00.000-06:00

From proggit, this is a presentation from OOPSLA 2008:

Building Memory-efficient Java Applications

Quote o' the week: Don Stewart on the big picture

2012-02-03T23:17:00.000-06:00

This is from Don Stewart's keynote at PADL'12 (formally, the Fourteenth International Symposium on Practical Aspects of Declarative Languages) and is one of the few fundamental truths of computer programming. (Number three might be controversial.)

Really big picture: why software?

Increase economic productivity by automating everything

Make the complexity of the world tractable by making it hackable

Impose structure through typed data

Transform work/jobs/tasks into resuable/composable functions

Find new efficiencies. Repeat

(Demonstrate you can do this and you'll never be out of work)

State space search: A*

2012-02-01T19:59:00.000-06:00

Last time, I quoted Wikipedia, "For the 15-puzzle, lengths of optimal solutions range from 0 to 80 moves". Unfortunately, the two solutions I found require 255 and 205 moves. That seems less than satisfactory.

So, here's the state of 15-puzzle solutions as it stands: we have depth-first search, which is relatively fast but which is not guaranteed to find a solution. On the other hand, we have breadth-first search, which is guaranteed to find an optimal solution, in the sense of the smallest number of moves for the 15-puzzle, but which is slow and expensive. And finally, we have a couple of heuristics which, used alone, relatively quickly find a solution, having some of the benefits of depth-first search, but which find markedly sub-optimal solutions.

What this situation calls for is a slightly modified algorithm. The algorithm I have in mind is called A*. A* is actually a basic modification of the state evaluation function used by an informed search. Instead of the Manhattan distance or the number of tiles out of position (which I have learned should be called the Hamming distance) as the evaluation function, A* uses the sum of a forward-looking heuristic function and the cost of the path from the initial state to the state being evaluated. For the 15-puzzle, this would be, say, the Manhattan distance of the current state from the goal state plus the number of moves from the initial state to the current state.

A* works by being a best-first search; by expanding the state that looks like it will produce the best solution, rather than a state that is simply structurally next (as in the case of uninformed searches) or a state that looks like it is nearest to a solution. As a result, A* is likely to use fewer resources than breadth-first search while finding a better solution than an informed depth-first search.

In fact, A* has a very nice property: if the forward-looking heuristic function is admissible, then the search algorithm is guaranteed to find the optimal solution. Admissible simply means that the heuristic function does not overestimate the cost of the path from the current state to a goal. Possibly the simplest way of finding an admissible heuristic function is to relax some of the constraints on the problem; for example, the Hamming distance heuristic relaxes the 15-puzzle problem by allowing tiles to be directly moved to their goal position and counting the number of tiles thus moved while the Manhattan distance heuristic relaxes the constraints by allowing tiles to move directly to their goal states (rather than requiring sliding them into the empty space) and counting the number of moves needed. Both the Hamming distance and the Manhattan distance are admissible.

Converting the fifteenpuzzle code to use A* is incredibly easy:

  public static class AStarDistance implements Comparator<FState>
  {
    @Override
    public int compare(FState o1, FState o2)
    {
      return (o1.totalDistance() + o1.pathLength) - (o2.totalDistance() + o2.pathLength);
    }
  }

I created a new implementation of Comparator<FState> which compares the two states by computing the totalDistance value (the Manhattan distance) of each object and the length of the path from the initial state to the states and then comparing the resulting sums. When creating an instance of Search<FState>, use a PriorityQueue based on this Comparator.

How well does it work? I've got no clue. Sorry. The A* search goes through hundreds of thousands of states before it exhausts the default JVM heap size, and it takes long enough to do so that I don't really feel interested in trying it with more memory. The implementation could be optimized, but this is an exponential algorithm and optimization would be unlikely to make too much of a dent. (On the other hand, there is the possibility, however remote, that I've really hoarked something up. If so, I'd appreciate knowing about it.)

But I have the next best thing: by modifying the A* evaluation function, I can bias the evaluation towards the heuristic function, producing a solution in reasonable time and space. Unfortunately by doing so, I am likely to effectively make the heuristic function inadmissible, meaning that A* is no longer guaranteed to find an optimal solution. This is the implementation:

  public static class BiasedAStarDistance implements Comparator<FState>
  {
    private final int bias;
    
    public BiasedAStarDistance(int bias)
    {
      this.bias = bias;
    }

    @Override
    public int compare(FState o1, FState o2)
    {
      return (bias * o1.totalDistance() + o1.pathLength) - (bias * o2.totalDistance() + o2.pathLength);
    }
  }

For me, it works significantly better than the un-biased A* search.

Bias	States examined	Path length
5	3865	75
4	4266	83
3	15,442	73
2	19,879	57

You can get the code on github. The previous posts are State space search: the basics and State space search: heuristics.

Nth Fibonacci number in Emacs Lisp

2012-01-29T13:36:00.000-06:00

Following a post by Phil, a video game developer in Orange County, this is the Fibonacci function in Emacs Lisp:

;;; Define some constants
(defconst s5 (sqrt 5) "square root of 5")
(defconst is5 (/ 1 s5) "inverse of the square root of 5")
(defconst ps52 (/ (+ 1 s5) 2) "1 plus sqrt(5) over 2")
(defconst ns52 (/ (- 1 s5) 2) "1 minus sqrt(5) over 2")

;;; The fibonacci function
(defun fibonacci (n)
  "Nth fibonacci number"
  (truncate (* is5
               (- (expt ps52 n)
                  (expt ns52 n)))))

I'll leave the proof of it to Phil (and it is pretty damn nice), but here are some quick examples:

(fibonacci 0)
0
(fibonacci 1)
1
(fibonacci 2)
1
(fibonacci 3)
2
(fibonacci 4)
3
(fibonacci 5)
5
(fibonacci 6)
8
(fibonacci 8)
21
(fibonacci 10)
55

And yes, I know it is using limited precision floating point numbers and will break six ways from Sunday.

Still, this is now my favorite answer to an interview question.

Quote o' the week: a journal that meets in a hotel

2012-01-25T22:56:00.000-06:00

I reading my pile of magazines and ran across Moshe Vardi's "Are you talking to Me?" in the CACM. (It's a brilliant editorial; he mentions Doug Zongker's "Chicken Chicken Chicken" talk (and paper!), the number of people attending a conference who think presentations are an opportunity to check their email (yeah, I know most of the good stuff is in the "hall track"), and the following:

I am reminded of Lance Fortnow's pithy description of a computer-science conference as "a journal that meets at a hotel."

Unfortunately, Fortnow, who notably doesn't care for the state of computer science conferences, disclaims responsibility for the quote.

How about this idea: We don't bother meeting and just collect the accepted papers into a single volume. We can give this idea an innovative name like a "journal".

In this month's CACM article, Moshe Vardi complains about the quality of conference talks. (I like the "journal that meets in a hotel" quote but it didn't originate with me). You see this at STOC and FOCS too, people giving a talk only to other specialists in their field instead of aiming for a general audience.

Personally, I believe that the word "weasel" is inherently funny and deserves to be used much more often than it is.

State space search: heuristics

2012-01-22T14:25:00.000-06:00

Last time, I wrote, without any explanation

Using a FIFO queue searches the state space breadth-first, visiting all of the states at a given distance from the initial state before any states at a greater distance. Using a LIFO queue searches the state space depth-first, visiting all of the states following a given state before visiting any other states.

The way that works is important to the power of search. Consider using a first-in, first-out queue and expanding an initial state $n$. Expanding $n$ enqueues the states $(o_1, o_2, o_3)$. The next step is to remove the first state from the queue, expand it, and enqueue the results, leaving the queue as $(o_2, o_3, p_1, p_2)$ (assuming expanding $o_1$ produced $p_1$ and $p_2$). As a result, following this queuing strategy, all of the states at depth $o$ from the initial state are expanded before any of the states at depth $p$. Hence, "breadth-first".

On the other hand, if the algorithm uses a last-in, first-out structure, expanding the same initial state $n$ still produces a queue of $(o_1, o_2, o_3)$. However, the next step is to remove the last state from the queue, expand it, and enqueue the results, producing $(o_1, o_2, p_1, p_2)$, assuming expanding $o_3$ produced $p_1$ and $p_2$ this time. This time, the next step will be to expand $p_2$, with the result that all of the states below $o_3$ will be examined before any of the other states $o_1$ or $o_2$. Thus, "depth-first".

So far, I have been discussing uninformed search; these approaches order their exploration of the problem's state space based on the pattern of state-space expansion. There is a better way: informed search applies information about the problem to focus the exploration of the state space on important regions. Here's an example:

Sliding number puzzles: fifteenpuzzle

Returning to Gerhard Wickler, he describes the basics of the 8-puzzle (a smaller version of the 15-puzzle) as,

The 8-puzzle is a smaller version of the slightly better known 15-puzzle. The puzzle consists of an area divided into a grid, 3 by 3 for the 8-puzzle, 4 by 4 for the 15-puzzle. On each grid square is a tile, expect for one square which remains empty. Thus, there are eight tiles in the 8-puzzle and 15 tiles in the 15-puzzle. A tile that is next to the empty grid square can be moved into the empty space, leaving its previous position empty in turn. Tiles are numbered, 1 thru 8 for the 8-puzzle, so that each tile can be uniquely identified.

The aim of the puzzle is to achieve a given configuration of tiles from a given (different) configuration by sliding the individual tiles around the grid as described above.

This puzzle is not hard to put into a form suitable for state space search, which should provide a solution as long as the algorithm does not expand a state more than once. If the shortest solution is needed, the breadth-first approach is a straightforward choice.

The state space for sliding puzzles is significantly larger than that of the missionaries and cannibals puzzle; there are $n!$ ways to permute $n$ tiles, although only half of those are reachable from a given goal state, although the proof is enlightening itself. (The 8-puzzle therefore illustrates one of the hazards of state space manipulation: some states may be unsolvable.) So, the 8-puzzle version has 181,440 possible states, including the empty tile; the 15-puzzle has 10,461,394,944,000.

As a result, a complete search of the state space is likely to be infeasible and any uninformed search will also likely take more resources than strictly desirable. But there are ways to exploit knowledge about the problem to shorten the search.

Suppose, for example, you can find out, given a state, approximately how many moves are needed to get from the state to a goal? Then, you could select the next state to explore based on your estimate of how close it is to the solution. Fortunately, both of these are possible: there are a number of heuristics that can provide the necessary estimate, and our friend, the priority queue, can handle the selection of the next state to expand.

One possible heuristic is the number of out of place tiles, because that is obviously going to be related to the number of moves necessary to get the tiles into their places. Importantly, for reasons that I don't intend to go into here, it always underestimates the number of moves. If the search explores the state space, focusing on the states with fewer and fewer tiles out of place, the search is likely to find the goal while significantly reducing the resources required.

To implement the states for the 15-puzzle, I chose to represent the positions of the tiles as locations in an ArrayList of integers, with the tile values being 1 through 15 with 0 as the empty tile. (For expediency, I also record the location of the empty tile in the array.) As a result, determining whether a state is the goal is simple. For locations 0 to 14, whenever the value of the location is one greater than the location number, the puzzle is solved.

  @Override
  public boolean isGoal()
  {
    // The final square should be 0 but I don't care.
    for (int i = 0; i < BOARD - 1; ++i)
    {
      if (board.get(i) != i + 1) { return false; }
    }
    return true;
  }

Expanding a state a bit more complicated since it requires attempting to move the empty space left, right, up, and down. (Or, alternately, move the tile to the left into the empty space. Depends on how you look at these things.) One of the directional methods is shown below; the other three are similar.

  @Override
  public List<FState> expand()
  {
    List<FState> result = new ArrayList<FState>();
    for (FState newState : Arrays.asList(this.left(), this.right(), this.up(), this.down()))
    {
      if (newState != null) { result.add(newState); }
    }
    return result;
  }

[...]

  private FState left()
  {
    if (empty % ROW != 0)
    {
      // Empty location is not at left edge
      return new FState(this, empty - 1);
    }
    else
    {
      return null;
    }
  }

(I'll leave it to you to figure out how modular arithmatic lets me fiddle with a rectangular grid in a one-dimensional array.)

Implementing the out-of-position heuristic is similar to checking isGoal, with the complication of counting the number of tiles out of place.

  public int outOfPosition()
  {
    int out = 0;
    for (int i = 0; i < BOARD - 1; ++i)
    {
      if (board.get(i) != i + 1)
      {
        ++out;
      }
    }
    return out;
  }

And finally, to allow the heuristic function to interface with a priority queue, I need a Comparator subclass.

  public static class OutOfPosition implements Comparator<FState>
  {
    @Override
    public int compare(FState o1, FState o2)
    {
      return o1.outOfPosition() - o2.outOfPosition();
    }
  }

The following code runs the search on a "harder" problem (harder than the one in the illustration above, anyway).

    System.out.println("Heuristic search: out of position");
    Queue priority = new PriorityQueue(100, new FState.OutOfPosition());
    Search search = new Search(queue, new HashSet(), FState.harder());
    FState end = search.findGoal();

This search exampines 4387 states to find a goal with a path length of 255.

There are certainly many possible heuristics. An alternative heuristic for the 15-puzzle is the total distance for each tile in a state between its position and its goal position. Specifically, the Manhattan distance, which is sum of the number of rows and columns each tile is out of position. The total of the Manhattan distance is computed by the totalDistance method. The advantage of this heuristic is that it more closely estimates the number of moves necessary to solve a puzzle from a given state.

  public int totalDistance()
  {
    int out = 0;
    for (int i = 0; i < BOARD; ++i)
    {
      if (i == empty) continue;
      int position = board.get(i) - 1;
      out += Math.abs((i % ROW) - (position % ROW));
      out += Math.abs((i / ROW) - (position / ROW));
    }
    return out;
  }

In this case, rather than implementing Comparator, I made the FState class Comparable

  @Override
  public int compareTo(FState o)
  {
    return this.totalDistance() - o.totalDistance();
  }

The driver program creates a PriorityQueue with no arguments to use the Comparable.

    System.out.println("Heuristic search: manhattan distance");
    Queue priority = new PriorityQueue();
    Search search = new Search(queue, new HashSet(), FState.harder());
    FState end = search.findGoal();

This version only examines 1469 states to find a solution of 205 moves.

For comparison, according to Wikipedia, "For the 15-puzzle, lengths of optimal solutions range from 0 to 80 moves". The difference is that the raw heuristic search that I am writing about here behaves similarly to depth-first search in that it makes no claim to find an optimal path. On the other hand, the raw heuristic search does find a solution quickly, much faster than a breadth-first search.

You can get the code on github . Other posts on the topic are State space search: the basics, and State space search: A*.

State space search: the basics

2012-01-15T22:37:00.000-06:00

A while back, briefly discussing Steve McConnell's Code Complete, I wrote, "On the other hand, McConnell previously presented as a good use of recursion a maze-solving function; maze solving is an application of state-space search, which has a simple, clear, and wildly flexible iterative implementation based on a priority queue." Between that, and the Stanford AI course (which only briefly mentioned most of what I spent a semester learning back in the late '80's), I have been pondering state space search lately. It really is an elegant algorithm. So, I thought I'd spend some spare time writing an elaborate and likely unnecessary post or three about it.

I'll begin with a state. A state is a particular configuration of the system in question. For example, a board position in chess is a state. When you place the pieces on the board, you create an initial state; after some number of moves, the board is in some other state. When the game is over, the board is in a terminal state; if you won, it's in a goal state, but the difference is the topic of some other post. For the moment, I will only be talking about systems where the only terminal states are goals.

A state space is the set of all possible states for a system. For chess, the state space is all possible board positions, and there are a lot of them. Chess has a fairly large state space. The states in a state space are related by the valid actions of the system; given a state those actions produce a collection of the next states reachable by one operation of the system. For chess, the actions are the valid moves of individual chess pieces and, because the initial state is defined by the rules of chess, the state space includes all board positions reachable from that initial state by legal chess moves.

State space search is the technique of searching for a goal state, beginning with an initial state and using the operations available in each state to generate new states. Or, alternatively, beginning with a goal state and searching for a suitable initial state. Or possibly even starting with an initial state and a goal state and searching for a way to connect the two in the state space. Each of those approaches is suitable for some problems, depending on the nature of the problem. The key point is to explore the state space of the problem, searching for a solution.

State space search is one of the most powerful techniques in computer science. If a problem can be framed in a way suitable to state space search (and most can), then the algorithm is guaranteed to find a solution. Theoretically, anyway. If you have a problem and do not have any more direct algorithm, it is the go-to way to solve it. Or, at least it was; there are other techniques that have become popular, usually for very good reasons.

On the other hand, state space search has some serious weaknesses. For one thing, not all problems can be usefully framed in terms of a state space. It requires that the problem be both discrete and deterministic; discrete in such a way that all states are distinct from one another and deterministic so that an action produces exactly one subsequent state from an input state. But that is not the worst part. State space search is the poster child for exponential algorithms. I said it was guaranteed to find a solution, but I carefully didn't say you would be alive to see it. Or, anything would be alive to see it. But there are plenty of problems to which state space search is applicable.

The algorithm

So, with all that buildup, the algorithm is a typical let-down:

def search(queue):
    while not empty?(queue):
        current_state := remove_element(queue)
        if is_goal?(current_state):
            return current_state
        for next_state in expand(current_state):
            if not seen?(next_state):
                mark_seen(next_state)
                add(queue, next_state)
    return nil

The intelligence of the algorithm is actually in the:

Queue that is used to store states before they are examined and expanded and which determines the nature of the search,
The rules that determine whether a state is a goal and how the state is expanded into subsequent states, and
The set used to determine whether a state has been seen before; this and the queue will determine how much memory the algorithm uses.

How does this look in Java?

  public T findGoal()
  {
    while (!queue.isEmpty())
    {
      statesExamined++;

      T current = queue.remove();
      if (current.isGoal())
      {
        return current;
      }
      for (T newState : current.expand())
      {
        if (!seen.contains(newState))
        {
          seen.add(newState);
          queue.add(newState);
        }
      }
    }
    return null;
  }

statesExamined is an accounting addition, just used for entertainment purposes. The rest of the class similarly simple, initializing seen and queue based on constructor arguments. Like I said, nothing up my sleeve....

public class Search<T extends State<T>>
{
  private int statesExamined;
  private final Queue<T> queue;
  private final Set<T> seen;

  public Search(Queue<T> queue, Set<T> seen, T initialState)
  {
    this.queue = queue;
    queue.add(initialState);
    this.seen = seen;
    this.statesExamined = 0;
  }

  [...findGoal...]

  public int statesExamined()
  {
    return statesExamined;
  }
}

The Set seen is used to prevent states from being expanded repeatedly. It records when a state is first seen and subsequently prevents it from being re-added to the queue. Without this, the algorithm could enter an infinite loop if the state space is not acyclic.

The State interface is not much more interesting. The only required methods are to expand the state, producing a list of subsequent states produced by valid actions, and a predicate that is true if the state is a goal.

public interface State
{
  public List expand();

  public boolean isGoal();
}

If the state space search code is so simple, how is the algorithm capable of such power? How about an example?

Missionaries and cannibals: rivercrossing

The problem is, according to Gerhard Wickler,

On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.

How can the boat be used to safely carry all the missionaries and cannibals across the river?

(I have seen versions where the threat is the missionaries converting the cannibals, rather than the cannibals cannibalizing (ahem) the missionaries. I am a traditionalist, however.)

Gerhard Wickler also has an excellent illustration of the complete state space for this problem. The initial state is on the left; the goal state is on the right. With 16 states, the state space is tiny in comparison with the space of other problems, but it gets my point across.

Each state is a configuration of the missionaries and cannibals on each side of the river as well as which shore the boat is on. The process of crossing the river is abstracted away; each state transition involves the boat, with at least one passenger, crossing the river.

Specifically, a state in the puzzle is made up of the participants on this side of the river, the participants on that side of the river, and the location of the boat, this side or that side.

  private static enum BoatSide { THIS, THAT };

On either side of the river are some number of missionaries and cannibals. I abstracted out the state of each side of the river as a class. There are a couple of special features of RiverSide, though.

First, the class includes methods missionaries, cannibals, and both which returns a new RiverSide instance with the number of missionaries or cannibals modified. These are used when generating new states while expanding a given state.
Second, the class implements equals and hashCode, making instances eligible to be stored in a HashMap.

  private static class RiverSide
  {
    public final int missionaries;
    public final int cannibals;
    
    public RiverSide(int missionaries, int cannibals)
    {
      this.missionaries = missionaries;
      this.cannibals = cannibals;
    }
    
    public RiverSide missionaries(int n)
    {
      return new RiverSide(missionaries + n, cannibals);
    }

    public RiverSide cannibals(int n)
    {
      return new RiverSide(missionaries, cannibals + n);
    }

    public RiverSide both(int n)
    {
      return new RiverSide(missionaries + n, cannibals + n);
    }
    
    @Override
    public boolean equals(Object o)
    {
      if (! (o instanceof RiverSide)) return false;
      final RiverSide other = (RiverSide) o;
      return this.missionaries == other.missionaries
          && this.cannibals == other.cannibals;
    }
    
    @Override
    public int hashCode()
    {
      return missionaries ^ cannibals;
    }
    
    @Override
    public String toString()
    {
      return String.format("[%d missionaries, %d cannibals]", missionaries, cannibals);
    }
  }

There are two constructors for the state class: the first, public, one creates the initial state for the problem, with three missionaries, three cannibals, and the boat on this side of the river. The second, private, one creates a new MCState based on a previous one and updated inhabitants of this and that side. The previous state is recorded so that the program can reconstruct the sequences of moves in a solution.

The methods required for State are next. isGoal is implemented by checking how many missionaries and cannibals are on that side of the river. expand is more complex, but breaks down into a number of branches; if the boat is on this side of the river, then expand generates all possible ways for it to get to the other side of the river, carrying one or two missionaries or cannibals; if the boat is on the other side, it does the reverse. Specifically, it collects a list of subsequent states; if at least one missionary is on this side, then a possible next state has the boat and one more missionary on that side. Likewise, if there are two missionaries on this side with the boat, another next state would be two less missionaries on this side and two more and the boat on that. The same logic applies to the cannibals and to a missionary and a cannibal moving to the other side. All of these branches go through queueNewState, which first checks whether the new state is invalid if it presents the opportunity for some cannibals to devour some missionaries. As a result of the branches, each state has five possible next states, although some (or most) of those states are invalid.

MCState also implements hashCode and equals, making instances eligible for HashSet storage.

public class MCState implements State<MCState>
{
  [...]
  
  public final BoatSide boatSide;
  public final RiverSide thisSide;
  public final RiverSide thatSide;
  public final MCState previous;
  
  public MCState()
  {
    boatSide = BoatSide.THIS;
    thisSide = new RiverSide(3, 3);
    thatSide = new RiverSide(0, 0);
    previous = null;
  }
  
  private MCState(MCState previous, RiverSide thisSide, RiverSide thatSide)
  {
    this.boatSide = previous.boatSide == BoatSide.THIS ? BoatSide.THAT : BoatSide.THIS;
    this.thisSide = thisSide;
    this.thatSide = thatSide;
    this.previous = previous;
  }
  
  @Override
  public boolean isGoal()
  {
    return thatSide.missionaries == 3 && thatSide.cannibals == 3;
  }

  @Override
  public List<MCState> expand()
  {
    List<MCState> newStates = new ArrayList<MCState>();
    if (boatSide == BoatSide.THIS)
    {
      if (thisSide.missionaries > 0)
      {
        final MCState newState =
            new MCState(this, thisSide.missionaries(-1), thatSide.missionaries(1));
        queueNewState(newStates, newState);
      }
      if (thisSide.missionaries > 1)
      {
        final MCState newState =
            new MCState(this, thisSide.missionaries(-2), thatSide.missionaries(2));
        queueNewState(newStates, newState);
      }
      if (thisSide.cannibals > 0)
      {
        final MCState newState =
            new MCState(this, thisSide.cannibals(-1), thatSide.cannibals(1));
        queueNewState(newStates, newState);
      }
      if (thisSide.cannibals > 1)
      {
        final MCState newState =
            new MCState(this, thisSide.cannibals(-2), thatSide.cannibals(2));
        queueNewState(newStates, newState);
      }
      if (thisSide.missionaries > 0 && thisSide.cannibals > 0)
      {
        final MCState newState =
            new MCState(this, thisSide.both(-1), thatSide.both(1));
        queueNewState(newStates, newState);
      }
    }
    else
    {
      if (thatSide.missionaries > 0)
      {
        final MCState newState =
            new MCState(this,thisSide.missionaries(1), thatSide.missionaries(-1));
        queueNewState(newStates, newState);
      }
      if (thatSide.missionaries > 1)
      {
        final MCState newState =
            new MCState(this,thisSide.missionaries(2), thatSide.missionaries(-2));
        queueNewState(newStates, newState);
      }
      if (thatSide.cannibals > 0)
      {
        final MCState newState =
            new MCState(this,thisSide.cannibals(1), thatSide.cannibals(-1));
        queueNewState(newStates, newState);
      }
      if (thatSide.cannibals > 1)
      {
        final MCState newState =
            new MCState(this,thisSide.cannibals(2), thatSide.cannibals(-2));
        queueNewState(newStates, newState);
      }
      if (thatSide.missionaries > 0 && thatSide.cannibals > 0)
      {
        final MCState newState =
            new MCState(this,thisSide.both(1), thatSide.both(-1));
        queueNewState(newStates, newState);
      }
    }
    return newStates;
  }
  
  private void queueNewState(final List newStates, final MCState newState)
  {
    if (newState.isValid())
    {
      newStates.add(newState);
    }
  }
  
  private boolean isValid()
  {
    return (thisSide.missionaries == 0 || thisSide.missionaries >= thisSide.cannibals)
        && (thatSide.missionaries == 0 || thatSide.missionaries >= thatSide.cannibals);
  }

  @Override
  public String toString()
  {
    final String format = (boatSide == BoatSide.THIS) ? "%s * -> %s" : "%s -> * %s";
    return String.format(format, thisSide, thatSide);
  }
  
  @Override
  public boolean equals(final Object o)
  {
    if (! (o instanceof MCState)) return false;
    final MCState other = (MCState) o;
    return this.thisSide.equals(other.thisSide)
        && this.thatSide.equals(other.thatSide)
        && this.boatSide == other.boatSide;
  }
  
  @Override
  public int hashCode()
  {
    return thisSide.hashCode() ^ thatSide.hashCode() ^ boatSide.hashCode();
  }
}

That is a fair amount of code, and nicely tedious. The key points, though, are the implementation of the State interface; the State knows whether or not it is a goal, and it knows how to generate the next states, following immediate, single step actions.

After that big wall o' code, you are probably waiting for a punch line. Unfortunately, there isn't one. Just a driver class invoking the search twice with a couple of different queue parameters. The first option uses ArrayDeque, which implements a First-In, First-Out queue.

    Queue fifo = new ArrayDeque();
    Search search = new Search(fifo, new HashSet(), new MCState());
    MCState end = search.findGoal();

The second option uses an anonymous subclass of ArrayDequeue where remove calls removeLast rather than removeFirst. As a result, it implements a Last-In, First-Out queue, or a stack.

    Queue lifo = new ArrayDeque() {

      @Override
      public MCState remove()
      {
        return super.removeLast();
      }
      
    };
    Search search = new Search(lifo, new HashSet(), new MCState());
    MCState end = search.findGoal();

These two options are my first demonstration of the flexibility of the state space search algorithm. Using a FIFO queue searches the state space breadth-first, visiting all of the states at a given distance from the initial state before any states at a greater distance. Using a LIFO queue searches the state space depth-first, visiting all of the states following a given state before visiting any other states. The difference in this case is modest; a FIFO queue visits 16 states while a LIFO queue visits 13 to find a solution. But that is just the tip of the iceberg.

Update: completely forgot about this. If you want to try it yourself, there is a related problem involving a farmer crossing a river. The farmer is carrying a bushel of corn, a duck, and a fox. (Yeah, I don't really get it either.) If the duck is left unattended with the corn, the corn gets eaten. If the fox is left unattended with the duck, the duck gets eaten. The boat will only carry the farmer and one of the other items. How can the farmer get to the other side of the river with the corn, duck, and fox intact? You can get the state space search code, such as it is, and you will need to write a State for the problem similar to MCState and a driver program.

For the continuing story of state space search, check out the next post, State space search: heuristics and State space search: A*.

You can get the code on github. I owe a considerable debt to Gerhard Wickler for his problem definition and illustration. He has a Java library of documented search code that you might want to check out as well.

Quote o' the week: I've got my skillet right here, buddy

2012-01-11T15:30:00.001-06:00

Perusing some cable-porn on /r/sysadmin, I found this piece of wisdom:

It's a two-pronged issue: Developers don't usually have the skillets or interests required for system administration.

That was part of a couple of insightful posts by sylver_dragon and tuba_man about the costs of using developers instead of sysadmins for system administration.

sylver_dragon:

> Developers are not sysadmins

This is one of my biggest complaints about the blanket term "IT". I have dealt with too many managers who don't understand that there really is (or should be) a separation between Systems Administration and Software Development. Usually, you get a developer acting as admin when either role is (at least) a full time job. The end result is usually that the little things on the sysadmin side suffer. Cable routing is treated as, "fuck it, good enough." Documentation is usually not maintained, regular log checking doesn't happen, etc. It's not that the developer can't do it, it's just that he doesn't have time.

tuba_man:

Exactly. Not only does he not have the time, but in a lot of ways, it prevents the developer (and the project or company as a whole) from operating most effectively. It's a two-pronged issue: Developers don't usually have the skillets or interests required for system administration. Application developers can work a lot better when they have solid systems to code on and deploy to. So a developer doing sysadmin work solely because he has to is in many cases shooting himself in the foot.

In my instance at least, our company's two developers work a hell of a lot better when they don't have to worry about systems or infrastructure. Since hiring me on, we've had more code output, higher quality code output, more uptime, better response times, and less customer complaints.

I, personally, keep my skillet with me at all times.

Update to "System programming"

2012-01-04T20:07:00.000-06:00

In case anyone is interested, I added a brief discussion of Jonathan Shapiro's "Programming Language Challenges in Systems Codes: Why Systems Programmers Still Use C, and What to Do About It" to Systems programming. He has an interesting definition of systems programs, and significant insights into the requirements for a systems programming language.

Tip: Converting a CVS repository to git

2011-12-30T18:25:00.001-06:00

I have a great load of source code (and other detritus) in a CVS repository that I've been copying around for years. I have not used CVS for anything new in a very long time, but because I was the only one modifying things, I did not bother to move the contents to anything more modern.

Occasionally, I need to reactivate a project, and usually want to move the history into a newer tool, git usually. And every time, I have to look up how to do it. So, here's the latest working scheme, in hopes that I don't have to search around anymore.

Copy the CVSROOT directory and the module from the repository to someplace local. My CVS root (and the master git repositories) live remotely. The destination doesn't matter much.
```
scp -r remote:CVS/{CVSROOT,module} CVS
```
Get a copy of the latest cvs2svn, which includes cvs2git, which seems to be working better than I remember. Use cvs2git to create the two git fast-import format files from the repository.
```
cvs2svn-2.3.0/cvs2git --blobfile=module-blob.dat --dumpfile=module-dump.dat --username me CVS/
```
Create a new git repository to act as the master repository for the project.
```
mkdir module.git
cd module.git/
git init --bare --shared
```

Import the project.

cat ../module-blob.dat ../module-dump.dat | git fast-import

Put the new master repository back on my remote server.
```
cd ..; scp -r module.git remote:GIT/
```
Clone the remote repository to create a local, working repository.
```
git clone ssh://remote/home/me/GIT/module.git
```
The import above leaves the CVSROOT and module directories in the git repository, so the useful content of the module is one level down into the repository. The first git operation on the working repository fixes that.
```
git rm -r CVSROOT/
git mv module/* .
git rm -r module
git commit -m 'Removing cvs residue'
git push
```

And with luck, that's that.

Quote o' the day: Criticism

2011-12-24T09:52:00.001-06:00

From reddit:

Criticizing another's favorite language is like criticizing their genitalia, religion or politics.

Words to live by.

Link o' the day: Set Theory

2011-12-15T20:30:00.000-06:00

I never really understood the whole deal about the Axiom of Choice. ("the last great controversy of mathematics"?) But now, I get it. Thanks, Randall Munroe!

Mad science, abstract data types, and objects

2011-12-12T06:00:00.000-06:00

Mad science, and mad scientists, are always good to find. They represent guaranteed entertainment. But they do show up in the oddest places. How about this one: OOPSLA 2009, William Cook presents a talk entitled "No one listened! But I'll show them, I'll show them all!". And the weird part was, nobody noticed. Well, sure, it's actually a popular paper that gets referenced frequently and the title is in fact "On Understanding Data Abstraction, Revisited", but there's no sign that the peasants went scurrying for their pitchforks and torches.

William Cook

So, what's the deal with Cook and his paper?

A little backstory

In 1990, Cook published "Object-Oriented Programming Versus Abstract Data Types" which is almost identical in content to, but somewhat longer than, "On Understanding Data Abstraction, Revisited". In both papers Cook describes the long-established, but little known, difference between objects and abstract data types. (For simplicity, the object-oriented side is limited to a subset of what I learned to call "object-based programming"; objects, as you might normally think of them, minus inheritance and also without modifications.)

Given those limitations, objects are data abstractions that "have a collection of methods, or procedures, that share access to private local state." Consider the type specimen of object-oriented programming: Smalltalk. In Smalltalk, objects have internal fields that contain the object's state, but this state is entirely unavailable to the outside world. Instead the object has a collection of messages that it responds to, exposing information potentially based on its internal state as necessary. Once an object is created, it is entirely encapsulated, isolated from any other code than that implementing its behavior. Because the interface of the data abstraction is the methods exposed by the object, Cook identifies objects as procedural data abstractions. The key feature of an object is that its interface is defined by its constructor: the collection of methods the object responds to and the semantics of those methods are defined by the construction of the object. In a sense, those methods are associated with the specific value or instance.

Abstract data types, on the other hand, have "a public name, a hidden representation, and operations to create, combine, and observe values of the abstraction." The classic examples of them are the primitive types in Java, C++, or most other common languages. A value has a defined type name, say "double", some representation (Do you really know, or care, what a double actually looks like? (Note: You should. Floating point numbers are a notoriously leaky abstraction.)), and operations like reading one or converting one from some other representation, adding or subtracting two of them, and converting one to another representation, such as a string of characters. The key feature of an ADT is that its interface is defined by a collection of operations that apply to a specific type.

Observations	[]	::
	Constructors
empty?	true	false
head	error	value

Let's say we create a matrix of operations on a data abstraction. My data abstraction is a list; it has two constructors, the Haskell-like "[]", or nil, building an empty list, and "::" or "cons", representing a constructor that takes a new element and an existing list and produces a new, combined list with the new element at the head. The list also has two "observation" operations, empty? which returns true for an empty list and false otherwise, and head, which produces some kind of error on an empty list, but returns the first value in the list otherwise. (This example is taken directly from "OOP Versus ADT".)

Observations	[]	::
	Constructors
empty?	true	false
head	error	value

Object-oriented

Suppose I want to create an object-oriented version of this data abstraction. I would divide up the operations by constructor, so that I had an implementation of empty? and head for an empty list and empty? and head for a cons cell. The details of each operation is divided among the objects created by each specific constructor. Adding a new constructor is easy, since it simply requires providing implementations of the observations on the new object. On the other hand, adding a new observation is difficult, since it requires modifying all of the existing constructors. This should sound familiar to anyone who has written code in almost any object oriented language.

Observations	[]	::
	Constructors
empty?	true	false
head	error	value

ADT

On the other hand, suppose I want an ADT version of this data abstraction. In this case, I would divide the operations by observation, so that I had an implementation of empty? and head that each covered all of the constructors. The details of each constructor is spread among the observation implementations. Adding new observation is easy; it just has to handle the individual cases of the constructors. Adding a new constructor is hard, though, because every observation needs to be modified. This option should be familiar to anyone who has used ML or Haskell, since it is how their algebraic data types work.

There are some less obvious consequences to these two styles of data abstraction. For one thing, the two approaches are almost duals; the advantages of one are the weaknesses of the other, and vice-versa. Both approaches do, in fact, provide data abstraction; objects by encapsulating the state of the data instance behind procedural abstractions, ADTs by encapsulating that state behind a type boundary. Both also describe (if you squint a bit) common data abstraction patterns. On the other hand, each approach has some peculiarities: because an object only has access to its own state, complex operations require weakening the encapsulation of objects. Cook calls "an operation 'complex' if it inspects multiple representations," like for example equality testing; I may not want to expose all of the implementation information necessary to compare two instances in the methods that an object responds to, yet I have no other option in order to implement some observations. Cook claims that object oriented, procedural abstractions are possible in dynamically typed languages but ADTs are not; "abstract data types depend upon a static type system to enforce type abstraction. It is not an accident that dynamic languages use objects instead of user-defined abstract data types. Dynamic languages typically support built-in abstract data types for primitive types; the type abstraction here is enforced by the runtime system."

I do not doubt the validity of this deconstruction of objects and abstract data types, if for no other reason than that it exactly covers Philip Wadler's "expression problem". Also, both ideas seem pretty productive, which is always the primary test of science on the hoof. If that was all there was to it, there would be no mad science involved.

The mad science part

Mad Science Tip #1: If you have to repeat the same message over 20 years, and no one seems to be listening to you, they're the crazy ones. They're the ones who don't see.

Mad Science Tip #2: A beautiful theory, one that explains everything, is obviously true. Even if reality doesn't seem to particularly agree. The ADT half of Cook's papers seems to be relatively uncontroversial, perhaps because no one actually uses the languages (like ML and Haskell) that have user-defined ADTs as the primary data abstraction scheme. On the other hand, Cook's minor point about the inability to use ADTs in dynamically typed languages doesn't seem particularly, well, true; most Lisps, for example, allow you to define structures (or write macros to build such structures) that have representations hidden from any functions other than a limited group. Such pseudo-ADTs may not be as encapsulated as Cook would like, but coupled with a common coding style rule, say "Don't do stupid things," they work well enough. Objects, likewise, do not actually seem to exist. It's been too long since I last used Smalltalk, but every other "object-oriented" language allows a method in a class to access the internals of more than one object of the same class, neatly avoiding (some cases of) the "complex" operation issue. (To avoid all of the difficulties presented by complex operations requires something like multimethods or other techniques that are even more rare.) Maybe some of the object systems for Scheme satisfy the requirements for objects, but Scheme doesn't have a standard anything, much less an object system; it is a toolkit for implementing other languages. Further, Cook's ideas on actually doing object-oriented programming in Java would likely horrify most Java-istas, even those that love interfaces as much as I do.

Mad Science Tip #3: You get extra points for hosting dinner parties where you torment your rivals.

What is the relationship between objects and abstract data types (ADTs)? I have asked this question to many groups of computer scientists over the last 20 years. I usually ask it at dinner, or over drinks. The typical response is a variant of “objects are a kind of abstract data type”.

Whereupon he goes all maniacal on them.

Last and possibly least, Mad Science Tip #4: Being a mad scientist is fun; you get to meet interesting people, there's nothing like the je ne sais quoi of carving your name in the moon with a giant laser. (For that matter, giant lasers are just plain cool no matter what you do with them.) But it may have detrimental effects on your social life.

Most groups eventually work through the differences between objects and ADTs, but I can tell they walk away feeling uneasy, as if some familiar signposts now point in different directions.

...or perhaps as if they're just glad to get away with all the right number of appendages.

Now, I'm not saying William Cook is going to destroy the world if Java 8 doesn't get objects right. But if you see him being followed by a giant tongue monster or psychopathic, hyper-intelligent gerbils, don't say I didn't warn you.

8,827,520 pixels!

2011-12-08T16:22:00.001-06:00

1440 x 900 on the (old) laptop,
3840 x 1080 in two monitors on the (new) laptop,
1920 x 1080 and 1280 x 1024 on the Mac.

We had a short-lived competition. I won only briefly.

Quote o' the day: flagrant reticulation

2011-12-08T12:17:00.000-06:00

In a reply to Ben Collins-Sussman's post, Your Community is NOT Your Tools, MarkusQ writes:

I think some of the git-resistance comes from different cultural assumptions around the cost of merging. I know from an svn mindset, the “mash the branches together and call it merged” mindset of the git-world can seem a little fast and loose. Likewise, I suspect the older “merging is to be approached with fear and reverence” culture may seem hidebound when you’re used to the flagrant reticulation, devil take the hindmost style that the git world embraces.

– MarkusQ

For those of you too lazy to look it up yourself,


$ dict reticulation
2 definitions found

From The Collaborative International Dictionary of English v.0.48 [gcide]:

  Reticulation \Re*tic`u*la"tion\, n.
     The quality or state of being reticulated, or netlike; that
     which is reticulated; network; an organization resembling a
     net.
     [1913 Webster]
  
           The particular net you occupy in the great
           reticulation.                            --Carlyle.
     [1913 Webster]

From WordNet (r) 3.0 (2006) [wn]:

  reticulation
      n 1: (photography) the formation of a network of cracks or
           wrinkles in a photographic emulsion
      2: an arrangement resembling a net or network; "the reticulation
         of a leaf"; "the reticulation of a photographic emulsion"

The only way to get more points would have been to work in "squamous".

Link o' the week: Bayes' Theorem

2011-12-02T23:38:00.000-06:00

I seem to be up to my armpits in Bayesian statistics. Between Thrun and Norvig's AI class (the AI classes I took back in the late '80's and early '90's primarily dealt with state-space search, neural networks, and predicate logic; there was nary a statistic to be found) and the very good textbook I ran across, Doing Bayesian Data Analysis: A Tutorial with R and BUGS by John K. Kruschke, this stuff seems to be appearing everywhere.

Then I ran across Eliezer Yudkowsky's post, An Intuitive Explanation of Bayes' Theorem. Now, intuition is a funny thing. It is not innate as most people seem to think, you have to train it. Yudkowsky does that, going over the same ground with many examples and good explanations. Better, his writing, like Kruschke's, is light and entertaining:

Fun Fact!
Q. How can I find the priors for a problem?

A. Many commonly used priors are listed in the Handbook of Chemistry and Physics.

Q. Where do priors originally come from?

A. Never ask that question.

Q. Uh huh. Then where do scientists get their priors?

A. Priors for scientific problems are established by annual vote of the AAAS. In recent years the vote has become fractious and controversial, with widespread acrimony, factional polarization, and several outright assassinations. This may be a front for infighting within the Bayes Council, or it may be that the disputants have too much spare time. No one is really sure.

Q. I see. And where does everyone else get their priors?

A. They download their priors from Kazaa.

Q. What if the priors I want aren't available on Kazaa?

A. There's a small, cluttered antique shop in a back alley of San Francisco's Chinatown. Don't ask about the bronze rat.

Bronze rat aside, I also like the Javascript calculators embedded in the article, allowing a reader to try to figure out the answers to Yudkowsky's examples without dredging up another app.

Quote o' the day: Coda Hale on the value of communities

2011-11-30T10:58:00.001-06:00

Coda Hale wrote a widely publicized private email to the-powers-that-be-in-Scala with the following line:

...but at some point a best practice emerged: ignore the community entirely.

Actually, there are some lessons there: Language communities are nice and fun and wonderful, but they may not be good ways of learning "best practices", whatever those are. It sucks to be an early adopter. (On the other hand, not having any early adopters isn't good either.) Oh, and if anyone asks you if they look fat, don't answer them.

Consolidated Reference List for the Software Engineering Body of Knowledge, Pt. 2

2011-11-24T11:27:00.000-06:00

This post contains the second half of a somewhat annotated version of the Consolidated Reference List for the IEEE Software Engineering Body of Knowledge (SWEBOK). You may want to start with the previous half.

A. Lopez-Ortiz. (1998, July 22, 2010). Algebraic Structures. Available: http://www.cs.uwaterloo.ca/~alopez-o/math-faq/mathtext/node6.html.

This one is more than a tiny bit ridiculous. The link is to the Frequently Asked Questions in Mathematics list from the Sci.Math FAQ Team. The specific link is to the section on algebraic structures: monoids, groups, rings, fields, and ordering. I'm sure that even the Sci.Math FAQ Team would find the reference to their FAQ in this list silly, if not insulting. Is that really all you need to know about abstract mathematics? Why not link to the FAQ's bibliography, one of the texts in it, or even my favorite, A Book of Abstract Algebra?
S. McConnell, Code Complete: A Practical Handbook of Software Construction , 2nd ed. Redmond, WA: Microsoft Press, 2004.

Unlike the previous, this text is completely unsurprising. McConnell's is one of the most popular books on programming and is likely filled with information that a professional software developer cannot live without. I personally don't know; I don't have a copy. You see, when I was first looking at it in a bookstore many years ago, I flipped to the section on recursion to see what he had to say:
One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it's really dumb to use it in either of those cases. If a programmer who worked for me used recursion to compute a factorial, I'd hire someone else. Here's the recursive version of the factorial routine:
```
 int Factorial( int number ) {
    if ( number == 1 ) {
      return 1;
    } else {
      return number * Factorial( number - 1 );
    }
  }
```
In addition to being slow and making the use of run-time memory unpredictable, the recursive version of this routine is harder to understand than the iterative version, which follows:
```
  int Factorial( int number ) {
    int intermediateResult = 1;
    for ( int factor = 2; factor <= number; factor++ ) {
      intermediateResult = intermediateResult * factor;
    }
    return intermediateResult;
  }
```
(Emphasis mine.) Now, where to start with this passage? Recursion is a powerful tool, and in some programming languages that McConnell may not be familiar with, it's fundamental; there may not even be any other iteration structures. So, whether it's dumb to use it in any specific case is a more difficult question than he seems to think. Heck, even most decent modern C compilers include tail call optimization, so the speed and memory use of recursion is an open question. On the other hand, McConnell previously presented as a good use of recursion a maze-solving function; maze solving is an application of state-space search, which has a simple, clear, and wildly flexible implementation based on a priority queue. Further, I find it simply bizarre that McConnell believes a recursive version of factorial is "harder to understand" than the iterative version. Quick! Prove to me that his two versions actually compute a factorial:
\[ n! = \begin{array}{lr} 1 & \textrm{if $n$ = 1} \\ n * (n-1)! & \textrm{if $n$ > 1} \end{array} \]
Finally, there's the whole "If a programmer who worked for me...I'd hire someone else" thing. The sections before and after recursion are on multiple returns in a routine and goto's; I'm afraid to look at either.
S. J. Mellor and M. J. Balcer, Executable UML: A Foundation for Model-Driven Architecture, 1st ed. Boston: Addison-Wesley, 2002.

This is another topic that leaves me cold. UML is good enough for what it is, a way of communicating ideas about a project, and I'm certainly a programming language collector. However, I have never felt that UML would make a good programming language, which is exactly what xUML and other executable model languages are.
D. C. Montgomery and G. C. Runger, Applied Statistics and Probability for Engineers , 4th ed. Hoboken, NJ: Wiley, 2007.

(The link is to the fifth edition.) Statistics and I have an uneasy relationship. I know there is a great deal of value in statistical data analysis, as an end itself as well as about the software development process. On the other hand, I don't really know much about the topic, and I reference my previous comments about lacking numerical methods experience and thus my inability to use floating point numbers. Anyway, it's an important topic; this may or may not be a good reference (several of the Amazon reviewers mention errors in the text), and I don't have a better one at hand. Your mileage may vary.
J. W. Moore, The Road Map to Software Engineering: A Standards-Based Guide, 1st ed. Hoboken, NJ: Wiley-IEEE Computer Society Press, 2006.

The Road Map to Software Engineering organizes relevant IEEE software and systems standards, along with standards from other sources, using two frameworks: the SWEBOK Guide's topical knowledge areas and the widely used IEEE/EIA 12207 standard [IEEE Standard for Information Technology - Software Life Cycle Processes].
The Road Map to Software Engineering allows practitioners to quickly locate the standards pertinent to questions arising in real projects. Providing students with a comprehensive body of knowledge, the text also assists experienced professionals in finding and filling gaps in their understanding.

Probably a vital reference for those using official standards; probably not something I need.
J. Nielsen, Usability Engineering, 1st ed. Boston: Morgan Kaufmann, 1993.

Jakob Nielsen is a very good writer on usability topics. I own and appreciate a copy of his Designing Web Usability even though my idea of usability seems to differ strongly from others'. I will be getting a copy, since I was not previously aware if this. On the other hand, this is nearly 20 years old; is there no more recent reference?

Update: I just got a copy of this book, and I am very impressed so far. The emphasis, at least from the parts I have read so far, is on providing basic usability information and usability testing techniques that do not require massive investments of resources. I do not have the book handy while I'm writing this, but if I interpret Nielsen correctly he writes that a (quantifiable) big win can be had by simply observing actual users for a few hours, and by asking them what they think.
L. Null and J. Lobur, Essentials of Computer Organization and Architecture, 2nd ed. Sudbury, MA: Jones and Bartlett Publishers, 2006.

(Link is to the third edition.) I love Linda Null's name, let me get that out of the way. Computer architecture is a topic I know a bit about, and, although I'm not familiar with this book, it does seem to cover most of the bases appropriately. Certainly, if a programmer who worked for me didn't know a good bit of this stuff, I'd hire someone else. But this text seems to relegate parallel and concurrent architectures to a section of a chapter on alternative organizations, which is somewhat surprising given the not-so-recent trend towards those architectures. There doesn't even seem to be anything on pipelines, which is vital for high-performance software. Another book, Computer Organization and Architecture: Designing for Performance by William Stallings, does have extensive coverage of parallel architectures although it looks to be less clear and well organized. Given the choice, I would probably favor clarity over coverage.
M. Page-Jones, Fundamentals of Object-Oriented Design in UML, 1st ed. Reading, MA: Addison-Wesley, 1999.

Object-oriented design and programming are not the end-all of software development strategies. It is not appropriate for everything, and an uncritical use of it is not appropriate for anything. I view it as a technique for managing complexity since is pretty successful at that while bringing along its own complications. I, on the other hand, would prefer to remove complexity. That being said, you will need to know a lot about object-oriented design, and Page-Jones is probably a good-enough teacher. (I have his Practical Guide to Structured Systems Design and don't know of anything wrong with it.) On the other hand, if you need a guide to UML, I prefer UML Distilled: A Brief Guide to the Standard Object Modeling Language by Martin Fowler.
G. K. Palshikar, "Applying Formal Specifications to Real-World Software Development," IEEE Software, vol. 18, pp. 89-97, 2001.

While formal methods are gaining acceptance in the software industry, there is a need for practical guidelines for making the best use of formal specifications. The author provides a few such pragmatic tips for people involved in the industrial use of formal specifications. The 15 guidelines are split into two areas, dealing with process and content. The author also includes a full-page reference for literature available over the Web.

A very good introduction to the use of formal specification methods. I hope the computer.org link above is available to non-IEEE and non-Computer Society members; if it isn't, please let me know. I am tempted to throw propriety (and copyright) out the window and host a link to this paper myself.
S. Redwine, "Security-Oriented Pointwise Changes to SWEBOK Guide," 2009. Available: http://www2.computer.org/cms/Computer.org/SWEBOK/Information-for-Item-Writers-v14.pdf

The original set of suggested changes to the 2004 SWEBOK to incorporate topics from the new security knowledge area. This paper is probably only useful in conjunction with that version of the SWEBOK guide. As an addition, two of the three referenced texts are Software Security Engineering and Computer Security, already found on this consolidated reference list; the third is Summerville's Software Engineering below. A fourth reference is to "Software Assurance: A Curriculum Guide to the Common Body of Knowledge to Produce, Acquire, and Sustain Secure Software Version 1.2", edited by Redwine and from the US Department of Homeland Security. (My tax dollars at work!)
K. Rosen, Discrete Mathematics and Its Applications, 6th ed. Boston: McGraw-Hill, 2006.

(Link is to the seventh edition.) Discrete mathematics is probably more important to software developers than, say, differential and integral calculus, and I'm not just saying that because calculus and I didn't really agree back in my undergraduate years. More information is available from the McGraw-Hill site for the book, including a sample chapter.
A. Silberschatz, et al., Operating System Concepts, 8th ed. Hoboken, NJ: Wiley, 2008.

True story: I was at a conference looking at the forthcoming books table and a full professor near me pointed to a copy of a new edition of one of Avi's (Abraham Silberschatz) books and asked "Avi has another kid going to college?" I seem to recall learning operating systems from a previous edition of this text, and databases from another of Avi's books, and I haven't been adversely affected. (The tics have mostly gone away.) They are pretty common, for a good reason, but there are alternatives from Tanebaum, Stallings, Deitel, and probably others that are just as good.
I. Sommerville, Software Engineering, 8th ed. New York: Addison-Wesley, 2006.

(Link is to the ninth edition.) A general text on software engineering, this got good reviews from Dr. Tom Hilburn, who taught the software engineering course at the IEEE Smart Tech mini-conference. It's about 800 pages and should be good to bludgeon many, many infidel software developers, managers, and what-not.
The Data and Analysis Center for Software. (2008, July 22, 2010). Goal-Question-Metric (GQM) Approach. Available: https://www.goldpractices.com/practices/gqm/
GQM is a top-down approach to establish a goal-driven measurement system for software development, in that the team starts with organizational goals, defines measurement goals, poses questions to address the goals, and identifies metrics that provide answers to the questions.... [It] is particularly useful for the following purposes:
- Understanding and baselining an organization’s software practices
- Guiding and monitoring software processes
- Assessing new software engineering technologies
- Evaluating and certifying improvement activities
GQM seems to be a general, relatively process-agnostic method for generating metrics for software development processes; it looks interesting. I need to look at it further.
S. Tockey, Return on Software: Maximizing the Return on Your Software Investment, 1st ed. Boston: Addison-Wesley, 2004.

Assuming this book does what it claims, it would be a very good text to have around. Particularly given the recent appearances of "Don't call yourself a programmer" postings, giving career advice on the advantages of appealing to the business side of technical decisions.
- Estimate how much each proposed software technical decision will cost, and how much it will return.
- Weigh the time frames for a software decision's costs and benefits against each other to reveal when there might be a more important factor than schedule.
- Attach a value to quality and produce a rational answer to the question, "How much testing is enough?"
- Account for risk and uncertainty in software technical decisions, such as when considering a new technology.
- Communicate your decisions in a way that speaks to the all-important bottom line.
Also from the back cover:

"This just what the doctor ordered to help software programs solve the problem of how to introduce engineering economics and business decision-making into their curricula. The economics of software development should not only be part of any computing curriculum they are an essential element of recent accreditation and certification recommendations.
This book is an accessible and relevant text for any student of software engineering. The style is clear and straightforward and the software examples will be appealing to students and faculty alike. I can't wait to use it in class!"
Thomas B. Hilburn, Professor
Department of Computer and Software Engineering
Embry-Riddle Aeronautical University

The introduction of the book is available online; I especially like this paragraph:

In another case I was developing software to monitor radiation at nuclear power plants. Part of that software needed a sorting routine. I wrote a simple insertion sort routine and had that part of the system running in a matter of hours. A coworker insisted on developing a QuickSort routine because "everybody knows that QuickSort is better than insertion sort." At that time (early 1980s) reusable QuickSort routines weren't available; if you wanted one, you had to write it yourself. Unfortunately, QuickSort is a recursive algorithm, and the programming language we were using, Fortran-IV, didn't support recursion. My coworker spent more than a week developing QuickSort in Fortran-IV. Only later did he realize that the list that needed sorting averaged only about 30 entries and was predominantly sorted to begin with. Small lists that are already mostly sorted cause QuickSort to have extremely poor performance, typically worse than simpler algorithms such as insertion sort. Moreover, sorting happened in this system fewer than 50 times a day. Even if QuickSort did perform better than insertion sort, it would take decades for the company to recover its investment. My coworker's effort turned out to be a pretty big waste of the company's money and time.

This is going onto my shopping cart.
G. Voland, Engineering by Design, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2003.

This looks to be a very interesting book, and I'm saying that as a Henry Pretrovski addict. Judging by what I can find, it appears to come from the physical object design world.

The book introduces readers to a broad range of important design topics. It provides numerous cases that illustrate both successes and failures in engineering design; qualitative presentation of engineering practices are easily understood by readers with little technical knowledge, and analytical techniques are given that allow the development and evaluation of proposed engineering solutions. Coverage includes: an overview of engineering design, needs assessment, structuring the search for the problem, structuring the search for a solution (design goals and specifications), acquiring and applying technical knowledge, abstraction and modeling, synthesis, ethics and product liability issues, and hazards analysis and failure analysis. An excellent handbook for design engineers.

Gerard Voland is Provost and Vice Chancellor at the University of Michigan-Flint. I've got no idea if that is a good thing or a bad thing.
K. E. Wiegers, Software Requirements, 2nd ed. Redmond, WA: Microsoft Press, 2003.

A book about requirements engineering. Keep in mind that, whatever I say about this book, the only reliable way I have found to identify, analyze, and satisfy requirements is by some variant of the "agile", open-source, throw-it-at-the-wall-and-see-what-sticks approach (which cannot with any justice be called prototyping). I do have a copy of the follow-on, More About Software Requirements: Thorny Issues and Practical Advice, and have not seen anything particularly wrong in it. Just not very applicable.
J. M. Wing, "A Specifier's Introduction to Formal Methods," Computer, vol. 23, pp. 8, 10-23, 1990.

I found two links to PDF versions of this paper, one a copy of the article as it appeared in Computer and the other a CMU technical report, CMU-CS-90-136. Pick the way you want to read it, I guess.

This paper is a decent introduction to formal methods, including examples of a fair number of specific techniques in the last half, as they stood in 1990. There is nothing really wrong with that; there have only been a few major changes in formal methods since then. Z (pronounced "Zed") and communicating sequential processes both appear, and both are as relevant or irrelevant as they ever were. (As an aside, I have a small stack of very good Z books.) I did not see anything covering model checking, and there certainly was nothing on dependently typed programming languages, two of what I believe to be the biggest changes in formal methods. That aside, it is a pretty good read.

Consolidated Reference List for the IEEE Software Engineering Body of Knowledge

2011-11-21T23:02:00.000-06:00

This is the first half of a none-too-serious annotated bibliography of the references that the IEEE Computer Society has identified as the most important sources for its Software Engineering Body of Knowledge (SWEBOK). (When you get done with this, you can read the second part.) Note: I have not actually read all (or most, for that matter) of these books, nor do I intend to. I will identify those I have, and those I have not are evaluated on what I, as a professional, think of their publicly available information. You have been warned.

A. Abran, et al., Eds., Guide to the Software Engineering Body of Knowledge. Los Alamitos, CA: IEEE Computer Society, 2004.
This consolidated reference list (if I were a true software engineer, I would have written that as "CRL") is associated with the version 3 of the SWEBOK (which is really too long to type out). However, because that version is still in development, it refers to the previous, 2004 version. The new version is supposed to add knowledge areas on professionalism, software engineering economics, mathematical and computing foundations, and possibly measurement and security, and revise the existing structure. Duck and cover!
J. H. Allen, et al., Software Security Engineering: A Guide for Project Managers . Upper Saddle River, NJ: Addison-Wesley, 2008.
Yes. Well. So, any book with "managers" in the title leaves me with a sort of squishy feeling, particularly as a reference for practitioners. The advertising text doesn't really help:

One view of secure software is software that is engineered “so that it continues to function correctly under malicious attack” [McGraw 2006] and is able to recognize, resist, tolerate, and recover from events that intentionally threaten its dependability. Broader views that can overlap with software security (for example, software safety, reliability, and fault tolerance) include the notion of proper functioning in the face of unintentional failures or accidents and inadvertent misuse and abuse, as well as reducing software defects and weaknesses to the greatest extent possible regardless of their cause. This book addresses the narrower view.
(Emphasis mine.) Personally, I do not really feel I need to "increase [my] awareness and understanding of the security issues in the design and development of software"; rather I need good information on producing secure systems or, better yet, a general approach that leads to secure systems by construction. But then, I suspect I take the broader view described above.
M. Bishop, Computer Security: Art and Science. Boston: Addison-Wesley, 2002.
This sounds like a much more useful book. It seems to have gotten good reviews in both SysAdmin and by Peter Salus in ;login, and appears to be an attempt at a complete reference tome. There are a couple of chapters available online at Bishop's UC Davis page; Chapter 13: Design Principles leaves me interested.
- Principle of Least Privilege
- Principle of Fail-Safe Defaults
- ...Economy of Mechanism
- ...Complete Mediation
- ...Open Design
- ...Separation of Privilege
- ...Least Common Mechanism
- ...Psychological Acceptability
Bishop also has an alternate version, Introduction to Computer Security , that "omits much of the mathematical formalism, making it more accessible for professionals and students who have a less formal mathematical background, or for readers with a more practical than theoretical interest". I think I may have to get a copy of Computer Security: Art and Science.
B. Boehm and R. Turner, Balancing Agility and Discipline: A Guide for the Perplexed . Boston: Addison-Wesley, 2003.
This book about agile software development processes also looks pretty interesting. One common complaint about agile methods from traditional or more engineering-oriented developers is that they are undisciplined; a common complaint from agile developers is that more disciplined processes are unusable. Both are ironic, since most methods are followed in name only, in my experience.
F. Bott, et al., Professional Issues in Software Engineering , 3rd ed. New York: Taylor & Francis, 2000.
Professional Issues in Software Engineering looks like a good reference to, well, professional issues: the profession and professional organizations, economics, contracts, intellectual property, employee relations, health and safety, liability, criminal law, and regulation of personal information are all represented in the table of contents. Now, professional issues may not interest most developers (or anybody else), but they are something that I am beginning to appreciate more, and something that I detect a serious lack of, now that I have moved into less technically-oriented employment. (Ahem.)
J. G. Brookshear, Computer Science: An Overview , 10th ed. Boston: Addison-Wesley, 2008.
Again, this is an introductory text that doesn't seem to be terribly useful to someone engaged in the profession of creating software systems.

Computer Science: An Overview uses broad coverage and clear exposition to present a complete picture of the dynamic computer science field. Accessible to students from all backgrounds, Glenn Brookshear uses a language-independent context to encourage the development of a practical, realistic understanding of the field. An overview of each of the important areas of Computer Science (e.g. Networking, OS, Computer Architecture, Algorithms) provides students with a general level of proficiency for future courses.
On the other hand, it looks like a very good book to give to someone who wants to know what computer science is about. On the other, other hand, however, it seems a little pricey.(The link is to the more-recent 11th edition.)
D. Budgen, Software Design , 2nd ed. New York: Addison-Wesley, 2003.
I have my own ideas about the concept of software design, which I will keep to myself for the moment. In the mean time, this book appears to be more of a meditation on what "design" is than a useful guide to software designs-man-ship. The three parts of the book are the nature of the design process, transferring design knowledge (which includes a chapter on "some design representations" and a chapter on design patterns), and design practices; the last breaks down into chapters on stepwise refinement, incremental design, structured analysis and design, Jackson Structured Programming, Jackson System Development, object-oriented design, component-based design, and the formal approach to design. Certainly, it seems a limited and idiosyncratic choice of topics.
E. W. Cheney and D. R. Kincaid, Numerical Mathematics and Computing , 6th ed. Belmont, CA: Brooks/Cole, 2007.
Strangely, I do not know either Ward Cheney or David Kincaid, although I've heard of the latter often enough. Also, I have never taken a course on numerical methods, which by my own rules means that I should never use floating-point numbers. I am afraid all I can say is that this looks like a textbook on numerical methods. Enjoy!
P. Clements, et al., Documenting Software Architectures: Views and Beyond . Boston: Addison-Wesley, 2002.
This is a text on documenting software architectures. That is probably not as goofy an idea as it sounds, since the architecture of a system is, in the first place, somewhat fundamental to the software, but, in the second, usually hidden behind the mass of trees. The actual architecture of a system may not appear outside of its documentation, and the notation for that documentation may well guide the architecture you get. Note: I'm still reserving my ideas about design and indeed, architecture.
One reviewer on Amazon writes that this book is an extension of the Carnegie Mellon Software Engineering Institute technical report CMU/SEI-2001-TN-01, Documenting Software Architectures: Organization of Documentation Package by a subset of the authors. That document may be a good place to start. (Book link is to the second edition.)
L. Copeland, A Practitioner's Guide to Software Test Design , 1st ed. Boston: Artech House, 2004.
This book seems to be a decent reference to some various forms of test design, black box and white box. On the other hand, the only references to unit testing are in chapter 1, the testing process, under "testing levels", and the introduction to white box testing. Test-driven development is not mentioned at all. In other words, it is a reference to old-school test methods. Not that those are unnecessary or detrimental, just that they are the kinds of things you run less than frequently, just prior to a release. Knowing how they work will certainly expand your options, even if you are into TDD, and somebody in your project will probably need to know this stuff.
R. E. Fairley, Managing and Leading Software Projects . Hoboken, NJ: Wiley-IEEE Computer Society Press, 2009.
Some management topics are necessary to development projects: estimating, measuring, and risks. I might just buy it for this sentence on the back cover:

It introduces software development methods, from traditional (hacking, requirements to code, and waterfall) to iterative (incremental build, evolutionary, agile, and spiral), and illustrates and emphasizes how to tailor the development process to specific projects.
(Emphasis mine.) On page 54, "hacking" is characterized by a reference to the cartoon with the caption, "You start coding and I'll go find out what they want," which is actually a pretty fair description of one of the few ways I know to reliably come up with a project's requirements.
[12] E. Gamma, et al., Design Patterns: Elements of Reusable Object-Oriented Software , 1st ed. Reading, MA: Addison-Wesley Professional, 1994.
And finally, a book that I own and have read. Now, this is an important book, and contains many good ideas, both for software designs and for communicating those designs. Yet, I am not a pattern-ista. In fact, I am of the set that regards design patterns as work-arounds for poor programming languages. Still, the contents of this book are probably necessary, if you are going to hang around software development for very long.
T. Gilb and D. Graham, Software Inspection , 1st ed. Reading, MA: Addison-Wesley, 1993.
An inspection is a formal examination of some artifact specifically to detect problems.

Zero-defect software is the Holy Grail of all software developers. It has proved to be an elusive goal - until now. The Inspection techniques illustrated in this book have brought clear benefits in terms of lower (or even zero) defects, higher productivity, better project tracking and improved documentation.
Maybe there is a silver bullet, after all.
P. Grubb and A. A. Takang, Software Maintenance: Concepts and Practice , 2nd ed. River Edge, NJ: World Scientific Publishing, 2003.
Judging by the table of contents, this looks like an interesting book; it includes how new development differs from maintenance, what takes place during maintenance (program understanding, reverse engineering, reuse, testing), and tools. On the other hand, the authors write in the preface, "...challenges that software engineers face when modifying complex software systems...can be seen in the cost of modifying software...[which] can reach 70% of the total life-cycle cost." That number always leaves a strange taste in my mouth, since for any successful project I have encountered, the cost actually asymptotically approaches 100%.
A. M. J. Hass, Configuration Management Principles and Practice , 1st ed. Boston: Addison-Wesley, 2003.
I am the first to claim that configuration management is one key to any reasonably successful project. However, I suspect that this is not the best book on the subject. The table of contents runs for 18 pages out of 350 or so with several interesting looking sections, but I do not see anything compelling overall. For example, Chapter 22 is "Getting started on configuration management---up to capability level 1" with subsections on "How to get started from nothing" and "First steps toward configuration management", but the next chapter, "Planning configuration management---up to capability level 2" seems to be all about a configuration management plan document, not what to do with the foundation from the previous chapter.
E. Horowitz, et al., Computer Algorithms , 2nd ed. Summit, NJ: Silicon Press, 2007.
I have never seen this book before. If they had referenced Introduction to Algorithms by Comen, Leiserson, Rivest, and Stein, I would not have said anything at all; that is the book most people would think of, I believe. (Strange but true: that was the one computer science class I ever dropped. After a single class session.) Still, Computer Algorithms looks to be a good book, although at 773 pages of algorithmy goodness, I suspect it's not light reading.
IEEE-CS/ACM Joint Task Force on Software Engineering Ethics and Professional Practices. (1999, July 22, 2010). Software Engineering Code of Ethics and Professional Practice (Version 5.2).
This one is free, reasonably short, and quick reading. The short version is:
Software engineers shall commit themselves to making the analysis, specification, design, development, testing and maintenance of software a beneficial and respected profession. In accordance with their commitment to the health, safety and welfare of the public, software engineers shall adhere to the following Eight Principles:
1. PUBLIC - Software engineers shall act consistently with the public interest.
2. CLIENT AND EMPLOYER - Software engineers shall act in a manner that is in the best interests of their client and employer consistent with the public interest.
3. PRODUCT - Software engineers shall ensure that their products and related modifications meet the highest professional standards possible.
4. JUDGMENT - Software engineers shall maintain integrity and independence in their professional judgment.
5. MANAGEMENT - Software engineering managers and leaders shall subscribe to and promote an ethical approach to the management of software development and maintenance.
6. PROFESSION - Software engineers shall advance the integrity and reputation of the profession consistent with the public interest.
7. COLLEAGUES - Software engineers shall be fair to and supportive of their colleagues.
8. SELF - Software engineers shall participate in lifelong learning regarding the practice of their profession and shall promote an ethical approach to the practice of the profession.
Learn it; love it; live it.
S. H. Kan, Metrics and Models in Software Quality Engineering , 2nd ed. Boston: Addison-Wesley, 2002.
This is another topic that I have never spent much time with. Looking at the table of contents, this text seems to offer a lot of interesting options, although I do not know if it goes into enough detail to actually implement them. Certainly, it cannot be worse than the "time to fix" numbers from various build and bug tracking tools. Chapters 15, 16, 17, and 18, on quality assessments and process improvement, do leave me somewhat concerned about the amount of snake oil involved.

If you are not completely bored yet, you can go to the second half of the list.

Link o' the day: Roslyn and eval for C#

2011-11-17T10:29:00.000-06:00

Engaging in a journey of adventure and discovery, InfoWorld's Microsoft's Roslyn: Reinventing the compiler as we know it shows that C# developers are on the way to learning that eval in production code is not such a great idea.

So what is Roslyn good for?

The most obvious advantage of this kind of "deconstructed" compiler is that it allows the entire compile-execute process to be invoked from within .Net applications. Hejlsberg demonstrated a C# program that passed a few code snippets to the C# compiler as strings; the compiler returned the resulting IL assembly code as an object, which was then passed to the Common Language Runtime (CLR) for execution. Voilà! With Roslyn, C# gains a dynamic language's ability to generate and invoke code at runtime.

Put that same code into a loop that accepts input from the user, and you've created a fully interactive read-eval-print loop (REPL) console for C#, allowing you to manipulate and experiment with .Net APIs and objects in real time. With the Roslyn technology, C# may still be a compiled language, but it effectively gains all the flexibility and expressiveness that dynamic languages such as Python and Ruby have to offer.

(One of the benefits of the difficulty of doing this sort of thing in C, for example, is that it's so painful that no one who would likely misuse it ever actually does.)

IEEE Smart Tech Workshop, Huntsville

2011-11-12T12:15:00.001-06:00

Last weekend, I spent a couple of days going to the IEEE Smart Tech metro-area workshop in Huntsville, AL. The Metropolitan Area Workshop is a traveling conference sponsored by the IEEE Power and Energy Society, IEEE Computer Society, IEEE Communications Society, and IEEE-USA, with tracks on software engineering, wireless communications, smart power grid and, in our case, career assistance. In Huntsville, it was November 4-5 at the Von Braun Center.

Overall, the workshop was pretty decent. About 120 people attended; breakfast (pastries), lunch (boxed sandwiches), and a reception with enough food for dinner were provided; the price for IEEE members was $119; and there were no major catastrophes. (And I'm not just saying that because I set up the wireless access point that seems to have survived pretty well. Go DD-WRT!)

Software engineering essentials

Friday, I went to the "Software engineering essentials" track session, which was billed as:

Designed for software development professionals interested in confirming knowledge of industry-standard software practices.

Learn the principles, standards, and practices of software engineering to create more robust applications.

Review all 15 Knowledge Areas presented in the Guide to the Software Engineering Body of Knowledge (SWEBOK) with a special focus on principles and practices of Software Requirements, Design, Construction, and Testing.

Quizzes to test knowledge.

Course based on curriculum for the IEEE CSDP [Certified Software Development Professional] designation.

Increase your overall knowledge of the software development lifecycle and value to your company.

The reality was not quite as expected. The class was taught by Dr. Tom Hilburn, Professor Emeritus of Software Engineering and Distinguished Engineering Professor at Embry-Riddle Aeronautical University. It briefly reviewed the following Knowledge Areas:

Software architecture and design
Software engineering process models
Software engineering economics
Professionalism and professional practice
Configuration management
Computing foundations, mathematical foundations, engineering foundations

There were more details on:

Requirements
Testing

The workshop was focused on the CSDP Assessment Course. The detailed information about requirements and testing was presented by going through the assessment course sections on those KAs. As a result, the course was described by one participant as an "advertisement" for the assessment course.

As a result, it failed as both an introduction to the essentials of software engineering and as a preparation for the CSDP. Like the Head First... books I have read, it was too focused on the assessment (in this case) to work as a tutorial on the given topic. And, because it spent so much time on the detailed topics, there was no time or effort put into trying to cover the scope of the CSDP.

The two images are taken from CMU/SEI technical report CMU/SEI-96-TR-004 / ESC-TR-96-004, A Mature Profession of Software Engineering, Gary Ford and Norman E. Gibbs, January 1996. The first, Figure 1-2, was was used by Dr. Hilburn as an illustration of a profession for software engineering; the second, Figure 1-3, is a little clearer about what is going on.

Introduction to the smart grid

The course I attended on Saturday was another kettle of fish. It's billing was:

Recommended for all technology professionals

NIST Conceptual Model and its domains and interfaces.

Smart metering.

The current state of smart grid applications and how these drive infrastructure requirements.

The integration of smart grid elements into utility operations.

Distribution automation as an enabling technology for smart grid.

Smart grid cyber security technology.

Smart grid standards framework and its challenges.

Overview of smart grid network communications and the data needed in/out of the network.

Monitoring equipment used by smart grid applications in the network to generate data for analysis and improving customer service.

The class not only covered all that, it was entertaining to boot. The class was presented by Jerry Melcher of Quanta Technology and included a stack of random factoids:

Storage per volume: Diesel 3300 joules/cc, lead acid battery 50 joules/cc, lithium ion batteries 150 joules/cc.
Storage on the customer side, rather than the utility side, is most efficient.
Economics today call for natural gas generators, or demand response technology.
Demand response systems look like generators to the utility. They act by reducing load from the consumer, providing the equivalent of low-cost generation for the provider. Demand response techniques are in widespread use for industrial consumers, but modern advanced metering technology and home area networking are needed to allow the utility to communicate with a non-industrial consumer's loads.
The expected longevity of utility equipment is 40 years, something that is a surprise to most technology firms attempting to enter the business.
Quote: "The worst thing that we could allow to happen to our client was to let them talk us into a custom deployment."

Unfortunately, since I know almost nothing about electrical power technology, most of the details of the class were not terribly useful for me.

ed is the standard text editor

2011-11-10T19:16:00.000-06:00

Yes, I know there are other ways of doing this kind of thing, particularly if you have chef or cfengine or whatever configured. Right here, right now, I don't. Yay.

ed has one very strong advantage over other editors: it is scriptable. No, not scriptable as in you can write code to modify how it works, scriptable as in it can be driven by a file full of commands, and thus can be run remotely, in a loop. So, if you need to edit a file on a mess of machines, to make the same change everywhere, remember, "ed is the standard text editor."

Create a script file containing the ed commands and the appropriate text:

$ cat /tmp/edit 
g/^SSLRandomSeed connect/
a

# http://www.g-loaded.eu/2011/09/27/mod_gnutls-rc4-cipher-beast/
SSLHonorCipherOrder on
SSLCipherSuite !aNULL:!eNULL:!EXPORT:!DSS:!DES:RC4-SHA:RC4-MD5:ALL
.
w
q
$

Then, use ssh to connect to the remote host and run the ed command on the file to be edited, reading standard input from the file. Trust me, using the separate file is easier than writing the commands in a here-document or something.

$ for j in 01 02; do for k in b c; do ssh host$k$j ed /usr/local/httpd/conf/httpd.conf < /tmp/edit; done; done

Link o' the day: Donald Knuth, Tony Hoare, and goto

2011-11-04T02:56:00.000-05:00

Hah! I found it!

Ok, I suspect I've found (and possibly blogged about) this before, but I like it, I think it is important and in any case, I just found it (again).

Following Edsger Dijkstra's Goto statement considered harmful [PDF], Donald Knuth wrote Structured programming with go to statements, in which is written (p. 289):

Axiomatics of Jumps

[...]

Just recently, however, Hoare has shown that there is, in fact, a rather simple way to give an axiomatic definition of go to statements; indeed, he wishes quite frankly that it hadn't been quite so simple. For each label $L$ in a program, the programmer should state a logical assertion $\alpha(L)$ which is to be true whenever we reach $L$. Then the axioms \[ \{\alpha(L)\}\ \textbf{go to}\ L\ \{false\} \] plus the rules of inference \[ \{\alpha(L)\}\ S\ \{P\}\ \vdash\ \{\alpha(L)\}\ L:S\ \{P\} \] are allowed in program proofs, and all properties of labels and go to's will follow if the $\alpha(L)$ are selected intelligently. One must, of course, carry out the entire proof using the same assertion $\alpha(L)$ for each appearance of the label $L$, and some choices of assertions will lead to more powerful results than others.

Informally, $\alpha(L)$ represents the desired state of affairs at label $L$; this definition says essentially that a program is correct if $\alpha(L)$ holds at $L$ and before all "go to $L$" statements, and that control never "falls through" a go to statement to the following text. Stating the assertions $\alpha(L)$ is analogous to formulating loop invariants. Thus, it is not difficult to deal formally with tortuous program structure if it turns out to be necessary; all we need to know is the "meaning" of each label.

Unfortunately, Knuth does not cite where Hoare had just recently shown that.

Systems programming

2011-11-01T22:07:00.000-05:00

People frequently come up to me and ask, "Bob, what is systems programming?" or, "Hey, Bob, what is a systems programming language?"

Those are more difficult questions than they appear. For part of the confusion, I blame John Ousterhout, the creator of the TCL programming language. TCL does not seem to get much use these days, but was one of the early, popular dynamic languages along with Perl, Python, and PHP. In "Scripting: Higher Level Programming for the 21st Century", Ousterhout wrote,

System programming languages were designed for building data structures and algorithms from scratch, starting from the most primitive computer elements such as words of memory. In contrast, scripting languages are designed for gluing: they assume the existence of a set of powerful components and are intended primarily for connecting components together.

I believe he was wrong on both counts. On the one hand, all programming languages are, or should be, designed for building data structures and algorithms; to do otherwise severely limits what can be done with the language, even more so than not being Turing complete[1]. On the other hand, designing a language for connecting components primarily written in some other language is a losing game since most users will not create separate components.[2][3]

What have Ousterhout's comments got to do with systems programming? His definition has, I believe, either led to (or been a result of the same cause of) many other languages such as Java being called "systems programming languages" when they rightly are not. The right question is not "What is the difference between systems programming languages and scripting languages", but "What is the difference between systems programming and applications programming?" To my mind, there is less real difference between TCL, Python, Perl, Ruby, and so on, and Java, Go, C#, etc., than between C and anything on that list.

So, what exactly is systems programming? It's hard to say. What are some of the characteristics of systems programming? That's an easier question. Systems programming usually involves the creation of software for use by other software, not by humans. Systems programming is almost always about managing resources for use by that other software. Systems programs may, and likely will, be built around complex data structures and algorithm and will also likely be built from the "most primitive computer elements" such as words of memory, if only because either

there is nothing below them to create "less primitive" abstractions, or
it is absolutely vital that their performance, or memory, or some other footprint not directly related to whatever the ultimate task is, be optimized.

Operating system kernels are definitely systems programming. As are device drivers. Compilers? Not systems programs. Interpreters and virtual machines? Maybe. Embedded programming is a bit of a special case: many of the tasks involved in embedded software may be similar to the tasks involved in applications, but because the resources available to embedded software are so relatively expensive, their management becomes essential to every part of the device. On the other hand, technological advances have moved some of what was embedded development solidly into the applications arena; witness smart phones in the past few years.

Here's a rule of thumb I came up with back when it seemed necessary to choose between C and one of those other, applications languages for some task: Does the problem statement explicitly mention having to manage your own memory? If not, then you shouldn't be using C, and you probably aren't doing systems programming.

James Iry made a very insightful observation about the nature of the C programming language:

Alan Perlis famously said "a programming language is low level when its programs require attention to the irrelevant." What's relevant depends on the problem and the domain, so a corollary would be that a language that's at too high a level prevents paying attention to some of what is relevant for your needs.

I believe that statement is insightful (and it is the casus belli for this post) because it touches on exactly the key of systems programming. What would it mean to write a memory manager or garbage collector in a language that has garbage collection? How could you use a language for systems programming if you cannot manipulate a device whose control system is mapped into memory at a specific location? Alternatively, why the stinking hell would you write an application in C if you didn't have to do some of those things?

I recently discovered a 2006 paper by Jonathan Shapiro, "Programming Language Challenges in Systems Codes: Why Systems Programmers Still Use C, and What to Do About It", describing the motives for BitC, a systems programming language that integrates advances of the last thirty years of programming language technology. Shapiro provides a very idiosyncratic, but also very accurate description of systems programs:

Systems programs operate in constrained memory.
Systems programs are strongly driven by bulk I/O performance.
Performance matters. (And as a corollary, data representation matters.)
Systems programs retain state. (And as a corollary, user-managed storage is a requirement.)

Shapiro's description of the first ("On a 32-bit [...] machine with [...] 64 gigabyte physical memory, it is extremely difficult to get the per-page book-keeping data structures to fit within a 0.5 gigabyte kernel virtual region."), second ("...the goal is to [perform] zero copies of that data [..., requiring] the creation of pointers that do not point to the beginning of an object [...or objects] multiply aliased in both the virtual and physical maps (e.g. by DMA) [...and sub-objects that] reference the storage of the original."), and third points ("...in the critical paths [...], the addition of only a few cache references — or worse, cache misses — in an inner loop can mean the difference between winning and losing customers") are largely what I mean by "resource management", specifically memory. Shapiro's fourth point is a little less obvious:

The most common pattern in systems programs is event loops. While there is short-lived data within these processing loops, the pattern overall is that there are (relatively) large amounts of state that live for the duration of the event processing cycle. This tends to penalize the performance of automatic storage reclamation strategies. To make matters more interesting, there are caches. These update frequently enough that “old space” techniques may not perform well, but are large enough that scanning them can be quite expensive.

Consider that the event loops he is speaking about may continue for the up-time of the device. My original thought was that implementing memory managers would be problematic in a language that provided automatic memory management; Shapiro is making the point that the presence of automatic memory management may be detrimental.

Oh, and when someone comes up to me and asks one of those "Bob,...?" questions, I always answer the same way: "My name's not Bob."

[Edit: Added the link to and paragraphs about Jonathan Shapiro's paper. Thanks to Eli Gottlieb and "The design and implementation of a modern systems programming language" for pointing it out (and Deca). And my name's still not Bob.]

[1] For example, TCL itself was designed with sole concern for glue capability, which leads to most of the reasons it has lost favor.

[2] TCL's glue capability created Tk, Expect, and AOLserver, but many more, complex, programs were simply written in TCL (likely using Tk) than were built by gluing other components together.

[3] Modulo command line shells such as sh, bash, etc., which are examples of programming languages as user interfaces. Also, the term "scripting" is much more appropriate for these languages. Complex applications in these languages are some of the most disturbing things I have ever seen.

Fun Fact!
	Q.	How can I find the priors for a problem?
	A.	Many commonly used priors are listed in the Handbook of Chemistry and Physics.
	Q.	Where do priors originally come from?
	A.	Never ask that question.
	Q.	Uh huh. Then where do scientists get their priors?
	A.	Priors for scientific problems are established by annual vote of the AAAS. In recent years the vote has become fractious and controversial, with widespread acrimony, factional polarization, and several outright assassinations. This may be a front for infighting within the Bayes Council, or it may be that the disputants have too much spare time. No one is really sure.
	Q.	I see. And where does everyone else get their priors?
	A.	They download their priors from Kazaa.
	Q.	What if the priors I want aren't available on Kazaa?
	A.	There's a small, cluttered antique shop in a back alley of San Francisco's Chinatown. Don't ask about the bronze rat.