Alfonso Caracciolo di Forino and Generalized Markov Algorithms

We explore the contributions of Alfonso Caracciolo di Forino, 1925-1996, to the creation of a school of formal methods in Italy, focusing on the problem of the formal definition of programming languages, including the semantic and pragmatic levels. In particular, we present his search for metalanguages and methods that could be used to give a “declarative definition” of a programming language. This research led him to the introduction of Generalized Markov Algorithms (GMAs), which extend Markov’s Normal Algorithms with metalinguistic variables, computable functions, and conditional applicability. For Caracciolo, a language definition was a GMA that, given a string, either rejects it if it is not a legal program or gives its meaning as a state-transforming function, thus taking care of the syntax (both context-free and context-dependent aspects) and semantics of the language, including non-terminating computations. Caracciolo’s group applied GMAs to several language definitions, to a complete simulation of the formalism used by the IBM Vienna Research Center to define PL/I, and, more generally, to the definition and simulation of dynamical systems. We contextualize these contributions in the Italian computing environment of the late 1950s and 1960s.