Arantium Maestum

プログラミング、囲碁、読書の話題

OCaml

OCamlのlambda IRをいじる(代数的データ型)

代数型データ型とそれに対するパターンマッチのlambda IRへのコンパイルを見ていく タグのみ直和型 まずは簡単なタグのみ直和型を見てみる: type t = A | B | C let () = let x = C in match x with | A -> print_int 1 | B -> print_int 2 | C -> print_in…

OCamlのlambda IRをいじる(レコード)

レコード型を定義して使うコードがどのようにlambda IRにコンパイルされるかを見ていく。 定義して使う 簡単なレコード型を定義した上でa.xなどとアクセスして使ってみる: type t = { x : int; y : string } let () = let a = {x=1; y="hello"} in print_en…

OCamlのlambda IRをいじる(リスト)

リストとパターンマッチ、Listモジュール使用のコンパイルを見ていく。 簡単なパターンマッチ 簡単なリストを作り、リストのコンストラクタ2つに対しての素直なパターンマッチをする: let () = let xs = [1;2] in match xs with | [] -> print_endline "he…

OCamlのlambda IRをいじる(タプル)

タプルとそれに対するパターンマッチがどうlambda IRにコンパイルされるかを見ていく。 fst/snd まずは非常に簡単なタプルと、その値をfst/sndでアクセスするコード: let () = let x = (1,2) in print_int @@ (fst x) + (snd x) -dlambdaでコンパイル: (se…

OCamlのlambda IRをいじる(再帰関数)

再帰関数のことを忘れていた! というわけで幕間的な記事。 Factorial 再帰で階乗なコード: let () = let rec f x = if x = 0 then 1 else x * (f (x-1)) in print_int @@ f 5 -dlambdaでコンパイル: (seq (let (*match*/83 = (letrec (f/80 (function x/8…

OCamlのlambda IRをいじる(関数)

前回に続いて、ローカルとモジュールレベルでの関数定義がどうlambda IRにコンパイルされるかを見ていく。 ローカル関数 まずはこんな感じの簡単な関数: let () = let f x = x + 1 in print_int @@ f 5 ocamlopt -c -dlambda localfunc.mlなどとすると: (s…

OCamlのlambda IRをいじる(変数)

前回に続いて、モジュール内で変数を定義して使うプログラムがどのようなlambda IRにコンパイルされるかを見ていく。 ローカル変数1つ OCamlで変数を定義する場合、モジュールのトップレベルでの定義と、ある式の一部としてlet x = y in zのxのような定義の…

OCamlのlambda IRをいじる(はじめに)

OCamlのコンパイラの話題でよく聞くflambdaという最適化ステップについて資料を読んでいた: https://ocaml.org/meetings/ocaml/2013/slides/chambart.pdf スライド5にコンパイラの中間表現のステップと説明が書いてあったのが面白かった。 parse tree: AST…

OCamlのGADTでVariadic Function(Stack Overflowより)

このStack Overflow問答が大変面白かったのでメモ: stackoverflow.com サンプルコードは少し(自分にとっては)わかりやすいように変えてある。 何をしたいか 第一引数によって、それ以降幾つの引数をとるかが変化するような可変長引数関数を書きたい。 例…

OCaml Batteries IncludedのLazyList/Seq/Enumについて

OCamlの標準ライブラリは貧弱なことで知られている。 OCamlコミュニティの間でも「あれはOCamlコンパイラを書くためのライブラリだ」と言われていて、実際INRIAで必要最低限(つまりコンパイラを書くのに必要な分だけ)提供している側面がある。 基本的なデ…

OCamlで存在型を試してみた(その4ーーGADT)

ここまで zehnpaard.hatenablog.com zehnpaard.hatenablog.com zehnpaard.hatenablog.com とモジュール関連の機能で存在型を扱う話をしてきた。 しかし、OCamlでもっとも直接的に存在型をエンコードしたいならGADTが使える。 ダメな例 まずはうまくいかない…

OCamlで存在型を試してみた (その3ーーモジュール)

シリーズ前々回と前回に続いて存在型を探っていく。 今回はパラメトリックな機構はまったく使わないただのモジュールと存在型について。 第1級モジュールやファンクタによる抽象化機能と存在型について書いてきたが、型としての「存在型」はどちらの場合で…

OCamlで存在型を試してみた (その2ーーファンクタ)

zehnpaard.hatenablog.com の続き。 前回は第1級モジュールを非常に綺麗に存在型に対応させられることが示せた。 しかし第1級モジュールを使わずとも、OCamlだとモジュールのシグニチャ自体が存在型的だ。(ただし微妙だが重要な差異もある) 今回はファン…

OCamlで存在型を試してみた (その1ーー第1級モジュール)

Types and Programming Languagesの24章の主題は存在型(Existential Types)である。 私は何回読んでもここでつまづく。 この章に到達するまでに部分型やら再帰型やら型推論やら全称型やら出てくるが、まあ難しくとも、なんとなくどういった言語機能に関連…

モジュールシグニチャの多重継承

前回の記事で module type ADD = sig type t val add : t -> t -> t val to_string : t -> string (* ここ *) end のようなシグニチャを書いたが、書いていて「うーん、これはおかしいな」と思った。 MULでto_stringが必要だったからといってADDのインターフ…

Expression ProblemにおけるOOPと関数型の対比について

Expression Problemという計算機科学・ソフトウェア工学の世界でそれなりに有名な問題がある。 この記事がいい感じにまとめていると思う: eli.thegreenplace.net Imagine that we have a set of data types and a set of operations that act on these type…

OCamlProのOCaml Cheat Sheets

OCamlProのブログを過去に辿っていたらこういう記事を見つけた: www.ocamlpro.com OCamlの構文の1ページまとめと、標準ライブラリの2ページまとめ。(出たのは2019年9月) 流石に構文に関しては(Objects & Classes関連以外は)知らないところはなかった…

Robert Harperの型クラス批判

Robert Harperのブログに(10年くらい前に)載っていたHaskellの型クラスに対する批判について@elpin1alさんに教えていただいたのでメモ。@elpin1al ありがとうございます! 型クラスとモジュール 言語の抽象化機構の中心的存在は何かと考えると、Haskellな…

open recursionなモジュールに型定義を持たせる(下改)

open recursionの記事に関して、より良い書き方があることに気づいたので書き留めておく。 あっちの記事ではシグニチャ二つを定義していて、GT.t = GT.s greet、NT.t = NT.s named greetと、GT.t型とNT.t型の形が違っていた: module type NT = sig type s t…

let rec内での多相とlocally abstract typeとpolymorphic type constraints

こういう記事を最近読んだ: tatta.hatenadiary.org (書かれたのは10年以上前だが) こういうコードは型チェック通らないよ、という話: let rec f x = x and g () = f 1 and h () = f true;; Line 3, characters 13-17: Error: This expression has type b…

OCamlでGADTを試してみた

なんとなく幽霊型がわかったので、その勢いに乗ってGeneralized Algebraic Data Typesについても調べてみた。 OCamlの言語機能としては: caml.inria.fr OCaml 4.00から導入された(ちなみに2021/3で最新版は4.12)とのことで、リリーススケジュールを見てみ…

OCamlで幽霊型を試してみた

open recursionなモジュールに型定義を持たせる(下) - Arantium Maestum のシグニチャ(シグネチャが正しいのか)についての話で module type S = sig type 'a t = 'a list end module M = struct type 'a t = int list end 的なコードを書いて「型が合わ…

OCamlのモジュールシグニチャ隠蔽しすぎてしまいがち問題

最近のopen recursion関連記事を書いていてふと思い出したのがこちらの記事: camlspotter.hatenablog.com モジュールを使ったプログラミングではプログラマが情報を必要以上に減らしたモジュール型を書いてしまって 型の同値性が知らず知らずに失われてしま…

open recursionなモジュールに型定義を持たせる(下)

ようやくopen recursion関連の話もひと段落になる(予定)。それなりにしっかりOOP継承っぽい機能を実装する。 前回の記事では module GreetF(Self : GT) : GT with type t = Self.t and type ctor = Self.ctor = struct include Self let addressee _t = "w…

open recursionなモジュールに型定義を持たせる(中)

今回は今まで散々参考にしてきたこの記事の内容に近い形でopen recursionを実装してみる: blag.bcc32.com 題材もまったく同一なのでパクリと言われても仕方ない・・・ 前回までの記事の内容を踏まえて少し整理したり、スタイルをいじったりしてあるくらい。…

open recursionなモジュールに型定義を持たせる(上)

前回はこちらの記事の内容を非常に簡略化した実装を探ってみた: blag.bcc32.com 最大の簡略化ポイントはモジュール内でtype t = ...のような型定義がなされないところで、それによっていろいろなところでモジュール間の型の整合性を満たすための制約を明示…

OCamlでも(オブジェクトもrefも使わずに)Open Recursionしたい!!・・・したい??

前回の記事をツイートしたら@dico_lequeさんからこういう話を教えていただいた: 多相バリアントでのやり方を考えるとファンクタ経由で非再帰で書いておいてmodule rec M = F(M)みたいな、と思ってググったところOpen Recursion with Modules | bcc32https:/…

OCamlでも(オブジェクト使わずに)Open Recursionしたい!・・・したい?

タイトルからも察していただいた方も多いと思うが、実用的な話はしません。あくまで「open recursionってなんだっけ」「こんな感じの開かれた再帰をOCamlで書いてみよう」という趣旨です。 Open Recursionってなんだ? ソフトウェアデザイン誌の2021年3月号…

TaPLの公式実装をduneでビルドする時にハマったこと

非常に限定された一部界隈では非常に有名なことで有名なTypes and Programming Languagesの公式サイトから、本に出てくる型システムの実装がダウンロードできる: www.cis.upenn.edu 以前も気になった部分を落として実装を覗いてみたりはしたのだが、コンパ…

js_of_ocamlでocamllex/menhir製パーサをJSにコンパイルする

私は趣味の言語処理系実装でocamllex/menhirというパーサジェネレータにお世話になることが多い。(このブログの過去記事を参照) js_of_ocamlは基本的にFFIを使わないライブラリだったらJavaScriptにコンパイルしてくれるはずなので、ブラウザでパーサが使…