Arantium Maestum

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

言語処理系

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

型推論を実装する その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 発言に責任を持つため…

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

自作言語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 でも書いた通り、まずは以下の機能を最低限として実装する: 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数…

PythonでForth処理系を書く! その2(実装する機能)

処理系で実装する機能を列挙してみる。 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数をひとつとり、その数を標準出力に表示する 標準出力に改行を表示する REPL機能 分岐構文 IF-ELS…

PythonでForth処理系を書く! その1(序)

Forthというプログラミング言語がある。分類としては「スタックマシン型言語」になるだろう。 スタックマシンというのは、データやアドレスをスタックに乗せたり取り出したりすることを基本の操作とするプログラム実行モデルで、有名どころでいうとJava Virt…

HaskellでLisp to LLVM IRコンパイラ その5 ( LispValの定義、パーサ作成とSSA中間言語への変換)

LispValという再帰的なデータ型を定義して、まずコードをそのLispValとしてパースする。流れはインタプリタを作った時とまったく同じ。 インタプリタの場合はそこでevalを適用したが、コンパイラの場合はそこからSSA中間言語に変換を加えていく。 LispVal型 …

HaskellでLisp to LLVM IRコンパイラ その4 (SSA中間言語)

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。 その中間言語の各行を表現するデータ型がこれ: data SSA = Alloc String | Store String String | Load String String Lispと違ってこの言語は再帰…

HaskellでLisp to LLVM IRコンパイラ その3 LLVM IRへの出力(数字の出力)

前回に続いてLLVM IRで数字を返す方法を考える。 比較的簡単でこのような形になる: %1 = alloca i32 store i32 3, i32* %1 %2 = load i32, i32* %1 スタック上に%1という変数をalloca命令で用意する %1に3という値を代入 %1に含まれている値を一時変数%2に…

HaskellでLisp to LLVM IRコンパイラ その2 LLVM IRへの出力(簡単なテンプレート)

LLVM IRというのはLLVMコンパイラ・フレームワークが定義・利用する中間言語だ。 https://en.wikipedia.org/wiki/LLVM#Intermediate_representation LLVMフレームワークでは、コンパイラのFront Endはソース言語をこのIRに翻訳することに集中し、Back Endは…