课题基金 / 基金详情

Type guided program synthesis: at the intersection of programmer tools, proof assistance and explainable AI

Type guided program synthesis: at the intersection of programmer tools, proof assistance and explainable AI
类型引导程序综合:程序员工具、证明辅助和可解释人工智能的交叉点
批准号:
2054778
负责人:
金额:
$0.0万
依托单位:
依托单位国家:
英国
项目类别:
Studentship
财政年份:
2018
资助国家:
英国
项目状态:
已结题
起止时间:
2018 至 --

项目摘要

项目成果

相似基金

相关文献

中文摘要
翻译
EPSRC的研究领域:人工智能技术、逻辑和组合学、编程语言和编译器、理论计算机科学、验证和正确性。潜在影响:程序合成是计算机科学中最古老的问题之一,在解决新出现的可解释人工智能问题方面具有巨大的潜力。编程通常涉及一些看似琐碎而乏味的小任务。程序合成将很快成为一种主流工具,用于快速解决此类问题(通过生成程序),或者让程序员知道手头有一项非常重要的任务。同时,综合可以理解为自动的证据搜索,迭代地应用形式规则,直到找到有效的证据。在人工智能中,程序合成作为一种生成程序的范例很有希望,这些程序不仅可以被机器理解,而且还可以让人类有效地推理他们的行为。上下文:起点将是一篇硕士论文,研究类型在归纳逻辑编程(ILP)环境中缩小程序假设空间的有效性,即从例子生成逻辑程序。在将程序的类型确定为合成的重要结构后,DPhil将专注于利用精化类型(和相关概念)作为规范综合问题的工具,以及让类型指导搜索。类型精化是限制属于该类型的值的命题。细化允许我们对何时编写程序有意义进行推理。由于程序/证明生成的自动化是目标,因此决定组合精化是否描述仍然与合成规范兼容的程序是重要的。为了使合成有用,它需要迅速完成。问题是,在综合过程中,对于所考虑的每个部分程序,需要确定程序中求精的可满足性。特别有希望的是可满足性模理论(SMT)求解器,因为它们被证明在受限逻辑上非常有效。影响工作方向的主要趋势是起源于ILP的元解释学习(MIL)框架和证明助手(例如CoQ)中提供的自动化。这两种方法都依赖于用户提供程序/证明和元规则/策略来通知合成器要考虑的假设类型。程序和证明之间的对应关系是众所周知的;元规则(程序允许结构的编码)和策略(证明构造中反向推理规则的集合)之间的关系尚未得到详细考虑。目的和目标:大大改进硕士论文中利用SMT求解来确定类型求精的兼容性的方法。主要的兴趣在于识别对合成有效的逻辑片段的编码。使用MIL框架作为测试基准。评估是否可以将逻辑中的综合问题编码为SMT问题确定元规则捕获的逻辑程序的强结构属性是否导致对函数程序/综合有用的证明中的结构模式的描述。研究元规则和策略的关系,分别是(逻辑)程序合成和证明助手中的证明搜索,并找到它们可以相互加强的领域。确定如何将用户对强结构属性的直觉捕获为这些框架中的高级规则,以及如何使用这些提示来限制搜索空间。合作者:Luke Ong教授(DPhil&MSc论文导师)Jeremy Gibbons教授(DPhil导师)Andrew Cropper博士(MSC论文导师)
英文摘要
EPSRC research areas: Artificial intelligence technologies, Logic and combinatorics, Programming languages and compilers, Theoretical Computer Science, Verification and correctness.Potential impact: Program synthesis, among the oldest problems in computer science, has great potential for addressing the newly arising problem of explainable AI. Programming often involves small tasks that seem trivial and tedious. Program synthesis will soon become a mainstream tool to either quickly solve such problems (by generating a program) or to let the programmer know that a non-trivial task is at hand. At the same time synthesis can be understood as automated proof search, iteratively applying formal rules until a valid proof has been found. Within AI, program synthesis has great promise as a paradigm for generating programs that are not just understood by machines, but also allow humans to effectively reason about their behaviour.Context: The starting off point will be research conducted for a master's thesis on the effectiveness of types in reducing the program hypothesis space in the setting of Inductive Logic Programming (ILP), i.e. generating logic programs from examples. Having identified typing of programs as important structure for synthesis, the DPhil will focus on leveraging refinement types (and related concepts) as a tool for the specification of synthesis problems, as well as letting types guide the search.A type refinement are propositions which restrict the values that belong to that type. Refinements allow us to reason about when composing programs makes sense. As automation of program/proof generation is the goal, deciding on whether combined refinements describe programs that are still compatible with the synthesis specification is important. For synthesis to be useful it needs to be done rapidly. The issue is that for each partial program considered, during synthesis, the satisfiability of the refinements in the program needs to be determinded. Especially promising are Satisfiability Modulo Theories (SMT) solvers, as they have proven to be very efficient on restricted logics.Major trends that influence the direction of the work are the Meta-Interpretive Learning (MIL) framework originating in ILP and the automation that is available in proof assistants (e.g. Coq.). Both approaches rely on the user to supply programs/proofs and metarules/tactics to inform the synthesizer of the kinds of hypotheses to consider. The correspondence between programs and proofs is well known; the relation between metarules, an encoding of the allowed structure of the program, and that of tactics, aggregations of rules for backward reasoning in proof construction, has yet to be considered in detail.Aims and objectives: Vastly improve on the master's thesis approach of utilizing SMT solving to decide on compatibility of type refinements. The prime interest is in identifying encoding to logic fragments that are effective for synthesis. Use the MIL framework as a testbench.Evaluate whether it is possible to encode the synthesis problem in a logic as a SMT problemDetermine whether the strong structural properties of logic programs, captured by metarules, lead to an description of structural patterns in functional programs/proofs useful in synthesis. Investigate how metarules and tactics relate, respectively (logic) program synthesis and proof search in proof assistants, and find areas where they can reinforce each other.Determine how users' intuitions for strong structural properties, such as the need for nested induction/mutually recursion (on particular variables), can be captured as high level rules in these frameworks and how such hints can be used to restrict the search space.Collaborators:Prof. Luke Ong (DPhil & MSc thesis supervisor)Prof. Jeremy Gibbons (DPhil supervisor)Dr. Andrew Cropper (MSc thesis supervisor)
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
海外基金