On the Existence of Cook Semantics

From MaRDI portal





Let \(\Sigma\) be the set of states, \(\Sigma^{\infty}\) the set of rows of states, Prog the set of program syntactic constructions for a programming language, \^{\ } the concatenation operator for rows of states, k the last element extraction operator. The Cook operational semantics [\textit{S. A. Cook}, SIAM J. Comput. 7, 70-90 (1978; Zbl 0374.68009)] is defined by attaching to every program its meaning as being a function Comp: \(\Pr og\to(\Sigma \to \Sigma^{\infty})\) satisfying Cook Equations (CE) of the following type: Comp \(<E| A>\sigma =<{\mathfrak A}A\sigma>;\) Comp \(<E| P_ i>\sigma =<\sigma>{\hat{\;}}Comp<E| S_ i>\sigma\), with \(P_ i\Leftarrow S_ i\) in E; Comp \(<E| if\) B then \(S_ 1\) else \(S_ 2>\sigma =<\sigma>{\hat{\;}}Comp <E| S_ 1>\sigma\), if \({\mathfrak B}B\sigma =tt\) and \(=<\sigma>{\hat{\;}}Comp <E| S_ 2>\sigma\), otherwise; Comp \(<E| S_ 1;S_ 2>\sigma =<\sigma>{\hat{\;}}\tau {\hat{\;}}Comp<E| S_ 2>(k\tau)\), where \(\tau =Comp<E| S_ 1>\sigma.\) The paper presents four approaches to the problem of finding out a solution (a function Comp) satisfying CE: (1) The first idea is to derive from the recursive definition of Comp in CE, an inductive one, which defines the elements of the outcome of Comp one by one. The solution is proven to be unique. It is shown why ordering \(\Sigma\) as a flat cpo set, the fixed point approach does not work. To avoid this fact, three other solutions are discussed: (2) Adding unfinished rows to \(\Sigma^{\infty}\), the new set of rows, with the prefix ordering, offer a unique fixed point solution whose restriction is the wanted CE solution function. (3) Using the continuation semantics instead of direct semantics, thus avoiding the discontinuity of the concatenation and last extraction element operators. The new defined function Comp is a unique solution to CE. (4) Following \textit{M. Nivat} [Found. Comput. Sci. III, Math. Centre Tracts 109, 1-52 (1979; Zbl 0423.68012)], the \(\Sigma^{\infty}\) can be seen as a metric topological space, the set \(D=\Pr og\to(\Sigma \to \Sigma^{\infty})\) too, and the operator \(\psi\) :\(D\to D\) has a (unique) fixed point - the function Comp - since it is shown to be a contraction between metric spaces. Remarks on the related work are made. The paper represents a useful and competent discussion within (Cook) operational semantics of programming languages.











This page was built for publication: On the Existence of Cook Semantics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3334967)