Article(id=1329419719511224943, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329419577676641015, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202550899, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1765728000000, receivedDateStr=2025-12-15, revisedDate=1772640000000, revisedDateStr=2026-03-05, acceptedDate=null, acceptedDateStr=null, onlineDate=1794887960554, onlineDateStr=2026-11-17, pubDate=1777564800000, pubDateStr=2026-05-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794887960554, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794887960554, creator=13701087609, updateTime=1794887960554, updator=13701087609, issue=Issue{id=1329419577676641015, tenantId=1146029695717560320, journalId=1324759914146529478, year='2026', volume='63', issue='5', pageStart='1095', pageEnd='1375', issueExtLink='null', onlineDate='null', pubDate='1777564800000', pubDateStr='2026-05-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794887926739, creator='13701087609', updateTime=1794887926739, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=1117, endPage=1138, ext={EN=ArticleExt(id=1329419719725134448, articleId=1329419719511224943, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms, columnId=1329419682488103033, journalTitle=Journal of Computer Research and Development, columnName=Special Issue on Security and Trustworthiness for AI-Enabled Human-Cyber-Physical Systems, runingTitle=null, highlight=null, articleAbstract=

Search tree algorithms are widely used in areas such as database indexing, compiler design, and file systems, where the functional correctness of these algorithms is a critical factor in ensuring software reliability. However, traditional development process faces two major challenges: first, algorithm design often lacks rigorous mathematical modeling, causing correctness verification to remain at an empirical level; second, existing verification approaches heavily rely on manual or interactive theorem proving, making the verification complexity grow exponentially with increasing algorithm scale. To address the above issues, an Isabelle-driven method for modeling and automated verification of search tree algorithms is proposed. This method builds on a formally verified functional modeling library to construct a modular modeling strategy that supports various search tree structures, and introduces a formal specification-driven framework for automatically synthesizing algorithmic code. Developers are required to supply only minimal functional expressions to complete the implementation. In addition, a reusable lemma library has been developed to support an automated block-wise verification strategy, significantly reducing verification costs. Furthermore, a method for generating functional executable programs is proposed. Experimental evaluation using a representative case study demonstrates that the proposed method substantially reduces verification costs. Compared with interactive verification approaches, the average reductions in code size and manual effort are 88.60% and 61.51%, respectively; compared with generative AI plus interactive verification methods, the average reductions in code size and manual effort are 88.09% and 41.76%, respectively. Overall, the proposed framework provides a systematic and highly automated solution for the formal verification of complex data structure algorithms in specific domains, while also offering a feasible pathway and methodological support for generating correct functional executable programs.

, authors=Zhengkang Zuo1, 2, 3, Xiaoying Zhu1, Zhen You1, Changjing Wang1, 2, 3, *, authorsList=Zhengkang Zuo, Xiaoying Zhu, Zhen You, Changjing Wang, authorCompany=null, correspAuthors=Changjing Wang, authorNote=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, correspAuthorsNote=null, copyrightStatement=Copyright © 2026 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329419724653441708, articleId=1329419719511224943, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=Isabelle驱动的搜索树类算法建模及自动化验证, columnId=1329419682655875195, journalTitle=计算机研究与发展, columnName=面向人机物融合智能系统的安全可信专题, runingTitle=null, highlight=null, articleAbstract=

搜索树类算法广泛应用于数据库索引、编译器设计、文件系统等领域,其功能正确性验证是保障软件可靠性的关键环节。然而,传统开发流程存在2个主要问题:首先,算法设计常缺乏严格的数学建模,导致正确性验证停留于经验层面;其次,现有验证方法多依赖手工证明或交互式定理证明工具,随着算法规模的扩大,验证复杂度呈指数级增长。为解决上述问题,提出了Isabelle驱动的搜索树类算法建模及自动化验证方法。该方法基于经过形式化验证的函数式建模库,构建了涵盖搜索树类结构的模块化建模策略,并设计了形式化规约自动合成算法代码框架。开发者仅需补充少量函数表达式,即可实现完整的算法。此外,开发了可复用的验证引理库,并通过自动化分块验证策略有效降低了验证成本。进一步地,提出了函数式可执行程序生成方法。通过典型案例实验验证,结果表明所提方法显著降低了验证成本。与交互式验证方法相比,代码行数和人工占比分别平均减少了88.60%、61.51%;与“生成式AI+交互式验证方法”相比,代码行数和人工占比分别平均减少了88.09%、41.76%。该框架为特定领域复杂数据结构算法的形式化验证提供了系统性且高度自动化的解决方案,同时为生成正确的函数式可执行程序提供了可行路径与方法保障。

, authors=左正康1, 2, 3, 朱小影1, 游珍1, 王昌晶1, 2, 3, *, authorsList=左正康, 朱小影, 游珍, 王昌晶, authorCompany=null, correspAuthors=王昌晶, authorNote=

作者贡献声明

左正康和朱小影共同提出方法思路和实验方案;朱小影完成实验并撰写论文;游珍和王昌晶提出指导意见并修改论文。

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, correspAuthorsNote=
王昌晶()
, copyrightStatement=版权所有 © 2026 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=2x+0WB18XTUE1rkCGp9tEg==, magXml=0M2H7rUorVfTPm04XqSTSw==, pdfUrl=null, pdf=n7z3Oyp8fIulCr3ESvd7pw==, pdfFileSize=9075874, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=xA17s18QHnZq2UwHaQRnyA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=jm2nBhX3qUqwObrttoLSCg==, mapNumber=null, fund=null)}, authors=[Author(id=1329419725169341111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zuo803@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725257421499, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725169341111, language=EN, stringName=Zhengkang Zuo, firstName=Zhengkang, middleName=null, lastName=Zuo, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725324530364, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725169341111, language=CN, stringName=左正康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"rL2tWBuciDKrtMqL2ejzBQ==","content":"

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

"}, bioImg=rL2tWBuciDKrtMqL2ejzBQ==, bioContent=

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419724984791728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=2, ext=[AuthorCompanyExt(id=1329419724988986033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419724997374642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419725077066419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=3, ext=[AuthorCompanyExt(id=1329419725089649332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419725098037941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])]), Author(id=1329419725383250622, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725450359488, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725383250622, language=EN, stringName=Xiaoying Zhu, firstName=Xiaoying, middleName=null, lastName=Zhu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

"}, bioImg=null, bioContent=

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725513274049, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725383250622, language=CN, stringName=朱小影, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"lZHsNxsnrDYSyB3ZXumHzw==","content":"

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=lZHsNxsnrDYSyB3ZXumHzw==, bioContent=

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419725571994307, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725639103173, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725571994307, language=EN, stringName=Zhen You, firstName=Zhen, middleName=null, lastName=You, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725702017734, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725571994307, language=CN, stringName=游珍, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"qsQFSPt9NXR0hQmt+2B0dA==","content":"

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

"}, bioImg=qsQFSPt9NXR0hQmt+2B0dA==, bioContent=

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419725781709512, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wcj@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329419725882372812, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725781709512, language=EN, stringName=Changjing Wang, firstName=Changjing, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022, bio={"content":"

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

"}, bioImg=null, bioContent=

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725945287373, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725781709512, language=CN, stringName=王昌晶, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"BInriQKiXVcqYhXUOwq0Ig==","content":"

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

"}, bioImg=BInriQKiXVcqYhXUOwq0Ig==, bioContent=

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419724984791728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=2, ext=[AuthorCompanyExt(id=1329419724988986033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419724997374642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419725077066419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=3, ext=[AuthorCompanyExt(id=1329419725089649332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419725098037941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])])], keywords=[Keyword(id=1329419726029173454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, orderNo=1, keyword=search tree), Keyword(id=1329419726087893711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, orderNo=2, keyword=Isabelle theorem prover), Keyword(id=1329419726142419664, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, orderNo=3, keyword=functional modeling), Keyword(id=1329419726201139921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, orderNo=4, keyword=automated verification), Keyword(id=1329419726276637394, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, orderNo=5, keyword=program generation), Keyword(id=1329419726339551955, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, orderNo=1, keyword=搜索树), Keyword(id=1329419726452798164, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, orderNo=2, keyword=Isabelle定理证明器), Keyword(id=1329419726515712725, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, orderNo=3, keyword=函数式建模), Keyword(id=1329419726595404502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, orderNo=4, keyword=自动化验证), Keyword(id=1329419726658319063, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, orderNo=5, keyword=程序生成)], refs=[Reference(id=1329419731037172495, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=石海鹤, 蓝孙文, 刘日明, 等. 生物序列比对动态规划算法的统一形式化构造与Isabelle验证[J]. 计算机研究与发展, 2025, 62(1): 119−131, articleTitle=null, refAbstract=null), Reference(id=1329419731108475664, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haihe, Lan Sunwen, Liu Riming, et al. Unified formal construction and Isabelle verification of the dynamic programming algorithms for biological sequence alignment[J]. Journal of Computer Research and Development, 2025, 62(1): 119−131(in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419731183973137, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Vazou N, Seidel E L, Jhala R. LiquidHaskell: Experience with refinement types in the real world [C]//Proc of the 2014 ACM SIGPLAN Symp on Haskell. New York: ACM, 2014: 39−51, articleTitle=null, refAbstract=null), Reference(id=1329419731263664914, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Xu D N. Extended static checking for Haskell[C]//Proc of the 2006 ACM SIGPLAN Workshop on Haskell. New York: ACM, 2006: 48−59, articleTitle=null, refAbstract=null), Reference(id=1329419731485963027, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Hutton G. Programming in Haskell[M]. Cambridge, UK: Cambridge University Press, 2016, articleTitle=null, refAbstract=null), Reference(id=1329419731557266196, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Dageförde J C, Teegen F. Structured traversal of search trees in constraint-logic object-oriented programming[C]//Proc of Int Conf on Applications of Declarative Programming and Knowledge Management. Cham: Springer, 2019: 199−214, articleTitle=null, refAbstract=null), Reference(id=1329419731632763669, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Huet G, Kahn G, Paulin-Mohring C. The Coq proof assistant a tutorial[R/OL]. Rapport Technique, 1997, 178. [2025-11-02]. https://www.cs.cmu.edu/~emc/15414-s14/lecture/Tutorial.pdf, articleTitle=null, refAbstract=null), Reference(id=1329419731691483926, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Klein G. Concrete Semantics: with Isabelle/HOL[M]. Berlin: Springer, 2021, articleTitle=null, refAbstract=null), Reference(id=1329419731754398487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Paulson L C, Wenzel M. Isabelle/HOL: A Proof Assistant for Higher-Order Logic[M/OL]. Springer Science & Business Media, 2021[2025-12-10]. https://isabelle.in.tum.de/website-Isabelle2021/dist/Isabelle2021/doc/tutorial.pdf, articleTitle=null, refAbstract=null), Reference(id=1329419731817313048, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=左正康, 黄志鹏, 黄箐, 等. LLRB算法的函数式建模及其机械化验证[J]. 软件学报, 2024, 35(11): 5016−5039, articleTitle=null, refAbstract=null), Reference(id=1329419731917976345, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Zuo Zhengkang, Huang Zhipeng, Huang Qing, et al. Functional modeling and mechanized verification of LLRB algorithm[J]. Journal of Software, 2024, 35(11): 5016−5039 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419731980890906, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=左正康, 刘增鑫, 柯雨含, 等. 动态顺序统计树类结构的函数式建模及其自动化验证[J]. 软件学报, 2025, 36(8): 3531−3553, articleTitle=null, refAbstract=null), Reference(id=1329419732056388379, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Zuo Zhengkang, Liu Zengxin, Ke Yuhan, et al. Functional modeling and automatic verification of dynamic order statistic tree structures[J]. Journal of Software, 2025, 36(8): 3531−3553 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419732123497244, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T. Automatic functional correctness proofs for functional search trees[C]//Proc of the 7th Int Conf on Interactive Theorem Proving. Cham: Springer, 2016: 307−322, articleTitle=null, refAbstract=null), Reference(id=1329419732224160541, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Guo Daya, Yang Dejian, Zhang Haowei, et al. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning[J]. arXiv preprint arXiv: 2501.12948, 2025, articleTitle=null, refAbstract=null), Reference(id=1329419732287075102, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Dubey A, Jauhri A, Pandey A, et al. The Llama 3 herd of models[J]. arXiv preprints arXiv: 2407.21783, 2024, articleTitle=null, refAbstract=null), Reference(id=1329419732375155487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang An, Li Anfeng, Yang Baosong, et al. Qwen3 technical report[J]. arXiv preprint arXiv: 2505.09388, 2025, articleTitle=null, refAbstract=null), Reference(id=1329419732496790304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Dong Kefen, Ma Tengyu. Stp: Self-play LLM theorem provers with iterative conjecturing and proving[J]. arXiv preprint arXiv: 2502.00212, 2025, articleTitle=null, refAbstract=null), Reference(id=1329419732559704865, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Ziyin, Xu Jiahao, He Zhiwei, et al. DeepTheorem: Advancing LLM reasoning for theorem proving through natural language and reinforcement learning[J]. arXiv preprint arXiv: 2505.23754, 2025, articleTitle=null, refAbstract=null), Reference(id=1329419732664562466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Xin Huajian, Guo Daya, Shao Zhihong, et al. DeepSeek-Prover: Advancing theorem proving in LLMs through large-scale synthetic data[J]. arXiv preprint arXiv: 2405.14333, 2024, articleTitle=null, refAbstract=null), Reference(id=1329419732735865635, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Mukherjee P, Delaware B. Towards automated verification of LLM-synthesized C programs[J]. arXiv preprint arXiv: 2410.14835, 2024, articleTitle=null, refAbstract=null), Reference(id=1329419732798780196, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhao Yongwang. Functional programming and proof[EB/OL]. 2021[2025-12-10]. https://www.yuque.com/zhaoyongwang/fpp/, articleTitle=null, refAbstract=null), Reference(id=1329419732857500453, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Back R. Invariant based programming: Basic approach and teaching experiences[J]. Formal Aspects of Computing, 2009, 21(3): 227−244, articleTitle=null, refAbstract=null), Reference(id=1329419732920415014, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Böhme S, Nipkow T. Sledgehammer: Judgement day[C]//Proc of the 5th Int Joint Conf of Automated Reasoning. Berlin: Springer, 2010: 107−121, articleTitle=null, refAbstract=null), Reference(id=1329419732979135271, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Sherriff M, Williams L. Tool support for estimating software reliability in Haskell programs[C]// Proc of IEEE Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2004: 61−62, articleTitle=null, refAbstract=null), Reference(id=1329419733037855528, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Haftmann F, Bulwahn L, Nipkow T. Code generation from Isabelle/HOL theories[EB/OL]. 2025[2025-12-10]. https://isabelle.in.tum.de/doc/codegen.pdf, articleTitle=null, refAbstract=null), Reference(id=1329419733117547305, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Ren Z Z, Shao Zhihong, Song Junxiao, et al. DeepSeek-Prover-V2: Advancing formal mathematical reasoning via reinforcement learning for subgoal decomposition[J]. arXiv preprint arXiv: 2504.21801, 2025, articleTitle=null, refAbstract=null), Reference(id=1329419733188850474, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=文成, 马智, 胡俊杰, 等. 大语言模型赋能软件形式化验证研究综述[J/OL]. 软件学报, 2026[2026-02-20]. http: //www.jos.org.cn/1000-9825/7603.htm, articleTitle=null, refAbstract=null), Reference(id=1329419733264347947, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Wen Cheng, Ma Zhi, Hu Junjie, et al. A review on software formal verification empowered by large language models[J/OL]. Journal of Software (in Chinese), 2026[2026-02-20]. http://www.jos.org.cn/1000-9825/7603.htm, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419724984791728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=2, ext=[AuthorCompanyExt(id=1329419724988986033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419724997374642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419725077066419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=3, ext=[AuthorCompanyExt(id=1329419725089649332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419725098037941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])], figs=[ArticleFig(id=1329419726868034264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 1, caption=Organizational structure diagram, figureFileSmall=09tjCJBBRQJiPcNbrLx31A==, figureFileBig=xA17s18QHnZq2UwHaQRnyA==, tableContent=null), ArticleFig(id=1329419726939337433, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图1, caption=组织结构图, figureFileSmall=09tjCJBBRQJiPcNbrLx31A==, figureFileBig=xA17s18QHnZq2UwHaQRnyA==, tableContent=null), ArticleFig(id=1329419727119692506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 2, caption=Instantiation of the search tree model, figureFileSmall=qGv0XQzV8nkPrma7goDRPw==, figureFileBig=94ZiTDHuvciH1g7Nb03w+A==, tableContent=null), ArticleFig(id=1329419727190995675, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图2, caption=搜索树模型实例化, figureFileSmall=qGv0XQzV8nkPrma7goDRPw==, figureFileBig=94ZiTDHuvciH1g7Nb03w+A==, tableContent=null), ArticleFig(id=1329419727300047580, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 3, caption=Generic locale of search tree structures and partial inheritance relationships, figureFileSmall=33gFxUvu0+tIaK/vUwL15A==, figureFileBig=Z/GOKMzL85rxsDDHrxaA6w==, tableContent=null), ArticleFig(id=1329419727375545053, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图3, caption=搜索树类结构通用区域及部分继承关系, figureFileSmall=33gFxUvu0+tIaK/vUwL15A==, figureFileBig=Z/GOKMzL85rxsDDHrxaA6w==, tableContent=null), ArticleFig(id=1329419727459431134, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 4, caption=Logical specifications of functional correctness for generic operations and partial inheritance relationships, figureFileSmall=+QKletwcDBaYxb1dFDZMJA==, figureFileBig=jKv15OXmS0AiN3zsbnInUA==, tableContent=null), ArticleFig(id=1329419727534928607, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图4, caption=通用操作功能正确性的逻辑规约及部分继承关系, figureFileSmall=+QKletwcDBaYxb1dFDZMJA==, figureFileBig=jKv15OXmS0AiN3zsbnInUA==, tableContent=null), ArticleFig(id=1329419727610426080, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 5, caption=Partial instantiation of structural invariants, figureFileSmall=vjAxKiZ9J6QhoVKvyNJyAA==, figureFileBig=ex8v7LlAsYcL2SyzP4R13g==, tableContent=null), ArticleFig(id=1329419727681729249, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图5, caption=结构不变式的部分实例化, figureFileSmall=vjAxKiZ9J6QhoVKvyNJyAA==, figureFileBig=ex8v7LlAsYcL2SyzP4R13g==, tableContent=null), ArticleFig(id=1329419727740449506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 6, caption=Framework for automatic synthesis of algorithm code, figureFileSmall=TokKJ7vzGCB5wzd6apqZ1g==, figureFileBig=na916a8+Aj/d5t4JxyeOog==, tableContent=null), ArticleFig(id=1329419727811752675, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图6, caption=自动合成算法代码框架, figureFileSmall=TokKJ7vzGCB5wzd6apqZ1g==, figureFileBig=na916a8+Aj/d5t4JxyeOog==, tableContent=null), ArticleFig(id=1329419727874667236, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 7, caption=Script modularization of algorithms in Isabelle, figureFileSmall=kV9XeeotZSvkQQP34OBotQ==, figureFileBig=coxznX53L3GkuAWIl9mLSw==, tableContent=null), ArticleFig(id=1329419727937581797, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图7, caption=算法在Isabelle中的脚本模块化, figureFileSmall=kV9XeeotZSvkQQP34OBotQ==, figureFileBig=coxznX53L3GkuAWIl9mLSw==, tableContent=null), ArticleFig(id=1329419728000496358, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 8, caption=Automated block-wise verification strategy, figureFileSmall=L+i7uNSBnI9ecnZ6XABxjA==, figureFileBig=aTYXeGk/Kt4KRLV0EuehQA==, tableContent=null), ArticleFig(id=1329419728059216615, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图8, caption=自动化分块验证策略, figureFileSmall=L+i7uNSBnI9ecnZ6XABxjA==, figureFileBig=aTYXeGk/Kt4KRLV0EuehQA==, tableContent=null), ArticleFig(id=1329419728117936872, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 9, caption=Program generation process, figureFileSmall=WO2kjv/5bvH/XAXYUx9+Jw==, figureFileBig=vk8BIjfGyLhfecc3MjDOGw==, tableContent=null), ArticleFig(id=1329419728189240041, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图9, caption=程序生成流程, figureFileSmall=WO2kjv/5bvH/XAXYUx9+Jw==, figureFileBig=vk8BIjfGyLhfecc3MjDOGw==, tableContent=null), ArticleFig(id=1329419728256348907, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 1, caption=null, figureFileSmall=m0bw5BCbKzR0GG+wxYnWag==, figureFileBig=alUEAymwI2QZR81n6jv5YQ==, tableContent=null), ArticleFig(id=1329419728331846380, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图1, caption=, figureFileSmall=m0bw5BCbKzR0GG+wxYnWag==, figureFileBig=alUEAymwI2QZR81n6jv5YQ==, tableContent=null), ArticleFig(id=1329419728394760941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 10, caption=Reuse of binary search tree structures, figureFileSmall=yNkPDvxXu1DieJNhh3bwJg==, figureFileBig=UmHjuQ384XvLOTCWxH3SoQ==, tableContent=null), ArticleFig(id=1329419728461869806, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图10, caption=复用二叉搜索树结构, figureFileSmall=yNkPDvxXu1DieJNhh3bwJg==, figureFileBig=UmHjuQ384XvLOTCWxH3SoQ==, tableContent=null), ArticleFig(id=1329419728528978671, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 11, caption=Locale and parameter instantiation of binary search tree, figureFileSmall=s5CJzQpTimK1AM7bVybEeg==, figureFileBig=NDGVT/x8WENFg6fNJJJ5YA==, tableContent=null), ArticleFig(id=1329419728587698928, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图11, caption=二叉搜索树区域及参数实例化, figureFileSmall=s5CJzQpTimK1AM7bVybEeg==, figureFileBig=NDGVT/x8WENFg6fNJJJ5YA==, tableContent=null), ArticleFig(id=1329419728679973617, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 12, caption=Framework for automatic synthesis of LCA algorithm, figureFileSmall=LYgiK7i5b+FUNWadw8VD0w==, figureFileBig=+JX/e+DCUti/W6kcbXBNjw==, tableContent=null), ArticleFig(id=1329419728738693874, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图12, caption=自动合成LCA算法框架, figureFileSmall=LYgiK7i5b+FUNWadw8VD0w==, figureFileBig=+JX/e+DCUti/W6kcbXBNjw==, tableContent=null), ArticleFig(id=1329419728801608435, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 13, caption=Verification lemma set for isinbst and is_ancestorbst functions, figureFileSmall=xiA/WZ/1leakUGqKQn6Uxg==, figureFileBig=CXlVM1fEbZ687oqryzR+Tw==, tableContent=null), ArticleFig(id=1329419728856134388, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图13, caption=isinbst和is_ancestorbst函数的验证引理集, figureFileSmall=xiA/WZ/1leakUGqKQn6Uxg==, figureFileBig=CXlVM1fEbZ687oqryzR+Tw==, tableContent=null), ArticleFig(id=1329419728919048949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 14, caption=Automated verification of lca_bst functional correctness, figureFileSmall=6LT4rlot7hX+tR9N/gJ0Fg==, figureFileBig=PmlRj2LsmMoz7cVhlD5YDg==, tableContent=null), ArticleFig(id=1329419728986157814, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图14, caption=lca_bst功能正确性的自动化验证过程, figureFileSmall=6LT4rlot7hX+tR9N/gJ0Fg==, figureFileBig=PmlRj2LsmMoz7cVhlD5YDg==, tableContent=null), ArticleFig(id=1329419729057460983, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 15, caption=Automated block-wise verification of LCA algorithm, figureFileSmall=izpdstPnED0uZjY9CAe18w==, figureFileBig=S4R9bUSWh9Gfb4xPZA7Vrg==, tableContent=null), ArticleFig(id=1329419729162318584, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图15, caption=LCA算法自动化分块验证, figureFileSmall=izpdstPnED0uZjY9CAe18w==, figureFileBig=S4R9bUSWh9Gfb4xPZA7Vrg==, tableContent=null), ArticleFig(id=1329419729225233145, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 16, caption=Haskell code generation for LCA algorithm, figureFileSmall=XuHfKfHIvqN31V10bGiqrg==, figureFileBig=+ENCES0kWLETPTJDBzt87w==, tableContent=null), ArticleFig(id=1329419729283953402, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图16, caption=LCA算法的Haskell代码生成, figureFileSmall=XuHfKfHIvqN31V10bGiqrg==, figureFileBig=+ENCES0kWLETPTJDBzt87w==, tableContent=null), ArticleFig(id=1329419729376228091, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 17, caption=Locale and parameter instantiation of RBT-based dynamic order statistic tree, figureFileSmall=HG3g6Vq4XbBDRPxYUYWc7w==, figureFileBig=ym6fdw3xeCSoPKwcdQwGiA==, tableContent=null), ArticleFig(id=1329419729455919868, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图17, caption=基于红黑树的动态顺序统计树区域及参数实例化, figureFileSmall=HG3g6Vq4XbBDRPxYUYWc7w==, figureFileBig=ym6fdw3xeCSoPKwcdQwGiA==, tableContent=null), ArticleFig(id=1329419729523028733, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 18, caption=Automated verification of structural invariant for insertion operations in the dynamically maintained Top k algorithm, figureFileSmall=asRhdZpmHTO0HdjXBaFIfg==, figureFileBig=8w211nyVwX1AhZYE39oztg==, tableContent=null), ArticleFig(id=1329419729590137598, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图18, caption=动态维护Top k算法插入操作结构不变性自动化验证, figureFileSmall=asRhdZpmHTO0HdjXBaFIfg==, figureFileBig=8w211nyVwX1AhZYE39oztg==, tableContent=null), ArticleFig(id=1329419729665635071, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 19, caption=Interactive theorem verification of LCA algorithm, figureFileSmall=l+DVHqjbe0Hsey/DOz9eMQ==, figureFileBig=Py+HLzD/40kf6a6TnH8+ZA==, tableContent=null), ArticleFig(id=1329419729728549632, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图19, caption=LCA算法交互式定理验证, figureFileSmall=l+DVHqjbe0Hsey/DOz9eMQ==, figureFileBig=Py+HLzD/40kf6a6TnH8+ZA==, tableContent=null), ArticleFig(id=1329419729787269889, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 20, caption=Prompt in initial generation phase, figureFileSmall=HkfqPhRjoBaELtEe3ECRzA==, figureFileBig=lUZ6Q1x/pjI9ztLjZjUp4Q==, tableContent=null), ArticleFig(id=1329419729858573058, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图20, caption=初始生成阶段提示词, figureFileSmall=HkfqPhRjoBaELtEe3ECRzA==, figureFileBig=lUZ6Q1x/pjI9ztLjZjUp4Q==, tableContent=null), ArticleFig(id=1329419729934070531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 21, caption=Error fixing prompt in the interactive phase, figureFileSmall=0s4E0s0EgzP9+w13jfveGg==, figureFileBig=kXeaBDeQfB1SRRia0uU49A==, tableContent=null), ArticleFig(id=1329419730085065476, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图21, caption=交互阶段错误修复提示词, figureFileSmall=0s4E0s0EgzP9+w13jfveGg==, figureFileBig=kXeaBDeQfB1SRRia0uU49A==, tableContent=null), ArticleFig(id=1329419730177340165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 22, caption=ChatGPT-4o model verification of LCA algorithm, figureFileSmall=Jcv3txiXH0lAx9E33MPoZw==, figureFileBig=hzJY0inF4zYY7ru8+hTcuQ==, tableContent=null), ArticleFig(id=1329419730248643334, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图22, caption=LCA算法ChatGPT-4o模型验证, figureFileSmall=Jcv3txiXH0lAx9E33MPoZw==, figureFileBig=hzJY0inF4zYY7ru8+hTcuQ==, tableContent=null), ArticleFig(id=1329419730324140807, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 23, caption=Model-generated auxiliary lemmas for non-empty trees, figureFileSmall=oB4a5WMmLv1c4NLqSOIg7g==, figureFileBig=j9xxB5sHpoM5lnEE2ogCkQ==, tableContent=null), ArticleFig(id=1329419730408026888, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图23, caption=在非空树情况下模型生成的辅助引理, figureFileSmall=oB4a5WMmLv1c4NLqSOIg7g==, figureFileBig=j9xxB5sHpoM5lnEE2ogCkQ==, tableContent=null), ArticleFig(id=1329419730479330057, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Figure 24, caption=DeepSeek-Prover-V2-671B model verification of LCA algorithm, figureFileSmall=fluR7o6hsSV+czP569bTXg==, figureFileBig=xzdBoBgi02CdDDf3u76xfg==, tableContent=null), ArticleFig(id=1329419730567410442, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=图24, caption=LCA算法DeepSeek-Prover-V2-671B模型验证, figureFileSmall=fluR7o6hsSV+czP569bTXg==, figureFileBig=xzdBoBgi02CdDDf3u76xfg==, tableContent=null), ArticleFig(id=1329419730647102219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Table 1, caption=

Comparison of Ref. [11] and Our Method

, figureFileSmall=null, figureFileBig=null, tableContent=
对比项文献[11]本文方法
函数式建模库结构与操作建模库
验证引理库列表辅助函数引理集搜索树类功能和
结构验证引理集
验证维度底层基本操作实际算法应用
目标建模—验证建模—验证—程序生成一体化
), ArticleFig(id=1329419730743571212, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=表1, caption=

文献[11]与本文方法对比

, figureFileSmall=null, figureFileBig=null, tableContent=
对比项文献[11]本文方法
函数式建模库结构与操作建模库
验证引理库列表辅助函数引理集搜索树类功能和
结构验证引理集
验证维度底层基本操作实际算法应用
目标建模—验证建模—验证—程序生成一体化
), ArticleFig(id=1329419730827457293, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=EN, label=Table 2, caption=

Comparison of Verification Methods

, figureFileSmall=null, figureFileBig=null, tableContent=
验证目标对比项ChatGPT-4oDeepSeek-Prover-
V2-671B(CoT)
交互式定
理验证
ChatGPT-4o+
交互式
定理验证
DeepSeek-Prover-
V2-671B(CoT)+
交互式定理验证
本文验
证方法
LCA算法功能
正确性验证
sorry数330000
拆分的目标数032033
自定义引理条数066760
验证代码
行数
自定义引理行数0Failure97103970
主定理行数FailureFailure81667329
人工交互占比/%88.7673.3765.8817.24
动态维护Top k算法
(插入操作)
正确性验证
sorry数550000
拆分的目标数110112
自定义引理条数6103429291
验证代码
行数
自定义引理行数FailureFailure1431291382
主定理行数FailureFaliure2626369
人工交互占比/%87.8567.7467.2436.36
), ArticleFig(id=1329419730907149070, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, language=CN, label=表2, caption=

验证方法的对比

, figureFileSmall=null, figureFileBig=null, tableContent=
验证目标对比项ChatGPT-4oDeepSeek-Prover-
V2-671B(CoT)
交互式定
理验证
ChatGPT-4o+
交互式
定理验证
DeepSeek-Prover-
V2-671B(CoT)+
交互式定理验证
本文验
证方法
LCA算法功能
正确性验证
sorry数330000
拆分的目标数032033
自定义引理条数066760
验证代码
行数
自定义引理行数0Failure97103970
主定理行数FailureFailure81667329
人工交互占比/%88.7673.3765.8817.24
动态维护Top k算法
(插入操作)
正确性验证
sorry数550000
拆分的目标数110112
自定义引理条数6103429291
验证代码
行数
自定义引理行数FailureFailure1431291382
主定理行数FailureFaliure2626369
人工交互占比/%87.8567.7467.2436.36
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550899, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550899, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202550899, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202550899, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1777564800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
Isabelle驱动的搜索树类算法建模及自动化验证
左正康 1, 2, 3 , 朱小影 1 , 游珍 1 , 王昌晶 1, 2, 3, *
计算机研究与发展 | 面向人机物融合智能系统的安全可信专题 2026,63(5): 1117-1138
收起
收藏切换
计算机研究与发展 |面向人机物融合智能系统的安全可信专题 2026 , 63 (5) : 1117 -1138
Isabelle驱动的搜索树类算法建模及自动化验证
全屏
[Author(id=1329419725169341111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zuo803@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725257421499, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725169341111, language=EN, stringName=Zhengkang Zuo, firstName=Zhengkang, middleName=null, lastName=Zuo, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725324530364, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725169341111, language=CN, stringName=左正康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"rL2tWBuciDKrtMqL2ejzBQ==","content":"

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

"}, bioImg=rL2tWBuciDKrtMqL2ejzBQ==, bioContent=

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419724984791728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=2, ext=[AuthorCompanyExt(id=1329419724988986033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419724997374642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419725077066419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=3, ext=[AuthorCompanyExt(id=1329419725089649332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419725098037941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])]), Author(id=1329419725383250622, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725450359488, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725383250622, language=EN, stringName=Xiaoying Zhu, firstName=Xiaoying, middleName=null, lastName=Zhu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

"}, bioImg=null, bioContent=

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725513274049, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725383250622, language=CN, stringName=朱小影, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"lZHsNxsnrDYSyB3ZXumHzw==","content":"

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=lZHsNxsnrDYSyB3ZXumHzw==, bioContent=

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419725571994307, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419725639103173, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725571994307, language=EN, stringName=Zhen You, firstName=Zhen, middleName=null, lastName=You, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725702017734, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725571994307, language=CN, stringName=游珍, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"qsQFSPt9NXR0hQmt+2B0dA==","content":"

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

"}, bioImg=qsQFSPt9NXR0hQmt+2B0dA==, bioContent=

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419725781709512, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wcj@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329419725882372812, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725781709512, language=EN, stringName=Changjing Wang, firstName=Changjing, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022, bio={"content":"

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

"}, bioImg=null, bioContent=

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419725945287373, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, authorId=1329419725781709512, language=CN, stringName=王昌晶, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"BInriQKiXVcqYhXUOwq0Ig==","content":"

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

"}, bioImg=BInriQKiXVcqYhXUOwq0Ig==, bioContent=

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419724905099949, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=1, ext=[AuthorCompanyExt(id=1329419724913488558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419724921877167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724905099949, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419724984791728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=2, ext=[AuthorCompanyExt(id=1329419724988986033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419724997374642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419724984791728, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419725077066419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, xref=3, ext=[AuthorCompanyExt(id=1329419725089649332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022), AuthorCompanyExt(id=1329419725098037941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419719511224943, companyId=1329419725077066419, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])])]
左正康1, 2, 3 , 朱小影1, 游珍1, 王昌晶1, 2, 3, *
作者信息
  • 1江西师范大学人工智能学院 南昌 330022
  • 2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
  • 3语言智能研究中心(江西师范大学) 南昌 330022
通讯作者:
王昌晶()
作者简介:

作者贡献声明

左正康和朱小影共同提出方法思路和实验方案;朱小影完成实验并撰写论文;游珍和王昌晶提出指导意见并修改论文。

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms
Zhengkang Zuo1, 2, 3 , Xiaoying Zhu1, Zhen You1, Changjing Wang1, 2, 3, *
Affiliations
  • 1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
  • 2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
  • 3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022
  • born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

    born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

    born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

    born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

出版时间: 2026-05-01 doi: 10.7544/issn1000-1239.202550899
文章导航
收藏切换

搜索树类算法广泛应用于数据库索引、编译器设计、文件系统等领域,其功能正确性验证是保障软件可靠性的关键环节。然而,传统开发流程存在2个主要问题:首先,算法设计常缺乏严格的数学建模,导致正确性验证停留于经验层面;其次,现有验证方法多依赖手工证明或交互式定理证明工具,随着算法规模的扩大,验证复杂度呈指数级增长。为解决上述问题,提出了Isabelle驱动的搜索树类算法建模及自动化验证方法。该方法基于经过形式化验证的函数式建模库,构建了涵盖搜索树类结构的模块化建模策略,并设计了形式化规约自动合成算法代码框架。开发者仅需补充少量函数表达式,即可实现完整的算法。此外,开发了可复用的验证引理库,并通过自动化分块验证策略有效降低了验证成本。进一步地,提出了函数式可执行程序生成方法。通过典型案例实验验证,结果表明所提方法显著降低了验证成本。与交互式验证方法相比,代码行数和人工占比分别平均减少了88.60%、61.51%;与“生成式AI+交互式验证方法”相比,代码行数和人工占比分别平均减少了88.09%、41.76%。该框架为特定领域复杂数据结构算法的形式化验证提供了系统性且高度自动化的解决方案,同时为生成正确的函数式可执行程序提供了可行路径与方法保障。

搜索树  /  Isabelle定理证明器  /  函数式建模  /  自动化验证  /  程序生成

Search tree algorithms are widely used in areas such as database indexing, compiler design, and file systems, where the functional correctness of these algorithms is a critical factor in ensuring software reliability. However, traditional development process faces two major challenges: first, algorithm design often lacks rigorous mathematical modeling, causing correctness verification to remain at an empirical level; second, existing verification approaches heavily rely on manual or interactive theorem proving, making the verification complexity grow exponentially with increasing algorithm scale. To address the above issues, an Isabelle-driven method for modeling and automated verification of search tree algorithms is proposed. This method builds on a formally verified functional modeling library to construct a modular modeling strategy that supports various search tree structures, and introduces a formal specification-driven framework for automatically synthesizing algorithmic code. Developers are required to supply only minimal functional expressions to complete the implementation. In addition, a reusable lemma library has been developed to support an automated block-wise verification strategy, significantly reducing verification costs. Furthermore, a method for generating functional executable programs is proposed. Experimental evaluation using a representative case study demonstrates that the proposed method substantially reduces verification costs. Compared with interactive verification approaches, the average reductions in code size and manual effort are 88.60% and 61.51%, respectively; compared with generative AI plus interactive verification methods, the average reductions in code size and manual effort are 88.09% and 41.76%, respectively. Overall, the proposed framework provides a systematic and highly automated solution for the formal verification of complex data structure algorithms in specific domains, while also offering a feasible pathway and methodological support for generating correct functional executable programs.

search tree  /  Isabelle theorem prover  /  functional modeling  /  automated verification  /  program generation
左正康, 朱小影, 游珍, 王昌晶. Isabelle驱动的搜索树类算法建模及自动化验证. 计算机研究与发展, 2026 , 63 (5) : 1117 -1138 . DOI: 10.7544/issn1000-1239.202550899
Zhengkang Zuo, Xiaoying Zhu, Zhen You, Changjing Wang. Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms[J]. Journal of Computer Research and Development, 2026 , 63 (5) : 1117 -1138 . DOI: 10.7544/issn1000-1239.202550899
搜索树类算法作为组织与管理程序状态、符号信息及结构化数据的关键技术,广泛应用于数据库索引、编译器设计、文件系统等领域,确保这些算法的功能正确性成为系统安全性和稳定性的关键保障[1],任何细微的错误都可能导致数据错误、性能下降,甚至引发安全漏洞和系统崩溃。然而传统的搜索树类算法开发流程中存在2个主要问题:首先,算法设计常缺乏严格的数学建模,导致正确性验证停留于经验层面;其次,现有验证方法多依赖人工定理证明或交互式定理证明工具,导致验证复杂度随算法规模呈指数增长。
在算法设计方面,搜索树作为索引、调度、缓存与事务管理等核心模块的基础数据结构,其相关算法通常需要处理复杂的结构变动,并严格依赖有序性与平衡性等不变式约束。若缺乏形式化规约,这些隐含约束往往难以被显式刻画与验证,从而在迭代或组合过程中造成结构完整性的破坏,例如,当开发者未能通过广义代数数据类型对红黑树的颜色约束进行编译期验证[2],可能引发违反平衡条件的运行时错误。与此同时,在实际开发中,开发者可能为了追求开发速度,忽视严格的类型检查和函数纯度,导致程序中引入隐蔽的逻辑错误或未处理的异常情况[3]。例如在递归函数设计中未能确保递归调用的终止条件,可能导致无限递归,最终导致栈溢出错误[4],在核心建模时忽视行为回溯会导致程序在不同分支间发生状态污染[5]。搜索树类算法设计若仅依赖经验性规则而非数学建模,程序异常可能通过算法层级传递,最终在系统集成阶段表现为逻辑崩溃,造成严重后果,甚至引发灾难性事件。在算法验证方面,目前形式化验证方法,如使用Coq[6]、Isabelle/HOL[7-8]等定理证明器对算法进行机械化验证,在理论上能够提供严格的正确性保证,但在实际应用中存在以下局限:验证过程通常针对具体的算法程序进行交互式机械化验证,导致验证的可复用性较低,当验证对象或应用场景发生变化时,需要重新设计验证方案;其次,现有验证方法自动化程度低,验证过程需要大量的人为干预,耗费大量时间和人力成本。这些因素限制了形式化验证方法在工业界的广泛应用,阻碍了函数式可执行程序的大规模产业化。
为解决上述问题,本文在不同的搜索树结构找到其中的共性,制定高效的建模及验证方法,在快速开发程序的同时,确保可执行程序的正确性和健壮性。进一步,建立函数式验证框架,构建统一的验证模式,引入自动验证技术,以在保证验证准确性的前提下,尽可能地减少人为参与,降低验证成本。并选取Haskell为示例语言,其适用于可靠性要求高的系统开发。结合程序生成,可将经形式化验证的算法转为Haskell可执行程序,从而推动函数式程序工业化应用。本文的组织结构图如图1所示,其贡献点总结为3个方面:
1)利用经过形式化验证的函数式建模库,构建了一个包含搜索树类结构的模块化建模策略,并设计了自动合成形式化规约算法的代码框架。开发者只需补充少量的函数表达式,即可完成算法的完整实现。
2)开发了可复用的验证引理库,并通过自动化分块验证策略使形式化验证流程更加高效,提高了验证过程的模块化的同时,还将平均验证成本显著降低。
3)提出了函数式可执行程序生成机制,将建模、验证方法与Isabelle提供的代码生成机制相结合。通过在建模阶段规约精确定义算法行为,并在验证阶段确保功能与结构正确性,最终生成的可执行程序能够与最初的规约保持严格一致,从而保证代码的正确性与可信度。
本文主要聚焦搜索树类结构算法建模及自动化验证研究,并与大语言模型验证进行实验比较。因此,本节将从搜索树类结构建模与验证框架、大语言模型验证2个方面进行相关工作比较。
1)搜索树类结构建模与验证框架。为突破单一算法验证模式的局限性,近年来研究逐渐转向通用验证框架的设计,旨在通过统一的方法支持多样化搜索树类结构的建模与验证。文献[9]基于函数式建模框架,给出了插入和删除的高阶泛化函数,对LLRB进行实例化建模,并对其附加性质进行细化,给出具体的验证方案。文献[10]提出了针对动态顺序统计树类结构的函数式建模和自动化验证框架,支持动态集合、顺序统计和搜索树等常用操作,构建完善的验证引理库并详细阐述具体的验证方法。上述文献针对具体类型的搜索树结构,其适用范围相对有限,较难在不同数据结构与算法间实现通用化迁移。
文献[11]提出用于验证8种搜索树类结构功能正确性的验证框架,通过中序遍历将树映射为列表,自动验证查找、插入以及删除操作的功能正确性,并严格证明了操作执行前后的搜索树属性保持。上述工作在构建通用验证框架方面取得了重要进展,但其构建的引理库主要集中于列表辅助函数,验证范围局限于搜索树的基本增加、删除和查找操作,对搜索树结构的实际算法应用尚未覆盖,且该研究未涉及实际算法的建模、验证与可执行程序生成的完整流程,具体对比见表1。
2)大语言模型验证。大语言模型辅助验证已成为提升形式化验证自动化能力的重要研究方向。随着大语言模型在数学推理领域的能力不断增强[12-14],相关研究正尝试将其能力系统地融入定理证明流程。文献[15]提出自玩定理证明框架,通过协同优化猜想生成与定理证明,有效克服了训练数据稀缺问题。DeepTheorem[16]构建了专用于自然语言定理证明的框架,包含12.1万条国际数学奥林匹克(IMO)级别定理的数据集,并采用RL-Zero强化学习方法,直接激励模型进行数学推理。DeepSeek-Prover[17]通过大规模自动形式化方法生成800万条基于Lean 4的定理证明数据,结合质量过滤与迭代训练策略,在多个基准测试上显著超越现有方法。上述方法在形式化数学领域取得了显著进展,但在处理需要深层次、多步骤推理以及高度抽象的问题时仍存在一定局限性,特别是在包括搜索树等数据结构算法的泛化能力方面仍有待提升。SYNVER是一种面向C程序的综合与验证框架,在大语言模型生成程序的过程中施加语法与语义偏置,从而使生成的程序更易于自动化验证[18]。但该方法目前尚难以应对复杂算法设计中数据结构维持不变量的验证任务。
为简化算法设计和验证及提高代码复用性,本文构建了基于Isabelle/HOL的搜索树类结构函数式建模库与验证引理库,涵盖二叉搜索树、AVL树、红黑树及变体、动态顺序统计树类、区间树以及简单多叉搜索树等典型结构,旨在为算法设计提供建模基础并降低验证复杂度。本节围绕搜索树类结构的函数式定义展开,设计了统一的建模策略。对于搜索树类结构对应的通用操作,开发了通用的操作模板,且这些操作已通过形式化方法严格验证其正确性。
函数式建模库的核心目标是通过严格的数学抽象,将搜索树类结构的语义约束与操作逻辑转换为可机械验证的形式化模型。本库基于Isabelle/HOL定理证明器,构建了结构定义层与操作模板层的双层建模体系:前者通过高阶逻辑精确刻画搜索树结构的本质特征,后者则提供已验证的通用操作模板,为后续代码生成与验证奠定基础。
函数式建模库基于Isabelle/HOL的代数数据类型系统,通过递归定义和参数化设计,实现搜索树类结构的统一建模与灵活扩展。通过多态类型参数与高阶逻辑约束,既支持搜索树结构的严格数学建模,又能快速实例化为特定领域结构,以适应不同的应用需求。
搜索树类的基础模型采用递归定义,搜索树的性质主要体现为每个节点的左子树所有键值小于该节点键值,右子树所有键值大于该节点键值,这一结构约束将在第2.2.2节结构正确性中进一步详细说明。其类型参数与结构约束定义为:
$ \begin{split}&{{\mathrm{datatype}}} \;\text{'}{\mathrm{a}} \;{\mathrm{treestr}} = \\&{\mathrm{Leaf}}\; |\; {\mathrm{Node}}\; [info] \;\text{'}\text{'}\text{'}{\mathrm{a}}\; {\mathrm{treestr}}\text{'}\text{'} \;\text{'}{\mathrm{o}}\; \text{'}\text{'}\text{'}{\mathrm{a}}\; {\mathrm{treestr}}\text{'}\text{'}\end{split} $
其中,Leaf代表叶子节点(即节点为空),Node代表非叶子节点(即节点非空),info为可选变量,在节点中存储额外的信息以支持特定操作,普通搜索树无需该信息位,例如顺序统计树类可通过该信息位记录子树规模。参数'a和'o为多态类型参数,'a是数据结构的类型参数,'o代表节点存储的信息类型,'o可以泛化为'a(单一数据)以及'a*extra(键值对)等情形,根据需求实例化为不同的具体类型。
普通的二叉搜索树节点值无附加性质,可根据搜索树的基础模型将treestr实例化为treestrbst。针对需含有其他附加信息的场景,如AVL树的高度信息、红黑树的颜色信息等,则利用参数封装复杂的数据类型,可将treestr分别实例化为treestravl、treestrrbt。对于多叉搜索树结构,可通过扩展搜索树类模型的参数以支持多路分支。搜索树模型实例化如图2所示。
搜索树类通用操作模板旨在通过预先设计好的代码框架,让开发者在保持形式化严谨性的前提下,同时快速实现不同变种搜索树结构的核心功能。通用操作模板不仅支持跨结构的实例化与扩展,还避免重复编写和验证基础逻辑,从而简化开发流程。
对于不涉及外部输入参数的操作,其核心只需关注2类情形:空树情形,即如何处理叶节点;节点情形,即如何将左右子树的计算结果与当前节点值或结构组合,整个过程自顶向下、逐层递归,每一步都依赖于对其子结构先前计算结果的调用,最终得出全树的整体结果。搜索树类结构中涉及输入参数的一系列操作基于比较函数(cmp)实现,比较元素必须满足可比较性和对称性,进而构建搜索树类结构相关操作的高阶复合函数:
fun <opname> :: " 'a treestr ⇒ <inputtype> ⇒ <outputtype> " where
" <opname> Leaf x = [adjustfuncLeaf] <endLeaf >"
" <opname> (Node l a r) x = [pre-operation]
case <cmpoperation> of
LT ⇒ <[adjustfuncLT] endLT> |
EQ ⇒ <[adjustfuncEQ] endEQ> |
GT ⇒ <[adjustfuncGT] endGT>"
其中,[]表示可选部分,<>表示实现功能需要补充的逻辑部分,opname是具体操作名称,决定函数的核心行为,'a treestr是泛化的搜索树结构,节点值类型为'a,其对应的元素需满足全序关系,inputtype和outputtype分别表示操作所需的输入参数类型和操作结果类型。在函数体中,对于树为空的情况,根据函数功能返回最终结果(endLeaf),如需处理可调用调整函数(adjustfuncLeaf)。对于树非空的情况,可进行预处理操作(pre-operation)后再调用比较函数判断目标节点与当前节点的大小关系。若比较结果为小于(LT)时,则对当前节点的左子树进行函数的递归操作,在左子树中找到目标节点后返回最终结果(endLT)。若结果为等于(EQ),则说明当前节点是需要处理的目标节点,可直接对当前节点执行相关操作,返回最终结果(endEQ)。若比较结果为大于(GT),则对当前节点的右子树进行函数的递归操作,在右子树中找到目标节点返回结果(endGT)。
通过模板参数化的形式,我们只需提供少量元素即可快速生成类型安全的操作函数。这一过程自然地继承了高阶复合函数的模块化特性,使得对其他需要输入参数的操作也能同样以少量替换完成实例化。
区域(locale)是Isabelle/HOL中提供的一种程序模块化和参数化机制,可以有效表达函数式程序结构之间复杂的依赖关系[19]。基于通用操作模板,我们利用locale定义高阶泛化函数,用于刻画搜索树类结构的一系列实例化操作。在此基础上,针对特定类型的搜索树结构,可通过locale的继承机制引入更具结构特性的约束与操作定义,进一步构造特定变体扩展操作,以对实例化操作进行补充和增强,图3展示了函数式建模库中搜索树类结构的通用区域及部分继承关系。
验证引理库是本文框架实现高效形式化验证的核心基础,由功能正确性验证引理集与结构正确性验证引理集组成,将搜索树类算法的功能正确性与结构正确性验证解耦,显著降低验证复杂度。本节从功能正确性与结构正确性2个维度出发,分别阐述引理库的设计与实现。
验证引理库包含了二叉搜索树、AVL树、红黑树及变体、区间树及变体、动态顺序统计树类、2-3树、2-3-4树、AA树、splay树在内的14种搜索树结构。
在功能验证引理集中共包含224条功能正确性主引理以及大量辅助引理,保证搜索树结构各类操作在执行过程中均严格符合既定的功能正确性要求,并为后续验证不同搜索树算法提供了坚实的逻辑支撑。
在结构验证引理集共包含66条子结构不变式及大量辅助引理,覆盖了搜索树在修改类操作中的关键约束条件。通过对这些子结构不变式的严格刻画与验证,保证了操作执行前后搜索树结构属性的维持,从而有效避免因局部调整而引发的全局结构失效。
功能正确性验证算法操作是否满足输入-输出的语义规约,搜索树结构与列表线性表示具有严格的数学等价关系[11],搜索树操作的语义可通过列表操作间接描述,引入列表辅助函数及其对应引理作为中介,进而验证搜索树类通用操作的功能正确性。
通过中序遍历函数,我们可以将任意搜索树映射成一个有序列表。具体地,我们在Isabelle/HOL中定义了通用的中序遍历函数:
fun inorder :: " 'a treestr => 'a list" where
"inorder Leaf = []" |
"inorder Node l (a, [_]) r=inorder l @ a # inorder r"
inorder函数主要提取每个节点的核心值信息,忽略所有的附加信息。考虑到节点可能包含多个附加信息位,采用占位符机制统一处理这些附加信息。
在此基础上,我们为每种操作在列表域中设计了对应的辅助函数,通过对列表进行模式匹配和条件分支来刻画理想的语义规范。功能正确性证明的关键在于建立搜索树操作和列表辅助函数之间的行为等价,即执行搜索树操作后再中序遍历得到对应的列表,与先中序遍历原树再在列表上执行对应的辅助函数得到的结果始终保持一致。对于特定搜索树结构的扩展操作,部分函数由于其依赖节点层次或结构关系,难以直接转化为列表操作进行验证。在此类情形下,可通过构造与该操作语义等价的辅助函数,借助其与通用函数之间的等价关系,将验证任务转化为对这些连接性引理的证明。图4展示了通用操作功能正确性的逻辑规约,并呈现了部分结构变体在功能正确性层面的继承关系,用以说明不同搜索树在复用通用操作逻辑规约基础上如何引入自身特性,并通过继承机制拓展验证路径。
在机械化验证过程中,还需要通过验证数据结构在操作过程中的不变性来保证其正确性。不变性是指操作执行前后某些性质或者特征始终保持不变。对数据结构进行不变性证明时,可通过证明在执行操作前后不破坏其依赖的不变式。不变式是数据结构要符合的逻辑规则式[20]。
搜索树类结构的性质可被定义为:
1)搜索树性质不变式(简称invarsort),即树中节点值的中序遍历序列呈现线性递增的顺序。inorder函数以中序遍历的方式将搜索树结构中的节点转换为列表。转换完成后利用sorted函数判断该列表是否按升序排列。invarsort根据2个函数组合定义为:
$ {{{\mathrm{definition}}}}\;\text{'}\text{'}inva{r}_{\text{sort}}\;t\equiv sorted\;(inorder\;t)\text{'}\text{'} 。$
2)附加性质不变式(统称invarextra)是可选约束项,根据具体搜索树结构的特性选择性补充。当实例化到某一具体搜索树结构且需保持附加性质不变时(如颜色信息、树的高度、树的大小等),应结合具体需求引入相应的附加不变式。
根据1)、2)统称为搜索树结构的不变式(简称invar),其定义为:
$ {{\mathrm{definition}}}\;\text{'}\text{'}invar\;t\equiv inva{r}_{\text{sort}}\;t\wedge inva{r}_{\text{extra}}\;t\text{'}\text{'}。 $
对于修改操作(插入、删除)的函数,在执行过程中可能会改变节点信息,则需要引入额外的逻辑规则来判断其是否保持结构特性。
在形式化验证过程中,不同类型的搜索树结构其不变式(invar)各不相同,这些不变式在定义和约束数据结构行为方面起着核心作用。因此,需要针对每种搜索树结构的特性对其进行拆分和调整,同时构建相应的辅助引理集以支持证明流程。图5列举了部分典型搜索树结构需要满足的结构不变式,旨在说明结构不变式在具体建模过程中的多样性。
为将搜索树类算法的形式化验证成果应用于工业场景,本文提出了搜索树类算法的建模及自动化验证方法。利用算法规约精确定义输入-输出,确保算法设计的正确意图;在模块化建模阶段,通过复用已验证的函数式建模库并在此基础上注入核心算法逻辑,构建严谨可测的算法代码框架;自动化分块验证过程中,借助验证引理库和自动化证明方法,对算法的功能正确性和结构正确性进行验证;最后,通过代码生成机制将验证无误的算法导出为结构化、可读的函数式可执行程序。
在搜索树算法的开发中,模块化建模不仅是实现自动验证和程序生成的基础,更是保证整个开发流程具有可维护性、可重用性和可扩展性的关键。其建模策略是将算法设计拆解为3个模块:模块1是搜索树类结构定义模块,用于明确结构特性并确保类型安全;模块2是通用操作复用模块,通过复用已验证的操作函数降低算法建模与验证的复杂度;模块3是自定义关键逻辑函数模块,设计人员基于树结构或列表转换的实现方式,调用实例化与变体扩展操作实现算法整体功能。图6展示了基于模块化建模策略的自动合成算法代码框架。
算法的形式规约用于精确定义算法的行为和期望结果,是设计和编制程序的出发点,也是验证程序是否正确的依据。我们使用霍尔三元组({P},C,{Q})明确算法的语法边界:前置条件{P}描述在执行算法之前必须满足的条件;程序体C是算法具体的实现逻辑;后置条件{Q}描述算法执行完成后应满足的条件。通过这一规范,为编码与形式化证明提供参考标准。
基于算法规约可直接或间接明确所需的搜索树结构,从而确定搜索树类结构定义模块(模块1),该模块负责构建满足特定需求的搜索树结构。若规约中提及“平衡” “节点统计”等概念时,会相应地映射到子树高度、节点权重或统计信息的需求。形式规约通过刻画访问模式与性能目标,限定所选用的搜索树结构必须具备的关键组织特性,为后续的建模与实现提供明确指引。函数式建模库提供了丰富的搜索树类结构,开发者可根据搜索树模型实例化直接复用已定义的结构,从而进一步调用相关操作和引理。通过imports语句导入相关程序,即可在建模算法和证明定理时直接调用辅助函数与引理。图7展示了算法在Isabelle中复用程序的脚本模块化过程。
通用操作复用模块(模块2)依托已验证的操作函数简化建模过程。函数式建模库中为搜索树类结构封装了共有的基本操作,还针对特定变体提供额外的扩展操作。借助locale机制,开发者在编写算法时可检索相应locale中是否有可复用的操作,无需重写或重新验证。通过复用已有函数,最大限度地减少算法的构造和验证工作量,提升建模效率和一致性。
自定义关键逻辑函数模块(模块3)是模块化建模的核心阶段。该模块实现通常分为2类方式:一种是基于树结构的实现,根据搜索树的数据类型生成关键逻辑函数的基础模板,从而覆盖所有可能的构造形式并确保分支完整性,这种方式能够直接反映搜索树的层次化语义,适用于需要紧密依赖树结构性质的算法;另一种是基于列表转换的实现,将树操作转化为等价的列表操作,适用于功能逻辑更偏向序列化处理的场景。而后根据结构归纳或列表,调用实例化与变体扩展操作,从而得到满足特定功能需求的实现。该过程不仅确保了函数逻辑与数据结构特性的紧密契合,还在设计层面提高了代码的可维护性与可扩展性,为后续的自动化证明奠定基础。
完成算法的函数式建模后,为确保其实现严格符合形式规约,我们采用自动化分块验证策略对算法进行形式化验证,将验证过程划分为2个模块以提高验证效率。验证模块1针对算法中复用的通用函数,这些函数在定义时已通过形式化验证,其正确性得到充分保证,无需二次证明。验证模块2聚焦于算法的核心逻辑部分,将最大化复用已有验证引理库,并结合自动化验证策略加速证明。图8展示了自动化分块验证策略。
针对建模过程中复用的搜索树结构和操作(验证模块1),验证引理库已提供功能和结构正确性证明,确保它们在输入输出层面与形式规约完全一致,同时保证任何基于该结构的修改类操作都不会破坏既有不变式。复用这些函数时,无需重新对其内部逻辑进行验证,只需信赖对应的引理集即可。
对于主算法中每一个待证明的定理(验证模块2),验证过程中可借助验证引理库中的引理集。对于待证主定理T,可采用以下自动化证明策略进行验证:
1)目标拆分。将主定理中各个独立的结论或条件子句拆分成若干互不相交的子目标,每个子目标对应一条子引理,每条子引理只聚焦单一性质或一组相关的条件。通过这种方式,子目标更简洁、更易于使用结构归纳和自动化方法完成证明。主定理只需将已证明的引理添加到证明过程,即可完成推导。此步骤可完全自动化。
2)归纳法。结构归纳针对递归定义的搜索树结构,系统自动生成归纳规则,将任意搜索树结构的证明任务分解为平凡与非平凡2种情况。平凡情况对应树为空,证明空树情况满足目标性质;非平凡情况则假设各个子树已满足该性质,再证明由它们构造出的更复杂场景也同样满足。induct和induction都可表示对项使用归纳法,使用归纳规则前,可用全称量词约束每个标记为arbitrary的变量,rule选项可用于指定归纳规则。
3)auto方法。Isabelle定理证明器中常用的自动化证明方法结合了化简和经典逻辑推理,能自动处理许多简单的证明目标。simp表应用化简行为,需要添加验证引理库中的辅助引理集,从而化简子目标或直接得证。子目标中如果含有if、case等表达式,可配合修饰符split进行分解,使auto方法可以分别处理分解后的情况,从而完成目标的证明。
4)try命令。尝试多种自动化方法证明当前命题而不改变证明状态。该命令会调用Sledgehammer[21]等用于自动化证明的组件,按顺序尝试多个证明方法。整个过程中,try命令自动利用当前上下文中的验证引理库,检索并复用已知的辅助引理,依次尝试多个方法直到成功或全部失败。值得注意的是,在自动化验证机制的性能方面,try命令会在可行范围内自动搜索与目标适配的证明策略。随着引理库规模的增加,耗时确实会有所增加,但由于本文仅构建了与搜索树类结构相关的引理,其规模远小于Isabelle内置的引理集,因此整体搜索空间仍然有限。且try命令内部设置了搜索深度与时间限制,该增长趋势得到有效抑制,并未呈现指数级膨胀,从而保证了整体验证效率与可用性。
结合Nipkow等人[11,21]提出的Isabelle自动验证方法,本文提出的自动化证明策略整合了归纳法、auto方法与try命令,实现了较高程度的证明自动化。在该策略中,归纳法用于分解复杂问题,auto方法完成基本的自动推导,而try命令则借助自动化组件,搜索验证引理库中的相关引理,探索可行的证明路径。通过这种组合方式,本文的自动化验证能够充分利用构建的验证引理库,将复杂问题分解成小的子问题,在保证辅助引理可靠性和通用性的前提下,高效处理不同场景下的证明任务。
本文所提出的程序生成方法具有较强的普适性,能够支持多种函数式可执行程序的生成。为展示方法的有效性与可行性,本文选择Haskell作为主要示例语言。Haskell具备高度抽象、类型安全与可验证性强等特性,适用于开发可靠性要求高的软件系统[22]。通过将经形式化验证的算法自动转化为Haskell程序,可实现工业级应用。尽管以下讨论主要围绕Haskell程序生成展开,但所提方法并不限于此,其应用范围可进一步推广至其他函数式编程语言。
以算法规约为核心驱动,通过将算法意图精确定义为输入输出之间的逻辑约束,确保程序设计阶段即具备明确的正确性目标。在建模过程中,数据结构通过复用建模库中已验证的数据结构与通用函数模板,显著降低开发负担。关键逻辑的实现基于类型系统,借助定理证明器的静态检查机制,在定义阶段规避不合理分支与非法操作,保障建模质量。验证阶段依托定制的引理库,对功能正确性与结构正确性进行验证,通过自动化分块验证以及基于验证引理库的证明策略,大幅提高自动化验证能力,减少验证成本。
已经过验证的Isabelle代码具有类型约束明确、结构表达清晰、逻辑语义严谨等特点。通过预处理、翻译、序列化3个阶段,可以转换为Haskell程序代码[23]。图9展示了程序生成流程。
由datatype和definition/primrec/fun声明的等式可直接用于代码生成,export_code命令是Isabelle/ML提供的顶层命令[23],用于从当前理论中导出可执行代码,可接收多个函数名称,并为这些函数及其所有依赖自动生成目标语言的实现代码。命令格式为:
为评估本文所提方法的有效性,我们在最近公共祖先、动态维护Top k、日程安排冲突检测、滑动窗口统计等算法中成功实验。限于篇幅,本文选取最近公共祖先(LCA)算法及动态维护Top k算法为实例,展示所提方法适用性,并明确了方法的适用范围。
LCA问题是计算机科学中的经典算法问题之一,对于社交网络、生物信息学以及互联网路由算法等应用场景具有重要意义。在一棵无环树上,任意两节点总能找到它们的公共祖先,而“最近”公共祖先即指那些公共祖先中深度最大的节点,亦即位于路径交叉处最靠近两者的节点。
在对二叉搜索树的LCA算法进行形式化开发时,采用霍尔三元组严格描述算法的行为规约:
$ \begin{split}\left\{bst\;t\right\}lca :=\;& lca\_ bst(t,p,q)\{isin(t,p)\wedge isin(t,q)\wedge\\& isin(t,lca)\wedge is\_ ancestor(t,lca,p)\wedge\\& is\_ ancestor(t,lca,q)\wedge\\& (\forall v.is\_ ancestor(t,v,p)\wedge\\& is\_ ancestor\left(t,v,q\right)\longrightarrow\\& is\_ ancestor(t,v,lca))\} \end{split}$
前置条件{P}要求输入的树t是一棵有效的二叉搜索树。程序体C执行lca_bst(t, p, q)函数,计算节点p、q在树t中的LCA,并返回节点lca。后置条件{Q}则保证p、q、lca节点存在于树t中,lca是p、q的LCA,即lca是p、q的LCA,且在所有这样的祖先中lca的深度最大。
根据以上的算法规约描述,我们可以直接明确该算法使用的数据结构为二叉搜索树,该结构已存在于构建的函数式建模库(Tree_BST)中,即可直接复用建模库中二叉搜索树结构的定义,将相关的文件导入到当前文件(LCA_basedBST)中,图10为复用二叉搜索树结构的示例图。
区域继承机制允许我们在已有locale的逻辑框架之上,扩展出更具结构特征的新区域。对于二叉搜索树,在搜索树类结构通用区域(tree_operations,定义见图3)的基础上进一步引入区域继承,通过显式指定局部参数与逻辑规约,构建出刻画二叉搜索树行为的新locale(BST_treestrbst)。图11展示了用locale刻画的二叉搜索树通用操作,并利用interpretation命令将locale及其内部信息实例化传递到当前上下文。LCA算法实现过程中需要判断节点是否存在于树中,二叉搜索树的通用操作包含的isinbst函数满足所需功能,且二叉搜索树变体扩展操作is_ancestorbst函数可用于辅助验证算法功能正确性,因此我们可以直接调用建模库中的这2个函数。
在上述组件的基础上,用户只需专注于LCA算法的关键逻辑实现,根据二叉搜索树结构进行模式匹配,覆盖所有分支,即Leaf和(Node l v r),并在此基础上通过结构化归纳,调用实例化操作(isinbst函数)填充具体细节。实现中需判断节点p、q是否存在于当前树t中,若都存在,再根据当前节点值与p、q的大小关系决定递归方向,最终在值处于中间范围时返回当前节点作为LCA。依据算法的关键逻辑,可以得到如下Isabelle的最终朴素实现:
fun lca_bst::"'a::linorder treestr ⇒ 'a ⇒ 'a⇒ 'a option"
where "lca_bst Leaf _ _ = None" |
"lca_bst (Node l v r) p q =
(if isinbst (Node l v r) p ∧ isinbst (Node l v r) q then
(if v > max p q then lca_bst l p q
else if v < min p q then lca_bst r p q
else (Some v))
else None) "
规约确保语义精确,建模库复用最大化避免重复工作,以及关键逻辑实现专注算法本质,最终我们构建了LCA算法模型,图12展示自动合成LCA算法框架过程,为后续的自动化分块验证进而函数式可执行代码生成打下坚实的基础。
基于第3.2节给出的基于验证引理库的自动化分块验证策略,可在Isabelle中以较低成本验证lca_bst函数的功能正确性。在该算法的实现过程中,调用了isinbst函数用于判断节点是否存在于树中;在满足后置条件时,还需判断某节点是否为另一个节点的祖先,所需的祖先关系由建模库中已定义的is_ancestorbst函数提供。图13展示了isinbst和is_ancestorbst函数相关的验证引理集。这些引理可作为验证前提简化lca_bst功能正确性定理的证明,并提升自动化验证的成功率。
接下来,我们关注于LCA算法本身的功能正确性,即根据规约完成函数式建模后,可构造定理1确保算法的语义实现与其完全一致。
定理1. 函数lca_bst功能正确性:
theorem lca_bst_correct: "bst t $\Rightarrow $ lca_bst t p q = Some lca $\Rightarrow $ isinbst t p $\wedge $ isinbst t q $\wedge $ isinbst t lca $\wedge $ is_ancestorbst t lca p $\wedge $ is_ancestorbst t lca q $\wedge $ (∀v. (is_ancestorbst t v p $\wedge $ is_ancestorbst t v q) $\to $ is_ancestorbst t v lca)"。
定理1表明当输入满足有效的二叉搜索树t,p、q的LCA是lca,则p、q、lca节点均存在树t中,lca是p、q的祖先,并且在所有的祖先中,lca的深度最大。为了让证明更加清晰且易于机械化处理,我们使用定理拆分策略将这一综合命题拆分为3个相互独立的子目标:目标1关注节点存在性,目标2关注祖先关系本身,目标3则专注最深性条件。
对于以上3个引理的验证,在采用归纳法分解目标后,使用simp方法进行化简和分解,可将结论拆分为多个子目标,基于验证引理库使用try命令,所有的子目标都可以自动证明。定理1的功能正确性通过合并3个引理即可得证,如图14所示。
由于lca_bst函数不会改变树的属性,无需验证结构正确性。整个算法的证明过程充分依赖已验证的isinbst、is_ancestorbst及排序等辅助引理,以最小的手工参与实现了对LCA算法功能正确性的自动化证明。图15展示了LCA自动化分块验证过程。
完成lca_bst算法的形式化建模与验证后,我们得到正确的LCA算法实现,通过export_code命令可将其依赖导出为符合Haskell语法的源文件。如图16所示。该生成过程保留了原始lca_bst算法的函数式结构和抽象逻辑,确保程序在形式语义上既完全符合高层逻辑规约,又具工业级的可读性和可维护性。
动态维护Top k算法是处理海量流式数据与实时系统的核心技术之一,支撑了互联网内容推荐、实时监控、金融风控以及大规模数据分析等典型应用场景。该问题的关键在于如何在动态数据更新过程中始终高效且正确地维护并返回集合中的前k大的元素。
为了形式化刻画算法行为,采用算法规约对其操作进行描述,主要包括查询、插入与删除操作。
采用霍尔三元组严格描述查询操作的行为规约:
$ \left\{invar\;t,k> 0\right\}list := top\_ k(k,t), $
$ \{list=rev(drop(size\;t-k)(inorder\;t))\}。 $
表明若搜索树满足不变式且k>0,则执行top_k返回的结果等价于树的中序遍历逆序后的前k个元素。
对于插入操作,其规约可表述为:
$ \left\{invar\;t,k> 0\right\}\left({t}',list\right):= insert\_ top\_ k\left(x,k,t\right), $
$ \{invar\;{t}'\wedge list=rev(drop\left(size\;{t}'-k\right)(inorder\;t'))\}, $
即在搜索树不变式保持的前提下执行insert_top_k(x, k, t),得到更新后的树t'与结果list,要求t' 继续满足不变式且list与更新后的列表逆序的前k个元素保持一致。删除操作与插入操作具有相似的规约,这里不再赘述。
根据上述规约要求,算法需要频繁动态插入与删除,故在搜索树类型上选择基于红黑树的动态顺序统计树实现以保证平衡性与高效性。在建模过程中,通过导入函数式建模库中的Tree_DOST_RBT文件,可直接复用基于红黑树的动态顺序统计树定义,并将其引入到当前文件Dynamic_Maintain_Top_k中。实现过程中依赖库中已经过验证的通用操作,见图17,包括中序遍历(inorder)、树大小(size)、结构不变式(invar)、插入(insert)和删除(delete)函数,这些复用的操作建模代码共计84行,而完整的验证代码需要212行。
在算法的自定义关键逻辑函数部分,可利用中序遍历的逆序收集前k个节点,从而形成完整的Top k列表。插入与删除操作则基于查询逻辑扩展实现,具体算法实现如下:
//查询
definition Top_k :: "nat ⇒ 'a dostrbt ⇒ 'a list" where
"Top_k k t = (if k > dost_size t
then rev(dostrbt_inorder t)
else take k (rev(dostrbt_inorder t)))"
//插入
definition insert_top_k :: "'a::linorder ⇒ nat ⇒ 'a dostrbt ⇒ ('a dostrbt * 'a list)" where
"insert_top_k x k t =
(let t' = dostrbt_insert x t in (t', Top_k k t'))"
在算法验证过程中,红黑树及其变体作为搜索树类结构中较为复杂的一类,其结构性约束的正确性验证往往具有较高难度。基于本文所构建的验证引理库,上述正确性问题已通过预先证明得到系统性保障。在关键逻辑函数验证中,我们主要以插入操作的结构正确性验证为例说明,在验证引理库的基础上结合自动化分块验证策略,能够直接复用中间函数在库中已确立的正确性结果,插入操作的验证调用一次try命令即可得证,仅需2行代码,验证过程如图18所示。
借助export_code命令,可以将经过形式化建模与验证的动态维护Top k算法自动转换为可执行的Haskell程序,通过该方式生成的Haskell程序,既规避了人工编写可能引入的逻辑错误,又具备工业级的可读性与可维护性,实现从逻辑规约到可执行程序的转换。
本文提出了搜索树类结构算法的建模及自动化验证方法,通过规约精确定义算法意图,结合函数式建模库与验证引理库支持,实现算法逻辑的严谨建模与自动化分块验证,并在功能与结构正确性得到保证后,自动生成结构化且可读的函数式可执行程序。本文所提方法主要适用于2种情况:
1)二叉搜索树类结构:包括二叉搜索树(BST)、红黑树(RBT)和AVL树等典型的二叉平衡搜索树。在这些树形结构中,不仅确保了其基础操作的功能正确性,且结构不变式维护均通过了形式化规约加以刻画,可在模块化建模阶段进行复用与扩展。本文方法能为不同变种的二叉搜索树提供统一的函数式建模与验证支撑,并尤其适合于对二叉搜索树类算法进行端到端的自动化验证,最终生成可信赖的函数式可执行程序。
2)多叉搜索树类结构:以2-3树和2-3-4树为代表。此类多叉搜索树结构在节点中存储多个关键字,并允许多个子树分支能够在更高层次上实现平衡性与搜索效率的统一。本文方法通过扩展对多关键字节点及其不变式的刻画,保证了在插入、合并或分裂等操作中结构约束得以保持,从而支持多叉树结构下算法功能与结构双重正确性的自动化验证与代码生成。
需要说明的是,Trie树类结构其路径分支依赖字符序列的层级匹配而非全局有序性约束,导致树在节点访问逻辑、键比较方式及不变式定义上,与本文所提模型和通用操作建模之间存在一定差异,因此Trie结构暂未纳入本文方法的直接适用范围。鉴于本文方法在搜索树类结构底层逻辑上的通用性以及验证框架所具备的可扩展性,未来工作将针对Trie树的建模特点,扩展现有验证引理库和函数式建模策略,使其能够支持Trie树及相关变体的功能与结构验证。
在形式化验证领域,交互式定理验证是主流手段,其优势在于灵活性高、逻辑推理过程严谨,能够支持复杂系统的逐步构造性证明。然而该方法对开发者的专业知识和验证经验要求较高,构造辅助引理与组织证明结构通常需要大量人工干预,导致验证效率受限。随着自动化定理证明技术的持续发展,尤其是大语言模型在该领域的深入应用,基于生成式AI的验证方式逐渐展现出强大的扩展性与生成能力,在提高验证便捷性与自动化水平方面取得积极进展,但其在稳定性、逻辑一致性以及对复杂证明细节的把控方面仍存在一定不足。
为验证本文所提出方法的有效性,限于篇幅,本节以LCA算法为例,分别从交互式定理验证与生成式AI验证2个方面进行对比分析。为确保对比的一致性,本节统一使用完整的函数式建模输入,包括算法主体与中间辅助函数,作为方法验证的共同输入,并将验证目标统一设定为算法的正确性。
交互式定理验证方法要求用户手动完成建模、引理设计与证明组织等流程。在实际操作中,为完成验证,需用户手动展开函数定义、构造中间引理、设定归纳结构,并结合多种证明策略逐步推进。该过程虽保证了较高的形式严谨性,但对用户的逻辑表达能力与系统使用熟练度要求较高,整体验证效率不高,尤其在面对更为复杂的数据结构和多条件合取的定理时,验证成本呈指数增长。
以LCA算法为例,交互式定理验证方法主要依赖于人工驱动和策略指导,我们从算法规约出发,以函数lca_bst的功能正确性为目标。在交互式验证中,其主定理通常难以直接由自动化工具证明,因此为简化验证流程,开发者可对其进行定理拆分,将其划分为较易处理的子引理,逐步构造证明链。这里我们将其拆分为2个子引理。图19展示了交互式定理验证的过程,定理拆分成2个子目标,需构造6条自定义前置引理,验证代码总数为178行。
函数定义通常具有递归结构,涉及多分支逻辑,验证者往往需要采用启发式策略构造中间引理。整个过程中,用户不仅要设计合适的引理,还需手动调用证明策略(如induct,auto,simp,blast等),反复调试证明路径,使之在各个子目标下都能被定理证明器接受。同时,开发者还需不断尝试不同的引理组合和证明顺序,以避免陷入无法自动化证明的瓶颈。这一验证过程具有高度的不确定性,严重依赖开发者的经验积累和对定理结构的理解,导致验证过程较为复杂、时间成本较高。
面向定理证明的大语言模型在不断发展,ChatGPT-4o作为多模态大语言模型在处理复杂数学推导、逻辑问题等方面表现更加稳定,为辅助形式化验证提供了更为通用和交互友好的解决方案。DeepSeek-Prover-V2-671B采用和DeepSeek V3-0324相同的架构,采用冷启动推理数据合成与强化学习相结合的训练策略,成功将非形式化数学推理与形式化证明能力融合为一体[24]。基于上述优势,本节选取这2种模型对基于二叉搜索树的LCA算法进行功能正确性验证,旨在评估生成式AI模型在自动化定理证明中的实际应用效果。基于文献[24]中的CoT(chain-of-thought)模式,我们设计了2阶段的模型提示词。首先,在初始生成阶段,我们引导模型进行初步证明,其提示词如图20所示。其次,在交互修正阶段,我们将Isabelle控制台返回的错误信息反馈给模型,指导其迭代优化证明思路,直至生成高质量版本,此阶段的错误修复提示词如图21所示。
在对ChatGPT-4o模型进行验证实验时,我们将LCA算法的完整建模代码作为输入,向ChatGPT-4o模型发出执行补全验证功能正确性定理的命令。该命令包含对数据结构、相关函数的定义以及核心定理lca_bst_correct的陈述,促使模型自动推导并生成完整的证明过程。在接收到该输入后,模型能够快速生成结构化的完整证明脚本,其验证过程如图22左图所示,存在3处未成功验证的部分。在最初生成的版本中,模型尝试通过rule:lca_bst.induct启动归纳证明过程,但由于其自动生成的case (Leaf p q)情形中存在类型匹配错误,验证器在此处抛出具体的反例并报错。值得注意的是,ChatGPT-4o在多轮交互过程中能够识别出该错误的具体原因,并尝试修正其推理路径与归纳策略,最终生成一个结构基本完整的验证脚本。虽然在个别复杂分支处仍使用sorry占位符代替未完成的子目标,但整体验证框架的生成质量已达较高水平。
为全面评估验证框架的有效性,我们以ChatGPT-4o所生成的代码为基础,在Isabelle的交互式环境中补全剩余的证明内容,并最终成功完成了主定理lca_bst_correct的验证,完整验证过程如图22右图所示。所需构造的前置引理与交互式验证方法的大致相同,只额外增加了1条关于节点存在性前置引理的证明。ChatGPT-4o模型将整个定理作为目标不进行拆分,需要构造7条自定义前置引理,验证代码共计169行。在“生成式AI+交互式验证”工作模式中,模型输出后的人工作业环节主要包括:对模型生成的前置引理进行筛选与语义修正,对生成的证明脚本进行语法调整与证明命令重构,以及在Isabelle中进行交互验证与错误修复。实际统计结果表明,该模型生成的证明仍需大量人工参与,其中人工修改行数占最终验证成功总行数的73.37%。
通过对比图22左图与图22右图可以看出,验证是否成功的关键在于辅助函数isin与is_ancestor所涉及的一系列前置引理的充分构造与调用。该类引理往往用于描述节点在树中的存在性、祖先关系的传递性等性质,而这些性质无法通过主定理本身直接得出,但却是主定理成功归纳推理、结构拆分以及分支展开的关键逻辑支撑。由于isin和is_ancestor函数的语义本身具有递归性和结构依赖性,相关引理的构造必须对其函数定义的递归展开模式、边界行为等有深入理解,大模型未能推导出其中的依赖关系,因此必须由开发者结合函数语义精心设计和导出。此外,在证明生成失败后,定理证明器返回的反馈多以类型冲突、子目标无法匹配等非自然语言呈现。模型对这类低层反馈的解析能力有限,难以据此定位问题根源并进行针对性修复,因而在多轮迭代修正后仍无法通过验证。
同样地,我们将LCA算法的完整建模代码作为输入,向DeepSeek-Prover-V2-671B模型发出执行补全验证功能正确性定理的命令,特别选择其CoT模式以生成可解释的证明过程[24]。
根据CoT模式的推理机制,模型在处理二叉搜索树结构下非空树情形时,自动生成了6条辅助引理,生成的辅助引理如图23所示。这些引理在形式上看似紧密关联于主定理的证明目标,涵盖了节点存在性、祖先关系及其在树结构中的传递性等多个方面。但分析发现,其中lca_in_l和lca_in_r引理在模型生成的具体证明过程中完全未被调用;而is_ancestor_left、is_ancestor_right、is_ancestor_main以及is_ancestor_main2引理虽在某些分支下被模型尝试调用,但将其移除后对整体证明过程并无实质性影响。更重要的是,所有这些自动生成的引理均未能覆盖主定理所依赖的关键前提条件,亦无法替代任何经过人工构造的有效前置引理。这表明模型虽具备生成辅助定理结构的能力,却未能正确识别出有助于归纳展开和逻辑化简的核心性质。因此,这些引理在证明中表现为冗余,无法在实际验证中发挥支撑作用,在缺乏目标驱动和语义约束的情境下,其生成的引理往往缺乏逻辑深度与语义针对性。
将冗余辅助引理删去后,模型生成的验证过程如图24左图所示,验证报错的地方尝试用try命令证明,无效则用sorry占位符取代模型无法验证成功的部分,共存在3处未成功验证的部分,可以看出整体上模型已能够构建出具有清晰逻辑结构的验证框架,并较为准确地划分了定理证明所需考虑的不同情况。这一结果在一定程度上展现出大语言模型在形式化验证任务中初步具备推导能力,尤其是在结构归纳与函数分析方面能够给出合理的分支判断和策略初始化。
对模型验证过程的进一步分析发现,其在处理递归结构中的具体分支推理时,尚未形成稳定有效的策略,导致证明任务在关键位置中断,无法完成整体推导。为深入评估其验证框架的可行性,我们以该模型生成的初始验证框架为基础,在交互式定理验证环境中对核心定理lca_bst_correct进行逐步补全和修改。证明过程中构造的前置引理与交互式验证方法构造的前置引理所需一致,最终获得完整、可通过验证器检查的形式化证明过程,如图24右图所示。验证过程中会将定理拆分成3个子目标进行推理验证,需构造6条自定义前置引理,验证代码共计170行,其中人工修改行数占最终验证成功总行数的65.88%。通过对比分析,发现模型验证的主要失败原因是其概率生成机制限制了形式化推理以及在逻辑推导过程中未能主动引入一系列相关的前置引理,从而无法对复杂命题进行有效化简。lca_bst_correct定理本身是一个结构复杂及涉及多个逻辑约束交织的复合性命题,其证明不仅需要树节点存在性的前提,还需要对祖先关系的传递性等性质进行精确刻画。模型基于概率生成机制自动生成证明步骤的过程中,并未意识到这些前置引理的必要性,导致在具体展开树结构或推理祖先关系时无法完成自动推导。
交互式验证方法在形式化建模与定理证明过程中具有较高的严谨性与可信度。但验证过程高度依赖人工参与,证明脚本的编写及中间引理的构造均需研究者手动完成,整体工作量较大。在面对复杂数据结构或多层嵌套逻辑约束时,证明步骤往往呈指数级增长,人工推理负担显著加重,导致验证效率较低[25]。且不同开发者在证明策略选择和工具使用熟练程度方面存在差异,验证过程的时间成本和稳定性难以保证。
大语言模型在形式化验证任务中表现出良好的交互能力和自我修正能力,能快速构建具备清晰逻辑结构的验证框架,体现其在定理自动化推理方面的潜力。但其在处理复杂数据结构和多条件逻辑推理任务时,失败原因可归纳为3点:1)概率生成机制限制了严格形式化推理。大模型具有概率性,缺乏完备证明保证[25],主要基于语法相关性,通过概率预测生成证明,而非语义因果推理。因此在定理证明涉及不变式保持或复杂约束时,容易出现推理链条断裂或关键步骤缺失。2)缺乏辅助引理的构造能力。模型难以识别并构造必要的中间引理,无法有效组织完整证明结构,导致最终定理的证明过程不完整。3)对验证器低层反馈解析能力不足。返回的错误信息通常以类型冲突、反例信息、约束不满足等结构化形式呈现,而非自然语言描述。当前大模型对形式化证明代码这类低层反馈的语义理解与修复能力有限,难以将其有效转化为针对性的修改策略,从而在一定程度上制约了闭环优化流程的泛化能力[25]。
本文构建的函数式建模库以参数化结构模型为核心,覆盖多类搜索树结构,可降低建模负担与错误风险;同时,验证引理库系统化刻画验证通用操作语义,支撑算法验证自动化。二者契合搜索树算法的结构归纳特性,兼具广泛适用性与扩展能力,实现了算法的统一建模与低成本、高自动化验证,为搜索树类算法形式化验证提供了通用、可扩展的技术基础。
以LCA算法的功能正确性和动态维护Top k算法(插入操作)正确性为例,表2给出了各个验证方法sorry数、拆分的目标数、自定义引理条数、验证代码行数以及人工交互占比的对比。
表2中,在“人工交互”环节,本次实验共招募9名参与者,年龄均为22~26岁,5名主修计算机科学与技术、3名主修软件工程、1名主修人工智能,其中6名男性与3名女性;在经验方面,3名为初学者(约1年经验),6名为具有1~3年经验的程序员。所有参与者均使用Isabelle/HOL定理证明器,均在相同的建模函数、相同的定理目标以及相同的大模型(ChatGPT-4o、DeepSeek-Prover-V2-671B)生成框架下开展形式化证明任务。最终实验结果以9名参与者的数据平均值作为统计结果。需要指出的是,尽管所有参与者均基于相同的建模函数与验证目标开展定理证明工作,但由于证明方式(Isar或apply风格)、证明选择策略以及对引理库熟悉程度的不同,不同开发者在相同验证任务下仍可能存在效率差异。因此,“人工交互占比”指标主要用于衡量验证自动化程度提升的相对趋势,而非对个体开发效率进行绝对评价。该指标能够反映方法在减少人工干预方面的整体效果,但其结果仍受到人员背景与经验差异的影响。
具体而言,LCA算法正确性若仅依赖大模型生成,ChatGPT-4o和DeepSeek-Prover-V2-671B模型二者均无法成功完成完整验证,存在3处sorry占位符。交互式定理验证方法将定理拆分成2条子目标,需构造6条自定义引理,自定义引理验证代码97行,主定理需81行。大语言模型结合交互式验证定理时,ChatGPT-4o未对定理进行拆分,而DeepSeek-Prover-V2-671B将定理拆分成3个子目标。二者验证成功分别需要自定义构造7条和6条引理,需要103行和97行代码,主定理验证需要66行和73行代码。这些前置引理均需手工额外构造并通过交互式定理证明补全,验证过程仍存在较高的人工依赖,人工交互占比分别为73.37%、65.88%。而本文提出基于验证引理库的验证方法,将定理拆分成3条子目标,无需构造前置引理的前提下完成自动化证明,验证代码行数缩减至29,仅在目标拆分时需要人工参与,人工交互占比为17.24%。在动态维护Top k算法(插入操作)的验证中,仅依赖大模型进行验证无法成功。采用交互式定理验证方法时,需构造34条自定义引理,其中自定义引理验证代码143行,主定理26行。在“ChatGPT-4o+交互式定理验证”和“DeepSeek-Prover-V2-671B(COT)+交互式定理验证”中,模型将结构正确性拆分处理。二者验证成功都需自定义构造29条引理,验证成功分别需要129行和138行代码,主定理验证需要26行和36行代码,人工交互占比分别为67.74%、67.24%。本文所提方法将定理拆分成2条子目标,构造查询操作正确性前置引理后可完成自动化证明,主定理验证代码仅需9行,人工交互占比为36.36%。本文所提方法自动验证能力大幅提高,主要得益于验证引理库系统化地预先封装了算法依赖的关键逻辑性质与前置引理,从而避免了重复构造和逐条验证的高人工成本。
本文提出了Isabelle驱动的搜索树类算法建模及自动化验证方法。构建了涵盖多种搜索树结构的函数式建模库,统一数据结构抽象与通用操作模板。引入模块化建模策略,将数据结构定义、通用操作复用与关键逻辑实现解耦,提升建模的灵活性与可拓展性。同时,通过构建验证引理库与自动化分块验证策略,显著降低自动化验证的复杂度,增强了对复杂结构性质的支撑能力。最后通过代码生成机制,可自动生成语义一致、结构清晰的函数式可执行程序。以LCA算法和动态维护Top k算法为例,本方法较交互式验证方法代码行数和人工交互占比平均缩减88.60%、61.51%,与“生成式AI(ChatGPT-4o、DeepSeek-Prover-V2-671B)+交互式定理验证”方法相比,代码行数和人工交互占比分别平均缩减88.09%、41.76%。实现对复杂数据结构算法的系统化、高度自动化验证,并提供生成正确函数式程序的可行路径。
在未来的工作中,我们将探索所提方法在并发数据结构中的扩展,以提升其在高性能与多线程场景下的适用性。此外,我们还将深入探索生成式AI在引理自动生成和验证引理库动态扩展方面的潜力,以降低人工构造成本并提升整体验证流程的自动化水平。

参考文献 引证文献
排序方式:
1
石海鹤, 蓝孙文, 刘日明, 等. 生物序列比对动态规划算法的统一形式化构造与Isabelle验证[J]. 计算机研究与发展, 2025, 62(1): 119−131
Shi Haihe, Lan Sunwen, Liu Riming, et al. Unified formal construction and Isabelle verification of the dynamic programming algorithms for biological sequence alignment[J]. Journal of Computer Research and Development, 2025, 62(1): 119−131(in Chinese)
2
Vazou N, Seidel E L, Jhala R. LiquidHaskell: Experience with refinement types in the real world [C]//Proc of the 2014 ACM SIGPLAN Symp on Haskell. New York: ACM, 2014: 39−51
3
Xu D N. Extended static checking for Haskell[C]//Proc of the 2006 ACM SIGPLAN Workshop on Haskell. New York: ACM, 2006: 48−59
4
Hutton G. Programming in Haskell[M]. Cambridge, UK: Cambridge University Press, 2016
5
Dageförde J C, Teegen F. Structured traversal of search trees in constraint-logic object-oriented programming[C]//Proc of Int Conf on Applications of Declarative Programming and Knowledge Management. Cham: Springer, 2019: 199−214
6
Huet G, Kahn G, Paulin-Mohring C. The Coq proof assistant a tutorial[R/OL]. Rapport Technique, 1997, 178. [2025-11-02]. https://www.cs.cmu.edu/~emc/15414-s14/lecture/Tutorial.pdf
7
Nipkow T, Klein G. Concrete Semantics: with Isabelle/HOL[M]. Berlin: Springer, 2021
8
Nipkow T, Paulson L C, Wenzel M. Isabelle/HOL: A Proof Assistant for Higher-Order Logic[M/OL]. Springer Science &amp; Business Media, 2021[2025-12-10]. https://isabelle.in.tum.de/website-Isabelle2021/dist/Isabelle2021/doc/tutorial.pdf
9
左正康, 黄志鹏, 黄箐, 等. LLRB算法的函数式建模及其机械化验证[J]. 软件学报, 2024, 35(11): 5016−5039
Zuo Zhengkang, Huang Zhipeng, Huang Qing, et al. Functional modeling and mechanized verification of LLRB algorithm[J]. Journal of Software, 2024, 35(11): 5016−5039 (in Chinese)
10
左正康, 刘增鑫, 柯雨含, 等. 动态顺序统计树类结构的函数式建模及其自动化验证[J]. 软件学报, 2025, 36(8): 3531−3553
Zuo Zhengkang, Liu Zengxin, Ke Yuhan, et al. Functional modeling and automatic verification of dynamic order statistic tree structures[J]. Journal of Software, 2025, 36(8): 3531−3553 (in Chinese)
11
Nipkow T. Automatic functional correctness proofs for functional search trees[C]//Proc of the 7th Int Conf on Interactive Theorem Proving. Cham: Springer, 2016: 307−322
12
Guo Daya, Yang Dejian, Zhang Haowei, et al. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning[J]. arXiv preprint arXiv: 2501.12948, 2025
13
Dubey A, Jauhri A, Pandey A, et al. The Llama 3 herd of models[J]. arXiv preprints arXiv: 2407.21783, 2024
14
Yang An, Li Anfeng, Yang Baosong, et al. Qwen3 technical report[J]. arXiv preprint arXiv: 2505.09388, 2025
15
Dong Kefen, Ma Tengyu. Stp: Self-play LLM theorem provers with iterative conjecturing and proving[J]. arXiv preprint arXiv: 2502.00212, 2025
16
Zhang Ziyin, Xu Jiahao, He Zhiwei, et al. DeepTheorem: Advancing LLM reasoning for theorem proving through natural language and reinforcement learning[J]. arXiv preprint arXiv: 2505.23754, 2025
17
Xin Huajian, Guo Daya, Shao Zhihong, et al. DeepSeek-Prover: Advancing theorem proving in LLMs through large-scale synthetic data[J]. arXiv preprint arXiv: 2405.14333, 2024
18
Mukherjee P, Delaware B. Towards automated verification of LLM-synthesized C programs[J]. arXiv preprint arXiv: 2410.14835, 2024
19
Zhao Yongwang. Functional programming and proof[EB/OL]. 2021[2025-12-10]. https://www.yuque.com/zhaoyongwang/fpp/
20
Back R. Invariant based programming: Basic approach and teaching experiences[J]. Formal Aspects of Computing, 2009, 21(3): 227−244
21
Böhme S, Nipkow T. Sledgehammer: Judgement day[C]//Proc of the 5th Int Joint Conf of Automated Reasoning. Berlin: Springer, 2010: 107−121
22
Sherriff M, Williams L. Tool support for estimating software reliability in Haskell programs[C]// Proc of IEEE Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2004: 61−62
23
Haftmann F, Bulwahn L, Nipkow T. Code generation from Isabelle/HOL theories[EB/OL]. 2025[2025-12-10]. https://isabelle.in.tum.de/doc/codegen.pdf
24
Ren Z Z, Shao Zhihong, Song Junxiao, et al. DeepSeek-Prover-V2: Advancing formal mathematical reasoning via reinforcement learning for subgoal decomposition[J]. arXiv preprint arXiv: 2504.21801, 2025
25
文成, 马智, 胡俊杰, 等. 大语言模型赋能软件形式化验证研究综述[J/OL]. 软件学报, 2026[2026-02-20]. http: //www.jos.org.cn/1000-9825/7603.htm
Wen Cheng, Ma Zhi, Hu Junjie, et al. A review on software formal verification empowered by large language models[J/OL]. Journal of Software (in Chinese), 2026[2026-02-20]. http://www.jos.org.cn/1000-9825/7603.htm
2026年第63卷第5期
71
34
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202550899
  • 接收时间:2025-12-15
  • 首发时间:2026-11-17
  • 出版时间:2026-05-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2025-12-15
  • 修回日期:2026-03-05
基金
作者信息
    1江西师范大学人工智能学院 南昌 330022
    2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
    3语言智能研究中心(江西师范大学) 南昌 330022

通讯作者:

王昌晶()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550899
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏