Posted on 2018-09-06

これは何

「自作言語インタプリタを作りたい」のまとめ記事、ポエムが多かったので分離しました。

構文

a: = { k: Int -> k + 1 }
a(2) // 3

dis: (Int, Int) -> Float = { sqrt(_1 ^ 2 + _2 ^ 2) }
dis(3, 4) // 5.0

こんなかんじでラムダ式を表現できるようになる予定です。

関数定義

fn name(a: Int) -> Int {
    return a
}

プログラム実行までの主な流れ

[字句解析] → [構文解析] → [意味解析] → [実行]

字句解析はソースコードを対応するトークンに置き換える作業です。これは正規表現で出来ます。構文解析は字句解析で生成されたトークン列を構文の構造に落とし込みます。これが難しそう、そんな時に見つけたのが Ruby の標準添付ライブラリ racc です。 racc は Ruby 版 yacc で、 yacc はパーサジェネレータの１つです。ここではraccの使い方などは割愛しますが yacc によって構文解析を容易に行うことが出来ました。

言語を解析するにあたって大体は大まかに分けて次のステップを踏む必要があります。(インタプリタの場合)

作業ログ

コミットログを見ながらいままで何をしてきたのか振り返りたいと思います。

7/16(1日目)

この日から Arcturus(注: 自作言語プロジェクトの名前) の開発が始まっています。この日は確か大学が補講日で休日にも関わらず、レポート提出ついでにテスト勉強しに大学に赴いた日です。テスト勉強しろ。この日は簡単な四則演算の字句解析器と構文解析器を実装して終わり。

7/17(2日目)

commit '関数呼び出し複数引数時のカンマにめちゃ苦戦したけどゴリ押しでなんとかなった'

この日は f(1, 2, 3, 4) みたいなプログラムをパースしようと苦戦していたみたいです。結果ゴリ押しで

parser.y

# 関数呼び出し
parameters: 
    PAREN_OPEN exp PAREN_CLOSE { result = [val[1]] }
    | PAREN_OPEN exp COMMA exp PAREN_CLOSE { result = [val[1], val[3]] }
    | PAREN_OPEN exp COMMA exp COMMA exp PAREN_CLOSE { result = [val[1], val[3], val[5]] }
    | PAREN_OPEN exp COMMA exp COMMA exp COMMA exp PAREN_CLOSE { result = [val[1], val[3], val[5], val[7]] }
    | PAREN_OPEN exp COMMA exp COMMA exp COMMA exp COMMA exp PAREN_CLOSE { result = [val[1], val[3], val[5], val[7], val[9]] }
    | PAREN_OPEN exp COMMA exp COMMA exp COMMA exp COMMA exp COMMA exp PAREN_CLOSE { result = [val[1], val[3], val[5], val[7], val[9], val[11]] }

6引数までをべた書きにすることで対応したようです。(後日改良してます) ていうかテスト勉強して

7/18(3日目)

この日は変数定義や関数定義の実装に取り組んでいたようです。この頃はまだ構文解析器と意味解析器が分離されておらず、racc の y ファイルの中に直接変数が宣言されたときの処理とかを書いていたようです。

変数は名前空間のシンボルをキーとするハッシュで管理されていて、各キーに対応する値は変数名のシンボルをキーとするハッシュです。例えば、

a: Int

のような形で宣言された時に global 空間での a の宣言なので、 var_table[:global][:a] に変数の情報(型など)が格納されます。こうすることによって関数の引数の変数名がグローバルで宣言されている変数名と被って使えないなどということが回避できます。最初に思いついたのがこれだけどもっといい方法があるかも・・・。

次に関数、関数は単純に関数名をキーとするハッシュで管理されていてキーに対応する値は関数の情報(各引数の型、返り値型、関数の実装)が格納されます。

fn f(a: Int) -> Int {
    a + 1
}

この時点では関数の戻り値は最後に評価された値を返すようにしています。ただまだ宣言された返り値型と実際の返り値の型が一致するかを検査していなかったりいろいろ荒削りです。

7/20(5日目)

型システムを少し拡張してタプルなどに対応しました。

a: Int -> Int = { i: Int -> i ^ 2 } // lambda
b: (Int, Int) = (1, 2) // tuple

ちなみに内部では Int -> Int は [['Int'], 'Int']、(Int, Int) は [['Int', 'Int']] という構造となっています。しかし、タプルは型を複雑にしすぎるという理由で後々導入をやめました。

7/24(7日目)

commit '式の評価をするTraverserを書き始めた'

パーサーと意味解析器を分離して、ASTを再帰的に辿るTraverserを書き始めました。例えば、

a := 1 + 1

は

['assign', ['decl', 'a', []], ['add', ['int_lit', 1, 'Int'], ['int_lit', 1, 'Int']]]

というASTが構築され、

['decl', 'a', []] -> ['id', 'a', []]
['add', ['int_lit', 1, 'Int'], ['int_lit', 1, 'Int']] -> ['int_lit', 2, 'Int']
['assign', ['id', 'a', []], ['int_lit', 2, 'Int']]
['id', 'a', 'Int'] # a => 2

という流れで評価されます。余談ですが宣言時の a の型は [] 、つまり空なのですが代入時に左辺の型から推論しています。つまり型推論を備えているということです。このような単純なパターンだからかもしれませんが実装は全く難しくないので、すぐに実現できています。(ラムダ式の型推論とかやると難しそう)

7/26(8日目)

そういえば、言語の作り方に興味を持ったのに伴ってAmazonでこちらの本を購入しました。
まつもとゆきひろ言語のしくみ Kindle版
この本はプログラミング言語 Ruby の作者であるまつもとゆきひろ氏が１つの新しい言語を作る過程をRubyの裏話やソースコードを交えながら丁寧に解説されています。淡々と実装していくわけでなく試行錯誤しながら使用者を考える、つまり言語のデザインの仕方を学べるのでとてもいい本でした。それでは続きを。

commit '右辺値に変数を使うことが可能に'
commit 'インクリメント、デクリメントに対応'

変数への代入の実装に手を加えて変数の代入とインクリメント、デクリメントが可能になりました。

a: Int = 3
b: = a++

このコードを実行すると a = 4, b = 4 と評価されます。注意したいのが Arcturus には C と違って 前置インクリメント、後置インクリメント の概念がなく、二項演算子より優先順位の高い単項演算子というだけなので C とは違う結果となっています。

int a = 3;
int b = a++;
printf("%d %d\n", a, b); // a = 4, b = 3

さらに、

commit '関数定義と呼び出し動くように'
commit '自動変数it, _nに対応'

関数定義と呼び出しの実装をしました。関数が定義されると 関数名 のシンボルがキーのハッシュが変数テーブルに作成されてそこに引数の情報が格納されます(値はまだない)。

関数が呼び出されるとそのハッシュの変数に具体的な値がセットされて、関数本体が評価されます。そして最後に評価された値を関数の評価値としています。

また自動変数 it と _n にも対応しています。宣言せずとも自動で割り当てられる変数なので自動変数です。 it は引数が１つの関数のみで使用できる引数を示す自動変数です。 _n はn番目の変数を示す自動変数です。またそれに伴って it = 3 のような行為を防ぐため Readonly の概念も地味に加わっていたりします。

fn f1(i1: Int) -> Int {
     i1 + it + _1
 }

f1(1 + 1) // 6

のような結果となります。

commit 'ラムダ式の代入と呼び出しに対応'
commit 'ラムダ式引数に対応'

なんとこの日はラムダ式も実装していました。とはいえ新しい実装は少ないです。なぜかというと、

fn_name = SecureRandom.urlsafe_base64(8)
fn_type = _define_function(fn_name, node[1], node[2], [], true)
return ['lambda', fn_name, fn_type]

のように内部ではラムダ式は名前がランダムな文字列の関数です。なので引数がラムダ式であってもそれを評価すれば良いだけの話です。

fn f(a: (Int) -> Int) -> Int {
    a(1)
}

f({ s: Int -> s + s }) // 2

上のようなコードが動くようになりました。いいね。それでは。

7/28(10日目)

今日は昼にピアノ教室があったので午前中はピアノを弾いてました。早くうまくなりたい。ということでこのエントリーはピアノ教室から帰宅して誰もいないリビングで蝉の声を聞きつつ涼風にあたりながら書いています。夏って感じ。
今日で7連勤の呪縛から開放されます。明日が休みってだけで無限に頑張れる気がする。残り少ない飲食店厨房バイトを大切にしていきましょう()。

commit 'for文を追加、バグ修正、変数の再定義可能に'
commit 'if式を実装'

制御文として必須である if式 と for文 を実装しました。 Arcturus では if は式なので三項演算子のように使うことが出来ます。

if(true) {
    println("True")
} else {
    println("False")
}

days: = if(isLeapYear()) { 366 } else { 365 }

しかしこの if式 には if { ... } else { ... } のみ対応しておらず、 else if に対応していないという欠点があります。
そこで用意されたのが次の ガード式 です。

bmi: = 22
result: = 
    bmi < 19 -> "Low" ?
    bmi < 25 -> "Normal" ?
    "Fat"
println(result)

ガード式 は (条件1) -> (返り値1) ? (条件2) -> (返り値2) ? ... ? (どれにも当てはまらないときの返り値) のような構造で条件を先頭から判定し最初に真となったものの返り値が返されます。
はっきり言って if式 の上位互換です。この ガード式 は将来的にはパターンマッチにも対応する予定です。

続いて for文 を紹介します。 for は式ではなく文です。 Scala には for式 なるものがあるらしいのですが。現時点の for は Range 型の引数を1つとって範囲の中を増分1でループする仕様です。まだ逆順やn増分などに対応していないので汎用性は低いです。

for(1..15) { i ->
    println(i)
}

start: = 4, end: = 10
for(start..end) { j ->
    println(j)
}

この for文 と ガード式 を組み合わせることでアレが書けます。

fn fizzBuzz(i: Int) -> String {
    i % 15 == 0 -> "FizzBuzz" ?
    i % 3 == 0 -> "Fizz" ?
    i % 5 == 0 -> "Buzz" ?
    str(i)
}

for(1..15) { i ->
    i |> fizzBuzz |> println
}

ちょうどこの時実装したパイプライン演算子 |> のテストも兼ねて使用しました。パイプライン演算子は F# などで採用されているらしいです。(i |> fizzBuzz |> println は println(fizzBuzz(i)) と等価)

ということで1つのマイルストーンである FizzBuzz を表現することができました。

8/1(11日目)

大学の期末テストが終わり夏休み突入です。確かこの時３日間くらい高熱が出ていたような気がします。完徹すると１週間以内に絶対に体調崩すジンクス。

commit '配列の宣言と添字のアクセス、代入を実装'

配列を実装しました。必須ですね。

array: = [1, 2, 3]
i: = 0, j: = 100
array[i] = j

ちなみに型は内部では Array<Int> (内部表現: ['Array', 'Int']) となっていますが、 ジェネリックプログラミング の機能をまだ実装していないので明示的に型を表現できません。なので型推論に任せています。

commit '再帰、return文に対応'
commit 'returnに関するバグ修正'

return.ac

fn f() -> Int {
    a := 2
    if(a == 1) {
        return a
    }
    3
}

print(f()) // 3

8/2(12日目)

commit 'make node class and do refactoring'
commit 'refactoring traverser'
commit 'improve architecture and check to run to m06'

何故かこの日だけコミットメッセージが英語です。とにかくリファクタリングを進めています。今まではノードを ['id', 'i', 'Int'] のように配列で扱っていたのでソースコードがマジックナンバーだらけでした。なので VariableNodeクラス などを導入してオブジェクト指向化しました。まだソースコードカオスだけど。

8/9(13日目)

まる一週間コミットがなかったようです。７連勤ロングシフトのせいだ。まぁ毎日エントリー書いてたし多少はね？

commit 'm08まで動くように'
commit 'm09動くように'
commit 'm11まで対応、右辺代入演算子追加'
commit 'm12まで対応、配列サポート'

リファクタリングを進めながらマイルストーン(サンプルコード)の動作確認をしています。また途中で右辺代入演算子 => を導入しています。これは先日買った 「言語つくる本」 から着想を得た(~~パクリ~~)もので左辺値を右辺に代入する演算子です。

2 |> square |> double => a: // 8

このようにパイプライン演算子と組み合わせることで直感的なコードがかけるはずです。

8/10(14日目)

commit 'ラムダ引数のときにラムダ式を省略してかけるように'
commit 'support omitted lambda expression assignment'

ラムダ式の省略を実装しました。今までは { 引数名:型... -> 文 } と書いていたのですが関数の引数や代入時の右辺値など型が明示的にわかっている時は引数と矢印を省略して { 文 } のように書けます。では省略された引数はどうやってアクセスするのかというと、自動変数の出番です。これによりとてもスマートにラムダ式をかけるようになりました。

さらに関数呼び出しの方にも手を加えて関数の引数が１つのみかつその引数がラムダ式のとき関数呼び出しの括弧を省略できます。

fn f(action: (Int, Int) -> Int) -> Int {
    action(1, 2)
}

f { _1 + _2 } |> p // 3

dis_sq: (Int, Int) -> Int = { _1 ^ 2 + _2 ^ 2 }
dis_sq(3, 4) |> p // 25

ちなみに内部では省略された引数名は __argN となってます。以下が該当部分。汚いし後で見たらわからなくなりそう。


elsif expected_type != given_type
    # ラムダ式が省略形のときは引数を補完
    if _is_lambda_type(expected_type) && @@FunctionTable[traversed_args[i].id.to_sym][:is_omit] then
        traversed_args[i].type = expected_type
        @@FunctionTable[traversed_args[i].id.to_sym][:fn_type] = expected_type
        @@FunctionTable[traversed_args[i].id.to_sym][:args] = (1..expected_type[0].length).map { |i|
            ArgNode.new("__arg#{i}", expected_type[0][i - 1])
        }
    else

また color_echo という gem を導入して実行画面の見た目も整えました。

CE.fg(:white)
    .pickup(/#{@@PremitiveTypes.join('|')}/, :index7)
    .pickup(/#>/, :yellow)
    .pickup(/=+.*?=+/, :index254, nil, :bold)
    .pickup(/<.*?>/, :green)

このように正規表現と色を指定するだけで標準出力が色付けされます。便利。

カラフルで見やすい。ちなみにターミナルは Hyper 使ってます。

これで最新のcommitに追従出来ました。これからは将来的に実装したい要素や実装した要素の解説などをしていきたいと思います。

8/13(15日目)

返り値の型推論

commit 'implement function/lambda return type estimation'
commit 'add call-functions return type estimation'

今までは適当にやっていた返り値の推論をしっかりするようにしました。
例えば、以下のようなコードがある時、

fn f(double: (Int) -> Int, a: Int) -> Int {
    double(3) + a * _2
}

f({ it * 2 }, 1)

以前は定義された時点では関数本体中の式や変数には型情報がありませんでしたが、定義時に型情報を取得するようにしました。

(double(3) + a * _2): ???型
double(3): Int型
a: Int型
_2 => a: Int型
a * _2:Int型 * Int型 = Int型
(double(3) + a * _2): ???型 => Int型

まだテスト不足なのでバグめちゃくちゃあると思う。

8/14(16日目)

型メソッド

commit 'support type method call'
commit 'support getting reciever variable/literal by "this"'

Kotlin でいう Extension Functions です。特定の型に対するメソッドを生やすことが出来ます。 this でレシーバーオブジェクト(ドットの前のオブジェクト)を取得できます。

// 型メソッド
fn Int.sq() -> Int {
    this ^ 2
}

4.sq() // 16
(1 + 5).sq() // 36

関数呼び出し時に型の制限を確認するだけで実装できます。

8/15(17日目)

ココらへんは遊びまくっていたので小さなバグ修正と些細なリファクタリングが中心でした。

8/18(18日目)

さて、本題です。今回はいろいろなサンプルを Arcturus で書くとしたらどのようになるかを見ていきましょう。未実装の機能をバリバリ使っているのでその場合は適宜解説します。

フィボナッチ数

&: |> { when(it) { 0, 1 -> it, else -> self(it - 2) + self(it - 1) } |> println

入力演算子 `&:`

前回までは >> でしたが、わかりにくいので変更しました。
&: は入力演算子で、入力のフォーマットに応じて自動的に型が決定されます。例えば数字を入力すると Int 型の入力として扱われます。明示的に型を指定したい場合は &: String のように後ろに型を指定します。

ラムダ式の即時呼び出し

&:| > { ... } は { ... }(&:) と等価なのでラムダ式の呼び出しをしているだけです。

自身を呼び出す `self`

関数やラムダ式内で self を使用すると自身を呼び出せるようにしたいです。

マインスイーパ

enum State { Closing | Opening | Flagging }

class Cell(isMine: Bool = false, hints: Int = 0, state: State = State.Closing) { 
    fn toString() -> String {
        [' * ', ' #{hints} ', ' F '][state.index]
    }
}

&: => num:
board: Mat<Cell, 8, 8>
board.select(num).map { isMine = true }
board.eachIndexed { cell: Cell, x: Int, y: Int ->
    cell.hints = board[x + -1..1, y + -1..1].count { is_mine }
}

while(board.count { isMine } < num) {
    println(board)
    println("mode(1 : OPEN, 2 : FLAG) x y ?: ")
    [mode: State, x: Int, y:Int] = [&:]
    when(mode) {
        State.Opening -> {
            board[&: + -1..1, &: + -1..1]
                .filter { !isMine }
                .map { state = State.Opening }
        }
        State.Flagging -> {
            board[&:, &:].state = if(board[x, y].state == State.Flagging) State.Closing else State.Flagging
        }
    }
}

２次元配列 `Mat`

二次元的な表現はプログラミングをするときによく使われると思うのですが、多くのプログラミング言語では２次元配列を表現するときに配列の配列を用いて表現することが多いと思います。
しかし、例えば座標の管理などで poses[x][y] だと思ってコーディングしたら実際は poses[y][x] でバグが発生していたり、要素を列挙するのに２重のfor文を使わなければならないなど煩わしさが多少あります。なので Arcturus では２次元配列を Mat として言語仕様に組み込もうと思います。

列挙型 `Enum`

enum Fruit { Apple | Orange | Grape }
fruit: Fruit = Fruit.Apple

列挙型です。

`Class`

class Human(age: Int, job: String) {
    fn greed() -> Unit {
        println("#{age} years old, I'm a #{job}")
    }
}

human: = Human(24, "student")
human.greed() // "24 years old, I'm a student"

まぁよくあるクラスです。

２次元配列と配列のアクセサ

１次元配列 Array では array[3] のようにして要素にアクセスできるのと同様に、２次元配列 Mat では mat[2, 4] とすることでアクセスできるようにしたい。
また、添字に 1..4 のような Range を指定することで配列の切り出しとかも出来るようにしたい。

分割代入

分割代入は最近の JavaScript とかにある [a, b] = [10, 20] のように配列の要素を分割して代入できる式です。

[a, b] = [10, 20]
assert(a == 10 && b == 20)
[a] = [10, 20]
assert(a == 10)
[a, *b] = [10, 20, 30]
assert(a == 10 && b == [20, 30])
[a, _, b] = [10, 20, 30]
assert(a == 10 && b == 30)

実装難しそう。これらのサンプルが動くようになるのはいつになることやら。

8/22(18日目)

commit 'add REPL'

最近の言語にはだいたいある REPL を実装しました。

> 1 + 2
evaled: [3]
> [1, 4, 9] == [1 ^ 2, 2 ^ 2, 3 ^ 2]
evaled: [true]

簡単なテストをするのに便利です。

オートマッピング

commit 'support auto-mapping of operators'

配列と非配列との演算時に自動で Array.map 相当のことをしてくれるのが オートマッピング です。何かの自作言語から影響を受けています。

// オートマッピング
assert([1, 2] + 1 == [2, 3])
assert([1, 2] + [3, 4] == [4, 6])
assert(([1, 2, 3] == 2) == [false, true, false])
assert(([1, 2, 3, 4] % 2 == 0).count() == 2)

8/25(19日目)

分割代入(続き)

xs: = [1, 2]
[xs , x: , y: ] = [1, 2, 3, 4]
assert(xs == [1, 2] && x == 3 && y == 4)

[x: Int, y: Int, xs: Array<Int>] = [1, 2, 3, 4]
assert(xs == [3, 4] && x == 1 && y == 2)

[x: Int, xs: Array<Int>, y: Int] = [1, 2, 3, 4]
assert(xs == [2, 3] && x == 1 && y == 4)

[_, x: Int, y: Int] = [1, 2, 3, 4]
assert(x == 3 && y == 4)