ทำไมเราจึงต้องการ Algebraic Effects

• Algebraic Effects เป็นฟีเจอร์ภาษาแบบหนึ่งที่จับและจัดการ control flow ได้คล้ายกับ exception ที่สามารถ resume ต่อได้ เป็นฟีเจอร์หลักของ Ante และยังถูกใช้เป็นแกนสำคัญในภาษาเชิงวิจัยอย่าง Koka, Effekt, Eff, Flix
• ด้วยกลไกเดียวกันนี้ สามารถสร้าง generator, exception, async, coroutine, automatic differentiation ได้ในระดับไลบรารี และด้วย effect polymorphism ฟังก์ชันอย่าง map ก็เขียนเพียงครั้งเดียวได้โดยไม่ขึ้นกับชนิดของ effect
• หากเปลี่ยน dependency injection และการส่ง context เช่น การเข้าถึงฐานข้อมูล, output, logging, การส่ง state ให้เป็น effect ก็สามารถจัดการ test mock, การเก็บ output, การกรอง log ได้ด้วยการเปลี่ยน handler
• เมื่อ effect อย่าง can IO, can Print, can Fail ปรากฏใน signature ของฟังก์ชัน จะเป็นประโยชน์ต่อ การรับประกันความบริสุทธิ์, record/replay และ security audit แต่ effect ที่ได้รับอนุญาตอยู่แล้วอาจถูกส่งต่อไปยัง handler เดิมโดยไม่ตั้งใจ
• จุดอ่อนดั้งเดิมคือ ความกังวลด้านประสิทธิภาพ แต่ภาษายุคหลังลดต้นทุนลงด้วยการ optimize tail-resumptive effects, evidence passing, การจำกัดให้ resume ได้ครั้งเดียว และ handler specialization

---

โมเดลพื้นฐานของ Algebraic Effects

• Algebraic Effects เรียกอีกอย่างว่า effect handlers และสามารถเข้าใจได้ด้วยโมเดล “exception ที่สามารถ resume ต่อได้”
• ใน pseudocode ของ Ante จะประกาศ effect function และระบุใน function signature ด้วย can ว่าสามารถใช้ effect นั้นได้
  • เมื่อเรียก effect function อย่าง say_message: Unit -> Unit จะเป็นรูปแบบของการ “throw” effect
  • ฟังก์ชันที่เรียกจะแสดงความเป็นไปได้ในการใช้ effect นั้นใน signature เช่น foo () can SayMessage
• expression handle คล้ายกับ try/catch ตรงที่จับ effect และเรียก resume เพื่อทำ computation ที่ถูกหยุดไว้ให้ดำเนินต่อ
  • หาก handler ของ say_message รัน print "Hello World!" แล้วเรียก resume () computation เดิมจะดำเนินต่อและคืนค่า 42
• ชื่อ “algebraic” ส่วนใหญ่เป็นคำที่หลงเหลือมา และในทางปฏิบัติคำว่า effect handlers ใกล้เคียงกว่ามาก แต่ยังใช้ชื่อ Algebraic Effects เพราะเป็นชื่อที่ผู้ใช้คุ้นเคย

Control flow ที่ผู้ใช้กำหนดเอง

• Algebraic Effects ช่วยให้ implement ฟีเจอร์ภาษาหลายอย่าง ได้ด้วยกลไกเดียว
  • generator
  • exception
  • async
  • coroutine
  • automatic differentiation
• Effect polymorphism ช่วยลดปัญหา what color is your function
  • map (input: Vec a) (f: a -> b can e): Vec b can e แสดงว่าไม่ว่า input function f จะทำ effect e ใด map ก็จะทำ effect เดียวกัน
  • สามารถใช้ map เดียวกันกับการพิมพ์ออก stdout, การเรียกฟังก์ชัน async, การ yield stream ฯลฯ ได้
  • ภาษา effect handler จำนวนมากละ effect variable e ได้ ทำให้เขียนในรูปที่คุ้นเคยอย่าง map (input: Vec a) (f: a -> b): Vec b
• Exception implement ได้ด้วยวิธี ไม่เรียก resume เมื่อจัดการ effect
  • นิยาม throw: a -> never_returns ของ effect Throw a
  • เมื่อหารด้วยศูนย์ ให้เรียก throw "error: Division by zero!" และ handler จะพิมพ์ข้อความแล้วไม่ resume computation
• Generator สามารถ implement ด้วย yield: a -> Unit ของ effect Yield a
  • วนผ่าน element ของ vector แล้วเรียก yield elem
  • handler filter จะเรียก yield x อีกครั้งหากค่าที่ yield มาเข้าเงื่อนไข แล้วใช้ resume () เพื่อไปยัง element ถัดไป
  • handler my_for_each จะรันฟังก์ชัน f กับค่าที่ yield มาแต่ละค่า แล้วดำเนินต่อด้วย resume ()
• Cooperative scheduler ก็สร้างได้ด้วย effect yield: Unit -> Unit โดย handler จะรับ control แล้วสลับไป execute ฟังก์ชันอื่น
  • ตัวอย่าง scheduler ของ Effekt แสดง pattern นี้
• หลาย effect สามารถ compose กันได้ดี และจุดนี้ถือเป็นข้อได้เปรียบด้าน usability เมื่อเทียบกับ abstraction ของ effect แบบอื่น

Dependency injection และความสามารถในการทดสอบ

• Effect สามารถใช้ทำ dependency injection ใน business application ทั่วไปได้
• แทนที่จะส่ง object ฐานข้อมูลเป็น argument ให้ฟังก์ชันโดยตรง สามารถนิยาม effect Database ได้
  • รูปแบบเดิมคือรับ object DB เป็น argument เช่น business_logic (db: Database) (x: I32)
  • รูปแบบที่ใช้ effect จะเป็น business_logic (x: I32) can Database และภายในเรียก query "..."
• การเลือกฐานข้อมูลจริงให้เป็นหน้าที่ของ handler ที่อยู่สูงกว่าใน call stack
  • สามารถเปลี่ยน production DB เป็น DB อื่น หรือแทนที่ด้วย mock DB สำหรับทดสอบได้
  • handler mock_database สามารถ ignore ข้อความ query แล้ว resume โดยคืน DbResponse.Ok เสมอ
• หากจัดการ output เป็น effect ก็สามารถเก็บเป็น string ระหว่างทดสอบแทนการเขียน stdout โดยตรงได้
  • handler print_to_string จะจับการเรียก print msg แล้วสะสมลงใน string all_messages พร้อมขึ้นบรรทัดใหม่
  • output_messages สามารถตรวจสอบค่าที่คืน 1234 และ string ข้อความได้โดยไม่ต้อง output จริง
• Logging สามารถเปลี่ยนเป็น conditional output ได้โดยใช้ effect Log และ LogLevel
  • log_handler จะเรียก print msg หาก level ของข้อความสูงกว่าหรือเท่ากับเกณฑ์ที่ตั้งไว้
  • foo () with log_handler Error จะพิมพ์เฉพาะ error log

API ที่สะอาดขึ้นและการส่ง context

• Algebraic Effects สามารถแสดง pattern ของ Context object ที่ถูกส่งต่อไปทั่วโปรแกรมหรือไลบรารีในรูปแบบ effect ได้
• Effect Use a มองได้ว่าเป็น state effect และให้ get: Unit -> a, set: a -> Unit
  • handler state จะเก็บ initial state, คืน context ปัจจุบันให้ get และอัปเดตเป็น context ใหม่ให้ set
  • นิยาม state ในตัวอย่างละเลยกฎ ownership และในการ implement จริงอาจต้องมี constraint Copy a
• ตัวอย่างที่เก็บ string ไว้ภายใน vector แล้วส่ง index เหมือนเป็น key แสดงให้เห็นต้นทุนของการส่ง context
  • หากไม่ใช้ effect ฟังก์ชันอย่าง push_string, get_string, append_with_separator, example ต้องรับ strings เป็น argument ต่อไปเรื่อย ๆ
  • ใน implementation แบบ effect primitive operation อย่าง push_string, get_string จะเรียก get/set และ code ระดับบนไม่ต้องส่ง strings โดยตรง
• วิธีนี้เหมาะเมื่อไลบรารีห่อหุ้มการส่ง context ภายในไว้
  • ผู้ใช้ไลบรารีไม่ต้องสนใจรายละเอียดภายในของวิธีส่ง context
  • หากไม่ต้องการผูกกับ context type ใดโดยเฉพาะ สามารถ abstract ฟังก์ชันที่จำเป็นเป็น interface ได้

การแทนที่ global variable และ direct style

• API ที่ภายนอกดูเหมือนไร้ state แต่จริง ๆ ต้องใช้ state เช่น random number generation หรือ memory allocation สามารถแสดงเป็น effect แทน global variable ได้
• ตัวอย่าง random number generation แสดงภาระในการส่ง object Prng ไปทั่วทั้งโปรแกรมโดยตรง
  • Prng แบบ global สะดวก แต่มีข้อเสียของ global value เช่น ต้องรองรับ thread safety
  • หากใช้ random: Unit -> U8 ของ effect Random ผู้ใช้เพียงระบุการ initialize ด้วย handler ที่ใดสักแห่งใน call stack ด้านบน
  • ภายหลังหากต้องการเปลี่ยนเป็น /dev/urandom หรือแหล่ง random อื่น ก็เปลี่ยนเฉพาะ handler โดยไม่ต้องแก้ code ส่วนอื่นของ call stack
• Memory allocation ก็แสดงเป็น effect Allocate ได้
  • allocate: (size: Usz) -> Alignment -> Ptr a
  • free: Ptr a -> Unit
  • โดยทั่วไปใช้ global allocator สำหรับการเรียกส่วนใหญ่ และภายใน tight loop สามารถเพิ่ม handler ที่ loop body เพื่อเปลี่ยนเป็น arena allocator ได้
• Effect ทำให้เขียนแบบ direct style ได้มากกว่าวิธีส่งผลลัพธ์ที่ถูกห่อด้วย value เฉพาะ
  • หากใช้ Maybe t ต้องต่อ success path ด้วย and_then, map
  • Syntactic sugar อย่าง ? ของ Rust เป็นกลไกเพื่อให้โฟกัสกับ path ที่ดี
  • get_line_from_stdin (): String can Fail, IO และ parse (s: String): U32 can Fail แบบ effect เขียนเหมือน sequential code ทั่วไปได้ เช่น line = ..., x = ..., x * 2
• การจัดการ failure ทำได้ด้วยการ apply handler เพื่อออกจาก good path
  • get_line_from_stdin () with default "42" จัดการ effect Fail ด้วยค่า default
• Error type ที่ต่างกันก็ compose กันอย่างเป็นธรรมชาติด้วยรายการ effect
  • LibraryA.foo (): U32 can Throw LibraryA.Error
  • LibraryB.bar (): U32 can Throw LibraryB.Error
  • my_function สามารถประกาศ Throw LibraryA.Error, Throw LibraryB.Error, Throw MyError ร่วมกันได้
  • หากการเขียนซ้ำยาวขึ้น สามารถสร้าง type alias เช่น AllErrors = can Throw ... ได้
  • effect Throw String เดียวกันจะถูกรวมเป็นหนึ่ง และหากต้องการแยก ต้องใช้ wrapper type อย่าง MyError

ความบริสุทธิ์, การรันซ้ำ, และ security audit

• ภาษา effect handler ส่วนใหญ่ ยกเว้นราว ๆ OCaml จะใช้ effect ในจุดที่อาจเกิด side effect
  • ใน Ante หากไม่ระบุอย่าง can Print, can IO จะไม่สามารถใช้ side effect ได้
  • นิยาม extern compiler ตรวจสอบไม่ได้ จึงต้องเชื่อถือ type definition
  • วิธีให้ทำ effect IO เฉพาะใน debug mode เพื่อรักษา effect safety ของ release mode เป็นฟีเจอร์ที่วางแผนไว้
• ฟังก์ชันบางอย่างต้องการ pure function เป็น input
  • เมื่อสร้าง thread ไม่ควรให้ thread ที่ถูกสร้างสามารถเรียก handler ที่เป็นของ current thread ได้
  • spawn_all (functions: Vec (Unit -> a pure)): Vec a can IO เป็นรูปแบบที่รับเฉพาะ pure function แล้วรันทุกฟังก์ชันเป็น thread และรอจนเสร็จ
• Software Transactional Memory(STM) เป็นเทคนิค concurrency ที่ต้องใช้ pure function
  • เมื่อรันหลายฟังก์ชันพร้อมกัน แล้วค่าระหว่าง transaction ถูกเปลี่ยนโดย thread อื่น จะเริ่ม transaction นั้นใหม่
  • Proof-of-concept implementation ของ Effekt อยู่ที่ effekt-stm
• ความบริสุทธิ์อาจให้ความสามารถ record/replay คล้าย utility debugging rr
  • handler สองตัวคือ record และ replay จะจัดการ top-level effect ที่ main ส่งออกมา ซึ่งโดยทั่วไปคือ IO
  • record บันทึกการเกิด effect และผลลัพธ์ แล้วส่งต่อขึ้นไปยัง handler IO ในตัวเพื่อจัดการจริง
  • replay ไม่ทำ IO จริง แต่ใช้ผลลัพธ์จาก effect log
  • หากบันทึกเป็น default ใน debug build ก็จะได้ deterministic debugging
• รายการ effect ใน function signature ช่วยทำ security audit คล้าย Capability Based Security
  • get_pi: Unit -> F64 ทำให้รู้ได้ว่าจะไม่แอบทำ IO อยู่เบื้องหลัง
  • หากหลังอัปเดตไลบรารีกลายเป็น get_pi: Unit -> F64 can IO ฝั่งที่เรียกจะได้รับ error ใน code เว้นแต่ว่าฟังก์ชันที่เรียกนั้นต้องการ IO อยู่แล้ว
  • ควรประกาศเฉพาะ effect ขั้นต่ำ เช่น ประกาศแค่ Print แทน IO ทั้งหมด
  • การเพิ่ม effect ใหม่ถือเป็นการเปลี่ยนแปลงที่ทำลาย semantic versioning
  • เอกสารที่เกี่ยวข้องมี Capability Based Security และ Designing with Static Capabilities and Effects

ข้อจำกัดและกลยุทธ์การ implement

• ข้อจำกัดหนึ่งของแนวทาง effect คืออาจเกิด การจัดการโดยไม่ตั้งใจ ได้
  • แม้ฟังก์ชันหนึ่งเริ่มต้องการ IO ใหม่ หากฟังก์ชันที่เรียกอนุญาต IO อยู่แล้ว ก็อาจไม่เกิด error
  • effect Fail ก็เช่นกัน หากฟังก์ชันไลบรารีที่เดิมไม่เคย fail ต่อมาสามารถ Fail ได้ ก็อาจถูกส่งต่อไปยัง handler Fail เดิม
  • พฤติกรรมนี้อาจยอมรับได้ในบางสถานการณ์ แต่ถ้าต้องการจัดการแยก เช่น ให้ค่า default ก็อาจไม่ตรงเจตนา
• ข้อเสียหลักแบบดั้งเดิมคือ ความกังวลด้านประสิทธิภาพ แต่ output จากการ compile ของ effect สมัยใหม่ดีขึ้นมาก
• ภาษา Algebraic Effects จำนวนมาก optimize tail-resumptive effect ให้เป็นการเรียก closure ปกติ
  • Tail-resumptive effect คือ effect ที่ handler เรียก resume เป็นสิ่งสุดท้าย
  • effect ส่วนใหญ่ในทางปฏิบัติเข้าข่ายนี้ และตัวอย่างส่วนใหญ่ในบทความก็อยู่ในหมวดนี้
  • Exception ถูกจัดเป็นกรณีพิเศษ เพราะไม่เรียก resume เลย
• กลยุทธ์การ optimize แตกต่างกันไปตามภาษา
  • Koka ใช้ evidence passing และยก effect ขึ้นไปถึง handler เพื่อ compile เป็น C โดยไม่ต้องมี runtime
  • Ante และ OCaml จำกัดให้เรียก resume ได้มากที่สุดหนึ่งครั้ง
    • ข้อจำกัดนี้กัน effect บางอย่างออกไป เช่น nondeterminism
    • แต่แลกกับการทำให้ resource handling ง่ายขึ้น และ implement continuation ภายในได้มีประสิทธิภาพขึ้นด้วยวิธีอย่าง segmented stacks
  • Effekt กำจัด handler ออกด้วยการ specialize ทั้งหมดในโปรแกรม
    • วิธีนี้มีข้อจำกัดว่าทำให้ฟังก์ชันส่วนใหญ่เป็น second-class
    • สามารถใช้รูปแบบ boxed เพื่อให้ได้ first-class function และเปลี่ยนไปใช้แบบ pay-as-you-go ได้
    • เอกสารที่เกี่ยวข้องมี เอกสาร captures ของ Effekt และ paper