スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#で入門 コンパイラ 、インタプリタ編 チューリング・マシン(1)

今回は一息いれて「チューリング・マシン」を実装してみたいと思います。 
 
チューリング・マシンは参考にする文献によって、いろいろ細かい部分が異なるのですが、今回はウィキペディア版のものを取り上げます。 
 
チューリングの仮想機械は、 
(1)マス目で区切られた無限に長いテープ(マス目毎に一文字が記録できるようになっている) 
(2)(1)のテープに格納された情報(文字群)のうち現在位置の一文字を読み書きする可動式ヘッド 
(3)機械の内部状態を記憶するメモリ(何種類かの最初に使用者側で設定した状態の内、「今状態6ですよ」というような情報を記録する) 
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。 
(Ⅰ)ヘッド位置のテープに情報を書き込む 
(Ⅱ)機械の内部状態を変える 
(Ⅲ)ヘッドを右か左に一つ移動する 
上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。 
 
というものです。 
 
流れとしては、次の繰り返しです。 
 
読み込みー>書き込み(ない場合あり)->読み込みの値と状態により遷移(状態と位置を変化させる) 
 
ではプログラムを考えます。 
読み込み時の状態と読み込みの値から次のする動作が決定するのでこれをmapにしておきます。 
例えば次のように考えます。 
「状態2で記号0を読み込んだ時に、何も書き込まずに、右に一つ移動する。また状態は4に移行する。」というのを、(2,'0')に対し(4,None, 1)を対応させると考えます。 
(書き込みがある場合はNoneの場所をSome(書き込む文字)とします。) 
これらの対応をmapにして定義します。(何のプログラムかは後で説明します。) 
 
> let changeTB = // _はブランクを表す 
    [((1,'0'),(2,None, 1));((1,'1'),(3,None, 1));((1,'+'),(8,None, 1));     ((1,'*'),(8,None, 1));     ((1,'_'),(8,None, 1)); 
     ((2,'0'),(4,None, 1));((2,'1'),(5,None, 1));((2,'+'),(8,None, 1));     ((2,'*'),(8,None, 1));     ((2,'_'),(7,None,-1)); 
     ((3,'0'),(5,None, 1));((3,'1'),(6,None, 1));((3,'+'),(8,None, 1));     ((3,'*'),(8,None, 1));     ((3,'_'),(7,None,-1)); 
     ((4,'0'),(8,None, 1));((4,'1'),(8,None, 1));((4,'+'),(2,Some('0'), 1));((4,'*'),(2,Some('0'), 1));((4,'_'),(8,None, 1)); 
     ((5,'0'),(8,None, 1));((5,'1'),(8,None, 1));((5,'+'),(3,Some('1'), 1));((5,'*'),(2,Some('0'), 1));((5,'_'),(8,None, 1)); 
     ((6,'0'),(8,None, 1));((6,'1'),(8,None, 1));((6,'+'),(2,Some('0'), 1));((6,'*'),(3,Some('1'), 1));((6,'_'),(8,None, 1)); 
     //7はaccept(正常終了を表します。) 
     //8,9はエラー処理(互いに相手を呼び合い終了しなくします。) 
     ((8,'0'),(9,None,-1));((8,'1'),(9,None,-1));((8,'+'),(9,None,-1));     ((8,'*'),(9,None,-1));     ((8,'_'),(9,None,-1)); 
     ((9,'0'),(8,None, 1));((9,'1'),(8,None, 1));((9,'+'),(8,None, 1));     ((9,'*'),(8,None, 1));     ((9,'_'),(8,None, 1)); 
 
    ] 
    |> Map.ofList;; 
 
val changeTB : Map<(int * char),(int * char option * int)> = 
  map 
    [((1, '*'), (8, null, 1)); ((1, '+'), (8, null, 1)); 
     ((1, '0'), (2, null, 1)); ((1, '1'), (3, null, 1)); 
     ((1, '_'), (8, null, 1)); ((2, '*'), (8, null, 1)); 
     ((2, '+'), (8, null, 1)); ((2, '0'), (4, null, 1)); 
     ((2, '1'), (5, null, 1)); ...] 
      
これはi j + k * (普通の書き方をすると(i+j)*k)の計算をするプログラムです。 
ただしi,j,kは0か1で 1+1=0と定義するものとします。 
テープは最初に11+1*とか10+0*等の形で、印字されているものとし、ヘッド位置は左端にあるものとします。(最後にヘッドが停止した位置の値が計算結果です。) 
 
テープもマップで表すことにして、例えば01+1*を計算させるためには次のようにマップの初期設定を次のようにします。 
 
> let init_tape = 
    [(0,'0');(1,'1');(2,'+');(3,'1');(4,'*')] 
    |> Map.ofList;; 
 
val init_tape : Map<int,char> = 
  map [(0, '0'); (1, '1'); (2, '+'); (3, '1'); (4, '*')] 
 
では上の動作対応Mapと、現在のテープおよび、現在の状態ナンバー、現在のヘッド位置を引数にして、変化したテープ、次の状態ナンバー、次のヘッド位置を返す関数を定義します。 
 
> let TM_OneStepExecResult (in_changeTB: Map<(int * char),(int * char option * int)>) ((curTape:Map<int,char>),curStateNo,curPos) = 
        //mapにindex登録があれば、indexに対応するchar、なければ'_'(blank) 
        let charAtPos = 
                if Map.containsKey curPos curTape then 
                    curTape.[curPos] 
                else '_' 
        let (nextStateNo,doWrite,headMove) = in_changeTB.[(curStateNo,charAtPos)] 
        let nextTape = 
            if doWrite.IsNone then 
                curTape 
            else 
                if doWrite.Value = '_' then 
                    Map.remove curPos curTape 
                else 
                    Map.add curPos doWrite.Value curTape 
        let nextPos = curPos + headMove 
        (nextTape,nextStateNo,nextPos);; 
 
val TM_OneStepExecResult : 
  Map<(int * char),(int * char option * int)> -> 
    Map<int,char> * int * int -> Map<int,char> * int * int 
 
先ほどのinit_tape と動作対応Mapを用いて、一ステップだけ動かしてみます。 
 
> TM_OneStepExecResult changeTB (init_tape,1,0)//1は最初の状態、0は最初の位置;; 
val it : Map<int,char> * int * int = 
  (map [(0, '0'); (1, '1'); (2, '+'); (3, '1'); (4, '*')], 2, 1) 
 
これで、状態2に移り、位置が1になったことがわかります。 
 
では、動作対応Map、初期テープ、最初の状態No.、最初のヘッド位置、終了状態No.を与えると、最後まで連続して実行する関数を定義します。 
 
> let TM_Exec in_changeTB in_initTape in_initStateNo in_startPos in_finStateNo  = 
        let oneStepExec = TM_OneStepExecResult in_changeTB 
        let rec execAll ((curTape:Map<int,char>),curStateNo,curPos) = 
            printfn "%A" (curTape,curStateNo,curPos) //表示用関数で表示 
            if curStateNo = in_finStateNo then 
                                (curTape,curStateNo,curPos) 
            else 
                let nextArg = oneStepExec (curTape,curStateNo,curPos) 
                execAll nextArg 
        execAll (in_initTape,in_initStateNo,in_startPos);; 
 
val TM_Exec : 
  Map<(int * char),(int * char option * int)> -> 
    Map<int,char> -> int -> int -> int -> Map<int,char> * int * int 
 
>  
 
では先ほど定義した、init_tape(01+1*の計算用)を試しに使って実行してみます。 
 
> TM_Exec changeTB init_tape 1 0 7 ;; 
(map [(0, '0'); (1, '1'); (2, '+'); (3, '1'); (4, '*')], 1, 0) 
(map [(0, '0'); (1, '1'); (2, '+'); (3, '1'); (4, '*')], 2, 1) 
(map [(0, '0'); (1, '1'); (2, '+'); (3, '1'); (4, '*')], 5, 2) 
(map [(0, '0'); (1, '1'); (2, '1'); (3, '1'); (4, '*')], 3, 3) 
(map [(0, '0'); (1, '1'); (2, '1'); (3, '1'); (4, '*')], 6, 4) 
(map [(0, '0'); (1, '1'); (2, '1'); (3, '1'); (4, '1')], 3, 5) 
(map [(0, '0'); (1, '1'); (2, '1'); (3, '1'); (4, '1')], 7, 4) 
val it : Map<int,char> * int * int = 
  (map [(0, '0'); (1, '1'); (2, '1'); (3, '1'); (4, '1')], 7, 4) 
   
最後のテープの状態から、ヘッド位置は4であることがわかり、4の位置には1が書き込まれているので、1が計算結果となります。 
 
最後に、状態番号はどのような意味になっているのかを少し説明しておきます。 
これはスタックマシンを模していて 
状態1はスタックが空で、今から「2項演算対象の一つ目の数値」をスタックに押し込む状態を表しています。 
0なら状態2へ、1なら状態3へ移行します。 
状態2は0がスタックに積まれた状態で、読み取った数字が0なら状態5へ、1なら状態6へ移行します。 
状態5は0が2個スタックに積まれた場合なので、+を読み込んだ時は計算結果の0が1個だけスタックに積まれた状態、すなわち状態2へ移行します...という意味合いでこのチューリングマシンのプログラムは書かれています。 
 
次回はWinソフト化します。今回のコードは以下の通りです。 
 
let init_tape = 
    [(0,'0');(1,'1');(2,'+');(3,'1');(4,'*')] 
    |> Map.ofList 
 
let changeTB = // _はブランクを表す 
    [((1,'0'),(2,None, 1));((1,'1'),(3,None, 1));((1,'+'),(8,None, 1));     ((1,'*'),(8,None, 1));     ((1,'_'),(8,None, 1)); 
     ((2,'0'),(4,None, 1));((2,'1'),(5,None, 1));((2,'+'),(8,None, 1));     ((2,'*'),(8,None, 1));     ((2,'_'),(7,None,-1)); 
     ((3,'0'),(5,None, 1));((3,'1'),(6,None, 1));((3,'+'),(8,None, 1));     ((3,'*'),(8,None, 1));     ((3,'_'),(7,None,-1)); 
     ((4,'0'),(8,None, 1));((4,'1'),(8,None, 1));((4,'+'),(2,Some('0'), 1));((4,'*'),(2,Some('0'), 1));((4,'_'),(8,None, 1)); 
     ((5,'0'),(8,None, 1));((5,'1'),(8,None, 1));((5,'+'),(3,Some('1'), 1));((5,'*'),(2,Some('0'), 1));((5,'_'),(8,None, 1)); 
     ((6,'0'),(8,None, 1));((6,'1'),(8,None, 1));((6,'+'),(2,Some('0'), 1));((6,'*'),(3,Some('1'), 1));((6,'_'),(8,None, 1)); 
     //7はaccept 
     //8,9はエラー処理(交互に呼び出し、エンドレスループに入る) 
     ((8,'0'),(9,None,-1));((8,'1'),(9,None,-1));((8,'+'),(9,None,-1));     ((8,'*'),(9,None,-1));     ((8,'_'),(9,None,-1)); 
     ((9,'0'),(8,None, 1));((9,'1'),(8,None, 1));((9,'+'),(8,None, 1));     ((9,'*'),(8,None, 1));     ((9,'_'),(8,None, 1)); 
 
    ] 
    |> Map.ofList 
 
let TM_OneStepExecResult (in_changeTB: Map<(int * char),(int * char option * int)>) ((curTape:Map<int,char>),curStateNo,curPos) = 
        //mapにindex登録があれば、indexに対応するchar、なければ'_'(blank) 
        let charAtPos = 
                if Map.containsKey curPos curTape then 
                    curTape.[curPos] 
                else '_' 
        let (nextStateNo,doWrite,headMove) = in_changeTB.[(curStateNo,charAtPos)] 
        let nextTape = 
            if doWrite.IsNone then 
                curTape 
            else 
                if doWrite.Value = '_' then 
                    Map.remove curPos curTape 
                else 
                    Map.add curPos doWrite.Value curTape 
        let nextPos = curPos + headMove 
        (nextTape,nextStateNo,nextPos) 
  
let TM_Exec in_changeTB in_initTape in_initStateNo in_startPos in_finStateNo  = 
        let oneStepExec = TM_OneStepExecResult in_changeTB 
        let rec execAll ((curTape:Map<int,char>),curStateNo,curPos) = 
            printfn "%A" (curTape,curStateNo,curPos) //表示用関数で表示 
            if curStateNo = in_finStateNo then 
                                (curTape,curStateNo,curPos) 
            else 
                let nextArg = oneStepExec (curTape,curStateNo,curPos) 
                execAll nextArg 
        execAll (in_initTape,in_initStateNo,in_startPos) 
 
 
 
TM_Exec changeTB init_tape 1 0 7  |> ignore 
 
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。