Microsoft PowerPoint - 2-LispProgramming-full

Size: px

Start display at page:

Download "Microsoft PowerPoint - 2-LispProgramming-full"

てるえかせ
5 years ago
Views:

2 今回あらすじ 1. Lisp の実践的な使い方を学習する. 2. Lisp インタープリタの動かし方, 電卓的使い方, 関数定義, 条件分岐,S 式の基本操作, プログラミング手法, プロトタイピング法などを中心に解説する. 3. チューリングマシンのシミュレータの構成方法を例にプログラミングの実際を学習する.

3 Lisp プログラミングの流れ表現人工知能プログラム私の人工知能理論解釈実行表示インタープリタ Gnu Common Lisp

4 情報の流れ入力テープとヘッド位置の外部表現チューリングマシンの状態遷移機械の外部表現入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態シミュレータチューリングマシンの状態表示

5 ((start q0) 初期状態がq0である (terminal q5) 停止状態はq5である. (states 以下では, 各状態における状態遷移規則を表す (q0 (0 (Right) q1)) 状態 q0で, 0を見たらヘッドを右に移動し, 状態 q1に遷移 (q1 (0 (Right) q1) 状態 q1で, 0を見たらヘッドを右に移動し, 状態 q1に遷移 (1 B q2)) 状態 q1で, 1を見たらBと書き換え, 状態 q2に遷移 (q2 (A (Left) q2) 状態 q2で, Aを見たらヘッドを左に移動し, 状態 q2に遷移 (B (Left) q2) 状態 q2で, Bを見たらBと書き換え, 状態 q2に遷移 (0 A q3)) 状態 q2で,0を見たらaと書き換え, 状態 q3に遷移 (q3 (1 B q2) 状態 q3で,1を見たらbと書き換え, 状態 q2に遷移 (A (Right) q3) 状態 q3で,aを見たらヘッドを右に移動し, 状態 q3に遷移 (B (Right) q3) 状態 q3で,bを見たらヘッドを右に移動し, 状態 q3に遷移 (_ (Left) q4)) (q4 (A (Left) q4) 状態 q4で,aを見たらヘッドを左に移動し, 状態 q4に遷移 (B (Left) q4) 状態 q4で,bを見たらヘッドを左に移動し, 状態 q4に遷移 ( q5)))) 状態 q4で, 空白 _ を見たら, 状態 q5に遷移状態 q3 で, 空白 _ を見たらヘッドを左に移動し, 状態 q4 に遷移

6 変数 input 入力テープとヘッド位置の外部表現 tm チューリングマシンの状態遷移機械の外部表現 left-stack current-cell right-stack current-state 入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態 test シミュレータ (print による副作用 ) チューリングマシンの状態表示

7 準備 1 input tm (let* ( [1] 入力テープとヘッド位置の外部表現 (current-state (second (assoc 'start tm))) ) ) チューリングマシンの状態遷移機械の外部表現 left-stack current-cell right-stack current-state 入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態 tm=((start test q0) (terminal q5) ) [1] Current-state=q0 シミュレータ (print による副作用 ) チューリングマシンの状態表示

8 準備 2 input 入力テープとヘッド位置の外部表現 [1] (setq right-stack (cdr (member '* input))) [2] (cond (right-stack [2] (setq current-cell (car right-stack)) [2] (setq right-stack (cdr right-stack))) [2] (t (setq current-cell '_))) [3] (dolist tm (cell input) [3] (cond ((eq cell '*) (return))) [3] (push cell left-stack)) チューリングマシンの状態遷移機械の外部表現 left-stack current-cell right-stack current-state 入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態 input=(1 test 2 3 * ); left-stack=(); current-cell=nil; right-stack= () [1] right-stack=( ) [2] シミュレータ current-cell=4; right-stack=(5 6 7) [3] left-stack=(3 2 1) (print による副作用 ) チューリングマシンの状態表示

9 中心部分 input 入力テープとヘッド位置の外部表現 tm チューリングマシンの状態遷移機械の外部表現 left-stack current-cell right-stack current-state 入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態 test シミュレータ (print による副作用 ) チューリングマシンの状態表示

10 典型的な状況例入力テープチューリングマシンの場合状態遷移機械開始 1/B, L A/A, L B/B, L 0/A, R A/A, R B/B, R A/A, L B/B, L q 0 q 1 q 2 q 3 q 4 q 5 1/B, L _/_, L _/_, R

11 チューリングマシン典型的な状況例入力テープ B 1 1 状態遷移機械開始 1/B, L A/A, L B/B, L 0/A, R A/A, R B/B, R A/A, L B/B, L q 0 q 1 q 2 q 3 q 4 q 5 1/B, L _/_, L _/_, R

12 中心部分 left-stack tm チューリングマシンの状態遷移機械の外部表現 current-cell right-stack current-state 入力テープ左 ( 逆順 ) ヘッド位置のマス目の内容入力テープ右現在状態 test シミュレータ tm=( (states (q1 (0 0 right q1) (1 B left q2)) ) ) left-stack=(0 0 0); current-cell=1; right-stack=(1 1) current-state=q1 [?] left-stack=(0 0); current-cell=0; right-stack=(b 1 1) current-state=q2

13 中心部分 tm=( (states (q1 (0 0 right q1) (1 B left q2)) ) ) left-stack=(0 0 0); current-cell=1; right-stack=(1 1) current-state=q1 [?] left-stack=(0 0); current-cell=0; right-stack=(b 1 1) current-state=q2 [1] (setq rules (cdr (assoc current-state states))) [2] (setq rule (assoc current-cell rules)) [3] (cond ((null rule) (return))) [4] (setq current-cell (second rule)) [5] (setq current-state (fourth rule)) [6] (case (third rule) [7] (right (cond [7] (right-stack [7] (setq left-stack `(,current-cell.,left-stack)) [7] (setq current-cell (car right-stack)) [7] (setq right-stack (cdr right-stack))) [7] (t (setq left-stack `(,current-cell.,left-stack)) [7] (setq current-cell '_)))) [7] (left (cond [7] (left-stack [7] (setq right-stack `(,current-cell.,right-stack)) [7] (setq current-cell (car left-stack)) [7] (setq left-stack (cdr left-stack))) [7] (t (setq right-stack `(,current-cell.,right-stack)) [7] (setq current-cell '_))))

14 プログラム test (defun test () (let* ((tm tm0) (input input-tm0) (left-stack nil) (right-stack) (current-state (second (assoc 'start tm))) (current-cell nil) (states (cdr (assoc 'states tm))) (terminal-states (cdr (assoc 'terminal tm))) (rules nil) (rule nil) (counter 1) (credits 1)) (setq right-stack (cdr (member '* input))) (cond (right-stack (setq current-cell (car right-stack)) (setq right-stack (cdr right-stack))) (t (setq current-cell '_))) (dolist (cell input) (cond ((eq cell '*) (return))) (push cell left-stack)) (loop (cond ((<= credits counter) (princ "How many more steps to go?") (terpri) (setq credits (read)) (cond ((<= credits 0) (return)) (t (setq counter 0)))) (t (setq counter (1+ counter)))) (princ "======================================") (terpri) (print-state left-stack current-cell right-stack current-state) (cond ((member current-state terminal-states) (princ "======================================") (terpri) (princ "*** Halt in a termnial state ***") (terpri) (princ "======================================") (terpri) (return))) ))) [1] (setq rules (cdr (assoc current-state states))) [2] (setq rule (assoc current-cell rules)) [3] (cond ((null rule) (return))) [4] (setq current-cell (second rule)) [5] (setq current-state (fourth rule)) [6] (case (third rule) [7] (right (cond [7] (right-stack [7] (setq left-stack `(,current-cell.,left-stack)) [7] (setq current-cell (car right-stack)) [7] (setq right-stack (cdr right-stack))) [7] (t (setq left-stack `(,current-cell.,left-stack)) [7] (setq current-cell '_)))) [7] (left (cond [7] (left-stack [7] (setq right-stack `(,current-cell.,right-stack)) [7] (setq current-cell (car left-stack)) [7] (setq left-stack (cdr left-stack))) [7] (t (setq right-stack `(,current-cell.,right-stack)) [7] (setq current-cell '_))))

15 ホームワーク次のチューリングマシンの動作をシミュレートせよ入力テープ状態遷移機械開始 0/X, R Y/Y, R 1/Y, L q 0 q 1 q 2 Y/Y, L 0/0, L X/X, R Y/Y, R _ / _, R q 3 q 4 Y/Y, R [Hopcroft 2001]

16 ホームワーク次のチューリングマシンの動作を分析せよ入力テープ _ 状態遷移機械 _ /_, R 1/1, R 開始 0/ _, R 1/1, R 0/1, L q 2 q 0 q 1 q 3 1/ _, R _ / _, L 0/0, L 1/1, L _ / _, R q 5 q 6 _ / 0, R q 4 0/ _, R 1/ _, R 0/ 0, L 1/ _, L [Hopcroft 2001]

17 ホームワーク次のチューリングマシンの動作を分析せよ入力テープ状態遷移機械開始 0/0, L _ /1, L q 0 q 1 _/ _, R q 2 _ / _, R q 11 1/1, R 0/0, L 1/1, L 0/ _, R 1/1, R q 3 q 4 0/X, R 1/1, R _ /0, L 0/0, L 1/1, L q 6 q 7 0/0, L q 5 1/1, L 1/1, R X/X, R 0/0, L 1/1, L q 8 q 9 q 10 X/0, L q 14 1/ _, R q 13 0/ _, R 1/ _, R q 12 _/ _, R [Hopcroft 2001]

r3.dvi

r3.dvi / 94 2 (Lisp ) 3 ( ) 1994.5.16,1994.6.15 1 cons cons 2 >(cons a b) (A. B).? Lisp (S ) cons 2 car cdr n A B C D nil = (A B C D) nil nil A D E = (A (B C) D E) B C E = (A B C D. E) A B C D B = (A. B) A nil.