バンチ計算システム

バンチ計算システムの構成素：

1. 項
2. バンチ
3. 書き換え規則
4. 書き換えアクション
5. 書き換え系列〈sequence〉

説明：

1. 項は構文的コンビネーション
   1. ツリー構造
   2. リーフは型付き変数または型付きリテラル、型は圏の対象
   3. リーフ以外のノードはコネクティブ
   4. 文法範疇があってもよい。
2. バンチは項の構文木
   1. ツリー構造
   2. リーフは項
   3. リーフ以外のノードは区切り記号〈コネクティブ〉
3. 書き換え規則は、個々の書き換えアクションのもとになるパターン
   1. 仮パラメータを持つかもしれない。
   2. 適用可能性条件が付くかもしれない。
4. 書き換えアクション
   1. 書き換え規則の仮パラメータに実パラメータを代入して得られる。
   2. 書き換え規則の名前、実パラメータ、適用ロケーションからなる。
   3. 書き換えの対象となるバンチの一部をリデックス〈redex〉、書き換えの結果をリダクテッド〈reducted | contractum〉と呼ぶ。オペランドとリザルトがいいかも。
   4. 実際の書き換えに使える。書き換え系列に出現する。
5. 書き換え系列
   1. バンチと書き換えアクションが交互に現れる系列。

項の文法とバンチの文法は類似、ときにまったく同じだが、項とバンチは区別する。項 ←→ バンチ の相互変換は、濃縮・希釈〈concentration dilution〉または折りたたみ・展開〈contraction expansion〉で行う。

バンチ書き換えと項書き換えは区別される。

ちなみに文法は次から構成される。

1. 語彙〈終端記号の集合〉
2. 文法範疇〈非終端記号の集合〉
3. 書き換え規則＝生成規則
4. 開始記号

文法はオートマトンと密接に関係する。

バンチ書き換えシステム＝バンチ計算システム、項書き換えシステム＝項計算システムは階層的に配置される。複数の計算システムの構造物・組織体を、計算システム連合〈federation of {calculation | calculating} systems〉と呼ぶ。現実の計算システムは連合を形成している。