Imperative programs from proofs

证明中的命令式程序

基本信息

  • 批准号:
    EP/W035847/1
  • 负责人:
  • 金额:
    $ 39.68万
  • 依托单位:
  • 依托单位国家:
    英国
  • 项目类别:
    Research Grant
  • 财政年份:
    2023
  • 资助国家:
    英国
  • 起止时间:
    2023 至 无数据
  • 项目状态:
    未结题

项目摘要

The aim of this project is to develop new logical methods for extracting programs from mathematical proofs. Traditionally, such programs are extremely complicated and difficult to understand. We will improve the situation by devising novel techniques that produce programs written in a more natural language, thereby making program extraction more effective in several areas in which it is currently being applied.Background: It has long been known that there is a deep connection between logic and computation, and that mathematical proofs can be converted to computer programs. Proof interpretations are a technique for doing this. They are useful for many reasons. When implemented in a computer, they provide us with a way of synthesising programs that are correct-by-construction and therefore guaranteed to be bug free. When applied to complex mathematical proofs, they can sometimes reveal new algorithms that have not been previously discovered. There is now a large subfield of logic dedicated to using proof interpretation to extract programs from proofs.The problem: Proof interpretations are formal mathematical techniques, and as such they often result in programs that are quite different from those a human would write. These programs tend to be written in a very abstract language and can be extremely long, syntactic, and difficult to understand. This represents a drawback to using proof interpretations for practical purposes: While it is useful to have a program that we know accomplishes a particular task, it would be more useful if we were able to understand how that program worked!My main goal:This project aims to bring programs obtained using proof interpretations closer to those a human would write. The aim is to improve the current state-of-the-art so that extracted programs are written in a more natural language and therefore easier to understand.My approach: We will take one of the most powerful and widely used of all proof interpretations - K. Goedel's Dialectica interpretation - and adapt it so that it produces programs in a language that is much closer in spirit to a real-world programming language. This will involve incorporating a global state along with control flow statements such as while-loops. These are all core features of everyday languages such as C and Python but are absent from the kind of theoretical languages traditionally associated with proof interpretations. We will then further refine the new interpretation so that it is optimized for the two main applications outlined above: (i) synthesising correct-by-construction programs, and (ii) revealing interesting new algorithms from complex mathematical proofs. These two applications will each require a different approach, and the second in particular will involve a number of deep ideas from mathematical logic. We will then demonstrate our new technique by carrying out a series of case studies, targeting problem areas (i) and (ii) respectively and aimed at specific communities who would most benefit from our new method. In parallel, we will explore generalisations of our new method so that it could potentially incorporate further interesting structures from programming.The project will require us to bring together ideas from both mathematical logic and the theory of programming languages, and the intended applications, which will be exemplified through our case studies, bring formal verification and pure mathematics into play. This makes the project fundamentally cross-disciplinary, and we will exploit this by organising visits to a range of relevant research groups in the UK and internationally, and by hosting a cross-disciplinary workshop towards the end of the project.
该项目的目的是开发新的逻辑方法,从数学证明中提取程序。传统上,这样的程序非常复杂,难以理解。我们将通过设计新的技术来改善这种情况,这些技术可以产生用更自然的语言编写的程序,从而使程序提取在目前正在应用的几个领域更加有效。背景:人们早就知道,逻辑和计算之间存在着深刻的联系,数学证明可以转换为计算机程序。证明解释是这样做的一种技术。它们是有用的,原因有很多。当在计算机中实现时,它们为我们提供了一种合成程序的方法,这些程序通过构造是正确的,因此保证没有错误。当应用于复杂的数学证明时,它们有时可以揭示以前没有发现的新算法。现在有一个很大的逻辑子领域致力于使用证明解释从证明中提取程序。问题:证明解释是形式化的数学技术,因此它们经常导致程序与人类编写的程序完全不同。这些程序往往是用一种非常抽象的语言编写的,可能非常长,语法和难以理解。这代表了将证明解释用于实际目的的一个缺点:虽然有一个我们知道可以完成特定任务的程序是有用的,但如果我们能够理解该程序是如何工作的,那就更有用了!我的主要目标:这个项目旨在使使用证明解释获得的程序更接近人类编写的程序。我们的目标是改进当前的最先进的技术,使提取的程序用更自然的语言编写,因此更容易理解。我的方法:我们将采取所有证明解释中最强大和最广泛使用的一个- K。Goedel的Dialectica解释-并对其进行调整,使其在精神上更接近真实世界的编程语言的语言中产生程序。这将涉及将全局状态沿着与控制流语句(如while-loops)合并。这些都是C和Python等日常语言的核心特征,但传统上与证明解释相关的理论语言中却没有这些特征。然后,我们将进一步完善新的解释,使其针对上述两个主要应用进行优化:(i)合成正确的构造程序,以及(ii)从复杂的数学证明中揭示有趣的新算法。这两种应用都需要不同的方法,特别是第二种应用将涉及许多来自数理逻辑的深刻思想。然后,我们将通过开展一系列案例研究来展示我们的新技术,分别针对问题领域(i)和(ii),并针对最能从我们的新方法中受益的特定社区。与此同时,我们将探索我们的新方法的推广,以便它可以潜在地包含来自编程的更多有趣的结构。该项目将要求我们将数理逻辑和编程语言理论的想法结合在一起,并将通过我们的案例研究来举例说明预期的应用,将形式验证和纯数学发挥作用。这使得该项目从根本上跨学科,我们将通过组织访问英国和国际上的一系列相关研究小组,并在项目结束时举办跨学科研讨会来利用这一点。

项目成果

期刊论文数量(1)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Proofs as stateful programs: A first-order logic with abstract Hoare triples, and an interpretation into an imperative language
作为有状态程序的证明:具有抽象霍尔三元组的一阶逻辑,以及对命令式语言的解释
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Thomas Powell其他文献

Early Prosthetic Valve Malfunction Leading to Cardiogenic Shock and Emergency Redo Mitral Valve Replacement.
早期人工瓣膜故障导致心源性休克和紧急重做二尖瓣置换术。
Computational interpretations of classical reasoning: From the epsilon calculus to stateful programs
经典推理的计算解释:从 epsilon 演算到有状态程序
108: Calcemic Uremic Arteriolopathy -Wide Excision is a Promising Curative Approach: Case Report and Literature Review
  • DOI:
    10.1053/j.ajkd.2008.02.116
  • 发表时间:
    2008-04-01
  • 期刊:
  • 影响因子:
  • 作者:
    Deepak Jasuja;Thomas Powell;Alice Rocke;Donna Finegan
  • 通讯作者:
    Donna Finegan
On bar recursive interpretations of analysis
On bar 分析的递归解释
  • DOI:
  • 发表时间:
    2013
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Thomas Powell
  • 通讯作者:
    Thomas Powell
Gödel’s functional interpretation and the concept of learning
哥德尔的功能解释和学习的概念
  • DOI:
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Thomas Powell
  • 通讯作者:
    Thomas Powell

Thomas Powell的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Thomas Powell', 18)}}的其他基金

Type 1 - The Dynamic Watershed and Coastal Ocean: Predicting Their Biogeochemical Linkages and Variability over Decadal Time Scales
类型 1 - 动态流域和沿海海洋:预测十年时间尺度上的生物地球化学联系和变化
  • 批准号:
    1049222
  • 财政年份:
    2011
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Collaborative Research: Estimating Ecosystem Model Uncertainties in Pan-Regional Syntheses and Climate Change Impacts on Coastal Domains of the North Pacific Ocean
合作研究:估计泛区域综合中的生态系统模型不确定性和气候变化对北太平洋沿海地区的影响
  • 批准号:
    0816241
  • 财政年份:
    2008
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Collaborative: US-GLOBEC NEP Phase IIIa-CCS: Effects of Meso- and Basin-scale Variability on Zooplankton Populations in the CCS using Data-Assimilative, Physical/Ecosystem Models
合作:US-GLOBEC NEP IIIa-CCS 阶段:使用数据同化、物理/生态系统模型观察中观和盆地尺度变异对 CCS 中浮游动物种群的影响
  • 批准号:
    0435574
  • 财政年份:
    2005
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Collaborative Research: WinDSSOcK: Winter Distribution and Success of Southern Ocean Krill
合作研究:WinDSSOcK:南大洋磷虾的冬季分布和成功
  • 批准号:
    9910093
  • 财政年份:
    2000
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant
GLOBEC Collaborative Research: Effects of Seasonal and Interannual Variability of Zooplankton Populations in the California Current System Using Coupled Biophysical Models
GLOBEC 合作研究:使用耦合生物物理模型研究加州海流系统中浮游动物种群的季节和年际变化的影响
  • 批准号:
    0002893
  • 财政年份:
    2000
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Northest Pacific U.S GLOBEC Coordinating Office
东北太平洋美国 GLOBEC 协调办公室
  • 批准号:
    9730412
  • 财政年份:
    1998
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant
Linked Biophysical Modelling in the California Current System: The Influence of Circulation and Behavior on Prominent Mesozooplankton Species
加州海流系统中的相关生物物理模型:循环和行为对重要中生浮游生物物种的影响
  • 批准号:
    9618173
  • 财政年份:
    1997
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant
Coordinating U.S. Globec: The Scientific Steering Committee
协调美国 Globec:科学指导委员会
  • 批准号:
    9523476
  • 财政年份:
    1995
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant
The U.S. GLOBEC Office: The Coordinating Office of the Scientific Steering Committee
美国GLOBEC办公室:科学指导委员会协调办公室
  • 批准号:
    9496223
  • 财政年份:
    1994
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant
The U.S. GLOBEC Office: The Coordinating Office of the Scientific Steering Committee
美国GLOBEC办公室:科学指导委员会协调办公室
  • 批准号:
    9209223
  • 财政年份:
    1992
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Continuing Grant

相似海外基金

I-Corps: Translation potential of learning engagement and assessment programs in multi-person virtual reality
I-Corps:多人虚拟现实中学习参与和评估项目的翻译潜力
  • 批准号:
    2417857
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
The Influence of Lifetime Occupational Experience on Cognitive Trajectories Among Mexican Older Adults
终生职业经历对墨西哥老年人认知轨迹的影响
  • 批准号:
    10748606
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
Alabama Agricultural and Mechanical University ALSAMP Bridge to the Doctorate: Navigating BD Scholars’ Successful Transition to STEM Graduate Programs
阿拉巴马农业机械大学 ALSAMP 通往博士学位的桥梁:引导 BD 学者成功过渡到 STEM 研究生项目
  • 批准号:
    2404955
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Planning: Pathways to Transforming Arctic Science Programs
规划:北极科学项目转型之路
  • 批准号:
    2421373
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Ownership-based Alias Analysis for Securing Unsafe Rust Programs
用于保护不安全 Rust 程序的基于所有权的别名分析
  • 批准号:
    DP240103194
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Discovery Projects
The neural underpinnings of speech and nonspeech auditory processing in autism: Implications for language
自闭症患者言语和非言语听觉处理的神经基础:对语言的影响
  • 批准号:
    10827051
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
Arlene George F32
阿琳·乔治 F32
  • 批准号:
    10722238
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
Investigating the Outcome of EMI Programs in Higher Education Context: Cases from Japan and Mongolia
调查高等教育背景下 EMI 项目的成果:日本和蒙古的案例
  • 批准号:
    24K16709
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Leveraging Machine Learning to Examine Engineering Students Self-selection in Entrepreneurship Education Programs
利用机器学习检查工科学生在创业教育项目中的自我选择
  • 批准号:
    2321175
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
Mapping Transfer into Undergraduate Engineering Programs in the Central New York State Region
纽约州中部地区本科工程项目转学计划
  • 批准号:
    2322574
  • 财政年份:
    2024
  • 资助金额:
    $ 39.68万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了