Semantic Structures for Higher-Order Information Flow

本研究的目的是开发一个描述和推理高阶程序的一般理论，高阶程序不仅可以对基本数据（如数值）进行操作，还可以对程序本身（也可以是高阶程序）进行操作。这些问题出现在许多不同的环境中，但它们微妙而复杂的性质意味着，如果没有强有力的理论基础，错误和低效很难识别、纠正或避免。描述这些程序的一种方法是使用数学模型，该模型将程序表示为正式游戏中的策略。这种游戏语义已被用于为各种高阶编程语言开发非常精确的模型和强大的推理工具-特别是具有命令式或可变变量的语言，这些变量可用于存储数据和程序并随后更新。然而，没有系统的方法来描述这些模型-证明它们是良好的"必须在个案的基础上进行。这个项目将研究一种新的方法来构建这种语言的模型，使用范畴理论的结构来以抽象的方式捕获计算中一个事件对另一个事件的依赖性（例如，从可变变量中阅读返回写入它的最后一段数据）。这些相对简单的结构的任何实例都可以用于构建相关语言的模型，并且它们还可以用于保证模型捕获语言的所有可观察属性。这将使寻找新模型并证明其关键属性变得更容易。通过开发一种演算来描述已经确定的语义结构，所提出的研究将产生一种新的方法来写下高阶命令式程序本身，生成用于确定两个程序何时等价（即可互换）的规则，并建议控制信息流的规则-例如，防止一个变量的更新改变存储在不同变量中的值。

The aim of this research is to develop a general theory for describing and reasoning about higher-order programs, which can operate not just on basic data (such as numerical values) but programs themselves (which may also be higher-order programs). These arise in many different settings, but their subtle and complicated nature means that errors and inefficiencies are difficult to identify and rectify or avoid, without a strong theoretical basis for doing so.One way to describe these programs uses mathematical models based on representing programs as strategies in a formal game. This game semantics'' has been used to develop very accurate models and powerful reasoning tools for a wide range of higher-order programming languages - in particular, languages with imperative or mutable variables, which can be used to store data and programs and subsequently updated. However, there is no systematic way of describing these models - proving that they are well-behaved'' must generally be done on a case-by-case basis. This project will investigate a new way of constructing models of such languages, using structures from category theory to capture the dependence of one event'' in a computation on another (for example, reading from a mutable variable returns the last piece of data written to it) in an abstract way. Any instance of these relatively simple structures can be used to construct a model of the associated language, and they can also be used to guarantee that the model captures all observable properties of the language, for example. This will make it easier to find new models and prove their key properties. By developing a calculus for describing the semantic structures which have been identified, the proposed research will yield a novel way to write down higher-order imperative programs themselves, to generate rules for determining when two programs are equivalent (i.e. interchangeable), and to suggest rules for controlling information flow - for example, preventing an update of one variable from changing the value stored in a different one.