言語処理系
前回のMaybeモナドに続いて、非決定性を扱うためのListモナドをつくってみたい。 非決定性の説明に関してはSICPを参照してほしい： sicp.iijlab.net 前回と同じくreifyとreflect（実装内容は違うが）、そして今回新たにreturnを実装していく。 さらにreflect…
shiftとresetが実装できたのでそれらを使ってモナドっぽい機能を実装してみる。 手始めに以前も紹介したこの資料に出てくるMaybeモナド的なものを試してみたい： モナドをつくろう from dico_leque www.slideshare.net HaskellやOCamlでMaybeモナドといえばJ…
ついに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関数を継続渡しスタイルに変換する。 そもそも継続渡しスタイルだと何が嬉しいのか。 インタプリタの実行手順を考えると、関数呼び出し…
shift/resetという限定継続を扱うための機構を備えた言語のインタプリタをOCamlで段階的に作っていく。長めのシリーズになりそう。 今回は整数と関連する演算が評価できるインタプリタを作成するまで。EoPLの最初の言語であるLETの二歩くらい手前。 例えば：…
つらつらと「型クラスのある自作言語の処理系を作りたいなー」と考えている。 実用性は度外視で、ある程度型クラスの雰囲気さえ味わえればいい。 Essentials of Programming LanguagesのINFERRED言語を以前実装した： zehnpaard.hatenablog.com 再帰関数くら…
OCamlでMonadic Parserを作ってみる 前編・後編で書ききれなかったポエム的なもの。さきにそちらを読んでもらえればわかりやすいかと思う。 HaskellのTypeclassopediaに The wise student will focus their attention on definitions and examples, without …
前回に続いてMonadic Parser Combinatorを実装していく。 再帰 OCamlのような先行評価の言語でMonadic Parserの定義に再帰を使うと問題になる場合とならない場合があるぞい。 問題にならない場合： let match_string s = let rec f = function [] -> pure []…
OCaml 4.08でmonadic/applicative letの構文が入ったことだし、これを使ってみよう、ということでHaskellのParsecのようなMonadic Parser Combinatorが作れるか試してみた。 具体的にはGraham HuttonのProgramming in Haskellの13章にあたる「Monadic parsin…
型なしの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) のように関数の仮…
前回登場したLETREC言語に型注釈と型検査をつけたCHECKED言語を実装する。 github.com 具体的には無名関数を定義するprocの仮引数、再帰関数を定義するletrecの仮引数と戻り値に対して型注釈を必要とし、その情報を元に型検査する。 型 CHECKEDで使う型は以…
Oleg先生のサイトのhttps://t.co/7F4vsWGgr7とhttps://t.co/ABdXWoAxcWをちゃんと読みたいと思っている・・・ 現在外堀を埋めている段階・・・— zehnpaard (@zehnpaard) June 23, 2019 とあるように、最近型推論や型クラスに興味があり、界隈では非常に著名…
Write Yourself a Scheme in 48 Hoursの最後の二章をやっていく。入出力と標準ライブラリ作成。 第九章：入出力 stdin, stdoutやファイルに対する入出力を実装する。 github.com 例によって「Haskellだとモナドが出現していろいろ型を頑張らないといけないけ…
前回から続いて、REPL機能を追加し、変数と関数を定義できるようにする。 第四章： REPL REPLとはRead Eval Print Loopの略で、対話的にプログラムを入力・実行できる環境である。 この場合は Lisp>>> などといったプロンプトを表示してS式を受け取り、評価…
第四章：エラーハンドリング 第四章の主眼はエラーハンドリング。 Haskellだとモナドでやるのが正しい作法なようで、型チェックの恩恵に与れる。その反面、一章を割いていろんな関数の実装と型注釈を変更していく必要がある。 OCamlだと例外を投げればいいの…
前回から続いてWrite Yourself a Scheme in 48 Hours第三章。 primitive関数適用の評価まで実装する。 github.com src/eval.mlというモジュールを新たに作った。 open Exp (* 省略 *) let rec f e = match e with | String _ -> e | Number _ -> e | Bool _ …
