|
Resumen:
|
[ES] La semántica denotacional es una rama de la Ciencia de la Computación dedicada a dotar de significado a los lenguajes de programación mediante el diseño de objectos matemáticos (denominados denotaciones o dominios ...[+]
[ES] La semántica denotacional es una rama de la Ciencia de la Computación dedicada a dotar de significado a los lenguajes de programación mediante el diseño de objectos matemáticos (denominados denotaciones o dominios semánticos) que describan el significado de las expresiones de dichos lenguajes. Esto proporciona un método para abstraer la definición de un lenguaje que permite establecer si una determinada implementación es correcta. Los orígenes de esta teoría se remontan a los trabajos de Strachey y Scott a principios de los años 70 [6], cuando intentaron desarrollar una teoría matemática para los lenguajes de programación de alto nivel. Así surgió el problema de buscar una categoría apropiada de objetos matemáticos para estudiar la semántica de los lenguajes de programación.
En [5], Scott propuso un cierto tipo de conjuntos parcialmente ordenados que satisfacen una condición de completitud y aproximación (en terminología moderna, un retículo completo y continuo) para modelar tipos de datos, y usar las funciones continuas respecto a la topología de Scott como modelo para las funciones computables. Esto permitió la resolución de ecuaciones semánticas propuestas por Strachey, ya que estas estructuras matemáticas permitían modelar los programas definidos recursivamente.
Sin embargo, la condición de completitud era demasiado fuerte tanto desde un punto de vista teórico como práctico, por lo que fue debilitada por la de completitud dirigida, dando lugar al concepto de dominio: un conjunto parcialmente ordenado completo respecto a conjuntos dirigidos y continuo. Estas estructuras matemáticas permiten modelar las nociones de aproximación y computación.
Además, la teoría de dominios apareció de forma independiente en otros contextos como topología, análisis y teoría de categorías (véase [3]). De este modo, muchos investigadores empezaron a trabajar en los fundamentos teóricos de estas estructuras que se han recogido en monografías tales como [3].
La idea de Scott sobre la computabilidad de un elemento de un conjunto parcialmente ordenado como el límite de una sucesión creciente de elementos ya aparecía en un trabajo antiguo de Lacombe sobre computabilidad en ciertos espacios métricos. Esto condujo al estudio de la computabilidad en espacios métricos arbitrarios mediante su embebimiento en el conjunto de puntos maximales de un conjunto parcialmente ordenado [4].
Por otro lado, el planteamiento de Scott sobre cuáles deben ser los dominios semánticos adecuados no es el único. Los espacios métricos también se han usado como dominios semánticos (véase, por ejemplo, [1]) al trabajar con procesos concurrentes y con lenguajes de procesamiento en paralelo o con características no deterministas. De este modo, los espacios métricos y los dominios han sido los principales objetos matemáticos usados como dominios semánticos.
Así, surge de modo natural la búsqueda de una estructura matemática que englobe tanto a los dominios como a los espacios métricos y que sea adecuada para el estudio de la semántica denotacional. Smyth [7] propuso los espacios casi-métricos o los espacios casi-uniformes ya que estos presentaban la ventaja de que sus preórdenes de especialización no eran triviales. Sin embargo, la teoría de completación se vuelve mucho más complicada.
Más tarde, Flagg y Kopperman [2] mejoraron la propuesta de Smyth desarrollando un marco más general para la semántica denotacional a través de los denominados espacios de continuidad, es decir, categorías enriquecidas en un cuantal.
Por tanto, como hemos visto, existe una relación muy estrecha entre la Ciencia de la Computación y algunas teorías matemáticas. Sin embargo, en la literatura no podemos encontrar un trabajo que aglutine todos estos resultados de modo uniforme que pueda servir como punto de partida para matemáticos e informáticos que quieran iniciarse en esta área.
De este modo, el principal objetivo de esta tesis de máster es revisar y ordenar, hasta cierto punto, parte del tr
[-]
[EN] Denotational semantics is a branch of Computer Science concerned with the meaning of programming languages by constructing mathematical objects (called denotations or semantical domains) that describe the meanings of ...[+]
[EN] Denotational semantics is a branch of Computer Science concerned with the meaning of programming languages by constructing mathematical objects (called denotations or semantical domains) that describe the meanings of expressions from the languages. This provides a method for abstracting the definition of a language allowing to determine whether a certain implementation is correct. The origins of this theory go back to the works of Strachey and Scott in the 70s [6]. They tried to formulate a mathematical theory of computation for high-level computer languages. Thus, the problem of searching for a convenient mathematical category for studying the semantics of programming languages appeared.
In [5] Scott proposed a certain type of partially ordered sets satisfying a certain condition of completeness and approximation (complete continuous lattices in modern terminology) for modeling the data types, and continuous functions with respect to the so-called Scott topology as a model for computable functions. This made possible to solve the semantic equations of Strachey, since this mathematical model gives meanings to recursively defined programs.
Nevertheless, the condition of completeness was too strong from a theoretical and practical point of view, so it was changed to a weaker one, directed completeness, giving rise to the domains, continuous directed complete partially ordered sets. This mathematical structure models the notion of approximation and computation.
Furthermore, the theory of domains also arose in other mathematical contexts like topology, analysis, and category theory (see [3]). This produced a big growth in the mathematical foundations of the theory that has been collected in some monographs as [3].
Scott s idea of the computability of an element of a partially ordered set as the limit of an increasing sequence of elements already appeared in Lacombe s work about computability on certain metric spaces. This leads to the study of computation in arbitrary metric spaces by embedding a metric space in the set of maximal points of a partially ordered set [4].
On the other hand, Scott s approach to denotational semantics is not the only one. Metric spaces have also been used as semantic domains (see, for example, [1]) when dealing with concurrent processes and languages with nondeterministic or parallel features. In this way, metric spaces and domains become the main semantic domains.
At this point, it is natural to look for a mathematical structure that encompasses domains and metric spaces for studying denotational semantics. Smyth [7] proposed the quasi-metric spaces or the quasi-uniform spaces since they have the advantage that their specialization preorders are not trivial. However, the completion theory is much more complicated in these spaces.
Later on, Flagg and Kopperman [2] refined Smyth s approach developing a more general framework for studying denotational semantics, the so-called continuity spaces, that is, categories enriched over a quantale.
Consequently, there is a close interaction between Computer Science and some mathematical theories. Nevertheless, we cannot find in the literature a work that collects all these results in a unified way that could help mathematicians and computer scientists start in this area.
Therefore, the main objective of this Master s Dissertation is to review, to some extent, the mathematical work related to Denotational Semantics.
BIBLIOGRAPHY
[1] J. W. de Bakker, and E. P. de Vink, Denotational models for programming languages: applications of Banach s fixed point theorem , Topology and its Applications 85 (1998), 35-52.
[2] B. Flagg, and R. Kopperman, Continuity spaces: reconciling domains and metric spaces , Theoretical Computer Science 177 (1997), 111-138.
[3] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, and D. S. Scott, Continuous lattices and domains , Cambridge University Press, 2003.
[4] J. Lawson, Computation on metric spaces via domain th
[-]
|
