Arantium Maestum

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

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%互換性がある言語仕様を目指している。(ただし今のところオブジェクト関連の機能についてはまったくノ…

100 Days of Codeをやってみた

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。 100 Days Of Code概要 ルールは簡単: なるべく毎日1時間以上、業務外のコードを書く github…

SECDマシンとLispあれこれ

時には昔の話をしようか、ということでPeter LandinのSECDマシンについて。Lisp Advent Calendar 2018 23日目の記事。 はじめに 最近、長らく積読してたThe Architecture of Symbolic Computersという本を読んでいる。 There is a revolution looming in com…

PythonでForth処理系を書く! その7(繰り返し処理 DO-LOOP)

繰り返し処理を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも書いた通り、この構文の要素は3つあって: DOでスタックに乗っている二つの整数を分岐のために使う スタックから得たはじめの整数がループカウンタの…

PythonでForth処理系を書く! その6(条件分岐 IF-ELSE-THEN)

条件分岐を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。 上記の記事からの再掲になるが、このような構文で: 1 IF 2 ELSE …

PythonでForth処理系を書く! その5(Read-Eval-Print-Loop)

REPL機能を実装する。 main.pyに引数がなければREPLを実行するようにする(引数としてファイル名が渡されていればそのファイルを実行)。REPLは一行ずつユーザからForthコードを受け取り、今まで受け取ったコードの環境を引き継ぎつつ実行する。 github.com …

PythonでForth処理系を書く! その4(内部状態をPython Dictionaryに保存)

前回の終わりで書いたように、Forth処理系の内部状態、とくにコンパイラ部分とインタプリタ部分のものをデータ構造として抜き出して、保存・出力できるようにしたい。 その変更がこれ: github.com 主要な変更は二点: 内部状態をPythonのDictionaryで表し、…

PythonでForth処理系を書く! その3(最低限の機能)

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestum でも書いた通り、まずは以下の機能を最低限として実装する: 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数…