今回やること

前回 + Index

実際に Turing Machine を動かしてみましょう。YANG を使って……の前に、XML をつかった Turing Machine に対する一連のオペレーションを試しておきたいと思います。そもそも Turing Machine って何? どういう風に動くもの? どうやって操作する? という話を押さえておきましょう。その上で、YANG ではどういうことが定義されているのか、実際オペレーションをするときに YANG をどう使えばいいのか、というのを見ていった方がわかりやすいと思うので。

そもそも Turing Machine ってなんだっけ…

このあと Turing Machine のデータモデルなどの話が出てきますが、そもそもの Turing Machine の話がわかってないと何のことやらサッパリになりかねません。チューリングマシン - Wikipedia をみると難しそうなことがいろいろ書いてありますが、チュートリアルを進める上で最低限把握しておかなければいけないのは以下の点です。

Turing Machine は "テープ" とテープを読み書きするための "テープヘッド" をもっている
Turing Machine は、今のテープヘッド位置からテープに書いてある記号を読み取る
Turing Machine は、読み取ったテープ記号と、現在の "状態 (state)" をもとに、次の状態とテープに対する操作(新しく値を書き込む、テープヘッドを動かす)を決定する
- いまの状態・テープ記号から次の状態・テープ操作を決めるために、"状態遷移表 (Transition Table)" をつかう
Turing Machine は、終了状態に到達したら停止する

YANG チュートリアルで扱う Turing Machine を図で書くとこんな感じ……。解説見るとたいていこういうのが出てきますよね。

でも、こういう話をされてもやっぱり「どう動くものなのか」ってわかりにくいんじゃないかな。ということで、 Turing machine visualization を参照してください。上のドロップダウンから適当な例を選んで、"Run" ボタンを押すと動きます。Turing Machine が実際にどのように動くものかが把握できると思います。

ここでは、"Turing Machine を使う" 時に何が(どんなデータが)必要なのか・どういう操作(オペレーション)が必要なのか、を押さえておきましょう。

Turing Machine がどういう処理をする(計算をする)のかは状態遷移表 (Transition Table) によってかわる
- Turing machine visualization では状態遷移表(下のプログラムリスト)で定義したものを状態遷移図として可視化しています。
Turing Machine に処理(計算)してほしいデータはテープの初期値として与える

どんな処理をさせるか?

Turing Machine は、状態遷移表にしたがってテープに書き込まれたデータを処理していきます。状態遷移表は「プログラム」に当たるもので、これを変えることで、Turing Machine がどんな処理(計算)をするのかを変更していくことができます。

「とりあえず動かしてみる」にあたって、YANG チュートリアルにある状態遷移表を使っていきます。これは、Turing Machine の処理としてよく知られている「ふたつの整数の足し算」をするためのものになっています。が、ちょっとバリエーションがあるのでその辺も合わせて解説します。

(a) YANG チュートリアルの「ふたつの整数の足し算」
- 整数を「その正数個」の 1 で表現し、0 をふたつの整数の間に入れるセパレータとして使います。例えば、"3 + 2" は 111011 になります。
(b) Turing Machines (Stanford Encyclopedia of Philosophy) (参考: コンピュータアーキテクチャの話(108) チューリングマシン | マイナビニュース) にある「ふたつの整数の足し算」
- 整数を「その整数 +1 個の 1 で表現し、0 をふたつの整数の間に入れるセパレータとして使います。例えば、"3 + 2" は 11110111 なります。

「データ(整数)をどう表現するか」という話がちょっと違うんですね。数のコード化ルールから、(b) は "0" を表現できます ("0" = 0+1 個の 1 = 1) が、(a) では表現できません。まあ、どう動くものなのかは実際動かしてみればわかるのでやってみましょう。(a)(b) どちらの状態遷移表も用意してみたので動かしながら違いを見てみると良いと思います。

使うデータは以下の通りです。

状態遷移表
- (a) YANG チュートリアルにある足し算の状態遷移表
- (b) Stanford のサイトにある足し算の状態遷移表¹

Turing Machine を動かしてみる

環境のセットアップ

この後使うツールは Go言語 (Golang) で実装しています。また、Ubuntu17/18 server, Golang/1.10 で動作確認をしています。(最初に apt install build-essential してあります。)

Golang のインストール

corestate55@ytut:~$ sudo apt install golang-go
corestate55@ytut:~$ mkdir go
corestate55@ytut:~$ echo 'export GOPATH=~/go' >> .bashrc
corestate55@ytut:~$ echo 'export PATH=$GOPATH/bin:$PATH'  >> .bashrc
corestate55@ytut:~$ . .bashrc

gRPC ライブラリのインストール

corestate55@ytut:~$ go get -u github.com/golang/protobuf/proto
corestate55@ytut:~$ go get -u google.golang.org/grpc

チュートリアル用 Turing Machine のダウンロードとビルド

corestate55@ytut:~$ git clone https://github.com/corestate55/yang-tutorial.git
corestate55@ytut:~$ cd yang-tutorial
corestate55@ytut:~/yang-tutorial$ make

Turing Machine を動かす

サーバ・クライアントの起動

まずサーバを起動します。こちらが Turing Machine の本体です。

corestate55@ytut:~/yang-tutorial$ ./tmserver

別のターミナルでクライアントを起動します。クライアントを起動すると Command Prompt が表示されます。以降、Turing Machine (サーバ)に対する処理はクライアントから実行します。

corestate55@ytut:~/yang-tutorial$ ./tmclient
command>

Turing Machine の状態取得

get はサーバ (Turing Machine) の状態を取得して XML で表示します。サーバ起動直後はまだ何もデータが設定されていません。

command> get
<TuringMachine>
  <head-position>0</head-position>
  <state>0</state>
  <tape></tape>
  <transition-function></transition-function>
</TuringMachine>

Turing Machine の状態遷移表の設定

config コマンドは Turing Machine の状態遷移表を xml file から読み込んでサーバへ送信します。まず (a) の足し算 config (turing-machine-config.xml) です。

command> config data/turing-machine-config.xml

このとき、サーバ側では受信した状態遷移表が出力されます。²

input        | output
state symbol | state symbol move
   S0      1 |  [S0]         -: left summand
   S0      0 |  [S1]     1   -: separator
   S1        |  [S2]        <=  right end
   S1      1 |  ----         -: right summand
   S2      1 |  [S3]     0  <=  write separator
   S3      1 |  ----        <=  go home
   S3        |  [S4]         -: final step

再度クライアント側で get コマンドを実行して Turing Machine の状態を取得してみてください。<transition-function> が設定されているはずです。

Turing Machine のテープの設定

init コマンドは Turing machine のテープへ初期データを書き込みます。

command> init data/turing-machine-rpc.xml

getして <tape> が設定されたか確認してください。

Turing Machine の処理(計算)実行

config, init で Turing Machine にテープと状態遷移表データを設定できていれば、処理(計算)実行が可能です。run で実行します。

command> run
<Notification  xmlns="urn:ietf:params:xml:ns:netconf:notification:1.0">
  <eventTime>2018-04-29 08:59:10.265261986 +0000 UTC  m=+249.208853529</eventTime>
  <halted>
    <state>4</state>
  </halted>
</Notification>
command>

実行 (run) すると、チューリングマシンが停止したよ、という通知 (notification) が飛んできました³。状態 4 で停止したようです。このとき、サーバ側ではどのように処理が実行されたかが表示されています。

Step State | Tape                   | Next Write Move
   1  [S0] | <1>| 1 | 0 | 1 | 1 | 1 | [S0]         -: left summand
   2  [S0] |  1 |<1>| 0 | 1 | 1 | 1 | [S0]         -: left summand
   3  [S0] |  1 | 1 |<0>| 1 | 1 | 1 | [S1]     1   -: separator
   4  [S1] |  1 | 1 | 1 |<1>| 1 | 1 | ----         -: right summand
   5  [S1] |  1 | 1 | 1 | 1 |<1>| 1 | ----         -: right summand
   6  [S1] |  1 | 1 | 1 | 1 | 1 |<1>| ----         -: right summand
tape out-of-range
   7  [S1] |  1 | 1 | 1 | 1 | 1 | 1 | [S2]        <=  right end
   8  [S2] |  1 | 1 | 1 | 1 | 1 |<1>| [S3]     0  <=  write separator
   9  [S3] |  1 | 1 | 1 | 1 |<1>| 0 | ----        <=  go home
  10  [S3] |  1 | 1 | 1 |<1>| 1 | 0 | ----        <=  go home
  11  [S3] |  1 | 1 |<1>| 1 | 1 | 0 | ----        <=  go home
  12  [S3] |  1 |<1>| 1 | 1 | 1 | 0 | ----        <=  go home
  13  [S3] | <1>| 1 | 1 | 1 | 1 | 0 | ----        <=  go home
tape out-of-range
  14  [S3] |  1 | 1 | 1 | 1 | 1 | 0 | [S4]         -: final step
  15  [S4] | <1>| 1 | 1 | 1 | 1 | 0 | END

あらためて get で Turing Machine の状態を確認してみてください。状態(State) やテープ (tape) 等が書き換わっていることがわかるはずです。

この例では、初期状態としてテープに書き込んだ 110111 ("2 + 3") に対して計算を実行したところ 111110 ("5") が得られました。正しく足し算ができていることがわかります。

処理を入れ替えて実行してみる

つづけて、(b) Stanford サイトの足し算をしてみましょう。テープを書き直して、状態遷移表(プログラム)を入れ替えます。

command> init data/turing-machine-rpc.xml
command> config data/turing-machine-config2.xml
command> run

使用しているテープの初期データは同じ (110111) ですが、解釈は "1 + 2" になります。実行結果が 001111 でこれは "3" を表しています。

「動かしてみる」で、なにをやったのか

さて、Turing Machine を「動かす」ための一連の操作を実際にやってみました。これは一体何をしていたのか、改めて振り返ってみましょう。

状態を取得する (get)
- 操作対象の状態や設定情報を抜き取る、いわゆる show コマンドに相当します。
データを送って機器の動作を変更する (config, init)
- config は操作対象がどのように動作するかの configuration を、init では機器が処理を実行する際の初期データを書き換えています。
実行する (run)
- 今回の実装では、設定データの変更と、それを元にした動作の実行は別のフェーズに分けてあります
- ネットワーク機器では candidate config を変更したあとで commit して実際設定したデータ (config) を機器の動作として反映させるようなイメージが近いでしょうか。

どんな操作をしていたのかイメージがわくでしょうか? これらを、XML で記述したデータを使って実行した⁴、というのがここまでの流れになります。

Stanfordのサイト "Figure 2" にある状態遷移図に基づいて作成していますが、YANG チュートリアルで想定されている実装と違いがあるので少し改変してあります。具体的には、(a) YANGチュートリアル版 Turing Machine では各ステップで必ずテープヘッドが左右いずれかに動く、となっているのですが、(b) Stanford 版ではそうなっていません。(b) の遷移図みると、状態遷移の出力が 2 種類で、ヘッドを動かすのとテープに書き込むのを同時に行わないようになっているからです。(a) では出力を 3 種類、状態・ヘッドの動き・テープへの書き込みとなっているので、実行ステップごとにヘッドが動く前提になっています。この点については (a) に合わせるように改変してあります。 ↩
move はヘッドをどちらに動かすかです。Head move が省略されている場合はデフォルトで右 -: 表示、"right" を明示的に指定した場合は => が表示されます。省略時に "right" とするのは YANG ファイル中に記載があります。 ↩
いま notification の扱いについてはあまりちゃんと実装していません。Notification はもともと Netconf を想定してあるはずのものなので、裏を gRPC にしているためあまり意味がありません。見た目だけ、それっぽく合わせているという程度です。 ↩
ちょっと YANG/Netconf というところに話を戻すと、もともと Netconf では Message, Operations, Content というつくりになっています。(参考: 知ったかぶりしない NETCONF - LGTM) YANG Tutorial でも Netconf でサーバとやりとり (RPC) する前提になっていて、<config> というタグで状態遷移表を渡していたり、<rpc> というタグで Initialize メッセージを送っていたりします。今回作ったツールでは、"見た目" は YANG Tutorial に合わせて、XML データがそのまま使えるように作ってありますが、裏の Client-Server 間 RPC は gRPC なので、本当はこれらのタグは必須ではありません。それは追って別な回でまた取り上げます。 ↩

YANGを使いこなす! (2) 操作対象を理解する