Good UX Life

人生のUXを高めるための知見

LISP in Two Days with Rust【和訳】

RustでLISPを書くチュートリアルがあったので和訳しました。

willspeak.me

LISP in Two Days with Rust

自作プログラミング言語の開発の副業として、私はLISPの開発に少し時間を費やしました。RustでASTを変換する実験のテスト場としてこの言語を使用する計画です。LISPシンタックスはシンプルでパースしやすいように開発されました。実験的なコンパイラーの出発点としては良いと思いました。

この言語はlispy Scheme derivativeにとてもインスパイアされています。振る舞いのいくつかの要素は、私が手渡さなければならなかったLISP実装であったため、Emacs LISPから直接作成されています。このチュートリアルの最後には次のような式を評価できる言語ができているはずです。

(begin
    (define foo 1007)
    (define bar 330)
    (print (+ foo bar))) ; ~> prints 1337

Step 1 - 読み込み

プログラミング言語への道の最初のステップは、構文解析です。はじめに(+ 1 foo)のようなソースコードを認識する作業を分割と獲得の2つに分けます。最初のステップは文字列をトークンリストに分割します。プログラミング言語の世界でこの工程は字句解析と呼ばれていてそれぞれのトークンは語彙素と呼ばれています。トークンは私たちにとって十分ではあり、入力しやすいです。これをトークナイザーと呼びます。

私たちのトークナイザーは、ソーステキストに対して一連の正規表現を実行し、一致した表現に基づいてトークンの種類を選択することにより、論理的に機能します。私たちの場合、完全な正規表現エンジンはいらず、いくつかのmatchステートメントから構築されたステートマシンで十分です。より深い議論に関しては私の前のブログをチェックしてください。

LISPの分析するのに必要なトークンは非常にシンプルです。 * S式のグループ化 * 数字: [0-9]+ * 空白: \n, \t, ``等 * それ以外は全て識別子

まず、トークナイザーの状態を定義します。RustではEnumを使うのがベストです。

enum TokeniseState {
    Start,
    Lparen,
    Rparen,
    Number,
    Symbol,
    Whitespace,
}

tokenise関数のシグネチャは非常にシンプルです。borrowed stringを受け取り、トークンのベクタを返します。

fn tokenise(source: &str) -> Vec<ast::Token>

おそらく、トークンとはなにかを定義する時が来ました。最初は、トークンを列挙型としてモデル化するのも魅力的かもしれません。しかし、いつか面倒臭くなる時が来ます。多くの場合、すべてのトークン間で共有される状態があります。これを解決するためにトークンを二つのパートに分割します。まずはkindで、これはトークンの種類やNumberトークンの値のようなトークン固有のデータを持つ列挙型です。残りの共通フィールドは、種類とともに構造体に収集されます。

#[derive(Debug, PartialEq)]
pub enum TokenKind {
    LeftBracket,
    RightBracket,
    Number(i64),
    Symbol(String),
}

#[derive(Debug, PartialEq)]
pub struct Token {
    pub kind: TokenKind,
    span: Span<ByteIndex>,
}

トークンをあとでエルゴノミックマッチングするためにkindはpublicになっていることに注意してください。ソースの位置情報とspan情報のためにcodespanクレートを使います。

すべての準備が整ったら、tokeniseメソッドの本体に取り組みます。ループでトークンを取得し二段階に分けて処理します。まず現在の状態、そして次の文字を処理します。

loop {
    let mut state = Start;
    let mut end = start;

    for c in source[start..].chars() {
        let next = match state {
            Start => match c {
                '(' => Some(Lparen),
                ')' => Some(Rparen),
                '0'...'9' => Some(Number),
                'a'...'z' => Some(Symbol),
                c if c.is_whitespace() => Some(Whitespace),
                _ => None,
            },
            Lparen | Rparen => None,
            Number => match c {
                '0'...'9' => Some(Number),
                _ => None,
            },
            Symbol => match c {
                'A'...'Z' | '0'...'9' => Some(Symbol),
                _ => None,
            },
            Whitespace => {
                if c.is_whitespace() {
                    Some(Whitespace)
                } else {
                    None
                }
            }
        };

        // If we transitioned then accept the character
        // by moving on our `end` index.
        if let Some(next_state) = next {
            state = next_state;
            end += c.len_utf8();
        } else {
            break;
        }
    }

    let token_str = &source[start..end];
    let span = Span::new(start, end);

    start = end;

    let kind = match state {
        Start => break,
        Lparen => ast::TokenKind::LeftBracket,
        Rparen => ast::TokenKind::RightBracket,
        Number => ast::TokenKind::Number(token_str.parse().unwrap()),
        Symbol => ast::TokenKind::Symbol(token_str.into()),
        // Skip whitespace for now
        Whitespace => continue,
    };

    result.push(ast::Token::with_span(
        kind,
        span.map(|s| ByteIndex(s as u32 + 1)),
    ));
}

ここでは、読みやすくするために記号を構成できる文字の一部を省略しました。

(+ 1 foo)のように入力された文字は次のようなトークンのリストにできるべきで。

vec![
    Token { kind: TokenKind::LeftBracket, ... },
    Token { kind: TokenKind::Symbol("+"), ... },
    Token { kind: TokenKind::Number(1), ... },
    Token { kind: TokenKind::Symbol("foo"), ... },
    Token { kind: TokenKind::RightBracket, ... },
]

次のステップは、トークンのリストを取得し、構文ツリーを構築することです。ツリーの各ノードは、ご想像のとおり列挙型で表されます。LISPでは構文ツリーにはatomsformsの2種類のノードがあります。私たちのLISPのatomsはNumberSymbolです。Formsは、Formsまたはatomsのリストを含むパラメーター化されたS式です。この二つのメンバーだけで構文ツリーノードを作成することができます。ただし、私たちの言語は二つの特別なフォームを持ちます。条件付き実行の場合と、変数バインディングを導入するための定義です。これらもツリーでモデル化します。

#[derive(Debug, PartialEq)]
pub enum Expr {
    /// A direct reference to a variable symbol
    Symbol(Token, String),
    /// A numeric literal
    Number(Token, i64),
    /// A conditional expression
    If(Token, Token, Box<Expr>, Box<Expr>, Box<Expr>, Token),
    /// A variable declaration
    Define(Token, Token, Token, Box<Expr>, Token),
    /// A funciton call expression
    Call(Token, Token, Vec<Expr>, Token),
}

重要な値を持つトークンだけでなく全てのトークンをツリー含めていることに注意してください。これは、あとでリンターや構文フォーマットを実行する時により多くの位置情報を利用できるようにするためです。このテクニックは、full-fidelity treesと呼ばれていてC#のRoslynコンパイラやSwiftのコンパイラなど多くのコンパイラで使われています。IDEを作成する場合、この追加のメタデータは非常に貴重であることがわかります。

先読みのシングルトークンのLISPを認識できるようになりました。RustのPeekableイテレータを使います。私たちのパーサーはトークンのpeekableリストから始めることを必要としています。

struct ParseState<I: Iterator<Item = ast::Token>>(std::iter::Peekable<I>);

トップレベル関数は次のトークンを調べます。それがatomの場合は直接パースし、そうでなければformのボディを読むためにparse_formに渡します。

fn parse_expr(&mut self) -> ast::Expr {
    if let Some(token) = self.0.next() {
        use ast::TokenKind::*;
        match token.kind {
            LeftBracket => self.parse_form(token),
            RightBracket => panic!("unexpected token!"),
            Number(n) => ast::Expr::Number(token, n),
            Symbol(ref s) => {
                let sym = s.clone();
                ast::Expr::Symbol(token, sym)
            }
        }
    } else {
        panic!("invalid expression.")
    }
}

これは少しパニックする可能性があります!製品レベルのパーサーなら上品にこれらのエラーをResultを返したり、診断をバッファリングし、欠落しているトークンをスタブアウトしてリカバーします。後者のアプローチにより、パーサーは任意のソーステキストから構文情報を抽出できます。IDEの継続的な台頭により、一般的なアプローチになりつつあります。

fn parse_form(&mut self, open: ast::Token) -> ast::Expr {
    use ast::TokenKind::*;
    match self.0.peek() {
        Some(&ast::Token {
            kind: Symbol(ref sym),
            ..
        }) => match &sym[..] {
            "if" => {
                let if_tok = self.0.next().unwrap();
                let cond = self.parse_expr();
                let if_true = self.parse_expr();
                let if_false = self.parse_expr();
                let close = self.0.next().unwrap();
                ast::Expr::If(
                    open,
                    if_tok,
                    Box::new(cond),
                    Box::new(if_true),
                    Box::new(if_false),
                    close,
                )
            }
            "define" => {
                let define_tok = self.0.next().unwrap();
                let sym_tok = self.0.next().unwrap();
                let value = self.parse_expr();
                let close = self.0.next().unwrap();
                ast::Expr::Define(open, define_tok, sym_tok, Box::new(value), close)
            }
            _ => {
                let sym_tok = self.0.next().unwrap();
                let mut args = Vec::new();
                while let Some(token) = self.0.peek() {
                    if token.kind == RightBracket {
                        break;
                    }
                    args.push(self.parse_expr());
                }
                let close = self.0.next().unwrap();
                ast::Expr::Call(open, sym_tok, args, close)
            }
        },
        _ => panic!("invalid expression"),
    }
}

parse_formメソッドも同様のアプローチをとります。汎用なCall式の識別にフォールバックする既知の特別な形式の一つに一致しようとします。これら全ての準備が整ったら、REPLがソーステキストをast::Exprに読み込むために使用する高レベルの解析メソッドを作成できます。

pub fn parse(source: &str) -> ast::Expr {
    let tokens = tokenise(source);
    ParseState(tokens.into_iter().peekable()).parse_expr()
}

Step 2 Eval

これで構文解析された構文ツリーができたので、次は評価に移ります。私たちのevalメソッドはExprを取り、Valueを生成します。evalはエラーが発生する可能性があるために Reslut型を返します。

#[derive(Debug, PartialEq, Copy, Clone)]
pub enum Value {
    Number(i64),
    Callable(Callable),
    Nil,
}

type Callable = fn(Vec<Value>) -> EvalResult;

pub struct EvalError(String);

pub type EvalResult = Result<Value, EvalError>;

pub fn eval(expr: ast::Expr) -> EvalResult {
    eval_with_env(expr, &mut make_global_env())
}

Valueは数字やCall可能な関数を持ちます。これらを評価の結果として返すだけでなく、環境に保存します。

evalにはあまりコードはありませんが、2つの興味深いことが進行中です。一つ目はグローバル関数を作るためにmake_global_envを呼びます。主な評価はeval_with_envで行われます。

私たちのLISPのeval環境は単なるValueSymbolHashMapです。make_global_env関数は新しいmapを作り、グローバルな関数を挿入するだけです。

pub fn make_global_env() -> HashMap<String, Value> {
    let mut env = HashMap::new();

    env.insert(
        "begin".into(),
        Value::Callable(|values| Ok(last_or_nil(values))),
    );
    env.insert(
        "+".into(),
        Value::Callable(|values| {
            let mut sum = 0;
            for value in values.iter() {
                sum += value.into_num();
            }
            Ok(Value::Number(sum))
        }),
    );
    env.insert(
        "-".into(),
        Value::Callable(|values| {
            Ok(if let Some((first, rest)) = values.split_first() {
                let mut sum = first.into_num();
                if rest.len() == 0 {
                    Value::Number(-sum)
                } else {
                    for value in rest {
                        sum -= value.into_num();
                    }
                    Value::Number(sum)
                }
            } else {
                // (-) ~> 0 ; apparently
                Value::Number(0)
            })
        }),
    );
    env.insert(
        "/".into(),
        Value::Callable(|values| {
            if let Some((first, rest)) = values.split_first() {
                let mut res = first.into_num();
                Ok(if rest.len() == 0 {
                    Value::Number(1 / res)
                } else {
                    for value in rest {
                        res /= value.into_num();
                    }
                    Value::Number(res)
                })
            } else {
                Err(EvalError("Wrong number of arguments: /, 0".into()))
            }
        }),
    );
    env.insert(
        "*".into(),
        Value::Callable(|values| {
            let res = values.iter().fold(1, |acc, v| acc * v.into_num());
            Ok(Value::Number(res))
        }),
    );

    env
}

eval実行環境の中ではかなり簡単な方です。数値atomは自分自身に評価されます。シンボルは環境で検索されます。

use ast::Expr::*;
match expr {
    Symbol(_, s) => env
        .get(&s)
        .cloned()
        .ok_or_else(|| EvalError(format!("eval: Undefined symbol {}", s))),
    Number(_, n) => Ok(Value::Number(n)),

If式を評価し、結果に基づいて評価するブランチを選択する場合:

    If(_, _, cond, then, elz, _) => Ok(if eval_with_env(*cond, env)?.is_truthy() {
        eval_with_env(*then, env)?
    } else {
        eval_with_env(*elz, env)?
    }),

Defineはその式を評価し、結果を環境ハッシュマップに挿入します。

    Define(_, _, sym, value, _) => {
        let value = eval_with_env(*value, env)?;
        let sym = to_sym(sym)?;
        env.insert(sym, value.clone());
        Ok(value)
    }

関数呼び出しは、環境内でCallableを検索し、すべての引数を評価して呼び出します。

    Call(_, sym, args, _) => {
        let sym = to_sym(sym)?;
        match env.get(&sym) {
            Some(Value::Callable(c)) => c(args
                                          .into_iter()
                                          .map(|a| eval_with_env(a, env))
                                          .collect::<Result<Vec<_>, _>>()?),
            _ => Err(EvalError(format!("eval: Invalid function {}", sym))),
        }
    }
}

Expr型はシンプルなので全てのケースを分類します。これはLISPの利点です。構文は小さいです。本当の力はそれを組み合わせることができるということです。

Step 3 出力

パースと評価が適切に行われているため、読み取り、実行、出力のループがほぼ機能しています。非常にシンプル評価の結果を出力できます。

fn print(result: eval::EvalResult) {
    match result {
        Ok(value) => println!(" ~> {}", value),
        Err(error) => println!(" !! {}", error),
    }
}

ソース行を読むには、最初にプロンプ​​トが必要です。

fn read() -> ast::Expr {
    let mut buff = String::new();
    print!(" > ");
    std::io::stdout().flush().unwrap();
    std::io::stdin().read_line(&mut buff).unwrap();
    parse::parse(&buff)
}

最終的なREPLは非常に簡単に構築できます。

let mut env = eval::make_global_env();
loop {
    print(eval::eval_with_env(read(), &mut env));
}

グローバル環境はloop前に初期化されそれぞれのREPLの状態は次のエントリで利用できることに注意してください。

 > (define foo 100)
 ~> 100
 > (define bar 99)
 ~> 99
 > (+ foo (- foo bar))
 ~> 101

Step 4 実験

基本を設定したら実験してみましょう。グローバルスコープに新しいCallable関数を含めることで、簡単に”基本ライブラリ”に追加することができます。この投稿で概説されている言語は、ユーザ定義関数やループの形式をサポートしていません。欠落しているもう一つの大きなLISP機能は、フォームを引用および評価して、ソースコードからデータに変換したり戻したりする機能です。

この投稿で作られたプログラミング言語ソースコードは、GitHubで入手できます。