AST — ต้นไม้ที่เป็น enum ไม่ใช่ Visitor pattern

scanner คายลำดับ token ออกมาเป็นเส้นตรง แต่ความหมายของโปรแกรมไม่ได้เรียงเป็นเส้น

1 + 2 * 3 มี token ห้าตัวต่อกัน และไม่มีตัวไหนบอกว่า * ต้องจับก่อน + ความจริงข้อนั้นอยู่ในกฎของภาษา ไม่ได้อยู่ในลำดับ

ด่านที่สองจึงต้องเปลี่ยนเส้นตรงให้เป็นต้นไม้ บทนี้ออกแบบต้นไม้นั้น ส่วนบทที่ 3 คือคนสร้างมัน

เส้นตรงเก็บลำดับความสำคัญไม่ได้

หัวข้อนี้บอกว่าทำไมความหมายของโปรแกรมต้องอยู่ในรูปต้นไม้ ไม่ใช่ลำดับที่แบนราบแบบ token

AST คือรูปที่เก็บ “อะไรอยู่ใต้อะไร” ได้ ซึ่งเป็นสิ่งที่ลำดับเก็บไม่ได้

ใน 1 + 2 * 3 การคูณต้องเกิดก่อน วิธีเขียนความจริงข้อนี้ลงในโครงสร้างคือให้การคูณเป็น ลูก ของการบวก ไม่ใช่พี่น้องที่ยืนเรียงกัน

คำว่า abstract ในชื่อหมายถึงสิ่งที่ถูกทิ้ง — ช่องว่าง comment และ ; ไม่มีที่ในต้นไม้ เพราะหน้าที่ของมันจบไปแล้วตั้งแต่ตอนที่รูปร่างถูกกำหนด

flowchart TD
    A["Binary · op = Add"] --> B["Literal · 1"]
    A --> C["Binary · op = Mul"]
    C --> D["Literal · 2"]
    C --> E["Literal · 3"]

คำบรรยายภาพ: ต้นไม้ของ 1 + 2 * 3 · การคูณอยู่ใต้การบวก ลำดับความสำคัญจึงไม่ใช่กฎที่เขียนแยกไว้ที่ไหน มันคือความลึกของ node

Visitor pattern ถูกสร้างมาแก้ปัญหาอะไร

หัวข้อนี้อธิบายว่า Visitor pattern มีไว้ให้เพิ่มการทำงานใหม่บนต้นไม้โดยไม่ต้องไล่แก้ class ของ node ทุกตัว และราคาของมันคือ double dispatch

ตำราต้นทางประกาศ base class ชื่อ Expr แล้วแตก class ลูกออกไปหนึ่งตัวต่อหนึ่งรูปแบบของนิพจน์

ปัญหาโผล่ตอนจะเพิ่มการทำงานใหม่บนต้นไม้ คอร์สนี้เพิ่มสามอย่าง คือ pretty-printer ในบทนี้ evaluator ในบทที่ 4 และ resolver ในบทที่ 7 ถ้าแต่ละอย่างเป็น method ก็ต้องไปเติมใน class ลูกทุกตัว

Visitor pattern ย้ายการทำงานออกมาไว้ข้างนอก — หนึ่งการทำงานเท่ากับหนึ่ง class ใหม่ ส่วน class ของ node เติม method accept ไว้ตัวเดียวแล้วไม่ต้องแก้อีก

ราคาคือ double dispatch ผู้อ่านต้องเดินสองต่อทุกครั้ง จาก accept ไปหา visit กว่าจะถึงบรรทัดที่ทำงานจริง

Java วันนี้ไม่เหมือน Java ในตำรา

ตั้งแต่ Java 21 เป็นต้นมา sealed interface คู่กับ pattern matching ใน switch ทำให้คอมไพเลอร์ตรวจความครบของกรณีให้ได้ โดยไม่ต้องมี Visitor เข้ามาคั่นกลาง

ตำราต้นทางเขียนก่อนหน้านั้น ข้อจำกัดที่มันเดินอ้อมจึงเป็นข้อจำกัดของ Java ในเวลานั้น ไม่ใช่ของ Java ตลอดกาล

enum เดียวแทนลำดับชั้นทั้งชั้น

หัวข้อนี้แสดงว่า enum ของ Rust เขียน “เป็นหนึ่งในรูปแบบเหล่านี้เท่านั้น” ได้ตรงๆ จึงไม่ต้องมีลำดับชั้นของ class

เริ่มจากตัวที่เล็กที่สุดใน file คือค่าคงที่ที่คนเขียนพิมพ์ลงไปตรงๆ

/// ค่าคงที่ที่เขียนตรงๆ ใน source
#[derive(Debug, Clone, PartialEq)]
pub enum Literal {
    Nil,
    Bool(bool),
    Number(f64),
    Str(String),
}

สี่กรณีข้างในนี้พูดสิ่งที่ลำดับชั้นของ class พูดไม่ได้ในประโยคเดียว คือ literal เป็นหนึ่งในสี่แบบนี้เท่านั้น ไม่มีแบบที่ห้า

ต้นไม้ของนิพจน์ใช้หลักเดียวกัน แค่ยาวกว่า

/// นิพจน์ — ทุกอย่างที่ให้ค่ากลับมา
///
/// `Box` โผล่ตรงที่ต้นไม้ซ้อนตัวเอง เพราะ Rust ต้องรู้ขนาดของ `Expr` ตอนคอมไพล์
/// และ enum ที่มีตัวเองอยู่ข้างในโดยไม่ผ่าน pointer จะมีขนาดไม่สิ้นสุด
///
/// ฟิลด์ `id` อยู่บน `Variable` · `Assign` · `This` เท่านั้น — สามอย่างนี้คือสิ่งที่
/// resolver ในบทที่ 7 ต้องจดคำตอบไว้ · Java ใช้ตัว object เองเป็น key ของ map ได้
/// เพราะทุก object มี identity ติดตัว แต่ Rust ไม่มี identity ให้ยืม เราจึงติดเลขให้
/// ตั้งแต่ตอน parse (ดู `parser::parse` ที่รับ `first_id` เข้าไป)
#[derive(Debug, Clone)]
pub enum Expr {
    Literal(Literal),
    Grouping(Box<Expr>),
    Unary { op: UnaryOp, line: usize, right: Box<Expr> },
    Binary { left: Box<Expr>, op: BinaryOp, line: usize, right: Box<Expr> },
    Logical { left: Box<Expr>, op: LogicalOp, right: Box<Expr> },
    Variable { name: String, line: usize, id: usize },
    Assign { name: String, line: usize, id: usize, value: Box<Expr> },
    Call { callee: Box<Expr>, line: usize, args: Vec<Expr> },
    Get { object: Box<Expr>, name: String, line: usize },
    Set { object: Box<Expr>, name: String, line: usize, value: Box<Expr> },
    This { line: usize, id: usize },
}

ฟิลด์ line ติดอยู่กับ node ที่ทำให้เกิดความผิดพลาดตอนรันได้ เพราะข้อความ error ต้องบอกบรรทัดได้แม้ตอนนั้นข้อความต้นฉบับหายไปแล้ว

Grouping เก็บวงเล็บที่คนเขียนใส่ไว้ ทั้งที่รูปร่างของต้นไม้บอกลำดับอยู่แล้ว หัวข้อผลรันข้างล่างจะกลับมาที่จุดนี้อีกครั้ง

Box โผล่ตรงที่ต้นไม้ซ้อนตัวเอง

หัวข้อย่อยนี้อธิบายว่าทำไม node ที่มีลูกต้องห่อลูกด้วย Box และราคาที่ติดมากับมัน

Rust ต้องรู้ขนาดของทุกชนิดตอนคอมไพล์ ถ้า Expr มี Expr อยู่ข้างในตรงๆ ขนาดของมันจะนิยามตัวเองไม่จบ

Box ตัดวงนั้นด้วยการย้ายลูกไปไว้บน heap แล้วให้ตัว node ถือแค่ pointer ขนาดของ Expr จึงคงที่ ไม่ว่าต้นไม้จะลึกแค่ไหน

ราคาคือทุก node ที่มีลูกต้องจองหน่วยความจำแยกก้อน และการเดินต้นไม้กลายเป็นการไล่ตาม pointer ทีละต่อ นี่เป็นข้อแลกที่ tree-walking interpreter รับไว้ตั้งแต่ต้น และคอร์สนี้ไม่ได้จับเวลา จึงไม่พูดว่ามันแพงเท่าไร

match ที่ลืมกรณีไม่ได้

หัวข้อนี้แสดง pretty-printer ที่เป็น function ธรรมดาตัวเดียว และเหตุผลที่คอมไพเลอร์กันการลืมกรณีให้ได้

/// พิมพ์ต้นไม้กลับเป็นข้อความแบบ S-expression
///
/// นี่คือหลักฐานว่าต้นไม้ถูกจริง: `1 + 2 * 3` ต้องออกมาเป็น `(+ 1 (* 2 3))`
/// ไม่ใช่ `(* (+ 1 2) 3)` · ลำดับความสำคัญไม่ใช่กฎที่เขียนไว้ที่ไหน มันคือ *รูปร่าง*
/// ของต้นไม้ที่ parser สร้าง
pub fn print_expr(expr: &Expr) -> String {
    match expr {
        Expr::Literal(Literal::Nil) => "nil".to_string(),
        Expr::Literal(Literal::Bool(b)) => b.to_string(),
        Expr::Literal(Literal::Number(n)) => format_number(*n),
        Expr::Literal(Literal::Str(s)) => format!("\"{s}\""),
        Expr::Grouping(inner) => format!("(group {})", print_expr(inner)),
        Expr::Unary { op, right, .. } => format!("({} {})", op.symbol(), print_expr(right)),

ไม่มี interface ชื่อ Visitor ไม่มี method accept การทำงานใหม่บนต้นไม้คือ function ใหม่หนึ่งตัวที่ match ต้นไม้ แล้วจบตรงนั้น

Pattern Matching ทำสองอย่างในจังหวะเดียว คือเลือกกรณีและดึงข้อมูลข้างในออกมาพร้อมกัน บรรทัดของ Unary ตั้งชื่อให้ op กับ right ในจังหวะเดียวกับที่มันบอกว่านี่คือกรณีไหน

.. ที่ท้ายแปลว่า “ฟิลด์ที่เหลือไม่ใช้” pretty-printer ไม่สนใจ line แต่ evaluator ในบทที่ 4 สนใจ เพราะมันคือตัวที่ต้องรายงานความผิดพลาดตอนรัน

สิ่งที่คอมไพเลอร์รับประกันคือความครบ ลบกรณีใดกรณีหนึ่งออกจาก match นี้แล้วคอมไพล์ไม่ผ่าน ไม่ใช่ผ่านแล้วไปพังตอนรันกับ input ที่ไม่มีใครทดสอบ

ราคาที่ enum จ่าย

หัวข้อนี้บอกว่าการเลือก enum ทำให้อะไรถูกลงและทำให้อะไรแพงขึ้น เทียบกับลำดับชั้นของ class และกับ Visitor pattern

ปัญหานี้มีชื่อของมันเอง คือ expression problem และตารางของมันมีสองแกน แกนหนึ่งคือชนิดของ node อีกแกนคือการทำงานที่เดินบน node

ลำดับชั้นของ class ธรรมดาทำให้แกนชนิดถูก เพิ่ม class ลูกใหม่หนึ่งตัวได้โดยไม่แตะ code เดิมเลย แลกกับการที่การทำงานใหม่ต้องไปเติมทีละ class

Visitor pattern สลับด้านให้ การทำงานใหม่กลายเป็น class ใหม่หนึ่งตัว แลกกับการที่ node ชนิดใหม่บังคับให้แก้ interface Visitor แล้วไล่แก้ visitor ทุกตัวที่มีอยู่

enum กับ match ยืนอยู่ฝั่งเดียวกับ Visitor พอดี เพิ่มการทำงานใหม่คือเพิ่ม function หนึ่งตัว ส่วนการเพิ่ม variant ใหม่ทำให้ match ทุกอันที่มีอยู่คอมไพล์ไม่ผ่าน

สิ่งที่ enum ทำไม่ได้เลย ไม่ใช่แค่ทำยาก

enum เป็นชุดปิด ไม่มีใครนอก crate นี้เพิ่ม variant ให้ Expr ได้ ไม่ว่าจะพยายามแค่ไหน

ถ้าต้นไม้เป็น API สาธารณะ การเติมกรณีใหม่คือ breaking change ของทุกคนที่ match มันอยู่

ทางเลือกฝั่งตรงข้ามใน Rust คือ trait object ซึ่งเปิดให้เพิ่มชนิดใหม่จากนอก crate ได้ แลกกับการที่การทำงานใหม่ต้องเติม method ลง trait แล้วไล่แก้ทุกชนิดที่ implement ไว้

ข้อต่างระหว่าง enum กับ Visitor จึงไม่ได้อยู่ที่ว่าต้องแก้กี่ที่ แต่อยู่ที่ว่าใครเป็นคนหาที่เหล่านั้น คอมไพเลอร์ฟ้องทุกจุดที่ match บน Expr พร้อมชื่อ file และเลขบรรทัด

คอร์สนี้เลือก enum เพราะชนิดของ node ในภาษาหนึ่งเปลี่ยนไม่บ่อย ส่วนการทำงานบนต้นไม้เพิ่มขึ้นแทบทุกบท — เลือกให้แกนที่ขยับบ่อยเป็นแกนที่ถูก

ลองรันจริง

หัวข้อนี้อ่านผลของ pretty-printer บน script ตัวอย่าง แล้วชี้ว่ารูปร่างของต้นไม้บอกอะไรบ้าง

script ตัวอย่างของบทนี้ไม่มีอะไรพังสักบรรทัด ทุกบรรทัดมีไว้ให้เห็นรูปร่างที่ต่างกัน

// บทที่ 2 — ลำดับความสำคัญไม่ใช่กฎที่เขียนไว้ที่ไหน มันคือรูปร่างของต้นไม้
1 + 2;
1 + 2 * 3;
(1 + 2) * 3;
-5 + 1;
!true;
"a" + "b";
nil;

โหมด --ast สั่งให้ interpreter หยุดหลังด่านที่สอง แล้วพิมพ์ต้นไม้ที่ได้กลับออกมาเป็นข้อความ

คำสั่งระดับบนสุดถูกพิมพ์ผ่าน function อีกตัวที่ match บน Stmt แทนที่จะเป็น Expr

/// พิมพ์คำสั่งหนึ่งคำสั่ง
///
/// `Stmt::Expression` พิมพ์เป็นต้นไม้ของมันเปล่าๆ ไม่ห่อวงเล็บอะไรเพิ่ม —
/// expression statement คือ expression ที่ทิ้งค่า ไม่มีอะไรให้พิมพ์มากกว่านั้น
pub fn print_stmt(stmt: &Stmt) -> String {
    match stmt {
        Stmt::Expression(e) => print_expr(e),
        Stmt::Print(e) => format!("(print {})", print_expr(e)),

(+ 1 2)
(+ 1 (* 2 3))
(* (group (+ 1 2)) 3)
(+ (- 5) 1)
(! true)
(+ "a" "b")
nil

อ่านผลนี้แล้วเห็นสี่อย่างที่หัวข้อก่อนหน้าพูดถึง

1 + 2 * 3 ออกมาเป็น (+ 1 (* 2 3)) ไม่ใช่ (* (+ 1 2) 3) — ลำดับความสำคัญกลายเป็น ความลึกไปแล้ว และไม่มีตารางกฎอยู่ที่ไหนในต้นไม้เลย
วงเล็บที่คนเขียนใส่เองไม่ได้หายไปเฉยๆ (1 + 2) * 3; ให้ (* (group (+ 1 2)) 3) ซึ่งมี node Grouping คั่นอยู่ ทั้งที่รูปร่างข้างในบอกลำดับไว้ครบแล้ว
-5 + 1 ให้ (+ (- 5) 1) เครื่องหมายลบหน้าเดียวจับแน่นกว่าการบวก มันจึงห่อแค่ 5 ไม่ได้ห่อทั้งก้อน
script มีแปดบรรทัด แต่ผลรันมีเจ็ดบรรทัด comment บรรทัดแรกถูกทิ้งไปตั้งแต่ด่าน scanner ตอนถึงที่นี่มันไม่เคยมีตัวตนให้พิมพ์

ต้นไม้นี้ยังไม่มีใครสร้าง

หัวข้อนี้บอกว่าบทนี้จบลงที่รูปร่างของต้นไม้ ส่วนตัวที่แปลง token เป็นต้นไม้ยังไม่มี

ทั้งบทพูดถึงรูปร่างของต้นไม้ กับ function ที่เดินบนมัน แต่ยังไม่มีที่ไหนเลยที่ประกอบต้นไม้ขึ้นมาจากลำดับ token

ตัวที่ทำงานนั้นคือ parser ในบทที่ 3 และวิธีของมันคือแปลงกฎไวยากรณ์แต่ละข้อให้กลายเป็น function หนึ่งตัว

ลำดับความสำคัญที่บทนี้แสดงเป็นความลึกของ node จะกลายเป็นลำดับการเรียกของ function พวกนั้น

🔗 อ้างอิงต้นทางของบทนี้

Crafting Interpreters — Robert Nystrom, บทที่ 5 “Representing Code” (ตรวจแล้ว 2026-08-12) — ที่มาของโครงต้นไม้ที่คอร์สนี้ใช้ และเป็นที่ที่ expression problem ถูกอธิบายเป็นตารางสองแกน พร้อมเหตุผลว่าทำไม Visitor pattern ถึงทำให้แกนการทำงานถูก โดยแลกกับแกนชนิด
The Rust Programming Language — บทที่ 15 “Using Box<T> to Point to Data on the Heap” (ตรวจแล้ว 2026-08-12) — หัวข้อ “Enabling Recursive Types with Boxes” อธิบายว่าทำไม ชนิดที่ซ้อนตัวเองโดยไม่ผ่าน pointer ถึงคอมไพล์ไม่ผ่าน ซึ่งเป็นเหตุผลเดียวกับที่ Expr ต้องใช้ Box
Oracle — Pattern Matching for switch (Java 21) (ตรวจแล้ว 2026-08-12) — หลักฐานว่าคอมไพเลอร์ของ Java ตรวจความครบของกรณีให้ได้แล้ว เมื่อชนิดที่รับมาเป็น sealed ซึ่งเป็นสิ่งที่ยังไม่มีตอนตำราต้นทางถูกเขียน

เช็กความเข้าใจ — บทที่ 2

ข้อ 1 / 3

ถ้าเติม variant ใหม่ลงใน enum Expr แล้วไม่ไปแก้อะไรอีกเลย แล้วสั่งคอมไพล์ จะเกิดอะไรขึ้น

AST — ต้นไม้​ที่​เป็น enum ไม่ใช่ Visitor pattern

เส้นตรง​เก็บ​ลำดับ​ความ​สำคัญ​ไม่​ได้

Visitor pattern ถูก​สร้าง​มา​แก้​ปัญหา​อะไร

enum เดียว​แทน​ลำดับ​ชั้น​ทั้ง​ชั้น

Box โผล่​ตรง​ที่​ต้นไม้​ซ้อน​ตัวเอง

match ที่​ลืม​กรณี​ไม่​ได้

ราคา​ที่ enum จ่าย

ลอง​รัน​จริง

ต้นไม้​นี้​ยัง​ไม่มี​ใคร​สร้าง