Work the Shell

For this article, I thought it would be beneficial to go back to some basics of shell scripting and look at how functions work. Most script writers probably eschew using functions because it's a bit antithetical to how scripts tend to evolve, as a sequence of commands on the command line that are captured in a file.

As with general programming, however, if you have a block of even a few lines that are invoked multiple times, in multiple locations in a script, turning that into a function makes a lot more sense.

The general syntax is thus:

MyFunction() {
  commands to execute
}

Within the main script—or any other functions, or the function itself—a function is invoked by simply referencing its name:

echo "before call to MyFunction"
MyFunction
echo "after call to MyFunction"

Easy enough. Positional parameters are given to the function in a manner exactly analogous to how command flags are handed to the script overall, as $1, $2, $3 and so on.

This means that within a function, I could write:

if [ -n "$1" ] ; then
  echo "I was given $1 as my first parameter"
fi

Well, that's a bit lazy of me, testing $# would be a better way to ascertain if positional parameters were handed to the function, so let's rewrite that as:

if [ $# -gt 0 ] ; then
  echo "I was given $# parameters"
fi

The biggest limitation with shell functions is that they can return an integer value only of 0–127, where a typical script actually utilizes the 0 = false or failure, 1 = true or success. Or, a lot of scripters just ignore return values entirely and use a global variable to pass back values, particularly if they're string values, which otherwise are impossible to deal with in a function.

Functions manipulating global variables is a bit sloppy compared to best practices in Ruby, Java or C++, but you've got to work with what you've got, right?

To make this column more interesting, I'm going to brush off a classic recursion program and see how to make it work as a shell script. The program is called Towers of Hanoi, and you've probably seen a kid's toy for this. It's a set of different sized disks and three pegs, with the goal being to move all the disks from one peg to another while never violating the rule that bigger disks should never be atop smaller ones. If the pegs are labeled 0, 1 and 2, the simplest case of one disk is to simply move it from peg 0 to peg 2. For two, the first (smaller) disk moves from 0 to 1; the second disk moves from 0 to 2, and the first then moves atop it from 1 to 2.

There's an iterative solution that's succinct:

#!/bin/sh
/bin/echo -n "Towers of Hanoi. How many disks? "
read disk
for (( x=1; x < (1 << $disk ); x++ )) ; do
  i=$((($x & $x - 1 ) % 3))
  j=$(((($x | $x - 1 ) + 1 ) % 3))
  echo "Move from tower $i to tower $j"
done

When run, this delightfully short script produces the result I desire, a step-by-step solution to the Towers of Hanoi problem:

Towers of Hanoi. How many disks? 4
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1
Move from tower 0 to tower 2
Move from tower 1 to tower 0
Move from tower 1 to tower 2
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1
Move from tower 2 to tower 0
Move from tower 1 to tower 0
Move from tower 2 to tower 1
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1

It turns out that the solution to n disks is 2**n + 1 steps mathematically. Put succinctly, 20 disks would take a staggering 1,048,577 moves. That's a lot more patience than I would have with a puzzle game; I don't know about you.

The point of introducing the Towers of Hanoi puzzle, however, was to demonstrate a neat recursion trick within a shell script, so let's have a look at how that might work too.

The basic algorithm has three steps:

There are various Web sites with illustrations of how this works, but it just might be easier to present my script so you can see what I'm talking about:

moves=0     # start with no moves
hanoi()
{
    if [ $1 -gt 0 ] ; then
      hanoi "$(($1-1))" $2 $4 $3
      echo move $2 "-->" $3
      moves=$(( $moves + 1 ))
      hanoi "$(($1-1))" $4 $3 $2
    fi
}
/bin/echo -n "Towers of Hanoi. How many disks? "
read disks
hanoi $disks 1 2 3
echo "It took $moves moves to solve Towers for $disks disks."

Notice that there are four parameters that you must give to the recursive Towers of Hanoi function and that you have to “prime the pump” with the initial invocation of:

hanoi $disks 1 3 2

The parameters, in order, are the number of disks and the identity of each of the three pegs you'll be using. For four disks and three pegs, the solution:

Towers of Hanoi. How many disks? 4
move 1 --> 3
move 1 --> 2
move 3 --> 2
move 1 --> 3
move 2 --> 1
move 2 --> 3
move 1 --> 3
move 1 --> 2
move 3 --> 2
move 3 --> 1
move 2 --> 1
move 3 --> 2
move 1 --> 3
move 1 --> 2
move 3 --> 2

It took 15 moves to solve Towers of Hanoi for four disks. Look closely at the code, and you'll realize you actually can use mnemonic names for the pegs by changing the initial invocation near the bottom of the script, which makes the output considerably more understandable as a solution, this time for just three disks:

Towers of Hanoi. How many disks? 3
move source --> temp
move source --> destination
move temp --> destination
move source --> temp
move destination --> source
move destination --> temp
move source --> temp
It took 7 moves to solve Towers of Hanoi for 3 disks.

Although you might not encounter situations where you need to create recursive functions in a shell script, the more general function creation and usage definitely can make your scripts more efficient and easier to understand. And, as for Towers of Hanoi? Well, do you have a better algorithm? It's a staple of computer science education, so I bet a lot of you have tackled this one in the past.

Credit to Kamaraj Subramanian for his iterative Hanoi script and phoxis for his recursive Hanoi script—they proved to be good starting points for my own creations this month.