A Programming Language for Feasible Solutions

Weijun Chen, Yuxi Fu, Huan Long · 2025

Read A Programming Language for Feasible Solutions by Weijun Chen, Yuxi Fu, Huan Long (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19176.txt.

Introduction

Weijun Chen and co-authors design a language where every program runs in feasible time in a 2025 paper. Checking that code halts fast enough is a classic hard chore in verification. Instead of checking after the fact, their language bakes the limit into its type system.

Two directions form the core claim about the language. Every program it accepts is guaranteed to finish in polynomial time. And every problem solvable in that time can be written in the language. Proving that match is far from trivial, the authors stress. A language with built-in limits could streamline how feasible software is certified.

Catalog record

CREATORWeijun Chen, Yuxi Fu, Huan Long
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19176

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Programming Language for Feasible Solutions Weijun Chen, Yuxi Fu, Huan Long Abstract Runtime efficiency and termination are crucial properties in the studies of program verification. Instead of dealing with these issues in an ad hoc manner, it would be useful to develop a robust framework in which such properties are guaranteed by design. This paper introduces a new imperative programming language whose design is grounded in a static type system that ensures the following equivalence property: All definable programs are guaranteed to run in polynomial time; Conversely, all problems solvable in polynomial time can be solved by some programs of the language. The contribution of this work is twofold. On the theoretical side, the foundational equivalence property is established, and the proof of the equivalence theorem is non-trivial. On the practical side, a programming approach is proposed that can streamline program analysis and verification for feasible computations. An interpreter for the language has been implemented, demonstrating the feasibility of the approach in practice. 1 1 institutetext: BASICS, Shanghai Jiao Tong University, Shanghai, China. 1 1 email: [email protected] , 1 1 email: [email protected] , 1 1 email: [email protected] 1 Introduction Program verification and analysis depend heavily on programming languages. From the early days of programming in assembly languages to recent experiments in applying deep learning techniques to verification and analysis [ 31 ] , different programming languages have been proposed to address the increasingly demanding concerns from industry on software correctness and safety. A lot of tools and theoretical frameworks (Hoare logic, symbolic execution, theorem prover, to name a few) [ 2 , 1 , 28 , 5 ] that have been developed in the field are based on program logics and program semantics. The fundamental barrier to program verification and analysis is the undecidability. One of the basic program properties is the termination issue, which is well-known to be undecidable. Even if a program property is decidable, it is often computationally infeasible. Exponential blowup is more a rule than an exception. Modern software systems are composed of many components with complex interconnections. Different parts of the system may well be designed at different times, in different locations, by different people using different programming languages. Most components of a software system do not require the full Turing computability. A good strategy to reduce the burden of verification is to impose strong constraints on the power of the programming language used to develop a particular component, thereby making some properties hold a priori . In many real-world cases, program executions should be feasible, meaning they can run within bounded resources, with running time being the most critical resource. If we can design a programming language that admits only feasible programs, the issue of program efficiency effectively disappears, placing us in a far better position to pursue program verification and analysis. To achieve this goal, we must first determine what constitutes practical efficiency , on which it is difficult for the industry to reach a clear consensus. Meanwhile, modeling feasible computation is also a central theme in theoretical research [ 21 ] . The thesis promoted by Cobham [ 8 ] and Edmonds [ 14 ] is widely accepted among theoretical researchers: an algorithm is considered theoretically feasible if it can be computed within polynomial time. The complexity classes \mathbf{P} (the class of the problems solvable in polynomial time) for decision problems and \mathbf{FP} for functions were introduced to capture the theoretically feasible problems. Strictly speaking, theoretical feasibility cannot fully predict a program’s practical performance, with the Coppersmith-Winograd algorithm [ 11 ] and the simplex algorithm [ 23 ] for linear programming serving as famous counterexamples. Nonetheless, the Cobham-Edmonds Thesis still provides a solid explanation for practical efficiency and has inspired extensive related research [ 10 , 9 ] . Based on this, designing a simple and elegant programming language that precisely characterizes the class \mathbf{FP} is a crucial step toward implementing our strategy. The original characterization of \mathbf{FP} is in terms of polynomial-time Turing machines that involve low-level manipulations and incur undecidability issues. A different research avenue is to design light-weight models that characterize \mathbf{FP} in a direct manner. The seminal work of Bellantoni and Cook [ 4 ] has laid down the foundation for this line of research and has inspired a wide range of subsequent developments [ 29 , 18 , 20 ] . This line of thinking has led to the implicit computational complexity (ICC) theory [ 12 ] , whose goal is to characterize complexity classes without imposing explicit restrictions on resources. Various research, such as linear logic systems [ 15 , 25 ] , bounded arithmetic [ 6 , 7 , 16 , 17 ] , and the soft lambda calculus [ 3 ] , also falls within this line of work. With the strong connection to application contexts, programming languages are well-suited to bridge theoretical foundations and practical concerns. In this light, a program for \mathbf{FP} represents both a continuation of ICC research and a further exploration of program verification. The challenge of designing such a language is twofold. Firstly, does it exist? Secondly, does such a language look natural? Studies in ICC [ 22 , 27 , 19 ] only partially affirm the first question. For the language to look natural, the loop statements are preferred over recursion. The problem now is that one has to settle for the loop statements without any bounds. Such programs may not terminate, which brings us back to square one. To design a language that is both intuitive to use and formally guarantees polynomial-time complexity is inherently challenging. This creates a trade-off, and in this paper, we aim to strike a balance between soundness and naturalness. We propose a novel programming approach based on an imperative programming language called PolyC that captures precisely the problems in \mathbf{FP} . The design of PolyC enables pre-verified efficient programming by embedding verification guarantees into the language. This contrasts to the practice in which implementation comes first and safety verification comes afterwords, often incurring significant overhead. In safety-critical scenarios such as aviation, PolyC, which guarantees termination and low time complexity, offers inherent advantages. Several programming languages and type systems have been designed to characterize complexity classes, including functional languages [ 22 ] , object-oriented languages [ 19 ] , tier-based type systems [ 27 ] , and so on. It has become a consensus that restrictions on the usage of variables in these languages is necessary. Despite sharing this common mechanism with the prior works, our design differs in some critical dimensions. 1. Our priority is to design a practical programming language for \mathbf{FP} , rather than proposing yet another model. In PolyC, termination and polynomial-time execution are guaranteed for all well-typed programs. Previous models [ 27 , 19 ] may admit non-terminating programs, necessitating termination verification techniques [ 26 , 24 ] to ensure polynomial-time termination. 2. Most previous works rely on flow analysis [ 33 ] to ensure non-interference that prohibits information flow across types. In contrast, PolyC restricts the use of variables in different program blocks. 3. We provide a deterministic static type-checker accompanied by an interpreter to validate practical feasibility. The implementation issue of the type system is

Read the complete text