Arantium Maestum

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

OCaml

mapの表現力

最近考えるきっかけがあったので書いておく。 一般的にmapやfoldは再帰を使って実装でき、そして再帰に比べて制約がかかっていて表現力が落ちるとされている。むしろその制約があるからこそそのコードの「何をしたくて何をしないか」という意図が明確になる…

OCaml Effects Tutorialの演習「Async/await」をやってみる

OCaml 5.0にeffect handlerが入った理由の一つである、並行処理をdirect styleで記述できるasync/awaitの実装をやってみる。 この演習: github.com 演習用のコード・サンプルはこれ: github.com Schedulerのインタフェース この演習ではasync/awaitといっ…

Effect Handlerで相互再帰を分割するコードの変遷

前回の記事で書かれたコードに到達するまで、いくつかのアプローチで漸進的に単純化されていったのでその経緯についても書いておく。 第一案 そもそも「相互再帰を分割するサンプルコードを書こう」と思い立ったのはComposable Interpreterで使った「すべて…

Effect Handlerで相互再帰を分割する

タイトルどおり、OCaml 5.0のeffect handlerを使って相互再帰的な関数を分割して別々に定義できるようにする。 相互再帰な処理 ベタだが今回はis_oddとis_evenという相互再帰な関数を例にとる: let rec is_odd n = if n=0 then false else is_even (n-1) an…

Effect Handler、Extensible Interpreter、Expression Problem

前回の記事に書いたとおり、今回はこのExtensible Interpreterの枠組みを使うとExpression Problemを解決できるということを見ていく。 Expression Problem Expression Problemについては以前この記事で書いた: zehnpaard.hatenablog.com かいつまんで説明…

OCaml 5.0のEffect HandlersでComposable Interpreter

前回のコードをベースに「任意のExtensionハンドラを変更なしで組み合わせて作る」Composable Interpreterを実装する。 問題 前回のコードの何がComposabilityを阻害していたかというとインタプリタを拡張するハンドラが、拡張前のインタプリタ関数を使って…

OCaml 5.0のEffect HandlersでExtensible Interpreter 続

前回「任意のハンドラを組み合わせてインタプリタを作るといったComposabilityも持たせることができる」と書いた。今回はそのComposable Interpreter実装への準備段階として、前回のコードをリファクタしてeval関数とeffect handlerをある程度分離した形にす…

OCaml 5.0のEffect HandlersでExtensible Interpreter

ツイッターでOCamlのEffect Handlerの話題を漁っていたらこのようなツイートを見つけた: Algebraic Effects (Multicore OCaml)を使ってExtensible Interpreterを実装する例:https://t.co/b1Tu4pys6dポイントはeffect handlerにcontinuationが渡ってくる (=…

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる3

前回の終わりに書いた通り、Effect.Shallowを使って「generatorが作成されてまだ要素を返していない」状態を特殊ケース化せずに処理できるようにする。 今回のコード type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit type 'elt ge…

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる2

前回に続いてOCaml Effects TutorialのGenerators from Iteratorsをやっていく。 前回のコード 前回のコードを再掲する: type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit type 'elt generator = unit -> 'elt option let generat…

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる1

OCaml Effects Tutorialの演習問題として、任意のcontainerとそれに対するiteratorからgeneratorを作成する関数を実装してみる。 github.com エフェクトハンドラが受け取る限定継続を直ちに使用あるいは破棄してきた今までの例と違って、「限定継続を一旦保…

Effect.Deepで書かれたResumable ExceptionをEffect.Shallowで書き直す

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

OCamlのlocally abstract typeに関するメモ2 (構文)

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

OCaml Effects Tutorialの演習「StateのHistory実装」をやってみる

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

OCaml Effects Tutorialの演習「StateのPut実装」をやってみる

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

OCamlのlocally abstract typeに関するメモ1 (基本的な疑問)

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

OCaml Effects Tutorialの例題「Stateの実装」を追ってみる

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

OCaml Effects Tutorialの第一演習「Exceptionの再実装」をやってみる2

前回の締めで書いたとおり、以下の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の第一演習「Exceptionの再実装」をやってみる1

前回に続いて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. …

OCaml 5.0のEffect Handlerのチュートリアルをやりはじめた

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

TIL: OCamlで再帰とlet多相

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

wamlのコードを読んでる

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

再帰型の実装に関して悩んでいること2 equi-recursive対iso-recursive

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

再帰型の実装に関して悩んでいること1 再帰する型変数の表現

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

wasm GC Proposalのために作られた実験的な関数型言語処理系Wamlが面白そう

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

型システム実装幕間2 unifyとoccurs check、adjust levelについて

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

型システム実装幕間1 各種matchヘルパ関数について

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

Hindley Milner型推論に機能を追加していく13 Listの追加(後編)

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

Hindley Milner型推論に機能を追加していく12 Listの追加(前編)

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

Hindley Milner型推論に機能を追加していく11 Refの追加(後編)

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