Phát triển chương trình bằng cách tinh chế từng bước
đã đăng vào 15, Tháng 1, 2025, 16:00Phát triển chương trình bằng cách tinh chế từng bước
Bản dịch không chính thức bài luận "Program Development by Stepwise Refinement" của tác giả Niklaus Wirth, xuất bản năm 1971. Người dịch có chỉnh sửa một số thứ cho hợp thời đại, sự thay đổi (hy vọng sẽ) được ghi tường minh, sửa văn phong trang trọng và cách dùng một số từ trừu tượng của bài luận cho gần gũi với người dịch (và hy vọng cũng với người đọc) hơn. Người dịch ghi chú cá nhân ở khúc mình thấy khó hiểu thành một số đoạn văn bắt đầu bằng cụm "Người dịch ghi chú:", người đọc có thể bỏ qua mà không ảnh hưởng tới nội dung hay trải nghiệm đọc bài luận.
Tóm lược
Lập trình khác với gõ code ở chỗ có sự sáng tạo, thường được dạy bằng ví dụ nhằm trưng bày kỹ thuật cụ thể. Trong bài luận này, hành động lập trình được xem là một dãy lựa chọn về thiết kế để xem xét chia nhỏ từ nhiệm vụ thành nhiều nhiệm vụ phụ và từ dữ liệu thành cấu trúc dữ liệu. Tiến trình liên tiếp tinh chế nội dung chi tiết được minh họa bằng một ví dụ ngắn nhưng không tầm thường, từ đây rút ra một số kết luận về nghệ thuật và cách dạy lập trình.
Giới thiệu
Lập trình thường được dạy bằng ví dụ. Kinh nghiệm cho thấy sự thành công của khóa học lập trình phụ thuộc sống còn ở chỗ lựa chọn ví dụ nào. Không may là, ví dụ quá thường xuyên được chọn với ý định chính yếu là trình diễn xem máy tính (hay ngôn ngữ lập trình đang được dạy) có thể làm được gì. Thay vì vậy thì tiêu chuẩn tuyển chọn chính cần phải là vì ví dụ này phù hợp để trình diễn kỹ thuật áp dụng được ở nhiều nơi. Hơn nữa, chương trình ví dụ thường là "sản phẩm" đã hoàn thành kèm theo giải thích về mục đích và chi tiết ngữ nghĩa. Nhưng lập trình có tính thiết thực sở dĩ là thiết kế ra chương trình mới hơn là ngắm nghía chương trình cũ. Hệ quả của phương pháp dạy này là học trò có ấn tượng rằng lập trình chính yếu là thành thạo một ngôn ngữ (thạo luôn nhiều cái kỳ dị và rắc rối của nó nhất là với ngôn ngữ lập trình hiện đại) rồi nhờ cậy trực giác để biến đổi ý tưởng thành chương trình hoàn thiện bằng cách nào đó. Rõ ràng là khóa học lập trình cần phải dạy phương pháp thiết kế và xây dựng, và chọn được ví dụ trình diễn được sự triển khai dần dần một cách thú vị.
Bài viết này nêu một ví dụ được chọn với hai mục đích này trong đầu. Vài kỹ thuật thông dụng được trình diễn một cách vắn tắt và khuyến khích (chiến lược chọn trước, xây dựng lời giải để thử theo từng bước, giới thiệu dữ liệu phụ trợ, đệ quy), và chương trình được triển khai dần dần theo dãy các bước tinh chế.
Mỗi bước như vậy chia nhỏ câu lệnh của chương trình đã cho thành vài câu lệnh chi tiết hơn. Sự chia nhỏ hay tinh chế nội dung chi tiết liên tiếp này kết thúc khi mọi câu lệnh được diễn tả bằng ngôn ngữ máy tính hay ngôn ngữ lập trình bên dưới, do đó việc này phải theo hướng của phương tiện sẵn có trên máy hay ngôn ngữ muốn đến. Kết quả thực thi chương trình được diễn tả bằng dữ liệu, và có thể cần phải giới thiệu thêm dữ liệu để liên lạc giữa các nhiệm vụ phụ hay câu lệnh thu được. Càng tinh chế nhiệm vụ, thì có thể càng cần tinh chế, chia nhỏ, cấu trúc hóa dữ liệu; cho nên tinh chế nội dung chi tiết của chương trình và của dữ liệu một cách đồng thời là điều tự nhiên.
Mỗi bước tinh chế dẫn tới vài lựa chọn về thiết kế. Quan trọng là các lựa chọn này cần được làm cho tường minh và là người lập trình cần nhận biết các tiêu chuẩn bên dưới và sự tồn tại của các lời giải khác. Các lời giải khả dĩ của bài toán đã cho nhô ra tạo thành lá của cây, mỗi nút của cây này biểu diễn một chỗ tính toán cân nhắc và đưa ra lựa chọn. Các cây con có thể xem là các họ lời giải có tính chất và cấu trúc chung nào đó. Ý niệm như vậy về cây có thể giúp ích một cách đặc biệt trong tình huống thay đổi mục đích và môi trường mà chương trình đôi lúc phải thích ứng.
Thông tin hướng dẫn tiến trình tinh chế từng bước cần và càng cần phải là nguyên lý để chia nhỏ các lựa chọn, để gỡ rối các lãnh vực chỉ tưởng chừng phụ thuộc lẫn nhau, và để trì hoãn lựa chọn về biểu diễn chi tiết lâu nhất có thể. Nguyên lý này tạo ra chương trình dễ thích ứng hơn với nhiều môi trường (ngôn ngữ hay máy tính) khác nhau có thể cần nhiều cách biểu diễn khác nhau.
Bài toán mẫu được chọn được phát biểu ở đầu chương 3. Người đọc nên cố gắng tự tìm lời giải trước khi đưa mình vào phần luận giải, vốn chỉ trình bày một trong nhiều lời giải khả dĩ.
Ký pháp
Wirth trong bản gốc dùng ngôn ngữ mở rộng của Algol 60 để mô tả chương trình, bản dịch này thay vì vậy dùng ngôn ngữ mở rộng của Oberon-2 - công trình của chính tác giả - để mô tả. Oberon-2 là ngôn ngữ dễ đọc, mọi từ khoá tiếng Anh đều dễ hiểu và được ghi hoàn toàn bằng chữ in hoa. Người dịch mở rộng cho phép ký tự unicode trong định danh để tiện trình bày bằng tiếng Việt; và cho phép chỉ số của mảng thuộc khoảng định nghĩa tùy ý thay vì bắt đầu từ 0, để trình bày cho rõ hơn. Hiểu biết các từ khóa tiếng Anh có thể làm mô tả chương trình được tự nhiên hơn. Lưu ý là Algol 60 lẫn Oberon-2 đều cho phép khai báo thủ tục lồng nhau, trong đó thủ tục khai báo bên trong truy cập được biến của thủ tục bên ngoài.
Bài toán 8-hậu và một cách tiếp cận lời giải
Cho bàn cờ vua 8 x 8 và 8 quân hậu thù ghét nhau. Tìm cấu hình, tức vị trí đặt từng quân hậu sao cho không có quận hậu nào nằm trên đường đi của quân hậu khác (tức là sao cho mỗi dòng, mỗi cột và mỗi đường chéo chỉ chứa tối đa một quân hậu).
Bài toán này là tiêu biểu cho tình huống khá thường thấy là không biết lời giải phân tích (dạng đóng tổng quát), mà phải viện tới phương pháp thử sai. Điển hình là, tồn tại tập hợp ứng viên cho lời giải $A$, từ $A$ cần chọn ra một cái thoả điều kiện $p$ nhất định. Do đó một lời giải được mô tả đặc điểm là cái $x$ sao cho $(x \in A ) \land p(x)$.
Chương trình hiển nhiên để tìm một lời giải là:
REPEAT sinh ra phần tử tiếp theo của A và gọi nó là x
UNTIL p(x) OR (không còn phần tử nào khác trong A);
IF p(x) THEN lời giải là x
Chỗ khó của bài toán dạng này thường là kích thước kinh khủng của $A$ không cho phép sinh ra hết mọi ứng viên vì lo ngại về hiệu quả. Trong ví dụ hiện tại, $A$ có $64!/(56! \times 8!) \approx 2^{32}$ phần tử (cấu hình bảng). Giả định rằng sinh ra và kiểm tra mỗi cấu hình tốn 100 micro-giây, thì cần khoảng 7 tiếng đồng hồ tìm một lời giải. Rõ ràng là cần sáng chế "đường tắt", là phương pháp giúp loại trừ một lượng lớn đối thủ mà "dễ thấy" là bị loại. Chiến lược chọn trước này có đặc điểm như sau: tìm cách biểu diễn của $p$ mà có dạng $p = q \land r$, rồi đặt $Br={x | (x \in A) \land r(x)}$. Hiển nhiên là $Br \subseteq A$. Thay vì sinh ra phần tử của $A$ thì chỉ cần tạo ra phần tử của $B$ rồi kiểm tra bằng điều kiện $q$ thay vì $p$. Ứng viên phù hợp cho điều kiện $r$ là những cái thoả mãn các đòi hỏi này:
$B_r$ nhỏ hơn nhiều so với $A$.
Dễ dàng sinh ra phần tử của $B_r$.
Điều kiện $q$ dễ kiểm tra hơn điều kiện $p$.
Chương trình tương ứng lúc này là:
REPEAT sinh ra phần tử tiếp theo của B và gọi nó là x
UNTIL q(x) OR (không còn phần tử nào khác trong B);
IF q(x) THEN lời giải là x
Một điều kiện $r$ phù hợp cho bài toán 8-hậu là luật mỗi cột của bảng phải có đúng một quân hậu. Điều kiện $q$ lúc này chỉ còn là có tối đa một quân hậu trong mỗi dòng và trong mỗi đường chéo mà rõ ràng là ít nhiều dễ kiểm tra hơn $p$. Tập hợp $B_r$ (mọi cấu hình mà mỗi cột có một quân hậu) chứa "chỉ có" $8^8=2^{24}$ phần tử. Các cấu hình này được sinh ra bằng cách giới hạn chuyển động của từng quân hậu theo từng cột. Do đó mọi điều kiện ở trên đều thoả mãn.
Lại giả định thời gian 100 micro-giây để sinh ra và kiểm tra một lời giải tiềm năng, tìm một lời giải bây giờ chỉ mất 100 giây. Ai có máy tính mạnh trong tay thì có lẽ dễ dàng thoả mãn với hiệu năng dường này. Ai kém may mắn hơn và buộc phải, chẳng hạn giải bằng tay, thì mất 280 tiếng đồng hồ sinh ra và kiểm tra cấu hình với tốc độ một giây mỗi cái. Khi đó có lẽ đáng để dành thêm thời gian tìm đường tắt đi xa hơn. Thay vì áp dụng cùng phương pháp như trước, một phương pháp khác được phát biểu có đặc điểm như sau: Tìm cách biểu diễn lời giải để thử $x$ thành dạng $[x1, x2, ..., xn]$ sao cho có thể sinh ra mọi lời giải để thử từ các bước mà lần lượt tạo ra $[x1]$, $[x1, x2]$, ..., $[x1, x2, ..., x_n]$. Sự chia nhỏ này phải sao cho:
Mỗi bước (sinh ra $x_j$) phải tính toán đơn giản hơn đáng kể so với toàn bộ ứng viên $x$.
$q(x) \supset q(x1...xj)$ với mọi $j \leq n$.
Vậy không bao giờ thu được lời giải hoàn chỉnh bằng cách mở rộng lời giải để thử một phần mà không thoả vị từ $q$. Tuy nhiên ở chiều ngược lại, lời giải để thử một phần thoả $q$ có thể không mở rộng được thành lời giải hoàn chỉnh. Phương pháp gọi là xây dựng lời giải để thử theo từng bước này do đó cần phải "rút ngắn" lời giải để thử nếu thất bại ở bước j để mà thử hướng mở rộng khác. Kỹ thuật này gọi là quay lui với đặc điểm được khái quát bằng chương trình này:
j:=1;
REPEAT ThửBước j;
IF ThànhCông THEN TiếnTới ELSE QuayLui
UNTIL (j<1) OR (j>n);
Trong ví dụ 8-hậu, có thể xây dựng lời giải bằng cách đặt quân hậu vào các cột liên tiếp bắt đầu từ cột 1 rồi ở từng bước thì đặt quân hậu vào cột tiếp theo. Hiển nhiên là cấu hình một phần mà không thoả điều kiện không đến được nhau thì không thể nào mở rộng bằng phương pháp này để trở thành lời giải hoàn chỉnh. Ngoài ra, vì ở bước thứ $j$ chỉ cần xem xét điều kiện không đến được nhau với $j$ quân hậu nên tìm lời giải một phần ở bước $j$ tốn ít công sức xem xét hơn tìm lời giải hoàn chỉnh mà toàn bộ 8 quân hậu nằm trên bàn cờ ở mọi lúc. Hai tiêu chí đã nêu do đó được thoả mãn bằng cách chia nhỏ sao cho bước $j$ đi tìm vị trí an toàn cho quân hậu ở cột thứ $j$.
Chương trình sắp tới được phát triển trên cơ sở là phương pháp này; nó sinh ra và kiểm tra 876 cấu hình một phần rồi tìm được lời giải hoàn chỉnh. Lại giả định mỗi bước sinh ra và kiểm tra (vốn đã dễ làm hơn lúc nãy) tốn một giây thì tìm thấy lời giải trong 15 phút, còn với máy tính tốn 100 micro-giây cho mỗi bước thì trong 0,09 giây.
Phát triển chương trình
Bây giờ chúng ta phát biểu phép sinh theo từng bước cho ra lời giải một phần cho bài toán 8-hậu bằng phiên bản đầu tiên của chương trình sau:
VAR bảng, conTrỏ, anToàn;
XétCộtĐầu;
REPEAT ThửCột;
IF anToàn THEN
ĐặtHậu; XétCộtKế
ELSE QuayLui END
UNTIL XongCộtCuối OR QuayLuiKhỏiCộtĐầu
Chương trình này gồm một nhóm câu lệnh (hay thủ tục) ban sơ được liệt kê và mô tả hành vi như sau:
XétCộtĐầu. Một phần quan trọng của bài toán là xem xét tính an toàn của ô vuông. Biến conTrỏ chỉ định ô vuông đang xét. Cột chứa ô vuông đang xét gọi là cột đang xét. Thủ tục này khởi tạo conTrỏ để chỉ tới cột đầu tiên.
ThửCột. Bắt đầu từ ô vuông đang xét trong cột đang xét, đi xuống theo cột cho tới khi hoặc tìm thấy ô vuông an toàn thì gán biến Boolean anToàn thành TRUE, hoặc đã tới ô vuông cuối cùng mà vẫn không an toàn thì gán biến anToàn thành FALSE.
ĐặtHậu. Đặt một quân hậu vào ô vuông đang xét gần nhất.
XétCộtKế. Tiến tới cột kế tiếp và khởi tạo conTrỏ xét ô vuông.
QuayLui. Quay lui về cột còn dịch chuyển được quân hậu xuống tiếp, và xoá quân hậu nằm ở cột đã xảy ra quay lui. (Lưu ý là có thể cần quay lui tối đa hai cột. Tại sao?)
Trong các câu lệnh này, sự tinh chế nội dung chi tiết của ThửCột và QuayLui được chọn làm bước phát triển tiếp theo của chương trình như sau.
PROCEDURE ThửCột;
BEGIN
REPEAT TiếnConTrỏ; ThửÔ
UNTIL anToàn OR ÔCuối
END ThửCột;
PROCEDURE QuayLui;
BEGIN XétLạiCộtTrước;
IF ~QuayLuiKhỏiCộtĐầu THEN
XóaHậu;
IF ÔCuối THEN
XétLạiCộtTrước;
IF ~QuayLuiKhỏiCộtĐầu THEN
XóaHậu
END
END
END
END QuayLui;
Chương trình được diễn tả dựa trên các câu lệnh:
XétCộtĐầu
XétCộtKế
XétLạiCộtTrước
TiếnConTrỏ
ThửÔ (gán biến anToàn)
ĐặtHậu
XóaHậu
và các vị từ:
ÔCuối
XongCộtCuối
QuayLuiKhỏiCộtĐầu
Để tinh chế các câu lệnh và vị từ này hơn nữa theo hướng câu lệnh và vị từ có mặt trong ngôn ngữ lập trình thông dụng, cần phải diễn tả chúng dựa trên dữ liệu biểu diễn được ở các ngôn ngữ đó. Do đó không còn trì hoãn lựa chọn làm sao biểu diễn các sự kiện liên quan dựa trên dữ liệu được nữa. Ưu tiên cao nhất của lựa chọn này được gán cho vấn đề là làm sao biểu diễn vị trí của các quân hậu và của ô đang xét.
Cách làm trực quan nhất (theo nghĩa phản ánh gần gũi nhất cái bàn cờ bằng gỗ và quân cờ bằng đá) là giới thiệu ma trận vuông Boolean với B[i,j]=TRUE biểu thị ô $(i,j)$ bị chiếm. Tuy nhiên sự thành công của thuật toán hầu như luôn luôn phụ thuộc vào lựa chọn cách biểu diễn dữ liệu cho phù hợp nhờ vào độ dễ mà cách này cho phép diễn tả các thao tác cần thiết. Bên cạnh đó, có thể cần ưu tiên đòi hỏi về lưu trữ (tuy trường hợp này thì không). Chỗ khó chung khi thiết kế chương trình nằm ở chuyện không may là tại thời điểm cần đưa ra lựa chọn về biểu diễn dữ liệu thì khó mà nhìn trước được các câu lệnh cần thiết sẽ thao tác chi tiết ra sao trên dữ liệu, và thường là gần như không thể ước tính được lợi thế của cách biểu diễn khả dĩ này so với cách kia. Nói chung, nên trì hoãn lựa chọn về cách biểu diễn dữ liệu lâu nhất có thể (mãi tới khi thấy rõ không có lời giải khả thi nào đáp ứng thuật toán đã chọn).
Trong bài toán trình bày ở đây, ở bước này cũng thấy được khá rõ ràng là lựa chọn sau thích hợp hơn ma trận vuông Boolean về độ đơn giản của câu lệnh sau đó cũng như độ tiết kiệm bộ nhớ.
$j$ là chỉ số của cột đang xét; $(x[j],j)$ là toạ độ của ô đang xét gần nhất; và vị trí của quân hậu ở cột $k<j x b c to trong l n khai bi>conTrỏ và bảng được tinh chế thành:</j>
j: INTEGER (* 0<=j<=9 *)
x[1..8]: ARRAY OF INTEGER (* 0<=x[i]<=8 *)
và vài câu lệnh và vị từ ở trên được tiếp tực tinh chế thành ra như sau:
PROCEDURE XétCộtĐầu;
BEGIN j:=1; x[1]:=0
END XétCộtĐầu;
PROCEDURE XétCộtKế;
BEGIN j:=j+1; x[j]:=0
END XétCộtKế;
PROCEDURE XétLạiCộtTrước;
BEGIN j:=j-1
END XétLạiCộtTrước;
PROCEDURE TiếnConTrỏ;
BEGIN x[j]:=x[j]+1;
END TiếnConTrỏ;
PROCEDURE ÔCuối: BOOLEAN;
RETURN x[j]=8;
END ÔCuối;
PROCEDURE XongCộtCuối: BOOLEAN;
RETURN j>8;
END XongCộtCuối;
PROCEDURE QuayLuiKhỏiCộtĐầu: BOOLEAN;
RETURN j<1;
END QuayLuiKhỏiCộtĐầu;
Ở bước này, chương trình được diễn tả dựa trên các câu lệnh:
ThửÔ
ĐặtHậu
XóaHậu
Thực tế là câu lệnh ĐặtHậu và XóaHậu có thể xem là rỗng, nếu chúng ta lựa chọn thủ tục ThửÔ để xác định giá trị của biến anToàn chỉ dựa vào các giá trị $x1$ ... $x{j-1}$ tức là vị trí bấy giờ của $j-1$ quân hậu trên bảng. Nhưng không may ThửÔ là câu lệnh được thực thi thường xuyên nhất, nên để cho ra lời giải tốt thì việc xem xét tính hiệu quả của câu lệnh này không những hợp lý mà còn thiết yếu. Rõ ràng là phiên bản ThửÔ diễn tả chỉ dựa trên $x1$ ... $x{j-1}$ thì kiểu gì cũng kém hiệu quả. Thật hiển nhiên là ThửÔ được thực thi thường xuyên hơn hẳn ĐặtHậu và XóaHậu. Hai thủ tục sau được thực thi mỗi lần cột ($j$) thay đổi (cho là $m$ lần), còn thủ tục đầu tiên được thực thi mỗi lần có sự di chuyển tới ô vuông tiếp theo (tức $xj$ bị đổi; cho là $n$ lần). Tuy nhiên, chỉ có thủ tục ĐặtHậu và XóaHậu ảnh hưởng tới bàn cờ. Tính hiệu quả do đó đạt được bằng phương pháp *giới thiệu biến phụ trợ* $V(x1 ... x_j)$ sao cho:
Tính được ô vuông có an toàn không từ $V(x)$ dễ hơn là tính trực tiếp từ $x$ (cho là trong $u$ đơn vị tính toán thay vì $ku$ đơn vị tính toán).
Sự tính toán $V(x)$ từ $x$ (mỗi khi $x$ thay đổi) là không quá phức tạp (cho là trong $v$ đơn vị tính toán).
Giới thiệu $V$ là có lợi (chưa tính tới mối quan tâm về tính tiết kiệm bộ nhớ), nếu
$n(k-1)u > mv$ hay $\frac{n}{m}(k-1) > \frac{v}{u}$
tức là nếu lượng lợi về đơn vị tính toán lớn hơn lượng mất.
Người dịch ghi chú: Mình từng cảm thấy vướng chỗ này, nhưng quả Wirth là nhà sư phạm giỏi khi ông tạo ra những thử thách nhỏ cho người đọc (ít nhất là cho mình). Trước khi tạo biến phụ thì lượng tính toán là $nku$, vì cột $j$ đổi hay không đổi thì vẫn phải tính lại anToàn, nên lượng tính toán không phụ thuộc $m$. Sau khi tạo biến phụ $V$ thì mỗi lần cột $j$ đổi - vốn có $m$ lần như vậy - phải tính lại $V$ tốn $v$; mỗi lần cần tính anToàn - vốn có $n$ lần như vậy - tốn $u$ thay vì $ku$ như cũ, vậy tổng lượng tính toán là $mv+nu$. Lượng đầu lớn hơn lượng sau thì sự giới thiệu $V$ là có lợi hơn. Hết ghi chú.
Cách làm trực quan nhất thu được phiên bản ThửÔ đơn giản là giới thiệu ma trận Boolean $B$ sao cho B[i,j] = TRUE báo hiệu ô $(i,j)$ không bị quân hậu khác chiếm. Nhưng không may, sự tính toán lại khi quân hậu mới bị xoá đi ($v$) bị cản trở (tại sao?) và do đó lớn hơn lượng lợi nhiều.
Khoảnh khắc bắt đầu nhận ra sự liên quan của điều kiện về tính an toàn của ô vuông là ô vuông không được nằm trên dòng hay đường chéo đã bị quân hậu khác chiếm, là lúc dẫn tới lựa chọn tiết kiệm hơn nhiều cho $V$. Chúng ta giới thiệu ba mảng Boolean $a$, $b$, $c$ với ý nghĩa:
$a_k$ = TRUE : không có quân hậu nào trong dòng $k$
$b_k$ = TRUE : không có quân hậu nào trong đường chéo / $k$
$c_k$ = TRUE : không có quân hậu nào trong đường chèo \ $k$
Phạm vi chỉ số của các mảng này được lựa chọn là vì thực tế là các ô có cùng tổng toạ độ nằm trên cùng đường chéo / và các ô có cùng hiệu toạ độ nằm trên cùng đường chéo . Với các dòng và cột có chỉ số từ 1 tới 8, chúng ta thu được:
a[1..8], b[2..16], c[-7..7]: ARRAY OF BOOLEAN
Với mỗi lần giới thiệu dữ liệu phụ trợ, cần chú ý khởi tạo cho đúng. Vì thuật toán của chúng ta bắt đầu từ bàn cờ trống, phải biểu diễn sự thật này bằng cách khởi tạo giá trị TRUE cho mọi thành phần của các mảng $a$, $b$, $c$. Bây giờ có thể viết:
PROCEDURE ThửÔ;
BEGIN anToàn:=a[x[j]] AND b[j+x[j]] AND c[j-x[j]]
END ThửÔ;
PROCEDURE ĐặtHậu;
BEGIN a[x[j]]:=FALSE; b[j+x[j]]:=FALSE; c[j-x[j]]:=FALSE
END ĐặtHậu;
PROCEDURE XóaHậu;
BEGIN a[x[j]]:=TRUE; b[j+x[j]]:=TRUE; c[j-x[j]]:=TRUE
END XóaHậu;
Tính đúng đắn của thủ tục cuối cùng là do mỗi quân hậu hiện tại trên bàn cờ vốn dĩ đã nằm trên ô vuông an toàn, và do mọi quân hậu mà đặt sau quân hậu cần xoá bỏ thì đã được xoá bỏ từ trước đó. Do đó ô vuông được xoá trống lại trở nên an toàn.
Xem xét phản biện chương trình thu được tiết lộ rằng biến x[j] xuất hiện rất thường xuyên, cụ thể là ở những chỗ được thực thi thường xuyên nhất của chương trình. Hơn nữa, sự xem xét x[j] xảy ra với tần số dày đặc hơn sự gán lại cho j. Hệ quả là, có thể áp dụng nguyên lý giới thiệu dữ liệu phụ trợ lần nữa để tăng tính hiệu quả: biến mới
i: INTEGER
được dùng để biểu diễn giá trị mà nãy giờ biểu thị bằng x[j]. Vì vậy và x[j]:=i phải luôn được thực thi trước khi j tăng lên, và i:=x[j] sau khi j giảm xuống. Bước cuối cùng phát triển chương trình này dẫn tới sự phát biểu lại một số thủ tục bên trên như sau:
PROCEDURE ThửÔ;
BEGIN anToàn:=a[i] AND b[i+j] AND c[i-j]
END ThửÔ;
PROCEDURE ĐặtHậu;
BEGIN a[i]:=FALSE; b[i+j]:=FALSE; c[i-j]:=FALSE;
END ĐặtHậu;
PROCEDURE XóaHậu;
BEGIN a[i]:=TRUE; b[i+j]:=TRUE; c[i-j]:=TRUE;
END XóaHậu;
PROCEDURE XétCộtĐầu;
BEGIN j:=1; i:=0
END XétCộtĐầu;
PROCEDURE TiếnConTrỏ;
BEGIN i:=i+1;
END TiếnConTrỏ;
PROCEDURE XétCộtKế;
BEGIN x[j]:=i; j:=j+1; i:=0
END XétCộtKế;
PROCEDURE ÔCuối: BOOLEAN;
RETURN i=8;
END ÔCuối;
Chương trình cuối cùng sử dụng các thủ tục
ThửÔ
ĐặtHậu
QuayLui
XóaHậu
và đem thay thế trực tiếp các thủ tục còn lại, chương trình giờ đây có dạng
j:=1; i:=0;
REPEAT
REPEAT i:=i+1; ThửÔ
UNTIL anToàn OR (i=8);
IF anToàn THEN
ĐặtHậu; x[j]:=i; j:=j+1; i:=0
ELSE QuayLui END;
UNTIL (j>8) OR (j<1);
IF j>8 THEN InRa(x) ELSE ThấtBại END;
Đáng chú ý là chương trình này vẫn thể hiện cấu trúc của phiên bản đã thiết kế ở bước đầu tiên. Dĩ nhiên là bằng cùng phương pháp tinh chế chương trình từng bước, có thể gợi ra và phát triển nhiều lời giải khác hợp lý như nhau. Một lời giải khác dưới đây được E. W. Dijkstra gợi ý cho tác giả, dựa trên góc nhìn là bài toán này gồm có sự từng bước mở rộng bảng theo từng cột có chứa một quân hậu ở vị trí an toàn, bắt đầu từ bảng trống và kết thúc sau 8 cột. Tiến trình mở rộng bảng được phát biểu thành thủ tục, và cách làm tự nhiên để thu được bảng hoàn chỉnh là gọi đệ quy thủ tục này. Dễ dàng soạn ra thủ tục này từ các câu lệnh nguyên thuỷ dùng trong lời giải đầu tiên.
PROCEDURE ThửCột(j: INTEGER);
VAR i: INTEGER;
BEGIN
i:=0;
REPEAT i:=i+1; ThửÔ;
IF anToàn THEN
ĐặtHậu; x[j]:=i;
IF j<8 THEN ThửCột(j+1) END;
IF ~anToàn THEN XóaHậu END;
END;
UNTIL anToàn OR (i=8);
END ThửCột;
Lúc này chương trình dùng thủ tục này là:
ThửCột(1);
IF anToàn THEN InRa(x) ELSE ThấtBại END;
(Lưu ý rằng vì sự giới thiệu biến i là cục bộ trong thủ tục đệ quy, nên mỗi cột có con trỏ biểu thị i riêng. Hệ quả là các thủ tục
ThửÔ
ĐặtHậu
XóaHậu
cũng phải được khai báo cục bộ bên trong ThửCột, bởi vì chúng tham chiếu tới biến i chỉ định ô đang duyệt qua trong cột hiện tại.)
Bài toán 8-hậu tổng quát
Trong thế giới tính toán thực tiễn, ít khi gặp chương trình mà một khi thực hiện đúng và hài lòng thì giữ mãi không thay đổi nữa. Thường là sớm muộn người dùng nhận ra chương trình của họ không đưa ra mọi kết quả mong muốn, hoặc tệ hơn là, các kết quả được yêu cầu không thực sự cần thiết. Khi đó cần mở rộng hoặc thay đổi chương trình, và chính tình huống này là chỗ mà phương pháp thiết kế chương trình từng bước và cấu trúc hóa có phương pháp là có giá trị và lợi thế nhất. Nếu cấu trúc và các thành phần chương trình được chọn cho tốt, thì thường là nhiều câu lệnh cấu thành có thể làm theo không cần đổi. Nhờ vậy giảm được rất nhiều công sức thiết kế lại và kiểm nghiệm lại. Thực tế thì tính thích ứng của chương trình đối với sự thay đổi mục tiêu (còn gọi là tính dễ bảo trì) và đối với sự thay đổi môi trường (còn gọi là tính dễ di động - portability) được đo đạc chủ yếu bằng mức độ gọn gàng của cấu trúc của chương trình đó.
Mục tiêu của chương tiếp theo là trình diễn lợi thế này khi xét tổng quát hóa bài toán 8-hậu gốc cùng lời giải bằng cách mở rộng các thành phần chương trình đã giới thiệu từ trước.
Bài toán tổng quát được phát biểu như sau:
Tìm mọi cấu hình khả dĩ của 8 quân hậu thù ghét nhau trên bàn cờ vua 8 x 8, sao cho không có quân hậu nào đến được quân hậu khác.
Bài toán mới về bản chất gồm hai phần:
Tìm phương pháp sinh ra thêm lời giải.
Xác định xem mọi lời giải đã được sinh ra hay chưa.
Rõ ràng là cần phải sinh ra và kiểm tra ứng viên cho lời giải theo lối có phương pháp nào đó. Một kỹ thuật thường dùng là tìm cách sắp thứ tự ứng viên và tìm điều kiện nhận diện ứng viên cuối cùng. Nếu tìm thấy một cách sắp thứ tự thì có thể ánh xạ các lời giải vào các số nguyên. Điều kiện giới hạn giá trị số nguyên tương ứng với các lời giải thì trở thành tiêu chí dừng thuật toán, nếu phương pháp được chọn sinh ra lời giải theo thứ tự tăng nghiêm ngặt.
Dễ tìm nhiều cách sắp thứ tự các lời giải cho bài toán hiện tại. Để cho tiện chúng ta chọn ánh xạ
$M(x) = \sum{j=1}^8{xj 10^{j-1}}$
Cận trên của các lời giải khả dĩ là
$M(x_{max}) = 88888888$
và sự "tiện lợi" nằm ở chỗ chương trình ở phần trước sinh ra lời giải nhỏ nhất nên có thể xem đây là điểm bắt đầu để tiếp tục lời giải kế tiếp. Đây là nhờ cách thử ô vuông đã chọn là tiếp tục một cách nghiêm ngặt theo thứ tự tăng dần của $M(x)$ bắt đầu từ 00000000. Bây giờ cần phải chọn cách thức sinh ra lời giải tiếp theo bắt đầu từ cấu hình lời giải đang có, tiếp tục theo cùng thứ tự tăng dần của $M$, cho tới khi tìm thấy lời giải cao hơn hoặc đạt tới giới hạn.
Chương trình mở rộng
Kỹ thuật mở rộng hai chương trình đã cho - vốn tìm một nghiệm của bài toán 8-hậu đơn giản - căn cứ ý tưởng là chỉ điều chỉnh cấu trúc toàn cục và là dùng lại các khối xây dựng đã có. Cấu trúc toàn cục cần điều chỉnh sao cho một khi tìm thấy lời giải thì thuật toán sinh ra biểu thị tương ứng - chẳng hạn như in ra lời giải - rồi tiếp tục tìm lời giải kế tiếp cho tới khi tìm thấy hoặc đạt tới giới hạn. Điều kiện đơn giản cho sự đạt tới giới hạn là sự kiện quân hậu đầu tiên di chuyển vượt qua dòng 8, lúc này xảy ra sự quay lui khỏi cột đầu tiên. Các ý cân nhắc này dẫn tới phiên bản chỉnh sửa này của chương trình không đệ quy:
XétCộtĐầu;
REPEAT ThửCột;
IF anToàn THEN
ĐặtHậu; XétCộtKế;
IF XongCộtCuối THEN
InRa(x); QuayLui
END
ELSE QuayLui END
UNTIL QuayLuiKhỏiCộtĐầu;
Biểu hiện tìm thấy lời giải bằng cách lập tức in ra xảy ra trực tiếp ở thời điểm nhận diện, tức là trước khi rời khỏi lệnh lặp REPEAT. Rồi thuật toán tiếp tục tìm lời giải kế tiếp, nhờ đó dùng đường tắt bằng cách là trực tiếp quay lui về cột trước đó; vì mỗi dòng của lời giải có một quân hậu, nên một khi đã tìm thấy lời giải thì tiếp tục tiến quân hậu cuối cùng trong cột thứ tám không có ích gì.
Chương trình đệ quy còn mở rộng dễ dàng hơn theo cùng ý tưởng cân nhắc:
PROCEDURE ThửCột (j: INTEGER);
VAR i: INTEGER;
(* Khai báo ThửÔ, TiếnHậu, ĐặtHậu, XóaHậu, ÔCuối *)
BEGIN
i:=0;
REPEAT TiếnHậu; ThửÔ;
IF anToàn THEN
ĐặtHậu; x[j]:=i;
IF ~XongCộtCuối THEN ThửCột(j+1) ELSE InRa(x) END;
XóaHậu
END;
UNTIL ÔCuối
END ThửCột;
Chương trình chính bắt đầu thuật toán gồm một câu lệnh ThửCột(1) (bên cạnh bước khởi tạo $a$, $b$, $c$).
Cuối cùng thì, cần chú ý là hai chương trình biểu diễn cùng một thuật toán. Cả hai đều xác định 92 lời giải theo cùng thứ tự bằng cách thử ô vuông 15720 lần. Tính ra trung bình là 171 lần thử cho mỗi lời giải; tối đa là 876 lần thử để tìm thấy lời giải kế tiếp (là lời giải đầu tiên), tối thiểu là 8 lần. (Cả hai chương trình được viết mã nguồn bằng ngôn ngữ Pascal và được thực thi bằng máy tính CDC 6400 trong vòng dưới một giây.)
Kết luận
Các bài học mà ví dụ đã mô tả có nhiệm vụ minh họa được tóm tắt thành các điểm sau đây.
Sự xây dựng chương trình gồm dãy nhiều bước tinh chế. Ở mỗi bước một nhiệm vụ được chia nhỏ thành một số nhiệm vụ phụ. Mỗi sự tinh chế nội dung mô tả nhiệm vụ có thể phải đi cùng với sự tinh chế nội dung mô tả của dữ liệu cấu thành phương tiện liên lạc các nhiệm vụ phụ với nhau. Cần phải tinh chế nội dung mô tả của chương trình và của cấu trúc dữ liệu một cách đồng thời.
Mức độ của tính mô-đun có được từ cách làm này sẽ xác định độ dễ hay khó để một chương trình thích ứng với sự thay đổi và mở rộng về mục đích hay sự thay đổi về môi trường (ngôn ngữ, máy tính) thực thi.
Suốt tiến trình tinh chế từng bước, cần dùng ký pháp có tính tự nhiên đối với vấn đề trong tay nhiều hết mức có thể. Hướng đi mà các ký pháp này phát triển trong tiến trình tinh chế được xác định bằng ngôn ngữ mà chương trình cuối cùng phải đặc tả, tức là ký pháp ở bước cuối cùng phải đạt tới. Ngôn ngữ này do đó cần phải cho phép chúng ta diễn tả một cách tự nhiên và rõ ràng nhất có thể cấu trúc chương trình và dữ liệu xuất hiện suốt tiến trình thiết kế. Đồng thời, ngôn ngữ này phải đưa ra hướng dẫn cho tiến trình tinh chế bằng cách trưng bày các tính năng cơ bản và nguyên lý cấu trúc có tính tự nhiên với máy tính thực thi chương trình được tạo ra. Đáng nói là khó mà tìm thấy ngôn ngữ thỏa các yêu cầu quan trọng này ở mức độ thấp hơn một ngôn ngữ mà thời điểm này (1971) vẫn được dùng rộng rãi để dạy lập trình: Fortran.
Người dịch ghi chú: Hơn năm mươi năm sau (2025), tính thời sự của câu nói vẫn còn đối với ngôn ngữ dạy lập trình ngày nay như C++ hay Javascript hay Python. So với Fortran có tiến bộ hơn, nhưng mình thấy chưa tiến xa lắm. Ngữ pháp cồng kềnh và cú pháp không tự nhiên của C++ là rất tồi đối với yêu cầu đầu tiên, và không mấy tốt ở yêu cầu thứ hai nếu dùng tính năng 'cao cấp'; Javascript và Python thì không mấy tốt ở cả hai, vừa không tự nhiên để mô tả dữ liệu do kiểu động, vừa không tự nhiên với máy tính mà cần biên hay phiên dịch lại. Ngày nay người dạy lập trình nhằm tăng tính hấp dẫn của khóa học có xu hướng vụ lấy ngôn ngữ có nhiều tiện ích phụ trợ giúp làm ra sản phẩm dễ dàng và nhanh chóng - vốn không phải là tinh hoa của kiến thức lập trình cần được dạy. Đây cũng là lý do người dịch chọn Oberon để mô tả chương trình vì chúng thỏa mãn cả hai yêu cầu có tính sư phạm ở trên. Hết ghi chú.
Mỗi bước tinh chế kéo theo một số lựa chọn về thiết kế dựa trên một nhóm tiêu chuẩn thiết kế. Trong các tiêu chuẩn này có thể kể tính hiệu quả, tính tiết kiệm lưu trữ, tính rõ ràng, và tính ít ngoại lệ (tính thường quy - regularity) của cấu trúc. Học sinh cần được dạy để có ý thức về các lựa chọn rối rắm, để xem xét phản biện, và để bác bỏ lời giải, thậm chí vào đôi lúc mà lời giải vẫn đúng nếu chỉ nhìn kết quả; họ phải học để cân nhắc nhiều khía cạnh của các thiết kế thay thế dựa trên các tiêu chuẩn này. Cụ thể là họ phải được dạy là cần phải rút lại lựa chọn trước đó và lùi về, thậm chí về lại từ đầu nếu cần thiết. Thường vài bài toán tương đối ngắn là đủ minh họa điều quan trọng này; không cần thiết phải xây dựng một hệ điều hành cho mục đích này.
Sự diễn giải chi tiết quá trình phát triển của một chương trình dù là ngắn cũng tạo thành câu chuyện dài, chứng tỏ rằng lập trình cẩn thận không phải chủ đề tầm thường. Nếu bài luận này đã giúp phá vỡ niềm tin đang thịnh hành là lập trình dễ lắm miễn sao có ngôn ngữ lập trình đủ mạnh và máy tính đủ nhanh, thì nó đã đạt được một trong các mục đích.
Ghi nhận
Tác giả ghi nhận một cách biết ơn ảnh hưởng hữu ích và thú vị từ nhiều cuộc thảo luận với C. A. R. Hoare và E. W. Dijkstra.
Tham khảo
Các bài luận sau đây được liệt kê nhằm tham khảo xa hơn về chủ đề lập trình. Người dịch do đó giữ nguyên tên và cấu trúc trình bày tên bài luận, nhằm giữ nguyên giá trị tra cứu.
Dijkstra, E. W. A constructive approach to the problem of program correctness. BIT 8 (1968), 174-186.
Dijkstra, E. W. Notes on structured programming. EWD 249, Technical U. Eindhoven, The Netherlands, 1969.
Naur, P. Programming by action clusters. BIT 9 (1969) 250-258.
Wirth, N. Programming and programming languages. Proc. Internat. Comput. Symp., Bonn, Germany, May 1970.