Arantium Maestum

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

2019-01-01から1年間の記事一覧

型クラスのある言語の実装に向けて:その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…

OCaml4.08のmonadic/applicative let/andについて

OCaml4.08でシンタックスシュガーとしてlet*、let+、and+などの構文が新たに導入された。 詳細については jobjo.github.io がわかりやすかった。 直接モナドやApplicativeをサポートする構文というよりは、 let (let*) x f = g x f などと好きに定義すれば l…

型推論を実装する その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で使う型は以…

型推論を実装する その1 (型なしの言語を作る)

Oleg先生のサイトのhttps://t.co/7F4vsWGgr7とhttps://t.co/ABdXWoAxcWをちゃんと読みたいと思っている・・・ 現在外堀を埋めている段階・・・— zehnpaard (@zehnpaard) June 23, 2019 とあるように、最近型推論や型クラスに興味があり、界隈では非常に著名…

OCamlで48 Hour Schemeをやってみる その5 (第九、十章)

Write Yourself a Scheme in 48 Hoursの最後の二章をやっていく。入出力と標準ライブラリ作成。 第九章:入出力 stdin, stdoutやファイルに対する入出力を実装する。 github.com 例によって「Haskellだとモナドが出現していろいろ型を頑張らないといけないけ…

OCamlで48 Hour Schemeをやってみる その4 (第六〜八章)

前回から続いて、REPL機能を追加し、変数と関数を定義できるようにする。 第四章: REPL REPLとはRead Eval Print Loopの略で、対話的にプログラムを入力・実行できる環境である。 この場合は Lisp>>> などといったプロンプトを表示してS式を受け取り、評価…

OCamlで48 Hour Schemeをやってみる その3 (第四章、五章)

第四章:エラーハンドリング 第四章の主眼はエラーハンドリング。 Haskellだとモナドでやるのが正しい作法なようで、型チェックの恩恵に与れる。その反面、一章を割いていろんな関数の実装と型注釈を変更していく必要がある。 OCamlだと例外を投げればいいの…

OCamlで48 Hour Schemeをやってみる その2 (第三章後半)

前回から続いて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 _ …

OCamlで48 Hour Schemeをやってみる その1 (第一章〜第三章前半まで)

こういうことを言ってしまった: これは宗教勧誘とかじゃなくて真面目に言うんですが、Lisp(処理系)ってある程度書けるようになるまでの学習コストがとても(?)低い。 https://t.co/OQPte4lm4I— zehnpaard (@zehnpaard) June 14, 2019 発言に責任を持つため…

let多相と型制約と型推論

こういう(けっこう前の)記事があって面白かった: no-maddojp.hatenablog.com 大変面白かったのと、何故こうなるのかが微妙に理解し切れなかったのと、で少し自分でも調べてみた。 ちょっと例を簡略化すると let f x = x in f 1, f true は型検査を通るけ…

ocamllexのlexerとmenhirのparserの間に任意のOCamlコードによる変換を挿入する

OCamlでパーサを書く場合 lexerをocamllexで書く そのlexerを受け取るparserをmenhirで書く というのが最近の鉄板のようだ。 let lexbuf = Lexing.from_channel stdin in let exp = Parser.f Lexer.f lexbuf in print (eval exp) というような流れ。 ocamlle…

OCamlで相互再帰な型を二つのModuleにわける方法二つ

Essentials of Programming LanguageをOCamlで実装するのをぼちぼちとすすめている。 前回LETを実装した時「式を評価した結果の値」を表す型とその型に対する関数を集めたValと「変数とそれに対応する値の対応関係を保持する環境」のモジュールEnvを作った。…

EoPLのLetlangをocamllex/menhir/duneで実装してみた

前回の記事の構成に従って、簡単な言語のインタプリタを実装してみた。 Essentials of Programming Languagesという本の最初に出てくるLETという言語で、機能としては整数値の引き算、0チェック、if式による分岐、let式による変数束縛。関数定義などはできな…

OCamlで言語処理系覚え書き ocamllex/menhirパーサをduneでビルドする

OCamlでocamllexとmenhirを使ったパーサを書き、duneでビルドする場合の構成を調べていて、ようやく少しわかってきたので備忘録的に書き留めておく。 例として整数のたし算をパースして評価する非常に簡単な計算プログラムを実装する。 ディレクトリ構成 . ├…

lambda関数だけのPython世界で四則演算

お察しかもしれないがラムダ計算についての話である。 最近あったPyConで気になるチュートリアルがあった: www.youtube.com このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、 Pythonのlambdaキーワードで作る無名関数…

AtCoder Beginners SelectionをOCamlで(後編)

OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた atcoder.jp 今回は最後の2問、白昼夢 / DaydreamとTravellingの解法とOCamlを使った所感。 ABC049C - 白昼夢 / Daydream atcoder.jp ある文字列が、"dream", "erase", "dream…

AtCoder Beginners SelectionをOCamlで(中編)

OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた atcoder.jp (この記事はSome Sums, Card Game for Two, Kagamimochi, Otoshidamaの4問について) ABC083B - Some Sums atcoder.jp 0~Nまでの数で、各桁の合計がa以上b以下に…

AtCoder Beginners SelectionをOCamlで(前編)

OCamlでAtCoderをやってみたいなーと考えている。 以前DP問題を解いてみたこともあったように、親和性は高いように思う。 具体的には、関数型・命令型どちらでも表現力が高く、実行過程の予想がつきやすく、コンパイルされるので早い、という利点がある。い…

Concepts, Techniques and Models of Computer Programmingを読みはじめた

過去何回かぱらっとめくったくらいで置いておいたConcepts, Techniques and Models of Computer Programmingという本を去年の終わりあたりに少し真面目に読み始めた。 なぜか時々「ポストSICP」と言われる本で、CSの根幹部分の一つを書き表した大作・名著で…

自作言語Xemono

去年の終わり頃からReason MLよろしくOCamlのシンタックスをいじった言語の仕様を考えている。 github.com 今のところ新規性はまったくなく、OCamlと100%互換性がある言語仕様を目指している。(ただし今のところオブジェクト関連の機能についてはまったくノ…