Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$26,100.00

Formal methods of programming

EF 2009-10

Résumé
I propose to continue investigating the use of predicate logic as a semantics of standard programming constructs, and to advance our understanding of the relation between logic and programming. I have developed my own programming logic in several papers and a book, and I continue to improve it. It applies to both terminating and nonterminating computation, to both sequential and parallel computation, to both stand-alone and interactive computation. It has most recently been applied to probabilistic programming, and to quantum programming. The logic includes time and space complexity. With the use of a theorem prover, it is being developed into a practical programming aid. My programming logic is also being used for deriving VLSI circuits. The circuits are neither synchronous (global clock) nor asynchronous (local feedback); instead, for timing they use the novel technique of calculated local delays. I give a formal semantics that works for both circuits and programs in order to prove that the circuits correctly implement the programs. I propose an alternative to least fixpoint semantics, called refinement semantics, that is more useful for programming. From it I derive new loop rules that are simpler and more general than the old ones. To help make logic more familiar and usable, I propose a unification of boolean algebra and number algebra. The laws of the unified algebra apply to both numbers and booleans. Calculation, which is commonly used for quantitative problems, can be used for logic problems also, including programming. The logical foundation of programming is a question of great theoretical significance in computer science. Pursuit of a technology that aids programmers to write correct and efficient programs is of considerable practical importance.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
9275-2008
Name nom
Hehner, Eric
Department département
Bahen Centre for Information Technology
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2008
Award amount
26100
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
330
Committee name en
Computing and Information Sciences - A
Committee name fr
Informatique - A
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2705
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software and development
Research subject fr
Logiciels et développement
Partie
2
Nb partie
5
Application title
Formal methods of programming
Keyword
NA
Application summary
I propose to continue investigating the use of predicate logic as a semantics of standard programming constructs, and to advance our understanding of the relation between logic and programming. I have developed my own programming logic in several papers and a book, and I continue to improve it. It applies to both terminating and nonterminating computation, to both sequential and parallel computation, to both stand-alone and interactive computation. It has most recently been applied to probabilistic programming, and to quantum programming. The logic includes time and space complexity. With the use of a theorem prover, it is being developed into a practical programming aid. My programming logic is also being used for deriving VLSI circuits. The circuits are neither synchronous (global clock) nor asynchronous (local feedback); instead, for timing they use the novel technique of calculated local delays. I give a formal semantics that works for both circuits and programs in order to prove that the circuits correctly implement the programs. I propose an alternative to least fixpoint semantics, called refinement semantics, that is more useful for programming. From it I derive new loop rules that are simpler and more general than the old ones. To help make logic more familiar and usable, I propose a unification of boolean algebra and number algebra. The laws of the unified algebra apply to both numbers and booleans. Calculation, which is commonly used for quantitative problems, can be used for logic problems also, including programming. The logical foundation of programming is a question of great theoretical significance in computer science. Pursuit of a technology that aids programmers to write correct and efficient programs is of considerable practical importance.