¿Cuál es la (s) diferencia (s) fundamental (es) entre la semántica operativa de pequeños y grandes pasos?
Me está costando comprender lo que es y la motivación para tener los dos.
semantics
operational-semantics
small-step-semantics
Simon Morgan
fuente
fuente
x = 0; while ( true ) { x = x + 1; }
?Respuestas:
La semántica de paso pequeño define un método para evaluar las expresiones un paso de cálculo a la vez. Hablando formalmente, una semántica de pequeños pasos para un lenguaje de expresiónE es una relación →:E×E llamada relación de reducción . La semántica de pequeños pasos describe lo que le sucede a una expresión en detalle. Es capaz de dar una cuenta precisa de incluso los programas sin terminación, con una cadena infinita e0→e1→e2→… . Un programa de terminación es tal que e0→e1→⋯→v v ∀e′∈E,v↛e′
En el otro extremo del espectro está la semántica denotacional . La semántica denotacional asigna un "significado" a cada expresión. Es una función desde expresiones hasta denotaciones: ( se llama dominio). El espacio de las denotaciones puede no tener relación alguna con el espacio sintáctico, por ejemplo, podría ser expresiones que se evalúen como un número y podría ser un conjunto de números como o .[[⋅]]:E→D D E D N R
La semántica de grandes pasos está en el medio. A la semántica grandes pasos en un lenguaje de expresiones y un conjunto de valores es una relación . Relaciona una expresión con su valor (posiblemente valores múltiples si el lenguaje no es determinista). A menudo, se usa un valor especial para expresiones que no terminan.E V ⇓:E×V ⊥
Entonces, ¿por qué tenemos estas tres nociones? Todas estas nociones pueden modelarse entre sí, pero el modelo agrega un grado de complejidad.
Hablando operacionalmente, la semántica de pequeños pasos corresponde a observar cada operación realizada por un intérprete para el idioma. La semántica de grandes pasos solo analiza el valor resultante. La semántica denotativa analiza una interpretación matemática que puede o no tener algo que ver con lo que sucede en una computadora.
La semántica de pequeños pasos es la más obvia. Claramente proporciona información útil sobre programas que no terminan. De manera más general, proporciona información detallada sobre el comportamiento del programa.
La semántica denotacional transforma las construcciones sintácticas en objetos matemáticos arbitrarios; puede expresar lo que quieran los científicos (puede definir la denotación de una expresión como todas las posibles cadenas de reducción de ella), pero a costa de agregar un nivel de complejidad. Se usa cuando queremos abstraer algunos detalles, como exactamente cómo se evalúa la expresión.
La semántica de grandes pasos está en el medio: abstrae los detalles de la evaluación pero conserva la naturaleza sintáctica del resultado. Por lo general, el concepto se usa cuando hay una semántica subyacente de pequeños pasos, como una forma de expresar de forma concisa " ”como“ ”. En tales construcciones, si bien los conceptos son muy diferentes (uno nos permite hablar sobre pasos de cálculo individuales y sobre programas que no terminan, el otro no), las definiciones serán muy similares, porque en este caso las reglas que definen el La semántica de grandes pasos es básicamente de la forma "if and ... y and∃(e1,…,en),e→e1→…en and ∄e′,en→e′ e⇓en e1→∗e2 en→∗v v es un valor entonces ”.e1⇓v
fuente
3
en((2+1)+1)⇓3
que supongo 'denotacional' es un fin, todo valor, pero en lo que sería ejemplo 'gran paso' no necesariamente el mapa directamente a eso? ¿La diferencia tiene algo que ver con el contexto, como(a + 1)
depender del entorno que contienea
?3