14 papers · ranked by Valyu relevance
Jinwoo Kim, Shaan Nagy, Thomas Reps, Loris D’Antoni
Applications like program synthesis sometimes require proving that a property holds for all of the infinitely many programs described by a grammar—i.e., an inductively defined set of programs. Current verification frameworks overapproximate programs' behavior when sets of programs contain loops, including two…
Chongyi Yuan, Lijie Wen, Xiongliang Yan
Program correctness used to be the main concern of computer software in the early days when formal semantics was a hot topic. But, the word "correct" was afterwards replaced by reliable, robust and trustworthy etc., a tradeoff situation then. This is not because correctness is no longer important, but because people…
Wolfgang Schreiner
We present an approach to program reasoning which inserts between a program and its verification conditions an additional layer, the denotation of the program expressed in a declarative form. The program is first translated into its denotation from which subsequently the verification conditions are generated. However…
Bertrand Meyer, Weber, Reto
- Zero axioms. No properties are assumed, all are proved (from standard set theory). - A single concept covers specifications and programs. - Its definition only involves one relation and one set. - Everything proceeds from three operations: choice, composition and restriction. - These techniques suffice to derive the…
In-Ho Yi
We present a novel approach to construction of a formal semantics for a programming language. Our approach, using a parametric denotational semantics, allows the semantics to be easily extended to support new language features, and abstracted to define program analyses. We apply this in analysing a duck-typed…
Dan R. Ghica, Khulood Alyahya
Game semantics is a powerful method of semantic analysis for programming languages. It gives mathematically accurate models ("fully abstract") for a wide variety of programming languages. Game semantic models are combinatorial characterisations of all possible interactions between a term and its syntactic context.…
Jinwoo Kim, Qinheping Hu, Loris D’Antoni, Thomas Reps
This paper develops a new framework for program synthesis, called semantics-guided synthesis (SemGuS), that allows a user to provide both the syntax and the semantics for the constructs in the language. SemGuS accepts a recursively defined big-step semantics, which allows it, for example, to be used to specify and…
Dan R. Ghica, Nikos Tzevelekos
Game semantics is a trace-like denotational semantics for programming languages where the notion of legal observable behaviour of a term is defined combinatorially, by means of rules of a game between the term (the Proponent) and its context (the Opponent). In general, the richer the computational features a language…
Zheng Cheng, Jiyang Wu, Di Wang, Qinxiang Cao
A desired but challenging property of compiler verification is compositionality in the sense that the compilation correctness of a program can be deduced from that of its substructures ranging from statements, functions, and modules incrementally. Previously proposed approaches have devoted extensive effort to…
Jorge Fandinno, Vladimir Lifschitz, Patrick Lühne, Torsten Schaub
This paper continues the line of research aimed at investigating the relationship between logic programs and first-order theories. We extend the definition of program completion to programs with input and output in a subset of the input language of the ASP grounder gringo, study the relationship between stable models…
Aditya Srinivasan, Andrew D. Hilton
This paper presents GEMINI, a functional programming language for hardware description that provides features such as parametric polymorphism, recursive datatypes, higher-order functions, and type inference for higher expressivity compared to modern hardware description languages. GEMINI demonstrates the theory and…
Bertrand Meyer
- To describe a specification or a program, it suffices to define one relation and one set. - To describe the concepts of programming, concurrent as well as sequential, three elementary operations on sets and relations suffice: union, composition and restriction. - These techniques suffice to derive the axioms of…
Andrej Brodnik, Andrew Csizmadia, Gerald Futschek, Lidija Kralj + 3 more
'Violetta Lonati' 'Peter Micheuz' 'Mattia Monga'] Abstract. Computer programs are part of our daily life, we use them, we provide them with data, they support our decisions, they help us remember, they control machines, etc. Programs are made by people, but in most cases we are not their authors, so we have to decide…
Keehang Kwon
SUMMARY We propose a notion of local modules for imperative langauges. To be specific, we introduce a new implication statement of the form D ⊃ G where D is a module (i.e., a set of procedure declarations) and G is a statement. This statement tells the machine to add D temporarily to the program in the course of…