PANON-1(ID:2880/pan006)Markov-pattern-directed string processing languagefor Programmazlone Algoritmi NOn Numerici 1st version of PANON - dialect based on Simple Generalized Markov Algorithms Structures: Related languages
References: in Ravello, [ed] NATO Spring School on "Automata Theory", June 1964, Academic Press, New York. view details in Ravello, [ed] NATO Spring School on "Automata Theory", June 1964, Academic Press, New York. view details in Ravello, [ed] NATO Spring School on "Automata Theory", June 1964, Academic Press, New York. view details Introduction PANON-1B is a Universal Programming Language for Symbol Manipulation (or, more exactly, for defining string transformation processes), based on a particular extension of the concept of a Markov Normal Algorithm (MNA) [1,2] The basic concepts concerning Generalized Markov Algorithm (GMA) have appeared in the report [3], where two particular extensions of the concept of a MNA, called S-GMA (Simple GMA) and CF-GMA (Conditional Functional GMA) have been discussed and assumed as a basis for two versions of the PANON (Programmazlone Algoritmi NOn Numerici) family of Programming Languages. Various other extensions appeared there as suggestions for further developments. The theoretical backgrounds and practical motivations have already been discussed in [3] as well as in the paper [4] where it has been applied to the definition of Recursive Functions and to various topics in Automata Theory. So that we shall simply remark here that PANON-IB is to be considered basically as a Universal Programming Language for Symbol Manipulation, since it includes Markov Normal Algorithms, which are notoriously equivalent to Turing Machines. Additional discussions have moreover appeared in two theses [5, 6]. In the first, a comparison is made between GMA's, lambda-calculus and LISP whereas in the second one GMA's are compared with Iron's Syntax Directed Compiler [7] and applied to the formal obtention of derivatives as well as to the simplification of rational algebraic expressions The main difference of the present version with respect to the original paper [3] is the introduction of labelled transformation rules, which were explicitly foreseen there, but considered for implementation only as a further development. A second difference is the elimination of the initial statement for reading the initial argument string and the introduction of a particular symbol to be included in the transformation rules for reading-in a character at a time in a way similar to TRAC [15] Another difference is a complete definition of particular hardware representation( instead of defining only a language) which has been particularly studied in order to make it possible to operate on any possibile object string, including these representing PANON-1B programs. The same basic ideas have occured too often in the literature, to deserve further introductory comments, except perhaps for pointing out that they appear as a very natural and basic device for defining string transformation processes, and very efficient from the point of view of the programming effort, at least for a large class of problems dealing with transformations of a single argument string, On the other hand, direct reference to the concept of a Markov Normal Algorithm or even, more formally, to Post-production systems [18] gives a theroretical basis to this approach to string manipulation processes. Unfortunately the same cannot be said from the point of view of the running time, since the language makes continuously reference to a syntactical analyser, in most cases simply for deciding that a substring does not belong to a given class, and that a substitution rule is not applicable, so that one has to try the one and so on. Among the actual Symbol Manipulations Languages, which are similarly based on the concept of MNA, although this is not usually mentioned, we can in fact cite COMIT and SNOBOL. On the other hand Formula Algol [8] seems to have adopted a substitution rule, essentially equivalent to our structural transformation rules. The same can be said of AMBIT [17], although both such systems are essentially ordinary programming languages, making no references to Markov Algorithms. Again a similarity can be noted between our transformation rules and the "operators" defined in the General Problem Solver[9] as well as with many concepts as developed in the field of Syntax Directed Compilers. And indeed our basic ideas were already laid down more than four years ago in connection with compiling problems, and a brief reference to this work has already appeared in the short paper[9] presented at the IFIP 1962 Congress in Munich. Some similarities as well as varluus differences can also be seen between our approach and Van Wijngaarden's Generalized Algol[10] as developed in particular by the De Bakker [ll], although such a comparison could be made better between a further "self-modificable" extension of Generalized Markov Algorithm, which is presently being investigated, rather than the actual concept of a fixed Generalized Markov Algorithm. A certain similarity exists also between TRAC [15] and Strachey's Macrogenerator [16] on the one hand and PANON on the other, since all those systems are based esentially on recursive substitution rules. Last, but not least, we have to mention finally the "Axiomatic of System for String Transformation" AXLE [12] recently defined by Cohen and Wegstein, since in this case rather than similarities we could speak of absolute identity. And indeed, apart from inessential terminological differences, AXLE differs from our labelled Generalized Markov Algorithm essentially because we admit the possibility of omitting the "transfer number" (our optional goto clause) understanding in such a case a transfer to the first "imperative llne" (our transformation rule) in accordance with the Markov Normal Sequencing Scheme. In the present paper we shall first give a definition of the Simple Labelled Generalized Markov Algorithm, and then we shall describe the PANON-1B language as developed so far at our Computing Center and implemented on our own-built computer, the CEP (Calcolatrice Elettronica Pisana). in [ACM] Proceedings of the ACM symposium on Symbolic and algebraic manipulation, 1966 view details in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details |