Arantium Maestum

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

言語処理系

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…

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は…

HaskellでLisp to LLVM IRコンパイラ その1

とりあえず作り始めた。 github.com 基本戦略としては、まずは数値計算だけのコードをLLVM IRに変換するのを目的に: Lispコード→LispVal型データ構造→SSA IR→LLVM IR の流れでコンパイルしていく。 長期的にはLLVM IR上でLispValを表すStructを作る必要があ…

Haskellで50行以内のミニマルコンパイラ

こんなツイートが流れてきた: A complete #compiler to x86 in one page for my lecture today. pic.twitter.com/PwFl4V5czy— Joe Gibbs Politz (@joepolitz) 2018年4月11日 元となっているのは"An Incremental Approach to Compiler Construction"という論…