Lập trình: lập trình bằng thứ còn ít hơn cả hư vô

 (joshmoody.org)
2 điểm bởi GN⁺ 2025-10-24 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bài viết này là một câu chuyện châm biếm trong bối cảnh phỏng vấn, nơi ứng viên cố triển khai bài toán FizzBuzz đơn giản bằng các tổ hợp hàm thuần túy dựa trên phép tính lambda
  • Nhân vật chính bắt đầu với JavaScript nhưng dần định nghĩa các tổ hợp tử S, K, I, tự mình tái dựng cấu trúc cơ bản của ngôn ngữ
  • Sau đó, anh ta biểu diễn boolean, số, danh sách, chuỗi chỉ bằng các tổ hợp tử, rồi hiện thực đệ quy thông qua tổ hợp tử Y
  • Cuối cùng, FizzBuzz được hoàn thiện theo phong cách point-free hoàn toàn, nhưng đoạn mã phình ra đến mức con người không thể hiểu nổi
  • Bài viết khám phá một cách hài hước bản chất của ngôn ngữ lập trình và cực hạn của sự trừu tượng hóa, đồng thời bộc lộ tính tự trào của văn hóa lập trình viên

Khởi đầu buổi phỏng vấn: FizzBuzz và tổ hợp tử

  • Câu chuyện mở đầu với cảnh người phỏng vấn Dana yêu cầu ứng viên giải bài toán FizzBuzz
    • Thay vì dùng vòng lặp thông thường, ứng viên bắt đầu bằng cách định nghĩa các tổ hợp tử S và K để giải bài toán
    • Dana thấy khó hiểu, nhưng ứng viên nói rằng “chỉ cần thêm một chút nữa thôi” rồi tiếp tục
  • Ứng viên định nghĩa thêm nhiều tổ hợp tử như I, B, C, W, T, và dùng chúng như những thành phần cơ bản của một ngôn ngữ mới
    • Mỗi tổ hợp tử hiện thực các khái niệm cốt lõi của phép tính lambda như hợp thành hàm, hoán đổi đối số, tự áp dụng
    • Trong chú thích mã xuất hiện các biệt danh như “Bluebird, Cardinal, Warbler, Thrush” cho những tổ hợp tử này

Định nghĩa boolean và số

  • Ứng viên xây dựng logic boolean bằng cách định nghĩa TRUE, FALSE, NOT chỉ với các tổ hợp tử
    • Dana hỏi “đây là phép tính lambda à”, nhưng ứng viên đáp rằng “phép tính lambda quá cồng kềnh”
  • Tiếp đó, anh ta định nghĩa ZERO, SUCC, PRED, IS_ZERO để tạo thành hệ số (Church numeral)
    • SUCC hiện thực toán tử kế tiếp, PRED là tiền nhiệm, còn DECREMENT là phép giảm không đi xuống dưới 0
    • Các số từ ONE đến TEN được định nghĩa tuần tự

Đệ quy và tổ hợp tử Y

  • Ứng viên định nghĩa hàm ADD rồi dần chuyển nó sang dạng point-free
    • ADD_MAKER được định nghĩa và bọc bằng tổ hợp tử Y để cho phép đệ quy
    • Dana chỉ ra rằng “JavaScript cũng đệ quy được”, nhưng ứng viên trả lời rằng “sắp nữa thì nó sẽ không còn là JavaScript nữa”
  • Khi đánh giá nghiêm ngặt (eager evaluation) của JavaScript gây tràn ngăn xếp, ứng viên chạy mã bằng một trình thông dịch JS “lười” tên là Skoobert
    • Kết quả in ra thành công 3

Số học, danh sách và chuỗi

  • Ứng viên hiện thực toàn bộ các phép toán số học như SUBTRACT, MULTIPLY, MOD, DIVIDE trên nền tổ hợp tử
    • Mỗi phép toán được cấu thành bằng cách kết hợp đệ quy IS_ZERO, PRED, SUCC và các thành phần khác
  • Sau đó, anh ta định nghĩa CONS, FIRST, REST, EMPTY để xây dựng cấu trúc danh sách
    • Các phép toán hàm bậc cao như MAP, FOLD, RANGE, CONCAT cũng đều được hiện thực dưới dạng tổ hợp tử
  • Để in danh sách dưới dạng chuỗi, anh ta viết các hàm renderList, showLines
    • Dana dường như đã bỏ cuộc và không còn phản ứng gì nữa

Cấu thành ký tự và chuỗi

  • Ứng viên định nghĩa mã ký tự từ 1 đến 9, rồi theo từng bậc 10 bằng các tổ hợp tử
    • Từ CHAR_A đến CHAR_Z, và từ CHAR_0 đến CHAR_9, tất cả đều được biểu diễn bằng các tổ hợp số
  • Thông qua hàm ARRAY, anh ta chuyển chuỗi thành danh sách và tạo ra FIZZ, BUZZ, FIZZBUZZ
    • Hàm extractString được dùng để chuyển danh sách thành chuỗi thực
    • Kết quả in ra console là "fizzbuzz"

Chuyển từ số sang chuỗi

  • Anh ta định nghĩa NUMBER_TO_DIGIT_LIST để đổi số thành danh sách chữ số, rồi NUMBER_TO_STRING để đổi danh sách đó thành chuỗi
    • DIVIDE, MOD, TEN được dùng để tách từng chữ số
    • Việc ánh xạ sang ký tự số được thực hiện qua danh sách DIGITS_NUMERAL
  • Nhờ quá trình này, phép biến đổi số → ký tự → chuỗi trở nên khả thi hoàn toàn trong hệ tổ hợp tử

Hoàn thiện FizzBuzz

  • FIFTEEN, ONE_HUNDRED được định nghĩa, rồi MAP và RANGE được dùng để tạo danh sách từ 1 đến 100
    • Với mỗi số, chương trình kiểm tra bội số của 3, 5, 15 để in "Fizz", "Buzz", "FizzBuzz" hoặc chuỗi biểu diễn số tương ứng
    • Kết quả cuối cùng được in bằng showLines(extractString)(FIZZBUZZ_RESULT)
  • Dana hỏi “giờ thì hài lòng chưa”, nhưng ứng viên tiếp tục xóa mọi định nghĩa biến và viết lại toàn bộ chỉ bằng các tổ hợp tử thuần túy
    • Kết quả là một biểu thức khổng lồ chỉ gồm S và K dài tới hàng nghìn dòng

Kết cục và ý nghĩa

  • Bài viết vừa khám phá những thành phần nền tảng của ngôn ngữ lập trình, vừa châm biếm xu hướng của lập trình viên biến một bài toán đơn giản thành thứ phức tạp quá mức
    • Tiêu đề “lập trình bằng thứ còn ít hơn cả hư vô” tượng trưng cho nỗ lực tái kiến tạo thế giới từ những đơn vị tối thiểu của ngôn ngữ
  • Đây là một tác phẩm kỹ thuật giàu tính văn chương, diễn giải bằng hài hước và tự sự về lập trình hàm, phép tính lambda, logic tổ hợp tử
    • Đồng thời, nó cũng trào phúng tinh thần “ngay cả FizzBuzz cũng có thể biến thành một thí nghiệm triết học” của giới lập trình viên

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-10-24
Ý kiến Hacker News

  • Có vẻ mọi người đang nghĩ “rốt cuộc cái này là gì vậy?”, nên thử giải thích trọng tâm của combinator
    combinator là một hàm không thay đổi trạng thái toàn cục và không capture biến bên ngoài. Với cùng một đối số, nó luôn cho ra cùng một kết quả và không ảnh hưởng gì đến phần còn lại của hệ thống
    Khi kết hợp các hàm thuần như vậy, ta lại tạo ra một combinator khác. Tức là hợp thành của các hàm thuần vẫn là hàm thuần
    Những hàm này cũng có thể dễ dàng viết bằng assembly hay C. Ví dụ, nếu hiện thực trực tiếp S và K trên x64, rồi biên dịch Common Lisp theo kiểu dựa trên combinator lên trên đó, thì rốt cuộc Lisp sẽ chạy trên hai hàm assembly
    Hiệu năng có lẽ không tốt, nhưng nếu tạo vài trăm mẫu dùng thường xuyên thành inline combinator và đặt tên cho chúng, thì nó sẽ trở thành một “cỗ máy” khá thực dụng
    Kiểu cấu trúc này cũng giống Forth sợ mutation, một bytecode VM, hoặc một CPU gọi combinator là “lệnh”
    Cuối cùng, có thể xem combinator là một biểu đạt của khoa học máy tính ứng dụng bỏ qua tối đa các chi tiết triển khai. Vì vậy có thể nói nó đơn giản hơn lambda calculus
    Nếu hiện thực lambda calculus bằng vài combinator, rồi đặt Lisp lên trên đó, thì lượng công việc phụ thuộc máy móc cần làm ở đáy của stack sẽ giảm xuống cực kỳ nhiều

    • Có cảm giác như ở đâu đó có một hàm đã tự gọi chính nó và nhận seed round
    • Hồi còn là sinh viên tôi từng làm thứ tương tự rồi (không phải Lisp mà là một ngôn ngữ đơn giản được mở rộng macro thành lambda calculus), và việc mọi thứ đều có thể hiện thực chỉ với S và K thật sự rất gây sốc. Nhưng đồng thời cũng ngạc nhiên vì nó kém hiệu quả đến mức nào. Dù vậy, khi tập lệnh cơ sở lớn dần lên thì tình hình cải thiện đáng kể
    • Về lý thuyết thì làm được cả, nhưng trong thực tế cần chọn một nền tảng tính toán thực dụng hơn nhiều so với graph rewriting. Trừ khi bạn đang thử nghiệm giới hạn của khả năng tính toán, không thì thứ này gần như chỉ là trò biểu diễn. Thêm nữa, cách biểu diễn số cũng là một vấn đề. Ít nhất phải dùng số nguyên bù hai và destructor hiệu quả thì mới đáng để trầm trồ
    • Tò mò không biết có Lisp hiện thực trên combinator kiểu này thật sự tồn tại không. Nếu có thì port nó chắc khá vui
  • let A = (x) => (y) => (z) => x(z)(y((w) => z))

    Chỉ cần tổ hợp cái này vài lần là được

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);

    “Tôi tuyệt đối không dùng lambda calculus. Nó là một ngôn ngữ phình to quá mức.”
    Nhưng trên thực tế, combinatory logic còn phình to hơn. Để biểu diễn cùng một chương trình thì cần nhiều bit hơn
    Lambda calculus trái lại là một trong những ngôn ngữ gọn nhất
    Ngay cả trong ngôn ngữ eager như JavaScript, nếu bọc đối số trong lambda giả thì vẫn có thể làm cho nó trở thành lazy. Xem ví dụ ở trình thông dịch JS BLC này
    Các bài viết liên quan: PDF này và ví dụ IOCCC

    • Điểm thú vị là những trình thông dịch lambda calculus nhanh nhất (ví dụ uni.c) rốt cuộc đều chuyển lambda expression sang combinatory logic để tính toán. Chỉ là chúng dùng một tập cơ sở lớn hơn S, K
    • “bloated language” nghĩa là một ngôn ngữ có quá nhiều tính năng không cần thiết. Ví dụ, C++ có thể ngắn hơn C về mặt mã nguồn nhưng lại là ngôn ngữ phức tạp hơn nhiều
    • Nhìn khối mã đó làm tôi bật ra âm thanh gần như trùng hẳn với danh sách đối số
    • Có vẻ định nghĩa K và S bị lỗi ngoặc. Bản sửa là như sau 
      let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
      Và để biến một ngôn ngữ eager thành lazy thì có thể làm kiểu này 
      let A = x => y => z => () => x()(z())(y()(w => z()));
    • Tự nhiên nảy ra câu hỏi “w là cái gì vậy?”

  • “Biết FizzBuzz chứ?”
    “Tất nhiên rồi. Bản code golf 10 ký tự, bản 12 dòng mà junior cũng hiểu, hay bản hoàn toàn quái lạ chỉ để khoe kiến thức kỳ quặc?”

    • Nhìn cái này xong tôi thử hiện thực FizzBuzz nhanh nhất bằng C64 BASIC. Lãng phí buổi sáng theo cách khá vui
      Liên kết kết quả

  • Phần giải thích combinator logic thật sự rất tuyệt. Văn phong làm tôi nhớ đến series này

    • Nói là giải thích thì đúng hơn là một màn trình diễn để phô diễn. Dù vậy vẫn khá ấn tượng
    • Đúng là có vẻ lấy cảm hứng từ series đó. Giá mà tác giả nhắc tên thì tốt hơn
    • Ở Anh thì bị chặn truy cập vì Online Safety Act, khá đáng tiếc

  • Làm tôi nhớ đến bài “FizzBuzz in TensorFlow” từng đọc trước đây
    Liên kết

    • Bài này ít nhất còn theo kịp được nên thấy ổn

  • Kiểu khung phỏng vấn lập trình này có vẻ hơi sai
    Mục đích của phỏng vấn là (1) kiểm tra kiến thức lập trình của ứng viên, (2) xem họ có phù hợp với văn hóa lập trình của công ty không
    Ví dụ, nếu đang tuyển vị trí JavaScript mà ai đó lại quá sa đà vào combinatory logic, thì có khả năng là không hợp về mặt văn hóa. Vì vậy bị loại cũng không có gì lạ

    • Có lẽ đang tham chiếu series này. Chỉ là trong nguyên văn không nói rõ
    • Đôi khi tôi thấy các commenter trên HN như những người đã quên mất niềm vui
    • Đúng là nó nhấn mạnh tính đa dạng của lập trình, nhưng đó chỉ là một dạng tuyển chuyên môn cho một hệ sinh thái cụ thể. Phần lớn là lựa chọn để làm việc với legacy code hay tận dụng hệ sinh thái sẵn có
    • Mấy câu kiểu “IQ thấp thì trượt” nghe buồn cười, nhưng rốt cuộc nếu trả đủ tiền thì kiểu OOP/FP/FRP nào người ta cũng thích nghi được
    • Ngoài đời gần như không có mấy cuộc phỏng vấn lý tưởng như vậy. Đa số là những người phỏng vấn thất vọng áp đặt thế giới quan của họ. Công việc thực tế thì hầu như chẳng liên quan gì đến nội dung phỏng vấn

  • Đến lúc phải nhớ tên Moses Schönfinkel rồi
    Ông đã phát minh combinatory logic vào năm 1920 khi còn là học trò của Hilbert. Sau khi trở về Nga, ông mắc bệnh tâm thần và qua đời trong nghèo khó ở Moskva. Theo Wikipedia, các bài báo của ông đã bị hàng xóm đem đốt làm chất đốt sưởi ấm

  • Khối mã cuối cùng lớn đến mức phải cuộn ngang (166KB)
    S và K là các hàm được curry, mỗi lần chỉ nhận một đối số
    Xem thêm câu trả lời StackOverflow này

    • Lúc cuộn xuống mà thấy syntax highlighting bỏ cuộc giữa chừng là buồn cười nhất

  • Tôi rất thích các tên loài chim như “Bluebird, cardinal, warbler, thrush”. Muốn lấy đó làm quy ước đặt tên mới luôn
    “Barendregt. Church nổi tiếng quá rồi.”
    “Sắp chẳng còn là JavaScript nữa đâu.”
    Cảm giác như Douglas Adams đang dạy SICP

    • Các tên loài chim này đến từ 『To Mock a Mockingbird』 của Smullyan. Trong đó còn có nhiều loài chim khác nữa

  • “Đó là… Y combinator à?”
    “Đúng vậy. Muốn đệ quy thì cần nó.”
    Một sự thật thú vị: fixed-point combinator có vô hạn biến thể. Tức là ngay cả không có Y combinator thì vẫn có vô số cách để hiện thực đệ quy