Mục lục bài họcĐang ở d04-b4
Sub-programs, Pre- and Post-conditions, Testing and Debugging
Sub-programs and their contracts. A sub-program (procedure or function) packages a task behind a name and a list of parameters. It is worth writing when the same steps are needed in more than one place, when a long program becomes readable only if split into named parts, or when a part can be tested on its own. Each sub-program has a contract: a pre-condition, what must be true before it is called (the array is sorted; N is positive), and a post-condition, what is guaranteed afterwards (returns the index of the item or −1). Binary search's pre-condition is the reason it fails silently on unsorted data: the contract was broken by the caller, not by the algorithm. Stating contracts is how large programs are built by many people without each reading the others' code.
Parameters and scope. A parameter passed by value gives the sub-program a copy, so changes inside do not affect the caller; passed by reference, the sub-program works on the original, which is how a sort routine modifies the caller's array. A local variable exists only inside the sub-program; a global one is visible everywhere, which is convenient and dangerous, because any sub-program can change it and the reason for a wrong value becomes impossible to trace. Prefer parameters and return values; use globals only for true constants.
Choosing test data. Testing shows the presence of errors, never their absence, so data must be chosen to make errors hard to hide. Three categories: normal data inside the expected range (a mark of 50); boundary data on and beside each limit (0, 1, 99, 100), where off-by-one errors live; and erroneous data outside the range or of the wrong type (−1, 101, 50.5, text, empty), which the program must reject without crashing. Add the empty case and the single-item case for every loop and every array. For each test, write the expected output before running, or the test proves nothing.
Finding the bug. When output is wrong: shrink the input to the smallest case that still fails (N = 3, not N = 1 000); trace by hand with one column per variable and one row per step; compare the actual column with the expected column, and the first row where they diverge is where the bug is; fix it; then rerun every earlier test, because a fix that breaks something else is common. Typical bugs to recognise on sight: a loop bound one too high or too low; a variable initialised in the wrong place; using the wrong comparison (less than versus less than or equal); integer division where real division was meant; updating a maximum without its position; and reading a variable before it has been assigned.
Chương trình con và hợp đồng của nó. Chương trình con (thủ tục hoặc hàm) gói một nhiệm vụ sau một cái tên và một danh sách tham số. Đáng viết khi cùng các bước được cần ở nhiều chỗ, khi chương trình dài chỉ đọc được nếu chia thành các phần có tên, hoặc khi một phần có thể được kiểm thử riêng. Mỗi chương trình con có một hợp đồng: tiền điều kiện, điều phải đúng trước khi gọi (mảng đã sắp xếp; N dương), và hậu điều kiện, điều được bảo đảm sau đó (trả về chỉ số của phần tử hoặc −1). Tiền điều kiện của tìm kiếm nhị phân là lý do nó thất bại âm thầm trên dữ liệu chưa sắp: hợp đồng bị bên gọi vi phạm, không phải thuật toán sai. Nêu hợp đồng là cách chương trình lớn được nhiều người xây mà không ai phải đọc mã của người khác.
Tham số và phạm vi. Tham số truyền theo giá trị cho chương trình con một bản sao, nên thay đổi bên trong không ảnh hưởng bên gọi; truyền theo tham chiếu, chương trình con làm việc trên bản gốc, và đó là cách thủ tục sắp xếp sửa mảng của bên gọi. Biến cục bộ chỉ tồn tại trong chương trình con; biến toàn cục nhìn thấy ở mọi nơi, tiện và nguy hiểm, vì bất kỳ chương trình con nào cũng đổi được nó và lý do của một giá trị sai trở nên không thể truy. Ưu tiên tham số và giá trị trả về; chỉ dùng toàn cục cho hằng thật sự.
Chọn dữ liệu kiểm thử. Kiểm thử cho thấy có lỗi, không bao giờ cho thấy không có lỗi, nên dữ liệu phải được chọn để lỗi khó trốn. Ba loại: dữ liệu bình thường trong khoảng mong đợi (điểm 50); dữ liệu biên trên và sát mỗi giới hạn (0, 1, 99, 100), nơi lỗi thiếu một cư trú; và dữ liệu sai ngoài khoảng hoặc sai kiểu (−1, 101, 50,5, chữ, rỗng), mà chương trình phải từ chối không sập. Thêm ca rỗng và ca một phần tử cho mọi vòng lặp và mọi mảng. Với mỗi ca, viết đầu ra mong đợi trước khi chạy, nếu không ca kiểm thử không chứng minh gì.
Tìm lỗi. Khi đầu ra sai: thu nhỏ đầu vào tới ca nhỏ nhất vẫn sai (N = 3, không phải N = 1 000); lần vết bằng tay với một cột mỗi biến và một dòng mỗi bước; so cột thực tế với cột mong đợi, dòng đầu tiên lệch là nơi có lỗi; sửa; rồi chạy lại mọi ca trước đó, vì sửa chỗ này hỏng chỗ khác là chuyện thường. Các lỗi điển hình cần nhận ra ngay: biên vòng lặp thừa hoặc thiếu một; biến khởi tạo sai chỗ; dùng sai phép so sánh (nhỏ hơn với nhỏ hơn hoặc bằng); chia nguyên khi cần chia thực; cập nhật giá trị lớn nhất mà không cập nhật vị trí; và đọc một biến trước khi nó được gán.
Thuật toán sau tính trung bình của mảng A có N phần tử nhưng cho kết quả sai: SUM = 0; loop I from 1 to N; SUM = SUM + A[I]; end loop; AVG = SUM div N; output AVG. Với A = [10, 20, 30], N = 3, kết quả mong đợi là 20. Hãy tìm lỗi bằng lần vết và sửa.
Bước 1 — ca nhỏ nhất. N = 3 đã đủ nhỏ. Mong đợi: SUM = 60, AVG = 20.
Bước 2 — lần vết. Chỉ số mảng từ 0 nên A[0] = 10, A[1] = 20, A[2] = 30, và A[3] không tồn tại. I = 1: SUM = 0 + A[1] = 20. I = 2: SUM = 20 + A[2] = 50. I = 3: SUM = 50 + A[3] — vượt biên mảng; tuỳ ngôn ngữ, chương trình sập hoặc cộng một giá trị rác. Dòng đầu tiên lệch với mong đợi là ngay I = 1: mong đợi SUM = 10 (A[0]) nhưng thực tế 20. Lỗi ở biên vòng lặp: phải chạy từ 0 tới N − 1.
Bước 3 — lỗi thứ hai ẩn sau lỗi thứ nhất. Sau khi sửa vòng lặp, SUM = 60 và AVG = 60 div 3 = 20 — đúng với ca này. Nhưng thử A = [10, 20, 25]: SUM = 55, 55 div 3 = 18 thay vì 18,33. Phép div là chia nguyên; trung bình cần chia thực. Ca kiểm thử đầu tiên tình cờ chia hết nên giấu lỗi này — minh hoạ vì sao một ca đúng không chứng minh chương trình đúng.
Bước 4 — ca biên còn lại. N = 0: chia cho 0. Thuật toán cần tiền điều kiện N lớn hơn 0, hoặc một nhánh kiểm và báo lỗi. N = 1: SUM = A[0], AVG = A[0], đúng.
Bản sửa. if N = 0 then output "empty" else SUM = 0; loop I from 0 to N − 1; SUM = SUM + A[I]; end loop; AVG = SUM / N; output AVG; end if. Chạy lại cả ba ca: [10, 20, 30] → 20; [10, 20, 25] → 18,33; [] → "empty".
Một chương trình quản lý thư viện cần: (a) hàm tìm vị trí của một mã sách trong mảng mã đã sắp xếp; (b) thủ tục sắp xếp mảng mã; (c) hàm tính phí trễ hạn từ số ngày. Với mỗi cái, viết tiền và hậu điều kiện, chọn truyền theo giá trị hay tham chiếu, và nêu vì sao không dùng biến toàn cục.
(a) FIND(CODES, N, TARGET) trả về số nguyên. Tiền điều kiện: CODES đã sắp tăng, N là số phần tử thật, N ≥ 0. Hậu điều kiện: trả về chỉ số I với CODES[I] = TARGET nếu tồn tại, ngược lại −1; mảng không bị thay đổi. Vì hàm chỉ đọc, truyền CODES theo tham chiếu là chấp nhận được để tránh sao chép mảng lớn, nhưng phải ghi trong hậu điều kiện rằng nó không sửa. Tiền điều kiện đã sắp là điều cho phép dùng tìm kiếm nhị phân; nếu bên gọi vi phạm, kết quả sai mà không có thông báo — nên bên gọi chịu trách nhiệm.
(b) SORT(CODES, N) thủ tục. Tiền điều kiện: N ≥ 0. Hậu điều kiện: CODES chứa cùng các phần tử như trước, theo thứ tự tăng. Phải truyền theo tham chiếu, vì mục đích là sửa mảng của bên gọi; truyền theo giá trị sẽ sắp một bản sao rồi vứt đi — lỗi kinh điển khiến chương trình có vẻ chạy mà mảng không đổi. Hậu điều kiện cùng các phần tử quan trọng: một thủ tục sắp xếp làm mất hoặc nhân đôi phần tử vẫn cho mảng tăng dần.
(c) FINE(DAYS) trả về số thực. Tiền điều kiện: DAYS là số nguyên ≥ 0. Hậu điều kiện: trả về 0 nếu DAYS ≤ GRACE, ngược lại (DAYS − GRACE) × RATE, không vượt MAXFINE. Truyền theo giá trị vì chỉ cần con số. GRACE, RATE, MAXFINE là hằng toàn cục — trường hợp duy nhất toàn cục hợp lý.
Vì sao không dùng biến toàn cục cho dữ liệu. Nếu CODES là toàn cục và cả FIND lẫn SORT đều chạm vào nó, một giá trị sai có thể do bất kỳ chương trình con nào gây ra và không truy được; các hàm cũng không kiểm thử riêng được vì phụ thuộc trạng thái bên ngoài. Tham số và giá trị trả về làm luồng dữ liệu nhìn thấy được ở chỗ gọi.
Bẫy 2 — truyền mảng theo giá trị cho thủ tục sắp xếp. Bản sao được sắp rồi vứt; mảng gốc không đổi mà không có báo lỗi.
Bẫy 3 — đổ lỗi cho thuật toán khi tiền điều kiện bị vi phạm. Tìm kiếm nhị phân trên mảng chưa sắp là lỗi của bên gọi.
Đọc xong rồi — làm thử ngay
Bài tập của chương Computational Thinking, Problem-Solving and Programming gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.