ทุกสิ่งล้วนเป็นฟังก์ชัน: บันทึกหลังเรียนคอร์ส SICP กับ David Beazley

บันทึกหลังเรียนคอร์ส SICP กับ David Beazley: ประสบการณ์ 1 สัปดาห์

ขอแบ่งปันประสบการณ์จากการเข้าร่วมคอร์ส SICP ของ David Beazley ช่วงปลายปี 2022 แม้จะมีสื่อฟรีอยู่มากมาย แต่คอร์สของ Dave มีประสิทธิภาพมากเพราะเลือกหัวข้อเฉพาะมาอธิบายอย่างลึกซึ้ง

จุดเริ่มต้น

คอร์ส SICP ใช้ภาษา Scheme และในที่นี้ได้อธิบายแนวคิดพื้นฐานอย่างโมเดล การแทนที่ค่า (substitution) ผ่านการสร้างตัวแปล Scheme แบบง่าย ๆ ด้วย Python

พื้นฐานของภาษา Scheme

• Primitive: ค่าพื้นฐาน (เช่น จำนวนเต็ม)
• Operator: ใช้การดำเนินการพื้นฐานอย่าง +, -, *, / ในรูปแบบ prefix notation
• define: นิยามตัวแปร

> (define x 2)  
> (+ x 3) ; 결과: 5  

• if: คำสั่งเงื่อนไข
• lambda: นิยามฟังก์ชันนิรนาม

> ((lambda (x) (* x x)) 3) ; 결과: 9  

ตัวแปล Scheme ใน Python

มีการสร้างตัวแปลอย่างง่ายสำหรับประเมินโค้ด Scheme โดยใช้ Python และนิยามการดำเนินการพื้นฐานด้วยฟังก์ชัน Python

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}  

ตัวอย่าง:

> evaluate(("+", 2, 3)) # 결과: 5  

รวมถึงการทำงานของ define และ lambda ตลอดจนการจัดการคำสั่งเงื่อนไข if

โมเดลการแทนที่ค่า (Substitution Model)

โมเดลการแทนที่ค่าเป็นวิธีตีความโปรแกรมแบบง่าย โดยประเมินโปรแกรมผ่านการแทนตัวแปรด้วยค่า แต่เมื่อมี assignment โมเดลนี้จะใช้ไม่ได้

สถานะ (State)

ตัวอย่างที่ทำให้โมเดลการแทนที่ค่าใช้ไม่ได้คือ assignment เช่น เมื่อต้องจำลองยอดเงินคงเหลือในบัญชีธนาคาร จะใช้ set! เพื่ออัปเดตตัวแปร

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)  

ในกรณีนี้ โมเดลการแทนที่ค่าไม่สามารถแยกความต่างของสถานะยอดคงเหลือก่อนและหลังได้

จึงจำเป็นต้องใช้โมเดล Environment ตัวแปรจะถูกนิยามภายใน environment และแต่ละ procedure จะมี environment ของตัวเอง

สตรีม (Streams)

อีกวิธีหนึ่งในการจำลองสถานะคือ stream ซึ่งสามารถจำลองค่าของอนาคตได้ผ่านการประเมินค่าแบบหน่วงเวลา (lazy evaluation)

ลูปไม่สิ้นสุดและลำดับการประเมินค่า

ความต่างของลำดับการประเมินค่า: ภาษาส่วนใหญ่ใช้ applicative-order evaluation ซึ่งจะประเมินอาร์กิวเมนต์ก่อน

> (square (+ 1 2)) ; 결과: 9  

แต่ normal-order evaluation จะเลื่อนการประเมินอาร์กิวเมนต์ออกไปจนกว่าจะจำเป็นจริง ๆ ทำให้หลีกเลี่ยงลูปไม่สิ้นสุดได้

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; normal order จะคืนค่า 0 แต่ applicative order จะเข้าสู่ลูปไม่สิ้นสุด  

Lambda Calculus และเลข Church

สามารถใช้ Church encoding เพื่อแทนตัวเลขเป็น procedure ได้ ซึ่งเป็นแนวคิดสำคัญของการเขียนโปรแกรมเชิงฟังก์ชัน

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))  

• zero คือฟังก์ชันที่คืนอาร์กิวเมนต์เดิม (identity function)
• increment คือการเพิ่มการเรียกใช้ฟังก์ชันอีกหนึ่งครั้ง

ตัวอย่าง

> ((zero (lambda (x) (+ x 1))) 0) ; 결과: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; 결과: 1  

การวนซ้ำ vs การเรียกซ้ำ

Scheme ใช้ recursion แทน for loop ในการทำงานซ้ำ

ตัวอย่างการเรียกซ้ำ: แฟกทอเรียล

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))  

การเรียกซ้ำลักษณะนี้อาจใช้หน่วยความจำมากเพราะต้องอาศัยสแตก

การเพิ่มประสิทธิภาพ tail-call

Scheme ลดการใช้หน่วยความจำผ่าน tail-call optimization ทำให้การทำงานมีลักษณะเหมือนกระบวนการแบบวนซ้ำ (iterative)

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))  

สรุป

คอร์สของ David Beazley คัดเลือกแนวคิดสำคัญของ SICP มานำเสนออย่างลึกซึ้ง โดยเฉพาะเรื่องการเขียนโปรแกรมเชิงฟังก์ชัน Lambda Calculus และลำดับการประเมินค่า ซึ่งช่วยให้เข้าใจพาราไดม์การเขียนโปรแกรมที่หลากหลายมากขึ้น

คำคมของ Knuth

ถ้าคุณเรียนแต่ทฤษฎี นั่นหมายความว่าถึงเวลาที่ควรหันไปโฟกัสด้านปฏิบัติ และถ้าคุณทำแต่ภาคปฏิบัติ นั่นหมายความว่าถึงเวลาที่ควรหันไปโฟกัสด้านทฤษฎี

[GN⁺]

ความคิดเห็นจาก Hacker News

• คอร์ส SICP มีเนื้อหาเข้มข้นมาก แต่ใช้เวลาค่อนข้างมากกับช่วงถามตอบของนักศึกษาและการใช้กระดานดำ และลำดับการสอนก็อาจจัดใหม่ได้ด้วย ส่วนตัวกำลังวางแผนทำวิดีโอซีรีส์ชุดใหม่

  • คอร์ส SICP ยังคงรักษาเจตนารมณ์ดั้งเดิมไว้ แม้จะใช้ภาษาสมัยใหม่อย่าง Python
  • Python เป็นภาษาหลายกระบวนทัศน์ที่มีพลังในการแสดงออกสูง

• มีการแนะนำวิธีเข้ารหัสสถานะให้เป็น pure function และมีการเข้ารหัสเชิงฟังก์ชันแบบบริสุทธิ์สำหรับข้อมูลหลากหลายประเภท

  • การเข้ารหัสอาจทำให้สับสนได้ แต่ก็สง่างามและกระชับ
  • มีตัวอย่างการนำ Maybe monad ไปใช้งานแบบฟังก์ชันใน JavaScript

• แองเคอร์/แฮชใน URL ของบล็อกโพสต์ทำให้กระโดดไปที่โพสต์สคริปต์ทันที จนเกิดความสับสน

• ตอนเห็นการ implement cons/car/cdr ด้วย lambda ครั้งแรก มันดูเหมือนเวทมนตร์ นี่แสดงให้เห็นว่า language runtime จำเป็นต้องรองรับการทำพจนานุกรมคีย์/ค่า

• David Beazley เป็นบุคคลระดับตำนานในโลกของ Python และคอร์สนี้แม้ตอนแรกจะน่าประหลาดใจ แต่ไม่นานก็รู้สึกว่าเป็นการจับคู่ที่ลงตัวมาก จึงสมัครคอร์สถัดไปแล้ว

  • สิ่งนี้แสดงให้เห็นว่าการศึกษาต่อเนื่องของวิศวกรซอฟต์แวร์อาจดำเนินไปในลักษณะใด

• ได้เจอแนวคิดที่ว่าจำเป็นต้องมี inductive data type เพราะเพียงแค่ Church encoding อย่างเดียวไม่สามารถพิสูจน์ทฤษฎีบทอย่าง 0 != 1 ได้

  • ได้โพสต์เนื้อหาที่เกี่ยวข้องไว้ใน Notion

• ตัวบทความเองน่าสนใจ แต่การนำทางในหน้ายาก และไม่สามารถเลื่อนด้วยปุ่มลูกศรบนคีย์บอร์ดได้

• โค้ดในส่วน "โมเดลทางเลือก" มีพิมพ์ผิด ควรใช้ fibonacci แทน fib แต่โค้ดใน GitHub repository ถูกต้อง

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

• มีการให้ลิงก์ YouTube