自作言語進捗 2019 Mar

Transcript

1. ࣗ࡞ݴޠਐḿ 2019 Mar @todesking
2. ͋Β͢͡ • 1݄͝Ζ͔Βࣗ࡞ݴޠΛ࡞Γ࢝ΊͨͷͰɺͨ·ʹਐḿΛใ ࠂ͠Α͏ͱࢥ͍·͢…… • ಈػ • Ұ෦ͰCίϯύΠϥࣗ࡞͕ྲྀߦͬͯͨ • ܕγεςϜͷ࣮ݧ͕͍ͨ͠ • JVMͰಈ͘MLܥݴޠΛ࡞͍ͬͯ·͢ • ηϧϑϗεςΟϯά΋໨ඪͱ͢Δ • https://github.com/todesking/ojaml
3. ࢓༷ • MLϕʔε • Standard ML, OCamlͳͲ͕༗໊ • ௚ܥͰ͸ͳ͍͕ɺHaskell΋ӨڹΛड͚͍ͯΔ • ϓϩάϥϛϯάݴޠͷݚڀͰΑ͘࢖ΘΕͯΔ • ؔ਺ܕݴޠ • call-by-value • ෭࡞༻͋Γ • ܕਪ࿦ • λʔήοτ͸JVM • ΫϥεϑΝΠϧΛग़ྗ͢ΔίϯύΠϥ • ܕγεςϜͷ࣮ݧ͚ͩͳΒΠϯλϓϦλͰ͍͍ΜͰ͕͢ɺ কདྷతʹηϧϑϗετ͍ͨ͠ͷͰίϯύΠϥʹ
4. ਐḿ Ϟδϡʔϧ Ϟδϡʔϧม਺ ؔ਺ ϩʔΧϧม਺(let/let rec) جຊతͳ੔਺ԋࢉ ݪ࢝తͳܕਪ࿦ Java FFI ADT ·ͱ΋ͳܕਪ࿦(HM) ύϥϝτϦοΫଟ૬ letଟ૬ Refinement types ηϧϑϗεςΟϯά
5. ͜Μͳͷ package test.ml0 import com.todesking.ojaml.ml0.lib.Predef.- import com.todesking.ojaml.ml0.lib.Predef.== module Example { let x = let rec is_even: int => bool = fun n: int => if n == 0 then true else is_odd (n - 1) ; is_odd: int => bool = fun n: int => if n == 0 then false else is_even (n - 1) in is_even 99 ;; (* x == false *) }
6. ͜Μͳͷ package test.ml0 import com.todesking.ojaml.ml0.lib.Predef.- import com.todesking.ojaml.ml0.lib.Predef.== module Example { let x = let rec is_even: int => bool = fun n: int => if n == 0 then true else is_odd (n - 1) ; is_odd: int => bool = fun n: int => if n == 0 then false else is_even (n - 1) in is_even 99 ;; (* x == false *) } Ϟδϡʔϧ Ϟδϡʔϧม਺ JNQPSU ύοέʔδએݴ ϩʔΧϧม਺ ؔ਺ఆٛ JG ೋ߲ԋࢉࢠ ؔ਺ݺͼग़͠ ίϝϯτ
7. ͜Μͳͷ • ͋ͱ͸Javaͷϝιουݺͼग़͠ߏจͳͲ java.lang.Integer##valueOf(10)
8. ίϯύΠϥͷߏ੒ • Parser: ιʔείʔυ͔ΒAST΁ͷม׵ • Namer: Ϋϥε໊΍ม਺໊ͷղܾ • Typer: ܕ෇͚ • Assember: όΠτίʔυ΁ͷม׵ Source Raw AST Named AST Typed AST Bytecode Parser Namer Typer Assembler
9. Parser • ιʔείʔυจࣈྻΛղੳͯ͠໦ߏ଄(Raw AST)ΛಘΔ • ߏจΤϥʔ͸͜ͷஈ֊ͰνΣοΫ struct A { let x = 1 ;; } Struct(name = "A") Let( name = "x", body = LitInt(1))
10. Namer • ϓϩάϥϜ಺ʹग़ݱ͢Δ໊લ͕ԿΛࢦ͢ͷ͔ղܾ͢Δ • "Integer": java.lang.IntegerΫϥε • fun಺ͷ"x": 1൪໨ͷϩʔΧϧม਺ • ະ஌ͷ໊લ͕ग़ݱͨ͠ΒΤϥʔ • Named ASTΛग़ྗ // ຊ౰͸Raw AST import java.lang.Integer module A { let x = Integer##valueOf(1);; let f = fun x: int => x ;; } Struct(name="A") Let("x") App Class(java.lang.Integer) "valueOf" LitInt(1) Let("f") Fun(int) Local(1, 0)
11. Typer • ܕΛਪ࿦͠ɺ੔߹ੑΛνΣοΫ͢Δ • Typed ASTΛग़ྗ Struct(name="A") Let("x"): Integer JCallStatic: Integer Method(Integer.valueOf) LitInt(1): int Let("f"): int -> int Fun(int): int -> int Local(1, 0): int Struct(name="A") Let("x") App Class(java.lang.Integer) "valueOf" LitInt(1) Let("f") Fun(int) Local(1, 0)
12. Assembler • Typed AST͔ΒΫϥεϑΝΠϧΛੜ੒͢Δ • ͜ͷม׵ͰΤϥʔ͸ൃੜ͠ͳ͍ class A { public static Integer x; public static Integer f; static { x = Integer.valueOf(1); f = new A$1(); } } class A$1 { ... } Struct(name="A") Let("x"): Integer JCallStatic: Integer Method(Integer.valueOf) LitInt(1): int Let("f"): int -> int Fun(int): int -> int Local(1, 0): int
13. ίϯύΠϧ: Ϟδϡʔϧ • Ϟδϡʔϧ͸Ϋϥεɺϝϯό͸staticϑΟʔϧυʹϚοϐ ϯά͞ΕΔ • ϝϯόͷ஋͸staticΠχγϟϥΠβ಺ͰॳظԽ͞ΕΔ package a module X { let x = 10 ;; let y = x + 1 ;; } package a class X { static int x, y; static { x = 10; y = x + 1; } }
14. ίϯύΠϧ: ୯७ͳࣜ • JavaͰදݱ͢Δͱɺׂͱͦͷ··(όΠτίʔυϨϕϧͷ ࿩Λ͢Δͱ௕͘ͳΔͷͰ΍Ί·͢) let x = if true then 1 else 2 if(true) x = 1 else x = 2
15. ίϯύΠϧ: ؔ਺ݺͼग़͠ • ؔ਺͸FunΫϥεͷαϒΫϥεͱ࣮ͯ͠૷͞ΕΔ • ΧϦʔԽͷͨΊɺؔ਺͸͢΂ͯ1Ҿ਺ͱͳΔ • ؔ਺ΦϒδΣΫτͷapp(Object): ObjectΛݺͿ͚ͩ • Ҿ਺ɾฦΓ஋͸దٓboxing͢Δ f 1 2 f = ... g = f.app(1) x = ((Fun)g).app(2) result = ((Integer)x).intValue
16. ίϯύΠϧ: ೋ߲ԋࢉࢠ • ؔ਺ݺͼग़͠ͷγϯλΫεγϡΨʔ x + 1 => (+) x 1
17. ίϯύΠϧ: ੔਺ԋࢉ • ੔਺ʹؔ͢Δԋࢉࢠ͸PredefͷϝιουΛݺΜͰ͍Δ • ࣮ࡍͷॲཧ͸JavaͰॻ͔ΕͨϥϯλΠϜ಺ʹهड़ x + 1 => Predef.+ x 1 (* Predef *) let + = fun x => fun y => runtime.Int##add(x, y) // runtime.Int int add(int x, int y) = x + y;
18. ίϯύΠϧ: ؔ਺ఆٛ • FunΫϥεͷαϒΫϥεͱ࣮ͯ͠૷ • ίϯετϥΫλͷҾ਺͸ޙड़ fun x: int => x + 1 class Fun$0(parent: Fun, local: Object) extends Fun(parent, local) { Object app(x: Object) = (int)x + 1 }
19. ίϯύΠϧ: ؔ਺ఆٛ • ؔ਺͕ωετͨ͠৔߹ • ؔ਺͝ͱʹΫϥε͕ੜ੒͞ΕΔ • Fun$1ͷੜ੒࣌ɺFun$0ͷҾ਺ͱͯ͠౉͞ΕͨxΛίϯετϥΫλʹ౉͍ͯ͠Δ • getLocal(1, 0) Ͱ depth = 1, index = 0 ͷ஋(͜ͷ৔߹Fun$1.local)Λऔಘ • indexʹ͍ͭͯ͸ޙड़(let recͰ࢖༻) fun x: int => fun y: int => x + y class Fun$0(parent: Fun, local: Object) extends Fun(parent, local) { int depth = 0 Object app(x: Object) = new Fun$1(this, x) } clas Fun$1(...) extends Fun(...) { int depth = 1 Object app(y: Object) = { val x = getLocal(1, 0) (int)x + (int)y } }
20. ίϯύΠϧ: ม਺ࢀর • ਤͰ͢ class Fun$0 depth = 0 local = null let f = fun x: int => // F0 fun y: int => // F1 x + y let g = f 10 class Fun$1 depth = 1 local = 10 g f def app(x: Any) = new Fun$0(this, x) def app(y: Any) = getLocal(1,0) + y
21. ίϯύΠϧ: letࣜ • Ϟδϡʔϧม਺Ͱ͸ͳ͘ɺࣜͱͯ͠࢖͏΄͏ͷlet • ؔ਺ఆٛ+ݺͼग़͠Ͱ࣮૷Մೳ • ܕਪ࿦ͷؔ܎্ɺ಺෦తʹ͸۠ผͯ͠ѻ͍ͬͯ·͢ • ௨ৗͷؔ਺ఆٛ͸ԾҾ਺ͷܕΛ໌ࣔ͢Δඞཁ͕͋Δ • letͷ৔߹͸࣮Ҿ਺ͷܕ͔Βਪ࿦Մೳ let tmp = 1 in tmp * 10 ;; // ࠨͷίʔυͱ౳Ձ (fun tmp: int => tmp * 10) 1 ;;
22. ίϯύΠϧ: let rec • จ๏ͷ֬ೝ • let rec x1 = e1; x2 = e2; ... in body • એݴ͞Εͨม਺x1, x2, ... ͸ɺ ࣜe1, e2, ..., body͔ΒࢀরՄ ೳ let rec is_even: int => bool = fun x: int => if x == 0 then true else is_odd (n - 1) ; is_odd: int => bool = fun x: int => if x == 0 then false else is_even (n - 1) in is_even 99
23. ίϯύΠϧ: let rec • Մม഑ྻΛڞ༗͓͖ͯ͠ɺޙ͔Β஋Ληοτ͢Δ • ม਺΁ͷࢀর͸഑ྻཁૉ΁ͷࢀরʹஔ͖׵͑Δ let rec is_even: int => bool = fun x: int => if x == 0 then true else is_odd (n - 1) ; is_odd: int => bool = fun x: int => if x == 0 then false else is_even (n - 1) in is_even 99 // ٖࣅίʔυ let body env = env[0] := fun x => ... else env[1] (n-1) env[1] := fun x => ... else env[0] (n-1) env[0] 99 in body (new Array[2])
24. ίϯύΠϧ: let rec • ਤʹ͢Δͱ͜͏ͳΔ class Fun$0 depth = 0 local = null let rec f = fun ... g = fun ... in f 1 def app(env: Array) = { env(0) = new Fun$1(this, env) env(1) = new Fun$2(this, env) env(0).app(1) } class Fun$1 depth = 1 local = env class Fun$2 depth = 1 local = env f g
25. ࠓޙͷ༧ఆ • ܕਪ࿦΍Δͧʂʂʂʂʂʂʂ