FP 05: Lazy Evaluation ขี้เกียจไว้ก่อนแล้วดีเอง?!

developer

บทความชุด: Functional Programming

รวมเนื้อหาเกี่ยวกับการเขียนโปรแกรมแนว Functional และหัวข้ออื่นๆ ที่เกี่ยวข้อง

- ตอนที่ 0 บทนำ, ก้าวแรกสู่โลกแห่ง Functional Programming
- ตอนที่ 1 Pure, First-Class, High-Order, พื้นฐานแห่ง Functional Programming
- ตอนที่ 2 Lambda Function and Closure ฟังก์ชันทันใจและพื้นที่ปิดล้อม!
- ตอนที่ 3 map filter reduce และเพื่อนๆ พระเอกแห่งโลก Functional
- ตอนที่ 4 โครสร้างแบบ Pair และ Either กับ List Comprehension การสร้างลิสต์ฉบับฟังก์ชันนอล
- ตอนที่ 5 Lazy Evaluation ขี้เกียจไว้ก่อนแล้วดีเอง?!
- ตอนที่ 6 Recursive Function ฟังก์ชันเวียนเกิด, เขียนลูปไม่ได้ทำยังไง? มาเขียนฟังก์ชันเรียกตัวเองแทนกันเถอะ!
- ตอนที่ 7 Curry, Partial Function
- ตอนที่ 8 Functor, Monad
- [บทความปี 2015] มารู้จักกับ Functional Programming สิ่งที่คุณต้องรู้ในตอนนี้กันเถอะ
- Function ทำงานยังไง?, ในมุมมองของโปรแกรมเมอร์สาย Imperative

---

Category Theory & Lambda Calculus

- ตอนที่ 1 บทนำ Category Theory ~ จากคณิตศาสตร์สู่ภาษาโปรแกรม
- ตอนที่ 2 Functor ~ คืออะไร
- ตอนที่ 3 Product Structure ^{(by Mu)}
- ตอนที่ 4 Co-Product Structure ^{(by Mu)}
- Lambda Calculus ~ พื้นฐานสู่ Functional Programming

ในบทนี้เราจะแบ่งออกเป็น 2 พาร์ท นั่นคือคอนเซ็ปของการใช้ Lazy ในภาษาสาย FP แท้ๆ กับการนำคอนเซ็ปนี้ไปใช้ในภาษาทั่วๆ ไปนะ ... ซึ่งช่วงแรก เราจะขออธิบายกันด้วยภาษา haskell (อ่านไม่ยากหรอก ฮา)

Laziness Evaluation

คำนี้ถ้าแปลเป็นภาษาไทยก็คงประมาณ "การประมวลผลแบบขี้เกียจ" ซึ่งฟังดูไม่ดีเท่าไหร่นะ ขอแปลแบบเข้าใจง่ายๆ ว่า "การประมวลผลเมื่อต้องใช้งานตอนนั้น" แทนละกัน

ในบทก่อนเราสอนวิธีการสร้างลิสต์ในรูปแบบ List Comprehension ไปแล้ว

เช่นถ้าเราต้องการลิสต์ของตัวเลข 1-1000 เราก็อาจจะเขียนได้แบบนี้
ในฐานะที่เรากำลังคุยเรื่อง FP กันอยู่ ขอยกตัวอย่างด้วยภาษาสายฟังก์ชันนอลแท้ๆ อย่าง haskell กันก่อนละกัน

evenNumbers = [1,2..1000]

แต่ใน haskell เราสามารถสร้างลิสต์แบบนี้ได้ด้วย

evenNumbers = [1,2..]

ในลิสต์ตัวแรก เราอ่านออกว่าต้องการสร้างตัวเลข 1-1000 ขึ้นมา

แต่ในลิสต์ตัวที่สอง เราตัดค่าตัวสุดท้ายทิ้งไป ... แล้วแบบนี้มันจะสร้างลิสต์ไปจนถึงตัวไหนกันล่ะ?

คำตอบก็คือ .. ไม่มีตัวสิ้นสุดยังไงล่ะ!!

สำหรับคนที่เคยเขียนโปรแกรมมาน่าจะรู้ว่าเราไม่สามารถสร้างลิสต์ของเลขแบบไม่รู้จบได้ เพราะตัวเลขแต่ละตัวต้องการพื้นที่ในเมโมรี่ และการสร้างตัวเลขไปเรื่อยๆ แบบนั้น ที่จุดหนึ่งก็จะทำให้เมโมรี่เต็ม!

สำหรับมนุษย์น่ะ อาจจะไม่มีปัญหา เราสามารถทำความเข้าใจคำว่าลิสต์ของตัวเลข 1, 2, 3, 4, ... ไปเรื่อยๆ ได้ เราสามารถทำความเข้าใจได้ว่านี่คือลิสต์ที่มีตัวเลขไล่ไปเรื่อยๆ เป็นล้านๆ ตัวได้เลย โดยที่เราไม่ได้จำตัวเลขทั้งหมดนั้นไว้ทั้งหมด แต่เราจำว่ามันคือลิสต์ที่เป็นเลขต่อๆ กัน แล้วเมื่อจะใช้งาน ค่อยคิดว่ามันจะต้องเป็นเลขอะไร

และนั่นแหละ มันคือสิ่งที่เรียกว่า "Lazy Evaluation"

ลิสต์แบบปกติเราจะเรียกว่ามันเป็น Static List นั่นคือลิสต์ที่มีข้อมูลพร้อมทุกตัวตั้งแต่แรกที่สร้างลิสต์ขึ้นมา แต่ถ้าเป็นลิสต์แบบ Lazy มันจะสร้างไอเทมแค่บางตัวไว้ตอนแรกเท่านั้น ส่วนตัวที่เหลือถือว่ามีนะ แค่ยังไม่ได้สร้างขึ้นมาเท่านั้นเอง

ลองดูตัวอย่างเวลาเราใช้งาน Lazy List กัน เริ่มต้นด้วยลิสต์ [1,2..] ที่มีเลขแค่สองตัว

ต่อมา ถ้าเรามีการ access ข้อมูลตัวไหนก็ตาม ลิสต์จะเช็กเองว่าข้อมูลตัวนั้นเคยสร้างขึ้นมารึยัง ถ้ายังไม่ได้สร้าง ก็จัดการสร้างมันซะจังหวะนี้แหละ

ข้อสังเกตอีกอย่างนึงคือ ตอนที่เรา access ไปถึงข้อมูล index 4 นั้น เราข้าม index 3 ไปนะ แต่ลิสต์มันก็สร้างตัวที่ index 3 ให้เราด้วยนะ เพราะ Lazy List จะสร้างไอเทมเรียงกัน ไม่กระโดดข้าม ถ้าต้องการไอเทมตัวท้ายๆ ก็ต้องสร้างตัวข้างหน้ามันให้เสร็จซะก่อน

เมื่อ FP มีฟีเจอร์แบบนี้ ทำให้เราสามารถสร้าง "ลิสต์ปลายเปิด" ที่ไม่ได้บอกว่าจะไปจบที่เลขเท่าไหร่ได้ยังไงล่ะ

ก่อนจะจบส่วนของเนื้อหา ลองมาดูตัวอยากการประยุกต์ใช้ Lazy กันหน่อย

Fibonacci Number

ลำดับฟีโบนัชชีคืออะไร ถ้ายังไม่รู้อ่านก่อนได้ที่ https://th.wikipedia.org/wiki/จำนวนฟีโบนัชชี

ถ้าสรุปง่ายๆ มันคือลำดับตัวเลขที่มาจากการบวกตัวเลข 2 ตัวข้างหน้า

Fibonacci Number:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

ซึ่งเราสามารถสร้างลิสต์ fibo ในภาษา haskell ได้แบบนี้

fibo = 1 : 1 : [a + b | (a, b) <- zip fibo (tail fibo) ]

อาจจะอ่านไม่รู้เรื่องว่ามันคืออะไรกัน (ฮา) ไม่เป็นไร เรากำลังจะอธิบายต่อ

• สำหรับ fibo นั้นต้องเริ่มด้วยตัวเลขคู่แรก กำหนดมาก่อนเป็น 1 และ 1 (บางครั้งก็นับว่าเริ่มด้วย 0 และ 1 แต่ในเคสนี้ขอเริ่มด้วยคู่แลขแบบแรกละกัน)
• เมื่อเรามีเลขคู่แรกเป็นตัวตั้งต้นแล้ว เราก็เลยกำหนดว่าชุดตัวเลขหลังจากนี้ (ลิสต์) เราจะสร้างมาจากลิสต์อีก 2 ตัว นั่นคือ fibo และ tail fibo
• เราจะเอาลิสต์ 2 ตัวนั้นมา zip กัน แล้ว + เป็นค่าตัวใหม่

ใครจำว่า zip และ tail คืออะไรอ่านทวนได้ใน บท 3 และ บทที่ 4 ได้เลยนะ

ดังนั้น ตอนเริ่มเราจะได้ลิสต์ fibo ที่มีหน้าตาแบบนี้ [1, 1, ...]

คำถามคือตัวต่อไปจะมาจากไหนล่ะ? ในโค้ดบอกว่าให้จับลิสต์ fibo ก็คือลิสต์ของตัวมันเองนั่นแหละ ที่ตอนนี้มีแค่ [1, 1] มา zip กัน (แต่ตัวนึง สั่งให้ tail ด้วย ก็คือตัดตัวแรกสุดทิ้งไป)

นั่นก็คือเราจะหยิบตัวเลขตัวแรกสุดของลิสต์ทั้งสองตัวออกมา คือ (1) และ (1) แล้วเอามาบวกกัน = 2

แล้วใส่เลขตัวนั้นต่อลิสต์ fibo ลงไป (สรุปคือตอนนี้ fibo = [1, 1, 2, ...] นะ)

ถึงตอนนี้อาจจะสงสัยว่า งั้นตัวเลขของเราก็หมดแล้วน่ะสิ !?

อย่าลืมว่า ลิสต์ที่เราเอาไว้ดึงตัวเลขตัวถัดไปของเรา มันไม่ใช่ static list หรอกนะ มันคือ lazy list ที่ชื่อว่า fibo นะ

เพราะลิสต์ที่เรากำลังสร้างอยู่ชื่อว่า fibo แถมลิสต์ที่เอาไว้ดึงค่าตัวต่อไปก็ดันอ่านมาจากลิสต์ fibo อีก!

ก็แสดงว่าเมื่อเรามีไอเทมเพิ่มเข้ามาใน fibo ลิสต์ทางขวา (ดูในรูป) ก็จะได้ไอเทมเพิ่มไปด้วยโดยอัตโนมัติ (เพราะจริงๆ มันคือลิสต์เดียวกัน!!)

หลังจากนั้นก็จะใช้คอนเซ็ปเดิม คือ

• เราจะสร้างตัวเลขต่อไปโดยการดึงค่าตัวแรกออกมาจากลิสต์
• เอามาบวกกัน แล้ว append ต่อเข้าไปในลิสต์ตัวหลัก
• และในจังหวะนั้นเอง เมื่อลิสต์ตัวหลักมีการเปลี่ยนแปลง ลิสต์คู่ที่ใช้ดึงข้อมูลก็จะได้ไอเทมไปเพิ่มทันที
• มันก็จะวนต่อๆๆ แบบนี้ไปเรื่อยๆ

แต่ถ้ามองว่าแบบนี้มันก็วนไปไม่มีสิ้นสุดน่ะสิ -> ใช้แล้วครับ มันสามารถวนไปได้เรื่อยๆ เลย แต่เนื่องจากมันเป็น lazy list กระบวนการทั้งหมดนี้จะยังไม่ถูกโปรเซสอะไรทั้งนั้น จนกว่าเราจะมีการดึงข้อมูลออกมา เช่นสั่งว่า take 10 fibo (ขอไอเทม 10 ตัวแรกจากลิสต์)

ผลลัพธ์ก็จะรันได้แบบด้านล่างนี่

$ ghci
GHCi, version 8.0.2

> fibo = 1 : 1 : [a + b | (a, b) <- zip fibo (tail fibo) ]
> take 10 fibo
=> [1,1,2,3,5,8,13,21,34,55]

ปัญหาคือ...

ภาษาทั่วๆ ไปที่เราเขียนกัน มันไม่ได้มีฟีเจอร์นี้แบบ haskell น่ะสิ! ดังนั้นเราลองมาดูกันว่าภาษาทั่วไปที่เราเขียนกันถ้าอยากใช้ Lazy Evaluation จะต้องเขียนยังไง

---

แล้วภาษาสาย Imperative จะทำยังไง?

ขอยกตัวอย่างด้วยสองภาษาคือ

• JavaScript: ตัวแทนของภาษาที่ฟีเจอร์ Generator
• Java: ตัวแทนของภาษาตระกูล OOP

yield มันซะ!, สำหรับภาษาที่มี Generator

ในภาษาเขียนโปรแกรมยุคใหม่ๆ ส่วนใหญ่จะมีฟีเจอร์ที่เรียกว่า "Generator" ใส่มาให้ด้วย (จะใช้คีย์เวิร์ดคำว่า yield) ซึ่งทำให้เราสามารถเขียนฟังก์ชันที่ทำงานแบบ lazy ได้

ลองมาดูตัวอย่างฟังก์ชัน range() กันก่อน

function range(start, end) {
    let numbers = []
    for(let i=start; i<=end; i++){
        numbers.push(i)
    }
    return numbers
}

ฟังก์ชันนี้มีการทำงานคือรับตัวเลขเริ่มต้นและจุดสิ้นสุดเข้าไป แล้วสร้างลิสต์ของตัวเลขออกมาให้ เช่น range(2,5) ก็จะได้ [2, 3, 4, 5]

แต่หลังจากเรารู้จัก lazy evaluation กันไปแล้ว เราอาจจะมองว่าฟังก์ชันนี้มันทำงานไม่ดีเลยแฮะ เพราะจะต้องสร้างลิสต์ของตัวเลขทั้งหดมขึ้นมาเลยเหรอ ทั้งที่ยังไม่รู้ว่าจะใช้เลขครบทุกตัวจริงๆ มั้ย

สิ่งที่เราต้องการก็คือเราอยากจะ return เลขทีละตัว

function range(start, end) {
    for(let i=start; i<=end; i++){
        return i 
        //return 1 value, then finish!
    }
}

แน่นอนว่าเราสั่งแบบนี้ไม่ได้ ถ้าเราสั่งreturnล่ะก็ หลังจากมันรีเทิร์นค่าแรกเสร็จแล้วโปรแกรมก็จะหยุดทำงานทันที

วิธีการแก้คือเปลี่ยนจากการใช้ return ไปใช้คำสั่ง yield แทน

function* range(start, end) {
    for(let i=start; i<=end; i++){
        yield i
    }
}

ฟังก์ชันที่สามารถ yield ได้ เราจะเรียกมันว่าฟังก์ชัน "Generator" ซึ่งมีความสามารถในการตอบค่าได้หลายครั้ง (คล้ายรีเทิร์นได้หลายค่า) โค้ดจะรันมาถึงจุดที่มีการสั่ง yield แล้วค้างอยู่ตรงนั้น จนกว่าจะมีการขอค่าครั้งแต่ไป

เอาง่ายๆ มันคือฟังก์ชันที่สามารถหยุดทำงานชั่วคราวได้ และสามารรีเทิร์นได้หลายครั้ง

เวลาใช้งานก็เอามาวนลูปแบบนี้

for(let x of range(1, 10)){
    console.log(x)
}

ข้อควรระวังเวลาใช้ Generator คือถ้ามันเป็นแบบปลายเปิด คือสามารถสร้างเลขไปได้เรื่อยๆ เราจะต้องมีเงื่อนไขสำหรับหยุดลูปเสมอ!

function* range(start) {
    let i = start
    while(true) {
        yield i
        i = i + 1
    }
}

เช่นในเคสนี้ เราสร้างGeneratorที่สร้างเลขมาเรื่อยๆ ไม่มีจุดสิ้นสุด ถ้าเราเอาไปวนลูปตรงๆ มันจะกลายเป็น Infinity Loop ไม่มีวันจบ

for(let i of range(1)) {
    //Infinity Loop!!
}

ในกรณีนี้ต้องมีเงื่อนไขที่เรียกว่า "Terminate Condition" เพื่อหยุดลูปเสมอ

for(let i of range(1)) {
    //Terminate Condition
    if(...) break
}

หรือเราอาจจะสร้างฟังก์ชันมาดึงไอเทมออกมาตามจำนวนที่ต้องการก็ได้ แบบนี้

function take(n, generator) {
    let elements = []
    let i = 0
    for(let element of generator) {
        if(i >= n) break
        elements.push(element)
    }
    return elements
}

let list = take(10, range(1))
//1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Fibonacci with yield

เราสามารถลองเอาฟังก์ชัน fibo มาเขียนใหม่ด้วยการใช้ yield ได้

ซึ่งส่วนใหญ่การเขียน Generator จะประกอบด้วยส่วนต่างๆ ประมาณนี้

function fibo(){
    // 1.init
    let n = pair(1, 1)

    // 2.infinity loop
    while(true) {

        // 3.yield first number
        yield n.first

        // 4.update current pair numbers
        n = pair(
            n.second, 
            n.first + n.second
        )
    }
}

ขี้เกียจสไตล์ OOP, เขียนเยอะกว่าเดิม บอกเลย!

สำหรับภาษาที่เคร่งเรื่อง OOP มากๆ แบบ Java การจะสร้าง Generator ขึ้นมาจะต้องสร้างในรูปแบบของ object แทน

เราต้องการให้อ็อบเจคตัวไหนสามารถเป็น Generator ได้เราจะต้องสั่งให้มัน implements Iterable ซึ่งจะบังคับให้เราเขียนเมธอด iterator

class Persons implements Iterable<People> {

    List<Person> persons = new ArrayList<>();

    //ถ้าข้อมูลของเราเป็น Iterable อยู่แล้ว
    public Iterator<Person> iterator() {
        return persons.iterator();
    }

    //ถ้าข้อมูลของเรา ไม่ได้เป็น Iterable (ต้องสร้างเอง)
    public Iterator<Person> iterator() {
        return new Iterator<Type>() {

            //ตัวนับ index
            private int currentIndex = 0;

            //เช็กว่าเรายังเหลือข้อมูลให้ตอบมั้ย
            @Override
            public boolean hasNext() {
                return currentIndex < persons.size();
            }

            //ดึงข้อมูลตัวถัดไป
            @Override
            public Type next() {
                return persons.get(currentIndex++);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

Lazy ใน Real-World

ก่อนจบบทนี้ ลองมาดูตัวอย่างเล็กๆ น้อยๆ กับการประยุกค์ใช้ที่เจอได้ในการเขียนโค้ดประจำวัน

Collections vs Sequences

ในบางภาษา เช่น Kotlin จะมีชนิดตัวแปรแบบ List 2 คือลิสต์แบบ static ธรรมดากับแบบ lazy ที่เรียกว่า "Sequence"

ลองดูตัวอย่างข้างล่างนี้เมื่อเราใช้คำสั่ง map กับ first

val numbers = listOf(1, 2, 3, 4, 5)

// Collections
val n = numbers.map {
    it * it
}.first {
    it > 10
}
// 1. นำเลขทุกตัวไปยกกำลังสอง  = [1, 4, 9, 16, 25]
// 2. เลือกเลขตัวแรกที่มากกว่า10 = 16

// Sequences
val n = numbers.asSequence().map {
    it * it
}.first {
    it > 10
}
// 1. นำเลขทุกตัวไปยกกำลังสอง (แต่ยังไม่ทำ เพราะยังไม่มีการขอตัวเลขไปใช้)
// 2. เลือกเลขตัวแรกที่มากกว่า10 (ในจังหวะนี้ค่อยนำตัวเลขจากสเต็ปที่แล้วไปยกกำลังสองทีละตัว ถ้าเจอตัวที่ตรงเงื่อนไขก็หยุดได้ทันที) = [1, 4, 9, 16, ...]

สำหรับรายละเอียดเพิ่มเติมลองไปอ่านที่บทความนี้ดู Collections and sequences in Kotlin

Singleton

Singleton เป็น Design Pattern ยอดนิยมหนึ่งตัวที่คนใช้กันเยอะมาก (แต่คำแนะนำของเราคือเราไม่ควรใช้แพทเทิร์นนี้เยอะๆ นะ)

คอนเซ็ปคือถ้าเรามีคลาสสไตล์ helper ที่ทั้งโปรแกรมสร้างอ็อบเจคแค่ตัวเดียวก็พอ เช่น

class Calculator {

    public static Calculator instance = new Calculator();

    public int add(int x, int y){
        return x + y;
    }
}

int ans = Calculator.instance.add(1, 2);

เราสร้างตัวแปรแบบ static ชื่อ instance เอาไว้ จากนั้นเวลาจะใช้งานจะได้เรียกจากตัวแปรนี้อย่างเดียวได้ ไม่ต้องคอย new อ็อบเจคเรื่อยๆ ให้เปลือง

แต่ก็มีปัญหาคือถ้าเราเขียนโค้ดแบบนี้ instance จะถูกสร้างทันทีที่โปรแกรมเริ่มทำงาน แม้ว่าจะยังไม่มีโค้ดส่วนไหน เรียกเมธอด add() เลยก็ตาม

ดังนั้นวิธีแก้ของแพทเทิร์นส่วนใหญ่จะนิยมให้เรียกผ่านเมธอด getInstance() แทน ซึ่งจะมีการเช็กว่าตัวแปรนั้นถ้ายังไม่เคยถูกสร้าง ให้สร้างใหม่ตอนนั้น (แปลว่าถ้าไม่มีใครเรียกใช้งานเลย ก็ไม่ต้องสร้าง = สร้างเมื่อใช้งานตามคอนเซ็ป lazy)

class Calculator {

    private static Calculator instance = null;

    public static Calculator getInstance(){
        if(instance == null){
            instance = new Calculator();
        }
        return instance;
    }

    public int add(int x, int y){
        return x + y;
    }
}

int ans = Calculator.getInstance().add(1, 2);

ในภาษายุคใหม่หลังๆ ส่วนใหญ่จะมีการใส่การใช้ lazy ลงไปใน syntax ของภาษาเลย

เช่น Kotlin (อีกแล้ว)

val instance: Calculator by lazy {
    Calculator()
}

จริงๆ มีตัวอย่างอีกมากมายที่เราสามารถนำหลักการ lazy มาใช้เพื่อเพิ่มประสิทธิภาพของโปรแกรมได้ เช่น ORM (ถ้าสนใจ ลองเสิร์จดูได้ หรือถ้ามีโอกาสในอนาคตเราจะพูดถึงเรื่องนี้กันต่อ)