プログラマから見えるCPU 一番下のレベルでコンピュータ上のプログラムがど のように表現されているかを理解する プログラムがどう表現されているか プログラムはコンピュータのメモリ上に載っている コンピュータのメモリには数字しか格納できない したがってプログラムは数字である どう表現されているのか 数

Transcription

1 計算機学 モデル計算機とソフトウェア

2 プログラマから見えるCPU 一番下のレベルでコンピュータ上のプログラムがど のように表現されているかを理解する プログラムがどう表現されているか プログラムはコンピュータのメモリ上に載っている コンピュータのメモリには数字しか格納できない したがってプログラムは数字である どう表現されているのか 数字で表現された 命令 機械語 CPUごとに異なる

3 コンピュータの構成 CPU ALU メモリ レジスタ キャッシュ バス I/O 周辺機器

4 コンピュータの構成 CPU 演算 データ転送のた めの数値の一時保存場 所 データの記憶領域 アドレス 番地 で管理 バス メモリとのデータ転送を 高速化 メモリ データの算術演算 論 理演算を行う レジスタ キャッシュ 計算やデータ転送 制 御などを司る ALU データを転送する経路 I/O 周辺機器との入出力イ ンタフェース

5 CPUアーキテクチャ CPUの設計方針及びインタフェースの総称 命令セットアーキテクチャ マイクロアーキテクチャ アドレス空間 データの処理単位の長さ 命令 の種類 機械語と命令の対応 レジスタの数や種類 レジスタや演算器 ALU の論理構成 キャッシュの構成や容量 システムアーキテクチャ 各部の実装方

6

7 CPUアーキテクチャの種類 CISC (Complex Instruction Set Computer) 1命令が複雑で高度な動作をする 回路は複雑 命令あたりの動作は遅い x86系cpuなど RISC (Reduced Instruction Set Computer) 1命令は単純な動作 回路は単純 命令あたりの動作は速い ARM, MIPSなど

8 モデルCPU COMET-II 情報処理技術者試験用CPU) 命令記述言語はCASL-IIと呼ばれる 16bit CPU (16bit/word) アドレス空間 64kword (128kbyte) レジスタ構成 SP (16) 8個の汎用レジスタ(GR) プログラムレジスタ(PR) スタックポインタ(SP) フラグ(FR) PR (16) FR (3) GR0 (16) GR1 (16) GR2 (16) GR3 (16) GR4 (16) GR5 (16) GR6 (16) GR7 (16)

9 CPUの動作 1.プログラムレジスタ(PR)に格納された数値をアドレ スとみなし そのアドレスのメモリに格納された数 値を取り出す 2.プログラムレジスタの値を１増やす 3.取り出した数値を 命令 とみなし 解読 4.解読した内容に応じた動作を行う 5.1に戻る

10 命令セット データ転送命令 算術演算 論理演算命令 比較演算命令 シフト演算命令 分岐命令 スタック操作命令 サブルーチン命令 その他

11 命令の形 命令 [オペランド] 例 LD GR1,#FF00,GR2 例 JNZ #001E オペランド 操作対象 の形 対象レジスタ1個 POP GR1 対象レジスタ2個 LD GR1, GR2 数値 アドレス JUMP #FF00 数値とレジスタ LAD GR0, 120 数値とレジスタ2個 ST GR0, #FF00, GR1

12 アドレッシングモード 例 LD GRx, 対象 LD GR0, GR1 GR0にGR1の内容を格納 LD GR0, #FF00 対象の内容をGRxに格納する アドレス FF00(16進)のメモリの内容をGR0に格納 LD GR0, #FF00, GR1 インデックス修飾 FF00(16進)にGR1の内容を加えた アドレスの内容をGR0に格納 右端のレジスタは GR1 GR7のみ

13 データ転送命令 レジスタとレジスタ レジスタとメモリの間でデータ を転送する LD GRx, {GRy アドレス アドレス, GRy} LAD GRx, {アドレス アドレス, GRy} 対象をGRxに転送 対象のアドレスそのものをGRxに格納 LAD GR0, #0010 ; GR0に16を格納 ST GRx, {アドレス アドレス, Gry} GRxの内容を指定したアドレスのメモリに格納

14 算術演算 論理演算命令 命令 GRx, 対象 GRxと対象を演算し 結果をGRxに格納 ADDA GRx, 対象 ; 算術加算 ADDL GRx, 対象 ; 論理加算 SUBA GRx, 対象 ; 算術減算 SUBL GRx, 対象 ; 論理減算 AND GRx, 対象 ; 論理積 OR GRx, 対象 ; 論理和 XOR GRx, 対象 ; 排他的論理和

15 算術加算と論理加算 算術加算/減算は数値を符号付整数とみなす 論理加算/減算は数値を符号なし整数とみなす 16bit符号なし整数 0~ bit符号付整数 ~32767 違いは何 符号なし =32768 問題なし 符号付 = オーバーフロー 符号なし 0-1 = アンダーフロー 符号付 0-1 = -1 問題なし

16 符号付整数と２の補数表現 nビットで数を表現する 8bit符号なし bit符号付き ２の補数による負数の表現 正の数 00(16) 7F(16) 負の数 FF(16) 80(16) : : の補数表現の利点 通常の加減算がそのまま使える 最上位ビットを見ると数の正負がわかる

17 2の補数表現 ある数の 2の補数 の求め方 すなわち符号の反 転 まず 1の補数 を求める 2進表現された数の各桁の 1 と 0 を反転する 次にその数に1を加える 例 -9 を8bit の２の補数表現で表す 9(10) = (2) NOT( ) = = 答

18 演習 次のを8ビット2進数で計算してみよう (-5) -6-2 [=(-6)+(-2)]

19 演算とフラグ 演算結果によってフラグレジスタ (FR)の内容が セットされる FR 3ビット には OF, SF, ZF 各1ビット のフラグが含 まれる OF (Overflow Flag) 演算結果がオーバーフローまた はアンダーフローした時1になる SF (Sign Flag): 演算結果が負のとき1になる ZF (Zero Flag): 演算結果が０のとき1になる 条件付き分岐命令で参照される

20 比較演算命令 減算をして結果のフラグだけをセットする 減算結 果は保存されない CPA GRx, 対象 ; 算術比較 CPL GRx, 対象 ; 論理比較 例 CPA GR0, GR1 ; GR0-GR1 を計算 GR0=GR1なら ZFに1がセットされる GR0<GR1なら SFに1がセットされる

21 シフト演算命令 レジスタの各ビットを右か左にずらす SLA GRx, シフト量 ; 算術左シフト 数値的に2倍 SRA GRx, シフト量 ; 算術右シフト 数値的に1/2倍 SLL GRx, シフト量 ; 論理左シフト 単純なシフト SRL GRx, シフト量 ; 論理右シフト 単純なシフト 算術シフト 論理シフト 0 0 0

22 シフト演算命令 演算例 8bit 本当は16bit 元の数値 SLA SRA 算術シフト SLL SRL 論理シフト 0 0 0

23 分岐命令 条件を満たす場合に 指定アドレスから実行 JUMP アドレス ; 指定アドレスから実行する JPL アドレス ; 演算結果が正の場合 JMI アドレス ; 演算結果が負の場合 JNZ アドレス ; 演算結果が0でない場合 JZE アドレス ; 演算結果が0の場合 JOV アドレス ; オーバーフローが起きた場合 条件 はフラグレジスタの状態に対応 正 SF=0 かつ ZF=0 負 SF=1 零 ZF=0 非零 ZF=1

24 分岐命令 どうやって実行順序を変えるのか 実行アドレスは PR レジスタに格納されている PR レジスタに値を格納すれば 次はそのアドレスから 実行が始まる 分岐命令はレジスタ間のデータ転送命令の一種

25 分岐命令の使用例 0000: LAD GR0,0 ;GR0=0 0002: LAD GR1,1 ;GR1=1 0004: LAD GR2,1 ;GR2=1 0006: B LAD GR3,11 ;GR3= : 2401 ADDA GR0,GR1 ;GR0+=GR1 0009: 2412 ADDA GR1,GR2 ;GR1+=GR2 000A: 4413 CPA GR1,GR3 ;GR1-GR3 000B: JNZ #0008 ;if not zero 0008

26 スタック操作命令 スタック 各種データを一時保存しておくメモリ データをスタックに入れる操作(PUSH)と取り出す操作 (POP)が対になる 最後に入れたデータが最初に取り出される PUSH, POP命令 PUSH 値 [, GRy] SPレジスタの値を-1し SPの示すアドレスのメモリに指定し た値(+GRy)を格納する POP GRy SPレジスタの値が示すアドレスのメモリの内容をGRyに格納 し SPの値を+1する

27 PUSHとPOP PUSH 0,GR1 PUSH 0,GR2 GR0 GR GR FFFF FFFE SP POP GR2 途中の処 理でGR1 とGR2の 値が破壊 される POP GR FFFD FFFD FFFE FFFF FFF8 FFF9 FFFA FFFB FFFC FFFD FFFE FFFF 5

28 サブルーチン命令 関数やサブルーチンを実現する 任意のアドレスから特定のアドレスにジャンプ し サブルーチン実行後に元のアドレスに戻ってく る CALL アドレス[,GRy] 現在実行中のアドレスの次のアドレスをスタックにPUSH 指定したアドレスにジャンプ RET スタックからアドレスをPOPして そのアドレスにジャンプ

29 サブルーチン命令 関数やサブルーチンを実現する 任意のアドレスから特定のアドレスにジャンプ し サブルーチン実行後に元のアドレスに戻ってく る CALL アドレス[,GRy] 現在実行中のアドレスの次のアドレスをスタックにPUSH 指定したアドレスにジャンプ RET スタックからアドレスをPOPして そのアドレスにジャンプ

30 サブルーチン 同じ処理をいろいろなところから利用する : CALL #2000 : : CALL #2000 : 2000 処理内容 : RET : CALL #2000 : : CALL #2000 : 2000 処理内容 : RET

31 サブルーチンの実現 : 1200 CALL # : : CALL #2000 : 処理内容 : RET PR SP FFFD FFFE FFFF 1200 FFFF : 1200 CALL # : : CALL #2000 : 処理内容 : RET PR 2000 SP FFFE FFFD FFFE FFFF 1202

32 サブルーチンの実現 : 1200 CALL # : : CALL #2000 : 処理内容 : RET PR SP 2024 FFFE FFFD FFFE FFFF 1202 : 1200 CALL # : : CALL #2000 : 処理内容 : RET PR 1202 SP FFFF FFFD FFFE FFFF 1202

33 その他 SVC アドレス[,GRy] アドレスを引数としてシステムコール 何が起きるかはOS依存 OSの機能を呼び出すために使う NOP 何もしない

34 命令コード それぞれの命令に数値が対応する 命令は1ワード(16bit)または2ワード(32bit) 命令語の構成 1ワード目 OP1 (4) OP2 (4) R1 (4) 0: NOP 1: データ転送命令 2: 加減算命令 3: 論理演算命令 4: 比較命令 5: シフト命令 6: 分岐命令 R2 (4) 7: スタック操作命令 8: サブルーチン命令 F: SVC

35 命令コード 算術演算の場合の例 OP1 2 OP2 R1,R2 命令長 命令 0 0~7 2 ADDA R1, addr, R2 1 0~7 2 SUBA R1, addr, R2 2 0~7 2 ADDL R1, addr, R2 3 0~7 2 SUBL R1, addr, R2 4 0~7 1 ADDA R1, R2 5 0~7 1 SUBA R1, R2 6 0~7 1 ADDL R1, R2 7 0~7 1 SUBL R1, R2 ADDL GR0, #FF00, GR3 SUBA GR2, GR4 ADDA GR2, # FF

36 プログラム例 GR1とGR2に入っている整数の乗算サブルーチン 0000: 0002: 0004: 0005: 0006: 0008: GR2 0を仮定 結果はGR0に格納 GR3の内容は破壊される LAD GR0,0 LAD GR3,1 ADDA GR0,GR1 SUBL GR2,GR3 JNZ #0004 RET ;GR0 0 ;GR3 1 ;GR0 GR0+GR1 ;GR2 GR2-GR3 ;if not zero goto 0004 ;return

37 プログラム例 GR1とGR2に入っている整数の乗算サブルーチン 0000: 0002: 0004: 0006: 0008: 0009: 000A: 000C: 000D: 000E: GR2,GR3を破壊しないバージョン LAD GR0,0 PUSH 0,GR2 PUSH 0,GR3 LAD GR3,1 ADDA GR0,GR1 SUBL GR2,GR3 JNZ #0008 POP GR3 POP GR2 RET ;GR0 0 ;GR2を退避 ;GR3を退避 ;GR3 0 ;GR0 GR0+GR1 ;GR2 GR2-GR3 ;if(not zero) goto #0008 ;GR3を復帰 ;GR2を復帰 ;return

38 演習 これは何をするプログラムか説明せよ 入力は GR1 アドレス GR2 正の整数 出力は GR3 整数 0011番地の 1 は定数 0000: 0002: 0004: 0006: 0008: 000A: 000C: 000E: 0010: 0011: LD GR3,0,GR1 ADDL GR1,#0011 SUBL GR2,#0011 JZE #0010 CPA GR3,0,GR1 JPL #0002 LD GR3,0,GR1 JUMP #0002 RET 1

39 機械語とニモニック 計算機は機械語 数字で表される命令列 で動く これではわかりにくいので 命令を表現する記号 ニモニック mnemonic でプログラムを書く 動作との対応がつけやすい 機械語とニモニックは1対1対応 機械語列にするには変換が必要 Mnemonic: 記憶術 LAD GR0,0 LAD GR3,1 ADDA GR0,GR1 SUBL GR2,GR3 JNZ #0004 RET

40 アセンブリ言語 ニモニックから機械語への変換 アセンブル 組立 表参照と簡単なルールで変換できる もっと便利に アセンブリ言語 疑似命令 ラベル ジャンプ先やデータのアドレスを自動計算 マクロ プログラム開始 終了の宣言 定数領域 データ領域の宣言 よく使う命令列を1行で表現する 機械語への変換はアセンブラが行う

41 アセンブリ言語の例 コメント ラベル ; GR1とGR2の掛け算 MULT START LAD GR0,0 LOOP ADDA GR0,GR1 SUBL GR2,ONE JNZ LOOP RET ONE DC 1 END 疑似命令

42 アセンブリ言語 疑似命令 命令と同じ形で記述されるが 命令そのものではな い START: プログラムの最初を指定する ラベル必須 END: プログラムの終わりを指定する DC: 定数を定義する メモリ上にその数字が格納されるが 命令ではない DS: データ領域を定義する メモリ上に指定した語数の領域が確保される データ処理などに使う用途

43 アセンブリ言語 ラベル プログラム内のアドレスやデータのアドレスを記号で参 照する 実際のアドレスへの変換はアセンブラが行う 命令を挿入 削除した時にも変更しなくてよい マクロ よく使う複数の命令列を1つの命令のように書ける IN アドレス,長さ OUT アドレス,長さ RPUSH RPOP 指定したメモリにデータを入力 指定したメモリの内容を出力 全レジスタをPUSH 全レジスタをPOP

44 アセンブリ言語 定数の記述 MULT LOOP 定数は演算などに頻繁に使うので あたかも定数を直 接演算できるかのように書ける START 自動 LAD GR0,0 ADDA GR0,GR1 生成 SUBL GR2,=1 JNZ LOOP RET END MULT START LAD GR0,0 LOOP ADDA GR0,GR1 SUBL GR2,CONST1 JNZ LOOP RET CONST1 DC 1 END

45 アセンブラによる処理 アセンブリ言語 のプログラム アセンブラ ライブラリ 機械語 のプログラム リンカ 実行可能 プログラム

46 演習 アセンブリ言語を使い 下記のプログラムをわかりやすく記述せよ 疑似命令: START, END ラベル 定数演算 0000: 0002: 0004: 0006: 0008: 000A: 000C: 000E: 0010: 0011: LD GR3,0,GR1 ADDL GR1,#0011 SUBL GR2,#0011 JZE #0010 CPA GR3,0,GR1 JPL #0002 LD GR3,0,GR1 JUMP #0002 RET 1

47 アセンブリ言語によるプログラミング CASL-IIを使ってさまざまなプログラムを書いてみ る 通常は高級言語(Cなど)で書く操作をアセンブラで書い たらどうなるか コンピュータの基本的な動きを理解する

48 高速な乗算 加算を繰り返す乗算は簡単だが効率が悪い a b=(a+a+...+a) aをb回加算 筆算の要領で計算する 乗算の値によらず 桁数に比例する計算で済む X X

49 高速な乗算 アルゴリズム Z A B) Z 0 For i=16 to 1 by -1 If Bの最下位ビットが1 then Z Z+A End if A A*2 B B/2 End for X

50 高速な乗算 i A B Z

51 注意点 GR2の下1ビットを取り出す AND GR2,=1 これを実行するとGR2の内容が破壊される GR2の内容を保存したい場合は別なレジスタを使う LD GR4,GR2 AND GR4,=1 GR1の値を2倍する SLA GR1,1 ; 1ビット算術左シフト GR2の値を1/2倍する SRA GR2,1 ; 1ビット算術右シフト

52 アセンブリ言語で書いてみる Z: GR0, A: GR1, B: GR2, i: GR3 とする FMULT LOOP SKIP1 START LAD GR0,0 LAD GR3,16 LD GR4,GR2 AND GR4,=1 JZE SKIP1 ADDA GR0,GR1 SLA GR1,1 SRA GR2,1 SUB GR3,=1 JNZ LOOP RET END ; ; ; ; ; ; ; ; ; ; ; GR0 0 GR3 16 G4 G2 G4 G4 and 1 if not zero then G0 G0+G1 G1 G1*2 G2 G2/2 G3 G3-1 if not zero goto LOOP return

53 再帰呼び出しによる計算 C言語でよくあるやつ int factorial(int n) { if (n == 0) return 1 return n*factorial(n-1) } さっきのFMULTを使ってみる FMULTはGR1,GR2を入力としてGR0を出力とする GR4を破壊する

54 再帰呼び出しによる計算 GR5を入力 GR0を出力とする 基本的な考え方 GR5が0ならGR0に1を代入して終了 GR5を退避 GR5を1減らして階乗を計算 GR0 GR5を復帰 GR5とGR0の積をGR0に代入して終了

55 プログラム FACT SKIP2 START CPA GR5,=0 JNZ SKIP2 LAD G0,1 RET PUSH 0,GR5 SUBA GR5,=1 CALL FACT LD GR1,GR0 POP GR5 LD GR2,GR5 CALL FMULT RET END ; ; ; ; ; ; ; ; ; ; ; ; GR5-0 if zero then GR0 1 return GR5を保存 GR5 GR5-1 GR0 GR5の階乗 GR1 GR0 GR5を復帰 GR2 GR5 GR0 GT1*GR2 return

56 メモリの内容の探索 GR1から始まるGR2個のメモリの中にGR3の内容 があるかどうかをチェック 存在する場合にはGR0にアドレスを返す 存在しない場合にはGR0に0を返す GR1=#8000,GR2=7,GR3=34 GR0=#8004 アドレス GR1=#8000,GR2=4,GR3=34 GR0= GR1=#8000,GR2=7,GR3=322 GR0=8005 値 23

57 アルゴリズム While GR2 > 0 If M[GR1] = GR3 then GR0 GR1 Return End if GR2 GR2-1; GR1 GR1+1 End while GR0 0 return

58 プログラム SEARCH LOOP SKIP1 SKIP2 BREAK START CPL GR2,=0 JNZ SKIP1 JUMP BREAK CPA GR3,0,GR1 JNZ SKIP2 LD GR0,GR1 RET ADDL GR1,=1 SUBL GR2,=1 JUMP LOOP LAD GR0,0 RET END ; ; ; ; ; ; ; ; ; ; ; ; GR2-0 if zero then goto BREAK GR3-M[GR1] if zero then GR0 GR1 return GR1 GR1+1 GR2 GR2-1 goto LOOP GR0 0 return

59 演習 メモリ領域をコピーするプログラムを書け GR0が指すアドレスからGR2の個数分のメモリをGR1 が指すアドレス移行にコピーする GR0 GR0+GR2の領域とGR1 GR1+GR2の領域 には重なりがないものとする アドレス 内容 アドレス 内容 例 GR0=#8000 GR1=#8100 GR2=5 でプログラム起動 C C F C F

60 演習 メモリ領域をコピーするプログラムを書け GR0が指すアドレスからGR2の個数分のメモリをGR1 が指すアドレス移行にコピーする GR0 GR0+GR2の領域とGR1 GR1+GR2の領域 には重なりがないものとする アドレス 内容 アドレス 内容 例 GR0=#8000 GR1=#8100 GR2=5 でプログラム起動 C C C C F F C F

61 演習の方針 必ずしもこの通りでなくてもよい 1.GR0の指すメモリの内容をGR3にコピー (LD) 2.GR3の内容をGR1の指すメモリにコピー (ST) 3.GR0に1を加える (ADDL) 4.GR1に1を加える (ADDL) 5.GR2から1を引く (SUBL) 6.0でなければ1.へ (JNZ) 7.RET

62 高級言語 アセンブリ言語の問題点 実現したい計算とCPUの機能が違う 複数の命令の組み合わせで1つの処理をする わかりにくい CPUによって命令が異なる ある計算機のプログラムをほかの計算機で使えない 高級言語 計算したい内容 を直接記述 自動的に機械語に変 換 人間にとって記述が容易 変換プログラムをCPUごとに書けば 高級言語のプロ グラムの移植ができる

63 初期の高級言語 FORTRAN (1955) 数値計算言語 計算を数で記述できる(FORmula TRANslator) 装置と直接対応する入出力 プリンタ カードリーダ キーボード 磁気テープなど GOTO文による実行制御 LISP (1958) 記号とその並び リスト を処理する(LISt Processor) 関数型言語 括弧 を使った記述 今なお使われる柔軟性

64 初期の高級言語 COBOL (1959) ビジネス処理用言語 (COmmon Business Oriented Language) 表の入出力と集計 現在の表計算処理に近い 読みやすさ重視 プログラムの説明文が言語仕様に含まれる 自然言語に近い命令文 COMPUTE X = Y+1.

65 いろいろなプログラム言語 ユークリッドの互除法を実装してみる GCD(m,n): If (n=0) then m Else GCD(n,m mod n) GCD(m,n): while (n 0) t n n m mod n m t End while Return m

66 Fortran (1954) 下のコードはFortran 66 (1966) M=100 N=72 IF (N) 20,30,20 CONTINUE I=N N=M-INT(REAL(M)/REAL(N))*N M=I GOTO 10 WRITE(6,40) M FORMAT(1H,I5) STOP END

67 Fortran (1954) 下のコードはFortran 95 (1995) integer function euclid_gcd(m,n) program GCD integer::m,n integer::euclid_gcd integer::t integer::m,n do while (n /= 0) m = 100 t = n n = 72 n = mod(m,n) Print *, euclid_gcd(m,n) m = t end program end do gcd = m return end function

68 LISP (1958) コードはCommon Lisp (1984) (defun euclid-gcd (m n) (if (= n 0) m (euclid-gcd n (mod m n)) ) ) (print (euclid-gcd ))

69 COBOL (1959) IDENTIFICATION DIVISION. PROGRAM-ID. EUCLID-GCD. AUTHOR. AKINORI ITO. DATE-WRITTEN. 2018/6/10. DATE-COMPILED. 2018/6/10. ENVIRONMENT DIVISION. CONFIGURATION SECTION. DATA DIVISION. WORKING-STORAGE SECTION. 01 M PICTURE N PICTURE T PICTURE X PICTURE PROCEDURE DIVISION. MOVE 100 TO M. MOVE 72 TO N. PERFORM UNTIL N = 0 MOVE N to T DIVIDE M BY N GIVING X REMAINDER N MOVE T to M END-PERFORM. DISPLAY M. STOP RUN.

70 BASIC 1964 下のコードは Chipmunk Basic (1990) 10 m=100:n=72 20 if n<>0 then goto print m:end 40 t=n: n=m mod n: m=t 50 goto 20

71 Pascal (1970) Program GCD(output); function euclid_gcd(m:integer; n:integer):integer; var t:integer; begin if n=0 then euclid_gcd := m else begin t := euclid_gcd(n, m mod n); euclid_gcd := t end end; begin writeln(euclid_gcd(100,72)); end.

72 C (1972) 下のコードは ANSI-C (1990) #include <stdio.h> int euclid_gcd(int m, int n) { if (n == 0) return m; return euclid_gcd(n, m%n); } int main() { printf("%d\n",euclid_gcd(100,72)); return 0; }

73 C++ (1983) #include <iostream> using namespace std; int euclid_gcd(int m, int n) { if (n == 0) return m; return euclid_gcd(n, m%n); } int main() { cout << euclid_gcd(100,72) << endl; return 0; }

74 Perl (1987) sub euclid_gcd { my ($m, $n) if ($n == 0) { return $m; } return euclid_gcd($n, $m%$n); } print euclid_gcd(100,72);

75 Tcl (1988) proc euclid_gcd {m n} { if {$n == 0} { return $m } else { return [euclid_gcd $n [expr $m%$n]] } } puts [euclid_gcd ]

76 Haskell (1990) euclid_gcd m 0 = m euclid_gcd m n = euclid_gcd n (m `mod` n) main = print (euclid_gcd )

77 Python (1991) def euclid_gcd(m,n): if n==0: return m return euclid_gcd(n,m%n) print(euclid_gcd(100,72))

78 Ruby (1993) def euclid_gcd(m,n) if n==0 then return m else return euclid_gcd(n,m%n) end end print euclid_gcd(100,72),"\n"

79 Lua (1993) function euclid_gcd(m,n) if n==0 then return m else return euclid_gcd(n,m%n) end end print(euclid_gcd(100,72))

80 Java (1995) public class Main { public static int euclid_gcd(int m, int n) { if (n == 0) return m; return euclid_gcd(n,m%n); } public static void main(string []args){ System.out.println(euclid_gcd(100,72)); } }

81 JavaScript (1995) function euclid_gcd(m,n) { if (n == 0) { return m; } return euclid_gcd(n,m%n); } console.log(euclid_gcd(100,72));

82 R (1996) euclid.gcd <- function(m,n) { if (n==0) { return(m) } return(euclid.gcd(n,m%%n)) } cat(euclid.gcd(100,72))

83 C# (2000) using System.IO; using System; class Program { static int Euclid_GCD(int m, int n) { if (n==0) return m; return Euclid_GCD(n,m%n); } static void Main() { Console.WriteLine(Euclid_GCD(100,72)); } }

84 Go (2009) package main import "fmt" func euclid_gcd(m int, n int) int { if (n==0) { return m } return euclid_gcd(n,m%n) } func main() { fmt.printf("%d\n",euclid_gcd(100,72)) }

85 Julia (2012) function euclid_gcd(m,n) if n==0 m else euclid_gcd(n,m%n) end end println(euclid_gcd(100,72))

86 高級言語の実現方 コンパイラ 高級言語のプログラムを読み込み それを機械語に変 換して 単独で動く機械語の実行形ファイルを生成す る 実行は高速 できたプログラムはCPU依存 デバッグが面倒 動いているプログラムとソースプログ ラムの対応がつけにくい ライブラリ ソース プログラム コンパイラ オブジェクト プログラム 機械語 リンカ 実行可能 プログラム

87 高級言語の実現方法 インタプリタ 高級言語のプログラムを読み込み その内容を直接実 行する 高級言語に対応する機械語のプログラムは生成され ない 実行は遅く プログラムのCPU依存性は少ない 実行状況が把握しやすい ソース プログラム インタプリタ 直接 実行

88 高級言語の実現方法 中間言語 バイトコード コンパイラ 仮想的なCPUの機械語にコンパイル CPUエミュレー タ 仮想マシン VM による実行 実行する計算機のCPUに依存せず インタプリタより速 い コンパイラより遅い 直接 実行 ソース プログラム コンパイラ オブジェクト プログラム 機械語 バイトコード エミュレータ 仮想マシン

89 代表的な高級言語と実現方法 コンパイラ Fortran LISP* C C++ Objective-C インタプリタ LISP* BASIC Perl Ruby Python* JavaScript PHP 中間言語 Smalltalk Java Python* C#

90 コンパイラのお仕事 ソースプログラムから最終的な機械語 コード を生 成するには段階がある ソース プログラム 構文解析 変換ルール 中間表現 最適化 コード コード コード生成 ルール 最適化 ルール

91 構文解析 単なる文字列であるソースプログラムから構造を 見つけ出す プログラム 文 a=b+1; 変数 a 構文木 = ; + 変数 定数 b 1

92 構文解析ルールの例 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + ()

93 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

94 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

95 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

96 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

97 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

98 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

99 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

100 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

101 構文解析ルールと構文木 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 + () プログラム 文 変数 a = ; + 変数 定数 b 1 構文木が1段下がる部分は構文解析ルール1つと対応する

102 演習 次のプログラムの構文木を示せ x=(y+1)-z;

103 構文木から中間表現へ さまざまな中間表現がある ここでは 四つ組 を紹介 四つ組 演算 対象１ 対象２ 格納先 元の文 四つ組 y=x+1 z=x+y+2 (+, x, 1, y) (+, x, y, T1) (+, T1, 2, z) x=a+b*c (*, b, c, T1) (+, a, T1, x) x=1 (=, 1,,x) T1は中間変数 自動的に確保される 必要に応じてT2, T3 なども 使う

104 構文木から中間表現へ 機械的な四つ組生成 変数=; の場合 文 の四つ組を生成 値が格納された中間変数をTと するとき (=, T,,変数) を生成 変数 a = ; の場合 1の四つ組を生成し 中間変 数T1に格納 2の四つ組を生成し 中間変 数T2に格納 自動生成された中間変数をTと するとき (+, T1, T2, T) を生成 変数 定数 b 1

105 構文木から中間表現へ 機械的な四つ組生成 変数 の場合 文 中間変数をTとすると (=, 変数,,T) を生成 定数 の場合 中間変数をTとすると (=, 定数,,T) を生成 変数 a = ; + 変数 定数 b 1

106 構文木から中間表現へ 生成例 文 変数 a = ; + 変数 定数 b 1

107 構文木から中間表現へ 生成例 の部分の四つ組を生成 してT1に格納 文 変数 = ; T1を変数に格納 a + 変数 定数 b 1

108 構文木から中間表現へ 生成例 の部分の四つ組を生成 してT1に格納 文 変数 = ; (=, T1,,a) a + 変数 定数 b 1

109 構文木から中間表現へ 生成例 左のの四つ組を生成してT2 に格納 変数 右のの四つ組を生成してT3 に格納 a (+, T2, T3, T1) (=, T1,,a) 文 = ; + 変数 定数 b 1

110 構文木から中間表現へ 生成例 変数の内容をT2に格納 右のの四つ組を生成してT3 変数 に格納 a (+, T2, T3, T1) (=, T1,,a) 文 = ; + 変数 定数 b 1

111 構文木から中間表現へ 生成例 (=, b,,t2) 右のの四つ組を生成してT3 変数 に格納 a (+, T2, T3, T1) (=, T1,,a) 文 = ; + 変数 定数 b 1

112 構文木から中間表現へ 生成例 (=, b,,t2) 定数をT3に格納 (+, T2, T3, T1) (=, T1,,a) 文 変数 a = ; + 変数 定数 b 1

113 構文木から中間表現へ 生成例 (=, b,,t2) (=, 1,,T3) (+, T2, T3, T1) (=, T1,,a) 文 変数 a = ; + 変数 定数 b 1

114 構文木から4つ組の生成 準備 構文木の節点 ノード Node n; 節点の子節点 n.child(k) 節点の種類 n.type == 文 文 変数 a = ; + 変数 定数 b 1

115 構文木から4つ組の生成 準備 構文木の節点 ノード Node n; 節点の子節点 n.child(k) 節点の種類 n.type == 文 文 変数 a = ; + 変数 定数 b 1

116 構文解析ルールの例 プログラム 文 プログラム プログラム 文 文 変数 = ; 変数 定数 +

117 4つ組生成手続き 文 Generate(Node n) { If (n.type == and n.child.type == ( 変数 = ; )) { tmpvar = 一時変数名 GenerateExpression(n.child(2), tmpvar) Output( =, tmpvar, null, n.child(0)) } }

118 4つ組生成手続き GenerateExpression(Node n, String tmpvar) { If (n.child(0).typeが 変数 または 定数 ) { Output( =,n.child(0).child(0), null,tmpvar) } Else if (n.child(1).type が + または - ) { t1 = 一時変数名; t2 = 一時変数名 GenerateExpression(n.child(0), t1) GenerateExpression(n.child(2), t2) Output(n.child(1).type, t1, t2, tmpvar) }

119 4つ組の生成例 Generate(n1) n1 文 n2 n3 変数 n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

120 4つ組の生成例 Generate(n1) GenerateExpression(n.child(2), tmpvar) Output( =, tmpvar, null, n.child(0)) n1 文 n2 n3 変数 n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

121 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") Output( =, tmpvar, null, n.child(0)) n1 文 n2 n3 変数 n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

122 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n2 n3 変数 n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

123 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n2 n3 変数 n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

124 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n.child(0).child(0), null,"t2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") n2 n3 変数 Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

125 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") n2 n3 変数 Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 変数 n11 定数 n13 n12 b 1

126 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") n2 n3 変数 Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) 変数 n11 定数 n13 n12 b 1

127 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output(n.child(1).type, "T2", "T3", "T1") n2 n3 変数 Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) 変数 n11 定数 n13 n12 b 1

128 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output(n.child(1).type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) 変数 n11 定数 n13 n12 b 1

129 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output(n.child(1).type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) 変数 n11 定数 n13 n12 b 1

130 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output(n.child(1).type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) (=, 1,, T3) 変数 n11 定数 n13 n12 b 1

131 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output(n.child(1).type, "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) (=, 1,, T3) 変数 n11 定数 n13 n12 b 1

132 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output("+", "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) (=, 1,, T3) (+, T2, T3, T1) 変数 n11 定数 n13 n12 b 1

133 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output("+", "T2", "T3", "T1") Output( =, "T1", null, n.child(0)) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) (=, 1,, T3) (+, T2, T3, T1) 変数 n11 定数 n13 n12 b 1

134 4つ組の生成例 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") n1 文 Output( =,n12, null,"t2") GenerateExpression(n9, "T3") Output( =,n13, null,"t3") n2 n3 変数 Output("+", "T2", "T3", "T1") Output( =, "T1", null, a) n6 a n4 = n5 ; n8 n7 + n9 n10 (=, b,, T2) (=, 1,, T3) (+, T2, T3, T1) (=, T1,,a) 変数 n11 定数 n13 n12 b 1

135 効率の良い中間表現生成 前ページの中間表現は実は1行で書ける (+, b, 1, a) 最初からこういう中間表現を生成するには 中間表現の生成ルールを細かくする 中間表現を生成した後 コードの無駄を省く処理を行う 最適化

136 細かいコード生成ルール 1 2 の場合 最後に格納する一時変数をT1とする 1の先 変数 2の 変数 先 定数 その他 (+,変数1,変数2, T1 定数 (+,定数1,変数2, T1 その他 1の四つ組を生成し てT2に格納 (+,T2,変数2,T1) (+,変数1,定数2, (+,定数1,定数2, 1の四つ組を生成し T1 T1 てT2に格納 (+,T2,定数2,T1) 1の四つ組を生成 1の四つ組を生成 1の四つ組を生成し してT2に格納 してT2に格納 てT2に格納 (+,T2,変数2,T1) (+,T2,定数2,T1) 2の四つ組を生成し てT3に格納 (+,T2,T3,T1)

137 最適化の例 中間表現があるパターンに合致する場合には置き換 えを行う 例 ある一時変数に何かを代入し そのあとその一時変数 が1回しか使われていなければ 後者の一時変数を前者 の変数または定数に置き換える (=, x,,t3) : (+, T3, T4, T2) (=, x,,t3) : (+, x, T4, T2) ある一時変数に結果を代入し それをすぐに別な変数に 代入しているとき 一時変数をその変数に置き換える (+, x, y, T1) (=, T1,, z) (+, x, y, z) (=, T1,,z)

138 最適化の例 (=, b,,t2) (=, 1,,T3) (+, T2, T3, T1) (=, T1,,a) (=, 1,,T3) (+, b, 1, T1) (=, T1,,a) (=, b,,t2) (=, 1,,T3) (+, b, T3, T1) (=, T1,,a) (+, b, 1, T1) (=, T1,,a) (=, 1,,T3) (+, b, T3, T1) (=, T1,,a) (+, b, 1, a) (=, T1,,a)

139 コード生成 四つ組の列を命令列に変換 変換ルール例 四つ組 (=, X,, Y) (+, X, Y, Z) (-, X, Y, Z) ニモニック LD G0,X ST G0,Y LD G0,X ADDA G0,Y ST G0,Z LD G0,X SUBA G0,Y ST G0,Z

140 コード生成例 高級言語 中間言語 生成コード X=Y+1; (+,Y, 1, X) Z=X+Y-2; (+, X, Y, T1) (-, T1, 2, Z) LD G0,Y ADDA G0,=1 ST G0,X LD G0, X ADDA G0, Y ST G0, T1 LD G0, T1 SUBA G0, =2 ST G0, Z

141 演習 Z=X+Y-2 からコード生成が行われるまでの処理を 記述せよ 構文木 四つ組の生成 最適化 コード生成

142 データ表現とデータ構造 コンピュータは数字しか扱えない メモリの１つの番地には一定範囲の整数しか格納でき ない 8ビットなら0 255 または それ以外のデータはどうやって表現されているの か 実数 文字と文字列 マルチメディアデータ 画像 音声

143 整数 符号なしnビット整数 0 2n-1 符号付きnビット整数 -2n-1 2n-1-1 ビット長 8 (char) 16 (short) 32 (long) 64 (long long) 符号なし 符号付き

144 実数 固定小数 有理数 浮動小数 固定小数 小数点の上と下の精度が固定 有理数 整数の比 浮動小数 小数点の位置が変動 数処理などでは使われるが あまり一般的でない のような形 多くの場合浮動小数形が使われる

145 固定小数表現 小数点の上と下の精度が固定 32ビット固定小数 FFF.FFFF16 10進では 最小精度 = 利点 計算が簡単 基本的に通常の整数演算と同じ 欠点 表せる数値の範囲が限られる 限られた範囲の数だけを高速に表現する用途に使 われる 信号処理チップなど

146 浮動小数表現 数値の有効桁数を一定にする表現方法 のような形 符号s 仮数a 基数b指数pの形で表される 通常1 a<2, b=2, s=1 or -1 s p ビット長 32 (float) 64 (double) 128 a s a 有効桁 数 p 1 1 1

147 IEEE形浮動小数 16, 32, 64, 128bit s=0 正の数 またはs=1 負の数 指数部はバイアス表現 -2n-1+2 2n-1-1を表現 整数の2n-1-1を0とする 表したい数値に2n-1-1を加える 8ビットの場合 0116が-126, 7F16が0,FE16が127 数でないもの の表現 オーバーフローを表す +Inf, -Inf (p=ff16, a=0) Not a Number (NaN) (p=ff16, a 0) ゼロ除算 負の数の平方根など

148 IEEE形浮動小数 例 -3.5をIEEE形32ビット浮動小数にする 負の数なのでs=1 3.5= より 3.5= = = = より a=1.112, p=1 pをバイアス表現にし(127を加え て2進数にすると p= sが1ビット pが8ビット aが23ビット aの先頭の1.を除く

149 演習 4.125をIEEE形32ビット浮動小数で表せ a) 符号sを決める b) 4.125を小数点付き2進数に変換する c) それを1以上2未満の数a 2pの形にする d) pを8ビットのバイアス表現に変換 e) s 1ビット p 8ビット a 23ビット を並べる a) b) aの先頭の1.は省く 23ビットに満たない部分は右に0を詰める

150 浮動小数演算 浮動小数の形に合わせるため 複雑な計算が 必要 x1=(s1,a1,p1)とx2=(s2,a2,p2)の加算 簡単のためs1=s2 p1>p2と仮定する a2 a2/2p1-p2 a a1+a2, p p1, s s1 while a>2 a a/2, p p+1 return (s,a,p)

151 浮動小数演算 x1=(s1,a1,p1)とx2=(s2,a2,p2)の乗算 s s1 s2 p p1+p2 a a1 a2 while a>2 a a/2, p p+1 return (s,a,p)

152 文字の表現 整数と文字を対応させる 符号化 文字セット 文字集合 表現すべき文字の集合 言語に依存する 多くの言語が同時に表現できる文字セットもある 文字コード 文字符号 文字セット内の文字と数字 の対応 またはその数字 1つの文字セットに対して文字コードが複数ある場合も ある

153 文字セット 表現すべき文字の集合 英語 日本語 JIS X0201: アルファベット 記号 数字 カタカナ い わゆる半角カナ JIS X0208: 漢字 記号 いわゆる全角記号 JIS X0213: 補助漢字 US-ASCII: アルファベット 数字 記号 多言語 ISO/IEC (JIS X0221): いわゆるUnicode

154 US-ASCII 英語のための代表的な文字セット 文字コード American Standard Code for Information Interchange の略 アルファベット 数字 記号を7ビットで表現する

155 US-ASCII 20 sp P 60 ` 70 p 21! A 51 Q 61 a 71 q B 52 R 62 b 72 r 23 # C 53 S 63 c 73 s 24 $ D 54 T 64 d 74 t 25 % E 55 U 65 e 75 u 26 & F 56 V 66 f 76 v 27 ' G 57 W 67 g 77 w 28 ( H 58 X 68 h 78 x 29 ) I 59 Y 69 i 79 y 2A * 3A : 4A J 5A Z 6A j 7A z 2B + 3B ; 4B K 5B [ 6B k 7B { 2C, 3C < 4C L 5C \ 6C l 7C 2D - 3D = 4D M 5D ] 6D m 7D } 2E. 3E > 4E N 5E ^ 6E n 7E ~ 2F / 3F? 4F O 5F _ 6F o 7F DEL

156 文字コード 文字符号化方 文字セット中の文字には番号が振られているが それをどうやってコンピュータ上で表現するかは別 途規定される 文字符号化方 日本語の場合 文字セット JIS X0201+X0208+X0213 文字コード ISO-2022-JP Shift-JIS EUC-JP

157 日本語の文字コード ISO-2022-JP 7ビットの符号の組み合わせで文字を表現する ASCII, X0201, X0208, X0213を切り替えるときには文 字セット切り替え用シーケンスを使う あaｱ 1b b b 28 4a b1 1b Shift-JIS 8ビットの符号の組み合わせで文字を表現する X0201は1バイト/文字 X0208は2バイト/文字 X0201 アルファベット 半角カナ とX0208の共存 あaｱ 82 a0 61 b1

158 日本語の文字コード EUC-JP UNIX用拡張文字コード(Extended Unix Code)の日本 語版 中国語 韓国語版もある 8ビットの符号の組み合わせで文字を表現する ASCII, X0201カナ, X0208, X0213が表現可能 ASCIIは1バイト X0201カナとX0208は2バイト X0213は3 バイト/文字 あaｱ a4 a2 61 8e b1

159 文字コード 文字符号化方 多言語用の文字セットと文字コード 文字セット Unicode, ISO/IEC 微妙に違う企画だが実質同じ Unicodeは業界規格 ISO/IEC 10646は国際規格 世界の多くの言語で使用される文字をカバーする 文字に対応する番号 U+nnnnn a=u+0061 ä=u+00e4 ऑ U+0911 ఊ U+0C0A あ U+3042

160 多言語の文字コード UTF-8 8ビットの符号の組み合わせで文字を表現する 1文字あたり1 4バイト 漢字は常に3バイト US-ASCIIと互換性がある あaｱ e ef bd b1 UTF-16 16ビットの符号の組み合わせで文字を表現する 1文字あたり2 4バイト 多くの文字は2バイト 上位バイトが先に来る(Big Endian)場合と下位バイトが 先に来る(Little Endian)場合がある あaｱ ff 71 (UTF-16BE)

161 画像の符号化 画像を数字に 画像を細かい点(pixel)の集まりで表現する

162 ピクセル

163 色の表現 加法混色による色の表現 赤(R)緑(G)青(B)の重ね合わせで 色を表現する それぞれの色の明るさの段階 1ビット 2段階(ON/OFF) 8色 8ビット=256段階 色 RGBそれぞれを8ビット =16進数2桁で表現 (R,G,B)=(6B,23,94) #6b2394

164 画像符号化 画像は情報量が多い サイズで1ピクセル3バイト 1画像あたり2.3Mバイト 画像の圧縮 画像のサイズをできるだけ縮める 無圧縮 可逆圧縮:圧縮前の画像に戻せる BMPなど GIF, PNGなど 圧縮率は低い 不可逆圧縮 圧縮前の画像に戻らない JPEG, JPEG2000など 圧縮率は高い

165 BMP 901kbyte JPEG 102kbyte JPEG 23kbyte JPEG 11kbyte

166 音声の符号化 音は空気の波 マイクロフォンで電圧変化に変換される 時間的に連続 取る値も連続 時間と電圧を離散化 整数列に変換 V t

167 標本化と量子化 時間的に離散化 標本化 電圧を離散化 量子化

168 標本化と量子化 時間的に離散化 標本化 電圧を離散化 量子化

169 標本化と量子化 標本化を細かくするほど 高周波数成分 まで再現 できる 量子化を細かくするほど 量子化雑音 を減らすこ とができる

170 アルゴリズム 計算モデル 計算量 コンピュータに計算させるなら 速いほうがいい どうやって計算させるのか アルゴリズム 算法 解を求めるための計算手順 それはどのくらい早いのか 計算量 実行するコンピュータの違いを吸収 計算モデル 絶対的な速さは求めにくい 漸近的計算量

171 アルゴリズム (algorithm) 問題と入力が与えられた時に 解を求める方法 同じ問題に対して複数のアルゴリズムがありうる ユークリッドの互除法 ２数から最大公約数を求める ２次方程の解の公 係数から解を求める 数学の問題に複数の解法があるのと同じ アルゴリズムがない問題もある 解が永遠に求まらない可能性がある問題など

172 アルゴリズムの例 ユークリッドの互除法 1. ２つの数をm,nとし m nとする 2.n=0ならば mが答えとなり 終了 3.(m, n) (n, m mod n) mod は剰余 4.2に戻る // C言語による記述例 // m>=0, n>=0, m >= nでなければならない int Euclid(int m, int n) { int new_m; while (n > 0) { new_m = n; n = m % n; m = new_m; } return m; }

173 計算の 大変さ を測る どうやって測るのか 計算にかかる時間 ベンチマーク 直接的だが問題が多い コンピュータによって変化する CPU クロック メモリ量など 入力によって変化する 入力が多ければ一般に時間がかかる ある量の入力サイズで突然遅くなることがある コンピュータによって処理できるサイズに上限がある 以上から 絶対的な指標 としては不適当

174 漸近的計算量と計算モデル 実際のコンピュータではなく 計算モデル を想定 計算時間ではなく ステップ数 を対象とする 理想化されたコンピュータ メモリの制約がない 等 ステップ数はコンピュータの種類への依存が少ない ステップ数そのものではなく 入力の増加に伴うステップ数の増え方 を考える 漸近的計算量 計算時間が問題なのはデータが多い時なので データ が巨大になったときどれだけ遅いかを重視

175 計算モデル 理想化された計算機械 さまざまなものがあるが 最も性能が高いものは どれ も計算能力は同じであることが証明されている チューリングマシン (TM) ランダムアクセスマシン (RAM) 帰納的関数

176 チューリングマシン Alan Turingによる最初の計算モデル 状態 ヘッド A = 1 0 ; B = A + テープ 2 ; 現在の 状態 と ヘッドが 読んだ文字に応じて 次の どれかの動作をする ヘッドの位置のテープに 指定された文字を書く ヘッドを右に１つ動かす ヘッドを左に１つ動かす 動作したら次の状態に遷移 する F 無限に長い

177 ランダムアクセスマシン 通常のコンピュータの抽象化 メモリ レジスタ があり アドレスの番号で指定できる メモリには任意の自然数が格納できる メモリは必要に応じて充分大きい メモリはそのアドレスの番号によらず一定時間で読み 書きできる ランダムアクセス メモリの内容に対して基本的な演算をして またメモリ に格納することができる メモリの内容をアドレスだと解釈して それが示すメモリ の内容が読み書きできる 間接アドレッシング

178 ステップ数 計算をするときに行う基本的な演算の回数 なにが 基本的な演算か は場合によって異なる 比較演算 値のコピー 加減算 乗除算

179 漸近的計算量 ある入力に対するステップ数 ではなく 入力の 変化に対するステップ数の変化 を見る 入力サイズが2倍になった時に ステップ数同じ ステップ数が定数回増える ステップ数が2倍 ステップ数が4倍 ステップ数が8倍 ステップ数が2乗 O(1) O(log n) O(n) O(n2) O(n3 ) O(2 n ) オーダー記号

180 オーダー記号 入力のサイズに対してステップ数がどのように大き くなるかを示す記号 O, Ω, Θ などの種類がある 数学的定義 入力のサイズをn ステップ数をT(n)とする 関数 f (n)について 定数Nとαが存在して n N T (n) α f (n) アルゴリズムの 漸近的 計算量はO( f (n))

181 オーダー記号 O( f (n)) α f (n) T (n) こちらでは T (n) α f (n) N n 問題のサイズが十分に大きいときのステップ数の上限

182 その他のオーダー記号 Ω( f (n)) T (n) Θ( f (n)) α 2 f (n) T (n) α 1 f (n) α f (n) N T (n) α f (n) 問題のサイズが十分 に大きいときのステッ プ数の下限 n n N α 1 f (n) T (n) α 2 f (n) 問題のサイズが十分 に大きいときのステッ プ数の上下限

183 オーダーの例 T (n)=3 n T (n)=n + 2 n+ 100 O (n) (α=4, N =10) 3 O (n ) (α=2, N =5) T (n)の中で最も早く発散する項を f (n)とすると O( f (n))

184 多項時間と指数時間 多項時間アルゴリズムの計算量 O (n k ) n O (k ) 指数時間アルゴリズムの計算量 指数時間アルゴリズムの計算時間は多項時間 アルゴリズムよりも遥かに早く増加する 大きいnについてはほとんど実用にならない

185 最悪時計算量と平均時計算量 入力によって計算量が異なる場合がある 例 データを探索する場合 最悪時計算量 たまたま最初に捜したところに目的のデータがあれば すぐ に終わる 目的のデータが最後まで見つからなければ時間がかかる もっとも都合が悪い入力に対してかかる計算量 平均時計算量 入力に対して仮定を置いたとき たとえば探索される要 素がある位置にある確率が一様 の計算量の期待値

186 探索問題 同じ問題に対して異なる計算量のアルゴリズムが ある典型的な例 探索 データの中に特定の要素が含まれるか調べる ソート データを順番に並べ替える 最短経路探索 ここでは簡単な探索問題を扱う データx1, x2,..., xnの中に y があるかどうか探す 線形探索 簡単な方法 二分探索

187 線形探索 最も簡単な探索法 最初から順番に捜す 見つかったら終わり i 線形探索 iを1からnまで変化させながら もし x[i]=yならば 見つかった を返し 終了 を繰り返す 見つからなかった を返す

188 線形探索の計算量 最悪時計算量 O (n) T (n)=n 平均時計算量 どの位置で見つかる確率も同じだと仮定 i番目に見つかる確率 P (i)=1/n n n n(n+ 1) n+ 1 1 T (n)= P (i)i= i= = n i=1 2n 2 i=1 O (n)

189 もっと高速な探索 もしデータが順番に並んでいたとしたら 小さいデータ 大きいデータ 昇順 (ascending) 大きいデータ 小さいデータ 降順 (descending) 最大値と最小値はすぐわかる 探索値が小さければ前の方を 大きければ後ろのほう を探せばよい 高速な探索 探索値がデータの前半と後半のどちらにあるのかを調 べる

190 二分探索 入力x1 x2... xnと仮定する 真ん中あたりの値を調べる 1+ n h= 2 x h= y 探索値が見つかった x h< y 探索値は中央より後にある x h> y 探索値は中央より前にある 次の探索範囲が半分になる

191 二分探索 探索値 右にある 左にある 当たり

192 二分探索 二分探索 b 1, e n 繰り返し h (b+e)/2 もし x[h]=y ならば 見つかった を返し 終了 そうでなく b e ならば 見つからなかった を返し 終了 そうでなく x[h]<y ならば b h+1 そうでなければ e h-1 を実行する

193 二分探索の計算量 入力サイズが２倍 比較が定数回増える ループが１回多い 入力サイズ 2N 比較回数 KN Kは定数 入力サイズ n 比較回数 K log2 n = T (n) 計算量のオーダーはO(log n)