Diferencia entre semántica operacional de pequeños y grandes pasos

28

¿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.

Simon Morgan
fuente
1
El artículo de Wikipedia sobre semántica operativa parece prometedor ... hasta que uno se da cuenta de que la suma total de información en la sección "Semántica de grandes pasos" es "Esta sección requiere expansión (febrero de 2011)".
David Richerby
1
¿Cuál es tu fuente de aprendizaje? ¿Qué contiene al respecto? ¿Qué piensas? Pista: ¿cuál es la semántica de los grandes pasos x = 0; while ( true ) { x = x + 1; }?
Raphael
@Raphael Estoy leyendo Comprensión de la computación . Mi opinión es que el enfoque de pequeños pasos es reducir una expresión en subexpresiones hasta que no se pueda reducir más y luego evaluar eso. El gran paso parece ser evaluar las cosas de inmediato, pero en realidad no hay ninguna diferencia interesante entre los dos métodos, ya que ambos parecen tratar de profundizar en construcciones de nivel superior.
Simon Morgan
El gran paso consiste en profundizar desde construcciones de nivel superior mediante la evaluación de subconstrucciones y el paso pequeño al reducir una construcción más grande, nuevamente, en sus subconstrucciones.
Simon Morgan

Respuestas:

32

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ón E 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 e0e1e2 . Un programa de terminación es tal que e0e1v veE,ve

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 .[[]]:EDDEDNR

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.EV⇓:E×V

Entonces, ¿por qué tenemos estas tres nociones? Todas estas nociones pueden modelarse entre sí, pero el modelo agrega un grado de complejidad.

  • Dada una semántica de paso pequeño , puede definir una semántica de paso grande correspondiente que relacione cada expresión con su valor (o valores, si la reducción no es determinista): si existe una cadena y no pueden reducirse más. Tenga en cuenta que, en general, no puede reconstruir la semántica de pequeños pasos a partir de la semántica de grandes pasos. Por ejemplo, todas las expresiones que no terminan son indistinguibles bajo la semántica de gran paso.evee1vv
  • Dado un gran paso-semántica , se puede decir que es un pequeño paso-semántica en . Esto no es particularmente útil.⇓:E×VEV
  • Dada una semántica de paso pequeño , puede definir una semántica denotacional correspondiente donde la denotación de una expresión es el conjunto de cadenas de reducción a partir de ella. Esto satisface la definición formal, pero no es particularmente útil, porque agrega un conjunto de gastos generales teóricos a los objetos que son más fáciles de razonar al mirar directamente la sintaxis.
  • Dada una semántica denotacional , puede definir una semántica de paso pequeño agregando todas las denotaciones posibles como valores en el lenguaje. Eso requiere crear valores que no formen parte de la sintaxis que el programador puede escribir, lo que significa que algunos resultados interesantes deben indicar "para todos los programas que el programador puede escribir" en lugar de "para todos los programas". Este tampoco es muy útil.[[]]
  • Dada una semántica de gran paso , puede definir una semántica denotacional correspondiente donde el dominio es el conjunto de conjuntos de valores: . Si la semántica de gran paso es determinista (cada expresión se reduce a un solo valor), puede definir una semántica denotatoria más simple donde el dominio es el conjunto de valores.[[e]]={vev}
  • Por el contrario, dada una semántica denotacional , puede definir una semántica de gran paso . De nuevo, este es un poco inútil.[[]]E[[]]

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),ee1en and e,eneeene1e2envves un valor entonces ”.e1v

Gilles 'SO- deja de ser malvado'
fuente
También estoy aprendiendo esto, pero tengo un problema con algo que dijiste en tu respuesta que me gustaría que aclararas. Dijiste "La semántica de grandes pasos está en el medio". Sin embargo, ¿no sería realmente un pequeño paso el modelo 'medio'? Considere las expresiones: A: ((5 + 7) + 3) B: ((5 + 5) + 5) C: ((1 + 2) + 1) D: ((2 + 1) + 1) Denotacional clasificaría incluso C y D con diferentes valores (posiblemente "C" y "D"), y big-step los clasificaría a ambos como "4" y a A y B como "15" Sin embargo, los pequeños pasos te darían "(12 + 3) "y" (10 + 5) "para A y B, y" (3 + 1) "para C y D.
Timothy Swan el
@TimothySwan Suponiendo que desea definir la evaluación aritmética habitual, una semántica denotacional no distinguiría C y D. Una semántica de paso pequeño definiría una cadena de reducción como . Una semántica de gran paso sería muy similar a una semántica denotacional: vs . El en la semántica de gran paso es el de la sintaxis del lenguaje, mientras que el en la semántica denotativa es el de la metateoría, pero la distinción no es visible o importante en este simple ejemplo. ((2+1)+1)3+14((2+1)+1)3[[((2+1)+1)]]=444
Gilles 'SO- deja de ser malvado'
Entonces, cuando dijiste, 'la semántica denotacional asigna un "significado" a cada expresión ". ¿No querías decir expresiones de identificación únicas, sino algún tipo de significado independiente de la evaluación? ¿Puede proporcionar un ejemplo simple que muestre claramente la diferencia entre la semántica de grandes pasos y la denotacional? También, por favor explicar el 3en ((2+1)+1)⇓3que 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 contiene a?
Timothy Swan
@TimothySwan Mientras no haya efectos secundarios, no determinismo ni funciones, la semántica denotativa de una expresión es el valor con el que se evalúa. El no determinismo es una buena manera de ilustrar la diferencia entre big-step y denotational: la denotación de una expresión sería el conjunto de valores que puede tener: , mientras que una semántica de gran paso tendría múltiples juicios admisibles: y y ... El fue un error tipográfico. [[rand(1..n)]]={1,2,,n}rand(1..n)1rand(1..n)23
Gilles 'SO- deja de ser malvado'