检索结果-内蒙古大学图书馆

Automated program refinement: Guide and Verify Code Large Language Model with refinement Calculus

PROCEEDINGS OF THE ACM ON programMING LANGUAGES-PACMPL 2025年第POPI期9卷 2057-2089页

作者： Cai, Yufan Hou, Zhe Sanan, David Luan, Xiaokun Lin, Yun Sun, Jun Dong, Jin Song Ningbo Univ Ningbo Peoples R China Natl Univ Singapore Singapore Singapore Griffith Univ Brisbane Australia Singapore Inst Technol Singapore Singapore Peking Univ Beijing Peoples R China Shanghai Jiao Tong Univ Shanghai Peoples R China Singapore Management Univ Singapore Singapore

Recently, the rise of code-centric Large Language Models (LLMs) has reshaped the software engineering world with low-barrier tools like Copilot that can easily generate code. However, there is no correctness guarantee for the code generated by LLMs, which suffer from the hallucination problem, and their output is fraught with risks. Besides, the end-to-end process from specification to code through LLMs is a non-transparent and uncontrolled black box. This opacity makes it difficult for users to understand and trust the generated code. Addressing these challenges is both necessary and critical. In contrast, program refinement transforms high-level specification statements into executable code while preserving correctness. Traditional tools for program refinement are primarily designed for formal methods experts and lack automation and extensibility. We apply program refinement to guide LLM and validate the LLM-generated code while transforming refinement into a more accessible and flexible framework. To initiate this vision, we propose Refine4LLM, an approach that aims to: (1) Formally refine the specifications, (2) Automatically prompt and guide the LLM using refinement calculus, (3) Interact with the LLM to generate the code, (4) Verify that the generated code satisfies the constraints, thus guaranteeing its correctness, (5) Learn and build more advanced refinement laws to extend the refinement calculus. We evaluated Refine4LLM against the state-of-the-art baselines on program refinement and LLMs benchmarks. The experiment results show that Refine4LLM can efficiently generate more robust code and reduce the time for refinement and verification.

关键词： program refinement Large Language Model program Synthesis

来源：评论

学校读者我要写书评

暂无评论

Building White-Box Abstractions by program refinement

Building White-Box Abstractions by Program Refinement

引用

ACM International Symposium on New Ideas, New Paradigms, and Reflections on programming and Software (Onward)

作者： Afshari, Mehrdad Su, Zhendong Univ Calif Davis Dept Comp Sci Davis CA 95616 USA

ISBN: (纸本)9781450340762

A Abstractions make building complex systems possible. Many facilities provided by a modern programming language are directly designed to build a certain style of abstraction. Abstractions also aim to enhance code reusability, thus enhancing programmer productivity and effectiveness. Real-world software systems can grow to have a complicated hierarchy of abstractions. Often, the hierarchy grows unnecessarily deep, because the programmers have envisioned the most generic use cases for a piece of code to make it reusable. Sometimes, the abstractions used in the program are not the appropriate ones, and it would be simpler for the higher level client to circumvent such abstractions. Another problem is the impedance mismatch between different pieces of code or libraries coming from different projects that are not designed to work together. Interoperability between such libraries are often hindered by abstractions, by design, in the name of hiding implementation details and encapsulation. These problems necessitate forms of abstraction that are easy to manipulate if needed. In this paper, we describe a powerful mechanism to create white-box abstractions, that encourage flatter hierarchies of abstraction and ease of manipulation and customization when necessary: program refinement. In so doing, we rely on the basic principle that writing directly in the host programming language is as least restrictive as one can get in terms of expressiveness, and allow the programmer to reuse and customize existing code snippets to address their specific needs.

关键词： white-box abstractions program refinement syntactic manipulation reusability

来源：评论

学校读者我要写书评

暂无评论

Specification transformation method for functional program generation based on partition-recursion refinement rule

引用

INFORMATION SCIENCES 2023年 633卷 613-632页

作者： Zuo, Zhengkang Zeng, Zhicheng Su, Wei Huang, Qing Ke, Yuhan Liu, Zengxin Wang, Changjing Liang, Wei Jiangxi Normal Univ Dept Comp & Informat Engn Nanchang 330022 Peoples R China Jiangxi Vocat Coll Ind & Engn Dept Informat Engn Pingxiang 337000 Peoples R China Hunan Univ Sci & Technol Sch Comp Sci & Engn Xiangtan 411100 Peoples R China

Implementations that follow the functional programming paradigm are being used in more and more domains. As functional programming paradigm has mathematical reference transparency, refinement to functional programs contributes to improving the reliability of the transformation process and simplifying the refinement steps. However, it is a challenge to generate functional programs from specifications. Most existing transformation methods refine specifications into abstract algorithm-level programs based on loop invariants rather than functional programs. This paper proposes a novel functional program generation method based on the partition-recursion refinement rule. It establishes a novel program refinement framework based on functional theory for the first time. This is the first study to regard the whole program refinement process as a composition of abstract functions. This paper designs a recurrence-based algorithm design language (Radl+) and implements a software prototype to map Radl+ algorithms into executable Haskell programs. To prove the feasibility and efficiency of this method, this paper transforms the polynomial multiplication problem from a specification into an executable Haskell program. This case shows that compared with existing approaches, the proposed method can simplify the transformation steps and reduce the number of lines of generated code from 38 to 10.

关键词： Functional program Specification transformation Partition-recursion rule program refinement Formal methods

来源：评论

学校读者我要写书评

暂无评论

A case study of a difficult refinement: A fast dictionary for a spell-checking program

引用

INFORMATION AND SOFTWARE TECHNOLOGY 1995年第12期37卷 671-680页

作者： Andrews, DJ Ince, DC OPEN UNIV DEPT COMP SCIMILTON KEYNESBUCKSENGLAND

We present a difficult refinement of a dictionary for a spell-checker. It represents a realistic problem and shows how a calculational approach using a relation known as a coupling invariant can improve the process of refinement over the conventional posit-and-prove approach. The paper concludes with a brief discussion of the advantages of the approach we adopt. We also hope that the paper will contribute a difficult refinement to the rather sparse corpus of such case studies in the literature-especially those using the calculational approach.

关键词： refinement spell-checker correct programs data refinement program refinement

来源：评论

学校读者我要写书评

暂无评论

Structured gamma

引用

SCIENCE OF COMPUTER programMING 1998年第2-3期31卷 263-289页

作者： Fradet, P Le Metayer, D Inst Natl Rech Informat & Automat IRISA F-35042 Rennes France

The Gamma language is based on the chemical reaction metaphor which has a number of benefits with respect to parallelism and program derivation, But the original definition of Gamma does not provide any facility for data structuring or for specifying particular control strategies. We address this issue by introducing a notion of structured multiset which is a set of addresses satisfying specific relations. The relations can be seen as a form of neighborhood between the molecules of the solution;they can be used in the reaction condition of a program or transformed by the action. A type is defined by a context-free graph grammar and a structured multiset belongs to a type T if its underlying set of addresses satisfies the invariant expressed by the grammar defining T. We define a type checking algorithm that allows us to prove mechanically that a program maintains its data structure invariant. We illustrate the significance of the approach for program refinement and we describe its application to coordination. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： multiset rewriting graph grammar type checking program refinement coordination software architecture

来源：评论

学校读者我要写书评

暂无评论

Abstractions of non-interference security: probabilistic versus possibilistic

引用

FORMAL ASPECTS OF COMPUTING 2014年第1期26卷 169-194页

作者： Hoang, T. S. McIver, A. K. Meinicke, L. Morgan, C. C. Sloane, A. Susatyo, E. ETH Inst Informat Secur Zurich Switzerland Macquarie Univ Dept Comp Sydney NSW 2109 Australia UNSW Sch Comp Sci & Engn Sydney NSW Australia

The Shadow Semantics (Morgan, Math Prog Construction, vol 4014, pp 359-378, 2006;Morgan, Sci Comput program 74(8):629-653, 2009) is a possibilistic (qualitative) model for noninterference security. Subsequent work (McIver et al., Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II, 2010) presents a similar but more general quantitative model that treats probabilistic information flow. Whilst the latter provides a framework to reason about quantitative security risks, that extra detail entails a significant overhead in the verification effort needed to achieve it. Our first contribution in this paper is to study the relationship between those two models (qualitative and quantitative) in order to understand when qualitative Shadow proofs can be "promoted" to quantitative versions, i.e. in a probabilistic context. In particular we identify a subset of the Shadow's refinement theorems that, when interpreted in the quantitative model, still remain valid even in a context where a passive adversary may perform probabilistic analysis. To illustrate our technique we show how a semantic analysis together with a syntactic restriction on the protocol description, can be used so that purely qualitative reasoning can nevertheless verify probabilistic refinements for an important class of security protocols. We demonstrate the semantic analysis by implementing the Shadow semantics in Rodin, using its special-purpose refinement provers to generate (and discharge) the required proof obligations (Abrial et al., STTT 12(6):447-466, 2010). We apply the technique to some small examples based on secure multi-party computations.

关键词： Non-interference security Probabilistic non-interference program semantics program refinement

来源：评论

学校读者我要写书评

暂无评论

Refiner: A problem-solving environment for scientific simulator creation

引用

SIMULATION-TRANSACTIONS OF THE SOCIETY FOR MODELING AND SIMULATION INTERNATIONAL 2002年第11期78卷 655-680页

作者： Hunt, K Cremer, J Univ Wisconsin Lacrosse Dept Comp Sci La Crosse WI 54601 USA Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

The science and engineering disciplines rely heavily on computer simulation as a tool for solving large, complex mathematical problems. The difficulty of creating scientific simulation code presents the need for a programming environment that is able to assist the programmer in the code development process. This paper describes a development methodology and a prototype implementation of a system that provides such assistance. Refiner, a programming environment for creating scientific simulators, provides expert users with online support for the entire development process, from mathematical modeling to low-level implementation details. Refiner is based on Posit, a high-level object-oriented modeling and programming language. Mathematical models are specified, and executable programs are then developed through the successive application of semantics-preserving program transformations. Code development is recorded in the form of a refinement tree structure where each path from root to leaf encodes a series of program transformations representing a single-solution strategy.

关键词： code generation formal specification program refinement program transformation PSE scientific simulation

来源：评论

学校读者我要写书评

暂无评论

ARCHITECTURE-DIRECTED refinement

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1994年第4期20卷 239-258页

作者： ROMAN, GC WILCOX, CD Department of Computer Science Washington University Campus Box 1045 One Brookings Drive St. Louis MO 63130-4899

As critical computer systems continue to grow in complexity, the task of showing that they execute correctly becomes more difficult. For this reason, research in software engineering has turned to formal methods, i.e., rigorous approaches to demonstrating the correctness of software systems. Unfortunately, the formal methods currently used in the design of concurrent systems do not provide any mechanisms for specifying and reasoning about the mapping of software to hardware. As a result, architectural constraints, even though they play an important role in the design process, are left out of the formal framework. In this paper, we show how to state architectural constraints in a formal notation, how to prove that programs are allocated correctly to the underlying architecture, and how to factor architectural considerations into a program derivation process which uses a mixture of specification and program refinements. The approach is illustrated by the derivation of two related programs that solve the same problem but are designed to work on distinct architectures.

关键词： program DERIVATION ARCHITECTURAL CONSTRAINTS SPECIFICATION refinement program refinement CONCURRENCY

来源：评论

学校读者我要写书评

暂无评论

An industrial application of modal process logic

引用

SCIENCE OF COMPUTER programMING 1997年第1-2期29卷 3-22页

作者： Bruns, G Department of Computer Science University of Edinburgh Edinburgh EH9 3JZ UK

Modal process logic is an extension of CCS that allows for more expressive specifications. We show how modal process logic was successfully applied in the development of a failure recovery protocol for an air-traffic information system now in service at Heathrow airport. Two example systems are used to show that CCS itself was not suitable for this application. (C) 1997 Published by Elsevier Science B.V.

关键词： verification program refinement process algebra CCS modal process logic fault tolerance safety-critical systems air-traffic control

来源：评论

学校读者我要写书评

暂无评论

Procedure compilation in the refinement calculus

引用

FORMAL ASPECTS OF COMPUTING 2006年第2期18卷 152-180页

作者： Lermer, K. Fidge, C. J. Queensland Univ Technol Sch Software Engn & Data Commun Brisbane Qld 4001 Australia Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld Australia

High-level language program compilation strategies can be proven correct by modelling the process as a series of refinement steps from source code to a machine-level description. We show how this can be done for programs containing recursively-defined procedures in the well-established predicate transformer semantics for refinement. To do so the formalism is extended with an abstraction of the way stack frames are created at run time for procedure parameters and variables.

关键词： program refinement program compilation procedures predicate transformers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：