Semántica Operacional
La semántica operacional define el significado de un programa especificando cómo se ejecuta, utilizando reglas de inferencia que describen los pasos de la computación.
Definition
La semántica operacional especifica el significado de un programa como la secuencia de pasos de computación que realiza, dada por relaciones de transición definidas inductivamente sobre configuraciones de programa.
Scope
Este tema abarca la semántica operacional de paso pequeño (estructural) y de paso grande (natural), en la que las relaciones de transición o evaluación definidas por reglas de inferencia dirigidas por la sintaxis describen cómo computan los programas. Aborda las estrategias de reducción, las máquinas abstractas y cómo las definiciones operacionales apoyan las pruebas de solidez de tipos y la equivalencia de programas.
Core questions
- ¿Cómo capturan las reglas de inferencia los pasos de una computación?
- ¿Cuál es la diferencia entre la semántica de paso pequeño y la de paso grande?
- ¿Cómo apoya la semántica operacional las pruebas de solidez y equivalencia?
- ¿Cómo se relacionan las máquinas abstractas con las definiciones operacionales basadas en reglas?
Key theories
- Semántica operacional estructural
- Plotkin define la ejecución mediante reglas de transición de paso pequeño estructuradas por la sintaxis del lenguaje, proporcionando una descripción composicional y dirigida por la sintaxis de cómo computa cada construcción.
- Semántica natural (de paso grande)
- La semántica natural de Kahn relaciona un programa directamente con su resultado final a través de reglas de evaluación, abstrayendo los pasos intermedios y facilitando ciertas pruebas.
Clinical relevance
La semántica operacional es la herramienta estándar para especificar el comportamiento de lenguajes reales y para probar la corrección de compiladores e intérpretes. Su estilo basado en reglas se corresponde estrechamente con las implementaciones y subyace a la metateoría de lenguajes verificada por máquina.
History
Las ideas operacionales aparecieron en las primeras definiciones de lenguajes basadas en intérpretes. Las notas de Aarhus de Plotkin de 1981 establecieron la semántica operacional estructural como un marco riguroso y dirigido por la sintaxis, y la semántica natural de Kahn de 1987 ofreció una alternativa de paso grande. Juntas se convirtieron en el enfoque dominante para definir y razonar sobre lenguajes de programación.
Debates
- Formulaciones de paso pequeño versus paso grande
- Los semanticistas eligen entre la semántica de paso pequeño, que expone estados intermedios y maneja la no terminación y la concurrencia de forma natural, y la semántica de paso grande, que es concisa pero menos adecuada para la computación divergente o entrelazada.
Key figures
- Gordon Plotkin
- Gilles Kahn
- Glynn Winskel
- Matthias Felleisen
Related topics
Seminal works
- plotkin1981
- kahn1987
- winskel1993
Frequently asked questions
- ¿Cuál es la diferencia entre la semántica de paso pequeño y la de paso grande?
- La semántica de paso pequeño describe los pasos de computación individuales y los estados intermedios entre ellos, mientras que la semántica de paso grande relaciona un programa directamente con su valor final, ocultando los pasos intermedios.
- ¿Por qué es útil la semántica operacional para probar la solidez?
- Debido a que hace explícitos los pasos de ejecución, se empareja naturalmente con el método de progreso y preservación, que razona sobre cómo se mantiene el tipado a medida que un programa da cada paso.