Paraphrasing Programming Idioms

Program long enough and you start to see the patterns.  Of course, there are whole books written on the subject.  Way back in the day, there was “Programming Pearls”, and various other such have sprouted up since.  In those books you find things like Duff’s device (great for graphics), and other oddities.

I’ve recently been doing a lot of work with Lua as a replacement for C, and as such I’ve been looking at a lot of switch statements, and how to code them.

Lua does not have a switch/case statement as such.  It does support if/then/else[if]/end blocks though, which for the most part are the same thing.  There are a couple of challenges in using this construct though, as compared to the C counterpart.

Here’s what I would consider to be a pathological switch/case statement, with all the goodies, tricks and shortcuts that C has to offer:

int nextstate(s, ch, somestruct)
{
  int newstate = SOME;
  somestruct.error = GOODNESS;

  switch(s)
  {
    case beginning:
      newstate++;
    case midway:
      newstate++;
      break;
    case ending:
      switch(ch)
      {
        case 'a':
          goto error;
        case 'b':
        case 'c':
        case 'd':
          --newstate;
          break;
      }
      break;

    default:
      break;
  }

  return newstate;

error:
  somestruct.error = BADNESS;
  return -1
}

So, let’s see, there’s a label (error:), there’s a case fallthrough (beginning to midway), there’s a switch within a case, there’s that ‘goto’, and there’s a return at the end, after the error: label. that’s enough to give you fits and starts if you’re coding in Lua. Some of the pattern breaks down easily, and other parts are a bit challenging. But, by breaking it down piece by piece, and recoding based on original intention, it becomes possible.

First, that goto. There is no goto in Lua. With a goto like this, the programmer is typically saying “there was an error. Do some cleanup, then exit the function”. OK, well this can be coded more explicitly, and wrapped up in a function. Luckily in Lua, you can embed a function within a function. In fact, that’s how you can create iterators. In this case, the error: label can turn into a function called error. Also, it would be a syntax error to have a return after a return. The Lua runtime will complain about that essentially unreachable code. Without a goto statement, there’s no way to reach that bit of code.

function errfunc()
  somestruct.error = BADNESS;
  return -1
end

The errfunc function has access to the variables that are within the outer function (there’s a name for that ability that escapes me). Therefore, the error function can set the error value of the somestruct. Now that this function is in hand, instead of writing – goto error; we can instead write – return errfunc(); This will cause an immediate return, while calling the errfunc function, which will do the intended cleanup.

I like this because it is more explicity of the original intention, without much black magic. With the goto, you really have no idea what’s going to happen. With the explicit return, as the programmer you are exactly aware of what’s going to happen, and in this case, I think that’s ok. An argument can be made that goto statements are a bad thing. I’m not making that argument, I’m just trying to show how an idiom can be recoded.

Now, for that ‘fallthrough’. What’s really going on is the following. When there are multiple case statements grouped together, it’s essentially saying, ‘in case this1, or this2, or this3, do the following. It’s obvious in this block:

case 'b':
case 'c':
case 'd':
  --newstate;
  break;

This is ‘fallthrough’. To recode this in Lua, I would write it thus:

if ch == string.byte('b') or ch == string.byte('c') or ch == string.byte('d') then
  newstate = newstate - 1;
end -- or elseif, depending on what follows

There are a couple of things to note here. First of all, the ‘fallthrough’ has been dealt with by essentially writing out the implied logic, meaning, the various ‘or’ statements are clearly spelled out, rather than being implied by the case statements being stacked up. Another thing is that Lua does not have character literals. Using the single quotes is the same as using double quotes, so a string is actually being created. In order to get the single byte representation of the character, you have to use the string.byte() function. These literals can be saved off as numbers somewhere so this function call doesn’t have to occur at every turn. Lastly, Lua does not have the auto increment/decrement semantics, so you can’t do ‘–nestate’, you have to be explicit.

That’s a lot of explicity. In some cases it’s good, in some cases it’s just a pain. My fingers have gotten used to typing var++, so having to type var = var + 1 is kind of a drag.

Back to fallthrough. There’s another more subtle fallthrough at the beginning. This one takes a little more thought.

  switch(s)
  {
    case beginning:
      newstate++;
    case midway:
      newstate++;
      break;

Ignoring the ‘newstate++’ that’s right after the ‘case beginning:’, this is exactly the same as the last fallthrough, so it can be coded similarly, but with a slight twist:

if s == beginning or s == midway then
  if s == beginning then
    newstate = newstate + 1
  end

  newstate = newstate + 1;
end

The fact that the first case does not have a ‘break’ (a subtle point easily missed) means that instead of jumping out of the switch statement after executing the ‘newstate++’, the code should continue on, as if the newstate++ wasn’t even there, and execute the next case statement ‘midway’. OK. So, we start off with the or of the two cases, just like with the previous example. But then, within the body, we have to test for the ‘beginning’ case again? Yes. The outer ‘or’ just says “if any of these cases exist”. Within the body, we still have to deal with the cases separately. It’s a bit rough, but this is in fact what’s happening with the case statement in C, it’s just so much black magic that allows it to be expressed in that nice error prone and subtle shorthand.

Pulling it all together:

local byte = string.byte

function nextstate(s, ch, somestruct)
  local newstate = s + 1;
  somestruct.error = GOODNESS;

  function errfunc()
    somestruct.error = BADNESS;
    return -1
  end
  
  if s == beginning or s == midway then
    if s == beginning then
      newstate = newstate + 1;
    end
    newstate = newstate + 1;   
  elseif s == ending then
      if ch == byte('a') then
        return errfunc();
      end

      if ch == byte('b') or ch == byte('c') or
        ch == byte('d') then
          newstate = newstate - 1; 
      end
  else 
      -- do nothing;
  end
  return newstate;
end

And that’s about it. It might not look as compact as the C version, but at least for this particular case, things worked out. There are some more interesting uses of the goto statement which aren’t quite as easy to untangle. In particular, if this were in a for loop, and there were a label at the top of the loop, and the code wants to ‘goto’ that top label. In most cases, some rearrangement of ‘if’ blocks can deal with it, and obviate the need for the goto statements.

The switch/case statement is a workhorse pattern in the C programming lexicon. Realizing the root intentions of the pattern then makes it possible to recode the original intentions where the target language has the necessary facilities to implement those intentions. Luckily, Lua has enough capabilities to allow for this particular programming idiom to be rephrased. Your mileage may vary.

Advertisements

2 Comments on “Paraphrasing Programming Idioms”

  1. Levi Pearson says:

    There actually is goto in lua now, both in the latest luajit2 beta and lua5.2: http://luajit.org/extensions.html#lua52

    • Yah. Now that LuaJIT also has goto, it makes porting typical C code that much easier. I like the constraint of not using goto though. It’s forcing me to program in a way that is different, and possibly better optimisable.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s