阿尔方索·卡拉乔洛·迪·福里诺与广义马尔可夫算法

《Formal Aspects of Computing》：Alfonso Caracciolo di Forino and Generalized Markov Algorithms

分析Alfonso Caracciolo di Forino在意大利形式化方法学派中的贡献，提出通用马尔可夫算法（GMAs）以定义编程语言语义和非终止计算，应用于PL/I模拟及动态系统建模。

　　

摘要

我们探讨了阿尔方索·卡拉乔洛·迪·福里诺（Alfonso Caracciolo di Forino，1925-1996）对意大利形式化方法学派发展的贡献，重点关注编程语言的形式化定义问题，包括语义和语用层面。具体而言，我们介绍了他对于能够用于为编程语言提供“声明性定义”的元语言和方法的探索。这项研究促使他提出了广义马尔可夫算法（Generalized Markov Algorithms，简称GMA），该算法在马尔可夫的常规算法基础上引入了元语言变量、可计算函数以及条件适用性。在卡拉乔洛看来，一种编程语言的定义应该是一种GMA：当给定一个字符串时，如果该字符串不是合法的程序，则GMA会将其拒绝；否则，它会将该字符串的含义表示为一个状态转换函数，从而同时处理语言的语法（包括上下文无关和上下文相关两个方面）和语义，甚至包括非终止计算。卡拉乔洛的研究团队将GMA应用于多种语言定义，对IBM维也纳研究中心用于定义PL/I的形式主义进行了完整模拟，并更广泛地应用于动态系统的定义与仿真。我们将这些贡献置于20世纪50年代末至60年代的意大利计算环境背景下进行阐释。