🦍
Rustで簡単なLispを書いてみた
初めに
先日Rustの勉強で、jpmens/joをRustに移植してみたんですが、
ちょっと課題がシンプル過ぎたので、Lisp処理系を書いてみました。
本記事は「こんなことをやったよ」くらいの内容で、実装について細かくは書いていないため、
それでも興味ある方は読んでもらえたら嬉しいです。
rispについて
四則演算、変数、関数しか動かない簡単なインタプリタです。
実装
Lisp自体がよくわかっていないので、お気楽 Common Lisp プログラミング入門を読みつつ雰囲気を掴んでいまた。
Lispのリスト構造は(関数 引数...)という感じなので、stack/pop すれば動くかなと思って、最初はこんな感じに雑に実装していました。
初期実装
fn eval(&mut self, chars: &mut Peekable<Chars>) -> String {
loop {
let ch = chars.next();
match ch {
Some(ch) => match ch {
'(' => {
let result = self.eval(chars);
self.stack.push(result);
}
')' => {
let result = self.inner_eval();
self.stack.push(result);
break;
}
'0'..='9' => {
let number = self.read_as_number(ch, chars);
self.stack.push(number);
}
'+' | '-' => match chars.peek().unwrap() {
'0'..='9' => {
let number = self.read_as_number(ch, chars);
self.stack.push(number);
}
_ => self.stack.push(ch.to_string()),
},
'*' | '/' => {
self.stack.push(ch.to_string());
}
_ => {
if ch.is_whitespace() {
continue;
}
break;
}
},
None => break,
}
}
self.stack.pop().unwrap()
}
fn inner_eval(&mut self) -> String {
let mut args = Vec::<String>::new();
loop {
match self.stack.pop() {
Some(value) => match value.as_str() {
"+" | "-" | "*" | "/" => {
let result = self.calc(value, args);
return result;
}
_ => match value.chars().next().unwrap() {
'-' | '+' | '0'..='9' => args.push(value),
_ => panic!("token is not number: {}", value),
},
},
None => panic!("not found valid operator, stack={:?}", self.stack),
}
}
}
しかし、変数定義(setq a 10)や(defun echo (x) x)のような構文はこのままだと実装がしんどいなと思ったので、
ちゃんとレキサーでトークン解析してパーサで構文木（Lispの場合はリスト）を作って評価する実装に切り替えました。
現実装
// トークナイズ
pub fn next_token(&mut self) -> Token {
while self.ch.is_whitespace() {
self.read();
}
let token = match self.ch {
'(' => Token::LPAREN,
')' => Token::RPAREN,
'*' => Token::ASTERISK,
'/' => Token::SLASH,
'+' => match self.peek() {
'0'..='9' => self.read_as_number(),
_ => Token::PLUS,
},
'-' => match self.peek() {
'0'..='9' => self.read_as_number(),
_ => Token::MINUS,
},
'0'..='9' => self.read_as_number(),
'"' => self.read_as_string(),
'a'..='z' | 'A'..='Z' => self.read_as_literal(),
'\0' => Token::EOF,
_ => Token::ILLEGAL(self.ch.to_string()),
};
self.read();
token
}
// パース
pub fn parse(&mut self) -> Result<Expr, ExprErr> {
let token = self.lexer.next_token();
match token {
Token::NUMBER(num) => {
return Ok(Expr::Number(num));
}
Token::STRING(s) => {
return Ok(Expr::String(s));
}
Token::LITERAL(symbol) => {
return Ok(Expr::Symbol(symbol));
}
Token::ASTERISK => {
return Ok(Expr::Symbol("*".to_string()));
}
Token::MINUS => {
return Ok(Expr::Symbol("-".to_string()));
}
Token::PLUS => {
return Ok(Expr::Symbol("+".to_string()));
}
Token::SLASH => {
return Ok(Expr::Symbol("/".to_string()));
}
Token::TRUE => {
return Ok(Expr::True);
}
Token::NIL => {
return Ok(Expr::Nil);
}
Token::ILLEGAL(token) => {
return Err(ExprErr::Cause(format!("invalid token: {}", token)));
}
Token::EOF | Token::RPAREN => {
return Ok(Expr::Nil);
}
Token::LPAREN => {
let mut list = Vec::<Expr>::new();
loop {
match self.parse() {
Ok(expr) => {
if expr == Expr::Nil {
return Ok(Expr::List(list));
}
list.push(expr);
}
Err(e) => {
return Err(e);
}
}
}
}
}
}
// 評価
pub fn eval(&mut self, expr: &Expr, env: &mut ExprEnv) -> Result<Expr, ExprErr> {
match expr {
Expr::String(_) => Ok(expr.clone()),
Expr::Number(_) => Ok(expr.clone()),
Expr::Nil => Ok(expr.clone()),
Expr::True => Ok(expr.clone()),
Expr::Symbol(sym) => match env.get(sym) {
Some(expr) => Ok(expr.clone()),
None => Err(ExprErr::Cause(format!(
"not found symbol: {}, env: {}",
sym,
self.print_env(env.clone()),
))),
},
Expr::List(list) => {
let (first, rest) = list
.split_first()
.ok_or_else(|| ExprErr::Cause("expected at least one number".to_string()))?;
match self.eval_builtin(first, rest, env) {
Some(expr) => expr,
None => {
let expr = self.eval(first, env)?;
match expr {
Expr::Func(f) => f(self.eval_args(rest, env)?.as_slice()),
Expr::Lambda(lambda) => self.eval_lambda(lambda, rest, env),
_ => unreachable!(),
}
}
}
}
_ => Err(ExprErr::Cause(format!("invalid expr: {}", expr))),
}
}
やってみた感想
Lisp処理系の実装で次のことが分かるようになったかなと思っています。
ある程度簡単なものなら、Rustで書けるようにはなったかなと思います。
- enum
- Result
- Option
- パターンマッチ
- 可変参照、不変参照
- derive
- トレイト
- 配列、スライス
また、簡単な四則演算や関数呼び出しくらいなら、Lispは新しい言語を学ぶ際にとてもよい題材だなと思いました。
今後、新しい言語を学ぶ時にまたやってみたいと思います。
これまではGoやTSがメインだったのですが、Rustはそれらと比べるとちょっと毛色が違くて難しいけど、
新鮮で面白いしそれなりに楽しんでいます。
次はちょっとRustでGraphQLのAPIを書いてみたいと思います。
おまけ
LispのコードをQRコードに変換して、
生成した画像から実行できるようにしてみたんですが、誰得感がすごかったので不採用になりました。
Discussion