Computer Science

CLC number: TP311

Nonlinear Program Construction and Verification Method Based on Partition Recursion and Morgan's Refinement Rules

¹ College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, Jiangxi, China
² College of Digital Industry Academy, Jiangxi Normal University, Shangrao 334000, Jiangxi, China

^† To whom correspondence should be addressed. E-mail: zhengkang2005@iscas.ac.cn

Received: 21 May 2022

Abstract

The traditional program refinement strategy cannot be refined to an executable program, and there are issues such as low verification reliability and automation. To solve the above problems, this paper proposes a nonlinear program construction and verification method based on partition recursion and Morgan's refinement rules. First, we use recursive definition technique to characterize the initial specification. The specification is then transformed into GCL(Guarded Command Language) programs using loop invariant derivation and Morgan's refinement rules. Furthermore, VCG (Verification Condition Generator) is used in the GCL program to generate the verification condition automatically. The Isabelle theorem prover then validates the GCL program's correctness. Finally, the GCL code generates a C++ executable program automatically via the conversion system. The effectiveness of this method is demonstrated using binary tree preorder traversal program construction and verification as an example. This method addresses the problem that the construction process's loop invariant is difficult to obtain and the refinement process is insufficiently detailed. At the same time, the method improves verification process automation and reduces the manual verification workload.