RustでSECDマシンを作って諦めた話

SICPの第4章を読んで実際に超循環評価器を作り、これはなかなか面白いと思ったものの、第5章ではいきなりレジスタマシンを作らされそうになってつらい気持ちになったので、なにかほかの方法はないかといろいろ調べていました。

すると、[SECDマシン](http://www.geocities.jp/m_hiroi/func/abcscm33.html)というものがあるらしいではありませんか。こういった仮想マシンについてまったく知らない状態でいきなり第5章を読むのではなく、ひとまずもうすこし書きやすい仮想マシンで試してみるのもいいだろうと、これをRustで作ってみることにしました。

以下は、そうやって純Lispに毛の生えたくらいのものを実装した結果をお伝えする記事になります。なにか気がついたことがありましたら、どしどしご指摘ください……！

なお、すべてのコードはこちら：https://github.com/murashit/secd

# だいたいの仕様と感想
* あるもの
    * フィボナッチ数を求めたりたらいまわし関数をまわすのに不便ではない程度の構文や手続きや構文を実装することにした
    * VMの節で簡単に触れているとおり`set!`が実装できなかった。なので、とりあえずこれを通じて定義することになる`letrec`がない。したがって内部defineもできない
    * もとから備えている構文は`quote`、`define`、`define-macro`、`lambda`、`if`、`begin`
        * 手続きを全部`lambda`で定義するのはダルいので、`(define (proc x y) ... body ...))`も使えるようにしている。可変長引数も使える
        * `cond`や`let`は別にマクロで定義している
        * `quasiquote`の処理もマクロで定義している
* ないもの
    * call/cc：ない
    * 末尾呼び出し最適化：ない！
    * GC：ない！！
    * REPL：ない！！！
* モジュールはとりあえず下記のとおりに分けた
    * パースしてASTを作るためのreader
    * ASTからVM用の命令を作るためのcompiler
    * VMを走らせるためのvm
    * シンボルやコンスセルといった値の型を定義したvalue
    * プリミティブとして扱う手続きを定義したprimitive
* プリミティブではないがあると便利な関数やマクロをSchemeで定義したファイルを別に作った

とりあえず「純Lispです」と言ってもまちがいではない感じにはなっているし、マクロも実装できたのでいったん満足。ただ、まさか`set!`の実装でつまづくと思っていなかったのでそこがくやしい。そのへん対応するには、大幅に変更しなきゃなのかなあ。ひとまず`set!`はとばして`call/cc`とかTCOあたりはもうすこし試してみてもいいかもしれない。

Rustを書くのにはまだ慣れない。所有権まわりについては……雑に書いたあとに見直すと、どんなコンパイルエラーが出るかくらいはなんとなく予想がつくようになってきた。ただ、やっぱりポインタを駆使したプログラムを書いたことがない（= C/C++を触ったことがない）こともあり、馴染んでいるとはとても言いがたい感じ。

- - -

以降、メインとなるreader、compiler、value、vmのコードとそれに対する簡単なコメントです。

# reader
* ソースコードをパースしてASTを作る部分
* [combine](https://github.com/Marwes/combine)を使ってざくざくやったので特筆することはございません
* 最初は直接Valueに変換していたのだけど、リストを最初からコンスセルにしちゃうと走査がわりとめんどいし、のちのちヒープとか実装するかもしれないと思ったのでASTはASTの型として定義
    * これを「AST」と呼んでいいのかどうかはよくわからない
* シンボル（識別子）だけは無駄にR5RS準拠（のはず）
* 今気付いたけど、`( . 1)`みたいな不正なドットリストを受け付けるようになってしまっているな……

```rust
use combine::*;
use compiler::Ast;

pub fn read(input: &str) -> Result<(Vec<Ast>, &str), ParseError<&str>> {
    parser(whitespace)
        .with(many1(parser(expression).skip(parser(whitespace))))
        .skip(eof())
        .parse(input.trim())
}

fn whitespace<I>(input: I) -> ParseResult<(), I>
    where I: Stream<Item = char>
{
    let comment = token(';')
        .and(skip_many(satisfy(|c| c != '\n')))
        .map(|_| ());
    skip_many(skip_many1(char::space()).or(comment)).parse_stream(input)
}

fn expression<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    between(token('('), token(')'), parser(list))
        .or(parser(atom))
        .or(parser(quote))
        .or(parser(quasiquote))
        .or(try(parser(unquote)).or(parser(unquote_splicing)))
        .parse_stream(input)
}

fn atom<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    try(parser(integer))
        .or(parser(symbol))
        .or(parser(hash))
        .parse_stream(input)
}

fn hash<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    token('#')
        .with(any())
        .map(|c| match c {
                 't' => Ast::Boolean(true),
                 'f' => Ast::Boolean(false),
                 _ => unimplemented!(),
             })
        .parse_stream(input)
}

fn integer<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    let unsigned = many1::<String, _>(char::digit());
    let positive = unsigned
        .to_owned()
        .map(|s| Ast::Integer(s.parse::<u32>().unwrap() as i32));
    let negative = token('-')
        .with(unsigned)
        .map(|s| Ast::Integer(-(s.parse::<u32>().unwrap() as i32)));
    negative.or(positive).parse_stream(input)
}

fn symbol<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    let special_initial = one_of("!$%&*/:<=>?^_~+-".chars());
    let peculiar_identifier = one_of("+-".chars());
    let initial = char::letter().or(special_initial);
    let special_subsequent = one_of("+-.@".chars());
    let subsequent = initial
        .to_owned()
        .or(char::digit())
        .or(special_subsequent);
    initial
        .and(many(subsequent))
        .map(|(i, s): (char, String)| Ast::Symbol(format!("{}{}", i, s)))
        .or(peculiar_identifier.map(|s: char| Ast::Symbol(s.to_string())))
        .parse_stream(input)
}

fn quote<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    token('\'')
        .with(parser(expression))
        .map(|val| Ast::new_list(&[Ast::new_symbol("quote"), val], Ast::Nil))
        .parse_stream(input)
}

fn quasiquote<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    token('`')
        .with(parser(expression))
        .map(|val| Ast::new_list(&[Ast::new_symbol("quasiquote"), val], Ast::Nil))
        .parse_stream(input)
}

fn unquote<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    token(',')
        .with(parser(expression))
        .map(|val| Ast::new_list(&[Ast::new_symbol("unquote"), val], Ast::Nil))
        .parse_stream(input)
}

fn unquote_splicing<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    token(',')
        .with(token('@'))
        .with(parser(expression))
        .map(|val| Ast::new_list(&[Ast::new_symbol("unquote-splicing"), val], Ast::Nil))
        .parse_stream(input)
}

fn list<I>(input: I) -> ParseResult<Ast, I>
    where I: Stream<Item = char>
{
    let former = char::spaces().with(many(parser(expression).skip(char::spaces())));
    let dotted = token('.').skip(char::spaces()).with(parser(expression));
    let nil = char::spaces().map(|_| Ast::Nil);
    former
        .and(dotted.or(nil))
        .map(|(former, last): (Vec<_>, _)| Ast::new_list(&former, last))
        .parse_stream(input)
}

```
# compiler
* ASTの定義と、それを命令列に変換する部分
* ASTについて
    * これを「AST」と呼んでいいのかどうかはよくわからない（再）
    * Nil、Boolean、整数(とりあえずi32）、シンボルはそのまんま。Undefinedは`if`で必要。このあたりはそのまんま実行時の値に変換できる
    * リストは、各セルの値をベクタにしたうえで、最後のcdrをまた別に持っている。実行時にはコンスセルに変換することになる
    * 一般的にLispのコンスセルをどう持つべきか、いまいち正解がわからない……
* ASTをコンパイルするのが`compile`。ASTに対してのメソッドにしたけど、それは設計的にどうなんだ
* ローカル変数を探す`location`/`position`について
    * ローカル変数について、最初はHashMapでいいのでは……？とやっていたが、それだと可変長引数が扱えないことに気がつき諦めた
    * いちばん参考にした[「お気楽〜」](http://www.geocities.jp/m_hiroi/func/abcscm33.html)では可変長引数を負値で表していたが、ここではそれぞれの型を作ってパターンマッチできるようにした
* コンパイルには、生成する命令列はもちろん、ローカル変数参照のための情報や、マクロ展開=VMを走らせるのに必要となるグローバル環境を持ち回る必要があって、関数の引数がめっちゃ多くなった

```rust
use value::{Value, vec2cons};
use vm::{Machine, Code, Global, CodeOp, Location, Position};

#[derive(Debug, Clone, PartialEq)]
pub enum Ast {
    Nil,
    Boolean(bool),
    Integer(i32),
    Symbol(String),
    List(Vec<Ast>, Box<Ast>),
    Undefined,
}

type Env = Vec<Ast>;

impl Ast {
    pub fn to_value(&self) -> Value {
        match *self {
            Ast::Nil => Value::Nil,
            Ast::Boolean(b) => Value::Boolean(b),
            Ast::Integer(i) => Value::Integer(i),
            Ast::Symbol(ref s) => Value::Symbol(s.to_owned()),
            Ast::List(ref former, ref last) => {
                vec2cons(&former
                              .iter()
                              .map(|x| x.to_value())
                              .collect::<Vec<Value>>(),
                         last.to_value())
            }
            Ast::Undefined => Value::Undefined,
        }
    }

    pub fn new_symbol(name: &str) -> Ast {
        Ast::Symbol(name.to_owned())
    }

    pub fn new_list(former: &[Ast], last: Ast) -> Ast {
        Ast::List(former.to_owned(), Box::new(last))
    }

    pub fn compile(&self, global: &Global) -> Result<Code, String> {
        let mut env = Vec::new();
        let mut code = Vec::new();
        self.compile_helper(&mut env, &mut code, global)?;
        Ok(code)
    }

    fn compile_helper(&self,
                      env: &mut Env,
                      code: &mut Code,
                      global: &Global)
                      -> Result<(), String> {
        match *self {
            Ast::Symbol(ref name) => {
                if let Some(location) = location(self, env) {
                    code.push(CodeOp::Ld(location));
                } else {
                    code.push(CodeOp::Ldg(name.to_owned()));
                }
                Ok(())
            }
            Ast::List(ref form, ref last) => {
                if **last != Ast::Nil {
                    return Err("proper list required".to_owned());
                }
                if let Some(&Ast::Symbol(ref name)) = form.get(0) {
                    if let Some(&Value::Macro(ref macro_code, _)) = global.get(name) {
                        let mut macro_code = macro_code.to_owned();
                        macro_code.remove(0); // 最後のRtnを削除
                        let macro_args = form[1..].iter().map(|ast| ast.to_value()).collect();
                        let result =
                            Machine::run(vec![macro_args], macro_code, &mut global.to_owned());
                        result
                            .unwrap()
                            .to_ast()
                            .compile_helper(env, code, global)
                    } else {
                        match name.as_str() {
                            "quote" => {
                                if form.len() != 2 {
                                    return Err("malformed quote".to_owned());
                                }
                                code.push(CodeOp::Ldc(form[1].to_owned()));
                                Ok(())
                            }
                            "define" => {
                                if form.len() < 3 {
                                    return Err("malformed define".to_owned());
                                }
                                define(&form[1], &form[2..], env, code, global)
                            }
                            "define-macro" => {
                                if form.len() < 3 {
                                    return Err("malformed define-macro".to_owned());
                                }
                                define_macro(&form[1], &form[2..], env, code, global)
                            }
                            "lambda" => {
                                let (params, body) = form[1..].split_at(1);
                                lambda(params[0].to_owned(), body, env, code, global)
                            }
                            "if" => {
                                let n = form.len();
                                if n < 3 || 4 < n {
                                    return Err("malformed if".to_owned());
                                }
                                let alt = form.get(3);
                                if_(&form[1], &form[2], alt, env, code, global)
                            }
                            "begin" => {
                                if form.len() < 2 {
                                    code.push(CodeOp::Ldc(Ast::Integer(0)));
                                    Ok(())
                                } else {
                                    begin(&form[1..], env, code, global)
                                }
                            }
                            _ => apply(form, env, code, global),
                        }
                    }
                } else {
                    apply(form, env, code, global)
                }
            }
            ref ast => {
                code.push(CodeOp::Ldc(ast.to_owned()));
                Ok(())
            }
        }
    }
}

fn begin(body: &[Ast], env: &mut Env, code: &mut Code, global: &Global) -> Result<(), String> {
    for exp in body.iter().rev() {
        exp.compile_helper(env, code, global)?;
        code.push(CodeOp::Pop)
    }
    code.pop();
    Ok(())
}

fn lambda(params: Ast,
          body: &[Ast],
          env: &mut Env,
          code: &mut Code,
          global: &Global)
          -> Result<(), String> {
    let mut new_env = env;
    new_env.push(params);
    let mut body_code = vec![CodeOp::Rtn];
    begin(body, &mut new_env, &mut body_code, global)?;
    code.push(CodeOp::Ldf(body_code));
    Ok(())
}

fn if_(pred: &Ast,
       conseq: &Ast,
       alt: Option<&Ast>,
       env: &mut Env,
       code: &mut Code,
       global: &Global)
       -> Result<(), String> {
    let mut conseq_code = vec![CodeOp::Join];
    conseq.compile_helper(env, &mut conseq_code, global)?;
    let mut alt_code = vec![CodeOp::Join];
    alt.unwrap_or(&Ast::Undefined)
        .compile_helper(env, &mut alt_code, global)?;
    code.push(CodeOp::Sel(conseq_code, alt_code));
    pred.compile_helper(env, code, global)?;
    Ok(())
}

fn apply(form: &[Ast], env: &mut Env, code: &mut Code, global: &Global) -> Result<(), String> {
    code.push(CodeOp::App(form[1..].len()));
    form[0].compile_helper(env, code, global)?;
    for ast in form[1..].iter().rev() {
        ast.compile_helper(env, code, global)?;
    }
    Ok(())
}

fn define(head: &Ast,
          tail: &[Ast],
          env: &mut Env,
          code: &mut Code,
          global: &Global)
          -> Result<(), String> {
    match *head {
        Ast::Symbol(ref name) => {
            if tail.len() != 1 {
                return Err("malformed define".to_owned());
            }
            code.push(CodeOp::Def(name.to_owned()));
            tail[0].compile_helper(env, code, global)?;
            Ok(())
        }
        Ast::List(ref former, ref last) => {
            if let Some(&Ast::Symbol(ref name)) = former.get(0) {
                code.push(CodeOp::Def(name.to_owned()));
                let params = Ast::new_list(&former[1..], *last.to_owned());
                lambda(params, tail, env, code, global)
            } else {
                Err("malformed define".to_owned())
            }
        }
        _ => Err("malformed define".to_owned()),
    }
}

fn define_macro(head: &Ast,
                tail: &[Ast],
                env: &mut Env,
                code: &mut Code,
                global: &Global)
                -> Result<(), String> {
    match *head {
        Ast::Symbol(ref name) => {
            if tail.len() != 1 {
                return Err("malformed define-macro".to_owned());
            }
            code.push(CodeOp::Defm(name.to_owned()));
            tail[0].compile_helper(env, code, global)?;
            Ok(())
        }
        Ast::List(ref former, ref last) => {
            if let Some(&Ast::Symbol(ref name)) = former.get(0) {
                code.push(CodeOp::Defm(name.to_owned()));
                let params = Ast::new_list(&former[1..], *last.to_owned());
                lambda(params, tail, env, code, global)
            } else {
                Err("malformed define-macro".to_owned())
            }
        }
        _ => Err("malformed define-macro".to_owned()),
    }
}

fn location(sym: &Ast, env: &[Ast]) -> Option<Location> {
    for (i, frame) in env.iter().enumerate() {
        if let Some(j) = position(sym, frame) {
            return Some((i, j));
        }
    }
    None
}

fn position(sym: &Ast, frame: &Ast) -> Option<Position> {
    match *frame {
        Ast::List(ref vec, ref last) => {
            if let Some(i) = vec.iter().position(|x| sym == x) {
                Some(Position::Index(i))
            } else if *sym == **last {
                Some(Position::Rest(vec.len()))
            } else {
                None
            }
        }
        Ast::Symbol(_) => {
            if sym == frame {
                Some(Position::Rest(0))
            } else {
                None
            }
        }
        _ => None,
    }
}
```

# value
* よくあるLispの値たち
* マクロ展開後にASTに戻す必要があるのだけど、直接変換するのがわりあい面倒そうだったので、一度外部表現に直してパースしなおすという手順を踏んでいる
* ヒープを実装しているわけではないので、すごく素直な感じ……になっているはず
    * 今後GCを実装するなら[oxischeme](https://github.com/fitzgen/oxischeme)が参考になるだろうか……と覗いてみたけれど……
    * Arenaに対するMark&Sweepはいいとして、Rootedな値をどう扱っているのかがよくわからない……
    * たぶん今後もわからないので、GCを実装することはあきらめよう……

```rust
use std::fmt;
use std::rc::Rc;
use vm::{Code, Env};
use compiler::Ast;
use reader::read;

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Nil,
    Boolean(bool),
    Integer(i32),
    Symbol(String),
    Cell(Rc<(Value, Value)>),
    Primitive(fn(Vec<Value>) -> Result<Value, String>),
    Closure(Code, Env),
    Macro(Code, Env),
    Undefined,
}

impl Value {
    pub fn to_ast(&self) -> Ast {
        let string = format!("{}", self);
        let (ast, _) = read(&string).unwrap();
        ast[0].to_owned()
    }

    pub fn cons(car: Value, cdr: Value) -> Value {
        Value::Cell(Rc::new((car, cdr)))
    }

    pub fn car(&self) -> Option<Value> {
        match *self {
            Value::Cell(ref cell) => Some(cell.0.to_owned()),
            _ => None,
        }
    }

    pub fn cdr(&self) -> Option<Value> {
        match *self {
            Value::Cell(ref cell) => Some(cell.1.to_owned()),
            _ => None,
        }
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        print(f, self)
    }
}

fn print(f: &mut fmt::Formatter, val: &Value) -> fmt::Result {
    match *val {
        Value::Nil => write!(f, "()"),
        Value::Boolean(ref b) => write!(f, "{}", if *b { "#t" } else { "#f" }),
        Value::Integer(ref i) => write!(f, "{}", i),
        Value::Symbol(ref s) => write!(f, "{}", s),
        Value::Cell(ref cell) => {
            try!(write!(f, "("));
            try!(print_cell(f, cell));
            write!(f, ")")
        }
        Value::Primitive(_) => write!(f, "#<subr>"),
        Value::Closure(_, _) => write!(f, "#<closure>"),
        Value::Macro(_, _) => write!(f, "#<macro>"),
        Value::Undefined => write!(f, "#<undefined>"),
    }
}

fn print_cell(f: &mut fmt::Formatter, pair: &Rc<(Value, Value)>) -> fmt::Result {
    try!(print(f, &pair.0));
    match pair.1 {
        Value::Nil => Ok(()),
        Value::Cell(ref cdr) => {
            try!(write!(f, " "));
            print_cell(f, cdr)
        }
        ref v => {
            try!(write!(f, " . "));
            print(f, v)
        }
    }
}

pub fn vec2cons(former: &[Value], last: Value) -> Value {
    if former.is_empty() {
        last
    } else {
        Value::cons(former[0].to_owned(), vec2cons(&former[1..], last))
    }
}
```

# vm
* 命令列をもとに実際にVMを走らせる部分
* 停止用の命令はなく、命令列が尽きたらスタックトップの値を返すようになっている
* これも参考にした「お気楽〜」そのまんまといえばそのまんまだが、手続きなどに与える引数をまとめるArgs命令はなく、App命令に「引数をいくつとるか」という情報を与える形にしている
* `set!`を実装しようとしたのだけど、うまくいかなかった
    * ローカル環境の値を変更する際に、Eレジスタだけじゃなく、クロージャに保存されている環境の値も変更しなきゃいけないから……だと思う
    * このあたり、Schemeでの実装だと自然と参照先を共有することになるけど、こっちだとコピーしているから……だと思う
    * 必殺`Rc<RefCell<_>>`も試してみたけど、こんどは無限ループが起こったりしてあきらめた
    * あきらめたんだ……！

```rust
use std::collections::HashMap;
use std::fmt;
use compiler::Ast;
use value::{Value, vec2cons};

pub type Global = HashMap<String, Value>;

pub struct Machine {
    stack: Stack,
    env: Env,
    code: Code,
    dump: Dump,
}

type Stack = Vec<Value>;
pub type Code = Vec<CodeOp>;
pub type Env = Vec<Vec<Value>>;
type Dump = Vec<DumpOp>;

#[derive(Debug, Clone, PartialEq)]
pub enum CodeOp {
    Ld(Location),
    Ldc(Ast),
    Ldg(String),
    Ldf(Code),
    App(usize),
    Rtn,
    Sel(Code, Code),
    Join,
    Def(String),
    Defm(String),
    Pop,
}

pub type Location = (usize, Position);

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Position {
    Index(usize),
    Rest(usize),
}

#[derive(Debug, Clone, PartialEq)]
enum DumpOp {
    DumpApp(Stack, Env, Code),
    DumpSel(Code),
}

impl Machine {
    pub fn run(env: Env, code: Code, global: &mut Global) -> Result<Value, String> {
        let mut machine = Machine {
            stack: Vec::new(),
            env: env,
            code: code,
            dump: Vec::new(),
        };
        loop {
            if let Some(op) = machine.code.pop() {
                machine.tick(op, global)?;
            } else {
                match machine.stack.pop() {
                    Some(v) => return Ok(v),
                    None => return Ok(Value::Undefined),
                }
            }
        }
    }

    fn tick(&mut self, op: CodeOp, global: &mut Global) -> Result<(), String> {
        match op {
            CodeOp::Ld(location) => {
                let value = get_var(&self.env, location)
                    .ok_or_else(|| "Runtime error: Ld")?;
                self.stack.push(value);
                Ok(())
            }
            CodeOp::Ldc(ast) => Ok(self.stack.push(ast.to_value())),
            CodeOp::Ldg(name) => {
                let value = global
                    .get(&name)
                    .ok_or_else(|| format!("unbound variable: {}", name))?;
                self.stack.push(value.to_owned());
                Ok(())
            }
            CodeOp::Ldf(code) => {
                self.stack
                    .push(Value::Closure(code, self.env.to_owned()));
                Ok(())
            }
            CodeOp::App(i) => {
                let n = self.stack.len() - 1;
                if i > n {
                    return Err("Runtime error: App".to_owned());
                }
                match self.stack.pop() {
                    Some(Value::Closure(code, mut env)) => {
                        env.push(self.stack.drain(n - i..).collect());
                        self.dump
                            .push(DumpOp::DumpApp(self.stack.to_owned(),
                                                  self.env.to_owned(),
                                                  self.code.to_owned()));
                        self.stack.clear();
                        self.env = env;
                        self.code = code;
                        Ok(())
                    }
                    Some(Value::Primitive(procedure)) => {
                        let result = (procedure)(self.stack.drain(n - i..).collect())?;
                        self.stack.push(result);
                        Ok(())
                    }
                    _ => Err("Runtime error: App".to_owned()),
                }
            }
            CodeOp::Rtn => {
                if let (Some(s), Some(DumpOp::DumpApp(mut stack, env, code))) =
                    (self.stack.pop(), self.dump.pop()) {
                    stack.push(s);
                    self.stack = stack;
                    self.env = env;
                    self.code = code;
                    Ok(())
                } else {
                    Err("Runtime error: Rtn".to_owned())
                }
            }
            CodeOp::Sel(conseq, alt) => {
                let value = self.stack.pop().ok_or_else(|| "Runtime error: Sel")?;
                self.dump.push(DumpOp::DumpSel(self.code.to_owned()));
                if value == Value::Boolean(false) {
                    self.code = alt;
                } else {
                    self.code = conseq;
                }
                Ok(())
            }
            CodeOp::Join => {
                if let Some(DumpOp::DumpSel(code)) = self.dump.pop() {
                    self.code = code;
                    Ok(())
                } else {
                    Err("Runtime error: Join".to_owned())
                }
            }
            CodeOp::Def(name) => {
                let value = self.stack.pop().ok_or_else(|| "Runtime error: Def")?;
                global.insert(name, value);
                Ok(())
            }
            CodeOp::Defm(name) => {
                if let Some(Value::Closure(code, env)) = self.stack.pop() {
                    global.insert(name, Value::Macro(code, env));
                    Ok(())
                } else {
                    unimplemented!()
                }
            }
            CodeOp::Pop => {
                self.stack.pop();
                Ok(())
            }
        }
    }
}

impl fmt::Debug for Machine {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        writeln!(f, "Machine:")?;
        writeln!(f, "  stack: {:?}", self.stack)?;
        writeln!(f, "  env:   {:?}", self.env)?;
        writeln!(f, "  code:  {:?}", self.code)?;
        writeln!(f, "  dump:  {:?}", self.dump)?;
        write!(f, "")
    }
}

fn get_var(env: &[Vec<Value>], location: Location) -> Option<Value> {
    let (i, j) = (location.0, location.1);
    if let Some(frame) = env.get(i) {
        match j {
            Position::Index(index) => {
                if index < frame.len() {
                    Some(frame[index].to_owned())
                } else {
                    None
                }
            }
            Position::Rest(index) => {
                if index <= frame.len() {
                    let (_, rest) = frame.split_at(index);
                    Some(vec2cons(rest, Value::Nil))
                } else {
                    None
                }
            }
        }
    } else {
        None
    }
}
```

# 実際に使ってみる
うちのマシンでは何度かやるとだいたい7秒前後でした。うーむ……まあまあ……ですかね……

```
% cat test.scm
(define (fib n)
  (cond ((eq? n 0) 0)
        ((eq? n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))
(print (fib 30))

% time ./target/release/secd test.scm
832040
./target/release/secd test.scm  7.40s user 0.05s system 99% cpu 7.502 total
```

# 参考にしたページなど
* http://www.geocities.jp/m_hiroi/func/abcscm33.html
    * 冒頭に示したとおり、ほぼ全面的にこちらに倣って実装していった
    * が、`set!`が実装できなかったのでそこであきらめた
    * quasiquoteまわりはかなりの部分引き写し状態になっている
    * ちょいちょいお世話になっています
* http://qiita.com/kmtoki/items/0e9a9e341e6b1d9528af
    * どんな型が必要かといった点で参考にさせていただいた
    * ちょうど昨日同じ@kmtokiさんが[「RustでLispインタープリター」](http://qiita.com/kmtoki/items/cc5bb1204fcba166fd6f)を公開されていて運命を感じた
        * 使っている命令とかが違う
        * 自分はかなりミュータブルなかんじにしているが、正しいのかよくわからない