Arantium Maestum

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

言語処理系

CPS変換はじめてみた

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その22 モジュール

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その21 やはり俺のListモナドはまちがっている。

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その20 Stateモナドとreflect

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その19 shift/resetでつくるStateモナド

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その18 shift/resetでつくるListモナド

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その17 shift/resetでつくるMaybeモナド

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その16 shift/reset

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

Shibuya.lisp #86 でKontlangについて発表した

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その15 末尾呼び出し最適化

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その14 ステップ実行インタプリタ

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その13 マクロ

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その12 文字列、入出力とDo

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その11 Cond&リファクタリング

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その10 Consとリスト

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その9 微調整

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その8 再帰

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その7 関数(レキシカル・スコープ)

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その6 関数(ダイナミック・スコープ)

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その5 変数とlet

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その4 真偽値

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その3 トランポリン化

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その2 継続渡しスタイル

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その1 四則演算

shift/resetという限定継続を扱うための機構を備えた言語のインタプリタをOCamlで段階的に作っていく。長めのシリーズになりそう。 今回は整数と関連する演算が評価できるインタプリタを作成するまで。EoPLの最初の言語であるLETの二歩くらい手前。 例えば:…

型クラスのある言語の実装に向けて:その1(何が必要かを考える)

つらつらと「型クラスのある自作言語の処理系を作りたいなー」と考えている。 実用性は度外視で、ある程度型クラスの雰囲気さえ味わえればいい。 Essentials of Programming LanguagesのINFERRED言語を以前実装した: zehnpaard.hatenablog.com 再帰関数くら…

Monadic Parser実装を通して近付く「モナドのお気持ち」

OCamlでMonadic Parserを作ってみる 前編・後編で書ききれなかったポエム的なもの。さきにそちらを読んでもらえればわかりやすいかと思う。 HaskellのTypeclassopediaに The wise student will focus their attention on definitions and examples, without …

OCamlでMonadic Parserを作ってみる(後編)

前回に続いてMonadic Parser Combinatorを実装していく。 再帰 OCamlのような先行評価の言語でMonadic Parserの定義に再帰を使うと問題になる場合とならない場合があるぞい。 問題にならない場合: let match_string s = let rec f = function [] -> pure []…

OCamlでMonadic Parserを作ってみる(前編)

OCaml 4.08でmonadic/applicative letの構文が入ったことだし、これを使ってみよう、ということでHaskellのParsecのようなMonadic Parser Combinatorが作れるか試してみた。 具体的にはGraham HuttonのProgramming in Haskellの13章にあたる「Monadic parsin…

型推論を実装する その3 (型推論のある言語を作る)

型なしのLETREC、型検査のCHECKEDときて、ついに型推論ができるINFERREDの実装に移る。 github.com 言語仕様の変更 前回のCHECKEDでは letrec int double(x : int) = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2)) in (double 6) のように関数の仮…

型推論を実装する その2 (型検査のある言語を作る)

前回登場したLETREC言語に型注釈と型検査をつけたCHECKED言語を実装する。 github.com 具体的には無名関数を定義するprocの仮引数、再帰関数を定義するletrecの仮引数と戻り値に対して型注釈を必要とし、その情報を元に型検査する。 型 CHECKEDで使う型は以…