OCaml 5.0のeffect handler機能はStandard Libraryに入っているEffectというモジュールを通して扱う。 このEffectというモジュールにはEffect.DeepとEffect.Shallowという二つのサブモジュールがあり、ほとんどの機能はこれらサブモジュールに入っている。 …

Locally abstract typeについてメモを続けていく。今回は構文について。 locally abstract typeに関する構文は４つある。そのうち３つは糖衣構文と言っていい。 基本構文 まず一番基本の構文 fun (type a) -> e ぱっと見では関数式のように見えるが、上記の…

前回に続いてState関連の演習問題を解いていく。 github.com 問題 今回は今までのStateの履歴をリストとして返すHistoryエフェクトの実装。 まずはSTATEシグニチャに追加： module type STATE = sig type t val get : unit -> t val put : t -> unit val his…

前回見たStateの実装はGetのみで、どちらかというとHaskellのReaderモナドに近いものだった。 Stateを更新するPutと、過去のStateの履歴を見るHistoryの実装が演習問題として提示されている： github.com 問題 今回はStateを更新する機能としてPutの追加をや…

「EffectでState実装」の記事で何故Stateエフェクトのためにpolymorphic locally abstract typeが使われる必要があったのかを掘り下げたいと書いた。それに関して@dico_lequeさんからこのようにご教示いただいた（ありがとうございます！）： loopの型が再帰…

OCaml Effect TutorialのStateの実装の話を見ていく。これはEffect.DeepとEffect.Shallowの違いを紹介するセクションの例題： github.com 実際に示されているコードはHaskellでいうところのReaderモナドに似たもので、Stateを読むGetは定義されているがPutは…

前回の締めで書いたとおり、以下のException再実装は結果こそ期待通りに返ってくるものの、内容的には不満が残る： open Effect open Effect.Deep type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = perform (Raise_excep…

前回に続いてOCaml Effects Tutorialをやっていく。 問題 github.com Exercise 1: Implement exceptions from effects ★☆☆☆☆ As mentioned before, effects generalise exceptions. Exceptions handlers are effect handlers that ignore the continuation. …

12月16日にOCaml 5.0が正式にリリースされた。 目玉機能としてはMulticoreサポートで、以前はPythonなどと同じくGlobal Interpreter Lockがあって複数スレッドでCPUバウンドな計算が同時に実行できなかったのを、ガベージコレクタをはじめとしたランタイムの…

これは相互再帰ではないですが、let main = id(3);let id(n) = n;のようなプログラムの時に、main: Int -> Int, id: a -> aと型推論したいのですが、現在(単相型推論)の場合構文解析時にトップレベルで定義された変数名を記録しておいて、型推論時に予め型環…

言語実装 Advent Calendar 2022の１日目の記事として書いた。 Lisp Advent Calendar 2022でも枠が空いていたのでダブル投稿。 プログラミング言語を実装してみたい！と思ったらまずは簡単なLispインタプリタから始めるというのは一つの王道だと思う。 複雑な…

今年の大河で出てきた源仲章が源姓なのに明らかに公家＆いわゆる源平合戦の源氏とは別な描写だった。 武家ではない公家な源氏というのは百人一首に選ばれた歌人として源融、源兼昌がいるし、さらにフィクションでは源氏物語の光源氏もいるわけだが、どういう…

wamlのコードを読んでいて let rec enforce inf (p : pred) = function ... | Bool | Byte | Text when p <= Eq -> () のようなコードに行き当たった。predというのは type pred = Any | Eq | Ord | Num のように定義されている。つまり普通のバリアントだ。…

Andreas RossbergがwebassemblyのGC proposalを試すために作ったミニML言語waml。以下の記事で紹介した： zehnpaard.hatenablog.com それからもちょこちょこと眺めていたのだが、 考えれば考えるほどwamlは(wasmとは関係なく)すごいな。正格評価なラムダ計算…

TaPLを読むと再帰型の理論と実装について、equi-recursiveとiso-recursiveという二つの流儀があると書いてある。 equi-とiso-については以下の記事でも少し触れた： zehnpaard.hatenablog.com しかし実際どういう違いなのかをメモった上でどちらにするのかを…

型システムにどうやって再帰型を追加するかで悩んで手が止まっている。何に悩んでいるのかを書き出して整理していきたい。 今回は「現在、型そのものをtyというバリアント型で表現しているが、その枠組みで再帰型をどう表現するか」について。 そもそも再帰…

自分で実装している型システムに再帰型をつけたくてiso-recursive typesで検索していたらwasm garbage collectorのGitHubレポジトリで行われている侃侃諤諤な議論を見つけて読み漁っていた。 その中で見つけたのがwasmの中心的な人物であるAndreas Rossberg…

match_fun_tyなどのヘルパ関数をなくす是非を考えていて「型変数を新しく作成して使うコストは低いのだから（破壊的代入でリンクをアップデートしてるので管理する型変数の数が増えても処理が重くならない）、match_fun_tyなどでパターンマッチせずTArrow(tv…

再帰型についてTaPLなどを読み返していて、ようやく再帰型の「2大流派」であるisorecursiveとequirecursiveの違いなどがわかってきた。調べている間にOCamlコンパイラの-rectypesというフラグについて知ったのでメモ。 OCaml（そしてほとんどの関数型プログ…

ここまで実装した型システムではコアな部分であるtypeofの中で使うヘルパ関数として５つmatch_..._tyという名前の関数を定義している： match_fun_ty match_tuple_ty match_rec_ty match_ref_ty match_list_ty これらは元々効率的なHM型推論のお手本として使…

前回に続いてList追加の実装を見ていく。今回はtypeofで使われるヘルパ関数について。 match_list_ty 前回見ていったtypeof関数で新しく使われたmatch_list_tyは「tyをとりリスト型と単一化させた上でそのリスト型が保持している型を返す」という関数。EHead…

前回「次は再帰型を追加する」と書いたが、その前振りとして関連しているがより簡単な「言語機能としてリスト型を提供する」をまずやっていく。 OCamlでユーザがリスト型を定義するなら： type 'a list = Nil | Cons of 'a * 'a list このように代数的データ…

第二次世界大戦以前に不透明な金融やM＆A戦略により世界的なマッチ帝国を築き、世界恐慌で全てを失った人物について知ったのでメモ スウェーデン富豪イーヴァル・クルーガーが一時期世界のマッチ生産の７５％を握り、世界各国でマッチの独占供給権を持ってい…

前回書いたとおり、Let多相とRefとパラメトリックな型を組み合わせても型安全性が維持されるためには、Letで型が全称化される対象の式を制限する必要があり、これをvalue restrictionと呼ぶ。 残念ながらこの「全称化される式」であるsimple valuesのリスト…

このツイートで知った： Gitで差分がなくても空コミット作ることができるのはじめて知った。今までプッシュでのCI/CDやり直したい時、適当にリファクタリングしていたりしてたんだけど必要なかったみたい。https://t.co/VkQDcEnJUz— いぐぞー！！ ✈️ 旅する…

こんな記事を読んだ： simonwillison.net 「ブログを書くススメ」的な記事で、その中で勧められている「Today I Learned」がよさそうだったので真似したい。 言ってしまえば日々知ったふとしたことをメモるまさに備忘録な小記事なわけで、そんなに大発見なわ…

前回の終わりに 前述のとおり今回のコードはRefとLet多相の関係により型安全ではない。 と書いた。 しかしよくよく考えてみると、現在実装した型システムだと機能がギリギリなところで弱く、Let多相とRef型があるにもかかわらず型安全性は保たれている、よう…

Ref型とそれに関係した式の処理を追加する。 この記事で（HM型推論なしで）追加したものと同じ： zehnpaard.hatenablog.com ref型を作るためのオペレータref（ここら辺OCamlだと型とオペレータの名前が被ったりしてややこしい）、ref型からデータを取り出すd…

ツイッターで型コンストラクタが型かどうか？という話があり、ツイートで少し書いたのだがもうちょっとまとめてみる。 TaPLにおける定義 型コンストラクタと型はまったく同じ概念を指す言葉である 型はカインドを持つ カインド*の型を真の型と呼び、これらは…

再帰関数を定義するためのFixオペレータを言語に追加する。 型推論なしで追加した時の記事はこれ： zehnpaard.hatenablog.com Fixの使い方などはこの記事を参照してほしい。 今回のコードはここ 型 型には変更なし。 式 Fix式を追加： type exp = ... | EFix…