新千葉 ガーベージ・コレクション

FPGA マガジンやインターフェースで書けなかったこと等をちょぼちょぼ書いてます。@ryos36

Min Caml コンパイラ その4

一向に Min Caml にたどり着かない。
今日は予備知識

The Essence of Compiling with Continuations
https://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf

何やら有益なことが書いてあるらしい。どういうわけか、誰かが（大和谷さんという人）が和訳していたりする。
http://www.jaist.ac.jp/~kiyoshiy/writing/flanagan_EssenceOfCompilingWithContinuations.tex
図などは原文を見ないといけないけど、こういう資料はありがたい。
pdf 化しておこうhttps://drive.google.com/file/d/0B03DLc17PR0DOTF4a0JIelBsV1k/view?usp=sharing

まぁつまり CPS は無駄なので K正規化しましょうということらしい。その真意はまだわかっていない（わたしが）。

Zybo で Jupyter + PYNQ のソース を動かす。

Zybo でも PYNQ で採用しているシステムが動いた。gpio と HDMI_OUT はできた。HDMI_IN は出来なかった。環境が悪いのか、どっかでしくじったのかは不明。

以下、作業備忘録

  • PYNQ の base.tcl から Vivado で合成（この時点では PYNQ のシステム)
  • デザインから
    • arudino の iop 削除
    • audio のブロック削除
  • ここで tcl をセーブ
  • さらにデザインから
    • pmod を２つ削除
  • PS の設定を Zybo に変更
    • UART などの MMIO
    • DDR の設定
  • xdc をZybo に変更
  • 合成
  • ハードウェアを export (ps7_init_gpl.[ch] ができる)
  • ps7_init_gpl.[ch] から u-boot をつくる（これで boot.bin と u-boot.img ができる）
  • boot.bin と u-boot.img と zybo 用の dtb に入れ替え。uImage はそのまま。
  • mmcblk0p2 を（どっかで) mount して以下の修正
  • rc.local から 4_boot_led.sh をコメントアウト
  • pl.py の devicetree の名称を変更
  • bistream に zybo の bit と tcl を base の名前でおく

この作業をしたのちに ol で download すると zybo の done が点滅して最終的には点灯。
あとは普通に Jupyter で実行すればよい。まちがったのを実行するとそのままお亡くなりになる可能性もあるので注意。

HDMI out 出来たとはいえ、pmod 経由で HDMI out する基板が必要。

f:id:ryos36:20161018003133j:plain

イメージはここ経由でダウンロード可能。

Min Caml コンパイラ その3

引き続き、コンパイラの社内研究会開催。

ざっくりと概要は読み終わった。

K 正規化とα変換で SSA と同等なことが達成ているのではないかと。A 正規化はインラインが楽。でもインラインしないなら、結局 K 正規化しないといけなさそう。

HLS ではクロージャ変換いらねーんじゃね？かと。関数を引数に渡したときにクロージャー変換が必要なのは謎。関数を引数に渡したときは結局テンプレート的なこと=多相にしないといけなさそう。

コンパイラを作る流れは一通り読めた。普通のコンパイラの作り方という結論。型推論以外は。

あと、型推論はうまく今のコンパイラの外側でやれないか？と。つまりオンオフができるように（直交的に）できないか検討したい。とりあえず試しにやってみることになった。なんちゃって型推定。

型推定をざっくりいうと、int と float （だけとすると）の世界を分けましょう。ということで、全部を全部、推定できないから、さいしょに * と *. といった型の決まった演算を足掛かりに推定していきましょうということらしい。なので、言語として最初からその思想があるかどうかがポイントで、その思想がない言語に後から導入するのは厳しそうな感じ。

F# を調べると *. みたいなのがなさそうだったのでどうしているのか不思議。

その他

qiita.com
これを読むと、私もコンパイラになれそうな気がしてきた。アイキャッチ画像があって、そういう時代の流れなんだなぁ、、、と思った。

compiler-errors-for-humans
「エラー発生時に「もしかして？」を表示してくれる。」らしいぞ。

これで、型変換を含めたコンパイラへの足掛かりは出来た（つもり）。

PYNQ のデザインを合成してみた

f:id:ryos36:20161013171056p:plain

2016.1 ようだったが、無理やり 2016.2 に変えて合成してみた。結構時間がかかると思ったら、単純なデザインではなかった。その上、なぜかタイミングエラーですが。気にせず、先に進みます。

f:id:ryos36:20161013172658p:plain

右下には audio や iop1 iop2 io3 というブロックがあります。iop は IO Processor のようです。pmod と arudino の sheild に対応しています。

f:id:ryos36:20161013172954p:plain

tracer buffer というのがあって、これは各ピンのログをとれるようです。(AXI Stream として）

大きそうな iop3 をのぞいてみます。
f:id:ryos36:20161013173114p:plain

MicroBlaze がはいっていることがわかりました。iop ごとに入っているので全部で3つです。

mb3_timers_subsystem というのがあります。

f:id:ryos36:20161013173438p:plain

pwm などのためのタイマーが5つあり、AXI でつながっています。MB からコントロールするようです。ほかに MB の interrupt controller があるので、おそらくこれらの割り込み処理を MB が担当するのでしょう。プログラムは BRAM に置くようです。

また、そのほか GPIO, SPI, IIC などのサブシステムがあります。shield で規定されている IO に対応しているようです。

全部入りのシステムにしたかったのでしょう。pmod も spi だったり iic, gpio, timer があります。switch というブロックで切り替えるようで、それも MB がやっているようです。

f:id:ryos36:20161013174305p:plain

かなり重そうな大規模システムです。FPGA の拡張性を考えるともうすこしシンプルなものも用意してくれるといい気がします。

Min Caml コンパイラ その2

速攻MinCamlコンパイラ概説 をみればいいだけだったりして。ML の解説まで書いてある。
あと OCaml の参考書としては「プログラミング in OCaml」という本を読んでいる。Kindle版はあるが、紙の本の方は絶版だ。いい本だけに残念。

「MinCamlはMLのサブセットです」とある。まず ML がわからないとダメ。ここで躓く。e::= の式も躓く。とりあえず自分の理解を書いておこう。

let が OCaml と違う。

let x = e1 in e2

となっている。OCaml では大域変数として

let pi = 3.14159

とかできるが、どうも Min Caml はできないらしい。上の文法を見るとそう書いてあるから、そうなのだが、ここで躓く。ML では let ... in ... しかないようにも見えるので(よく知らない)、Min Caml という名前から OCaml に誘導されそうになるが、「MinCamlはMLのサブセットです」ということらしい。

関数の定義が独自(?)

関数の定義にわざわざ「再帰関数定義」と銘打っているので、再帰じゃない関数があるのかと？勘違いするが、どうも、すべての関数（プリミティブを除くと）は「再帰関数定義」らしい。そして、

let rec f a0 a1 a2 = e1 in e2

となっていて、rec という特別なキーワードが出てくる。このキーワードは ML にも OCaml にもないように思う（自信なし）。(hatena のキーワードでハイライトされてしまった。OCaml に let rec が let とは別にあった)。ということで、関数の定義は let rec で、それは常に再帰関数定義となる。再帰関数定義の意味がよくわからないが、上の e1 でも使えるということなのだろうか？

最初に理解しなくて張らならないのは Min Caml の文法

OCaml の文法とは Min Caml は違うので、まず Min Caml 自身の文法を「CCaml とは違う」ということを念頭に理解しなくてはならないと思う。コンパイラを作るうえで OCaml の理解は必要だけど、極端な話、この時点では OCaml しらなくてよい。Min Caml を理解するのが先。そして、どこが OCaml と違うのかを理解する。というのが感想。とくに OCaml や ML 知らない人（私だよ）は特にそうだと思う。

Min Caml を使う

  • まず、 git clone する。
  • to_x86 というシェルプロを走らせる。(ほかに to_ppc, to_sparc なんてのがある)
  • make する。min-caml ができる。 (min-rt は興味のある人だけ make すればよい。直接コンパイラに関係ないから)
  • test をみて Min Caml の雰囲気を知る
  • 自分の環境で Min Caml のソースを作る（あるいは test からコピーする）
  • Min Caml でコンパイル
min-caml adder
adder: adder.s libmincaml.S stub.o
        gcc -m32 -g -O2 -Wall $^ -lm -o adder

こんな感じで理解を深めていけばよい。

*. はあるけど * はない？

OCaml で躓くのが整数と小数点ありの数。これ ML では別々の世界を持っていると考えるみたいね。なので、掛け算も小数点の場合は *. で、整数の場合は * 。
ただし、Min Caml で * はサポートされていないっぽい。*. はある。

let pi = 3.14159 in
    let rec f r = r *. r *. pi in
        print_int (int_of_float (f 789.0));
print_newline()

Kiss4 の環境作り

f:id:ryos36:20161008233416j:plain
Kiss4 という Zynq のボードのために、環境作り。Yocto で環境を作っている。krogoth という branch を使用。

  • poky
  • meta-xilinx
  • meta-openembedded

と zybo からぱくった

  • meta-kiss4

まちがえて meta-openembedded の branch を master にしたら、

python-dbus fails configure with "could not find Python headers"

というエラーが出て止まってしまった。branch をちゃんと krogoth に合わせたらうまくいった。
yocto に bug として出ていたのでバグかと思ってしまった。単純ミスだった。
https://bugzilla.yoctoproject.org/show_bug.cgi?id=2072

Pynq に大きく水をあけられてしまったので、こつこつ環境を構築して、追いつきたいと思う。

Mini Caml コンパイラ その1

github.com

ここにある pdf をみながら、社内でコンパイラ(型推論)の勉強会を開く。
http://esumii.github.io/min-caml/jpaper.pdf
いま、見たら tutorial-minicaml.doc なんてのがあった。

最初から躓くよね。「単相性」ってなによ。K くんの指摘で「多相型がないこと」の意味をちょっと理解する。template のように型をいくつも取れるのが多相型という理解をした。よんでいくと、決定できないときは int と推論するとある。そういうことか。

サンクとクロージャの違いが明確にわからん。とか、（クロージャは遅延評価とは関係ないのか、、、）正格性とか線形性とか、、、軽く読み飛ばす（深い理解もなく先に行く）。最初の週は OCamlLex と OCamlYacc をある程度理解すればいいと。MinCaml の抽象構文と型ってのが、そもそも Ocaml を理解してないとダメだ。数か月前に読んだんだけど、、、fix record の問題も軽く読み飛ばし。非カリー化、、う～む。先にいこう！！

ということで、3.1 に字句・構文解析にたどり着く。そして、3. 型推論を経て、K正規化で時間切れ。

まずはちゃんと OCaml を思い出して、構文を理解しないとね。そして、K正規化に突入していかないといけない。だれかがそういえば、Scheme で書いていたような。