発端は@dico_lequeさんのこのツイート そういえばOCamlでtype t = [ atom | `List of t list | `DottedList of t list * atom ]and atom = [ `Int of int | `Vector of t array ]みたいなのはThe type constructor atom is not yet completely definedになっ…

最近Bartosz MilewskiのCategory Theory for ProgrammersシリーズをYoutubeで観はじめた。メモとして記事にしておく。 第一シリーズは全10回、各回が前後篇にわかれている。 1.1回目： www.youtube.com 最初の回はプログラマにとっての圏論の意義とは？とい…

前回に続いてCPS変換の話。 前回はパーサから帰ってくるExp.t型のASTを同じExp.t型のCPS形式になっているASTに変換してからインタプリタに実行させていた。 インタプリタが（特にビルトイン関数について）関数の最終引数を継続だと認識するようになったので…

インタプリタ自作によってプログラミング言語の諸概念を学んでいく「Essentials of Programming Languages」の第5章、第6章はどちらも継続渡しスタイルについて語っている。 第5章は「インタプリタを継続渡しスタイルで書くとどうなるか」という話を掘り下げ…

もう一週間以上前になるが、Shibuya.lisp #86に続いて#87でもKontlangについて話してきた。 speakerdeck.com 内容としては kontlangの紹介 shift/resetのセマンティクスとkontlangにおける実装 マクロとモジュール shift/resetとマクロとモジュールを使ったm…

kontlang作成の一つの目標は、この資料を元に： モナドをつくろう from dico_leque www.slideshare.net モナドをつくれるようにしてみたい、というものだった。 結果的にMaybe、ListやStateモナドを「つくって」みたのだが。 そもそもこのつくったものは本当…

実装したモナドやmap、fold_leftなどの関数をライブラリ化することで毎回定義し直さなくても済むようにしたい。 その準備段階としてモジュールを実装する。（ファイルから読み込む場合もモジュールとして扱いたいため） 具体的には (module [...])という構文…

私は現在Visual Studio CodeでOCaml & Reason IDEを使っている。 全般的に非常に気に入っているのだが、一つ頻繁に起きて心をすこしだけささくれ立たせることがあるので書き出しておく。OCaml & Reason IDEプラグインはエラー検出などにmerlinを使っているの…

前回こう書いた： ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた 今回はその話。 reifyの型 Representing Monadsのreifyとreflectの型定義： signature RMONAD = sig structure M : MONAD val reflect : '1a M.t -> …

前回このように書いた： Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。 しかし「限定継続を使ってモナドを表現する」というアイデアの元となるRepresenting Monadsという論文を読み直していたらちゃんと…

shiftとresetを使ってStateモナドを実装する。ちなみに今まで実装したモナドの中で随一のややこしさである。 Stateモナドはその名のとおり、計算に局所的な「状態」を持たせることができるモナドである。状態とは「値を参照したり書き換えたりできる何か」を…

前回のMaybeモナドに続いて、非決定性を扱うためのListモナドをつくってみたい。 非決定性の説明に関してはSICPを参照してほしい： sicp.iijlab.net 前回と同じくreifyとreflect（実装内容は違うが）、そして今回新たにreturnを実装していく。 さらにreflect…

shiftとresetが実装できたのでそれらを使ってモナドっぽい機能を実装してみる。 手始めに以前も紹介したこの資料に出てくるMaybeモナド的なものを試してみたい： モナドをつくろう from dico_leque www.slideshare.net HaskellやOCamlでMaybeモナドといえばJ…

OCamlのFunctorは一般的なOOPにおけるClassに似ているところと似ていないところがあるぞい。 最近1000行ほどのOCamlコードを一から書く機会があって、その時いろいろとFunctorを使ってみたのだが、気付いたらOOPっぽいことをしていて「面白いなー」「本当に…

ついにshift / resetを実装するところまで到達！ resetで区切った限定継続をshiftで取り出して使う、という言語機能だ。 shift/resetプログラミング入門に出てくるような処理が実装できるようになる： (* (reset (+ 3 (shift [k] (* 5 (k 2))) -1)) 2) この…

「めざそう言語処理系の沼」の内容がようやく発表したところに追いついたので、遅ればせながら・・・ 5月28日のShibuya.lispがリモート開催されるということだったので、ひさしぶり（４年ぶりくらい・・・ 遠くに移ってしまったので・・・）に参加。 発表枠…

関数型言語の多くはループを再帰で、あるいは再帰を使った高等関数（mapやfold / reduceなど）で表現することが多い。 命令型プログラミングで使われるforやwhileループだと「ループごとに現在の変数環境で何かが変わっている必要がある」、つまり「状態に対…

ここまで実装してきたインタプリタは 式を表す文字列をパースし 評価して 結果の値を表す文字列を返していた。 もちろんそれで正しいのだが、インタプリタの中でどのような挙動になって式が値に変換されているのかがわかりにくい。 限定継続のようにかなり微…

簡単なマクロ機構を実装していく。 背景 shift/resetが実装されたらやってみたいことの一つが@dico_lequeさんの発表「モナドをつくろう」をいろいろ試してみること。 モナドをつくろう from dico_leque www.slideshare.net スライド１９に出てくるreifyがマ…

今まで作ってきた言語には副作用がなかったが、やはり入出力くらいはほしいよね、というわけで 式と値に文字列を追加 標準入出力からの読み取り・書き込みのための組み込み関数 副作用のある処理を順次実行して、最後の式の値をとるDo式 を言語に追加する。 …

今回の変更は三点： condによる条件分岐 Val.FnとVal.RecFnを統一 式の中の自由変数を検出するget_freeをリファクタ 前回とのコード差分： Comparing v0.10...v0.11 · zehnpaard/kontlang · GitHub condによる条件分岐 すでにifによる条件分岐は実装してある…

今回は言語で簡単なデータ構造を扱えるようにする。具体的にはイミュータブルなconsセル（とnil値）を導入して、linked listを作れるようにする。 ついでにLisperならお馴染みのcar、cdrやリストを便利に作れる・使えるlist、applyなども定義する。 こんな感…

今回は細かいところを調整しただけ。 前回との差分： Comparing v0.8...v0.9 · zehnpaard/kontlang · GitHub 調整ポイントは： レキシカル・スコープで関数作成時にクロージャに束縛する自由変数の重複を排除 Exp.Letsを評価する時、変数に束縛されるべき式…

普通の関数が実装できたので、今度は再帰関数を定義できるようにする。 具体的にはこのような構文： (letrec [factorial [n] (if (= 1 n) 1 (* n (factorial (- n 1))))] (factorial 6)) あるいは： (letrec [(odd? [x] (if (= 0 x) false (even? (- x 1))))…

前回実装したダイナミック・スコープの関数は、実装は楽だが使うにはけっこうピーキーである。より一般的なレキシカル・スコープに直すとする。 関数の定義を評価して「関数の値」を作成する時に、関数内に出てくる自由変数を検出して、定義時の変数環境でそ…

分岐や変数束縛が出来るようになったので、次は関数定義を追加したい。 機能としては： fnで無名関数を作成 letfnで関数を名前付きで作成（複数同時も可） 多引数に対応、引数の数が定義時と呼び出し時に合っていなかったらエラー 今回はダイナミック・スコ…

前回でようやくifで分岐ができるようになった。今回はletを使って変数を定義できるようにする。 こんな感じの式が評価できるようになる： (let [x 5] (+ x 6)) (let [(x 5) (y 6)] (+ x y)) Clojureっぽく[]が構文に現れるようにしてみた。複数の変数を同時…

前回までは言語で扱える値は整数値と組み込み関数だけだった。比較とか分岐とかしたいよね、ということで今回は真偽値を追加して、ifで分岐できるようにする。 以下のようなコードが書けるようにする： (if (and (>= 3 1 1) (< 0 3) false (<= 1 2 3 3 5)) 1…

前回継続渡しスタイルで末尾再帰化したインタプリタにさらに手を加えてトランポリン化する話。 一般的に、トランポリン化は「末尾再帰のない言語でスタックオーバーフローを起こさずに深い再帰をシミュレートする」手法だと言える。再帰的な関数呼び出しを遅…

前回に続いて、機能としては整数と四則演算だけのインタプリタの話。 今回は機能はそのままで、式を評価して値を返すeval関数を継続渡しスタイルに変換する。 そもそも継続渡しスタイルだと何が嬉しいのか。 インタプリタの実行手順を考えると、関数呼び出し…