Zenn
Open14

RustでLispインタープリタを実装する

Rust
scheme
#
lisp
#
インタープリタ
nakaakistnakaakist

用語

  • syntax: 言語の、正しいstatement (文)やexpression (式)を形作る文字の並び
  • semantics: それらstatement, expressionの意味
  • evaluation: expressionを評価し、値を決定すること。<式> => <値>のようにここでは書く

普通の数学を言語としてみたときの例

  • 1足す2のsyntaxは"1 + 2"、semanticsは1に2を足すということ。
nakaakistnakaakist

Language 1: Lispy Calculator

電卓とif, defineが使える単純なschemeのサブセット。

使えるexpressionは下記

variable reference

  • syntax: symbol
  • semantics: symbolが変数名として解釈される。evaluateされると、変数の値となる
  • 例: (rが以前に10とdefineされてたら) r => 10

constant literal

  • syntax: number
  • semantics: 数字は、それ自身の値にevaluateされる
  • 例: 12 => 12

conditional

  • syntax: (if test conseq alt)
  • semantics: testをevaluateし、trueならconseqをevaluateしreturn、そうでなければaltをevaluateしreturn
  • 例: (if (> 10 20) 3 5) => 5

definition

  • syntax: (define symbol exp)
  • semantics: 新しい変数名を定義し、expをevaluateし、その値を入れる
  • 例: (define r 10)

procedure call

  • syntax: (proc arg...)
  • semantics: procが、if、define、quote以外だったら、それはprocedureとして扱われる。まず、procとargの全てがevaluateされた後、procがargを引数にとって実行される
  • 例: (sqrt (* 2 8)) => 4.0
nakaakistnakaakist

What A Language Interpreter Does

1. Parsing

  • 文字列を受け取り、言語のsyntactic rulesに従ってるかを検証し、内部表現(=シンプルなインタープリタの場合はabstract syntax tree, AST)に変換する。
  • 「コンパイラ」と呼ばれるlanguage translatorでは、複数の内部表現が存在する場合が多い。ASTから始まり、最終的に機械語になる。
  • Lispyでは、parseという関数を実装している。

2. Execution

  • 内部表現は、言語のsemantic rulesに従って処理され、計算が実行される。
  • Lispyでは、evalという関数を実装している。

eval(parse("(begin (define r 10) (* pi (* r r)))")) みたいなイメージ

nakaakistnakaakist

Type Definitions

lispyでの、schemeとpythonのデータ型の対応は下記。

Symbol = str              # A Scheme Symbol is implemented as a Python str
Number = (int, float)     # A Scheme Number is implemented as a Python int or float
Atom   = (Symbol, Number) # A Scheme Atom is a Symbol or Number
List   = list             # A Scheme List is implemented as a Python list
Exp    = (Atom, List)     # A Scheme expression is an Atom or List
Env    = dict             # A Scheme environment (defined below)
nakaakistnakaakist

Parsing: parse, tokenize and read_from_tokens

  • パースは、歴史的には次の2つからなる
    • lexical analysis (字句解析)
      • 文字列をトークンのリストにする
    • syntactic analysis (構文解析)
      • トークンのリストをASTにする
  • lexical analysisにはいろいろなツールがある。lispyでは、pythonの文字列のsplitメソッドを使っている。
nakaakistnakaakist

Environments

  • プログラム内で定義された変数名とその値のマップを保持するものを、lispyではenvironmentと呼んでいる。
  • lispyでevalがよばれたとき使われるglobal environmentには、+や>といった標準関数が含まれている。ここに、ユーザー定義の変数が加わっていく。
nakaakistnakaakist

Evaluation: eval

  • あとは、ASTを評価していくだけ。ASTのリストの最初のトークンを読み、その内容(e.g., define, if)によって、その後の対応を変えていく。
nakaakistnakaakist

とりあえずパーサまで実装。
https://github.com/nakaakist/scheme-interpreter-rust/blob/94719312478b8e2e2f5a642f188873c27e0fba4a/src/parser.rs

下記のような感じでAstNodeを定義

pub struct AstNode {
    children: Vec<AstNode>,
    value: Option<String>,
}

プログラム文字列をトークンに分解した後、下記のような関数でAstNodeを構築。

fn read_from_tokens(tokens: &mut Vec<String>) -> Result<AstNode, &'static str> {
 ...
 // tokensから一つずつtokenをpopしつつ、再帰的にAstNodeを組み立てる
}

ハマったポイント

  • read_from_tokens関数を作る際、所有権周りでハマった。
    • 結論、引数を&mut Vec<String>にすればよかった。これで、関数の中でtokensをいじりつつ、所有権は呼び出し元で保持できる。
nakaakistnakaakist

各モジュールの責務

  • lexer: integer, symbol, カッコ、というタイプを持つtokenに文字列を分解
  • parser: tokenをネストされたinteger, symbol, listの構造にする
  • eval: parserの結果を変形していく。この過程で、void, lambda, boolタイプがparseの結果に追加されていく