Program Development by Stepwise Refinement

Program Development by Stepwise Refinement

April 1971 | Niklaus Wirth
The creative activity of programming, distinct from coding, is usually taught through examples that demonstrate techniques. This paper considers programming as a sequence of design decisions involving task decomposition and data structuring. It illustrates the process of successive refinement of specifications using a nontrivial example, leading to conclusions about programming and its instruction. The paper focuses on the 8-Queens problem, where the goal is to place eight queens on a chessboard so that none attack each other. The solution involves stepwise refinement, where each step decomposes instructions into more detailed ones. This process continues until all instructions are expressed in terms of a programming language. The example demonstrates the importance of design decisions and the need for explicit criteria in programming. The paper also discusses the use of auxiliary data and recursion in program development. The 8-Queens problem is solved through a stepwise construction of trial solutions, with backtracking used to revise previous steps when necessary. The program is refined through a series of steps, leading to an efficient solution. The paper emphasizes the importance of structured programming and the need for clear, well-structured code. It also discusses the generalization of the 8-Queens problem and the extension of the program to find all possible solutions. The paper concludes that programming is a complex activity requiring careful design and refinement, and that structured programming is essential for effective program development. The paper also highlights the importance of teaching programming as a design process rather than just as a language mastery task.The creative activity of programming, distinct from coding, is usually taught through examples that demonstrate techniques. This paper considers programming as a sequence of design decisions involving task decomposition and data structuring. It illustrates the process of successive refinement of specifications using a nontrivial example, leading to conclusions about programming and its instruction. The paper focuses on the 8-Queens problem, where the goal is to place eight queens on a chessboard so that none attack each other. The solution involves stepwise refinement, where each step decomposes instructions into more detailed ones. This process continues until all instructions are expressed in terms of a programming language. The example demonstrates the importance of design decisions and the need for explicit criteria in programming. The paper also discusses the use of auxiliary data and recursion in program development. The 8-Queens problem is solved through a stepwise construction of trial solutions, with backtracking used to revise previous steps when necessary. The program is refined through a series of steps, leading to an efficient solution. The paper emphasizes the importance of structured programming and the need for clear, well-structured code. It also discusses the generalization of the 8-Queens problem and the extension of the program to find all possible solutions. The paper concludes that programming is a complex activity requiring careful design and refinement, and that structured programming is essential for effective program development. The paper also highlights the importance of teaching programming as a design process rather than just as a language mastery task.
Reach us at info@study.space
[slides] Program development by stepwise refinement | StudySpace