サンプルコードで身につける: 評価と環境 — 変数の表を外側へ辿り、関数呼び出しごとに新しい表を作る

// 環境(Environment): 変数名 → 値 の表(HashMap)と、外側の環境への参照(outer)。
// 名前を探して無ければ外側へ辿る。これがスコープチェーン。内側で定義した名前は外側から見えない。
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

type EnvRef = Rc<RefCell<Environment>>;

#[derive(Debug, Clone, PartialEq)]
enum RuntimeValue { Undefined, Number(f64), Str(String) }

#[derive(Default)]
struct Environment {
    values: HashMap<String, RuntimeValue>,
    outer: Option<EnvRef>,
}

impl Environment {
    fn new(outer: Option<EnvRef>) -> EnvRef {
        Rc::new(RefCell::new(Environment { values: HashMap::new(), outer }))
    }

    /// 名前を探す。無ければ外側へ(スコープチェーン)
    fn get(&self, name: &str) -> Option<RuntimeValue> {
        match self.values.get(name) {
            Some(v) => Some(v.clone()),
            None => self.outer.as_ref().and_then(|o| o.borrow().get(name)),
        }
    }

    /// この環境に新しく定義する(var / 仮引数)
    fn define(&mut self, name: &str, value: RuntimeValue) {
        self.values.insert(name.to_string(), value);
    }

    /// 既存の変数に代入する。見つかった環境で書き換える。どこにも無ければ false
    fn assign(&mut self, name: &str, value: RuntimeValue) -> bool {
        if self.values.contains_key(name) {
            self.values.insert(name.to_string(), value);
            return true;
        }
        match &self.outer {
            Some(o) => o.borrow_mut().assign(name, value),
            None => false,
        }
    }
}

fn main() {
    // var base = 10;  function f(a) { var local = 'x'; base = 20; ... }  f(5) を呼んだときの 2 つの環境
    let global = Environment::new(None);
    global.borrow_mut().define("base", RuntimeValue::Number(10.0));
    let local = Environment::new(Some(global.clone())); // 関数の中の環境。外側は global
    local.borrow_mut().define("a", RuntimeValue::Number(5.0));
    local.borrow_mut().define("local", RuntimeValue::Str("x".to_string()));

    println!("local.get(\"a\")     = {:?}", local.borrow().get("a"));
    println!("local.get(\"base\")  = {:?}   <- 自分に無いので外側で見つかる", local.borrow().get("base"));
    println!("global.get(\"local\") = {:?}      <- 内側の名前は外から見えない", global.borrow().get("local"));

    let ok = local.borrow_mut().assign("base", RuntimeValue::Number(20.0));
    println!("local.assign(\"base\", 20) = {} -> global.get(\"base\") = {:?}", ok, global.borrow().get("base"));
    let ok = local.borrow_mut().assign("nope", RuntimeValue::Undefined);
    println!("local.assign(\"nope\", ..) = {}  <- どこにも無い(参照実装はこのとき global に作る)", ok);
}

// 関数を呼ぶたびに新しい環境を作り、外側を「定義されたときの環境」にする(クロージャ)。
// return は Completion::Return で呼び出し元まで持ち上げ、残りの文は実行しない。関数宣言はブロックの先頭で先に定義する(巻き上げ)。
use std::{cell::RefCell, collections::HashMap, rc::Rc};
type EnvRef = Rc<RefCell<Environment>>;

#[derive(Debug, Clone)]
enum RuntimeValue { Undefined, Number(f64), Function { params: Vec<String>, body: Vec<Node>, closure: EnvRef } }

#[derive(Debug, Clone)]
enum Node {
    FunctionDeclaration { name: String, params: Vec<String>, body: Vec<Node> },
    ReturnStatement(Box<Node>),
    BinaryExpression { left: Box<Node>, right: Box<Node> }, // + だけ
    CallExpression { callee: String, arguments: Vec<Node> },
    Identifier(String),
    NumericLiteral(f64),
}

#[derive(Debug, Default)]
struct Environment { values: HashMap<String, RuntimeValue>, outer: Option<EnvRef> }

impl Environment {
    fn get(&self, name: &str) -> Option<RuntimeValue> {
        self.values.get(name).cloned().or_else(|| self.outer.as_ref().and_then(|o| o.borrow().get(name)))
    }
}
/// 文の実行結果。return が起きたら呼び出し元まで持ち上げる
enum Completion { Normal(RuntimeValue), Return(RuntimeValue) }
fn exec_block(statements: &[Node], env: &EnvRef) -> Completion {
    for s in statements { // 巻き上げ: 関数宣言を先に全部定義する
        if let Node::FunctionDeclaration { name, params, body } = s {
            let f = RuntimeValue::Function { params: params.clone(), body: body.clone(), closure: env.clone() };
            env.borrow_mut().values.insert(name.clone(), f);
        }
    }
    let mut last = RuntimeValue::Undefined;
    for s in statements {
        match s {
            Node::FunctionDeclaration { .. } => {} // 巻き上げ済み
            Node::ReturnStatement(e) => return Completion::Return(eval(e, env)), // ここで抜ける
            other => last = eval(other, env),
        }
    }
    Completion::Normal(last)
}

fn eval(node: &Node, env: &EnvRef) -> RuntimeValue {
    match node {
        Node::NumericLiteral(n) => RuntimeValue::Number(*n),
        Node::Identifier(name) => env.borrow().get(name).unwrap_or_else(|| panic!("ReferenceError: {} is not defined", name)),
        Node::BinaryExpression { left, right } => match (eval(left, env), eval(right, env)) {
            (RuntimeValue::Number(a), RuntimeValue::Number(b)) => RuntimeValue::Number(a + b),
            _ => RuntimeValue::Undefined,
        },
        Node::CallExpression { callee, arguments } => match env.borrow().get(callee) {
            Some(RuntimeValue::Function { params, body, closure }) => {
                let local = Rc::new(RefCell::new(Environment { values: HashMap::new(), outer: Some(closure) })); // 呼び出しごとに新しい環境
                for (p, a) in params.iter().zip(arguments) {
                    let v = eval(a, env);
                    local.borrow_mut().values.insert(p.clone(), v);
                }
                match exec_block(&body, &local) {
                    Completion::Return(v) => v,
                    Completion::Normal(_) => RuntimeValue::Undefined, // return が無ければ undefined
                }
            }
            _ => panic!("TypeError: {} is not a function", callee),
        },
        other => panic!("文は式の位置に来ない: {:?}", other),
    }
}

fn main() {
    let num = |n| Box::new(Node::NumericLiteral(n));
    let id = |s: &str| Box::new(Node::Identifier(s.to_string()));
    // add(1, 2); function add(a, b) { return a + b; 99 }   ← 呼び出しが宣言より前にある
    let program = vec![
        Node::CallExpression { callee: "add".to_string(), arguments: vec![*num(1.0), *num(2.0)] },
        Node::FunctionDeclaration { name: "add".to_string(), params: vec!["a".to_string(), "b".to_string()], body: vec![
            Node::ReturnStatement(Box::new(Node::BinaryExpression { left: id("a"), right: id("b") })),
            Node::NumericLiteral(99.0), // return の後ろ。実行されない
        ] },
    ];
    let global: EnvRef = Rc::new(RefCell::new(Environment::default()));
    match exec_block(&program, &global) {
        Completion::Normal(v) | Completion::Return(v) => println!("最後の値 = {:?}", v),
    }
    println!("global に a はある? {}  <- 仮引数は呼び出しの環境に入り、呼び終わると捨てられる", global.borrow().get("a").is_some());
}

// 実務に写す: テンプレートの変数展開。サイト全体 → ページ → 繰り返しの 1 件、と環境を重ねる。
// {{name}} は内側の環境から順に探し、無ければ外側へ(スコープチェーン)。内側に同じ名前があれば外側を隠す。
use std::collections::HashMap;
use std::rc::Rc;

struct Environment { values: HashMap<String, String>, outer: Option<Rc<Environment>> }

impl Environment {
    fn new(pairs: &[(&str, &str)], outer: Option<Rc<Environment>>) -> Rc<Environment> {
        let values = pairs.iter().map(|(k, v)| (k.to_string(), v.to_string())).collect();
        Rc::new(Environment { values, outer })
    }

    /// 自分 → 外側 → さらに外側。どこにも無ければ None
    fn get(&self, name: &str) -> Option<&str> {
        match self.values.get(name) {
            Some(v) => Some(v.as_str()),
            None => self.outer.as_ref().and_then(|o| o.get(name)),
        }
    }
}

/// {{name}} を env で引いた値に置き換える。未定義なら {{name}} のまま残す(気づけるように)
fn render(template: &str, env: &Environment) -> String {
    let mut out = String::new();
    let mut rest = template;
    while let Some(start) = rest.find("{{") {
        out.push_str(&rest[..start]);
        let after = &rest[start + 2..];
        match after.find("}}") {
            Some(end) => {
                let name = after[..end].trim();
                out.push_str(env.get(name).unwrap_or(&format!("{{{{{}}}}}", name)));
                rest = &after[end + 2..];
            }
            None => break,
        }
    }
    out.push_str(rest);
    out
}

fn main() {
    let site = Environment::new(&[("site", "study-site"), ("title", "(無題)"), ("currency", "円")], None);
    let page = Environment::new(&[("title", "カート")], Some(site.clone())); // title はサイト既定を隠す
    println!("{}", render("{{title}} | {{site}}", &page));
    let items = [("Rust 本", "3200"), ("キーボード", "9800")];
    for (name, price) in items.iter() {
        let item = Environment::new(&[("name", name), ("price", price)], Some(page.clone())); // 1 件ごとの環境
        println!("  {}", render("- {{name}} {{price}}{{currency}}  ({{title}})", &item));
    }
    println!("{}", render("合計: {{total}}{{currency}}", &page)); // total はどこにも無い
}