mrasu’s blog

読んだ物の内容など

算機プログラムの構造と解釈(4章)

「計算機プログラムの構造と解釈(SICP)」の4章です

解釈法を定義し、文字列を読み込み、実行できるようにします。
コンパイラDSLなどで行われる方法で、Lispで実行できるようにします。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


4章 超言語的抽象[metalinguistic abstractionn]

4.1 超循環評価器

Lispを使った評価器で、Lispプログラムを評価する。
このように、評価対象の言語が評価する言語と同じである評価器は超循環[metacircular]であるという

4.1 評価器の中核

評価は2つの手続きの相互作用として記述できる

  1. eval
    式と環境を引数として、式を評価する
    式には種類がある
    1. 自己評価式
      数値のような自己評価式にはそれ自身を返す。変数の値は環境から得る
    2. クォート式
      クォートされていた式を返す
    3. 代入(定義)
      新しい値を取得するために再帰的にevalを呼び出し、その値で環境の変数の束縛を変更・作成する
    4. if
      述語の真偽により、帰結式・代替式を評価する
    5. lambda
      式で指定されたパラメタと本体を環境に合成した手続きへ変換する
    6. begin
      要素式を順に評価する
    7. cond
      ifの入れ子に変換し、評価する
    8. 組合せ
      演算子部分と非演算子部分を再帰的に評価したのち、評価する
  2. apply
    「手続き」と「引数のリスト」を引数にとり評価する
    基本演算と合成手続きの評価を行う

4.1.2 式の表現

評価器の言語構文は評価器の要素の取り出し方によってきまる(前置、中置など)

4.1.3 評価器のデータ構造

データ構造を定義する

4.1.4 評価器をプログラムとして走らせる

初期状態の環境とその環境への値追加を可能にすることにより評価できるようにする
評価器を走らせるため、読込→評価→出力をループさせる

4.1.5 プログラムとしてのデータ

Lispプログラムを入力としてLisp式を評価できるので作成した評価器は、万能機械といえる
評価器に対して、プログラム言語を入力すると、それをデータとして解釈する

4.1.6 内部定義

(define (f x)  
    (define (even? x)  
        (if (= x 0)  
            #t  
            (odd? (- x 1))  
        )  
    )  
    (define (odd? x)  
        (if (= x 0)  
            #f  
            (even? (- x 1))  
        )  
    )  
    (even? 3)  
)  

という定義をすると、even?とodd?は同じスコープにあり、実行時には両関数が定義されているので、動く。
しかし、実行時に両関数が定義されているのは偶然で、even?とodd?の間にeven?を実行されたらだめ。
これを回避するなら、lambda

4.1.7 構文解析と実行を分離する

同じ関数に対して呼ばれるたびに評価するのは無駄なので、キャッシュする

4.2 Schemeの変更 - 遅延評価

4.2.1 世紀順序と作用的順序

言語について

  • 世紀順序(遅延評価): 引数の値が必要になったときに評価する
  • 作用的順序: 関数の引数を内部実行前に評価する

手続きについて、同様の意味でノンストリクト(non-strict)、ストリクト(strict)という言葉をつかう。

4.2.2 遅延評価の解釈系

遅延評価用に今までの各種関数を変更する必要がある

4.2.3 遅延評価リストとしてのストリーム

cons をノンストリクトにすることにより、ストリームとリストを同一にする

4.3 Schemeの変形 - 非決定性計算

4.3.1 ambと探索

amb(候補の中から1つを適当に返す式)を導入する

2つのリストの要素を組み合わせて、要素の和が素数になる組み合わせを取ろうと思うと、

(prime-sum-pair '(1 2 3) '(20 35 110))  
(define (prime-sum-pair list1 list2)  
    (let ((a (an-element-of list1))  
            (b (an-element-of list2))  
        )  
        (require (prime? (+ a b)))  
        (list a b)  
    )  
)  
(define (require p)  
    (if (not p) (amb))  
)  
(define (an-element-of items)  
    (require (not (null? items)))  
    (amb (car items) (an-element-of (cdr items)))  
)  

無限の範囲から選択するには、

(define (an-integer-starting-from n)  
    (amb n (an-integer-starting-from (+ n 1)))  
)  

4.2.3 非決定性プログラムの例

ambの使用例

Baker, Cooper, Fletcher, Miller, Smithが1~5階に住んでいて、
Bakerは最上階ではない。Cooperは最下階ではない。Fletcherは最上階でも最下階でもない。MillerはCooperより上の階。SmithはFletcherの隣の階ではないFletcherはCooperは隣の階ではない。
という条件が与えられたとき、各人の階を求めることができる

4.4 論理型プログラミング

(define (append x y)  
    (if (null? x)  
        y  
        (cons (car x) (append (cdr x) y))  
    )  
)  

は、
(a b)と(c d)をappendすることができるが、逆はできない。
ので、逆もできるように「定義を定義して、解決を自動化する」

4.1 推論的情報検索

データベースにデータを入れて、取り出すことを考える。

(job (Bitdiddle Ben) (computer wizard))  
(job (Hacker Alyssa P) (computer programmer))  
(job (Cratchet Robert) (accounting scrivener))  

と、登録すると

(job ?x (computer . ?type))  

と検索することで

(job (Bitdiddle Ben) (computer wizard))  
(job (Hacker Alyssa P) (computer programmer))  

が得られる。
さらに、

  1. and/or/notによる質問の合成
  2. 変数化

ができるようにする

質問を抽象化したものを規則(rule)とすると、再帰が使える
すると、論理的推論が可能になる

例えば、

(rule (append-to-form () ?y ?y))  
(rule (append-to-form (?u . ? v) ?y (?u . ?z))  
    (append-to-form ?v ?y ?z)  
)  

という規則から

(append-to-form (a b) (c d) ?z)  

を満たすものは、(a b c d)であり、

(append-to-form (a b) ?y (a b c d))  

を満たす?yは (c d)であり、

(append-to-form ?x ?y (a b c d))  

を満たす?x/?y の組み合わせは全て導出される

4.4.2 質問システムはどう働くか

質問システムは、2つの演算からなる

  1. パターンマッチング
    (a b c) (x? y? z?) はそれぞれa,b,cでマッチし、(x? y?)に失敗する
  2. ユニフィケーション
    ( (a ?y c) (a b ?z))と(x? x?)では連立方程式のようにして、?x=(a b c)を導く

4.4.3 論理型プログラミングは数学的理論か

同一視できそうだが、論理型プログラミングは手続き的に解釈する制御構造があるがために、同一視するのは正しくない
以下の問題がある

  1. 無限ループ

    lisp (assert! (rule (married ?x ?y) (married ?y ?x) ) ) (married? Mickey ?x)

    とすると、
    (married? Mickey ?x)と (married? ?x Mickey)を交互に探し続ける

  2. notの問題

    lisp (and (supervisor ?x ?y) (not (job ?x (computer programmer))) ) (and (not (job ?x (computer programmer))) (supervisor ?X ?y) )

    は同じ結果が期待されるが、後者は(job ?x (computer programmer))を評価した結果にnotでフィルターするため結果は常に空になる

算機プログラムの構造と解釈(3章)

「計算機プログラムの構造と解釈(SICP)」の3章です

関数型プログラミングとストリーム、遅延評価についてです。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


3章 標準部品化力、オブジェクトおよび状態

3.1 代入と局所状態

3.1.1 局所状態変数

銀行口座を考える

  1. 高設定
  2. 引出

これらを隠蔽して、以下を公開する

  1. 金額の設定
  2. 預金機能

3.1.2 代入を取り入れた利点

rand関数のシードがあるとすると、シードをユーザーが覚えておく意味がないので、関数内に隠蔽とすると楽

3.1.3 代入を取り入れた代価

代入を使わないのが関数型プログラミング(functional programming)

代入があることによる難しさを見ると、

再代入あり

(define (make-simplified-withdraw balance)  
    (lambda (amount)  
        (set! balance (- balance amount)  
            balance  
        )  
    )  
)  

再代入無し

(define (make-decrementer balance)  
    (lambda (amount)  
        (- balance amount)  
    )  
)  

この二つを比べると、make-decrementerは置き換えが簡単にできるが、
make-simplified-withdrawはbalanceの初期状態と代入後の値を区別する必要があるが、置換えモデルではできない
つまり、変数の値が変化するために、置き換えが出来ない。(今まで変数は値の「名前」だったが、代入では値の「格納場所」になった)

参照透明(referentially transparent[参照透過性])があるかないか。
参照透明がないと「同じ」である時の「置き換え」が出来ない、ともいえる

命令型プログラミングと関数型プログラミングを比べると

関数型

(define (factorial n)  
    (define (iter product counter)  
        (if (> counter n)  
            product  
            (iter (* product counter) (+ counter 1))  
        )  
    )  
    (iter 1 n)  
)  

命令型

(define (factorial n)  
    (let ((product 1)  
            (counter 1))  
        (define (iter)  
            (if (> counter n)  
                product  
                (begin (set! product (* product counter))  
                    (set! counter (+ counter 1))  
                    (iter)  
                )  
            )  
        )  
    )  
    (iter)  
)  

関数型では、実行順序を気にする必要はないが、命令型では代入の順序を変えるとバグになる。

3.2 評価の環境モデル

代入が存在することにより、既存のモデルが使えないので、新しいモデルを作成する

環境 : フレームの並び
フレーム: 変数名と値を持つ束縛(bindings)の集まり。外側の環境(外部スコープ)へのポインタを持つ
未束縛: フレームをたどっても変数が束縛されていない状態

このモデルでは、
手続きはlambda式の評価のみから得られ、lambda式を評価した場所が「環境」で、
また、defineはlambdaのシンタックスシュガーである。

3.3 可変データのモデル化

キューの実装は

  1. 追加
  2. 取り出し

表の実装

  1. キーに対応する値の取り出し
  2. キーの存否
  3. 追加
  4. 初期化

インターフェースは作成できるが、Lispではlistしかないのでハッシュ化できない
二次元の表にすることはできる

デジタル回路のシミュレータ

デジタル回路を実装する

  1. 半加算器
  2. 全加算器
  3. 順次呼び出し

wireを実装する

  1. 値を取得する
  2. 値を設定する
  3. 回路につなげる

さらに、
0. シミュレータの経路を作る
0. 接続する

3.4 並列性

3.4.1 並列システムでの時

並列プログラムにおける正しいふるまいとは、「結果」が「正しい」ことであり、「結果」が複数あることもあり得る
つまり、順序が決定していない環境で割合計算が発生すると、どの時点で計算したかにより結果が変わる

例えば、

初期値100のものに以下の並列計算を実行すると、

  1. 20引く
  2. 2で割る

(100 - 20) / 2
(100 / 2) - 20

結果は違うが、どちらも正しいといえる。本質的に並列計算は非決定的である

3.4.2 並列性の制御機構

直列変換器

  1. 積算→加算(101)
  2. 加算→積算(121)
  3. (* x x)のx評価中に加算が発生(110)
  4. (+ x x)のx評価中に積算が発生(110)
  5. 両者の引数の評価が終わった後に、両者の代入が実行される(100, 11)

順序を確定する必要があるのなら、資源をロックすればいい、両方同時にロックするmutexを実装する
ただし、デッドロックは気を付ける必要がある

3.5 ストリーム

3.5.1 ストリームは遅延リスト

リストを使用すると、メモリや時間の消費が大きいので、ストリームを使って逐次処理ができるようにする
計算が終わっていなくても、必要な要素を取得していれば次の処理へ行くことができるのだから、評価を遅延させてもよい

3.5.2 無限ストリーム

遅延評価ができるということは、無限ストリームもできる
素数がほしいのなら、数の連続をエラトステネスのふるいにかけ続ければいい
ストリームを暗黙に使うこともできる

3.5.3 ストリームパラダイムの開発

再帰などはストリームであらわせる

例えば、

  1. 平方根
  2. 交項級数によるπの近似
  3. オイラーの並び加速[sequence accelerator]による改良
  4. 2要素の対の無限ストリーム(両方のストリームの内容を対としてもつ無限ストリーム、i <= j となる(i,j)の無限ストリーム)

3.5.4 ストリームと遅延評価

delayを採用することにより定義前の名前が使用可能になる

3.5.5 関数的プログラムの部品化度とオブジェクトの部品化度

ストリームで状態を表す

手続き型では

(define (make-simplified-withdraw balance)  
    (lambda (amount)  
        (set! balance (- balance amount)  
            balance  
        )  
    )  
)  

ストリームにすると

(define (stream-withdraw balance amount-stream)  
    (cons-stream  
        balance  
        (stream-withdraw (- balance (stream-car amount-stream) (stream-cdr amount-stream)))  
    )  
)  

これによって、変数の状態を持つことなく、状態を表現できるようになり、

算機プログラムの構造と解釈(2章)

「計算機プログラムの構造と解釈(SICP)」の2章です

必要なものを関数化して抽象レベルを上げます。

  1. 別型に共通インターフェースをつける、各型を区別できるようにする
  2. 各要素を区別できるようにする
  3. 型変換ができるようにする

とすれば、共通インターフェースを通して同一のもののように扱うことができるというところまで持っていけます。
オブジェクト指向ポリモフィズムです。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


2章 データによる抽象の構築

2.1 データ抽象入門

2.1.1 有理数の演算

以下の手続きを仮定する

  1. (make-rat <n> <d>): 分子 <n> と分母<d>で仮定された有理数を返す
  2. (numer <x>): 有理数<x>の分子を返す
  3. (denom <x>): 有理数<x>の分母を返す

すると、以下の演算を定義できる
0. 加算
0. 減算
0. 乗算
0. 除算
0. 比較

また、対(pair)という合成データ要素が存在し、以下の手続きを定義されている。

  1. (cons <a> <b>): <a>と<b>をデータに持つpairを返す
  2. (car <x>): pair <x> の前半(cons における<a>部分) を返す
  3. (cdr <x>): pair <x> の後半(cons における<b>部分) を返す

これは、有理数を表すのに適したデータ形式である。
pairを基に先に仮定した3つの手続き(有理数を作成する。分子を返す。分母を返すの3つ)を実装する

  1. 有理数を作成する。
  2. 分子を返す。
  3. 分母を返す

また、デバッグ目的として有理数を表示する関数も定義する

2.1.2 抽象の壁

有理数の実装では、

  • consという事前に用意された、2つの値を保持するデータ
  • consを利用した有理数
  • ratを利用した演算利用できる有理数

という3層に分かれる。
どの層も1つ下の層のみを参照する。
これにより、実装の変更が容易になる。

2.1.3 データとは何か

データは

  1. 選択子(selector) (抽象データ。プログラムから利用される)
  2. 構成子(constructor) (具体的データ表現。選択子が内部的に使用する)
  3. データとして有効な条件

を持つものと定義できる

2.2 データ構造と閉方性

2.2.1 並びの表現

cons の短縮形がlist

(cons (1 cons (2 cons 3 (cons 4 ()))))

(list 1 2 3 4)

リストの内容を取得したいなら、cdrを繰り返せばよい。

  1. n番目を取得する
  2. 長さを取得する
  3. 連結(第1引数の最終要素と第2引数をつなげる)

写像をつくるなら、各項目を訪れてその項目に影響を与えればよい

2.2.2 階層構造

ツリー構造に対してもできる

  1. 長さ
  2. 写像(定数倍)
  3. map

2.2.3 公認インターフェース(conventional interfaces)としての並び

信号処理により、処理を切り離す。

  • フィルタ
  • 計算
  • 要素の取得
    1. 範囲
    2. ツリー

2.3 記号データ

2.3.1 クォート

クォート(')をつけると値が評価されない。
(価値がよくわからない)

微分

関数定義

  • variable? 変数かどうか
  • same-variable? 同じ変数か
  • sum? 和か
  • addend 加数
  • augend 被加数
  • make-sum 和を構成する
  • product? 積か
  • multiplier 乗数
  • multiplicand 被乗数
  • make-product 積を構成

集合

集合を定義する

  • 要素があるか
  • 追加
  • 交差

Huffman符号化木

  • 複合化

2.4 抽象データの多重表現

プログラム内で異なる方法で表現されているデータに対処するために、汎用手続(generic procedure)の話が本節

2.4.1 複素数の表現

複素数を直交座標と極座標で表現できるようにする

  • 加算
  • 減算
  • 積算
  • 除算

これらを、2つの方法で定義できる

  1. 直交座標を基にして複素数を表現する
  2. 極座標を基に表現する

2.4.2 タグつきデータ

両者を同時に実装する場合は

  1. どちらかを判断するためにタグをつける
  2. 各要素取得関数を外部から秘匿する
  3. 複素数作成用を定義する

これによって、既存の算術演算が直交座標・極座標の別を意識せずに動く

2.4.3 データ手動プログラミングと加法性

型タグによる振り分けには弱点がある

  1. 新しい表現を作成した場合は、既存の汎用手続き全てに分岐を追加する必要がある
  2. 名前の衝突を防ぐ必要がある

これでは大変なので、

  1. 呼び出す関数を型に依って変化するようにする
  2. 演算に外からアクセスできるようにする

これで、複素数に対する新しい表現が追加されても既存のものを修正する必要がなくなった。

2.5 汎用演算のシステム

2.5.1 汎用算術演算

有理数複素数(直交座標・極座標)の以下の演算を抽象化する

  1. 加算
  2. 減算
  3. 積算
  4. 除算

2.5.2 異なる型のデータ統合

各演算が抽象化できたので、強制型変換(coercion)によるデータ変換ができる

計算機プログラムの構造と解釈(1章)

「計算機プログラムの構造と解釈(SICP)」を読み始めました

Structure and Interpretation of Computer Programs(SICP)の翻訳本。 Schemeを利用して、プログラミングパラダイムを考察、実装する本です。
実装のみをしている章は省いています

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


1.0 Scheme

Scheme(Lisp)を使用する。
Lispは標準化をしないので、方言が存在できそれが柔軟さにつながっている。
「受動的」なデータと「能動的」なプロセスをぼかし、手続きをデータとして表現することが、プログラムの議論の土台とするのに適している

1.1 プログラム

1.1.1 式

演算子も、関数のように引数を取ることで表すようだ
(* 2 4)
一見、ポーランドっぽいが、ポーランド記法ではない。

1.1.2 変数

変数を定義できる
変数を定義することは、最も単純な抽象化。
変数と値の記憶をenvironment(global environment)と呼ばれる

1.1.3 combinationの評価

組み合わせ(pair)は
0. 部分式の評価
0. 演算子を被演算子に作用させる
という動きをする。

つまり、
部分式の評価を行うことから再帰が必然であり、演算子に作用しない定義式(define)は特殊である。

1.1.4 合成

(define (square x) (* x x))
(define (sum-of-square x y) (+ (square x) (square y)))
で定義できる

1.1.5 関数の置き換え

  1. 作用的順序
    式を逐次評価する
  2. 正規順序
    式を全て展開したのちに、評価する

効率性の問題から、実際には作用的順序が使用される

1.1.6 条件式

  1. cond
    switch。else がdefaultに相当する
  2. if
    if。第二引数がelse
  3. and, or, not

1.1.7 Newton法による平方根

再帰の定義

改行の場所が難しい

1.1.8 ブラックボックス

  1. 束縛変数(関数内部でのみ有効な変数名。外部からは見えず、意味を持たない)
  2. ブロック構造と静的有効範囲(名前空間とか、jsの即時関数と同じ)

1.2 手続き

1.2.1 線形再帰と線形反復

  1. 線形再帰的プロセス
    再帰で自分を呼び出す時に他の情報を覚えている必要があるための記憶が必要(必要容量は線形に増加する)
  2. 線形反復的プロセス
    呼び出し時の値を記憶せず、再帰が止まるところから実行するため、呼び出し元の記憶が不要

1.2.2 木構造再帰

木を舐めまわして、再帰する

1.2.3 オーダー

オーダー記法とかシータ記法について

1.2.4 べき乗

  • 線形再帰
  • 線形反復
  • 線形再帰よりもオーダ減少(Θ(log n))

1.2.6

Fermat(= フェルマー)の素数性テスト

1.3 高階関数

1.3.1 手続きを引数とする

関数も引数にとれる

1.3.2 lambda

無名で関数を作れ、関数を戻り値にすれば、実行したいときに評価させられる

30日でできる! OS自作入門 (4週目から最後)

「30日でできるOS自作入門」の4週目から最後までです

この本でできるようになるのは描画、マルチタスクAPI、ファイル処理
この本を使ってできるようになったのは

  1. アセンブラとCに慣れた
  2. APIの中で処理していることが分かった
  3. OSが処理している部分とCPUやドライバが処理している部分との差が見えるようになった

30日でできる! OS自作入門

30日でできる! OS自作入門


22日目

例外が起きた時に割込が発生するので、そこをハンドリングすれば、例外処理ができる

23日目

メモリを静的に確保するのは無駄なので、malloc()

24日目

ウィンドウを切り替えたければ、出したいのを一番上(マウス描画の下)に置き、一番上を一つ後ろに
ウィンドウを閉じるときは、アプリケーションが止まるということなので、タイマなどもまとめて閉じる

25日目

beepを流すのもPITでできる
色を出すのはvramで出せるが、色数が少なければグラデーションを使って数を増やせる

26日目

移動を描画するのはコストがかかる。
8bitづつ代入するのではなく、32bit連続で突っ込めば速くできる
そもそもマウスの移動に合わせて全て描画するのではなく、マウスが止まった時にそこに描画すれば、速い

27日目

LDTでは、アプリケーション専用のメモリ空間を作成できる
各アプリケーションに必要な関数のみをincludeするために、libファイルを作成すればいい

28日目

ファイルを読む時は、ファイル場所を取得し、シークする。
日本語を出力するなら、フォントファイルを読み込んで各エンコードと文字を対応させる

29日目

ファイルサイズがでかいなら圧縮すればいいし、読み込むときに解凍しながら読めばいい

30日目

計算とか画像出力とかの実装

30日でできる! OS自作入門 (3週目)

「30日でできるOS自作入門」の3週目分です

マルチタスク、ファイル管理、API作成、メモリ保護までです。

30日でできる! OS自作入門

30日でできる! OS自作入門


15日目

マルチタスクは、タスクを入れ替えているだけなので、入れ替え時に現在状態を退避して、別のタスクの状態をロードする
画面描画などはある程度の時間(0.01sとか)待ってやれば十分

16日目

タスクに作業時間をつけることで、必要な処理にリソースが割ける
さらに、優先順位もつければ、割り込みにも即時対応できる

17日目

コンソールを描画することは、背景を変更することと何も変わらないので、vramに画像変更を送るだけ
キーボードの入力に合わせて、描画を変更する
LOCK初期情報などは、BIOS

18日目

コマンドは、入力を覚えて対応する機能を実行すればいい。
ファイル情報はBIOSに記録されているのでそれを引き出す。

19日目

ファイルの内容はFAT(File Allocation Table)に保存先が書いてあるので、それを利用する
実行時には、対象ファイルの内容をメモリに読んでジャンプする

20日目

APIをCで作る場合は、対象の関数を呼び出すのは別メモリ空間へ移動することが必要になる
よって、ジャンプできる仕組みが必要。(本では、アセンブラ呼び出しからのFarJump)

21日目

アプリケーションに割り当てているメモリ以外にアクセスはさせない。
例外割り込みでハンドリングしよう

30日でできる! OS自作入門 (2週目)

「30日でできるOS自作入門」の2週目分です

時間を図れるようになります

30日でできる! OS自作入門

30日でできる! OS自作入門


8日目

マウスの動きもIOからくるので、順次処理する

9日目

メモリサイズを出す

メモリサイズのチェックのために、

  1. メモリの場所を指定して値を代入する
  2. 代入されたかチェックする
  3. メモリの値を反転する
  4. 値をチェックする
  5. 代入場所をずらす

とやれば、メモリがない場所がわかる = メモリサイズがわかる

コンパイラ

コンパイラの最適化が走ると、意図しないコードになることがあるので、アセンブラが読めたほうがいいね!

メモリ管理

空き場所の記録方法

  1. 使っているかどうかのフラグを作る
  2. 空いている連続の場所(開始点と終了点)を記録する。解放されたら、前後を見てつなげたりもする

という方法がある。当然、後者のほうが速い

10日目

描画時には、重ね合わせ(レイヤー)で描画するようにする

理論的には、
レイヤーの描画や順位が変わった段階で画面全体を再描画すればよいが、それだと処理が重いので、
変更範囲のみを再描画するようにする

11日目

レイヤーで下から順に描くようにすると、レイヤーが重なったときに同一個所への処理が重複する
→各場所で一番上にあるものを覚えてそこだけ描く

12日目

PIT(Programmable Interval Timer)に対して、100Hzごとに通知させることで、10ms毎の割り込みを実現できる
割り込みに対して、複数の構造体それぞれでカウントすれば、複数タイマが作成できる

13日目

速度改善の結果を見るために、一定間隔で発生した無限ループ中のSTIの回数を数える。
fifoをタイマ、マウス、キーボードに分けていたのを統一して、if文の3条件チェックをなくしたら結構速度が上がる。
しかし、割り込みタイマのスタック(もどき)を配列からリンクトリストに変えても速度は変わらなかった

参考) 自環境でのSTI回数
初期:
0901049237
if文削除:
1320863127
リンクトリスト化:
1345018184

14日目

解像度はビデオカードに送信する値によって変化する