Đến sáng hôm sau, Ken Thompson đã biến code tìm kiếm trong trình soạn thảo ed thành grep, công cụ tìm kiếm văn bản của Unix.

17/10/2026 · VietTechies · Biên tập

Một buổi chiều ở Bell Labs, Doug McIlroy — theo lời ông tự kể — hỏi Ken Thompson liệu có thể tách bộ so khớp biểu thức chính quy (regular expression) ra khỏi trình soạn thảo văn bản ed, rồi biến nó thành một chương trình đọc qua tệp trong một lượt hay không. “Sáng hôm sau, tôi thấy trong hộp thư có lời nhắn thông báo về một chương trình tên là grep”, McIlroy sau này nhớ lại. Trang hướng dẫn (manual page) đầu tiên của Unix dành cho grep đề ngày 3 tháng 3 năm 1973.

Kể vắn tắt thì câu chuyện nghe như một kỳ tích lập trình trong một đêm. Điều hữu ích hơn lại nằm ở những gì Thompson không phải viết. Code tìm kiếm đã nằm sẵn trong ed, và grep chính là phần code ấy, được giải phóng khỏi một trình soạn thảo không chứa nổi tệp lớn.

Cuốn từ điển mà ed không chứa nổi

Đề nghị của McIlroy xuất phát từ việc ông đang làm một chương trình đọc văn bản thành tiếng qua bộ tổng hợp giọng nói. Trong lúc nghĩ ra các quy tắc phát âm dựa trên chính tả tiếng Anh, ông tra từ điển Webster để tìm những từ có thể không tuân theo một quy tắc nào đó. Chẳng hạn, cặp chữ “ui” được đọc khác nhau trong “fruit”, “guile”, “guilty” và “anguish”.

Trở ngại nằm ở chính ed. McIlroy phải chia cuốn từ điển thành từng phần cho vừa vùng đệm (buffer) có hạn của ed, sau đó dùng lệnh toàn cục (global) của trình soạn thảo này để lọc ra các danh sách từ, rồi quét đi quét lại để thu hẹp dần các danh sách ấy. Trong ed, lệnh g/re/p có nghĩa là: với mọi dòng khớp biểu thức chính quy re, in dòng đó ra. Mỗi lần như vậy, ed chép một phần từ điển vào một tệp tạm, quét tệp ấy hai lượt rồi vứt bỏ. McIlroy nhận xét quy trình ấy vừa tẻ nhạt vừa “lãng phí kinh khủng”.

Đến sáng hôm sau, Thompson đã làm được gì

Thompson đáp lại bằng cách lấy chính lệnh ed mà McIlroy cứ chạy đi chạy lại và biến lệnh ấy thành một chương trình riêng. McIlroy nhớ lại rằng khi được hỏi cái tên lạ lùng grep có nghĩa gì, Thompson bảo điều đó là hiển nhiên: cái tên ấy ứng với lệnh ed mà chương trình này mô phỏng, tức g/re/p, viết tắt của “global regular expression print”. Bộ tài liệu hướng dẫn của Unix phiên bản thứ tư (Fourth Edition) — bộ đầu tiên có grep — tóm gọn chương trình này trong đúng một dòng: “tìm một mẫu trong một tệp”.

Vì grep đọc qua dữ liệu đầu vào trong một lượt thay vì nạp dữ liệu vào vùng đệm của một trình soạn thảo, McIlroy không còn phải chia cuốn từ điển thành từng phần nữa. Nếu không được chỉ định tệp nào, grep đọc từ đầu vào chuẩn (standard input), nhờ vậy đầu ra của một chương trình khác có thể chảy thẳng vào grep.

Bản thân bộ so khớp không có gì mới. Trước đó, Thompson đã đưa biểu thức chính quy vào phiên bản trình soạn thảo QED của mình, và mô tả một phương pháp so khớp trong một bài báo năm 1968 đăng trên Communications of the ACM, một tạp chí của Hiệp hội Máy tính (ACM). Tài liệu năm 1987 của McIlroy về lịch sử Research Unix mô tả việc Thompson làm: “Thompson nhanh chóng giải phóng bộ so khớp biểu thức chính quy của mình và đặt tên cho nó theo lệnh g/re/p của ed.” Theo cách McIlroy kể, việc cần làm là giải phóng code có sẵn, chứ không phải nghĩ ra code mới.

Về mặt kỹ thuật, câu chuyện còn có một điểm bất ngờ. Theo lập trình viên Russ Cox, khi viết ed, Thompson đã chọn không dùng thuật toán năm 1968 của mình, và thay vào đó, ed cùng hậu duệ của nó là grep dùng phương pháp quay lui đệ quy (recursive backtracking). Một bộ so khớp kiểu quay lui thử một cách khớp; nếu cách đó không thành, nó lùi lại và thử cách khác. Cũng theo lời Cox, công cụ Unix đầu tiên hỗ trợ đầy đủ cú pháp biểu thức chính quy là egrep của Al Aho, ra mắt trong phiên bản thứ bảy (Seventh Edition) năm 1979; egrep so khớp bằng một ôtômat (automaton) tính sẵn, tức một máy trạng thái dựng từ mẫu trước khi bắt đầu tìm kiếm.

Hai lời kể về người đã đề nghị viết grep

Không phải bản kể nào cũng có McIlroy. Trong một cuộc phỏng vấn năm 2018 với kênh YouTube Computerphile, Brian Kernighan, đồng nghiệp của Thompson ở Bell Labs, lại kể rằng lời đề nghị đến từ Lee McMahon, người muốn tìm mọi chỗ một từ xuất hiện trong bộ tiểu luận Federalist Papers. Bộ văn bản này nặng khoảng một megabyte, vượt quá sức chứa của ed. Theo lời Kernighan kể, McMahon đem chuyện này hỏi Thompson rồi về nhà; hôm sau quay lại, McMahon thấy Thompson đã viết xong chương trình.

Trong lời tự kể in ở cuốn sách Netizens năm 1997, McIlroy đặt chính mình và cuốn từ điển vào trung tâm câu chuyện. Còn tài liệu lịch sử năm 1987 do chính McIlroy viết thì không nói ai là người đề nghị: tài liệu ấy viết rằng grep ra đời khi Thompson “được hỏi làm sao tìm các mẫu trong một tệp quá lớn đối với trình soạn thảo”. Các nguồn tư liệu không phân định được ai là người đề nghị. Cả hai bản kể đều thống nhất ở những điểm cốt lõi: một tệp mà ed không chứa nổi, và đến hôm sau đã có một chương trình chạy được.

Từ một lệnh ed thành cả một họ công cụ Unix

Tài liệu lịch sử năm 1987 của McIlroy ghi rằng grep “thường được nhắc tới như hình mẫu tiêu biểu của công cụ phần mềm”: một chương trình nhỏ chuyên làm một việc với bất kỳ văn bản nào được đưa vào. Al Aho, tác giả của egrep, còn đưa fgrep vào phiên bản thứ bảy; fgrep tìm các chuỗi cố định thay vì biểu thức chính quy. Cái tên grep cũng lan ra ngoài phạm vi Unix. Năm 2016, McIlroy gọi grep là “một từ mới nghe êm tai, hữu ích đến mức đã lọt vào OED [Từ điển tiếng Anh Oxford] ở cả dạng danh từ lẫn động từ”.

Vì sao giải phóng code quan trọng hơn viết code nhanh

Lựa chọn thiết kế có sức sống lâu dài không phải là một thuật toán tài tình. Đó là quyết định thôi coi tìm kiếm là việc một trình soạn thảo làm trên tệp mà nó đang giữ, và thay vào đó, biến tìm kiếm thành một lượt duyệt duy nhất qua một luồng (stream) gồm các dòng văn bản. Cùng một bộ so khớp ấy, khi nằm trong ed thì chật chội, ra khỏi ed lại trở nên hữu ích hơn nhiều.

Khi một tính năng bị kẹt bên trong một chương trình lớn hơn, cách khắc phục có thể là tách tính năng ấy ra thay vì viết lại. Hơn 50 năm sau, lập trình viên nào gõ grep cũng đang đánh vần lại — chỉ thiếu các dấu gạch chéo — chính lệnh ed mà McIlroy từng chạy trên cuốn từ điển bị cắt thành từng phần: g/re/p.

Bài liên quan

Đọc bằng ngôn ngữ khác: English