Upgrade to Pro — share decks privately, control downloads, hide ads and more …

「Go言語でつくるインタプリタ」を Rust で移植してみた / "Write An Inte...

「Go言語でつくるインタプリタ」を Rust で移植してみた / "Write An Interpreter In Go" In Rust

RustのLT会 Shinjuku.rs #7 @FORCIA
https://forcia.connpass.com/event/146253/

Kei Shiratsuchi

November 19, 2019
Tweet

More Decks by Kei Shiratsuchi

Other Decks in Programming

Transcript

  1. ࣗݾ঺հ • ന౔ɹܛʢγϥπνɹέΠʣ@kei_s • גࣜձࣾϨτϦό • ࣗવݴޠॲཧɺԻ੠ೝࣝɺػցֶश • ੢৽॓ •

    ʮձࣾର߅ͷͲࣗຫେձʯͰ༗໊ͳ৽॓ࡾҪϏϧ • Ruby on Rails / JavaScript / Python / Elixir • Rust ͸ࠓճॳΊͯ৮ͬͨʢͷͰɺποίϛ׻ܴ…ʣ
  2. ֓ཁ • ʰGo ݴޠͰ࡞ΔΠϯλϓϦλʱ • https://www.oreilly.co.jp/books/9784873118222/ • ΛɺRust Ͱ࠶ݱ͢Δ •

    https://github.com/kei-s/waiir • Write An Interpreter In Rust • ຊฤɺ෇࿥(ϚΫϩγεςϜ)Λ׬ྃ • ίϛοτίϝϯτʹ೔هΛॻ͍ͨ
  3. Go ݴޠͰͭ͘ΔΠϯλϓϦλ • ΦϦδφϧͷϓϩάϥϛϯάݴޠͷΠϯλϓϦλΛɺGo ͰΠν͔ Βͭ͘Δ • ֎෦ϥΠϒϥϦΛ࢖༻͠ͳ͍ • ϓϩάϥϜʢจࣈྻʣ

    →
 → ࣈ۟ղੳ →ʢτʔΫϯྻʣ→
 → ߏจղੳ →ʢந৅ߏจ໦ʣ→
 → ධՁ →ʢ࣮ߦ݁Ռʣ
  4. ࠓճ࡞Δݴޠ “Monkey” • Cݴޠ෩ͷߏจ • ม਺ଋറ • ੔਺ͱਅِ஋ • ࢉज़ࣜ

    • จࣈྻσʔλܕ • ഑ྻσʔλܕ • ϋογϡσʔλܕ • ؔ਺ • let age = 1; let name = "Monkey"; let result = 10 * (20 / 2); let myArray = [1, 2, 3, 4, 5]; let myHash = {"name": ”Hi", "age": 28}; myArray[0] // => 1 myHash["name"] // => ”Hi" let add = fn(a, b) { return a + b; }; let add = fn(a, b) { a + b; }; add(1, 2);
  5. ࠓճ࡞Δݴޠ “Monkey” let twice = fn(f, x) { return f(f(x));

    }; let addTwo = fn(x) { return x + 2; }; twice(addTwo, 2); // => 6 let fibonacci = fn(x) { if (x == 0) { 0 } else { if (x == 1) { 1 } else { fibonacci(x - 1) + fibonacci(x - 2); } } }; • Ϋϩʔδϟ • ؔ਺ͷ࠶ؼݺͼग़͠ • ୈҰڃͷߴ֊ؔ਺ •
  6. σϞ • cargo build --release ͯ͠ target/release/waiir Ͱ REPL ىಈ

    • ΋͘͠͸ cargo run • ෳ਺ߦΛड͚෇͚ΒΕͳ͍ͷͰ஫ҙ •
  7. Go ͔Β Rust ΁ • ͠ΜͲ͔ͬͨͱ͜Ζ 2. nil Λฦͤͳ͍ 3.

    ΠϯλʔϑΣʔε͔Β࣮ମΛऔΕͳ͍ 4. ؀ڥͷॴ༗ݖ
  8. nil Λฦͤͳ͍ • ະ࣮૷ͷτʔΫϯͷॲཧ Ͱ nil Λฦͯ͠αϘΕͳ͍ • Result ͰΤϥʔΛฦ͢

    func (p *Parser) parseStatement() ast.Statement { switch p.curToken.Type { case token.LET: return p.parseLetStatement() default: return nil } } fn parse_statement(&mut self, cur_token: Token) -> Result<Statement, ParseError> { Ok( match cur_token.t { TokenType::Let => Statement::LetStatement(self.parse_let_statement()?), _ => return Err(ParseError{message: String::from("not implemented")}) } ) }
  9. ΠϯλʔϑΣʔε͔Β࣮ମΛऔΕͳ͍ • Go Ͱ͸ΠϯλʔϑΣʔε͔Β࣮ମΛऔΕΔ • ast.Expression ͱͯ͠౉͖ͬͯͨ exp Λɺast.Boolean Ͱ͋Δ͔

    νΣοΫ͍ͯ͠Δ • Rust ͷ trait Ͱ͸ෆՄೳ func testBooleanLiteral(t *testing.T, exp ast.Expression, value bool) bool { bo, ok := exp.(*ast.Boolean) if !ok { t.Errorf("exp not *ast.Boolean. got=%T", exp) return false } …
  10. ΠϯλʔϑΣʔε͔Β࣮ମΛऔΕͳ͍ • Enum ͷྻڍࢠʹ࣮ࡍͷσʔλΛ֨ೲ͠ɺύλʔϯϚο νͰ࣮ମΛ࢖͏ enum Expression { Integer(IntegerExpression), Boolean(BooleanExpression),

    ... } #[test] fn test_boolean_expressions() { ... if let Expression::Boolean(boolean) = &stmt.expression { assert_eq!(boolean.value, *expected); } else { assert!(false, "program.statements[0] is not ast::BooleanExpression") }
  11. ؀ڥͷॴ༗ݖ • let a = 1; Λอଘ͢ΔͨΊʹɺΩʔ ”a”ɺ஋ Integer(1) ͱͯ͠อଘ͢Δ

    • ஋Λଋറ͢ΔͨΊͷɺ؀ڥ(Environment)ɻத਎͸ϋογϡϚοϓ type Environment struct { store map[string]Object } func (e *Environment) Get(name string) (Object, bool) { obj, ok := e.store[name] return obj, ok } func (e *Environment) Set(name string, val Object) Object { e.store[name] = val return val }
  12. ؀ڥͷॴ༗ݖ • ؔ਺͕ఆٛ͞ΕͨΒɺ؀ڥΛؔ਺ΦϒδΣΫτʹ౉͠ ͓ͯ͘ • ࣮ߦ࣌ʹɺͦͷ؀ڥΛݩʹ࣮ߦ͢Δ func Eval(node ast.Node, env

    *object.Environment) object.Object { ... case *ast.FunctionLiteral: params := node.Parameters body := node.Body return &object.Function{Parameters: params, Env: env, Body: body}
  13. ؀ڥͷॴ༗ݖ • Rust ൛Ͱ͸࠷ॳɺؔ਺ΦϒδΣΫτ͕࣋ͭ env ͸ clone() ͯ͠౉͍ͯͨ͠ • ͔͠͠࠶ؼؔ਺ͰΤϥʔ

    • ؔ਺ΦϒδΣΫτ͕࣋ͭ env ʹɺޙ͔Β { “fibonacci”: ؔ਺ΦϒδΣΫτ} Λొ ࿥͠ͳ͍ͱ͍͚ͳ͍ͨΊ impl_eval!(FunctionLiteral => (self, env) { Object::Function(Function { parameters: self.parameters.clone(), body: *self.body.clone(), env: env.clone(), }) }); let fibonacci = fn(x) { ... fibonacci(x - 1) + fibonacci(x - 2); };
  14. ؀ڥͷॴ༗ݖ • Rc/RefCell Λ࢖ͬͯղܾ͠ ͨ • ಉҰͷ env Λผʑʹॴ ༗ͤ͞ΔͨΊʹ

    Rc Λ࢖ ͏ • Env ΛมߋͰ͖ΔΑ͏ ʹ RefCell Λ࢖͏ impl Environment { pub fn new() -> Rc<RefCell<Environment>> { let store = HashMap::new(); let env = Environment { store, outer: None }; Rc::new(RefCell::new(env)) } } impl_eval!(FunctionLiteral => (self, env) { Object::Function(Function { parameters: self.parameters.clone(), body: *self.body.clone(), env: Rc::clone(&env), }) });
  15. ࠓޙ • ஌ࣝෆ଍ͷͨΊɺແବʹ clone() ͯ͠ޡຐԽ͍ͯ͠ΔՕॴ͕͍ͭ͘ ΋͋Δ… • ΍ͬͺΓϥΠϑλΠϜཧղ͠੾Ε͍ͯͳ͍ • HashMap

    ʹొ࿥ͨ͠ value ͷॴ༗ݖ೉͍͠ • ొ࿥ͨ͠ value Λͦͷ··มߋ͍ͨ͠৔߹Ͳ͏͢Ε͹ྑ͍…? • Rust తʹ៉ྷʹ͢ΔͱɺGo ͰͷΞʔΩςΫνϟ͔Β͔ͳΓဃ཭ ͦ͠͏…