Maniagnosis

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 .

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.

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 really "On Understanding Data Abstraction, Revisited", but there's no real 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 atdinner, 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.

Oracle JDBC API changes: things that make me sigh

2011-10-28T21:45:00.000-05:00

For reasons that escape me at the moment (something about support from Oracle, I think), we are having to upgrade the Oracle JDBC driver from 10.2.0.4 to 11.2.0.3. Ideally, this would be a simple, transparent change. But it isn't.

A co-worker quickly found an issue with the driver's handling of java.sql.Date and java.sql.Timestamp. Specifically, the previous driver would map SQL DATE columns to java.sql.Date, while the current driver maps SQL DATE columns to java.sql.Timestamp. The details are described by the Oracle JDBC faq, What is going on with DATE and TIMESTAMP? (Note: that entry describes the previous, 10.2.0.4 behavior as the "problem".)

The bottom line is that if you use resultSet.getObject(i) then for a DATE column you will now get a java.sql.Timestamp object where you would previously get a java.sql.Date object. Also, if you use code like


      switch (metaData.getColumnType(i))
      {
      case Types.DATE:
        map.put(name, resultSet.getDate(i));
        break;
      case Types.TIMESTAMP:
        map.put(name, resultSet.getTimestamp(i));
        break;
      ...

You will also get a java.sql.Timestamp instead of a java.sql.date, since the java.sql.Types mapping has changed as well.

Now, I don't know whether or not this is the Right Thing To Do. I don't actually care either way. But the change, even to fix a problem, just makes me want to sob quietly.

And the Java standard library's API is just as wacky as ever.

Why I usually prefer the GPL

2011-10-24T23:46:00.000-05:00

[I was busy this weekend with Peter Norvig and Sebastian Thrun's AI course and Bayesian probabilities, so I am reduced to recycling reddit replies. But it is a topic I've been meaning to mention, so I do not feel too bad.]

Why does the license determine contributions?

Once upon a time, there was an operating system that I'll call BSD UNIX. This OS was distributed under a very permissive license that basically allowed anyone do to anything they wanted with it, including redistributing it as a closed-source product. Which they did, creating a host of different, but somewhat similar operating systems, which I'll call AIX, HP-UX, SunOS, and IRIX (and a large stack of others, but those'll do for now). Each of these OS's grew lots of new features; bugs were fixed, changes were made, markets were differentiated, everyone was happy.

Until everyone noticed that software that ran on one of the pile didn't run on the others, leading to the creation of wonderful things like POSIX, imake, and autoconf. But that was a little bit too late and a little bit too little (and quite a bit too flaky), leading many people to the conclusion that all of these similar operating systems were a bizarrely painful sewer that they wanted nothing to do with. Market differentiation became market fragmentation, almost leading to the death of Unix operating systems.

In the mean time, the greatest developers in the world were working on BSD. Or so they thought, apparently, given that the license they had chosen didn't even have a strong suggestion that any changes that someone else made should be passed back to BSD. (Sure, if they weren't the best, they might want contributions, but since they were, obviously they could do a better job of new features and bug fixes, right?)

So, one day a young programmer comes along trying to decide if he wants to check out this new Linux thing or if he should spend some time with the newly un-encumbered BSD, which was a real Unix and obviously closely related to the OS's he was familiar with. Unfortunately, the new upstart supported shared libraries and FreeBSD didn't, because all of the descendant operating systems which did, did it in completely different ways and no one ever saw fit to contribute it back to the ancestor.

[All characters and operating systems appearing in this work are fictitious. Any resemblance to real persons or operating systems, living or dead, running or panicked, is purely coincidental.]

Quote o' the Day: Appel fanbois

2011-10-18T12:57:00.000-05:00

Yes, I know it's three years old at this point, but I had to link to it:

Yeah, I agree with you. I've had it with all these Appel fanbois.

It's from a discussion about simplified introductions to compiler construction that included a recommendation for Andrew Appel's Modern Compiler Design in Java. Thank you, officemonkey.

And there's a comment for anyone interested in the history of Go.

Quote o' the day: Dennis Ritchie

2011-10-14T16:04:00.000-05:00

From net.unix-wizards:

I am not now, nor have I ever been, a member of the demigodic party.

From Odd Comments and Strange Doings in Unix:

"values of β will give rise to dom!"

 /*
  * If the new process paused because it was
  * swapped out, set the stack level to the last call
  * to savu(u_ssav).  This means that the return
  * which is executed immediately after the call to aretu
  * actually returns from the last routine which did
  * the savu.
  *
  * You are not expected to understand this.
  */

"A substory: at some point several were sitting around working away. Bob Morris asked, almost conversationally, 'what are the arguments to ld?' Someone told him. We continued typing for the next minute, as a thought began to percolate, not quite to the top of the brain-- in other words, not quite fast enough. The terminal stopped echoing before anyone could stop and say 'Hold on Bob, what is it you're trying to do?'"

Link o' the Day: Everyone's first quantum program

2011-10-07T14:06:00.001-05:00

From the reddit thread on QML -- a functional quantum programming language, by erg0S4m:

And the first program to be written has to be
"Hello Worlds!"

Some notes on A Tour of Go

2011-10-05T19:09:00.002-05:00

I have no particular comment about this; my feelings (and the appearance of my eyebrows) should be reasonably obvious to reasonably regular readers.

Inside a function, the := short assignment statement can be used in place of the short var declaration.
(Outside a function, every construct begins with a keyword and the := construct is not available.)

"Outside of a dog, a book is a man's best friend. Inside of a dog, it's too dark to read." -- Groucho Marx.

Oddly, according to 20, the predicate of an if statement is not an expression:

The if statement looks as it does in C or Java, except that the ( ) are gone (they are not even optional)....

Or so I assume, because in most languages, expr is equivalent to (expr); the extra parentheses do nothing, but don't hurt anything either.

What the...?!

Like for, the if statement can start with a short statement to execute before the condition.
if v := math.Pow(x, n); v < lim {
 return v
 }

In case I seem excessively negative, they have fixed one of C's major shortcomings: The basic types specify their sizes.

Go's basic types areboolstringint int8 int16 int32 int64uint uint8 uint16 uint32 uint64 uintptrfloat32 float64complex64 complex128

The syntax for map types is...odd.

var m map[string]Vertex

Functions...

are full closures.The adder function returns a closure. Each closure is bound to its own sum variable.

For those of you misusing the term "closure", please stop. A closure is a implementation technique for lexically scoped functions, not a feature in itself.

Switch statements:

A case body breaks automatically, unless it ends with a fallthrough statement.

Cry "Havoc!" and let slip the dogs of the inverse of the "break" war! Probably is a better default, though.

today := time.LocalTime().Weekday
 switch time.Saturday {
 case today+0:
  fmt.Println("Today.")
 case today+1:
  fmt.Println("Tomorrow.")
 case today+2:
  fmt.Println("In two days.")
 default:
  fmt.Println("Too far away.")
 }

today is an int (2 is Wednesday); time.Saturday is the int representing Saturday (6). The switch expression and the chosen case expression should match.

switch {
 case t.Hour < 12:
     fmt.Println("Good morning!")
 case t.Hour < 17:
     fmt.Println("Good afternoon.")
 default:
     fmt.Println("Good evening.")
 }

Switch without a condition is the same as switch true.

Unless the switch expression is missing, in which case the switch is equivalent to chained if statements.

Cooperative threads?

package main

import (
 "fmt"
// "runtime"
)

func say(s string) {
 for i := 0; i < 5; i++ {
//  runtime.Gosched()
  fmt.Println(s)
 }
}

func main() {
 go say("world")
 say("hello")
}

yields

hello
hello
hello
hello
hello

Go language shows the influence of Plan 9, which I suspect means a definite case of not-invented-here syndrome; it also seems to have a lot of local optimizations, choices that make sense for a particular case. Perl is another major language fond of local optimizations inflated to major features. I'm still not seeing a good reason to focus on Go rather than some of the alternatives. Your mileage may vary.

IEEE Smart Tech Metro Area Workshops: Huntsville

2011-09-22T12:07:00.000-05:00

The two-day IEEE travelling Metro Area Workshop Series called IEEE Smart Tech is coming to Huntsville in November, the 4th and 5th. It looks like a pretty good deal: $99 for IEEE members, $179 for non-members (with a $20 discount for early registration) gets you breakfast and lunch both days, a Friday evening reception with hors d'oeuvres, plenary speakers (in Huntsville, Michael Griffen, former NASA Administrator), and two days of instruction at the scenic Von Braun Center. Oh, and two day-long courses in

Wireless Communications Engineering: Current Practice,
Introduction to Smart Grid, and
Software Engineering Essentials.

On Saturday, you can also attend a career assistance workshop.

I'll be going to the Software Engineering Essentials presentation; while I may not care much for Software Engineering as a field in itself, I do believe software engineering techniques are a wee-bit useful when programming professionally. I'm torn between Introduction to Smart Grid, which just sounds like fun, and Wireless Communications Engineering, which is somewhat close to my network-protocol-ish heart.

If you are in the Huntsville area around November 4th and 5th, or in Austin around October 21st, check it out.

Changes over at www.crsr.net: nginx

2011-09-02T14:32:00.002-05:00

I recently read 9 million hits/day with 120 megs RAM, in which Alex Micek benchmarked his small website with blitz.io and made some significant improvements to his performance. blitz.io is very easy to use, so I pointed it at www.crsr.net and let 'er rip, with very disappointing results. www.crsr.net is a very simple, static file site that is (er, was) served by Apache, and according to blitz.io I was taking approximately 300ms to serve a request. Ick.

A while back, I looked at nginx, the allegedly faster web server, and considered replacing Apache with it. But I was lazy and didn't figure that nginx would really help much. Now, though, I had some incentive. I set up nginx on port 8080, pointing at the same www.crsr.net files, and fired off blitz.io again. Nginx took a factor of ten off Apache's results, and the configuration for replacing Apache was trivial.

www.crsr.net is now being served by nginx. Thanks, Igor Sysoev! And thanks, blitz.io!

Link o' the Day: Markets are Efficient If and Only If P = NP

2011-08-24T00:18:00.003-05:00

This one from Jeff: a pointer to If computer scientists are right, you can make money on the market. If economists are right, you can compute fast, which is a reference to a paper to appear in Algorithmic Finance by Philip Z. Maymin, Markets are Efficient If and Only If P = NP.

Economics and computer science have some things in common; they are the only two fields I know where exponential growth is a common situation, for one thing. Now, speaking as an innocent economic bystander, I have been convinced by the arguments in favor of the weak efficient market hypothesis, that "that future prices cannot be predicted by analyzing prices from the past" (my emphasis), but significantly unconvinced by any of the arguments for any of the stronger forms, specifically the semi-strong (that the current price incorporates all publicly available information) and the strong form (that the current price incorporates all private information). I am also a computer scientist, falling into the "I believe P is not equivalent to NP" camp.

This paper seems to argue that even the weak form is untenable, because the complexity of identifying an exploitable-inefficiency in the stream of market data requires exponential resources (while verifying an inefficiency requires only polynomial resources). As Anders Sandberg says, "In any case, it seems that the paper shows that computational complexity makes markets complex."

I am not sure I buy the complete argument, particularly the second half, where Maymin attempts to encode the SAT-3 problem in market orders, but the paper does have an interesting perspective. Maybe those head-n-boulders charts are good for something.

How the Internet Architecture Got its Hourglass Shape

2011-08-19T21:10:00.001-05:00

And in other news, Constantine Dovrolis and Saamer Akhshabi at the School of Computer Science at the Georgia Institute of Technology "created an evolutionary model called EvoArch to study the emergence of the Internet’s hourglass structure," as described by Staying in Shape: How the Internet Architecture Got its Hourglass Shape and What That Means for Future Internet Architectures.

In the model, the architecture of the network changed with time as new protocols were created at different layers and existing protocols were removed as a result of competition with other protocols in the same layer.

Unfortunately, I am too busy to appreciate the success of the work, wondering if anyone explained to them that the hourglass shape of the internet architecture was a deliberate design choice.

The authors of the GIT press release wrote that,

to ensure more diversity in the middle layers, EvoArch suggests designing protocols that are largely non-overlapping in terms of services and functionality so that they do not compete with each other.

I wonder exact kind of diversity and non-overlapping services they have in mind, considering the IP layer essentially provides universal connectivity.

The Tappan Zee Bridge and software development

2011-08-19T18:42:00.001-05:00

A recent Planet Money podcast discussed the Tappan Zee Bridge and the perplexing issue of its location. The Tappan Zee is located at one of the widest points on the Hudson river, and as a result after only a half-century or so is needing some significant replacement. If it were a few miles south, the river would be much narrower and the structure would be more sound.

The bridge was built as part of the New York Thruway, one of the first controlled-access highways in the country, a grand scheme of then-governor Thomas Dewey. In order to build the rest of the Thruway, Dewey needed the revenue from the tolls on the bridge, and placing the bridge in a better location further south would have meant it was in the domain of the New York Port Authority, which has a monopoly on bridges, tunnels, and what-not within 25 miles of the Statue of Liberty. As a result, the Port Authority would have gotten the toll income, not the State of New York. So, the Tappan Zee is about twenty-five and a half miles from Liberty Island, is three and a half miles long, and is in need of repairs. But the Thruway exists, and seems to function admirably. (Or as much so as such can.)

I am moved to this posting by the realization that many enterprise applications (since I am currently stuck in enterprise-land) are similarly constrained by the perversities of their environments. The best technical or engineering options are ruled out on seemingly irrational reasons, simply because there is no other way to get the damn thing built. And getting the working application is more important than the subsequent pains involved in a below-best-standards mechanism.

This sad fact is not limited to just the enterprise, though. Many of the failed projects I have been involved with were similarly constrained by non-technical decisions; in some cases, those were not even the reason the project failed.

Next time, how H.P. Lovecraft's classic "The Shadow over Innsmouth" applies to modern software development.

User space file system comments

2011-07-09T11:34:00.004-05:00

This is a comment I made on the Gluster blog, about a post on one of Linus Torvalds' incendiary comments on user-space filesystems.

Way back in the dim mists of time, when microkernels were hot, Linus was having flame wars with AT, and the HURD actually sounded like it might someday be usable, I worked on the IBM microkernel project writing filesystem benchmarks. The idea was to build OS/2 (!), AIX, and other OS personalities on top of Mach, as multiple user-space servers.

There were a lot of things wrong with the implementation (getpid() required a trip through Mach to an OS server), but the one thing that was a continual problem was filesystem performance. At one point, reading a page off disk was CPU bound. The issue wasn’t context switches, really, which can themselves be made arbitrarily fast, but carrying pages of data along with the context switch. The original copy-on-write turned out to be a pessimization—a very-well-written memcpy took a little less time to copy a page than the vm system took to set up the page share and copy-on-write. Then, if you eventually had to copy the page….

I never figured out what was going on with the virtual memory system, but I’ve seen the same issue over and over. The MkLinux paper at the (1st and only, AFAIK) FSF conference is one of my favorite performance papers ever. The table showing performance comparisons looks good, as long as you didn’t notice that the top third was dhrystones; MkLinux didn’t actually slow the processor down. The Scout OS, a good research uK OS reported excellent performance, but didn’t separate user-space processes into different memory domains. The numbers reported by the security-enhanced follow-on, whose name I can’t remember but which did use multiple memory domains, was much worse. If you read between the lines of that paper comparing it to Linux, it would still have been a small multiple slower than Linux if it only used 2 protection domains instead of 3 for filesystem accesses.

I’m as big a fan of user-level filesystems as anyone. They provide a neat and protected way of doing things that would otherwise not be as clean. On the other hand, to say “user space advantages far outweigh kernel space advantages” as a general rule is a pretty thoroughly blinkered view, too.

Oh, and if you want the references to the MkLinux, Scout, and whatever-that-other-one-was papers, I’ll try to round them up.

Snakes! On a Yeti!

2011-07-04T19:09:00.003-05:00

Continuing on my Lisp kick, I have been reading Programming Clojure, by Stuart Halloway. But that fact is a red herring for the moment; I have also been looking at a language called Yeti. In order to take a pass at Yeti, I was casually trying to find a good sample program, which I finally found in Programming Clojure: the Snake game from section 6.6.

Yeti is a ML-style programming language for the JVM, featuring Hindley-Milner type inference with structurally-typed records and open variant types similar to O'Caml. It also provides reasonable access to Java and compiles to JVM bytecode. Yeti is similar to Scala, and andrewcooke posted what I believe is a good comparison on Hacker News; the key point is, "scala is baroque; yeti minimal."

As described by Halloway, "The snake game features a player-controlled snake that moves around a game grid hunting for an apple. When your snake eats an apple, it grows longer by a segment, and a new apple appears. If your snake reaches a certain length, you win. But if your snake crosses over its own body, you lose." The implementation is simple Swing and Halloway lists a number of other implementations for comparison:

Typed Scheme
Small and readable Java
Tiny Clojure
Partially verified in ACL2
Readable Clojure

Bear in mind that this is literally my second Yeti program, following hello-world. I have fiddled with ML a bit and O'Caml a lot (for a while, it was my official favorite programming language). I have also done rather a lot of Java lately, but only a small amount of Swing. Comments and suggestions are more than welcome.

Given that, this is my version of Snake, snake.yeti.

import java.util.Random;
import java.awt: Color, Dimension, Graphics;
import java.awt.event: ActionEvent, KeyEvent, ActionListener, KeyListener;
import javax.swing: JFrame, JPanel, JOptionPane, Timer;

The program begins with a stack of imports, for the Java classes needed later. Each class can be imported separately or multiple classes from the same package can be listed together.

A functional model

width = 75;
height = 50;
pointSize = 10;
turnMillis = 75;
winLength = 5;
dirs =
  [ KeyEvent#VK_LEFT :  {x = -1, y = 0},
    KeyEvent#VK_RIGHT : {x = 1,  y = 0},
    KeyEvent#VK_UP :    {x = 0,  y = -1},
    KeyEvent#VK_DOWN :  {x = 0,  y = 1} ];

These variables (in the mathematical sense) describe the width and height of the game grid, the conversion factor between the grid and pixels, the length of a game time step in milliseconds, and the number of segments required to win. (5 is a "boringly small number suitable for testing.") dirs is a map from numbers, given by static constants in the Java class KeyEvent, to points, as represented by a record or structure with x and y fields. dirs will be used to map key press events to changes in direction for the snake.

Using the Yeti REPL, I captured Yeti's inference of dirs' type:

dirs is hash<number, {`x is number, `y is number}> = [38:{x=0, y=-1},...elided...]

Similar to Java's Map<K,V>, dirs is a map from number (Yeti's only numeric type, as far as I know), representing the key event values, to structurally-typed x,y pairs where each field is also a number.

Because any key event will wind up looking in dirs, it is convenient to set a default for unrecognized key event values using setHashDefault. The first argument to setHashDefault is the map to be updated, while the second is an anonymous function (using Yeti's do notation) which ignores the argument (which is the unrecognized key) and always returns a null direction. (This will have the effect of pausing the game, if your snake has not eaten any apples. If your snake has eaten apples, you will lose immediately. But at least it doesn't throw any exceptions. Don't like it? Submit a bug report.)

setHashDefault dirs do _: {x = 0, y = 0} done;

See below for more about functions and do.

When I originally wrote this, I needed a couple of list utility functions, which I knew might be part of the standard library (the only documentation I had was a cached copy of the Yeti tutorial), or better expressed another way. The lists I am working with are the segments of the snake, which will not be terribly long, so I figured it did not matter much.

// butLast lst =
//     if (length lst) <= 1 then [] else (head lst) :: (butLast (tail lst)) fi;

// member? v lst =
//     if empty? lst then false
//     elif v == (head lst) then true
//     else member? v (tail lst)
//     fi;

butLast copies a list, excluding the last element. member? (and yes, Yeti allows the question mark in function names) tests whether the value v is an element of the list. Both written written using basic recursion, although Yeti is reputed to support better tail call optimization than Scala. Also, at the time, I could not figure out how to do pattern-matching destructuring on lists; instead, I used head, tail, length, and empty?.

Fortunately, Madis pointed out

that the standard library does contain member?, known as "contains", and
that Yeti does do pattern-matching destructuring on lists, very cleanly.

butLast lst = case lst of
    [_] : [];
    h :: t : h :: butLast t;
    _ : [];
    esac;

The underscore '_' is an anonymous variable; a placeholder that requires a value in the destructuring, but which cannot be referenced later. In the first case the underscore indicates that the lst should have exactly one element; the third that anything is acceptable. See below for more on case and destructuring.

The basic form of a function definition in Yeti is

var = do args... : expressions... done

Since the form of the bare lambda expression in Yeti is

do args... : expressions... done

the basic form is just assigning a function expression to a variable. However, because function definitions are fairly common in Yeti code, there is a shorthand syntax illustrated by butLast:

fcn args... = expressions...

Another simple function is addPoints, which adds two x,y points together, producing another point.

addPoints m n = {x = m.x + n.x, y = m.y + n.y};

The type of addPoints is

addPoints is {.x is number, .y is number}
 -> {.x is number, .y is number}
 -> {x is number, y is number} = <snake$addPoints>

The type indicates that addPoints takes two structures containing (at least) numeric fields x and y and returns another structure with fields x and y. Because Yeti uses structural typing, the structure representing points is actually anonymous; any structure containing suitable x and y fields could be added by addPoints.

Because Yeti supports the ML-style definition of new operators, addPoints could have been written as

// (.+.) m n = {x = m.x + n.x, y = m.y + n.y};

The resulting operator could be used like:

> {x=4,y=3} .+. {x=1,y=1}
{x=5, y=4} is {x is number, y is number}

I chose instead to remain consistent with Halloway's code.

pointToScreenRec converts a game board point to a rectangle in screen coordinates for the display functions.

pointToScreenRec pt =
  { x = (pt.x * pointSize),
    y = (pt.y * pointSize),
    w = pointSize,
    h = pointSize };

Once again, this function just builds and returns a new structure, with x, y, width, and height fields. The fields in the argument are accessed pretty traditionally, by a period followed by the field name.

Yet another pseudo-constant is the random number generator used to place apples on the game board.

r = new Random();

r's value will be an instance of java.util.Random, illustrating some of Yeti's Java integration.

The next two functions create apples and snakes, both of which are also structures.

createApple () =
   { location = {x = r#nextInt(width), y = r#nextInt(height)},
     color = new Color(210,50,90) };

createSnake () =
  { body = [{x = 1, y = 1}],
    dir = {x = 1, y = 0},
    color = new Color(15,160,70) };

Both also illustrate Java integration: the location of the apple is set randomly, by calling the nextInt(n) method. '#' replaces '.' in this use for Yeti. As well, the color of both apples and snakes is defined using java.awt.Color.

createApple and createSnake take the special Yeti 'unit', (), as an argument. If they were defined without taking something as an argument, they would be evaluated immediately as variables. The unit argument allows them to be defined as functions while simultaneously indicating that they do not take any interesting arguments. () indicates both a type and the single, uninteresting value of that type.

The function turn is simply used to replace the direction the snake is traveling. Originally, I wrote it as:

// turn snake newdir =
//   { dir = newdir,
//     body = snake.body,
//     color = snake.color };

Madis also pointed out that Yeti

has a with syntax to create a new structure based on an existing one, and
has a shortcut for associating variables and fields within a structure.

As a result, turn is:

turn snake dir = snake with {dir};

The value of turn is a copy of the structure snake, with modifications. The form "{dir}" is equivalent to "dir = dir", meaning that the dir field in the new structure is given the value of the dir parameter.

On the other hand, move is slightly more complex.

move snake grow =
  ( newhead = addPoints (head snake.body) snake.dir;
    newbody = if grow then snake.body else (butLast snake.body) fi;
    snake with {body = newhead :: newbody} );

newhead is computed to be the location of the snake's head plus the current direction. newbody is the either current body of the snake (if the snake is growing a new segment) or the current body without the terminal segment---if the snake is growing, it does so by extending at the head; if the snake is simply moving, a new head segment is added at one end while a tail segment is removed.

Since the move function uses two local variables, newhead and newbody, and thus multiple expressions, the expressions in the function's body are enclosed in parentheses.

This part of the program completes with a number of predicates used to determine if the player has won, lost, or if the snake can eat an apple.

win? snake = length (snake.body) >= winLength;

headOverlapsBody? body = member? (head body) (tail body);

lose? snake = headOverlapsBody? snake.body;

eats? snake apple = (head snake.body) == apple.location;

Mutable state

The state of the game is kept in two mutable variables, snake and apple.

var snake = createSnake ();
var apple = createApple ();

The addition of the 'var' to the definition allows the two variables to be modified by assignment.

There are three functions which update the state of the game.

resetGame () =
  ( snake := createSnake ();
    apple := createApple () );

updateDirection newdir = snake := turn snake newdir;

updatePositions () =
    if eats? snake apple
    then apple := createApple ();
         snake := move snake true;
    else snake := move snake false
    fi;

resetGame returns the game to something like it's initial state (remember, apple placement is random). updateDirection is a simple wrapper for turn, replacing the value of snake with a new snake traveling in the new direction. Finally, updatePositions tests whether the snake and apple are co-located; if they are, a new apple is created and the snake moves and grows a new segment; if they are not, the snake simply moves.

resetGame and updatePositions also take the Yeti unit value to prevent the expression from being evaluated immediately. All three functions return unit:


resetGame is () -> () = <snake$resetGame>
updateDirection is {`x is number, `y is number} -> () = <snake$updateDirection>
updatePositions is () -> () = <snake$updatePositions>

Since () indicates both a type and the single value of that type, these typings indicate that these three functions do not return a useful value; any effect they have must be done via side effects, in this case by updating variables.

GUI

In comparison with the mutable state, the GUI is a bit more complex and fancy, due to its integration with Java Swing.

My first step is to define a type name, point, for the structure containing fields x and y.

typedef point = { x is number, y is number };

The reason I did it is the next function, fillPoint.

fillPoint g pt c is ~Graphics -> point -> ~Color -> () =
   ( {x,y,w,h} = pointToScreenRec pt;
     g#setColor(c);
     g#fillRect(x,y,w,h) );

fillPoint is the first function I have used that needs a type specification. It takes an argument, g, which is a Graphics context (marked with a '~' to indicate it is a raw Java class instead of a Yeti type), a point structure, and a Java Color. This function needs the type declaration because Yeti's type inference is unable to do anything with g, since the only thing I do is call the methods setColor and fillRect. fillPoint is also the first function in which I have used a destructuring bind, which picks apart the structure returned by pointToScreenRec into variables x, y, w, and h. These variables are then used to provide the necessary arguments to Graphics#fillRect. That statement also makes use of the "{x}" == "{x=x}" equivalence shortcut.

I used the point type definition to clean up the fillPoint type declaration. Because it acts as a simple alias, the type of fillPoint reported by the REPL is

fillPoint is ~java.awt.Graphics -> {`x is number, `y is number} -> ~java.awt.Color -> () = <snake$fillPoint>

Next, I have a bug. I left it in the code because it is instructive.

paintApple g a = fillPoint g apple.location apple.color;

paintApple draws an apple using fillPoint, but it should take graphics context and the apple as an argument. Instead, it is using the apple variable. I noticed the type of paintApple is

paintApple is ~java.awt.Graphics -> 'a -> () = <snake$paintApple>

The interesting part is the 'a; that is a raw type variable. Type variables appear with parametric polymorphism, as in Java's List<t> or the equivalent Yeti's list<'a>. However, in this case it indicates something seriously wrong with paintApple since a type variable can take any type. Specifially in this code, it means that the parameter a is never used.

paintSnake does not have the bug.

paintSnake g s =
    for s.body do segment: fillPoint g segment s.color done;

Its type is

paintSnake is ~java.awt.Graphics
 -> {.body is list?<{`x is number, `y is number}>, .color is ~java.awt.Color}
 -> () = <snake$paintSnake>

paintSnake also shows a for loop, the use of the function for to iterate through the segments of the snake, calling the anonymous function do...done to draw each segment.

At this point things get a little hairy. To display the game board and interact with the player, I need to create a subclass of JPanel and an implementation of ActionListener and KeyListener. That is, I need GamePanel.

class GamePanel(JFrame frame) extends JPanel, ActionListener, KeyListener
    void paintComponent(Graphics g)
        super#paintComponent(g);
        g#clearRect(0,0,(width+1) * pointSize,(height+1)*pointSize);
        paintSnake g snake;
        paintApple g apple,

    void actionPerformed(ActionEvent e)
        updatePositions ();
        if lose? snake
        then resetGame();
             JOptionPane#showMessageDialog(frame,"You lose!")
        elif win? snake
        then resetGame();
             JOptionPane#showMessageDialog(frame,"You win!")
        fi;
        this#repaint(),

    void keyPressed(KeyEvent e)
        updateDirection dirs.[e#getKeyCode()],

    Dimension getPreferredSize()
        new Dimension((width + 1) * pointSize,
                      (height + 1) * pointSize),

    void keyReleased(KeyEvent e),

    void keyTyped(KeyEvent e)
end;

GamePanel is a Java class defined in Yeti code. The methods it implements are paintComponent (JPanel), actionPerformed (ActionListener), keyPressed (KeyListener), getPreferredSize (JPanel), keyReleased (KeyListener), and keyTyped (KeyListener).

paintComponent clears the game board's window and draws the snake and the apple. It also shows how to make a call to a superclass' method, the call to the superclass' paintComponent.

actionPerformed is called based on a timer; it updates positions and tests whether the win or loss conditions are satisfied and completes by updating the game board.

keyPressed is used to change the direction of the snake, based on arrow-key input. getPreferredSize returns a Dimension containing the on-screen size of the game board. keyReleased and keyTyped are ignored and do nothing.

An instance of GamePanel is created using the gamePanel function, which accepts a JFrame as the constructor argument.

gamePanel frame = new GamePanel(frame);

Like Scala, Yeti uses an implicit constructor scheme, where the arguments to the constructor are stored as members of the instance. Unlike Scala, bizarre do-what-I-mean semantics do not seem to be involved.

Finally, the game function itself is relatively simple imperative code:

game () =
  ( frame = new JFrame("Snake");
    panel = gamePanel frame;
    timer = new Timer(turnMillis,panel);
    panel#setFocusable(true);
    panel#addKeyListener(panel);
    frame#add(panel);
    frame#pack();
    frame#setVisible(true);
    timer#start() );

Endgame

To play the game, fire up the Yeti REPL, load the module, and invoke game:

$ java -jar yeti.jar
Yeti REPL.

> load snake
...elided...
> game ()

Miscellanea

The remaining part of Yeti which I explored, but did not ultimately use in the snake game, is open variant types. To use these, the record returned by createApple could be tagged with 'Apple':

// createApple () = Apple {
//              location = {x = r#nextInt(width),
//                          y = r#nextInt(height)},
//              color = new Color(210,50,90),
//              };

Using that, I could define a single function, paint, to replace paintApple and paintSnake:

// paint g object =
//     case object of
//         Snake s : for s.body do segment: fillPoint g segment s.color done;
//         Apple a : fillPoint g a.location a.color;
//     esac;

The type of paint is:

paint is
    ~java.awt.Graphics
 ->   Apple {.color is ~java.awt.Color, .location is {`x is number, `y is number}}
    | Snake {.body is list?<{`x is number, `y is number}>, .color is ~java.awt.Color}
 -> () = <snake$paint>

The second argument of paint is either an appropriate structure tagged with Apple or an appropriate structure tagged with Snake; the tag determines which branch is expected.

Conclusion

I like Yeti. It seems a pretty nice representative of the ML family on the JVM. The integration with Java seems to be a little clunky, but not irritatingly so.

Madis made several excellent suggestions about this posting (and code changes to yeti). Thanks!

Quote o' the day: Interpretive dance as a user interface

2011-07-01T10:27:00.000-05:00

From a reddit discussion of Netflix user interfaces,

netflix, on Xbox, could use a lot of work.... -- theDrWho
I think the input device is the major limiting factor there. -- recursive
The Kinect should solve that problem. Of course, you might have to take a few classes in jazz dancing to use the UI. -- jadero

Link o' the day: Greatest xkcd ever!

2011-06-22T04:54:00.002-05:00

Forget the map of Internet users scaled by bandwidth-donut consumption product. This is it:

Some Lisp suggestions

2011-06-17T22:53:00.003-05:00

I am most definitely not a Lisp guru, but after finishing Land of Lisp, I have a couple of suggestions that might reduce the general imperviousness of Lisp code. In my opinion, most of the antipathy towards Lisp's parentheses is a red herring; those parentheses merely express the structure of the code---which is present but implicit in any code---while the actual problem is that the code is bad, a problem which is exacerbated by the explicit structure.

defstruct is your friend! Use it!

Allegedly, J.B.S. Haldane once described what a lifetime of biology had taught him about God as "an inordinate fondness for beetles". One thing that frequently bothers me about code in untyped languages in general, but specifically in Lisp, is an excessive focus on representations of data, rather than the structure of data. Rather than identifying and building on an abstract data structure, the programmer will simply put the components of data into a hash table or a list and access the components using raw hash or list functions.

For example, this is a function for Land of Lisp; below I rewrote the function using defstruct to reify the game tree (tree-node) and moves (attacking-move and passing-move). I also slapped some color on the two functions to emphasize the corresponding functions.

(defun limit-tree-depth (tree depth)
  (list (car tree) 
        (cadr tree) 
        (if (zerop depth)
            (lazy-nil)
            (lazy-mapcar (lambda (move)
                            (list (car move) 
                                  (limit-tree-depth (cadr move) (1- depth))))
                         (caddr tree)))))


(defun limit-tree-depth (tree depth)
  (labels ((limit-depth-move (move)
             (let* ((next-tree (limit-tree-depth (get-tree move) (1- depth))))
               (if (passing-move-p move)
                   (make-passing-move :tree next-tree)
                   (make-attacking-move :src (attacking-move-src move)
                                        :dst (attacking-move-dst move)
                                        :tree next-tree)))))
    (make-tree-node :player (tree-node-player tree)
                    :board (tree-node-board tree)
                    :moves (if (zerop depth)
                               (lazy-nil)
                               (lazy-mapcar #'limit-depth-move
                                            (tree-node-moves tree))))))

Now, the first function is markedly shorter than the second (although part of that is my apparent fondness for large names). However, unless you are fond of remembering that the car of one kind of list identifies a player in a node of the game tree, while the list of subsequent moves is the caddr, and the car of another kind of list identifies the aggressor and defender of a move (and implicitly whether it is an attacking move or a passing move), I respectfully suggest that the second might be preferable. In fact, a significant chunk of the length difference is that I have used different structures for the passing move (which only has the subsequent game tree node) and the attacking move (which also has the attacking and defending board positions).

Abstraction is good, too.

There are those in the functional programming community who identify function with abstraction. If I understand them correctly, they use the two words interchangeably. I believe that is a very grave mistake, since it would mean that the lambda expression in the first example is, in some sense, the same as the use of the limit-depth-move function. As for me, if I had to identify abstraction with a single technique, I would link it to naming; to my mind, the first lambda expression is an implementation detail that clutters up the building of the moves of the new game tree node, while the second version (as hideous as the labels construct is) provides the function as an identifiable, named, meaningful chunk.

If you compare typical Lisp code with typical code in a language from the ML family, I think you'll find that Lisp code has more functions built of multiple steps, and greater nesting, than the ML code; ML code will more likely use let or where to break out identifiable functions and values. As a result, in my opinion, the ML code is consistently easier to read.

After some further thought, I suspect the emphasis on representations is a result of working top-down to design the program. Further, I am almost positive that the more complex code and lack of abstraction are also a symptom of the same approach. Top-down design tends to be fine down to a certain level, at which point the code appears "simple enough". Further work, however, makes the code more complex but without redesigning the existing structure. A bottom-up approach almost calls for the identification of abstractions for working with the next level of code. (On the other hand, a bottom-up approach usually requires more work, since it involves traveling towards a destination without being sure of the best direction. Also, it can suffer from the same problem at the other end of the program, where the higher structure of the code seems simple enough until it needs elaboration to complete the solution.)

I do not want to pick on Land of Lisp unfairly. It is a very good, and entertaining, book. The code examples are, overall, very clean and nice. However, reading it reminded me of the difficulties I have had with other Lisp (and other dynamically-typed code) in the past.

[Edit: Typo and second-to-last paragraph fixed due to comments from reddit. Thanks!]

Link o' the Day: protolol

2011-06-10T11:35:00.001-05:00

“There. There is. There is nothing. There is nothing funny about path MTU detection.”
— protolol

Courtesy of Corey.

Shell scripting fun: pdfsplit

2011-06-07T16:38:00.000-05:00

Like various other people, I have been irritated by the problems with viewing two-column PDF files on a Kindle. Yesterday, however, I ran across pdfsplit, which made me decide to do something about it.

I downloaded the package, which is Cabal-ized Haskell (!), and like my other adventures with Cabal, it failed to build. Naturally, I took a peek at the code, and found it to be a very simple script that used some libraries I apparently don't have (or have and don't know it; or something).

I like writing Haskell as much as anyone, but sometimes the right tool really is a hammer. In that spirit, here is a Bourne shell script:

#!/bin/sh
#
# pdfsplit - create a single-column version of a 2-column PDF file

if [ $# -lt 1 ]
then
  echo "Usage: $0 file.pdf ..."
  echo "  Produces file-split.pdf ..."
  exit 1
fi

for input in "$@"
do

  base=`basename $input .pdf`
  tmp=$base-split.tex
  pages=`pdfinfo $input | grep Pages | awk '{print $2}'`

  cat <<eof >$tmp
\\documentclass{article}
\\usepackage[paperwidth=4.25in,paperheight=11in]{geometry}
\\usepackage{pdfpages}
\\begin{document}
eof

  n=1
  while [ $n -le $pages ]
  do

    cat <<eof >>$tmp
\\includepdf[pages=$n,noautoscale,offset=2.125in 0]{$input}
\\includepdf[pages=$n,noautoscale,offset=-2.125in 0]{$input}
eof

    n=$((n+1))
  done

  cat <<eof >>$tmp
\\end{document}
eof

  pdflatex $tmp

  rm -f $tmp $base-split.aux $base-split.log

done

To use it, you will need pdflatex, the pdfpages package, and pdfinfo (from the poppler-utils package on my Ubuntu laptop).

When Domain Specific Languages Attack!

2011-06-04T22:41:00.002-05:00

Or, why I don't particularly like Common Lisp

Once upon a time, many years ago, Common Lisp was my favorite programming language. This was mostly when I was taking upper division classes at UT Austin, and mostly due to the AI faculty in the department, who were excellent teachers. In fact, I recall getting a laugh out of Ham Richards, when he read my answer to one of the questions on the final of the C++ class he was teaching: The question was on C++ operator precedence, and my answer included the comment, "I want my Lisp!"

Anyway, enough about that. I have recently been meandering through Land of Lisp: Learn to Program in Lisp, One Game at a Time!, by Conrad Barski (check out the sample chapter, with the most violent programming example ever put into a textbook). (I've been meaning to learn something about Clojure, and I had nothing better to do.) The book gets a big thumbs up. It is entertaining, the cartoons (especially those that go with the evolution simulation) are perfect, the games bring back a surprising number of memories, and I'm picking back up my Lisp. Fortunately or unfortunately, Barski uses Common Lisp, which is also bringing back some less pleasant memories.

What happens when an embedded domain-specific language escapes into the general language in which it is embedded? The DSL probably doesn't fit in with the general language, stylistically, syntactically, or semantically, and the result may not be very pretty.

One example that is less problematic involves parsing combinators; for one thing, parsers are usually isolated from the remainder of the program due to modularity concerns; for another, a parser isn't generally driving the remainder of the program.

On the other hand, Common Lisp has three more problematic DSLs:

The setf accessor sublanguage,
the loop sublanguage, and
the format sublanguage.

The first of these is built for the generic settor, setf. The first argument to setf is a pattern, identifying a location in a data structure which is to be updated. This pattern can use the ever-present car and cdr, as well as things like structure field accessors. It does not allow all general programs, and I refuse to figure out what parts can be used, what cannot, and why.

The second and the third are the reason for this post. Barski admits loop and format are not pretty in the two chapters dedicated to them, and shows a single-function game in the chapter dedicated to the latter. This game, robots, is a third-person, avoid-the-monsters thing, that I recall as being reasonably entertaining. Without much ado, here's the code:

(defun robots ()
  (loop named main with directions = '((q . -65) (w . -64) (e . -63) (a . -1)
                                       (d . 1) (z . 63) (x . 64) (c . 65))
     for pos = 544
     then (progn (format t "~%qwe/asd/zxc to move, (t)eleport, (l)eave:")
                 (force-output)
                 (let* ((c (read))
                        (d (assoc c directions)))
                   (cond (d (+ pos (cdr d)))
                         ((eq 't c) (random 1024))
                         ((eq 'l c) (return-from main 'bye))
                         (t pos))))
     for monsters = (loop repeat 10 collect (random 1024))
     then (loop for mpos in monsters collect (if (> (count mpos monsters) 1)
                                                 mpos
                                                 (cdar (sort (loop for (k . d) in directions
                                                                for new-mpos = (+ mpos d)
                                                                collect (cons (+ (abs (- (mod new-mpos 64) (mod pos 64)))
                                                                                 (abs (- (ash new-mpos -6) (ash pos -6))))
                                                                              new-mpos))
                                                             '<
                                                             :key #'car))))
     when (loop for mpos in monsters always (> (count mpos monsters) 1))
     return 'player-wins
     do (format t "~%|~{~<|~%|~,65:;~A~>~}|"
                (loop for p below 1024 collect (cond ((member p monsters)
                                                      (cond ((= p pos) (return-from main 'player-loses))
                                                            ((> (count p monsters) 1) #\#)
                                                            (t #\A)))
                                                     ((= p pos) #\@)
                                                     (t #\space))))))

If you can figure out what is going on there, you're a better man than I. Even if you're not a man.

My complaints: loop has absolutely nothing to do with the rest of CL, it has a very baroque interface, and enough features that I feel no urge to analyze or remember them all. format, on the other hand, is just simply loony.

I spent some time unraveling robots, and came up with this, which is more understandable but which still contains the complexity of loop and format:

(defparameter *directions* '((q . -65) (w . -64) (e . -63)
                             (a . -1)            (d . 1)
                             (z . 63)  (x . 64)  (c . 65)))

(defparameter *initial-position* 544)

(defparameter *n-monsters* 10)

(defun initial-monsters () (loop repeat *n-monsters* collect (random 1024)))

(defun read-move ()
  (format t "~%qwe/asd/zxc to move, (t)eleport, (l)eave:")
  (force-output)
  (read))

(defun monster-wrecked (mpos monsters) (> (count mpos monsters) 1))

(defun new-monster-position (pos mpos wrecked)
  (labels ((player-distance (new-mpos) (+ (abs (- (mod new-mpos 64)
                                                  (mod pos 64)))
                                          (abs (- (ash new-mpos -6)
                                                  (ash pos -6))))))
    (let ((possible-moves (loop
                for (k . d) in *directions*
                for new-mpos = (+ mpos d)
                collect (cons (player-distance new-mpos) new-mpos))))
      (if (not wrecked) (cdar (sort possible-moves '< :key #'car)) mpos))))

(defun new-monster-positions (pos monsters)
  (loop for mpos in monsters collect
       (new-monster-position pos mpos (monster-wrecked mpos monsters))))

(defun all-monsters-wrecked (monsters)
  (every (lambda (mpos) (monster-wrecked mpos monsters)) monsters))

(defun board-contents (pos monsters)
  (loop for p below 1024 collect
       (cond ((member p monsters) (if (monster-wrecked p monsters) #\# #\A))
             ((= p pos) #\@)
             (t #\space))))

(defun robots ()
  (loop named main
     for pos = *initial-position* then
       (let* ((c (read-move))
              (d (assoc c *directions*)))
         (cond (d (+ pos (cdr d)))
               ((eq 't c) (random 1024))
               ((eq 'l c) (return-from main 'bye))
               (t pos)))
     for monsters = (initial-monsters) then
       (new-monster-positions pos monsters)
     when (all-monsters-wrecked monsters) return 'player-wins
     when (member pos monsters) return 'player-loses
     do (format t "~%|~{~<|~%|~,65:;~A~>~}|" (board-contents pos monsters))))

Now, bizarro DSLs are not limited to Common Lisp (Olin Shivers, who also wrote scsh and more importantly the acknowledgements in its manual, wrote a paper about a suitably hideous version of loop in Scheme) but Common Lisp is the only example that I know about of several in one place, and of a culture that seems to really enjoy creating them.

Postscript

2000/07/24 Per Bother infects Scheme with a setf-alike.

Quote o' the Day: Software Awesomeness

2011-06-03T11:41:00.000-05:00

Courtesy of reddit, Jesse Emery writes How to keep your software awesome, which has a stack of interesting ideas. A couple:

It also means that your process should never, ever get in the way of someone wanting to make your software better. Do they have to ask permission or get approval to fix a bug? Really? Do they have to justify and sell their idea to you even if they’re willing to work on it in their own time? If the answer to any of these questions is “yes” then your process is working against, rather than for, your software. (Note: if you don’t trust your team at this level than either you shouldn’t have hired them or You Need to Let Go).

Regarding dealing with "technical debt", a piece of code that "is causing a lot of problems – either it’s causing bugs or making it hard to add (one of those that you thought long and hard about) features":

This type of work isn’t sexy for business owners or your sales force, but it still makes your product a lot better. Never lose sight of the fact that responsiveness and stability are every bit as much a part of your user experience as whether you used the glossy or the flat buttons.

Diagonalization and the Continuum Hypothesis

2011-05-27T21:57:00.001-05:00

I have recently been reading Gödel's Theorem: An Incomplete Guide to its Use and Abuse, by Torkel Franzén, which is very good even though Franzén's attempts to explain Gödel's theorems in natural language frequently feel like he is tap-dancing around the theorems themselves; when your explanation of a formal proof is more complex than the proof itself, something is wrong. On the other hand, his discussion the various philosophical (and other) conclusions that have been drawn from Gödel's theorems (and what is wrong with them) is very, very good.

One thing that Franzén mentions that I had not known before is that Cantor's Continuum Hypothesis is one of the most rare things in mathematics: a statement that is undecidable in Zermelo-Fraenkel set theory (with the axiom of choice) and one which is not specifically constructed to be undecidable in ZFC.

Now, my purpose here is not really to talk about the Continuum Hypothesis (a.k.a. CH), nor about incompleteness, Gödel, or Franzén. Instead, I want to talk about some of the background to the CH and one of the top five mathematical proofs of the last, say, 200 years.

To start with, say I have a set of three apples, a Red Delicious, a Fuji, and an Arkansas Black, and a set of three people: Alice, Bob, and Georg. How would I know whether or not the two sets are the same size, or cardinality? Simple. I need to put the two sets into a relationship where exactly one object from one set is associated with exactly one object from the other. If Alice eats the Red Delicious, Bob eats the Fuji, and Georg has the Arkansas Black flung at his head, then I know the two sets are the same size. What I have done is to put the two sets into a one-to-one relation. (Technically, my one-to-one correspondence is a bijection; it needs to be both injective and surjective.)

You might point out that I could just count the two sets to know if they were the same size. But that is ultimately the same thing: instead of putting a set of people in a one-to-one relation with a set of apples, I would be putting both sets of people and apples in a one-to-one relation with numbers. In fact, those are typically the counting numbers: 1, 2, 3, .... Counting the objects in a set simply amounts to putting the objects in a one-to-one relation with an initial-prefix subset of the counting numbers.

At this point, I feel the need to toss out a couple of factoids that you may (or may not) already be aware of:

The counting numbers are infinite. That "..." indicates they continue forever.
There are (many) different kinds of numbers, including counting numbers, natural numbers (0, 1, 2, 3,...), integers (..., -2, -1, 0, 1, 2,...), rational numbers (x/y, where x and y are integers), and real numbers (0, 4, pi, e, 34.56,...).

And here is a neat point that is the crux of this whole post: by explicitly setting things in one-to-one relations, you can compare the sizes of infinite sets.

But wait, you say, what the heck does that mean? Here is a question for you: are there as many counting numbers as there are natural numbers. It does not seem like there should be, because the naturals have that extra 0 that is not included in the counting numbers. But infinite sets are weird. For one thing, I can't show you a one-to-one mapping, like I could with people and apples. Instead, I can exhibit a relation: \[ \forall n : n \in \textrm{natural} : (\exists c : c \in \textrm{counting} : n = c - 1) \] \[ \wedge \] \[ \forall c : c \in \textrm{counting} : (\exists n : n \in \textrm{natural} : n = c - 1) \] Or, in English, for any natural number $n$ you can give me, I can give you back a counting number $c$ such that $n$ is $c - 1$ and vice-versa. I'll spare you the demonstration that this relation is suitably one-to-one and just point out that it shows that the counting numbers and the naturals have the same cardinality, or size. Like I said, infinite sets are weird: one of the defining characteristics is that an infinite set can be put in a one-to-one correspondence with a proper subset of itself.

So, if that is the case, how do the counting numbers and the naturals compare with the integers? It turns out that they are the same size, too. Consider the following two functions, nat, which converts any integer to exactly one natural number, and int, which converts any natural number to an integer.
\[ \textrm{nat}(n) = \begin{array}{cl} 2n & \textrm{if } n \geq 0 \\ -2n - 1 & \textrm{if } n < 0 \end{array} \]\[ \textrm{int}(n) = \begin{array}{cl} n/2 & \textrm{if } n \textrm{ even} \\ {-(n + 1) \over 2} & \textrm{if } n \textrm{ odd} \end{array} \]Without any particular argument that these two functions are inverses, I assert that they define a one-to-one relationship and therefore demonstrate that the natural numbers and the integers are the same cardinality.The rationals? This is where things start to get tricky. Consider for a moment the relationship I defined between the integers and the naturals above; what I did was to effectively take the integer number line, fold it in half between -1 and 0, and then alternately take one number from each half to match each natural number:

0,	1,	2,	3,	4,	...	(the naturals)
0,	-1,	1,	-2,	2	...	(the integers)

A similar trick can be done with the rationals by, first, only looking at the positive, natural numbers. (If I can put the positive fractions in a one-to-one relationship with natural numbers, I can use the same folding argument to include the negative fractions in the same sort of relationship.) Then, make a table with the numerators starting at 0 on the horizontal axis and the denominators starting at 1 on the vertical axis. (Obviously, the denominators cannot include zero.) Starting from the upper left cell, 0/1, zig-zag out one cell at a time, producing 1/1, 0/2, 2/1, 1/2, 0/3, collecting each upper-right-to-lower-left diagonal.

0/1	1/1	2/1	3/1	...
0/2	1/2	2/2	3/2	...
0/3	1/3	2/3	3/3	...
...	...	...	...

Based on the table and the diagonal paths, I assert

Every positive rational number shows up at least once in this table, and by multiplying each entry by -1, I can construct another table where every negative rational number shows up, and so that every rational number appears in one of the two tables at least once.
By taking the diagonals in order, I can create a single list of the positive rationals, where each cell shows up in exactly one place in my list. By alternating between tables, I can construct a list containing every cell in both tables.
And therefore, the set of rational numbers is not larger than the set of natural numbers.

Slick, eh?All I have done so far is to argue that a few different infinite sets are the same size, for my definition of "size", which is the ability to find a one-to-one relationship. If that's all I have, well, it's neat but not earthshaking. But now I get to one of my favorite proofs: Cantor's Diagonalization gag.Are the real numbers, say those between 0 and 1, the same size as the counting numbers? Say they are, which means I can construct a list of those real numbers, mapping each to the counting numbers:

1	0.435246687003...
2	0.076201826664...
3	0.000000000000...
4	0.999999999999...
...	...

It doesn't matter in the least what that order actually is, though, because I can now construct another real number between 0 and 1 that cannot be on that list:

Take the first digit after the decimal point of the first number on the list.
Add one to this digit, wrapping around to 0 if the digit is 9.
Make this new digit the first digit after the decimal in my new number.
Repeat with the second digit after the decimal point of the second number, creating the second digit of my new number.
And so on, incrementing the next digit of the next number to get the corresponding digit of the new number.

This new number cannot be on the list created by the one-to-one relationship with the naturals, because the new number differs from every number on the list in at least one decimal place: 0.5810....As a result, the cardinality of the real numbers between 0 and 1 is greater than the cardinality of the counting numbers, natural numbers, the integers, and the rationals. There are more real numbers between 0 and 1 than there are integers. Infinity comes in multiple sizes.
(Feel smarter yet? I know I do.)

So, what's this continuum hypothesis, then? Cantor identified the size, or cardinality, of the integers as the transfinite number $\aleph_0$. He went further to identify other transfinite numbers $\aleph_1$, $\aleph_2$, and so on, using completely different definitions. Now, we now know that the cardinality of the reals between 0 and 1, call it C, is greater than $\aleph_0$, but the open question is whether C is less than or equal to $\aleph_1$.

De re profanae

2011-05-22T17:13:00.002-05:00

According to Wikipedia, Alfréd Rényi, rather than Paul Erdős, said, "a mathematician is a device for turning coffee into theorems." My personal corollary to that is, "a programmer is a device for turning coffee into profanity." In the same vein, some other wit also said, "Profanity is the one language all programmers know best." There are many reasons why invective and informatics go hand-in-hand. I personally do not have a problem with that, though for most of my career I have been the one in the office who cursed the least. My sole reason was that when I do, I want people to pay attention. At the moment, however, I seem to be one of the fouler folks around. This is somewhat unsettling, but it makes for a quieter workplace anyway.

I do not have a problem with profanity, but I do have a problem with euphemisms. Specifically, the term "f-bomb", which seems to be more common than I had realized. A while back, I ran across a story in the Chronicle of Higher Education involving a student at Hinds Community College who received 4/5 of a suspension after uttering the word "fuck" after class. What I found upsetting was not the story (Who expects maturity from one of those diploma mills?), but the response. The title of the story was entertaining, but several of the commentors seemed to be using the term "f-bomb" with a straight face. Most of the Chronicle's readers are teachers and administrators at institutes of higher education; I expect them to know better.

I am afraid I have news for some. "Fuck" is a word. It is not a bomb. It will not explode. It cannot kill anyone. If you, like those Chronicle readers, are dealing with people potentially in military service who are likely to face real explosive devices, it is a bit silly to dance around a word as if it were dangerous.

To bring this back to programming a bit, I am not a really big fan of profanity in code. Again, it does not bother me, but seeing a comment such as "This in fucking stupid!" is less useful to me than seeing a description why it is stupid and letting me exercise my own vocabulary. On the other hand, if you cannot mention "brainfuck" without turning red, I am going to have to suggest that you need to grow up a bit. (I hesitate to mention Scunthorpe, North Lincolnshire, England.) And if you interrupt me while I am battling Java, that will not be Yosemite Sam I am quoting.

This post brought to you by the geniuses behind Java, who have shown their creativity by introducing every possible interface mistake, misdesign, and gratuitous stupidity known to mankind.

Quote o' the Day: Tony Morris and Edsger W. Dijkstra on metaphor and analogy

2011-05-15T11:46:00.002-05:00

While poking around Tony Morris' site, I found a fairly nice presentation on monads. In it, he makes a pithy quote which extends another pithy quote from Edsger Dijkstra:

...but the most disorienting thing was that I found myself suddenly submerged in a verbal tradition that was totally foreign to me! [Legal professionals at a "Seminar on Information, Law and Technology"] were on the average very verbose —some even repetitive—, they had a tendency to "reason" by analogy and more than once I felt that speakers cared more about the potential influence of their words than about what they actually said. -- EWD

Metaphors are training wheels that obscure learning opportunities and stall progress (object-oriented programming anyone?). -- Tony Morris

Tony Morris on static types

2011-05-09T23:01:00.031-05:00

Tony's blog has an interesting discussion of API design and static typing that includes one of the best reasons for very strongly typed interfaces:

Now, why these rules? Well, because if you can achieve the goal of enforcing these rules, then the next phone call that I get in L3 support from an upset client, I can be guaranteed that one of the following are true:
I have a bug in my code, in which case, the sooner the call, the better! …unless of course, fixing the bug results in only more bugs — but we have avoided that possibility — hopefully you can see why.
The client has misused the API and circumvented the type system. The client has used null, thrown an exception or performed a side-effect within the API or perhaps even used such things as Java reflection or even type-casting or type-casing. Unfortunately, in some environments, there’s not much I can do about enforcing that except impose a de facto rule where you assume non-existence of these possibilities (Just don’t do that!). Hopefully you haven’t yet jumped to the conclusion that any of these things are necessary or even useful — they aren’t.
The client is simply mistaken about the merits of their complaint.

The only better reason I have heard of is the one I use: I would rather think hard for an hour or so to come up with an interface I would have a hard time screwing up than spend the next weeks or months trying to remember what is and what is not legitimate. In short, I'm lazy.

What are the rules Morris is talking about? He has an advanced programming course assignment for

students to write an API for the game tic-tac-toe. No need for the computer to tactically play tic-tac-toe — just an API that you can use to model the game itself. You can use any programming language you like, however, I think you will find certain environments to be lacking in the available tools, so I will guide you so that you’re not off somewhere “shaving yaks” so to speak.

The rules of the assignment are:

If you write a function, I must be able to call it with the same arguments and always get the same results, forever.
If I, as a client of your API, call one of your functions, I should always get a sensible result. Not null or an exception or other backdoors that cause the death of millions of kittens worldwide.
If I call move on a tic-tac-toe board, but the game has finished, I should get a compile-time type-error. In other words, calling move on inappropriate game states (i.e. move doesn’t make sense) is disallowed by the types.
If I call takeMoveBack on a tic-tac-toe board, but no moves have yet been made, I get a compile-time type-error.
If I call whoWonOrDraw on a tic-tac-toe board, but the game hasn’t yet finished, I get a compile-time type-error.
I should be able to call various functions on a game board that is in any state of play e.g. isPositionOccupied works for in-play and completed games.
It is not possible to play out of turn.

The first rule is a typical virtue of functional programming: referential transparency; a piece of code which violates that rule unnecessarily is much harder to understand than code that obeys it. The second rule is somewhat less typical, but still a well-known virtue: the function should be total. A total function always returns a meaningful value, as opposed to a partial function which is not well-defined on some part of its domain; in other words, if the code calling it compiles without error, a total function always returns a useful value, while a partial function may throw an exception or return a bad value for some arguments.

The third, fourth, fifth, and seventh rules are the interesting ones. (The sixth just says that there may be operations that the other rules don't apply to.) These require encoding a model of the valid operations in the game into the types of the API.

First, a little background. The type of a computational artifact (a variable or function, for example) is actually a predicate in a formal system defined by the type system of the programming language. (Go read up on the Curry-Howard correspondence, if you want. I'll still be here.) Some type systems are strong enough to make very strong, and very useful, statements about the program being written. In this case, Morris wants the API to specify limits on its interface to prevent invalid operations in the game of tic-tac-toe.

Take the third rule: the move(board, position, player) operation should be invalid on a board that is in a finished-game state, for example. In other words, if you define "write" to be limited to code that compiles (and in particular, typechecks), then it should not be possible to write code that attempts to make a move on a finished board. Or, the move operation is governed by a predicate that prevents it from being applied to a finished board. Or, a board is governed by a predicate that prevents it from having a move applied to it.

Now, writing the API and the predicates to satisfy these rules is not exactly easy. But it is possible in at least some programming languages. Specifically, Morris mentions Haskell, Scala, C# and Java. (Morris' API for Java uses Functional Java, if you are interested.) There are a fair number of approaches to doing this in various languages, some of which can be euphemistically called "open research areas"; I would like to focus on a few of the less euphemistic.

I found Morris' post from a link in Vasil Remeniuk's solution in Scala that uses phantom types. I may come back in a bit to see how this looks in Java.

If I am not completely confused, Morris' API uses higher-order functions to convince Java's type system to make the correct promises. Rather than have move(board, position, player) return a new board (to drastically oversimplify what I think Morris has done), move effectively takes three additional objects, each of which is a functor (in C++ lingo) or "command object" (in Patternish), an object that encapsulates a function along with necessary data; that is, a half-assed implementation of a closure, or a first-class functional value. These three function-objects handle three possible cases: the move's position is already occupied, the game is already over, or the move is valid and the game should continue. This approach is uncommon in Java, and certainly looks hideous. But, it works.

The third approach I want to mention actually involves weakening Morris' rules, in order to get an API that is somewhat less uncomfortable. Consider what happens if you make a valid move in tic-tac-toe: the resulting board may represent the end of the game, or it may allow the game to continue. Morris' API specifies that client code has to handle this bifurcation (Hi, Del!) by passing in two different function-objects for the two different cases, because Java's options are limited. (As I understand Morris, anyway.) The alternative I have in mind is to allow a certain minimal bit of non-total functionality, by having the move operation return either an in-progress board or a final board, where the "either" is given by an Either algebraic type:

public abstract class Either<S,T> {
  private static class Left<S,T> extends Either<S,T> {
    private final S s;
    private Left(S s) { this.s = s; }
    @Override public S isLeft()  { return s; }
    @Override public T isRight() { return null; }
  }

  private static class Right<S,T> extends Either<S,T> {
    private final T t;
    private Right(T t) { this.t = t; }
    @Override public S isLeft()  { return null; }
    @Override public T isRight() { return t; }
  }

  public abstract S isLeft();
  public abstract T isRight();

  public static <S,T> Either<S,T> left(S s)  { return new Left<S,T>(s); }
  public static <S,T> Either<S,T> right(T t) { return new Right<S,T>(t); }
}

This class is used something like:


    Either<Integer,String> is1 = Either.left(4);
    Either<Integer,String> is2 = Either.right("four");
    
    System.out.println(is1.isLeft() + " " + is1.isRight());
    System.out.println(is2.isLeft() + " " + is2.isRight());

where the output is:


4 null
null four

Notice that Either encodes a type-level choice; a value of Either contains a value of one of two other types. In the tic-tac-toe case, move can return Either<InProgressBoard,FinishedBoard> and the client code can pick out the right board, at which point it can type-safely take the next step. The non-totality enters because calling isRight on a Left value returns null; client code using that value cannot do anything unsound, but it also will not get a compile-time error. This approach provides an API that more closely resembles normal Java but weakens Morris' rule three to something like "If I call move on a tic-tac-toe board, but the game has finished, I should get a compile-time type-error unless I have done something god-awful stupid. In other words, I am required to check the result and actively be idiotic to get a run-time error." Which is bad, don't get me wrong, but may not be as bad as trying to explain Functional Java to the numbskulls soiling your API by trying to use it.

Morris would disagree, as witnessed by his comments quoted above and by the following, from another post:

Some people like to think “correctness” includes the thoughts of one or more persons in order to make the assessment. For example, one might proclaim, “sure you have a proof of program termination, but that is not the program that I asked for!” I think this is a poor use of the term “correctness” and I am not considering it any further here.

As a bit of a formalist myself, I can certainly feel the attraction to that definition of correctness, but it still leaves one in the unpleasant position of having a rather strange, technical meaning for a commonly-used word; somewhat like the difference between true and formally proven. For myself, I have seen too many comments to the effect of "if we proved everything correct, there wouldn't be any bugs" (for example, see David Harel's Algorithmics) or "[system X] has [huge percentage Y] devoted to handling situations that shouldn't occur" (see David Gries' The Science of Programming); even with software that is correct according to Morris, my to-do list would likely not be much shorter and TCP would still have to send retransmissions.

In any case, Morris has given a really nice challenge as well as an excellent description of why the challenge is worthwhile, and I too look forward to the day when I can be assured that that phone call likely represents genuine bug.

[Edit] Amazingly, a quick-and-dirty translation of Remeniuk's Scala code to Java seems to demonstrate the properties I was looking for. (This code was put together very quickly and does not attempt to satisfy all of Morris' rules. Nor does it meet all of the guarantees made by Remeniuk's code. But it's not bad.)

public class Phantom
{
  static abstract class Mark { }
  static class Nought extends Mark { }
  static class Cross extends Mark { }
  
  /* ... */
    
  static abstract class GameState { }

  static class NotFinished extends GameState { }
  static class Started extends NotFinished { }
  static class NotStarted extends NotFinished { }
  
  static class Finished extends GameState { }
  static class Failed extends Finished { }
  static class WinState extends Finished { }
  static class DrawState extends Finished { }

  static class Position {
    public final int x, y;
    Position(int x, int y) { this.x = x; this.y = y; }
  }
  
  static final class NextTurn<Last extends Mark,Next extends Mark> {
    // Type witnesses: values used only to force specific types.
    public final NextTurn<Nought,Cross> crossesTurn = new NextTurn<Nought, Cross>();
    public final NextTurn<Cross,Nought> noughtsTurn = new NextTurn<Cross, Nought>();
  }
  
  // S: Board's position in the game: NotStarted, Started, etc.
  // M: Last mark to be played.
  // Next: Next mark to be played.
  static class Board<S extends GameState, M extends Mark> {
    <Next extends Mark, S extends Started>
      Either<Board<Finished,Next>,Board<Started,Next>>
      move(Position position, NextTurn<M,Next> nextTurn, S isNotFinished) { /*...*/ }
  }

One thing that differs from the Scala code is that I have had to use explicit type witness values; in Scala I believe they are implicit. Also, the Scala code uses the same function argument approach as Morris', by calling Either.fmap.

This code would be very easy to circumvent, but it does demonstrate some of the desired features:

  public static void main(String[] args) {
    new Board<NotStarted,Nought>()
    .move(new Position(1,1), NextTurn.crossesTurn, new Started())
    .isRight() // The resulting board will not be Finished.
    .move(new Position(1,2), NextTurn.crossesTurn, new Started());
  }

The second move() call indicates that Cross is taking another turn, and fails to compile with the following error:

$ javac -cp src src/tictactoe/Phantom.java
src/tictactoe/Phantom.java:87:
 <Next,S>move(tictactoe.Phantom.Position,
              tictactoe.Phantom.NextTurn<tictactoe.Phantom.Cross,Next>,
              S) in 
    tictactoe.Phantom.Board<tictactoe.Phantom.Started,tictactoe.Phantom.Cross>
  cannot be applied to
    (tictactoe.Phantom.Position,
     tictactoe.Phantom.NextTurn<tictactoe.Phantom.Nought,tictactoe.Phantom.Cross>,
     tictactoe.Phantom.Started)
      .isRight().move(new Position(1,2), new NextTurn<Nought, Cross>(), new Started());
                ^
  1 error

There are limits to what you can do in the child process.

2011-05-02T22:19:00.000-05:00

According to the Mac OS X manual page for fork(2),

CAVEATS
There are limits to what you can do in the child process. To be totally safe you should restrict yourself to only executing async-signal safe operations until such time as one of the exec functions is called. All APIs, including global data symbols, in any framework or library should be assumed to be unsafe after a fork() unless explicitly documented to be safe or async-signal safe. If you need to use these frameworks in the child process, you must exec. In this situation it is reasonable to exec yourself.

Async-signal safe operations are (according to Mac OS X sigaction(2)):

Base Interfaces: _exit(), access(), alarm(), cfgetispeed(), cfgetospeed(), cfsetispeed(), cfsetospeed(), chdir(), chmod(), chown(), close(), creat(), dup(), dup2(), execle(), execve(), fcntl(), fork(), fpathconf(), fstat(), fsync(), getegid(), geteuid(), getgid(), getgroups(), getpgrp(), getpid(), getppid(), getuid(), kill(), link(), lseek(), mkdir(), mkfifo(), open(), pathconf(), pause(), pipe(), raise(), read(), rename(), rmdir(), setgid(), setpgid(), setsid(), setuid(), sigaction(), sigaddset(), sigdelset(), sigemptyset(), sigfillset(), sigismember(), signal(), sigpending(), sigprocmask(), sigsuspend(), sleep(), stat(), sysconf(), tcdrain(), tcflow(), tcflush(), tcgetattr(), tcgetpgrp(), tcsendbreak(), tcsetattr(), tcsetpgrp(), time(), times(), umask(), uname(), unlink(), utime(), wait(), waitpid(), write().

Realtime Interfaces: aio_error(), clock_gettime(), sigpause(), timer_getoverrun(), aio_return(), fdatasync(), sigqueue(), timer_gettime(), aio_suspend(), sem_post(), sigset(), timer_settime().

ANSI C Interfaces: strcpy(), strcat(), strncpy(), strncat(), and perhaps some others.

Extension Interfaces: strlcpy(), strlcat().

All functions not in the above lists are considered to be unsafe with respect to signals. That is to say, the behaviour of such functions when called from a signal handler is undefined. In general though, signal handlers should do little more than set a flag; most other actions are not safe.

The bottom line is that the child process is apparently sharing a lot with the parent process, along the same lines as older BSD's vfork(2) optimization. The normal Unix behavior of fork(2) involves sharing almost nothing; with the exception of some pretty painful operations, the child process shares nothing with the parent. Resources are duplicated instead.

fork(2) is a fundamental operation in Unix; radical changes in it's behavior imply radical changes in the operating system. Certainly, reading that CAVEATS paragraph would lead me to believe that essentially no existing Unix programs could run on iOS without significant code changes. (Ahhh, brings back memories of the bad old days when I had to deal with SunOS, Solaris, AIX, HP-UX, and Irix; all of which claimed to be Unix, but all of which had their own bizarre behavior from basic operations. Wonderful.)

My conclusion: Mac OS X isn't Unix, no matter how many people say it is. That man page is a fine counter-example.

Want to know more about Unix system programming? See Advanced Programming in the Unix Environment by the late W. Richard Stevens. (Truthfully, you'll probably want the second edition.) It shouldn't take long to appreciate the depraved insanity that is the Unix family tree.

SQL Combinators in Java

2011-04-13T21:43:00.001-05:00

Combinators are another technique common in functional programming which seems to be significantly less common in object-oriented languages. This is unfortunate, because combinators work very well in an object-oriented design. What I am going to present below is a very simple use of them that hopefully displays some of their features. Other common examples include parsers and various embedded domain specific languages.

Now, I will admit that I am a crazed neo-Luddite. I am proud to say that I hate persistent objects, believe remote procedure calls are evil, and regard most of the enterprise development infrastructure and practices with a considerable amount of disdain. But the bottom line is that I do not use Hibernate, JPA, or any of the other object/relational/database/mapper hoo-has. They, in the immortal words of Del, purport to make something easier that was not difficult in the first place. In doing so, they stack another layer of stuff on top of the actual solution; witness the fun when combining OSGi modularity with Hibernate.

Instead, I am perfectly happy writing SQL statements in my cheerfully modular code, performing just the operations that I need when I need them, and enjoying the control that I get. However, there are times when that is not enough, when plain SQL statements will not do the job. One such case that has come up several times in my career is a semi-general, ad hoc query based on a HTTP request.

For example, consider a web form that displays rows from a database table. This web form submits a number of parameters, and based on those parameters the server-side code formulates a query that returns the appropriate rows, which are then returned to the client. Now, there are two ways to formulate a SQL query: parameterized and non-parameterized. The latter involves building a text string including the SQL and the values to be selected; the values must be appropriately sanitized to avoid SQL injection. I prefer the parameterized option. The thing about the parameterized option is that it needs two passes: one to build the SQL, "SELECT * FROM table WHERE whosit = ?" and one to inject "Fred" to match ? number 1 (remembering the order that the ?'s came in, too). This is where the combinators enter the picture. These combinators provide a way of building the where-clause of a SQL statement in a semi-general way.

To demonstrate, this code selects all of the rows with NAMEs equal to "Doe".

Predicate p = Predicate.stringEquals("NAME", "Doe");
statement = connection.prepareStatement("SELECT * FROM people WHERE " + p.toSql());
p.parameterize(statement);
ResultSet rs = statement.executeQuery();

The following example selects all of the rows with NAMEs equal to "Doe" and ADDRESSes LIKE "Main Street".

Predicate p = Predicate.and();
p.add(Predicate.stringEquals("NAME", "Doe"));
p.add(Predicate.stringLike("ADDRESS", "Main Street"));
statement = connection.prepareStatement("SELECT * FROM people WHERE " + p.toSql());
p.parameterize(statement);
ResultSet rs = statement.executeQuery();

Finally, this code selects all of the rows with NAMES equal to "Doe" and orders the result by "CITY", ascending.

Predicate p = Predicate.orderedByAscending(Predicate.stringEquals("NAME", "Doe"), "CITY");
statement = connection.prepareStatement("SELECT * FROM people WHERE " + p.toSql());
p.parameterize(statement);
ResultSet rs = statement.executeQuery();

The primary abstract interface to a combinator is to evaluate it. (This is one of the reasons they work so well in functional languages.) For my SQL combinator, I wanted a little richer interface:

public abstract class Predicate
{
  /**
   * Return the SQL for the given predicate, including parameter markers (?).
   * @return A String.
   */
  public abstract String toSql();
  
  /**
   * Set the parameters in the {@link PreparedStatement} associated with the parameter markers from the toSQL string.
   * This method must be called after the statement is created from the string and before the query is executed.
   * @param statement {@link PreparedStatement} which should have the values injected into it.
   * @throws SQLException If the parameterization fails.
   */
  public void parameterize(PreparedStatement statement) throws SQLException
  {
    [...]
  }

  /**
   * Test whether the {@link Predicate} represents an empty WHERE clause.
   * 
   * @return True if the predicate represents an empty WHERE clause, false otherwise.
   */
  public boolean isEmpty() { return false; }

[...]

The two key methods are toSql(), which returns the SQL predicate clause, and parameterize(), which accepts a PreparedStatement generated from the SQL and inserts the values. A base-case combinator (ignoring the empty one) is something that compares a value with a column:

  public static class StringEquals extends Predicate
  {
    private final String column;
    private final String value;
    
    public StringEquals(String column, String value)
    {
      this.column = column;
      this.value = value;
    }

    @Override
    public String toSql()
    {
      return String.format("(%s = ?)", column, operator);
    }

    @Override
    protected int setParameter(int index, PreparedStatement statement) throws SQLException
    {
      statement.setString(index, value);
      return index + 1;
    }
  }

The parameterize() method of the Predicate calls setParameter() for the Predicate structure; each setParameter returns the next index value into the SQL statement.

  [...]
  public void parameterize(PreparedStatement statement) throws SQLException
  {
    this.setParameter(1, statement);
  }
  [...]

By ensuring that the order of the ?'s in the SQL is the same as the order that setParameter() is called, the values are associated with the appropriate clauses.

Another combinator class is used to search for timestamps appearing on a given day:

  public static class OnDate extends ColumnComparison
  {
    private final String column;
    private final Date date;
    
    protected OnDate(String column, Date date)
    {
      this.column = column;
      this.date = date;
    }

    @Override
    public String toSql()
    {
      return String.format("(%s BETWEEN ? AND ?)", column);
    }

    @Override
    protected int setParameter(int index, PreparedStatement statement) throws SQLException
    {
      final Calendar calendar = Calendar.getInstance();
      calendar.setTime(date);
      statement.setDate(index, new Date(calendar.getTimeInMillis()));
      calendar.roll(Calendar.DATE, true);
      statement.setDate(index + 1, new Date(calendar.getTimeInMillis()));
      return index + 2;
    }
  }

The interesting part of combinators (and the ad hoc query) is the ability to generate a higher-level Predicate from one or more more-basic predicates. In this case, that is the purpose of And and Or:

  private static class And extends Aggregate { public And() { super(" AND "); } }
  private static class Or  extends Aggregate { public Or() { super(" OR "); } }

which are based on a general Aggregate:

  public abstract static class Aggregate extends Predicate implements Collection
  {
    protected final String join;
    protected final List subPredicates = new ArrayList();
    
    protected Aggregate(String join)
    {
      this.join = join;
    }
    
    @Override
    public String toSql()
    {
      List sqls = new ArrayList(subPredicates.size());
      // Some hot mapping action here.
      for (Predicate sub : subPredicates)
      {
        sqls.add(sub.toSql());
      }
      return StringUtils.join(sqls, join);
    }
    
    @Override
    protected int setParameter(int index, PreparedStatement statement) throws SQLException
    {
      for (Predicate sub : subPredicates)
      {
        index = sub.setParameter(index, statement);
      }
      return index;
    }
  [...]
}

The final piece is the capability of ordering the results of the query.

  public static class Ordered extends Predicate
  {
    private final String sortColumn;
    private final Predicate predicate;
    private final boolean ascending;
    
    protected Ordered(Predicate predicate, boolean ascending, String column)
    {
      this.predicate = predicate;
      this.sortColumn = column;
      this.ascending = ascending;
    }
    
    @Override
    protected int setParameter(int index, PreparedStatement statement) throws SQLException
    {
      return predicate.setParameter(index, statement);
    }

    @Override
    public String toSql()
    {
      // Default: ASC
      final String asc = ascending ? "" : " DESC";
      return predicate.toSql() + " ORDER BY " + sortColumn + asc;
    }
  }

There is a small problem here; once an Ordered has been wrapped around a Predicate, the result is no longer really a Predicate; it admits the same interface, but an Ordered instance cannot legitimately be added to an And or Or collection. I will leave the fix as an exercise for the reader.

To make using Predicates easier, I included a number of static methods that can be used to create individual instances.

and() returns an And aggregate which will join its sub-predicates with AND.
or() returns an Or aggregate which will join its sub-predicates with OR.
stringEquals(String, String) returns a simple StringEquals predicate joining a column with a String via '='; this comparison is case sensitive.
stringEqualsIgnoreCase(String, String) returns a simple predicate joining a column with a String via '='; this comparison is case-insensitive.
stringLike(String, String) returns a simple predicate joining a column with a SQL pattern expression via 'LIKE'; this comparison is case-insensitive.
onDate(String, Date) returns a simple predicate joining a column with a Date; BETWEEN is used to allow any time between DATE and the next day.
orderedBy(Predicate, boolean, String) returns an Ordered predicate, ordered as described by the flag and the column names.

The examples I gave are not as syntactically nice as some of the DSLs implementable in Haskell, say. (But in Java, what is?) However, it does allow me to cleanly build up a predicate in stages

Poison, forensic medicine, and facts

2011-04-01T22:56:00.002-05:00

I like The Poisoner's Handbook: Murder and the Birth of Forensic Medicine in Jazz Age New York. Really, I do.Deborah Blum writes well, the story is fascinating, the history is both vital as well as, well, timely. But it could have been so much better.

I don't really mind Blum's bizarre dual organization: the book's chapters are named after, and focus on, specific poisons like chloroform, wood alcohol, cyanides, and so on, but the text is also chronological, from 1915 in chapter one, 1918 and 1919 for chapter two, 1920 through 1922 for chapter three, and so on. I mean, it follows the career of New York's first medical examiner and his forensic chemist, Alexander Gettler. Through a career, it's obvious that some issues, like some poisons, will be more important at specific times. Likewise, some poisons, like some issues, will continue to rear their heads through the years although perhaps in different guises.

[My coroner story: I am from Texas. My required undergraduate Texas government class was enlivened by stories like the Justice of the Peace who, acting as coroner, declared a death involving something like 27 bullet wounds to be a suicide.]

I also don't really mind when Blum's writing style ventures far beyond the pale; comparing the color of a body poisoned by carbon monoxide with the hourglass on a black widow may impress some of the reviewers I have read, but it is just too much of a stretch for me.

What I do mind is a lack of trust. History is vital because, to paraphrase Marx and Santayana, those who cannot remember the past are condemned to be characters in a bad comedy. Blum's tale has many lessons, from prohibition to overconfidence. (Did anyone notice the similarities between Marie Curie and Thomas Midgley, Jr., the GM engineer who introduced tetraethyl lead to gasoline, washed his hands in the stuff for the press, and who was last seen vacationing in Europe and seeking treatment for lead poisoning?)

But details matter. This story is about science; wrong is wrong. When Blum explains that "gamma radiation [...] contains a dangerous mixture of X-rays and other subatomic materials" (pg. 184), or that "beverages containing ethyl alcohol were known as 'hard liquor'" (pg. 197), I am left wondering if her other assertions, such as "one of the benefits, or curses, of [...] Prohibition: every drink was a stiff one" (pg. 200) are similarly fuzzy. One might imagine that a PLoS blogger would know the importance of checking facts.

So I am left with one conclusion: although The Poisoner's Handbook is a good read, it is a failure as anything more.

[Ps. More about Midgley. According to Wikipedia, he was also involved in the synthesis of chlorofluorocarbon refrigerants, the production of "[...] which is being phased out by the Montreal Protocol because they contribute to ozone depletion". Also, he died of strangulation after becoming entangled in a "a self-devised harness for getting in & out of bed" after being disabled by polio.]

Link o' the day: Johann Carl Friedrich Gauss

2011-04-01T12:55:00.001-05:00

A little known fact about Gauss:

It only takes Gauss 4 minutes to sing “Aleph-Null Bottles of Beer on the Wall”.

Frans Kaashoek wins the 2010 ACM-Infosys Foundation Award

2011-03-30T11:31:00.000-05:00

According to ACM TechNews and the MIT news, Frans Kaashoek has won the Association for Computing Machinery’s 2010 ACM-Infosys Foundation Award in the Computing Sciences. Prof. Kaashoek has done a lot of interesting distributed systems work and certainly deserves assorted awards. However, the weird part and what prompts this post is the specific award. According to SD Times and the ACM itself,

[the] ACM-Infosys Foundation Award, established in August 2007, recognizes personal contributions by young scientists and system developers to a contemporary innovation that exemplifies the greatest recent achievements in the computing field. Financial support for the $150,000 award is provided by an endowment from the Infosys Foundation.

Specifically, notice the "young scientists and system developers" part. Kaashoek won the NSF national young investigator award in 1994 according to his page at MIT. He received his Ph.D. in 1992 under Andy Tannenbaum. Heck, the earliest publication listed by him was in 1991. That would seem to make him roughly my age; certainly, it doesn't seem like he would be eligible for a Fields Medal.

So, congratulations to Frans! And maybe there is some hope for my aging carcass. I mean, if he is a "young scientist"....

Quote o' the Day: Agressively stupid

2011-03-23T13:07:00.000-05:00

This is from TheServerSide.com's article, Developers still skeptical of Oracle’s stewardship of Java.

James Gosling, considered the father of Java, said during his keynote session at the Java Symposium that it is in Oracle’s own interest to “not be really aggressively stupid.” But he said it’s been clear that Oracle didn’t exactly know what it was getting into with the acquisition of Java.

Not being really aggressively stupid is a problem to which many of us can relate.

A few more comments about ...Why Is the Phone on Fire?

2011-03-14T21:56:00.002-05:00

Since I gave such a ringing endorsement of If I Only Changed the Software, Why is the Phone on Fire? (at least as ringing as I plan on getting), there are a few more comments I can make related to the book.

Network protocols

Header	Address	Message ID	Group ID	Data Length	Data	CRC
4 bytes	4 bytes	1 byte	1 byte	1 byte	0-27 bytes	2 bytes

One of Simone's chapters deals with a network-communication timing related bug that strikes somewhere close to my heart. Part of the problem deals with the format of protocol messages.

Raw Data Message Formats
Message Name/ID	Data Length	Data Format
DATA_CHAR/5	1 byte	Single char
...
DATA_INT_ARRAY/11	1+(0-n)	Num ints (1 byte), raw int data
...
Formatted Data Message Formats
Message Name/ID	Data Length	Data Format
...
BLOOD_PRESSURE/21	24	Timestamp, 10 samples bit-packed (4 chars, 1 int)
...

This format has a lot of excess redundancy. Consider that the data length is encoded in the message three times: as the message id, as the data length itself, and sometimes in the data itself. For example, the raw integer array includes a total data length as well as the number of integers. On the other hand, the raw messages are irrelevant; any actual use is going to need a dedicated message id, and the id determines the data size. Further, the data size may also be in the header, as an overall message length, and in the CRC, because anything that goes on the wire, or in the air, needs to be checksummed.
Since a part of the problem being discussed is a tight network-bandwidth bound, ditching the useless data length byte plus an unused byte in the data would allow another sample to be sent in the pulse-oxygen message, reducing the original bandwidth used from 120kbps and the solution's 29kbps to 27kbps, a reduction of about 6%.

(Strangely, Simone cites TinyOS in the discussion of the message format. I have no idea why.)

Tips

Despite providing another example of the Heavenly Emporium of Benevolent Knowledge, Simone's list of tips has some interesting features.

Find a sounding board (doesn't have to be a live person!) - talk through ideas to quickly identify good ideas and discard bad ones.

Surprisingly effective. Also found in The Psychology of Computer Programming, where Gerald Weinberg advised talking to a stuffed bear. Or you can try a rubber duck, according to Del.

Use visual aids (flowcharts, graphs, function call trees)....

The opposite of a correct statement is a false statement. But the opposite of a profound truth may well be another profound truth. - Niels Bohr.

I come from the land of Dijkstra, where flowcharts and such are frowned on, for good reason. However, visual aids can easily show parallel structures, or the lack thereof, in the system.

Play Computer.

Or don't. As I may have mentioned before, I view dynamic reasoning with roughly the same enthusiasm as flowcharts. Both have their uses, but static reasoning and more formal methods are usually more effective.

Think with your brain, not your debugger.

My disdain for debuggers occasionally earns me abuse, but they really should be a last resort, not a first choice.

Be clever.

I reiterate my earlier reference to Niels.

If I Only Changed the Software, Why Is the Phone on Fire?

2011-03-11T20:54:00.001-06:00

I just returned from a vacation having read If I Only Changed the Software, Why is the Phone on Fire?: Embedded Debugging Methods Revealed, by Lisa Simone. I have to admit that this is not a great book; it did nothing to change the way I think and I don't remember seeing anything that I had not seen (or done) before. However, it is a pretty nice introduction to the subtle skill of debugging.

Debugging is a difficult thing to teach. In fact, it seems to me to be more difficult to teach than to learn: I have never seen an attempt to teach debugging succeed on any greater level than a list of tips and rules of thumb. On the other hand, the most successful debuggers, and the most effective debugging efforts, have completely transcended any tips or rules. The person doing the debugging coupled a deep (if not specific) understanding of the system or at least technology in question with the problematic behavior to arrive on the trail of the problem almost mystically.

Of the works that try to present a more thorough approach to debugging than a list of tips, many that come to mind attempt to teach a simplified, corrupted version of the scientific method: hypothesis followed by test; hypothesis, test; hypothesis, test. Unfortunately, without some significant guidance on the hypothesis phase, that method boils down to guess-and-hack, which is horribly inefficient. The whole art of debugging is in determining a likely, or at least useful, hypothesis.

If I Only Changed the Software... does not try to present a grand theory of debugging, and it does have a list of tips, but it does more to teach the feeling of debugging than any other work I've read. Perhaps the fictional, narrative-based style can teach what the process of debugging looks like.

One nice (although someone else may feel otherwise) feature of the book is the use of, well, less than perfect code in examples. Certainly, when I was less experienced than I am now, I would have found the code a ghastly horror and a crime against nature. In fact, I would probably have been right. On the other hand, having seen more code, I now view the examples in the book as pretty typical. Certainly, none of it is procmail.

The big benefit of the code is that it demonstrates a bug may not be the bug. For example, the following is taken (and simplified) from one of the book's examples:

/*
   Function: Part of ISR. Every 1000 ms the new ovenPW is calculated.
 */
void periodic_timer()
{
  /* ------ 10 msec ------ */
  ... code ...
  /* ------ 1000 msec ------ */
  ten_msec_ctr++;
  if (ten_msec_ctr == 10)
  {
    ...
    ovenPW = ...
    ten_msec_ctr = 0;
  }
}

The function periodic_timer appears to be called every ten milliseconds. The bug I immediately spotted involves the code labeled with "1000 msec"; it is actually executed every 100 milliseconds. However, that issue is completely unrelated to the bug described in the chapter. Updating the oven-heater-on pulse width ten times more frequently than expected should not have any particular ill effects, certainly nothing involving the actual problem. That is a vital lesson for anyone doing debugging.

I would recommend If I Only Changed the Software... to just about any programmer, certainly anyone inexperienced in the task that has occupied much of my career. Although at least some exposure to low-level programming would be good, embedded programming experience is not a requirement. The book may be focused on embedded debugging, but the lessons are applicable to any programming task.

A paean to the pulldown resistor

2011-03-06T10:50:00.000-06:00

As a Computer Sciences sophomore or junior (it has been so long I don't remember) at UT Austin, I took a class on basic digital logic (EE316; I think they're using a later edition of the same textbook). What I learned there has not materially helped me any itself, although it provided an excellent base for later architecture and operating systems classes, and gosh knows I have used those a lot, in later classes, in research, and in actual productive work.

On the other hand, I just acquired and started fiddling with an Arduino and its excellent tutorials, especially Limor Fried's Arduino Tutorial: Learn Electronics using Arduino! (one of the 10 women who secretly control the Internet). And I just learned something basic, something that I did not have a clue about before.

When you connect a switch to a digital logic input, such as a pin on a microcontroller programmed to turn on a LED when the switch is closed, you actually only have half of the work done. Consider the top half of Wikipedia's diagram to the left: if the switch is closed, the Logic Gate (representing my microcontroller pin) will see a voltage $V_{in}$. $V_{in}$ will normally be provided at a value that the microcontroller can interpret as 1, say, and work properly. On the other hand, as I recently learned, when the switch is open, the Logic Gate will see neither a 1 nor a 0; instead, it will see some odd, floating, unconnected value. In my Arduino experience, the LED will be in a weird, half-lit state, presumably switching on and off as the value fluctuates.

What needs to be added is a connection to Ground, the 0 state, that takes over the input when the switch is closed. Unfortunately, if you connect the input to ground, it will be grounded whether or not the switch is open. So, you add the pulldown resistor, which allows the input state to go to 0 when the switch is open but which prevents the input from going to 0 when the switch is closed.

Anyway, here's a tip of the hat to the humble pulldown resistor and the opposite, pullup resistor.

The one problem with open source

2011-02-01T21:47:00.007-06:00

[Corey, of Soup In A Deli, pointed this out to me this morning, but it was such a disturbing thought that I immediately had to write this post.]

What is the worst problem with open source software? It would have to be a completely inescapable problem, one which cannot be resolved while the software remains open source, as well as a problem restricted entirely to open source, one which simply cannot apply to any of the various forms of proprietary software.

Let me pause here a minute and let you ponder the question....

The usual suspects are right out. Documentation? Most reasonably popular open source projects have documentation at least as accessible as Oracle's, IBM's, or Microsoft's. Quality? It has been two decades since that one went out the window. Usability? Nah. (Looks like Atwood's got some broken links.)

No, the worst problem with open source software is...let me draw you a picture. If you're like me, and I know I am, you are a contractor working in a biggish enterprise shop. You probably have service level agreements as part of the contract, but unlike me, you probably have not just converted to a fixed-price contract, putting teeth into those SLA's. Suppose a problem rears its head, a mean one. A not-fixable-within-the-SLA-period problem.

If you are using proprietary software, it's vendor time (if not Miller time). Generally, the SLA timer is going to have to be put on hold while you wait for a response from the vendor. If your shop has planned ahead, you will have a SLA with the vendor, but I have never seen any agreements that were coordinated, so that any problem requiring vendor involvement was guaranteed to be handled within the local SLA period. So, while you are waiting for the vendor to get back to you, the clock waiting for your performance has to be stopped. You have time to cast around for the actual solution to the problem. You have time to find a suitable scapegoat. You might even have time for lunch. So, even if the vendor comes back with a "Not me!" response, you have extra time to come up with a convenient work-around.

But if you are using open source software, you are in a completely different boat. This time, without a paddle. In the worst case, you don't have anyone to point the finger at. A mailing list? Sure, I'll let you give that a try. Besides, I bet you sold the open source software with the promise that "I could fix it myself if I had to." Now, you have people looking at you with that annoying "Well?" expression. The only person you can point the finger at is yourself, and the timer is still running.

I suppose this is why managers seem so interested in "indemnification" from vendors supporting open source software. Unfortunately, I'm neither a manager nor a weasel (to the extent that that is not redundant), so I never really understood it before. I'm one of the people who just has to make it work, which is why I like open source; the baggage that comes with proprietary vendors is tremendous and very, very ugly.

So, there's your problem with open source software. If you are only interested in getting work done, open source is great. On the other hand, if you are interested in making money whether or not work gets done, open source software has a big problem.

What Every Computer Scientist Should Know About Floating-Point Arithmetic

2011-01-28T15:55:00.001-06:00

According to this post on reddit, Oracle has broken the links to "What Every Computer Scientist Should Know About Floating-Point Arithmetic", originally published in the March 1991 issue of the ACM's Computing Surveys. Oddly enough, that is the only issue of Computing Surveys that I own, having stolen a copy from someone at UTCS for just that article.

In any case, lest it be lost entirely in the depths of Oracle's documentation, I grabbed a copy of "What Every Computer Scientist Should Know About Floating-Point Arithmetic" without any permission whatsoever simply because everyone (not just computer scientists) who deals with floating-point numbers really ought to have some kind of grasp of the stuff in this paper.

(Of course, if Oracle sends me a cease-and-desist, I'll probably collapse like a soggy waffle.)

Orthogonality

2011-01-06T21:38:00.000-06:00

This is a story about how bad code gets written by someone who knows better.

Orthogonality, in a basic geometrical definition, means that two lines are perpendicular to each other. Consider the traditional x and y axes as the two lines. These two lines are perpendicular, and so orthogonal. All of the points on the y axis, projected onto the x axis, share the same point. If you move from one point on the y axis to another, you keep the same x value; your shadow on the x axis does not move.

The alternative involves having the two lines non-perpendicular. Now, all of the points on the y axis, projected on the x axis, are mapped to different points on the x axis. If you move from one point on the y axis to another, you also have to change your x value; the shadow on the x axis moves with you.

What has this got to do with bad code? Non-orthogonality is a problem when it appears in code. In this case, I could have avoided the problem, but I didn't. Now, I get to write bad code. It will work, but it will not be pretty, and I bet it will cause problems in the future.

Take a pretty normal user authorization system, where users have the ability to perform their designated operations for the site where they work. As a result, the user's home location maps to their authorization. Unfortunately, it never stays that way. In my case, one group of users is authorized to do things for remote sites, and a sub-group of them cannot do things for their own site. So, location no longer cleanly maps to authorization.

One proposal was to use location as the primary authorization mechanism, with group membership overriding the location for the special cases. My proposal, on the other hand, was to use a group for every location and add users to the correct group to allow them to do whatever they need to do. Unfortunately, I didn't press the issue and it is too late now, given that the special groups are set up and populated and the sheer inertia of the organization is overwhelming.

So I am now writing code using location as a primary authorization field with group membership as an override. Yay.

Quote o' the Day: Appropriate shoes for protection from electrostatic charge

2010-12-27T12:59:00.001-06:00

I was recently pointed by a cow-orker to the Things I won't work with segment of Derek Lowe's In the Pipeline blog, which includes some great comments like,

"The paper mentions that 'Introducing N-oxides onto the tetrazole ring may . . . push the limits of well-explored tetrazole chemistry into a new, unexplored, dimension.', but (of more immediate importance) it may also push pieces of your lab equipment into unexplored parts of the far wall."

and

Our noses can immediately tell the difference between garden variety nitriles and their evil twins [isonitriles]. The former often have no smell at all, or run to a faint spicyness. The latter smell like. . . like. . .well, I've never actually been downwind of the Abominable Snowman's armpit or been had my eyeglasses fogged up by a Komodo dragon with stomach trouble, but those are the examples that come to mind.

But my favorite is a quote from one of the papers mentioned:

"The use of suitable protective clothing, in particular a face shield, ear protectors, a bullet-proof vest, arm protectors, and kevlar gloves, as well as appropriate shoes for protection from electrostatic charge, is mandatory. Ignoring these safety precautions can result in serious injury!"

And I thought my life was difficult when I had to wear a hard-hat because I was dealing with emacs.

Equational programming

2010-12-25T18:53:00.000-06:00

It is Christmas and Dr. McGuire is too busy watching snow fall to come up with a real post, so he is just rehashing a reply to a question on the haskell-beginners mailing list as if it were new. Typical.

Jun HU wrote:

My first language is C, and I've strong intention in learning a pure functional programming language. My very first question is how to think in the functional programming way, anyone has some ideas.

I cannot claim C as my first language, but I do say it is my "natural" language; I have written more code in C than I have in any other, and I've been using it for nigh on 20 years. I also cannot claim to think in the functional programming way, but using O'Caml and Haskell has definitely changed how I program in any language. In fact, I suspect functional programming has had a bigger effect than I had previously considered. But I am definitely not a Haskell guru.

I believe the biggest difference between functional and procedural programming is thinking equationally rather than operationally. With procedural programming as in C (and most object oriented languages, which in my experience are more procedural than not), the tendency is to think operationally: "First the program does this, then that happens, then that,...." Now, back at UT Austin (I grew up in the land of Dijkstra), at the time anyway, they were fond of teaching axiomatic thinking: "At this point in the program text, the state is this; at that point in the text, the state is that...." That is definitely a significant improvement, and I attribute what decent code I have written to that approach, but it definitely is not as natural as either operational or equational thinking.

Thinking operationally (or "pretending to be the computer") is problematic because there are typically an exponential number of paths through a program. As a result, it is impossible to completely understand even middling small program. Further, operational approaches provide no particularly good strategies for developing programs.

If you can get past the initial visceral revulsion at the thought of proving programs correct (Horrors!), thinking axiomatically has significant benefits. On one hand, it reduces the exponential number of paths through the program to a linear number of positions in the program text. For example, if you have a block of program text s which, in a program state p is guaranteed to arrive at another state q, and likewise program text t going from q to r, then you have s;t going from p to r; it doesn't matter what happens in the middle. Further, axiomatic thinking does provide some guidance to writing code: if you think you need a conditional statement, then you want to go from p to some narrow, definite state q; if you need a loop, then you can look for an invariant and a termination condition. Not easy, but there is something

On the other hand, in functional languages (and also when taking functional approaches in a non-functional language), it is very important to think equationally: "This means that; this other thing is that...." This is especially true in Haskell, which is not strict; if you try to think operationally or even axiomatically, you run into difficulties when the state of a non-strict program does not resemble the state of a strict program.

Equational thinking completely does away with the "number of paths" argument. A functional definition is, or should be, small enough to understand directly, based on any underlying definitions. Further, because the state does not change (in operational terms, or equivalently in axiomatic terms, there is only one state), it becomes less important to manipulate the program as a whole. Instead each definition can be dealt with separately.

Now, equational thinking is easy for stuff like

\[\textbf{add_one}\ n = n + 1\]

But it is not immediately apparent how that extends to something that needs recursion, say. The big "Ah-ha!" moment for me was the realization that recursion and mathematical induction are the same thing (ok, it's not a surprise for anyone; the big deal was when I internalized it enough to use the idea to naturally write code). With that, you can deal with anything programmatically equational and recursive as mathematically equational and inductive. The change in thinking is as big as the difference between operational and axiomatic.

Equational thinking extends beyond basic function definitions; I think it is the key to the type system, classes, and most of the other neat language features. At this point, I am still struggling with category theory, although I have been able to make use of monads reasonably elegantly (in my (humble) opinion, of course). I think there is another step there, although I haven't made it.

This is all rather fuzzy and exceptionally difficult to put into words. However, I am willing to change my traditional definition, Programming is applied formal logic, to include at least abstract algebra and category theory at this point, though.

Speaking of Peano arithmetic...

2010-12-15T14:36:00.000-06:00

Objection 8. Peano's axioms are clearly nonsense: Let f be a bijection from the supposed $N_0$ to a set of filing cabinets. Lock f(0) and put the key in f(1), lock f(1) and put the key in f(2), and continue by induction. Now all the cabinets are locked, with their keys locked inside their neighbors. That is obviously impossible. Hence $N_0$ does not exist.

Reply to Objection 8. Filing cabinets are not mathematics.

"Arithmetic", Mathematics Made Difficult. Carl E. Linderholm, The World Publishing Company, 1971; p. 19.

In other news, I just discovered the worst idiocy I have ever perpetrated in a programming language. For some obscure reason, it apparently seemed a good idea at the time to write,

raStr != null ? "false".equalsIgnoreCase(raStr) : true;

As a result, to get this particular parameter to evaluate to false, I need to set the argument to some string other than "false". Nice. Good one there, Tommy.

Measured Finger Trees

2010-12-11T21:01:00.004-06:00

As I wrote a couple of weeks ago about Finger Trees,

Finger trees combine several features that make them incredibly useful, including [functional] purity, flexibility, efficiency, and simplicity.

A large portion of those advantages spring from the structure of the finger trees themselves, which provide efficient, purely functional deque operations and concatenation. While I was working on completing my finger tree implementation, I began to wonder how it achieved its efficiency, specifically the efficient concatenation. Hinze and Paterson say,

It is easy to check that in each of the invocations of [foldWings], the list argument has length at most 4, so each of these invocations takes Θ(1) time. The recursion terminates when we reach the bottom of the shallower tree, with up to 4 insertions, so the total time taken is Θ(log(min{n1 , n2})), where n1 and n2 are the numbers of elements in the argument trees.

...which is a little too telegraphic for me. The problem is that, in order to get the log n behavior, the tree must be balanced, and no operation in building the finger tree explicitly keeps the tree balanced. Then, I realized that the the structure of the tree it self performed that magic.

Consider a normal binary tree where each node has a data element and two children, and the element in the node is greater than any value under its left child and less than any value under its right child. If the tree is complete, then it is balanced; every internal node has two children, so an operation that traverses from the root of the tree to a specific leaf visits log n nodes. However, if the tree was built from a sorted sequence with no effort at keeping it balanced will structurally resemble a linked list, and an operation attempting to find a specific node will visit n nodes. As a result, with no effort to keep the tree balanced, the worst-case behavior of tree operations will be O(n), not O(log n).

So, what does it mean to be balanced? There are several possibilities; a complete tree is obviously balanced. For finger trees, however, I think the best definition lies in the number of elements at a depth k as compared to depth k-1. For example, continuing with the complete binary tree, the number of elements at depth 0 is 1, the root element. The number of elements at depth 1 is 2; the number at depth 2 is 4; and the number at depth 3 is 8. The number of elements grows exponentially with depth.

Now look at the structure of the finger tree. The spine of the finger tree, where the depth of the structure lies, is not made of a collection of elements, but a collection of 2-3 tree Nodes of the elements of the current level. To put it another way, the first layer of the finger tree contains elements of type T, in the Empty or Single form or in the two Digits; the second layer contains Node<T> elements, and the third layer contains Node<Node<T>> elements. Now, assume that the tree is made entirely of instances of Deep, with a terminal spine of Empty, and that the digits are minimal, in the sense of having the fewest possible contents. At depth 0 are 2 elements of type T. At depth 1 are two elements of type Node<T>, each containing at least 2 elements of type T for a total of at least 4 elements of type T. At depth 2 are two elements of type Node<Node<T>>, containing a total of 8 elements of type T.

As a result of its structure, even in the case of this minimal tree, the number of elements grows exponentially with depth. The finger tree is balanced by its structure with no explicit operations to keep it balanced.

Of course, part of that structure is the guarantee that only elements at each end are easily accessible. But the other half of the finger tree remedies that....

Measurement

I have no intention of trying to provide an insightful lesson into the use of monoids, which when combined with the finger tree make the data structure a very powerful too. For that, check out Monoids and Finger Trees by Heinrich Apfelmus. Instead, I intend to just describe how the monoids and measures work with the Java finger trees.

What is a monoid? On one hand, it is a triple of a set of values, called a carrier set, an operation which is closed in the carrier set as well as being associative, and a specific value from the carrier set which is an identity. On another hand, it is an implementation of the following interface.

public interface Monoid<T>
{
  public T zero();
  public T plus(T l, T r);
}

With, of course the same property requirements and where T is the carrier set. For a standard example of monoids, there are

  public static class IntegerAdd implements Monoid<Integer>
  {
    @Override public Integer plus(Integer l, Integer r) { return l + r; }
    @Override public Integer zero() { return 0; }
  }

integers as the carrier set with addition as the operation and 0 as the identity form a monoid. Also,

  public static class IntegerMult implements Monoid<Integer>
  {
    @Override public Integer plus(Integer l, Integer r) { return l * r; }
    @Override public Integer zero() { return 1; }
  }

integers with multiplication (as "plus", the operation) and 1 (as the zero) form another monoid. ("1 is the zero of multiplication." I dedicate that sentence to my four (!) calculus instructors at the University of Texas at Austin, who are probably rolling in their graves at the thought of me discussing mathematics (even though I don't think any of them are dead).)

Anyway, with a monoid, the next thing I need to build is a Measure,

public abstract class Measure<T, V> implements Monoid<V>
{
  public final Monoid<V> monoid;
  public Measure(Monoid<V> monoid) { this.monoid = monoid; }
  @Override public V plus(V v1, V v2) { return monoid.plus(v1, v2); }
  public V plus(V v1, V v2, V v3) { return monoid.plus(v1, monoid.plus(v2, v3)); }
  @Override public V zero() { return monoid.zero(); }
  public abstract V measure(T t);
}

A Measure<T,V> is a monoid over a carrier set V, based on a lower level monoid which is passed as an argument to the Measure's constructor. The measure adds two operations. One is a three-argument plus method, which is safe due to the properties of the monoid and very convenient. The other is the method measure, which takes an element of a type T and projects that element into the carrier set, V. To put that another way, measure constructs a tag value for the T element as required by the ultimate data structure being constructed from the finger tree.

An example Measure is

  public static class Counter<T> extends Measure<T,Integer>
  {
    public Counter() { super(Monoids.INTEGER_ADD); }
    @Override public Integer measure(T t) { return 1; }
  }

The Counter projects elements of T into the carrier set Integer by returning 1; with the Integer addition monoid, this measure counts the elements in a measured data structure.

Following along Hinze and Paterson, Digits are relatively unchanged, although they do now carry a reference to a Measure used to compute measure tags for the Digit instances. Nodes, on the other hand, also carry a tag value

  public final V tag;

representing the measure of the contents of the Node. Likewise the Empty, Single, and Deep classes have tag fields. The tag of Empty is the zero of the monoid, while Single and Deep are tagged with the plus-combination of the tags of the contained elements.

Besides managing the tag values, what can you do with a measured finger tree? How about splitTree?

  public abstract Split<MeasuredFingerTree<T,V>,T,V> splitTree(Predicate<V> p, V i);

A Split of a finger tree is a triple containing two finger trees and a designated value. If you have a finger tree representing a sequence of elements $t_i$ tagged with measures $v_i$,
\[ (t_0,v_0), (t_1,v_1), \ldots, (t_n,v_n) \]
as well as a monotonic predicate p over V and an initial V value i, splitTree creates a Split structure containing
\[ [ (t_0,v_0), \ldots, (t_{j-1},v_{j-1}) ], t_j, [ (t_{j+1},v_{j+1}), \ldots, (t_n,v_n) ] \]
where $p(i + v_0 + \ldots + v_{j-1}) \equiv \textbf{false})$, but $p(i + v_0 + \ldots + v_j) \equiv \textbf{true})$. In other words, splitTree divides the finger tree into a prefix where the predicate p is false, a designated value where p becomes true, and a suffix, where p remains true if it is monotonic. (For more on monotonic predicates, see apfelmus' article; basically it means the predicate is false up to some value where it becomes true and remains true for all further values. All modulo the monoid, of course.)

A predicate is an implementation of the interface

public interface Predicate<V>
{
  public boolean apply(V v);
}

and an example is

final int half = max/2;
new Predicate<Integer>() { @Override public boolean apply(Integer v) { return half < v; } };

where max is the number of elements in a given collection. Given the Counter measure, this predicate can split a tree in half.

The splitTree method is implemented by Empty as

    @Override public Split<MeasuredFingerTree<T,V>, T, V> splitTree(Predicate<V> p, V i) { throw new IndexOutOfBoundsException(); }

In other words, and Empty finger tree cannot be split. For Single, the implementation is

    @Override
    public Split<MeasuredFingerTree<T, V>, T, V> splitTree(Predicate<V> p, V i)
    {
      MeasuredFingerTree<T, V> empty = empty(measure);
      return new Split<MeasuredFingerTree<T, V>, T, V>(empty, t, empty);
    }

(Hinze and Paterson put some preconditions on the operation:

Note also that the preconditions $\neg p.i$ and $p.(i + t)$ are used only if the split occurs at one or other end of the sequence. Consequently, if we treat those cases specially it suffices to require that the initial tree t is non-empty....

which is reflected in the assumption that a Single element represents the right place to split.)

For Deep instances, splitTree is

    @Override
    public Split<MeasuredFingerTree<T,V>,T,V> splitTree(Predicate<V> p, V i)
    {
      final V vpr = measure.plus(i, left.measure());
      if (p.apply(vpr))
      {
        final Split<Digit<T,V>,T,V> spl = left.splitDigit(p, i);
        MeasuredFingerTree<T,V> prefix = empty(measure);
        for (T t : spl.prefix()) { prefix = prefix.addLast(t); }
        final MeasuredFingerTree<T,V> suffix = deep(spl.suffix(), spine, right);
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, spl.current(), suffix);
      }
      final V vm = measure.plus(vpr, spine.tag);
      if (p.apply(vm))
      {
        final Split<MeasuredFingerTree<Node, V>, Node<T,V>, V> splSpine = spine.splitTree(p, vpr);
        final Split<Digit<T,V>,T,V> splDigit
            = splSpine.current().toDigit().splitDigit(p, measure.plus(vpr, splSpine.prefix().tag));
        final MeasuredFingerTree<T,V> prefix = deep(left,splSpine.prefix(), splDigit.prefix());
        final MeasuredFingerTree<T,V> suffix = deep(splDigit.suffix(), splSpine.suffix(), right);
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, splDigit.current(), suffix);
      }
      else
      {
        final Split<Digit<T,V>,T,V> spl = right.splitDigit(p, vm);
        MeasuredFingerTree<T,V> suffix = empty(measure);
        for (T t : spl.suffix()) { suffix = suffix.addLast(t); }
        final MeasuredFingerTree<T,V> prefix = deep(left, spine, spl.prefix());
        return new Split<MeasuredFingerTree<T,V>,T,V>(prefix, spl.current(), suffix);
      }
    }

The first branch is taken if the split point is in the left Digit, the second if the split point is in the spine, and the third if the split point is in the right Digit. The first and third branches are symmetric. The second branch first splits the spine (producing splSpine), then converts the designated element (which is a Node<T>, remember) to a Digit and splits it to get the designated element and partial prefixes and suffixes to be added to the original edge digit and the prefix and suffix spines. All three branches use a specialized Deep constructor, the deep method, which correctly handles the possibility of empty Digits. (Under normal circumstances, the invariant of Digits includes that they are non-empty.)

Because of the balanced nature of the finger tree, this method can only recurse into the spine log n times; the other operations are constant time; as a result this method is O(log n).

I will post links to the code soon, after I have played with it some more. In the mean time, I did find an implementation of finger trees in the Functional Java library.

More Phantom Types in Java

2010-12-09T18:30:00.001-06:00

Text unabashedly stolen from Ralf Hinze, Fun with Phantom Types.

Introducing phantom types

Suppose you want to embed a simple expression language in Haskell. You are a firm believer of static typing, so you would like your embedded language to be statically typed, as well. This rules out a simple Term data type as this choice would allow us to freely mix terms of different types. Idea: parameterize the Term type so that Term $\tau$ comprises only terms of type $\tau$.

Zero :: Term Int
Succ, Pred :: Term Int $ \rightarrow $ Term Int
IsZero :: Term Int $\rightarrow$ Term Bool
If :: $\forall\alpha$. Term Bool $\rightarrow$ Term $\alpha \rightarrow$ Term $\alpha \rightarrow$ Term $\alpha$

Alas, the signature above cannot be translated into a data declaration[...in un-extended Haskell 98. It can be done with Generalized Abstract Data Types.]

Idea: augment the data construct by type equations that allow us to constrain the type argument of Term.
\[
\begin{equation}\begin{split}
\textit{data}\ \textit{Term}\ \tau & = & \textit{Zero}\ & \textit{with}\ \tau = \textit{Int} \\
& | & \textit{Succ (Term Int)} & \textit{with}\ \tau = \textit{Int} \\
& | & \textit{Pred (Term Int)} & \textit{with}\ \tau = \textit{Int} \\
& | & \textit{IsZero (Term Int)} & \textit{with}\ \tau = \textit{Bool} \\
& | & \textit{If (Term Bool)} (\textit{Term}\ \alpha) (\textit{Term}\ \alpha) & \textit{with}\ \tau = \alpha
\end{split}\end{equation}
\]
Thus, Zero has [type Term $\tau$] with the additional constraint $\tau$ = Int.

NB. The type variable does not appear on the left-hand side; it can be seen as being existentially quantified.

Here is a simple interpreter for the expression language. Its definition proceeds by straightforward structural recursion. Even though eval is assigned the type $\forall\tau.\textit{Term}\ \tau\rightarrow\tau$, each equation has a more specific type as dictated by the type constraints. The interpreter is quite noticeable in that it is tag free. If it receives a Boolean expression, then it returns a Boolean.

I apologize for the Peano arithmetic, but, really, it's not my fault.

  public static abstract class Term<T>
  {
    public abstract T eval();
  }
  
  public static class Zero extends Term<Integer>
  {
    @Override public Integer eval() { return 0; }
  }
  
  public static class Succ extends Term<Integer>
  {
    public final Term<Integer> pred;
    public Succ(Term<Integer> pred) { this.pred = pred; }
    @Override public Integer eval() { return 1 + pred.eval(); }
  }
  
  public static class IsZero extends Term<Boolean>
  {
    public final Term<Integer> i;
    public IsZero(Term<Integer> i) { this.i = i; }
    @Override public Boolean eval() { return i.eval() == 0; }
  }
  
  public static class If<A> extends Term<A>
  {
    Term<Boolean> test;
    Term<A> t, f;
    public If(Term<Boolean> test, Term<A> t, Term<A> f) { this.test = test; this.t = t; this.f = f; }
    @Override public A eval() { return test.eval() ? t.eval() : f.eval(); }
  }
  
  public static     Term<Integer> zero()                  { return new Zero(); }
  public static     Term<Integer> succ(Term<Integer> i)   { return new Succ(i); }
  public static     Term<Boolean> isZero(Term<Integer> i) { return new IsZero(i); }
  public static <A> Term<A>       iff(Term<Boolean> test, Term<A> t, Term<A> f)
                                    { return new If<A>(test, t, f); }

  public static void main(String[] args)
  {
    Term<Integer> iff = iff(isZero(succ(zero())), zero(), succ(zero()));
    System.out.println(iff.eval());
    // Fails to compile with: The method isZero(Eval.Term<Integer>) in the type Eval is
    // not applicable for the arguments (Eval.Term<Boolean>)
    // isZero(isZero(zero()));
  }

The type Term $\tau$ is quite unusual.
Term is not a container type: an element of Term Int is an expression that evaluates to an integer; it is not a data structure that contains integers.
We cannot define a mapping function $ (\alpha\rightarrow\beta) \rightarrow (\textit{Term}\ \alpha\rightarrow\textit{Term}\ \beta) $ as for many other data types.
The type Term $\beta$ might not even be inhabited: there are, for instance, no terms of type Term String.
Since the type argument of Term is not related to any component, we call Term a phantom type.

Hinze's definition of phantom type is different from what I would call a phantom type. Instead of calling Term a phantom type, I would refer to Integer in Term<Integer> as a phantom type, in the definition of Zero. In that case, although the return value of eval is an Integer, the type Integer does not play any other role in the structure of the Zero type. In other words, the type Integer does not appear on the right-hand side of Zero values; nor does Boolean appear on the right-hand side of IsZero, except in the return value of eval.

Quote o' the Day: Open sores

2010-11-30T13:59:00.001-06:00

Being 'open source' is a sign that an operating system will be inexpensive, adaptable and far less restricted than a closed platform like iOS. Having open sores is a sign of severe medical / hygiene issues.

From techeye.net, Nokia's MeeGo is doomed.

Thanks, Del.

Finger Trees

2010-11-25T23:29:00.005-06:00

I want to take a minute to think about finger trees.[1]

Ralf Hinze and Ross Paterson published "Finger trees: a simple general-purpose data structure" in the Journal of Functional Programming in 2006, and since then it has become relatively famous in functional programming circles as, as someone put it, "a data structure in a can". Finger trees combine several features that make them incredibly useful, including

purity; finger trees are a purely functional data structure,
flexibility; finger trees can be used as the basis for a host of more specialized data structures,
efficiency; finger trees provide efficient implementations of a number of operations, and
simplicity; like most extra fancy data structures, finger trees are more tedious than complex, and their relatively simple structure even reduces the complexity.

Until now, however, I have not seen any implementations in Java. Let's see what we can do about that.

But first...

I want to make a quick digression about purely functional data structures. A purely functional data structure is one which does not provide nor make use of modification operations. The most common example of a purely functional data structure is a singly-linked list, as seen in Lisp and other functional languages. These structures have a number of advantages over traditional data structures: they are "persistent", in the sense that an update to the structure creates a new structure, leaving the original unchanged; and they are almost automatically thread safe. However, they have had problems achieving the performance of traditional structures. For example, while a non-functional hash table can provide best-case O(1) lookups, a search tree cannot normally provide better than O(log n) lookups.

2-3 trees

Several of the discussions about finger trees such as apfelmus' and Good Math, Bad Math's have focused on the interaction of monoids with tree structures; that is certainly where finger trees get much of their flexibility, but I think missing the first half of the solution Hinze and Paterson present is a significant loss. For one thing, bare finger trees by themselves support efficient, amortized O(1) deque operations (accessing the first and last elements) as well as O(log n) sequence concatenation.

Finger trees, as originally described, are based on a form of search tree called a 2-3 tree. 2-3 trees are a little-known (to me, at least) variant designed for simplicity in keeping trees balanced. A 2-3 tree consists of

an empty tree,
a tree with a single value
a tree made of nodes, each of which has either two or three values and two or three child links.

Part of Hinze and Paterson's improvement involves modifying the base 2-3 tree to provide "fingers" akin to Gérard Huet's zippers. These fingers provide efficient access to one to four elements on either end of the structure, while the remainder of the tree creates a "spine" down the center of the structure. As an end result, a finger tree consists of two collections of 1 to 4 elements, the first and last few elements of the collection, and a central spine made of a tree of 2-3 tree nodes of elements.

Digits

In this implementation, the "fingers" are instances of Digit (there is a pun there somewhere, but I am not sure I understand it). A Digit is a non-empty sequence of one to four elements. My original implementation used separate subclasses for the four possibilities, but that seemed excessively verbose.

public class Digit<T> implements Iterable<T> {
  private final int length;
  private final List<T> contents;

Instead, I have implemented the Digits using a list in order to share the implementation. (I used the alternate approach on the Nodes below.)

Methods like length(), isEmpty(), and get() are straightforward.

public int length() { return length; }
  public boolean isEmpty() { return length == 0; }
  public T get(int index) { return this.contents.get(index); }

On the other hand, because a Digit is necessarily a functional data structure, head()[2] (which returns a Digit containing all but the last element of this Digit) may seem a little strange.

public Digit<T> head() { return new Digit<T>(this.contents.subList(0, this.length - 1)); }

This method creates and returns a new digit instance containing the first length-1 elements of this Digit; the method tail() is symmetrical. These methods as written may not preserve the invariant of Digit, that there is at least one element.

Likewise, append() and prepend return new Digits. The constructors do ensure that the length invariant is established.

public Digit<T> append(T t) { return new Digit<T>(this.contents, t); }

I also implemented a small number of collect() static methods to create Digits from zero to four elements.

public static <T> Digit<T> collect(T t1, T t2) { return new Digit<T>(Arrays.asList(t1,t2)); }

The remainder of the Digit class consists of the Iterable<T> implementation and assorted constructors.

Nodes

The Node class is the implementation of the 2-3 tree internal nodes; for reasons that probably made sense at the time, I wrote the 2-nodes and 3-nodes as separate subclasses of a general Node class.

public abstract class Node<T> {
  public abstract Digit<T> toDigit();

Fortunately, the only method converts a Node to a Digit with the same elements.

Two static methods provide easy constructors for Node2s and Node3s. (These serve the same function as Digit's collect(), which originally worked the same way.

public static <T> Node<T> two(T x, T y) { return new Node2<T>(x,y); }
  public static <T> Node<T> three(T x, T y, T z) { return new Node3<T>(x,y,z); }

The Node2 and Node3 classes are about as simple as possible.

private static class Node2<T> extends Node<T>
  {
    public final T x, y;

    public Node2(T x, T y)
    {
      this.x = x;
      this.y = y;
    }

    @Override public Digit<T> toDigit() { return Digit.collect(x, y); }
  }

Finger tree

The base finger tree provides efficient implementations of the deque operations: accessing, adding, and removing elements from each end of a sequence. It adds implementations of sequence concatination. The interface is below.

public abstract class FingerTree<T>
{
  public abstract boolean isEmpty();

  public abstract FingerTree<T> push(T t);  
  public abstract FingerTree<T> pop();
  public abstract T top();
  
  public abstract FingerTree<T> unshift(T t);
  public abstract FingerTree<T> shift();
  public abstract T bot();

  public abstract FingerTree<T> append(FingerTree<T> other);
  public abstract FingerTree<T> prepend(FingerTree<T> other);

Notice that the deque operations come in trios: push() adds an element and pop() removes an element with both returning a new, modified FingerTree, and top() returns the last element in the sequence without changing the sequence. (Keep in mind I am misusing the words "add", "remove", and "modified"; the original FingerTree is still available and the new, returned tree shares as much of the structure of the original as possible.)

Empty

The FingerTree is implemented as three classes, Empty representing an empty tree, Single representing a tree containing one element, and Deep representing a tree containing more than one element. The Empty and Single classes are very simple; Empty is below.

public static class Empty<T> extends FingerTree<T>
  {
    @Override public boolean isEmpty() { return true; }

    @Override public Single<T> push(T t) { return new Single<T>(t); }
    @Override public FingerTree<T> pop() { throw new IllegalStateException(); }
    @Override public T top() { throw new IllegalStateException(); }
    // ...
    @Override public FingerTree<T> append(FingerTree<T> other) { return other; }
    @Override public FingerTree<T> prepend(FingerTree<T> other) { return other; }
  }

The implementations of shift(), unshift(), and bot() are identical to push(), pop(), and top().

Single

Single is very nearly as simple.

public static class Single<T> extends FingerTree<T>
  {
    public final T t;

    public Single(T t) { this.t = t; }

    @Override public boolean isEmpty() { return false; }

    @Override public FingerTree<T> push(T n)
      { return new Deep<T>(Digit.collect(t), new Empty<Node<T>>(), Digit.collect(n)); }

    @Override public T top() { return t;  }

    @Override public FingerTree<T> pop() { return new Empty<T>(); }
    // ...
    @Override public FingerTree<T> append(FingerTree<T> other) { return other.unshift(t); }
    @Override public FingerTree<T> prepend(FingerTree<T> other) { return other.push(t); }
  }

The important method is push() (and unshift()), which introduce Deep, the class which implements the trio of left and right Digits and central FingerTree spine. The important detail is that, while the new Deep object is a collection of T, the spine FingerTree is a collection of Node<T>.

Deep

Deep is indeed the magic ingredient of the FingerTree. As expected, it consists of left and right Digit<T> and a centeral FingerTree<Node<T>> spine.

public static class Deep<T> extends FingerTree<T>
  {
    public final Digit<T> left;
    public final FingerTree<Node<T>> spine;
    public final Digit<T> right;

    public Deep(Digit<T> l, FingerTree<Node<T>> s, Digit<T> r)
    {
      this.left = l;
      this.spine = s;
      this.right = r;
    }

    @Override public boolean isEmpty() { return false; }

    @Override public T top() { return right.get(right.length() - 1); }

    @Override
    public FingerTree<T> push(T t)
    {
      if (right.length() < 4)
      {
        return new Deep<T>(left, spine, right.append(t));
      }
      else
      {
        Node<T> node = Node.three(right.get(0), right.get(1), right.get(2));
        return new Deep<T>(left, spine.push(node), Digit.collect(right.get(3), t));
      }
    }

In the push() method, if the current length of the right Digit is less than four, the new element t can be handled by adding it to the Digit. If the right Digit is already full, it must be broken into the first three elements, which are placed in a Node<T> and pushed onto the spine, and the fourth and new elements, which become the contents of the new right Digit.

push() demonstrates one of the principles that makes FingerTrees efficient. Adding a new element to a FingerTree is O(1) 2/3 of the time, when the new element fits in the terminal Digit; it only needs to recurse 1/3 of the time. As a result, amortized over a number of operations, the push() (and the other deque operations) are O(1). Hinze and Paterson say,

Each deque operation may recurse down the spine of the finger tree, and thus take Θ(log n) time in the worst case. However, it can be shown that these operations take only Θ(1) amortized time, even in a persistent setting. The analysis is essentially the same as Okasaki’s for implicit deques (Okasaki, 1998). We outline the main points here.

We classify digits of two or three elements (which are isomorphic to elements of type [Node<T>]) as safe, and those of one or four elements as dangerous. A deque operation may only propagate to the next level from a dangerous digit, but in doing so it makes that digit safe, so that the next operation to reach that digit will not propagate. Thus, at most half of the operations descend one level, at most a quarter two levels, and so on. Consequently, in a sequence of operations, the average cost is constant.

In other words, while any specific operations may require O(log n) operations, a large number of sequential operations will behave appear to be O(1).

The pop() method is longer, but not any more difficult. It has three cases:

If the right Digit has more than one element, the new FingerTree can be built by dropping the rightmost element.
If the right Digit has only one element, that element can be dropped and a new FingerTree constructed by pulling the rightmost Node from the spine and unpacking it into the right Digit.
If the right Digit has only one element and the spine is empty, then pop() must redistribute elements from the left Digit, potentially making the new FingerTree an instance of Single.

@Override
    public FingerTree<T> pop()
    {
      if (right.length() > 1)
      {
        return new Deep<T>(left, spine, right.head());
      }
      else if (!spine.isEmpty())
      {
        return new Deep<T>(left, spine.pop(), spine.top().toDigit());
      }
      else
      {
        switch (left.length())
        {
        case 1:
          return new Single<T>(left.get(0));
        case 2:
          return new Deep<T>(Digit.collect(left.get(0)),
                                spine,
                                Digit.collect(left.get(1)));
        case 3:
          return new Deep<T>(Digit.collect(left.get(0)),
                                spine,
                                Digit.collect(left.get(1), left.get(2)));
        case 4:
          return new Deep<T>(Digit.collect(left.get(0), left.get(1)),
                                spine,
                                Digit.collect(left.get(2), left.get(3)));
        default:
          throw new IllegalStateException();
        }
      }
    }

The analysis of pop() is similar to that of push().

Concatenation

In addition to the deque operations, Deep implements sequence concatenation in the form of append() and prepend() (which is symmetric with append()).

@Override
    public FingerTree<T> append(FingerTree<T> other)
    {
      if (! (other instanceof Deep<?>))
      {
        return other.prepend(this);
      }
      else
      {
        Deep<T> o = (Deep<T>) other;
        return new Deep<T>(left, foldWings(this, o), o.right);
      }
    }

In the new FingerTree, the left Digit is the left digit of the appended-to tree, the right Digit is the right digit of of the appended tree, and the spine is built from the remaining two digits and the spines by the foldWings() method.

The foldWings() method first collects all of the elements from the two inner Digits and, arbitrarily choosing the left spine, pushes them into the spine. This process is the task of the while loop in foldWings() and is complicated by the need to break the two to eight elements into Nodes of two or three elements. This code prefers three-element Nodes, and only uses two-element Nodes when either only two elements are left or four elements are left, in which case two two-element Nodes are needed. Finally, the new spine is created and returned, by recursively appending the new left and original right spines.

private static <T> FingerTree<Node<T>> foldWings(Deep<T> port, Deep<T> starboard)
    {
      List<T> fist = new ArrayList<T>(port.right.length() + starboard.left.length());
      for (T t : port.right) { fist.add(t); }
      for (T t : starboard.left) { fist.add(t); }
      int seen = 0;
      int all = fist.size();  /* 2 <= all <= 8 */
      FingerTree<Node<T>> spine = port.spine;
      while (seen < all)
      {
        int diff = all - seen;  /* Initially, 2 <= diff <= 8 */
        if (diff == 2)
        {
          T a = fist.get(seen++);
          T b = fist.get(seen++);
          spine = spine.push(Node.two(a,b));
          /* diff reduced by 2 */
        }
        else if (diff == 4)
        {
          T a = fist.get(seen++);
          T b = fist.get(seen++);
          T c = fist.get(seen++);
          T d = fist.get(seen++);
          spine = spine.push(Node.two(a,b)).push(Node.two(c, d));
          /* diff reduced by 4 */
        }
        else
        {
          T a = fist.get(seen++);
          T b = fist.get(seen++);
          T c = fist.get(seen++);
          spine = spine.push(Node.three(a,b,c));
          /* diff reduced by 3 */
        }
      }
      /*    (port.spine)
         + ("loose" port-right nodes, folded)
         + ("loose" starboard-left nodes, folded)
         + (starboard.spine) */
      return spine.append(starboard.spine);
    }
  }

The analysis of concatenation by Hinze and Paterson is,

It is easy to check that in each of the invocations of [append, the list fist has length at most 8], so each of these invocations takes Θ(1) time. The recursion terminates when we reach the bottom of the shallower tree, with up to 4 insertions, so the total time taken is Θ(log(min{n1 , n2 })), where n1 and n2 are the numbers of elements in the argument trees.

Note that the debit analysis of Section 3.2 remains valid, because although [append] must discharge any debits on the nodes on the spines that are merged, there will be at most Θ(log(min{n1 , n2 })) of these.

Comparisons

Given the analysis of the behavior of finger trees as sequences, how do they actually perform? I ran some quick tests, comparing them with JDK-standard ArrayLists and LinkedLists on element addition, removal, and concatenation. The contents of the sequences were Integers.

Keep in mind that these results are benchmarks (at the lower level of lies, damned lies, statistics, and benchmarks), and are also poorly done benchmarks. I did not use a quiescent machine, I did not "warm up" the program, I did not make any effort to optimize anything, I even ran the things in Eclipse for crying out loud. As a result, they are full of noise, they are not statistically significant (although they were repeatable), and I would not hesitate to disclaim them if someone really wants to complain. But they are kind of interesting.

Push

For inserting elements, I started with a sequence of n elements and timed adding n elements, reporting the time taken divided by n. The additions were performed by

t = t.push(j);         /* FingerTree */
al.add(j);             /* ArrayList */
ll.add(j);             /* LinkedList */

The results are shown in Figure 1.

Figure 1: Adding an element

Yes, the left side of the graph is very inaccurate. Sorry.

I added some guide lines showing log n, n, and $n^2$ performance. I also used log scales for both horizontal and vertical axes, which I really wish more systems researchers used in papers, since otherwise the right half of the graph would be effectively empty.

The primary thing to notice is that the trends of the three lines are roughly the same, and indicate something like O(1) performance, which all three should exhibit.

Pop

For removing elements, I followed a similar process, starting with a sequence of n elements, inserting n more elements and then timing removing those n elements with the following operations:

t = t.pop();                /* FingerTree */
al.remove(al.size() - 1);   /* ArrayList */
ll.remove(ll.size() - 1);   /* LinkedList */

The results are shown in Figure 2.

Figure 2: Removing an element

Concatenation

Comparing concatenation, I concatenated two sequences of n elements 100 times (resulting in some truly huge sequences), reporting the total time. The operations were:

t = t.append(t2);       /* FingerTree */
al.addAll(al2);         /* ArrayList */
ll.addAll(ll2);         /* LinkedList */

The results are shown in Figure 3.

Figure 3: Concatenating sequences

Figure 3 shows the one advantage of finger trees: the slope of the finger tree concatenation line is significantly less than that of the ArrayList or LinkedList; FingerTree looks, in fact, to be roughly log n, while the other two are roughly parallel to n.

With some luck, I will be following this post with another that tells the rest of the finger tree story.

Footnotes

1. Cue Petey Fisk.

2. Think the head and tail Unix commands.

[Edit: fixed Ralf Hinze's and Ross Paterson's names. Darn you, traitorous fingers! Darn you!]

Quote o' the Day: Cloudebauchery

2010-11-23T13:27:00.000-06:00

Two Clouds walk into a bar. Bartender says “Your server will be right with you”.

Knights, knaves, and Program Construction

2010-11-11T20:03:00.001-06:00

I have a confession to make: I was raised in the land of Dijkstra. Although I have posted frequently about exploring Haskell and other functional languages, the lambda calculus is comparatively new to me. Denotational semantics, category theory, generalized algebraic data types, these are all foreign from the approach I first learned: what I learned to call axiomatic semantics. So, when I finally dragged out a copy of Roland Backhouse's Program Construction: Calculating Implementations from Specifications and started reading (I am currently up to chapter five), I was brought back to the long-lost days of my youth, days of Phil. 313k, CS 336, Ham Richards, David Gries, ....

Anyway, chapter five is on calculational logic, using the properties of equality and negation to calculate the logical consequences of propositions. What I found especially entertaining is Backhouse's use of examples from Raymond Smullyan's knights and knaves puzzles to illustrate the principles. The cool part is that so many of the puzzles are so easy to solve using so simple a box of tools: negation, equality, and the properties of equality, transitivity, symmetry, and associativity.

For example

Briefly, these puzzles involve you as a traveler on an island inhabited only by knights, who only tell the truth, and knaves, who only tell lies. Consider the following question from To Mock a Mockingbird:

Question 1: Is it possible for any inhabitant of this island to claim that he is a knave?

Backhouse points out, "Smullyan's proofs invariably involve detailed case analysis." Case analysis is a very useful technique (in both logic and programming), but it quickly becomes complex and tedious, making it a less preferred alternative. Instead, Backhouse proposes something like the following approach (the example here is mine; don't blame Backhouse):
\[
\begin{equation}\begin{split}
& A \equiv \neg A & \\
\equiv & & \{ \textrm{Def. negation} \}\\
& A \equiv A \equiv \textbf{false} \\
\equiv & & \{ \textrm{Assoc., def. const. true} \}\\
& \textbf{true} \equiv \textbf{false} \\
\equiv & & \{ \textrm{Simpl.} \}\\
& \textbf{false}
\end{split}\end{equation}
\]

The initial formalization of the question begins with a native, named A; the logical proposition $A$ indicates, "A is a knight", and the formalization of any statement by A begins, $A \equiv \ldots$ because the entire statement will be true if and only if A is a knight. Therefore, the original equation can be read, "A is a knight if and only if A is a knave" or as "The statement 'A is a knave' is true if and only if A is a knight." The final statement, $\textbf{false}$, indicates that no inhabitant of this island can claim he is a knave. In Smullyan's reasoning, that statement would be a lie for a knight and the truth for a knave.

(There are a small stack of identical operations here: equality $=$, equivalence $\equiv$, and bi-implication $\leftrightarrow$ (a.k.a. "if and only if", or just "iff"). The first two directly indicate the same thing, that the thing on the left is the same as the thing on the right, but are kept separate because equality applies to any two things: 4, true, a puppy,..., while equivalence is limited to boolean values. This prevents confusion in statements like $4 = 4 = \textbf{true}$, which would mean something completely different parenthesized like $4 = (4 = \textbf{true})$. "Iff" simply has the same logical meaning as equivalence, but sometimes reads easier.)

Here is another example:

Question 4: [Suppose an inhabitant A says about himself and his brother B]: "Exactly one of us is a knave." What type is A and what type is B?

I would formalize the calculation as:
\[
\begin{equation}\begin{split}
& A \equiv A \not\equiv B & \\
\equiv & & \{ \textrm{Def. not equiv.} \}\\
& A \equiv A \equiv \neg B & \\
\equiv & & \{ \textrm{Def. negation} \}\\
& A \equiv A \equiv B \equiv \textbf{false} & \\
\equiv & & \{ \textrm{Def. const. true} \}\\
& \textbf{true} \equiv B \equiv \textbf{false} & \\
\equiv & & \{ \textrm{Assoc., simpl.} \}\\
& B \equiv \textbf{false} & \\
\equiv & & \{ \textrm{Def. negation} \}\\
& \neg B &
\end{split}\end{equation}
\]

The answer to the question is that B is a knave, but the statement gives no information about A.

The astute reader will notice that I skipped a few questions there. I had to because, after a good bit of thought I have no idea how to formalize "...to claim that he and his brother are both knaves" or "at least one of us is a knave" using only equivalence and negation. On the other hand, they can easily be formalized using conjunction and disjunction. I propose the following reason for my difficulties: it is impossible to express all logical propositions using equivalence and negation. In particular, it is not possible to express the proposition $p \wedge q$.

Define a symmetric proposition to be one where the truth table for the proposition has an even number of true values, where the truth table has one row for each possible combination of truth assignments to the variables of the proposition. Define a asymmetric proposition to be one with an odd number of true values.

$p$ (a single variable) is symmetric. Trust me: true or false.
true and false are symmetric. They have no variables and so no rows in their truth tables.
$p \equiv q$ is symmetric. It is true when both are true or when both are false.
$\neg p$ is symmetric. True is false and false is true.

However, $p \wedge q$ is asymmetric; it is only true in the one case where both $p$ and $q$ are true. An asymmetric proposition cannot be built with only symmetric components. (This argument could be formalized by induction on the structure of propositions.)

This matters...why?

This stuff, besides being an opportunity to play with MathJax, is valuable for a number of reasons: On the one hand, programs are proofs. Quite beyond the Curry-Howard correspondence, programs and formal proofs have a great deal in common, including the amount of detail required and the advantages of abstraction. Further, and more specifically, axiomatic semantics are fundamentally how I understand programs, particularly imperative programs in languages such as Java. (Axiomatic semantics are somewhat less useful in Haskell or Prolog, probably giving rise to the difficulties I have had with them over the years.)

Further, the ability to reason closely is somewhat important to a programmer. When I started, I did not know that conjunction could not be expressed using equivalence and negation; given the proof sketch I gave above, I am still not sure. I would bet that someone has proved it one way or another, but I am not familiar with that proof and could not easily find it. However, I have convinced myself, and have done so using basically the same techniques I used when I was fooling with a weird string fiddling problem in Java last weekend.

Expect more faffing about with proofs soon.

Subclassing and Java Generics, revisited

2010-11-03T17:08:00.001-05:00

Last summer, I wrote a post working through the relationship between subtyping and generics in Java. Unfortunately, I never really related my conclusions to Java as it is spoken in the wild. The topic came up again, and once again I not only could not remember the ideas, I couldn't even remember the words.

Specifically, the problem started with an attempt to create a Map whose values were themselves Maps.

Map<String, Map<String,String>> map = new HashMap<String, HashMap<String,String>>();

(The red highlighted code will not compile and shows the cute little red underline in Eclipse.)

The question became one of generics and subtyping with the following attempt to fix the error, which appears to work but just pushes the error down to the use of the map.

Map<String, ? extends Map<String,String>> map = new HashMap<String, HashMap<String,String>>();
map.put("one", new HashMap<String, String>());

The problem there, I think, is that the Java compiler believes the values of map to be some-anonymous-but-concrete subtype of Map<String,String>, and sees the call to put() as an attempt to insert a HashMap<String,String> into a position requiring some-anonymous-but-concrete subtype of Map<String,String>, which does not match HashMap<String,String>. Or something like that.

The ultimate fix is to un-typo the HashMap constructor call in the original assignment to map, leaving the values of the map to be generic Map<String,String>'s rather than specific HashMaps.

Map<String, Map<String,String>> map = new HashMap<String, Map<String,String>>();
map.put("one", new HashMap<String, String>());

Class structure

Anyway, my purpose here is to recreate my table of what works and what does not using actual Java code rather than the pseudo-Java examples of my previous post. The class structure I need to work with is:

public class A { }
public class B extends A { }
public class C extends A { }

To briefly recap my previous post, given those class definitions where B is a subtype of A (or, B <: A),

List can be used as a subtype of List<A> (or List <: List<A>), which is described as a covariant use,
List<A> can be used as a subtype of List (or List<A> <: List), which is described as a contravariant use, or
List<A> and List can be entirely unrelated and cannot be interchanged, which is described as invariant.

The two important variations are covariance and contravariance (in C++ with templates, as far as I know, generics are treated as invariant, which is entirely reasonable if somewhat less featuriferous).

Whether covariance or contravariance works depends on how the subtype relationship is being used. Now, by "works" I mean "is guaranteed not to result in runtime errors". Further, by "how the subtype relationship is being used", I mean "whether information is being inserted or extracted from the generic type".

The following table shows the four possibilities, with resulting errors. (I have highlighted the extends/super keywords to show the relationship with covariance and contravariance.) Each quadrant of the table contains two methods. The first, top method has a generically typed, covariant- or contravariant-use parameter, which potentially shows a compile-time error. The second, bottom, method shows code that uses the top method to either insert or extract an element from a List.

	Covariant	Contravariant
Extraction	public A covExtInner(List<? extends A> as) { return as.get(0); } public void covariantExtraction() { List<B> bs = new ArrayList<B>(); bs.add(new B()); A a = covExtInner(bs); }	public B conExtInner(List<? super B> bs) { return bs.get(0); } public void contravariantExtraction() { List<A> as = new ArrayList<A>(); as.add(new A()); B b = conExtInner(as); }
Insertion	public void covInsInner(List<? extends A> as, A a) { as.add(a); } public void covariantInsertion() { List<B> bs = new ArrayList<B>(); A a = new A(); covInsInner(bs, a); }	public void conInsInner(List<? super B> bs, B b) { bs.add(b); } public void contravariantInsertion() { List<A> as = new ArrayList<A>(); B b = new B(); conInsInner(as, b); }

Covariant

Contravariant

Extraction

public A covExtInner(List<? extends A> as) {
    return as.get(0);
  }
  
  public void covariantExtraction() {
    List<B> bs = new ArrayList<B>();
    bs.add(new B());
    
    A a = covExtInner(bs);
  }

public B conExtInner(List<? super B> bs) {
    return bs.get(0);
  }
  
  public void contravariantExtraction() {
    List<A> as = new ArrayList<A>();
    as.add(new A());
    
    B b = conExtInner(as);
  }

Insertion

public void covInsInner(List<? extends A> as, A a) {
    as.add(a);
  }
  
  public void covariantInsertion() {
    List<B> bs = new ArrayList<B>();
    A a = new A();
    
    covInsInner(bs, a);
  }

public void conInsInner(List<? super B> bs, B b) {
    bs.add(b);
  }
  
  public void contravariantInsertion() {
    List<A> as = new ArrayList<A>();
    B b = new B();
    
    conInsInner(as, b);
  }

Valid operations

The upper left and lower right quadrants show valid operations, which are guaranteed not to result in runtime errors and which therefore do not generate compile-time errors.

Covariant extraction

The upper left quadrant shows a List of B's passed to a method which retrieves an element as an instance of A and returns it. Simple and working.

Contravariant insertion

The lower right quadrant shows a List of A's and a B passed to a method that treats the list as if it were a List of some superclass of B, and adds the B instance to it. Once again, works fine.

Invalid operations

The upper right and lower left quadrants show problematic operations, which could potentially cause errors at runtime. The compile-time error is shown in red.

Covariant insertion

The lower left quadrant shows an attempt to write a method with a covariant use which attempts to insert an element. The compiler generates an error on the call to add().

Consider what would happen if the compiler did not flag the call to add(): the method covInsInner would be able to insert any A into the as list; rather than an A, it could insert a C or any other subtype of A. However, the covariantInsertion method that called covInsInner is using a List of B's, and the insertion of anything that is not a B corrupts the list.

Java chooses to flag the call to add() as the error, rather than, say, the call to covInsInner, because the call to covInsInner looks correct: bs is a List of something that extends A. The error arises with the call to add() because as is passed as covariant; the "? extends ..." syntax does not modify A, but rather indicates that the List can be used in a covariant manner. And the call to add() is not a covariant usage.

Contravariant extraction

The upper right quadrant shows an attempt to write a method with a contravariant use which attempts to extract an element. The compiler generates an error on the call to get().

Consider what could happen if the compiler did not flag the call to add(): The conExtInner method could extract a B object from a list of A objects, resulting in a class cast error at runtime.

Java again chooses to flag the call to get() because the type "List<? super B>" marks the List bs as a contravariant usage, and get() is not allowed by that usage.

The bottom line

The syntax "? extends A" marks the type as a covariant usage, allowing collections of subtypes of A to be assigned, but only allowing extraction. The "? super B" syntax marks the type as a contravariant usage, allowing collections of supertypes of B to be assigned, but only allowing insertion. Or, as Naftalin and Wadler put it in Java Generics,

The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you both get and put.

Or, more succintly, extends = covariant = read-only and super = contravariant = write-only.

[Edit] Del just reminded me of a key point: The covariant and contravariant markers might appear to modify the type argument to the generic, but they do not. The type List<? extends ...> controls the usage of the List; it does not affect the contents of the list.

Link o' the day: Meditations on Bluish Coder and inadequacy

2010-10-27T18:24:00.001-05:00

Every once in a while, I run across someone who makes me feel inadequate. (As opposed to the people I work with every day, who make me feel completely adequate.)

Recently, I have been interested in programming languages with dependent data types, mostly because they seem to be the natural end point of type system evolution. (Perhaps "end point" is the wrong term; "next step" may be better.) Unfortunately, most of the dependently typed languages I have seen are unappealing for various reasons.

Epigram seems neat, but the last time I looked at it I seem to recall it only worked within its own IDE. Not a terrible failing, but still.... And version 2 is not out yet.
Agda also seems neat, but for some reason I am having a hard time getting enthusiastic about it.
Coq is neat (there may be a trend here), but as a programming language? Certainly, it is the best computer game I have played in ages, but one issue I have is that I find Coq proofs almost unreadable. It does get lots of extra points for Coq'Art, a truly excellent book.
Many of the others that I have heard about are not actively developed.

However, there is one alternative with a significant feature: ATS has excellent placement in the computer language shootout. (Hey, that's how I found OCaml, which quickly became my last favorite programming language.) Plus, the current implementation is named "Anairiats", which is both cool and enigmatic.

To come back around to the point of this post, I was casting around for more information about ATS, and found Bluish Coder, the blog of Chris Double, who, judging by the tags and posts, seems to have already done most of the things on my to-do list. Scheme in Javascript, ATS, continuations, factor, etc., etc. Worst of all, he's in New Zealand.

Damn, I'm inadequate.

[Edit: Yah, and I can't even remember to tag my posts.]

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.