Rust で遅延評価を 実装してみる

RustのLT会！ Rust入門者の集い #3

Transcript

1. Rust Ͱ஗ԆධՁΛ ࣮૷ͯ͠ΈΔ RustͷLTձʂ Rustೖ໳ऀͷू͍ #3 @Linda_pp @rhysd 
2. ͋Β͢͡ • ७ਮؔ਺ܕσʔλߏ଄ΛಡΈͳ͕ Β Rust Ͱ࣮૷͍ͯͨ͋͠Δ೔ɼ ஗ԆධՁΛ࢖͏σʔλߏ଄͕ग़ݱ • Rust ͸஗ԆධՁ͡Όͳ͍… • ࣮૷ͨ͠ https://goo.gl/qMGuZQ 
3. ஗ԆධՁͱ͸ ࣜΛ͙͢ʹ͸ධՁͤͣɼඞཁʹͳͬͨ࣌ʹධ Ձ͢Δ 
4. ஗Ԇ͠ͳ͍ධՁ 1 // 1000ݸͷૉ਺Λͭ͘ΔʢΊͬͪΌॏ͍ॲཧʣ 2 let n = primes1000(); 3 4 // ... 5 6 // 100൪໨දࣔ 7 println!("{}", vec[99]); 8 9 // 1000൪໨දࣔ 10 println!("{}", vec[999]);  ιʔεɿ https://goo.gl/qMGuZQ
5. ஗ԆධՁ 1 // lazily! Ͱғ·Εͨࣜ͸஗ԆධՁ͞ΕΔ 2 // ͜ͷ࣌఺Ͱ͸ vec ͸ܭࢉ͞Ε͍ͯͳ͍ 3 let vec = lazily!{ 4 prime1000th() 5 }; 6 7 // vec Λ࢖༻͢ΔλΠϛϯάͰॳΊͯ vec ΛධՁ 8 println!("{}", vec[99]); 9 10 // Ұ౓ධՁͨ݁͠Ռ͸Ωϟογϡ͞Εͯ࢖͍·Θ͞ΕΔ 11 println!("{}", vec[999]);  ιʔεɿ https://goo.gl/qMGuZQ
6. σʔλͷ࣋ͪํ 1 // αϯΫɿܭࢉΛද͢σʔλߏ଄ 2 enum Thunk<'a, T: 'a> { 3 // ·ͩܭࢉ͞Εͯͳ͍ঢ়ଶΛΫϩʔδϟͰ࣋ͭ 4 NotYet(Box<Fn() -> T + 'a>), 5 // ܭࢉࡁΈ 6 Memo(T), 7 } 8 9 // ஗Ԇ͞ΕͨࣜΛද͢ߏ଄ମ Delayed 10 pub struct Delayed<'a, T: 'a> { 11 thunk: RefCell<Box<Thunk<'a, T>>> 12 }  ιʔεɿ https://goo.gl/qMGuZQ
7. σʔλͷ࣋ͪํ 1 impl<'a, T: 'a> Delayed<'a, T> { 2 // ৽͍͠஗ԆධՁࣜΛੜ੒ 3 // ΫϩʔδϟΛड͚औͬͯ RefCell ʹಥͬࠐΉ 4 pub fn new<F>(f: F) -> Self where F: Fn() -> T + 'a { 5 Delayed { thunk: RefCell::new( 6 Box::new( 7 NotYet(Box::new(f)) 8 ) 9 ) } 10 } 11 } 12 13 // ϚΫϩͰ move Ωϟϓνϟ͢ΔΫϩʔδϟʹల։͢Δ 14 // lazily!{42} -> Delayed::new(move || { 42 }) 15 #[macro_export] 16 macro_rules! lazily { 17 ($($b:tt)+) => { 18 self::Delayed::new(move || { $($b)+ }) 19 } 20 }  ιʔεɿ https://goo.gl/qMGuZQ
8. force: ஗Ԇ͞ΕͨࣜΛධՁ 1 impl<'a, T: 'a> Delayed<'a, T> { 2 pub fn force(&self) { 3 // ͜͜Ͱ mut ʹ͠ͳ͍ͱαϯΫ͕ߋ৽Ͱ͖ͳ͍ͷͰɼ 4 // RefCell ͰแΉ 5 let mut thunk = &mut *self.thunk.borrow_mut(); 6 let val = match **thunk { 7 // ະධՁͳΒอ͍࣋ͯͨ͠ΫϩʔδϟΛ࣮ߦ͠ɼ 8 // ܭࢉΛ࣮ߦ͢Δɽ 9 NotYet(ref invoke) => { 10 Box::new(Memo(invoke())) 11 }, 12 // ͢ͰʹܭࢉࡁΈͳΒԿ΋͠ͳ͍ 13 Memo(_) => return, 14 }; 15 // ܭࢉͨ͠஋Λ͓࣋ͬͯ͘ 16 *thunk = val; 17 } 18 }  ιʔεɿ https://goo.gl/qMGuZQ
9. ஗ԆධՁͷλΠϛϯά Rc<T> ͕΍͍ͬͯΔΑ͏ʹɼDerefτϨΠτ Λ࢖ͬͯɼϝιουݺͼग़͠ͷλΠϛϯάͰ ࣗಈͰத਎͕ධՁ͞ΕΔΑ͏ʹ͢Δ 1 let s = lazily!("foo".to_string()) 2 3 // s ͕ࣗಈͰධՁ͞ΕΔ 4 s.as_str(); 5 6 // * ԋࢉࢠͰ໌ࣔతʹධՁ΋Ͱ͖Δ 7 *s;  ιʔεɿ https://goo.gl/qMGuZQ
10. Deref Ͱࢀর࣌ʹࣗಈධՁ 1 impl<'a, T: 'a> Deref for Delayed<'a, T> { 2 // T ͕ධՁ݁Ռͷ஋ͷܕ 3 type Target = T; 4 fn deref(&self) -> &T { 5 self.force(); 6 // RefCell ͷத਎ΛҰ࣌తʹऔΓग़͢ 7 let thunk = unsafe { 8 self.thunk.as_ptr().as_ref().unwrap() 9 }; 10 match **thunk { 11 // αϯΫͷத΁ͷࢀরΛฦ͢ 12 Memo(ref v) => v, 13 _ => unreachable!(), 14 } 15 } 16 }  ιʔεɿ https://goo.gl/qMGuZQ
11. ͭͬͨ͘஗ԆධՁͰ஗ԆϦετ Λͭͬͨ͘ײ૝ • ΄΅ॻ੶಺ͷઆ໌௨Γʹίʔυ͕ॻ͚ͯྑ͍ײ͡ • Deref ͸༧૝֎ͷλΠϛϯάͰܭࢉ͕࣮ߦ͞Εͯ͠· ͏͜ͱ͕͋ͬͨɽ • Clone Λ࣮૷͢ΔͨΊʹ݁ہ Box Λ Rc ʹ͢Δඞཁ͕ ͋ͬͨ • ϜʔϒΩϟϓνϟͰण໋͕བྷΉͷͰɼlazily! Ͱੜ੒͠ ͨ஋ͷѻ͍͕Ϝζ͍  ιʔεɿ https://goo.gl/qMGuZQ