GCamlというOCamlにオーバーロード機能を追加した言語あるが、それの型推論機構をうまく使って、論理プログラミングっぽいことができないかと試行錯誤してみた。まずは基本的な定数項を型として定義する。 type hanako = Hanako;; type taro = Taro;; type i…

flexといっても，adobeのやつではなく，スキャナージェネレータの方．以下のようにflexの-Sオプションでオリジナルのスケルトンファイルを指定することで，生成ファイルをいろいろと調整することができる．応用例としては，Linuxのkernel moduleに組み込むた…

OCamlのHashtblは，(=)演算子による構造比較なのに気がつかなくて，はまってしまった． # let key = ref 0;; val key = int ref {contents = 0} # Hashtbl.add tbl key ();; - : unit = () # Hashtbl.mem tbl key;; - : bool = true # key := 1;; // <-- key…

以下のようなヴァリアント型を定義する． type term_ = | Lit of int | Inc of term_ | IsZ of term_ | If of term_ * term_ * term_ | Pair of term_ * term_ | Fst of term_ | Snd of term_ type 'a term = term_ そして，これらのコンストラクタ用の関数…

OCamlで，let recで定義した多相関数は，束縛の右辺では多相にならないことに気がついた． let rec id x = x and y () = id 0 and z () = id true;; ^^^^intでないのでエラーになる

カリー化された関数opとそれに適用する引数をリストで受け取り1つずつ適用するようなexpand_args関数を以下のように定義する． let rec expand_args op args = match args with [] -> op | v::rest -> expand_args (op v) rest以下のように使いたい． # expa…

OCamlの2項演算子の評価順序は右から左だった． # let x = ref 3 in (let () = x := 5 in !x) + !x;; - : int = 8 # let x = ref 3 in !x + (let () = x := 5 in !x);; - : int = 10 関数の引数の評価順序も同様 # let f x y = x + y;; val f : int -> int -…

自然意味論によってTclのセマンティクスを定義してみることにする． Tclの構文 まず，抽象構文を以下のように定義する． C ::= W W* | C ; C W ::= V | [ C ] | { C } V ::= s | x | $x s ∈ Str x ∈ Var sは文字列を表し，xは変数を表すメタ変数である．Tcl…

CormenのIntroduction to Algorithmsには，グラフGと有向辺を逆にしたG_revに対してそれぞれDFSする方法が紹介されている．これは，わかりやすいアルゴリズムではあるのだけれど，逆グラフを求める必要があるのが玉にキズである．一方，SedgewickのAlgorithm…

CPSからDS(Direct Style)の関数を呼び出すのは，以下のように何の問題もなくできる． fun f_cps(k, x) = let t = g_ds(x) in ... (k t) // リターン ではその逆はどうか？ DSの関数は，現在の継続を明示的にパラメータとして渡されていないので，呼び出した…

値としてのラベル GCCはいろいろな独自拡張があるけど，その1つにラベルの指すアドレスを値として取得する機能がある． void *address = &&label; ... label: ... goto *address;のように&&演算子をラベル名の前に付けると，そのラベルのアドレスを取り出す…

CPS変換の手法にもいろいろある．前提として，λ式は以下のような構文で定義されているとする． M, N ::= x | λx.M | M N CPS(継続渡し形式)とは，計算が行われる順序を明示するために，ある式の計算結果を，残りの計算を表す継続（途中結果を受け取り，残り…

KL1とかGHC、FlengはCommitted-Choice型の言語と呼ばれている。 並行論理型言語の一種なのだが、どうして、Committed-Choiceと呼ばれるのかが やっとわかった。 そこで KL1 では, どの公理を選ぶかを決めたら決して後戻りしない方針をとった. そのかわり, ど…