Bash $((算術式)) のすべて

算術式についてまとめます! 以下の衛星記事もご参照ください。

• Bash $((算術式)) のすべて - A 基本編 - Qiita
• Bash $((算術式)) のすべて - B 罠・バグ回避編 - Qiita
• Bash $((算術式)) のすべて - C 応用編 - Qiita

本当は どうでも良い Bash 算術式の細かいこと をメインで書きたいのですが、それだと余り役に立たない記事になってしまうので、基本も網羅します! 先ず節1に基本事項をまとめ、それ以降に他に書かれていない色々の注意点・応用方法などを簡潔にまとめます。ちゃんとした説明は附録記事に譲ります。

これらの内容(特に節2以降)は、自分で算術式を使う過程で分かったこと・学んだことを基にしています。Bash のマニュアルに載っていないのは勿論のこと、他の場所にも載っていない情報を多く入れられたように思います。役に立つどうかは分かりませんが一つの集大成として投稿いたします。

※タイトルに「すべて」と銘打ちましたが本当に全てかは分かりません。多分全てじゃありません

目次

1. 算術式 (arithmetic expression) とは (初級):
   Bash における算術式の機能・仕様についてまとめます
2. Bash 算術式の罠にかからないために (初級):
   使用時に初心者が嵌るかもしれないことの注意点についてまとめます
3. Bash 算術式の応用 (中級):
   Bash 算術式の応用的な使用方法などについてまとめます
4. Bash のバグたちとその避け方 (中級):
   古今の Bash の version における算術式実装のバグと回避方法についてまとめます
5. Bash 算術式はチューリング完全 (上級冗句):
   Bash 算術式はそれ単体でチューリング完全なんです!
6. 附録A Bash 算術式の基本詳解 → 別記事 A 基本編
7. 附録B Bash 算術式の罠・バグの回避法 → 別記事 B 罠・バグ回避編
8. 附録C Bash 算術式の応用詳解 → 別記事 C 応用編

#■ 1. 算術式 (arithmetic expression) とは
$((i+1)) とかのことです。シェルの組み込み機能で整数 (シェルによっては小数も) の計算ができます。

殆どの Bourne Shell 系のシェルで使えますが、オリジナルの Bourne Shell では使えないらしい(?)です。POSIX sh 規格に加えて bash, zsh, ksh, ash/dash, yash, etc. で使えます。ただしシェルによって様々な拡張が加えられています。例えば Bash の算術式では、四則演算など C でお馴染みの演算子たちは勿論のこと、累乗 a**b なども計算できます。

この記事は Bash の算術式 の記事なので、ここでは Bash の算術式に絞って (不必要に) 深く仕様をまとめます。

##1.1 序 ～皆さま算術式使っていますか?～
さて、記事を書くに当たって、少しでも算術式に言及のある記事が Qiita にどれだけあるのか調べてみました ("算術式" で検索しました):

• 普通に紹介
  • 2015-05-20 本当は使いたいけど使わないBashのTIPS - Qiita
• インクリメントの方法の紹介として:
  • 2016-11-16 bash でインクリメント - Qiita
  • 2015-07-06 bash Tips - コマンド置換と算術式展開、パラメータ展開 - Qiita
  • 2014-12-27 シェルで変数のインクリメントに expr を使うと100倍遅い件 - Qiita
• ${var:offset:length} の offset と length が算術式だということ
  • 2013-07-12 シェルスクリプトで最後の引数 or 要素 - Qiita
  • 2013-03-19 最後のコマンドライン引数を取得する - Qiita (コメント中)
• expr の exit code の話
  • 2016-03-24 expr の計算結果が0になる時は注意 - Qiita
• n進数の話
  • 2013-03-29 Bashでn進数を扱うには - Qiita
• 名前だけ登場
  • 2016-06-15 シェルスクリプト勉強して1日で覚えたやつ - Qiita
  • 2016-05-18 bashのmanを読んで使いそうなものだけまとめる - Qiita
  • 2015-04-20 シェルの基礎とSSH Tips - Qiita

検索して思ったことは…意外と少ないです…何かもっと算術式を前面に押し出したような記事が沢山あるんじゃないかと思っていました。expr と比べると圧倒的に少ない気がします。もしかして算術式ってマイナーな機能ですか? (きっと…きっとみんな算術式という名前を知らないだけなんですよ。そうにちがいありません!) 需要ないかもしれないけれど、算術式ってこんなに便利だよという宣伝のためだと思って進めることにしましょう。

もう一つ気づいたことは、算術式の基本について包括的に説明している記事が存在しない ということです! いい加減に箇条書きにして後は別の記事に丸投げしようと思っていましたが、これでは丸投げできません! しようがないので別に記事を作ることにしました。附録A Bash $((算術式)) のすべて - A 基本編 - Qiita です。(附録を書いていたら本記事を書く時間がなくなってしまいました…後悔しています…。)

追記: いま検索したら 算術式 - Bash Advent Calendar - Day 6 という記事が見つかりました! 良い記事です! 早く検索するべきでした。

ここでは要点だけ箇条書きでまとめます。

##1.2 算術式評価の起こる場所
算術式は $((～)) の形でしか使えない機能ではありません! Bash の色々なところで算術式評価が実行されます。皆が整数を指定すると思っているところは、実は算術式を指定するところだったりします。

ほら! ここも! あそこも! 皆さまは以下のうち幾つをご存知でしたか?

1. 算術式展開: $((ここ)) と $[ここ] ($[] は非推奨なので使っては駄目)
2. 算術式の構文・コマンド: ((ここ)) と let ここ。あと for ((ここ;ここ;ここ)) も。
3. 配列変数の添字: arr1[ここ]=${arr2[ここ]} や arr3=([ここ]=value)。更に unset 'arr4[ここ]' も。
4. パラメータ・変数展開の offset/length: ${text:ここ:ここ} ${array[@]:ここ:ここ}
5. declare -i された変数への代入の右辺: declare -i number; number=ここ; number+=ここ
6. [[ ～ ]] の算術二項演算子の引数: [[ ここ OP ここ ]] (但し OP は -eq, -ne, -lt, -le, -gt, -ge のどれか)
7. 算術式中の変数・配列要素の中身 (つまり再帰が可能): 例えば a=1+2+3 b=2; echo $((a*b)) は、まず a, b の中身が算術式評価されて 6, 2 になった後で、更に $((6*2)) が算術式評価されます。

注意

• 連想配列 (bash-4.0) の添字はもちろん算術式評価の対象ではありません。
• 以上は Bash における算術式評価の起こる場所です。算術式評価の起こる場所はシェルによって異なることに注意して下さい。
• 7. 算術式中の変数の中身 は、厳密に言うとその変数の値 (C/C++ でのいわゆる右辺値) が必要な時だけ、中身が算術式評価されます。代入演算子 (=) の左辺にある場合など、その中身に元々入っていた内容が不要な場合は、中身についての算術式評価は起こりません。
• 7. 算術式中の変数の中身 に基づく再帰には上限があります。基本的に1022 回です。
• クォートされていない括弧 ( の数と ) の数はバランスしている必要があります。
• 空の式 (空文字列・空白だけからなる文字列) の評価結果は 0 です。ただし、for ((;;)) の真ん中の式に空の式を指定した場合は 1 を指定したものと見なされます。また、文法上、空文字列は配列添字に指定できません。
• 文脈によって記号類 ()<>& がシェルの特別な意味を持ったり、グロブ展開・チルダ展開・プロセス置換などの望まないシェル置換が起こったりするので、文脈に応じて適切にクォートする様に注意が必要です。詳細は 附録 A4.8 の表を御覧ください。

##1.3 基本
式 (算術式) は以下の形をしています。式の定義の中に 式 が再帰的に現れますが、式はこれらの生成規則を有限回適用して得られる文字列です。

• 整数: 123 十進法, 0755 8進法, 0xA 0XA 16進法, ★n#hoge n進法
• 変数名: a var など
• 配列要素: arr[...] など
• 式 二項演算子 式: + - * / % < > <= >= == != << >> & ^ | && || = += -= *= /= %= <<= >>= &= ^= |= ** , がある。★** は累乗。&& || は短絡評価。
• 前置演算子 式: ++ -- ! ~ + - がある。
• 式 後置演算子: ++ --
• 括弧: ( 式 )
• 条件演算子: 式 ? 式 : 式。短絡評価です。

空白改行の類は構成要素の間に自由に挿入可能です。★をつけたところは (C言語にはない) 独特の機能です。演算子の優先順位は C と同じです。ただし累乗 ** は、* / % より強く ++ -- などより弱く、また四則演算などと違って右結合です。具体的な演算子の結合規則は附録 A3.6.2 の表を御覧ください。

注意

• Bash では整数 (intmax_t) の計算しかできません。POSIX 的には浮動小数点などを取り扱えるように勝手に拡張したりするのは自由ということになっています。実際 zsh では浮動小数点数を取り扱えます。

• また、C言語と異なる驚くべき振る舞いとして、Bash算術式では ++・-- 演算子の前後に変数名または配列要素がない場合には、それぞれ 2つの +・2つの - と解釈されるというものがあります。つまり、1++2 は 1+(+2) という意味の正しいBash算術式です。一方 a++2 は正しくありません。

##1.4 ⚙ 配列添字のシェル展開

配列要素を参照するとき、添字の文字列はコマンド置換・パラメータ展開・算術式展開の対象です。

例1

var='x[$(echo hello >&2)]'
: $((var)) # 結果: hello が標準エラー出力に出力されます

当然、配列要素を参照する度に毎回コマンド置換が実行されます。初回だけということはありません。

例2

$ exec 5>&1 # (動作例示のため fd 5 を標準出力に繋いで置く)

$ x=1234
$ arr=('x[$(echo hello >&5)]' 'x[$(echo world >&5)]')
$ declare -p arr
declare -a arr='([0]="x[\$(echo hello >&5)]" [1]="x[\$(echo world >&5)]")'
# ↑クォートしたので、まだこの時点ではコマンド置換は実行されていません。

$ echo $((i=0,arr[i++%2],arr[i++%2],arr[i++%2],arr[i++%2]))
hello
world
hello
world
1234
# ↑ x[...] を評価した回数だけコマンド置換が実行されます。
# 算術式自体の評価結果は `x[0]` → `x` → `1234` となります。

#■ 2. Bash 算術式の罠にかからないために
詳しい内容は附録記事 Bash $((算術式)) のすべて - B 罠・バグ回避編 - Qiita §B1 で説明します。ここでは項目を箇条書きにするに留めます。詳しくは附録記事を御覧くださいね。

• 変数を無駄に変数展開しない: ×$(($a*$b)) → ○ $((a*b))
• 0で左詰めされた整数には基数 10# を指定する
• 代入済の値は declare -i の対象外なことに注意する
• ${変数:式1:式2} の式1が -/+ で始まるときは半角空白を前置する
• ${変数:式:式} に副作用のある式を指定しない
• unset arr[式] はダメ。常にクォートして unset 'arr[式]' とする

#■ 3. Bash 算術式の応用
詳しい内容は附録記事 Bash $((算術式)) のすべて - C 応用編 - Qiita で説明します。ここではそれぞれの項目の要点をまとめます。

##3.1 シェル関数の引数に算術式を指定できるようにする
引数を変数で受け取る時にオプション -i を指定すれば良いです。

function myfunc {
  local -i arg1=$1; shift
  local -i arg2=$1; shift
  local -i arg3=$1; shift

  # 処理
}

##3.2 let × ブレース展開技
for ループを記述する代わりに let × ブレース展開で繰り返し処理を記述できます。しかも高速です。

let s=0 i={0..99},'s+=i*(i+1)' # ← 1行で書ける
echo $s # 結果: 333300

##3.3 算術式だけでいろいろな処理を行うということ

• 算術式を使って変数に値を代入できます
• 複数の算術式をカンマ演算子で繋げば、一つの算術式で逐次的に一連の処理を行えます
• 条件演算子 ?: や論理演算子 ||、&& は短絡評価なので条件分岐を記述するのに使えます

##3.4 変数名を格納した変数の取り扱い

• 整数を扱うのであれば eval や printf -v を使わなくても、変数名に値を格納できます: (($varname=value))
• 整数を扱うのであれば ${!varname} などの様に記述する必要はありません: ((a=varname))。算術式の再帰的な評価によって目的の値を取得できます

##3.5 構造体・クラスの実現方法
これは技術的には実は算術式と関係ありません。しかし、算術式を使うとそれっぽい雰囲気でメンバ変数のアクセスを記述できます!

• 複数の変数をひとまとまりとして扱うことで実現します
• 構造体 "変数名" はひとまとまりの変数の接尾辞と解釈することにします

function main {
  # "構造体" 定義
  Rect=(x y w h) # メンバ変数のリスト

  # "変数" rect の宣言
  local "${Rect[@]/#/rect_}" # rect_x ～ rect_h を一括宣言
  ((rect_x=1,rect_y=2,rect_w=3,rect_h=4))

  # 参照
  local ptr=rect

  # 参照を通したメンバアクセス
  ((${ptr}_x=10,${ptr}_y=10))

  # メンバ関数
  function Rect::move {
    local this=$1; shift
    local dx=$1 dy=$2
    ((${this}_x+=dx,${this}_y+=dy))
  }
  Rect::move rect 5 5

  # 派生クラス
  Board=("${Rect[@]}" color)
}

• 更に、メンバに _vptr などといったものも加えれば容易に仮想関数も実現できます。

###3.5.1 (追記 2016/12/8) @syui さんの記事で紹介された Bash Infinity Framework

正直この §3.5 は半ばふざけて書いたものでしたが、本気でクラスなどの仕組みを導入するフレームワーク (Bash Infinity Framework) が 同 AdC の 7 日目 Bashで便利なフレームワーク - Qiita で紹介されました! こんなものもあるのですね!

でも、このフレームワークって shopt -s nullglob の状態で使うと [array] などが全て消滅して大変なことになるような気がします…? いいのですかね。

#■ 4. Bash 算術式のバグたちとその避け方
この節の詳しい内容も附録記事 Bash $((算術式)) のすべて - B 罠・バグ回避編 - Qiita §B2 にあります。ここでは Bash のバグと回避方法を箇条書きにするに留めます。詳しくは附録記事を御覧ください!

• 特定の式でシェルがクラッシュする (bash-4.2)
  少なくとも bash-4.2 で一回実行してみて問題なければOKです。クラッシュする様ならば算術式を一旦切れば問題ありません
• 条件演算子式の分岐にある最初の変数内の算術式評価が常に実行される (bash-3.0 ～ bash-4.4.7)
  条件演算子式の分岐を括弧で囲めば問題ありません。
• 条件演算子の直列ができない (bash-3.1 以下)
  条件演算子を入れ子にする場合には必ず括弧で囲むようにします。
• 条件分岐中の配列要素参照が必ず実行される (bash-3.2 ～ 4.1)
  条件分岐内で配列要素を参照する場合はシェルの構文で条件分岐を行います
• 変数展開の配列添字が2回算術式評価される (bash-3.0 ～ 4.1)
  変数展開の配列添え字に副作用のある式を指定しなければ問題ありません

#■ 5. Bash算術式はチューリング完全
Bashの算術式はそれ単体でチューリング完全です!

※ただし §1.4 で述べたコマンド置換の呼び出しを使ってしまうと何でもできてしまって自明なので、もちろんこれは使わないという前提です。

基本で説明したことを振り返ってみましょう。Bash の算術式では:

• i++ や a=... などで変数の書き換えができます。
• そして、算術式の中から配列要素を読み書きすることもできます。つまり記憶領域も(実質的に)無限です。
• さらに A&&B, A||B, A?B:C は短絡評価です。つまり、条件分岐ができます。
• そして、変数の値を取り出す時は再帰的に算術式評価が適用できます。つまり、ループが作れるということです。

ここまでの機能が揃っていれば、もう明らかにチューリング完全です。

特に、変数に格納された文字列が再帰的な算術式評価の対象であることが一番効いています。この再帰的な評価は zsh と ksh でも使えます。つまり、zsh 算術式と ksh 算術式も Bash 算術式と同様にチューリング完全と思われます。

一方で、dash/ash や yash は再帰的な算術式評価は行わないようですので、これらは (この意味では) チューリング完全ではありません。ただし、ひょんなことである体系がチューリング完全になってしまうということはよくあるので、ひょっとすると dash や yash の算術式も何らかの意味でチューリング完全ということもあるかもしれません。

##⚙ 5.1 再帰限界の突破
チューリング完全なことはもう殆ど自明な感じがしますが、やはりチューリング完全を主張するためには、チューリングマシンの模倣をしてみたいものです。ここでは Bash の色々のバグを考慮に入れるのが面倒なので bash-4.3 の上でチューリングマシンを模倣することにします。

しかし、その前に Bash の算術式評価の再帰に問題があります。それは、再帰の深さに上限があるということです。1022回までしか再帰できません。Bash の算術式評価の実装は末尾再帰ならセーフみたいな上等なものでもありません。従って、チューリングマシンの実装を始める前に何らかの方法でこの限界を実効的に取り払って置く必要があります。

Bash 算術式の再帰の限界

$ loop='(i<1021)&&(s+=i,i++,loop)'
$ echo $((s=0,i=0,loop,s))
520710 # OK (呼び出し元算術式1回 + loopの1021回 = 1022回までならOK)
$ loop='(i<1022)&&(s+=i,i++,loop)'
$ echo $((s=0,i=0,loop,s))
bash: (i<1022)&&(s+=i,i++,loop): 式の再帰可能レベルを越えました (エラーのあるトークンは "i<1022)&&(s+=i,i++,loop)")

今回は、有限の深さの再帰を使って (実効) 無限ループを実装します。チューリングマシンは、その無限ループを使って実装すれば良さそうです。

さて、上記の例では変数 loop から自身 loop を一回ずつ呼び出す事によって繰り返し処理を実装しました。深さ 1021 で処理をやめたとすると、合計で 1021 回の処理を行うことができることになります。

という事は、loop から自身を $n$ 回ずつ呼び出す事にすれば、呼び出し回数はねずみ算式に増えます。深さ $N$ で処理をやめたとすると合計の繰り返し回数は、

$$\sum_{d=0}^{N-1}n^{d} = \frac{n^N - 1}{n - 1}, (n>1)$$

になるはずです。実際の計算機では無駄に大きくしても仕方がないので $n=2, N=64$ 程度で問題ないでしょう。例えば 4 GHz ($\sim 2^{32}$ Hz) の CPU で 1ループに $C$ サイクルかかるとして $2^{64}$回ループが終わるまでにかかる時間を見積もると、$2^{64} C / 2^{32} ;[\textrm{sec}] \sim 136 C ;[\textrm{year}]$ になります。到底終わりません。というかその前に Bash を動かしているマシンの寿命が来て壊れます。という訳で:

実効的無限ループ

$ loop_body='s+=i'
$ loop='inest++,(loop_body,i++,inest<64&&(loop,loop)),inest--'
$ echo $((s=0,i=0,loop,s))

実際には計算が終了した場合に任意のタイミングで停止したいので、停止するための機能もつけておきます。また、処理を分離して定義できるようにもします。

使いやすく

# 定義 (bash-4.3以上)
readonly while='__depth=0,__break=0,__loop,__break'
readonly __loop='__depth++,__break||(__break=!cond)||((body),__depth<64&&(__loop,__loop)),__depth--'

# 使用方法
cond='続行条件' # ループの繰り返しを続行する条件を記述
body='算術式' # ループで毎回行う処理を記述
((while)) # 処理の開始

##⚙ 5.2 チューリングマシンのエミュレータ

うーん。考えるのが面倒なので Wikipedia にあるチューリングマシンをそのまま模倣する方法について考えます。

チューリングマシン - Wikipedia から引用:
あるチューリング機械は次の 7つ組 $M=\langle Q,\Gamma,b,\Sigma,\delta ,q_{\mathrm{init}},q_{\mathrm{acc}}\rangle$ で定義される。

• $Q$ は有限集合であり、その元を状態という。
• $\Gamma$ は $Q$ に交わらない有限集合であり、字母とよばれる。その元を記号という。
• $b$ は $\Gamma$ の元であり、空白記号とよばれる。
• $\Sigma$ は $\Gamma - \{b\}$ の部分集合であり、入力字母とよばれる。その元を入力記号という。
• $\delta$ は $Q\times\Gamma$ から $Q\times\Gamma\times\{\leftarrow, \rightarrow\}$ への写像であり、遷移函数とよばれる。$\delta(q, a) = (q', a', m)$ は、「現在の状態が $q$ であり、着目位置にある記号が $a$ であれば、状態を $q'$ に移し、着目位置に記号 $a'$ を書き込んでから、着目位置を $m$ 方向に1つずらす」と読む。
• $q_{\mathrm{init}}$ は $Q$ の元であり、初期状態とよばれる。
• $q_{\mathrm{acc}}$ は $Q$ の元であり、受理状態とよばれる。

先ず $Q$ と $\Gamma$ の元に整数を対応付けて、それらを整数で表すことにします。

# Gamma の定義
((Gmin=0,Gmax=999,Gnum=Gmax-Gmin+1)) # 範囲は適切に設定する
((b=0)) # 空白記号

# Q の定義
((Qmin=1000,Qmax=1999,Qnum=Qmax-Qmin+1)) # 範囲は適切に設定する
((qinit=1000)) # 初期状態
((qacc=1001)) # 受理状態

同時に着目位置の移動方向にも $\leftarrow = 0, \rightarrow = 1$ と整数を割り当てます。

そして遷移関数 $\delta$ を配列 delta で表現します。形式的には

• $\mathrm{pair}(q, a) := (q-Q_{\rm min})\cdot \Gamma_{\rm num}+(a-\Gamma_{\rm min}),$
• for all $(q, a) \in Q\times\Gamma$:
  • $(r,b,m) := \delta(q, a),$
  • delta[$\mathrm{pair}(q, a)$]=$(\mathrm{pair}(r, b)\cdot 2 + m).$

という具合にして配列 delta を作成します。実際には以下の様な雰囲気の定義になるでしょう。

delta=(
  [0]=2134 # 適当
  [1]=4231
  [2]=1234
  [3]=1231
  [4]=4321
  # つづく …
)

後は遷移関数に従って処理を行う算術式を書けば良いです。

# 動作の定義
cond='q!=qacc'
body='
  triplet=delta[(q-Qmin)*Gnum+(tape[head]-Gmin)],
  qnext=Qmin+triplet/(2*Gnum),
  awrite=Gmin+triplet/2%Gnum,
  direction=triplet&1,
  q=qnext,
  tape[head]=awrite,
  direction?head++:head--
'

そしたら入力を与えて実行すれば良いです。

# 入力
head=0 tape=(入力列)

# 実行
((q=qinit,while))

テストしていないのでバグなく動くかは分かりませんが、まあ、少なくとも技術的に実現可能だということは明らかです。実際に具体的なチューリングマシンをエンコードして実行できたらいいなと思いましたが、もう時間がないので省略します…。

追記 (2016/12/8): 何かいいチューリングマシンのプログラムはないかなと思っていましたら、折しも、Qiita 記事 "Turing Machine で無理数を生成する" にチューリングマシンのプログラムが現れました!

これはもう翻訳して動かしてみるしかありません。以下に算術式による実装と動作例を追加しました。ただし、元のプログラムだと無理数を延々と書き出し続けて停止しないので、勝手に停止する仕組みをつけ加えました (悲しいかなチューリングテクニック(?)がないので、折角 0 と 1 だけで minimal に構成された $\Gamma$ を拡張してしまいましたがお許し下さい)。

demo-turing1.sh

#!/bin/bash

# チューリングマシン (bash-4.3以上)
readonly while='__depth=0,__break=0,__loop,__break'
readonly __loop='__depth++,__break||(__break=!cond)||((body),__depth<64&&(__loop,__loop)),__depth--'
readonly cond='q!=qacc' body='
  triplet=delta[(q-Qmin)*Gnum+tape[head]-Gmin],
  qnext=Qmin+triplet/(2*Gnum),
  awrite=Gmin+triplet/2%Gnum,
  direction=triplet&1,
  q=qnext,
  tape[head]=awrite,
  direction?head++:head--
'

#------------------------------------------------------------------------------
# プログラム

((Gmin=0,Gmax=999,Gnum=Gmax-Gmin+1,
  Qmin=0,Qmax=999,Qnum=Qmax-Qmin+1,
  qinit=0,qacc=999))

# http://qiita.com/aTakaakiSeki/items/570c1f417be30c419c0b
add_rule='delta[q*Gnum+a]=(r*Gnum+b)*2+d'
((R=1,L=0,
  q=0,a=0,b=1,d=R,r=1,add_rule,
  q=1,a=0,b=1,d=R,r=2,add_rule,
  q=2,a=0,b=1,d=R,r=3,add_rule,
  q=3,a=0,b=1,d=L,r=4,add_rule,
  q=4,a=0,b=0,d=L,r=4,add_rule,
  q=4,a=1,b=1,d=L,r=5,add_rule,
  q=5,a=0,b=0,d=L,r=5,add_rule,
  q=5,a=1,b=0,d=L,r=6,add_rule,
  q=6,a=0,b=1,d=R,r=7,add_rule,
  q=7,a=0,b=0,d=R,r=7,add_rule,
  q=7,a=1,b=1,d=R,r=8,add_rule,
  q=8,a=0,b=0,d=R,r=8,add_rule,
  q=8,a=1,b=0,d=R,r=9,add_rule,
  q=9,a=0,b=1,d=L,r=4,add_rule,
  q=6,a=1,b=1,d=R,r=10,add_rule,
  q=10,a=0,b=0,d=R,r=10,add_rule,
  q=10,a=1,b=1,d=R,r=11,add_rule,
  q=11,a=0,b=0,d=R,r=11,add_rule,
  q=11,a=1,b=0,d=R,r=1,add_rule))

# 停止用追加ルール
((q=1,a=999,b=999,d=R,r=qacc,add_rule,
  q=2,a=999,b=999,d=R,r=qacc,add_rule,
  q=3,a=999,b=999,d=R,r=qacc,add_rule,
  q=9,a=999,b=999,d=R,r=qacc,add_rule))

#------------------------------------------------------------------------------

# 入力を設定
tape=([${COLUMNS:-80}-3]=999) # 停止位置の設定

# 実行
((head=0,q=qinit,while))

# 結果を出力
IFS= eval 'echo "${tape[*]}"'

動作例 (bash-4.3以上)

$ ./demo-turing1.sh
10100100010000100000100000010000000100000000100000000010000000000100000000001999

##⚙ 5.3 Intel ごっこ (現実的な算術式上の処理系)

さて、実際にはチューリングマシンの状態遷移規則を使ってプログラムを書くのはきついです。やはり、算術式の機能を最大限に利用して直感的にプログラムを書きたいものです。既に述べた様に、変数の書き換えや条件分岐などは既に算術式によって自然に記述されます。残っているのは、ループ (for・do・while) やジャンプ (goto・longjmp・throw) と関数呼出です。

これらを実現する方法の1つが Intel CPU ごっこ方式です。

1. 実行する算術式の列を配列 text に順番に格納しておいて
2. 次の実行位置 (instruction pointer) を変数 rip に保持し
3. text[rip++] をループで回す

という具合にします。goto は rip にジャンプ先の text のインデックスを代入することによって実現できます。goto さえ実現できればループは goto を使って実現できます。

FizzBuzz.sh

#!/bin/bash

# ※bash-4.3以上
readonly while='__depth=0,__break=0,__loop,__break'
readonly __loop='__depth++,__break||(__break=!cond)||((body),__depth<64&&(__loop,__loop)),__depth--'
readonly cond='!exit' body='text[rip++]' start='exit=0,rsp=0,rip=0,while'

text=(
  i=1
  iout=0
  'i<100||(rip+=19)'
  flag=0
  'i%3==0||(rip+=5)'
  stdout[iout++]=0x46
  stdout[iout++]=0x69
  stdout[iout++]=0x7a
  stdout[iout++]=0x7a
  flag=1
  'i%5==0||(rip+=5)'
  stdout[iout++]=0x42
  stdout[iout++]=0x75
  stdout[iout++]=0x7a
  stdout[iout++]=0x7a
  flag=1
  '!flag||(rip+=2)'
  'i>=10&&(stdout[iout++]=i/10+48)'
  stdout[iout++]=i%10+48
  stdout[iout++]=0x0a
  i++
  rip=2
  exit=1
)

# 実行
((start))

# 結果
LC_ALL=C printf "$(printf '\\x%x' "${stdout[@]}")"

残るのは関数呼び出しです。Bash 算術式には関数を定義したり呼び出したりする方法はありません。従って、これも Intel ごっこで行く必要があります。先ず、関数の引数の受け渡しや関数の呼び出し元の位置 (return address) の保持をし、更に再帰的な関数の呼び出しも可能 (リエントラント) にするためには、やはりコールスタックを用意するしかありません。

都合上スタックは小さいアドレスから大きいアドレスの方向に向かって成長することにします。

funcall.sh (関数呼出の雰囲気)

#!/bin/bash

# ※bash-4.3以上
readonly while='__depth=0,__break=0,__loop,__break'
readonly __loop='__depth++,__break||(__break=!cond)||((body),__depth<64&&(__loop,__loop)),__depth--'
readonly cond='!exit' body='text[rip++]' start='exit=0,rsp=0,rip=0,while'

Push='stack[rsp++]'
Pop='stack[--rsp]'
Call="$Push=rip,rip"
Ret="rip=$Pop"
arguments=(stack[rbp-{3..258}])
locals=(stack[rbp+{0..255}])

text=(
  # 00000000: 開始位置
  $Push=4 # 引数2
  $Push=3 # 引数1
  $Call=6 # 関数呼び出し
  rsp-=2
  rax+=10
  exit=1

  # 00000006: 関数の実体
  $Push=rbp
  rbp=rsp
  'rax=arguments[0]*arguments[0]+arguments[1]*arguments[1]'
  rsp=rbp
  rbp=$Pop
  $Ret
)

# 実行
((start))

# 結果
echo $rax

こんな感じにしていけばアセンブリを書く雰囲気で算術式で様々なプログラムが書けそうです。本当は何かプログラムを書こうとか考えていましたが、もう時間がなくなりました。

##⚙ 5.4 x86-64 簡易エミュレータ
初めは、x86-64 の簡易エミュレータを作って算術式上で動かすという壮大な計画 (?) があったのですが、案の定、いつの間にかに AdC 前日になり結局計画は消えてなくなりました。

当初の妄想は、以下のような感じだったのですが誰かやってくれませんか?

1. 適当な整数の計算を行う関数をコンパイルして得た ELF イメージをこの記事の方法でロード
2. ELF を算術式で読んで関数の先頭位置を取得しエミュレーションを開始
3. 命令を算術式でデコードしながら実行 (レジスタはシェル変数・メモリはBash配列)
4. システムコールは仕方がないので §1.4 を用いてコマンド置換で呼び出し

ここまで説明した方法を駆使すれば技術的には簡単だと思うのです。労力的には面倒ですが。