论文标题
反射算法的行为理论I：反射顺序算法
Behavioural Theory of Reflective Algorithms I: Reflective Sequential Algorithms
论文作者
论文摘要
我们开发了一种反射顺序算法（RSA）的行为理论，即可以修改其自身行为的顺序算法。该理论包括一组与语言无关的假设，该假设定义了RSA类，一个抽象的机器模型，以及所有RSA均由该机器模型捕获的证据。就像Gurevich的行为理论中，顺序算法RSA是顺序的，有限的平行算法，其中结合仅取决于算法，而不是输入。与顺序算法类别不同，RSA的每个状态都包含该算法的表示，从而实现语言反射。使用术语作为值保留有限的探索。反射顺序抽象状态计算机（RSASM）的模型使用扩展状态扩展了顺序ASM，其中包括该状态机器将执行的主ASM规则的可更新表示。 ASM签名和规则表示的更新是通过复杂的树代数来实现的。
We develop a behavioural theory of reflective sequential algorithms (RSAs), i.e. sequential algorithms that can modify their own behaviour. The theory comprises a set of language-independent postulates defining the class of RSAs, an abstract machine model, and the proof that all RSAs are captured by this machine model. As in Gurevich's behavioural theory for sequential algorithms RSAs are sequential-time, bounded parallel algorithms, where the bound depends on the algorithm only and not on the input. Different from the class of sequential algorithms every state of an RSA includes a representation of the algorithm in that state, thus enabling linguistic reflection. Bounded exploration is preserved using terms as values. The model of reflective sequential abstract state machines (rsASMs) extends sequential ASMs using extended states that include an updatable representation of the main ASM rule to be executed by the machine in that state. Updates to the representation of ASM signatures and rules are realised by means of a sophisticated tree algebra.
