MalgoでLispインタプリタを書きました

言語処理系Slack定期ミーティング用資料

昨日夜ふかししたのでめっちゃ眠いです。

今日話すこと

MalgoでLispインタプリタを書きました

パーサを書く

evalを書く

Malgoを一から実装するためのマイルストーンを作りはじめました

リファクタリング

Malgoでのセルフホスト

MalgoでLispインタプリタを書きました

思ったよりMalgoの表現力が高い

コンパイラのパフォーマンスが問題になった

思ったよりMalgoの表現力が高い

ちょっと話はそれて、Haskellの拡張構文MaltiWayIf

code:MultiWayIf.hs

if n <= 0

then 1

else if n == 1

then 1

else f (n - 1)

-- ↑これが↓こう書ける

if | n <= 0 -> 1

| n == 1 -> 1

| True -> f (n - 1)

code:cond.lisp

(cond (((<= n 0) 1)

((== n 1) 1)

(#t (f (- n 1))))

Malgoにもこういうのが欲しくて、文法を考えた

いまいちスッキリしたのが思いつかない

code:MultiWayIf.mlg.hs

-- イマイチ。悪くはないけど…

{ ? n <= 0 -> 1

| ? n == 1 -> 1

| ? True -> f (n - 1)

}

シャワーを浴びてたら思いついた

code:cond.mlg.hs

cond [(n <= 1, { 1 }),

(n == 1, { 1 }),

(True, { f (n - 1) })]

コンパイラのパフォーマンス

式中に型注釈を書けるようにした

code:cast.mlg.hs

cast Nil : Ptr# Char#

これを入れるとパースがめちゃくちゃ遅くなった

型注釈が無くても必ずバックトラックが起きる

あらゆる部分式を2回パースする

それでもコンパイルがめちゃくちゃ遅い

300行のLispインタプリタのコンパイルに1分くらいかかる

mutableな変数を表現するモナドの一つ

結合可能な値（文字列とかリストとか）を次々結合していくパターンに特化

ASTの構築に使っている

リフレクションみたいな機能

ボイラープレートは減らせるが、速度は手書きほどは出ない

プロファイル取ったらボトルネックになっていたので、手で書き直した

もろもろ高速化して1分→4秒ぐらいまで縮めた

Lispの実装

Malgoを一から実装するためのマイルストーン

最終的にはMalgoでMalgoをセルフホストしたい

段階的にMalgoを実装するためのマイルストーンが必要