トランプ大統領の「業績」は何だったのか?
「経済を成長させた?」 - 歴代の大統領と大差なし。
「中国に厳しい?」 - ほとんどは口だけ。
その他、日本ではほとんど報道されない「業績」:
第4Qの授業の改善のため、Google Forms による アンケートの回答をお願いします (リンクは Discord 上に投稿)。 氏名は書かなくてよいので、好き勝手に書いてください。 授業をもっと面白くするためのアイデア歓迎。
この課題を実現するには、おもに2つの方法がある:
r
を「集合」とみなし、余りをひとつずつ入れていく。
この場合、必ず 2重の whileループ (または while + forループ) が必要になる。
r
を「頻度表」とみなし、「余りが出た番目」の要素に 1 を足す。
この場合、whileループは 1つでよい。
a = 1 x = int(input("x?")) a = a % x check = False # 循環の有無を表すためのブール変数。初めはFalseと定義する。 count = 0 # whileループが何回目のループかをカウントするための変数。 # 20個分の余りを記録できるようにする。 r = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 余りがゼロになるまで続ける。循環になれば、breakする。 while a != 0: a = a * 10 d = a // x # 商を求める。 a = a % x # 余りを求める。 print(f"digit={d}, remainder={a}") r[count] = a # 余りをリストに格納する。 count += 1 # カウントを1増やす # リストの0番目から現在のあまりの一つ前の番目(count-1番目)の余りまでを、 # 現在の余りと等しいかチェックする。 for i in range (count - 1): # count-1以降は初期値の0であり、調べるのは余分なので除いた。計算量を少し減らせた。 if a == r[i]: # 等しければ、checkをTrueにする。(循環) check = True if check: # forループで探索後、checkがTrue(循環)ならば、whileループを終了する。 break if check: # whileループが終了後、checkがTrueならば、「junkan」と表示する。 print("junkan")
# 割られる数 a の初期値は 1 a = 1 # x を入力から受け取る x = int(input("x?")) # 小数部分を表示するので a % x で余りをとり a < x とする # このプログラムでは 2 <= x <= 20, a = 1 が保証されていて a < x を常に満たすので必要ない a %= x # 20個分の余りを記録できるようにする # 余りは必ず 0 以上 x 以下になるので listの大きさは x で十分 # 今回は x の最大値が 20 であるため 20 とする r = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 余りが 0 になるか、循環するまで続ける while a != 0: # a を10倍する # これは筆算でどんどん右にずれていくのと同じ行為 a *= 10 # 商をを求める # 筆算の上に書かれる数字と対応している d = a // x # 余りを求める # 筆算の下に書かれる数字と対応している a %= x # 商と余りを表示する print(f"digit={d}, remainder={a}") # 余りを記録する r[a] += 1 # 2回以上同じ余りが出た場合、循環している if r[a] > 1: # 循環していることを出力する print("junkan") # while文を終わらせるbreak処理 break
これまで Python を使ったプログラミングの練習をしてきたが、 本日はもっと初歩的なコンピュータの原理を説明する。
本日は、コンピュータのもっとも原始的なプログラミング言語である 「機械語 (machine language)」でのプログラムを体験する。 機械語は Python のような現代的なプログラミング言語とは違い、 文字列で書かれていない。機械語プログラムは、基本的には記憶装置上の 数値 (命令語) の列によって表現される。これを演算装置が 1つずつ読み込んで動作する。
ここでは「MOS 6502」という、 1975年に開発された原始的な演算装置 (のエミュレータ) を使ってみる。 これはファミコンや Apple II などの初期のパソコンに使われていた。 価格は $100 程度で、当時としては破格に安かった。
MOS 6502 は、以下のような機能をもっている:
実際にはもうひとつ特別な変数 PC (プログラム・カウンタ) がある。 これは、次に記憶装置上のどの命令語を読むかの位置を示しており、 演算装置は命令を読んでは実行を永久にくりかえす。 演算装置の動作を Python 風に書くと、次のようになる: (実際にはこれはプログラムではなく電子回路そのものによって実現されている)
# メモリの内容 (65536要素のリスト) M = [0, 0, 0, 0, 0, ... ] # PCは現在実行する命令の位置。 PC = 0 # 以下を永久にくり返す。 while True: # 現在の命令を調べる。 c = M[PC] if c == 1: A = A + 1 # 変数 A に1を足す。 elif c == 2: A = A - 1 # 変数 A から1を引く。 elif ... # 次の命令を実行。 PC = PC + 1
演算装置の中では、変数のことをレジスタ (register) とよぶ。 MOS 6502 には以下のようなレジスタが装備されている。
名前 | 大きさ | 機能 |
---|---|---|
PC | 16ビット | これから実行する命令のメモリ上の位置。 |
Aレジスタ | 8ビット | 計算のために使う。 |
Xレジスタ | 8ビット | メモリ上の位置を指すために使う。(後述) |
Yレジスタ | 8ビット | (今回は使わない) |
Zフラグ | 1ビット | 計算結果がゼロになったときに 1 になる。(後述) |
Cフラグ | 1ビット | 計算結果が桁あふれしたときに 1 になる。(後述) |
ブラウザで http://visual6502.org/ を開き、"Visual Sim / 6502" の "Advanced" リンクをクリックする。 これは本物の 6502 の電子回路の動きをブラウザ上で仮想的に再現するエミュレータである。
演算装置の世界では、なぜか数値は16進数で表されることが多い。 16進数 (Hexadecimal, 通称Hex) とは、 1ケタの文字で 16種類の数を表わせるようにしたものである。 通常の10進数の 0〜9 までの数字に加え、 アルファベットの a〜f の文字 (大文字・小文字はどちらでもよい) を「数字」として利用している。 16進数を使うと、2進数の4ケタの数値を1文字で表すことができるため、 0 と 1 の羅列を表す短縮記法としてよく使われている。
10進数 | 2進数 | 16進数 |
---|---|---|
0 | 0000 | 0 |
1 | 0001 | 1 |
2 | 0010 | 2 |
3 | 0011 | 3 |
4 | 0100 | 4 |
5 | 0101 | 5 |
6 | 0110 | 6 |
7 | 0111 | 7 |
8 | 1000 | 8 |
9 | 1001 | 9 |
10 | 1010 | a / A |
11 | 1011 | b / B |
12 | 1100 | c / C |
13 | 1101 | d / D |
14 | 1110 | e / E |
15 | 1111 | f / F |
では最初のプログラムとして、メモリ上のある位置 (演算装置の世界では、番地 (address) と呼ばれる) に ある8ビットの数値を格納する処理をやってみる。 これは、以下のような数値の羅列で表現される。
0000: A9 01 ; LDA #$01 - Aレジスタに $01 を格納。 0002: 95 10 ; STA $10 - Aレジスタの値をメモリの 16 番地に格納。 0004: 00 ; BRK - CPUの停止。
これは Python でいえば、以下のような処理に等しい:
A = 1 # LDA #$01 M[16] = A # STA $10
プログラムは、メモリ上の 16進数が書かれている部分を
ダブルクリックして直接入力する。
ここでは LDA
命令、STA
命令、BRK
命令を使っている。
命令語 (16進) | バイト数 | 表記 | 機能 |
---|---|---|---|
A9 XX |
2 (命令 1 + 値 1) | LDA #$XX |
Aレジスタに値 16進数 XX を記録する。 |
95 XX |
2 (命令 1 + アドレス 1) | STA $XX |
Aレジスタの値をメモリの XX 番地に記録する。 |
00 |
1 | BRK |
制御装置を停止する。 |
(もっと詳しい命令語と数値の対応表は以下を参照のこと)
次に足し算とおこなう ADC
命令 とジャンプ命令 JMP
を使ってみる。
「ジャンプ命令」とは繰り返し処理をおこなうための命令で、
これがくると CPU は指定された番地から実行をおこなう。
つまり、以前実行した命令にまた戻ることができる。
なお、ジャンプ命令がやっていることは、
実際には PC レジスタの値を書き換えることだけである。
0000: A9 01 0002: 95 10 0004: 69 02 ; ADC #$02 - Aレジスタに $02 を足す。 0006: 4C 02 00 ; JMP $0002 - $0002番地の命令にジャンプする。
これは、Python でいえば、以下のような処理に(ほぼ)等しい:
A = 1 # LDA #$01 while True: M[16] = A # STA $10 A = A + 2 # ADC #$02
命令語 (16進) | バイト数 | 表記 | 機能 |
---|---|---|---|
69 XX |
2 (命令 1 + 値 1) | ADC #$XX |
Aレジスタの値に 16進数で XX を加える。 |
4C PP QQ |
3 (命令 1 + アドレス 2) | JMP $QQPP |
16進数で QQPP 番地から実行を開始する。
番地の上2桁、下2桁が逆になっていることに注意。 (リトルエンディアン) |
上のプログラム2種類をエミュレータ上で実際に実行せよ。 Aレジスタの値が FF を超えると何が起こるか?
いちいち命令語の数値を調べるのは面倒くさいので、 これからはアセンブリ言語 (assembly language) というプログラムを使う。 これは、文字で命令語を入力すると自動的に数値に変換するものである。 ここでは別のサイト http://6502asm.com を使う。
LDA #$01 STA $0200
ここでは、$XXXX
というのは 16進数の数値であることを表す。
さらに、以下のような表記の決まりがある:
#$01
… $01
という値そのもの。
$0200
… $0200
という「メモリ上の番地に入っている」値。
6502asm.com のエミュレータでは、
メモリ上の番地 $0200
〜 $05ff
の範囲が
画面の各ピクセルに対応している。
ここに値を格納すると、それが実際に画面に表示される。
つまり、ここではメモリへの書き込みが出力装置も兼ねているのである。
アセンブラを使うと、プログラム中の場所にラベルをつけることができ、 実際の番地を書くかわりに使うことができる。
LDA #$01 loop: ; ラベル "loop" をここに設定。 STA $0200 ADC #$02 JMP loop ; "loop" の番地にジャンプする。
注意: ラベル自体はただプログラム中の位置を表すもので、実際の命令ではない。
差分アドレッシングという機能を使うと、 メモリ上の可変の位置のデータを読み書きできる。 これは、画面上のある連続した領域を埋めるのに使える。
LDA #$01 LDX #$00 ; Xレジスタに $00 を格納。 loop: STA $0200,X ; Aレジスタの値を ($0200+X) の位置に格納。 ADC #$02 INX ; Xレジスタの値を 1だけ増やす。 JMP loop
以下、Python 相当の処理:
A = 1 # LDA #$01 X = 0 # LDX #$00 while True: M[512+X] = A # STA $0200,X A = A + 2 # ADC #$02 X = X + 1 # INX
命令語 | バイト数 | 機能 |
---|---|---|
LDX #$XX |
2 (命令 1 + 値 1) | Xレジスタに値 $XX を記録する。 |
STA $ZZZZ,X |
3 (命令 1 + アドレス 2) | Aレジスタの値を ($ZZZZ+X) の位置に格納する。 (差分アドレッシング) |
INX |
1 | Xレジスタの値を 1だけ増やす。 |
上のプログラムをエミュレータ上で実際に実行せよ。 なぜ画面の一部しか更新されないのか?
条件分岐とは、「場合によって、違ったことをする」 処理のことである。画面をつねに同じ色で塗るのではなくて、 「特定の場所に到達したときのみ、色を変える」にはどうするか?
LDX #$00 loop: CPX #$10 ; Xレジスタの値を $10 と比較。 BEQ on ; 等しければ、on に分岐する。 JMP off ; 等しくなければ、off に分岐する。 on: LDA #$01 JMP put off: LDA #$02 put: STA $0200,X INX JMP loop
Python 相当の処理:
X = 0 # LDX #$00 while True: if X == 16: # CPX #$10, BEQ on A = 1 # LDA #$01 else: A = 2 # LDA #$01 M[512+X] = A # STA $0200,X X = X + 1 # INX
命令語 | バイト数 | 機能 |
---|---|---|
CPX #$XX |
2 (命令 1 + 値 1) | Xレジスタの値を $XX と比較する。
等しければ Zフラグを 1 にする。 |
BEQ ラベル |
2 (命令 1 + アドレス 1) | Zフラグが 1 ならば (直前の値が等しければ)、 指定されたラベルに分岐する。 |
6502 では、比較・演算命令
(ADC
, CPX
, INX
など) の結果によって
内部のフラグ (flag) が変化する。フラグとは 1ビットの特殊な変数で、
ふつう直前の計算によって生じた変化を記憶している。
上のBEQ
命令は実際には何も計算してないように見えるが、
内部的には 2つの数の引き算をおこなっている。これによって、
2つの数が等しいときに結果が 0 になり、結果として Zフラグが 1 になる。
上の条件分岐は、以下のようにも書ける:
LDX #$00
loop:
LDA #$02
CPX #$10
BNE put ; 等しくなければ、put に分岐する。
LDA #$01
put:
STA $0200,X
INX
JMP loop
命令語 | バイト数 | 機能 |
---|---|---|
BNE ラベル |
2 (命令 1 + アドレス 1) | Zフラグが 0 ならば (直前の値が等しくなければ)、 指定されたラベルに分岐する。 |
MOS 6502 ではほとんどの計算は 8ビットでしかできないが、
工夫することで 16ビットの計算が可能である。じつは "ADC
" 命令は
与えられた数に加えて C フラグの値も加える ようにできており、
これを使って 8ビットの数を 2回に分けて計算する。
CLC ; Cフラグをクリアする。 LDA $30 ; メモリ$30番地の値を Aレジスタに読み込む。 ADC #$01 ; A = A + 1 + 0 STA $30 ; Aレジスタの値をメモリ $30番地に書き込む。 LDA $31 ; メモリ$31番地の値を Aレジスタに読み込む。 ADC #$00 ; A = A + 0 + C STA $31 ; Aレジスタの値をメモリ $31番地に書き込む。
命令語 | バイト数 | 機能 | CLC |
1 | Cフラグの値を 0 にする。 |
---|
以上のテクニックと以下の「間接差分アドレッシング」を組み合わせると、 256バイト (=8ビット) 以上のメモリ領域にアクセスできる。 つまり、画面のより広い領域に描画できるようになる。
命令語 | バイト数 | 機能 |
---|---|---|
STA ($ZZ,X) |
2 (命令 1 + アドレス 1) | 間接差分アドレッシング。
|
LDA #$00 STA $30 LDA #$02 STA $31 loop: LDX #$00 LDA #$01 STA ($30,X) ; A をメモリ ($30+X) 番地に書かれている番地に書き込む。??? ; 16ビットの加算をおこなう ...JMP loop
上のプログラムを完成させ、 画面全体を塗りつぶすようにせよ。
パソコンで、エディタを起動して A のキーを押し、
画面上に日本語の「あ
」という文字が表示されたとする。
このとき、コンピュータの内部では以下のことが起きている。
これを Python 風にかくと、以下のようになる:
(実際は Python ではなく、機械語で書かれている)
keyCode = 65
あ
」に変換する。
# 永久に動きつづけている。 while True: if keyCode == 65: # Aが押された場合。 if inputMode == 日本語: print("あ") elif inputMode == 英語: print("A") elif keyCode == 73: # Iが押された場合。 if inputMode == 日本語: print("い") elif inputMode == 英語: print("I") ...
print
関数の中はどうなっているか?
実際には、画面に文字を表示するには文字コードだけでは不完全である。
x = 20 # カーソルのX座標 y = 30 # カーソルのY座標 font = "Gothic" # 表示に使うフォント名 size = 16 # 文字の大きさ color = "Black" # 文字の色 background = "White" # 背景の色 letter = "あ" # 表示する文字 showOneLetter(x, y, font, size, color, background, letter)
showOneLetter
の中はどうなっているか?
画面に表示される「あ」の文字は、実際にはいくつものピクセルで構成されている。
ここでは「あ」の輪郭にしたがって、ひとつひとつのピクセルの濃さを計算する。
def showOneLetter(x, y, ...): # ピクセルの色 (R,G,B) を計算する。 if color == "White": R = 255 G = 255 B = 255 ... # 文字「あ」の形状を多角形で近似する。 if letter == "あ": polygon = [1, 1, 14, 3, 7, 4, ... ] # 16×16ピクセルの文字の場合: for i in range(16): for j in range(16): # 輪郭に従って、位置(i,j) のピクセルの濃さを計算する。 d = calculateDensity(polygon, i, j) # ピクセルを表示する。 drawPixel(x+i, y+j, R*d, G*d, B*d)
def drawPixel(x, y, R, G, B): x = x + 200 # ウィンドウのX座標を足す y = y + 300 # ウィンドウのY座標を足す if 10 <= x and x <= 20 and 100 <= y and 200 <= y: # 他のウィンドウに隠れていたら何もしない。 doNothing() else: # 他のウィンドウに隠れていなければ表示する。 reallyDrawPixel(x, y, R, G, B)
def reallyReallyDrawPixel(x, y, R, G, B): if x < 1000: # 画面1用に色を補正する。 if R == 255 and G == 255 and B == 255: R = 244 G = 250 B = 230 # 画面1に表示。 reallyReallyDrawPixelScreen1(x, y, R, G, B) else: # 画面2に表示。 reallyReallyDrawPixelScreen2(x, y, R, G, B)
def reallyReallyDrawPixelScreen1(x, y, R, G, B) width = 1920 # 画面1の幅 height = 1080 # 画面1の高さ # 現在のピクセルに相当するリストの位置を計算する。 i = (y*width + x) # そのピクセルの色を変える。 pixel_R[i] = R pixel_G[i] = G pixel_B[i] = B
この処理はただエディタで「1文字を入力するだけ」の処理である。 実際には、絵を動かしたり音を慣らしたり、それらど同時に実行したりといった 処理がコンピュータ上では起きている。
現在のコンピュータでは、一般人が上で示したような プログラムを書く必要はない。文字表示などの非常に基本的な部分は、 「オペレーティングシステム (OS, 基本ソフトウェア)」として 最初からPCと一緒に提供されているためである。 ほとんどの人は、このオペレーティングシステムを使った アプリケーション (応用ソフトウェア) を書く。 しかし実際にはこれはコンピュータで動いているソフトウェア全体の ごく一部にすぎない。
また、OS は多くの仮想化処理を実現している。 画面や記憶装置は、コンピュータにとっては (長さの決まった) 0 と 1 のリストであるので、実際には以下のものは OS が あるかのように見せかけている「幻影」である。 このような OS の仮想化機能により、 現在のパソコンは実際の仕組みを知らなくても 「なんとなく」使えるものになっている。 しかし実際の中身は非常に複雑なのである。
現代の 最新鋭の演算装置でも、 基本的にやっていることは変わらない。ただ量が増えているだけである。
1975年 | 2018年 | |
---|---|---|
レジスタの数 | 4 | 40 |
計算できるビット数 | 8 | 64 |
メモリの容量 | 65,536 | 34,359,738,368 |
1秒間の命令実行数 | 1,000,000 | 1,000,000,000 |
プログラムの大きさ | 10,000 | 10,000,000,000 |
結局のところ、コンピュータはみな非常に単純な原理で動いている。 これを組み合わせて複雑な処理をしているように見せかけているのが、 現代のコンピュータシステムなのである。
$ python drawline.py [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0, 1, 0, 0, 0] [0, 0, 1, 0, 0, 0, 1, 0, 0, 0] [0, 0, 1, 0, 0, 0, 1, 0, 0, 0] [0, 0, 1, 1, 1, 1, 1, 1, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
以下の未完成のプログラム drawline.py を改良して、 これが正しく動作するようにせよ。 完成版のプログラムを T2SCHOLA から提出せよ。
# 画面の大きさ (w列 × h行) w = 10 h = 10 # 画面のピクセル (screen) を 0 で埋める。 screen = [] for i in range(h): row = [] for j in range(w): row = row + [0] screen = screen + [row] # drawline: (x0,y0)-(x1,y1) に線分を描く関数。 # 画面上の該当部分に 1 で埋める。 # 注意: この関数は不完全である。 def drawline(x0, y0, x1, y1): #print(f"drawline({x0}, {y0}, {x1}, {y1})") x = x0 while x <= x1: # 現在の x 座標に対応する y を計算する。 y = y0 + (x-x0)*(y1-y0)//(x1-x0) # y行 x列目を 1 にする。 screen[y][x] = 1 #print(f"at {x},{y}") x = x + 1 return # 画面上に三角形を描く。 drawline(2,8, 5,1) drawline(5,1, 7,8) drawline(2,8, 7,8) # 画面の内容を表示する。 for i in range(h): print(screen[i])
これは内部で drawline()
関数を定義している。
この関数を 3回呼び出し、(2,8)-(5,1)、(5,1)-(7,8) および (2,8)-(7,8)
それぞれの線分を描画しているのだが、現行のバージョンでは
この drawline()
関数が不完全であるため、
以下のような結果になってしまう:
$ python drawline.py (未完成バージョン)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
現行の drawline()
では、(高校のときに習った)
直線の方程式を使って
「x座標をひとつずつ進めながら、対応する y 座標に点を打っていく (1 を埋めていく)」
方法を使っている。ところがこれは横長の線 (|y座標の差| < |x座標の差|) に対しては
うまくいくが、縦長の線に対しては途切れた点になってしまう。
なぜなら、縦長の線の場合、x が 1変化するのに対して、
y は 1 より大きく変化してしまうからである。
これに対処するためには、おもに2つの方法が考えられる: