Amosapientiam

https://yuchiki.github.io/

古代ローマ人は投げたがり

英単語によく出てくる○jectの語源についての記事です。

jacio: 投げる

“jacio"は「投げる」を意味するラテン語の動詞である。 この動詞は「立てる」「作る」「セットする」「拡散する」「放出する」「据える」「置く」などをも意味する1大変多義な語である。私は古代ローマ人ほど上品ではないので(?)、対象をひっ掴んで遠くにぶん投げるなり置きたい場所にドンと置くようなイメージでついつい括って考えてしまう。 「ぶん投げる」「おっ立てる」「こしらえる」「ぶっ散らかす」「ぶっ放す」「叩きつける」「押さえつける」…などのように。

古代ローマ人はよほどjacioがお気に入りだったようで、この動詞は多くの語に派生し、様々な動作、状態、物などがjacioを使って表現されている。

jactus:投げられた

jactusはjacioの完了分詞であり「投げられた」などの意味を持つ。 カエサルの「賽は投げられた。」は、原語では"Alea jacta est".である。 また、複合語では母音が弱化してxx-jectusなどになる。

英語は投げられてばかり

英語はラテン語と、ラテン語の子孫の一つであるフランス語から大量に語を借用しており、それゆえ *ject の形の単語が大量にある。 以下にその一部を示す。 語と意味の対応の他に、その意味がどう導かれるかをこじつける考察するために語の構成も示す。

英単語 意味  構成(括弧内は恣意的)  備考
subject 臣民 sub(下に) ject(据えられた)
subject 主題 sub(下に) ject(据えられた) ギリシャ語のὑποκείμενον(基層, 主題)を訳した語
project 計画, 投影する pro(前に) ject(投げられた)
object 対象 ob(目的として) ject(据えられた)
object 反対する ob(反抗して) ject(ぶっ放す)
reject 断る、拒絶する re(返す) ject(投げられた) 投げ返された
inject 注射する in(中に) ject(ぶちかます)
adjective 形容詞 ad(〜に) ject(据えられた) ギリシャ語のἐπίθετον(付加的な, 形容詞)を訳した語
eject 追い出す ex(外に) ject(ほっぽり出された)
conjecture 予想 con(一緒に) ject(据えられた) 物事に対して自分の考えを結びつける
abject 落ちぶれた ab(奪って) ject(据えられた)
deject がっかりさせる de(離して) ject(据えられた)

ラテン語では xx-jectusは間違いなく形容詞か、あるいは形容詞の名詞用法である。 英語では、xx-jectの品詞は語形からは全くわからない。能動の意味の動詞ですら完了分詞形を経由して輸入されている。 どうしてこうなった…

共変/反変についての走り書き

Covariant(共変)/Contravariant(反変)/Invariant(不変)について、自分用に走り書きした。 うまく説明できずにもにょったり、どれがどれだかわからなくなった時にこれを読みなおす。

記号

 \vdash t : T
項tは型Tを持つ。
 \vdash A \leq B
型Aは 型B の部分型である。もし項tが \vdash t : Aであるならば \vdash t : B でもある。この場合B型の値が要求されているところで、代わりにA型の値を使っても問題ない。

定義

 Op :: Type \rightarrow Typeを型演算子とする。

Opはcovariantである。
 \vdash A \leq Bを満たす任意の型A, Bに対して  \vdash {Op}\ {A} \leq Op\ B
Opはcontravariantである。
 \vdash A \leq Bを満たす任意の型A, Bに対して  \vdash {Op}\ {B} \leq Op\ A
Opはinvariantである。
Opはcovariantでもcontravariantでもない。
Opはbivariantである。
Opはcovariantかつcontravariantである。

Covariant, Contravariantな型演算子の例

 \vdash a_0:A ,  \vdash b_0 : B かつ  \not\vdash b_0 : A,  \vdash A \leq Bとする。 型演算子 Get,  Setを次のように定義する。  Get = T \mapsto (() \rightarrow T)

 Set = T \mapsto (T \rightarrow (){})

このとき、  Get は CovariantであるがContravariantではなく、  Setは ContravariantだがCovariantではない。 すなわち、  \vdash Get\ A \leq Get\ B \vdash Set\ B \leq Set\ Aは言えるが、他は言えない。

例の例

関数  get_A,\ get_B,\ set_A,\ set_B

 \vdash get_A : Get\ A

 \vdash get_B : Get\ B

 \vdash set_A : Set\ A

 \vdash set_B : Set\ B

だとする。

このとき、

 Get\ B\ b = get_A\ ({}(){})
OK
 Get\ A\ a = get_B\ ({}(){})
だめ
 set_A\ (b_0)
だめ
 set_B\ (a_0)
OK

 Get\ B型の項が要求されている箇所に get_Aを渡したり、  Set\ A型の項が要求されている箇所に set_Bを渡したりすることはできるが、  Get\ A型の項が要求されている箇所に get_Bを渡したり、  Set\ B型の項が要求されている箇所に set_Aを渡したりすることはできない。

【C#】メモ化再帰の抽象化

C#を真面目に勉強しようと思い、kekyoさんの

Final LINQ Extensions

を読んでしょっぱなから衝撃を受けた。 C#ってこんなに簡単に無限列が書けるんだ!

イテレータと無限列

たとえば0の無限列のイテレータは以下の通り。

   public static IEnumerable<int> Infinity() {
        while(true) yield return 0;
    }

以下はInfinityを用いて0を100回出力するコード。

   public static void Main (string[] args) {
        Console.WriteLine(string.Join("\n", Infinity().Take(100)));
    }

Fibonacci数列なら以下のように書ける。

   public static IEnumerable<ulong> Fib(){
        yield return 0;
        yield return 1;
        foreach (var k in Fib().Skip(1).Zip(Fib(), (m, n) => m + n)) {
            yield return k; 
        }
    }

    public static void Main (string[] args) {
        foreach (var n in Fib().Take(40)) {
            Console.WriteLine(n);
        }
    }

書ける。が、上記のコードは再帰を使っており遅い。そこで、メモ化して線形時間で計算できるようにする。

   public static IEnumerable<ulong> MemoFib(){
        ulong predpred = 0;
        ulong pred = 1;
        yield return predpred;
        yield return pred;
        while (true) {
            ulong current = predpred + pred;
            predpred = pred;
            pred = current;
            yield return current;
        }
    }

無事に書けた。が、メモ化により状態管理のコードが混ざったため、先ほどのfib実装が宣言的に書けているのに比べると手続き的だ。 また、メモ化自体は様々な無限列で必要になりうる。そこで、メモ化の仕組みと再帰的な数列生成の部分を切り分けたい。

メモ化

というわけで下のように切り分けた。

   public static IEnumerable<T> memoize<T>(Func<Func<int, T>, int, T> generator){
        Dictionary<int, T> memo = new Dictionary<int, T>();
        T accessor (int n){
            if (!memo.ContainsKey(n)) memo[n] = generator(accessor, n);
            return memo[n];
        };
        int i = 0;
        while(true) yield return accessor(i++);
    }

    public static ulong FibFactory (Func<int, ulong>accessor,int i){
        switch (i) {
        case 0:
        case 1:
            return (ulong)i;
        default:
            return accessor(i - 2) + accessor(i - 1);
        };
    }
        
    public static void Main (string[] args) {
            foreach (var n in memoize<ulong> (FibFactory).Take(80)) {
            Console.WriteLine (n);
        }
    }

memoize内部のaccessor関数はメモテーブルの読み出しをラップし、すでに値が計算されていればテーブルの値を使い、そうでなければgeneratorを用い値を計算する。 generatorはaccessorとindexを受け取り、数列のindex番目の値を計算する。

いかに僕がIOに20日以上を費やしたか

この記事は愚痴です。

動かないIOラッパ

まさかIOでハマるわけがないと思っていた。IOなんて夏学期と夏休みで何回も書いたはずなのに...

Carina 内部で用いるデータは4byte単位なので、夏学期に書いたIOをword=4bytes 単位アクセスできるようにちょっとラッパするだけだ。1日あれば終わるはずだった。まさか20日もハマるなんて。Carina 最大の誤算がこれだ。シミュレータでは動くのに実機では全く動かない現象。完全に寿命が縮んだ。

絶対ucfファイル確認しような(12 days)

実機は0x00を返すばかり。完全に謎だった。

SRAMRS232Cを用いる。そこでucfファイルは夏学期の実験で使用したものをコピペして使った。SRAMを使えているかのテストをし、デバッグ出力を実機に送信するという内容の実験だった。ここに大きな見落としがあって、この実験ではデータをPCから受信していないのでRS-RXの制約が抜けていたのだ。ucfの入れ忘れではなく、100行近いucfファイルに1行抜けがあったのだ。

ここのデバッグは概ね次の要領で行われた。

  1.  余計に待ってみたり、ラッチを入れたりして確実にデータを受け取る
  2.  シミュレータで正しく動くことを確認する
  3.  ucfがないので実機で正しく動かない
  4. タイミングのバグを疑う
  5. 1に戻る

ラッパするだけだったモジュールは、いつしか完全にグニャゲッティと化した。これが後述の full-empty-hack問題を起こす。

First Word Fall Through(2 days)

core generator が生成する同期FIFOには大きく2つのモードがある。Standard FIFOと FWFT FIFOだ。前者はread_enableを掛けると、次にREを掛けるまでFIFOの最後のデータが出力され続ける。後者はFIFOの最後のデータは到着以降常に出力されており、REを掛けるとFIFOが一つ流れて、次のデータが出力されるようになる。感覚としては前者のREは「データを読ませてくれ」のREであり、後者のREは「データを読んだので次を頼む」のREだ。

IOのbufferとしては後者のFIFOの方が良かった。前者だとREを掛けてから1clk待たねば読めないからだ。しかし、夏学期の僕は前者を用いてIO moduleを構成していた。そもそもFWFTモードの存在を知らなかったのである。コアは後者のFIFOを前提して組んでいた。ここの埋め合わせもIOラッパがしなければならない。IOラッパが更に水膨れする。

 full-empty-hack(3 days)

元々のIOユニットにはFIFOがついていたので、タイミングを気にすることなくバーストアクセスできるはずだった。しかしFIFOから4byteを読んで1wordのデータをこしらえている以上、それは不可能になった。どうするか。

最適な設計は、 FIFOをbyteではなくword単位のものに変えて、ラッパの外側におくことだろう。しかし、このIOラッパは下手なところを触ると途端に動かなくなった。それに今動いているところを書き直す体力は残っていなかった。そこで、FIFOから出てくるfull,emptyを誤魔化そうという発想に至った。ラッパで作業している最中はfullやemptyを立てておき、コア側からのアクセスを遠慮してもらう。自分がもはや正気で無いのはわかっていたが、一刻も早くIOの実装を終わらせたかった。

int main(){

  puts("hoge");

  return 0;

}

を2週間掛けても書けないでいるなんて!

test(1 day)

無心でテストを書いていた。IOを書くためだけに学校に10泊以上していた。たかがIOのために。テストケースが全て動作していることを確認すると、僕はIOフォルダに心の中で chmod 444 した。僕自身は二度とそのディレクトリを覗くことはないはずだ。アクセスごとにfullとemptyが数クロック起ち続けるゴミIOが一つ世に生まれた。

 IO revival(3 days)

衝撃の事実。raytracerはword-wise送信をしなかった。全てが無駄だった。

IOの中身も、プログラムローダも、コアも、この頃には闇IOラッパの闇と四つに組んでしまい分離不可能であった。byte-wiseアクセスモードを追加するのに3日要した。

 

IO再設計

完動した。次にすることは明らかだ。一番下から一番上までIOを再設計する。夏学期のIOは使わない。CarinaのIOラッパは見もしない。一から全部書き直す。前回の反省を踏まえてたっぷり2週間取った。

1日で完成した。

教訓

ダメなときはフルスクラッチしましょう。