To Home | English
Last modified: Mon Mar 21 21:21:04 JST 2011

Ocaml Internal


前半はversion 3.06 でのおはなし、バイトコードは 3.07

コンパイラで関数適用の部分をパーズしているところを見つけたいと思った

parsing/parser.mly で構文木を生成し、 parse.ml でそれを処理する

それを型付けしたい

typecore.ml で構文木読み込み。ここがメイン。
型情報の前にstaticなcall graphを書きたい
関数呼出のパーズ。

ちょっとお絵書き

Xmamewo:~/project/analyze_ocaml> drawMakefile -i .depend -g -sub typing/typecore > r.vcg

dependency graph

必要とされる側から必要とする側に枝を貼ったグラフで、 typing/typecore{ml, mli} から たどれる部分を描画している。上の三つの依存性に注目したい。 

Typemod.type_structure
  -> Typecore.type_binding
    (* -> Typetexp.reset_type_variables(); *)
    -> type_let
      -> type_pattern_list
      -> unify_pat
      -> iter_pattern (when !Clflags.principal)

typemodで遊びたい

準備 ocaml-* ディレクトリで以下のコマンドを使ってコンパイルする。 
  > ocamlc -I utils -I parsing `tsort_cmo .depend -g typing/typemod.ml -setE .cmo -e` -a -o typemod.cma

Type_mod.type_structure で型をつけてみる。つけた後とかどうなんの? customized_parsing ディレクトリで 以下のようにする 
# #use "init.ml";;
...
# #load "typemod.cma" ;;
# let sample = t ();;
print expression
let a = 1;;
val sample : Parsetree.structure =
...
# Typemod.type_structure Env.empty sample;;
- : Typedtree.structure * Types.signature * Env.t =
([Typedtree.Tstr_value (Asttypes.Nonrecursive,
   [({Typedtree.pat_desc = Typedtree.Tpat_var <abstr>;
      Typedtree.pat_loc =
       {Location.loc_start = 4; Location.loc_end = 5;
        Location.loc_ghost = false};
      Typedtree.pat_type =
       {Types.desc =
         Types.Tlink
          {Types.desc =
            Types.Tconstr (Path.Pident <abstr>, [], {contents = Types.Mnil});
           Types.level = 100000000; Types.id = 29};
        Types.level = 35; Types.id = 28};
      Typedtree.pat_env = <abstr>},
    {Typedtree.exp_desc = Typedtree.Texp_constant (Asttypes.Const_int 1);
     Typedtree.exp_loc =
      {Location.loc_start = 8; Location.loc_end = 9;
       Location.loc_ghost = false};
     Typedtree.exp_type =
      {Types.desc =
        Types.Tconstr (Path.Pident <abstr>, [], {contents = Types.Mnil});
       Types.level = 100000000; Types.id = 29};
     Typedtree.exp_env = <abstr>})])],
[Types.Tsig_value (<abstr>,
  {Types.val_type =
    {Types.desc =
      Types.Tlink
       {Types.desc =
         Types.Tconstr (Path.Pident <abstr>, [], {contents = Types.Mnil});
        Types.level = 100000000; Types.id = 29};
     Types.level = 35; Types.id = 28};
   Types.val_kind = Types.Val_reg})],
<abstr>)

ちょっとしたながれ

   parsing      =>  typing    => bytecomp 
parser->parse -> typemod -> translmod -> compile

この流れをうむものは driver ディレクトリ内で定義されている。
typing/typemod (型付け。型つきの木へ。Ident.t がでてくるということは名前から Id に変化するのかな?)
bytecomp/matching.ml (lub letのような静的パターンマッチング)
bytecomp/translmod.ml (Typedtree を lambda 式に変換)
Ident.t は抽象型であるけれども名前情報は持っている。createで渡す文字列は name フィールドに保存する。 (typing/ident.ml) そして Ident.name 関数で取り出せる。 まぁ、普通か。
clambda, printcmm なんかが asmcomp/ にある。中間言語の変換とか最適化かな (cmm は C--)

さすがにlambdaまでいくとパターンはない

ここを触ってみたいと思った。 bytecomp/printlambda.ml があるのでとりあえず これを触ってみよう。その前に、もちろん lambda への変換が必要。で、 transl.mli をみてみると 
  val transl_implementation: string -> structure * module_coercion -> lambda

module_coercion ってなんだろう? これは Typedtree で定義されている。
じゃぁ、 transl_implementation ってどんなふうに使われるのかな?
ここまでくると、 driver/compile.ml までくるのであった。
transl_implementation の最初の文字列は モジュール名。
二番目の引数には Translmod.type_implementation の返り値をそのまま渡している。
{type, transl}_implementaion はコンパイル単位 (ファイル) に適用する。
tranls_structure は translmod.ml が公開していない。ちゃんと implementation をつかいますか。
Typemod.type_implementationの使用例 
Typemod.type_implementation sourcefile prefixname modulename env

simplif.ml にかけてみたい。とりあえず、ここまでのセッションをファイルに保存。
compile_session.txt

単純になったlambda (bytecomp/simplif.ml)

Xmamewo:~/test> ocamlopt.opt -dlambda dump_raw.ml -o dump_raw
(seq
  (let (match/60 [0: 100 200])
    (seq (setfield_imm 0 (global Dump_raw!) (field 0 match/60))
      (setfield_imm 1 (global Dump_raw!) (field 1 match/60))))
  (apply (field 27 (global Pervasives!)) (field 1 (global Dump_raw!))) 0a)
もう名前が数字で表されたフィールド (オフセットのようだ) になっている。 (field 1 (global Dump_raw!)) は 直前で定義した b を表している。この オフセットと名前の対応をとりたいなぁ。

例えばある型の値を文字列化したり、Serialize したり (保存できる形式にすること) するには型の関係を知らなければならない。例えばあるレコードを文字列化するには、 そのレコードのフィールドの文字列化の方法を知らなければならない。深くたどっていく うちに、ユーザー定義でないプリミティブな型にたどり着く。これらにはあらかじめ、 文字列化関数や、Serialize関数を対応付けておく。この構造をたどるのがメイン。 Polytypic とかいうのがにているトピック。
例えば、各基本型の表示関数 print_int, print_string, print_char は準備 されているものとして、ユーザー定義型(variant, record) の単純な表示関数を定義する。 単純なとは、プリミティブ型のフィールドはそれに対応する関数を呼び、そうで なければたどるということ。

ぐっと範囲を狭めて Ocaml でそんなことをやってみようとする。そんなことをするには 多分型のついた後の抽象木が良いだろうと予測して、Typemod.type_structure で得られる 結果をいじることにする。
ちょっとした問題
  引数に渡すEnv.tの取扱。 初期値と後で渡すときの環境
だいたいコンパイラ全体でこの部分はどのようにして使われているんだろう?
それよりもコンパイラは Typemod.type_implementation を使っている。これはファイル名、 プレフィックス名モジュール名と環境をとるようだ。環境は Compiile.initial_env () をつかっている。

otherlibs/labltk/browser をみてみる

あの、型でライブラリ関数を検索とかいうのはどうやってるのかちょっと興味があっただけ。
落書
Xmamewo|1:25|~/project/analyze_ocaml/otherlibs/labltk/browser> xvcg -silent -scale 80 -psoutput ocamlbrowser.ps ocamlbrowser.vcg
... gimp で変換 ...
dependency graph of ocamlbrowser
Search ラベルを手がかりにしてみてみる。
viewer.ml:428 search_string をSearchエントリボックスでリターンキーを押したときの ハンドラとして登録。
viewer.ml:163 search_string の定義
  mode が "Type" だったら search_string_type ~mode:`Included
  Exact なんてモードもある。
searchid.ml:280 search_string_type の定義。型は↓ 
val search_string_type :
  string -> mode:[< `Exact | `Included] -> (Longident.t * pkind) list
type pkind =
    Pvalue
  | Ptype
  | Plabel
  | Pconstructor
  | Pmodule
  | Pmodtype
  | Pclass
  | Pcltype
じゃ、searchid.ml から切り出してみよう。。。。。 topを作ろう。
 otherlibs/labltk/browser> ocamlmktop -I ../../../parsing -I ../../../typing -I ../../../utils ../../../toplevel/toplevellib.cma list2.ml searchid.ml -o stop
toplevellib.cma を使うとそれなりに遊べそう〜。
うきゃ。できた。 search_type.ml
type_server.ml

型を表す値 (type_expr) を文字列にする

Printtyp モジュールでできる。 コンパイラを -i つきで起動したときにはこのモジュールの 関数が呼ばれて型が表示される。
例
  type_server_with_type_annotation.ml
ocamlのバイトコード
バイトコードインタプリタ ocamlrun を java で書き換えたら、ocamlのバイトコードが JVM上で走る。けど、 ocaml のバイトコードってどんなのだろう?
byterun/interp.c をみる
レジスタ
pc
sp
accuaccumulator
env
transp
extra_args
スタックは下に向かって延びる (-- が延びる方向)
ACCN (N = 0 .. 7)スタックのN番目の値を accuに入れる
PUSHaccu の値をスタックトップにつむ
PUSHACCN (N = 0 .. 9)スタックトップに accu の値を積んで、つんだ後のスタックでN番目の値を accu に入れる。(PUSH と PUSHACC0は同じ)
PUSHACCPUCHACC0, PUSHと同じ
ACCスタックのをポップ。スタックのトップの値を accu に入れる
POPsp += *pc++; !?
ASSIGNsp[*pc++] = accu;
accu = Val_unit; !?
ENVACCaccu = Field(env, *pc++);
ENVACCN (N = 1 .. 4)envのN番目の値をアキュムレーターに入れる
PUSHENVACCN (N = 1 .. 4)accu の値をスタックにプッシュして、 accu に env の N番目の値を入れる
PUSH_RETADDR0: pc + *pc (戻りアドレス?)
1: env レジスタの内容
3: extra_args レジスタの内容
APPLY extra_args = *pc - 1;
pc = Code_val(accu);
env = accu;
APPLY, APPLYN (N = 1, 2, 3)関数適用のようで。。。
extra_args: 引数の数 - 1
  APPLY のときは *pc - 1 を入れている。。。。
accu の値をpc に入れているので APPLY 実行時には呼び出す関数の アドレスが accu に入っているのだろう。
スタックレイアウト (トップから)
引数1
...
引数N
pc
env
extra_args
APPTERM, stackのレイアウトは!?
APPTERMN (N = 1 .. 3)スタックレイアウト
sp = sp + *pc - 2; の後
引数をスタックに積む
accu に飛ぶ
env を accu の値にセット
RETURNsp += *pc++
CLOSUREpc から nvars によみこみ。引数の数?
accu = pc + *pc
CLOSUREREC
PUSHOFFSETCLOSURE
OFFSETCLOSURE
PUSHOFFSETCLOSUREM2
OFFSETCLOSUREM2
PUSHOFFSETCLOSURE0
PUSHOFFSETCLOSURE2accu の値をスタックにプッシュ
OFFSETCLOSURE2accu = env + 2 * sizeof (value)
GETFIELDN (N = 0 .. 3)accu + Nを accu に読み込み
GEFIELDaccu + *pc を accu に読み込み
BRANCHpc += *pc (相対ジャンプ)
BRANCHIFaccu の値がfalseでないならば pc += *pc (BRANCH) そうでなければ次の命令を実行
BRANCHIFNOTBRANCHIFNOT の条件部分を反転した命令
BOOLNOTaccu の値を boolean 反転
CONSTN (N = 0 .. 3)accu に N を入れる
PUSHCONSTN (N = 0 .. 3)accu の値をスタックに積んで、Nを accu に入れる
PUSHCONSTINTacumulator の値をスタックに積む
CONSTINTaccu に *pc を入れる。(コードを読み込む?)
NEGINT2 - accu を accu に入れる。再下位ビットはタグで整数ならば1 ポインタならば0
C_CALLN (N = 1 .. 5)Cの関数を呼ぶ。第一引数はaccu第二引数はsp[1]!!(0ではない)
accuに結果を格納する
C_CALLN...?
ADDINT, SUBINT, MULINT, DIVINT, MODINT
ANDINT, ORINT, XORINT		accu とスタックトップで演算を行い結果をaccuに入れる。スタックはポップされる。
LSLINT, LSRINT, ASRINTaccu に入っている整数をスタックトップ にある整数分だけシフトする。スタックはポップされる。
結果を accu に入れる。整数としてタグがつけられる。
EQ, NEQ, LTINT, .... (整数比較)accu とスタックトップを比較し、 結果を accu に入れる。スタックはポップされる。
BEQ, BNEQ, BLTINT .... (整数比較後分岐) 比較が真ならば pc += *pc (BRANCH)
OFFSETINTaccu += *pc << 1
OFFSETREFField(accu, 0) += *pc << 1
accu がさすメモリ領域にpcの値を整数として入れる (1 bit shift)
ISINTタグをみて整数か否かを調べる。結果は accuへ (accu & 1)
Next.. goto next_instr
Fallthrough !? (PUSHACC, PUSHENVACC) Next; がなくて下に行く
演算結果は accumulator に入れる
curr_instr = *pc++
pc の型は int32
Cの外部関数を呼ぶ前に pc, sp, env を保存する

byterun で make ocamlrund とすることで、 -DDEBUG オプションつきで コンパイルされたバイトコードインタプリタ ocamlrund が作成される。 -t オプション つきで実行すると実行したバイトコード列を表示する

インタプリタのブート。byteコードの書式

caml_main -> interprete
load_code (fix_code.c) で start_code へのコードよみこみ

書式に関連しそうなところ
exec.h のコメントにデーターフォーマットの説明がある。基本的にセクションのあつまり になっていて、各セクションには4バイトの名前がつけられる。セクションの列のあとに目次 がつく。目次ではセクション番号とそのサイズがセクションの順に並べてかかれている。 最後は trailer。マジック番号とセクション数がかかれている。

ocaml_main での処理
trailerを読む (attempt_open -> read_trailer)
セクション情報を読む (read_section_descriptors)
  exec_trailer の section_descriptor はファイルから読んだセクション情報を格納するための場所。ここは section_descriptor の配列がはいる。 section_descriptor はセクションの名前 4 byte とセクションサイズ (unsigned int 4 byte) からなる。(からって num_sections * 8 って直書きはちょっと。。。。。)
セクション情報を読み終った後は seek_section, read_section でセクションを読める。
まず seek_section でコードセクションにファイルの位置をあわせる。このときコードセクションのサイズは seek_section の返り値からわかる。
load_code でバイトコードを読み込む。
プリミティブ関数の読み込み? PRIM セクションを読んで build_primitive_table をよぶ
DATAセクション読み込み
  ファイルデスクリプタを Ocamlでのチャネルに変換。 Ocaml での値が読めるように (open_descriptor_in)
  input_val で値を読み込み global_data という変数にいれる
close_channelでチャネルを閉じる。fd も閉じられる。

attempt_open
read_section_descriptors
seek_section (fd, &trail, "CODE"); でコードサイズがわかる。。。
exec.h
まずはマジック番号、セクション数を書いたヘッダがある。

exec.hのコメントと同じだけどファイルフォーマット 
section1
section2
...
table_of_contents (toc)
  name_of_section1 size_of_section1
  name_of_section1 size_of_section1
  ...
trailer
  number_of_sections
  magic

attempt_open
  read_trailer
   lseek -TRAILER_SIZE, SEEK_END (= ファイルサイズ+オフセットの位置にオフセットをあわせる)
つまりtrailer は最後に書かれている
TRAILER_SIZE は 4 + 12 と定義されている。
4 .. num_sections (uint32 = unsigned int)
12 .. magic
seek_section -> seek_optional_section
  セクションの名前とサイズの配列が trailer.section にある。これを先頭から順に 読んで目的のセクションがでるまでサイズを足していき、オフセットを求める。目的のセクションの サイズを返す。セクションがなかった場合は -1 を返す。
read_section
  目的のセクションを読んでそのデーターを返す。データの最後は 0 で区切られる。 セクションのサイズ + 1 のバッファを確保。

作者: 増山隆 mail
To Home
Valid HTML 4.01!