C言語を憶えたてのころに見たことがある方もたくさんいると思います。 再帰呼び出しのサンプルとして有名な 「ハノイの塔」をシェルスクリプトで書いたものです。速度は期待できません が再帰処理さえも簡単にこなしてしまうシェル言語には目を見張るものがあります。
再帰による「ハノイの塔」の解を求めるスクリプトそのものは簡単なものですが、 このことにこじつけて他のことも併せて説明しようと欲張ったので行数の 多いスクリプトになってしまいました。
listingsitem #!/bin/sh
# Tower of HANOI
#: ${1?Parameter unset}
set -u
sub='./hanoisub'
export sub
trap 'rm -f $sub;exit' 0 1 2 3 15
cat > $sub << 'EOF'
eval X=¥`expr 6 - `expr $2 + $3`¥`
if test $1 -gt 1; then
$sub `expr $1 - 1` $2 $X
fi
echo "Move disk #$1 from $2 to $3."
if test $1 -gt 1; then
$sub `expr $1 - 1` $X $3
fi
EOF
chmod +x $sub
$sub $1 1 2
「ハノイの塔」スクリプトの本質は23行目の $sub $1 1 2 で、$1 には
スクリプトの第１引数としてに与えられた円盤の枚数がセットされています。このあとは
$sub が再帰呼び出しを重ねて解を表示してきます。
サブルーチン $sub の所在は11〜20行目のヒアドキュメント部分です。
サブルーチンをメインのシェルスクリプトに含めておき、実行するときにだけ
サブルーチンをディスクに展開して使用し、
終了時には削除するようにしてあります。
では7行目から見て行きましょう。ここは前準備部分で、サブルーチンとする シェルスクリプト名を定義し、 それを export 宣言(8行目)しサブシェル側に伝わるようにしておきます。 続いて trap 文を使って終了する時には必ずサブルーチンとしてディスクに書き出 したスクリプトを削除するようにしておきます。これをスクリプトの最後に(24行目 あたりに)削除命令を入れておいたのではDELキーによる中断などの時にゴミを残して しまいます。
11行目の cat >$sub << 'EOF' が12〜19行目をサブルーチンとして
ディスクに書き出します。
listingsitem eval X=¥`expr 6 - `expr $2 + $3`¥`
if test $1 -gt 1; then
$sub `expr $1 - 1` $2 $X
fi
echo "Move disk #$1 from $2 to $3."
if test $1 -gt 1; then
$sub `expr $1 - 1` $X $3
fi
$sub を export 宣言した意味がお分かりでしょうか。このサブルー
チンにも同じシェル変数が3行目と7行目に使われています。もし、 export されて
いなければこの変数はサブシェル側では未定義となりますので
シェルは `expr $1 - 1` をコマンドと解釈して誤動作の原因になります。
サブルーチン $sub を切り出したならば実行属性を与えてスクリプトとして
実行できるようにします。そして、柱に通してある円盤の数を第１引数として $sub
を起動します。解を求める作業が終了すれば $sub から戻ってきます。
ディスクに書き出したサブルーチンの後始末は9行目の trap が請け負っています。
実際には23行目の処理が済むスクリプトを終える時点でシグナル0が送られてきますか
ら trap の第１引数で指定した rm -f $sub が実行されます。
行目の set -u は「5 スクリプトの
デバッグ」(p.
) で説明したスイッチで、
未定義の変数が参照された時にエラーメッセージを表示して
スクリプトを停止させるものです。ここでは引数なしで hanoi が呼び出されたときの
処理に利用しています。
さて、5行目に見慣れないものが書かれています。これはシェル変数置換の一種で、
第一引数($1) が未定義ならばエラーメッセージ "Parameter unset" を表示してスクリプ
トを停止させます。表示させたいメッセージを書かずに : ${1?} とすれば
シェルが持っているエラーメッセージを表示します。この時にヌルコマンドとしての
コロン ： を行頭に置くことを忘れないでください。
［「4.4.3 ヌルコマンド」(p.) 参照］
クエスチョンマーク ? 以外 にも、マイナス記号 - や等号 = も使うことができ、 それぞれ次のような意味を持っています。
本題からそれますが、このスクリプトを PS5523-S(386sx, 12MHz) で実行させたところ
円盤が8枚の時の255個の解を求めるのに7分20秒ほどかかりました。
この時に $sub(./hanoisub) が7つ重なり、さらにそれを呼び出した
親シェル hanoi、そしてログインシェルと9つのシェルが走ります。
１つのシェルは50kほどのメモリを必要としますから、小さいminixといえどもかなりの
メモリが必要になります。（BSDあたりに比べると可愛いのですが）
リアルモードのminixで円盤が8枚の解を求めるのは無理かも知れません。
例として取り上げたハノイの塔のスクリプトは起動された本体からサブルーチン用の スクリプトを展開し、それを呼び出しています。解を求めるために２つのスクリ プトが必要になることに変わりありません。そこで、サブルーチンを用いずに１つ のスクリプトだけで解を求めるものを作ってみてください。