Diferença entre semântica operacional de pequeno e grande passo

28

Qual é a diferença fundamental entre a semântica operacional de pequeno e grande passo?

Estou tendo dificuldade para entender o que é e a motivação para ter os dois.

Simon Morgan
fonte
11
O artigo da Wikipedia sobre semântica operacional parece promissor ... até que se perceba que a soma total de informações na seção "Semântica de grandes etapas" é "Esta seção requer expansão. (Fevereiro de 2011)".
David Richerby
11
Qual é a sua fonte de aprendizado? O que ele contém sobre o assunto? O que você acha? Dica: qual é a semântica do passo grande x = 0; while ( true ) { x = x + 1; }?
Raphael
@ Rafael Estou lendo Noções básicas de computação . Meu pensamento é que a abordagem em pequenos passos é reduzir uma expressão em subexpressões até que não possa mais ser reduzida e depois avaliar isso. O grande passo parece ser sobre avaliar as coisas imediatamente, mas eu realmente não tenho nenhuma diferença interessante entre os dois métodos, pois ambos parecem ser sobre a exploração de construções de nível superior.
Simon Morgan
O grande passo consiste em analisar detalhadamente as construções de nível mais alto, avaliando as sub-construções e as pequenas etapas, reduzindo uma construção maior, novamente, em suas sub-construções.
Simon Morgan

Respostas:

32

A semântica de pequenas etapas define um método para avaliar expressões, uma etapa de computação por vez. Formalmente falando, uma semântica de pequeno passo para uma linguagem de expressão é uma relação : E × E chamada de relação de redução . A semântica de pequenas etapas descreve o que acontece com uma expressão em detalhes. É capaz de fornecer uma descrição precisa de programas não termináveis, com uma cadeia infinita e 0e 1e 2 . Um programa de encerramento é aquele que e 0e 1vE→:E×Ee0e1e2e0e1vtermina com um valor de tal modo que e 'E , v e ' . veE,ve

No outro extremo do espectro está a semântica denotacional . A semântica denotacional atribui um "significado" a cada expressão. É uma função de expressões a denotações: ( é chamado de domínio). O espaço das denotações pode não ter relação com o espaço sintático, por exemplo, podem ser expressões avaliadas para um número e pode ser um conjunto de números como ou .D E D N R[[]]:EDDEDNR

A semântica de grandes etapas está no meio. A grande passos semântica em uma linguagem de expressão e um conjunto de valores de é uma relação . Relaciona uma expressão ao seu valor (possivelmente vários valores se o idioma não for determinístico). Freqüentemente, um valor especial é usado para expressões que não terminam.V : E × V EV⇓:E×V

Então, por que temos essas três noções? Todas essas noções podem se modelar, mas o modelo adiciona um grau de complexidade.

  • Dada uma semântica de passo pequeno , você pode definir uma semântica de passo grande correspondente que relaciona cada expressão ao seu valor (ou valores, se a redução não for determinística): e v se existir uma cadeia e e 1v e v não pode reduzir ainda mais. Observe que, em geral, você não pode reconstruir a semântica de pequenas etapas a partir da semântica de grandes etapas. Por exemplo, todas as expressões que não terminam são indistinguíveis na semântica de grandes etapas.evee1vv
  • Dado um grande passo-a semântica , você pode dizer que é um pequeno-passo semântica sobre E V . Isto não é particularmente útil.⇓:E×VEV
  • Dada uma semântica de pequena etapa , é possível definir uma semântica denotacional correspondente em que a denotação de uma expressão é o conjunto de cadeias de redução que começam a partir dela. Isso satisfaz a definição formal, mas não é particularmente útil, porque adiciona uma sobrecarga teórica definida a objetos que são mais fáceis de raciocinar olhando diretamente para a sintaxe.
  • Dada uma semântica denotacional , você pode definir uma semântica de pequenas etapas adicionando todas as possíveis denotações como valores no idioma. Isso requer a criação de valores que não fazem parte da sintaxe que o programador pode escrever, o que significa que alguns resultados interessantes precisam indicar "para todos os programas que o programador pode escrever" em vez de "para todos os programas". Portanto, este também não é muito útil.[[]]
  • Dada uma semântica de passo grande , é possível definir uma semântica denotacional correspondente em que o domínio é o conjunto de conjuntos de valores: [ . Se a semântica da etapa principal for determinística (cada expressão se reduz a um único valor), você pode definir uma semântica denotacional mais simples em que o domínio é o conjunto de valores.[[e]]={vev}
  • Por outro lado, dada uma semântica denotacional , você pode definir uma semântica de grande passo E [[[]] . Novamente, este é um pouco inútil.E[[]]

Operacionalmente falando, a semântica de pequenas etapas corresponde à observação de cada operação executada por um intérprete para o idioma. A semântica de grandes etapas apenas analisa o valor resultante. A semântica denotacional analisa uma interpretação matemática que pode ou não ter algo a ver com o que acontece em um computador.

A semântica em pequenos passos é a mais óbvia. Ele fornece claramente informações úteis sobre programas que não terminam. De maneira mais geral, fornece informações detalhadas sobre o comportamento do programa.

A semântica denotacional transforma construções sintáticas em objetos matemáticos arbitrários; ele pode expressar o que os cientistas desejam (você pode definir a denotação de uma expressão para ser todas as cadeias de redução possíveis), mas com o custo de adicionar um nível de complexidade. É usado quando queremos abstrair alguns detalhes, como exatamente como a expressão é avaliada.

A semântica de grandes etapas está no meio: abstrai os detalhes da avaliação, mas mantém a natureza sintática do resultado. Normalmente, o conceito é usado quando há uma semântica subjacente em pequenos passos, como uma maneira de expressar de forma concisa “ ”Como“ e e n(e1,,en),ee1en and e,eneeen”. Em tais construções, enquanto os conceitos são muito diferentes (um permite falar sobre etapas de computação individuais e sobre programas não-termináveis, o outro não), as definições serão muito semelhantes, porque nesse caso as regras que definem o big-passo semântica são basicamente de forma “se e ... e n * v e v é um valor, em seguida, e 1v ”.e1e2envve1v

Gilles 'SO- parar de ser mau'
fonte
Também estou aprendendo isso, mas tenho um problema com algo que você disse na sua resposta que gostaria que você esclarecesse. Você disse que "a semântica de grandes etapas está no meio". No entanto, o pequeno passo não seria realmente o modelo "intermediário"? Considere as expressões: A: ((5 + 7) + 3) B: ((5 + 5) + 5) C: ((1 + 2) + 1) D: ((2 + 1) + 1) Denotacional classificaria mesmo C e D com valores diferentes (possivelmente "C" e "D"), e o grande passo os classificaria como "4" e ambos A e B como "15" No entanto, o pequeno passo daria a você "(12 3 +)" e "(10 + 5)" para a e B, e "(3 + 1)" para C e D.
Timothy Swan
@TimothySwan Supondo que você queira definir a avaliação aritmética usual, uma semântica denotacional não distingue C e D. Uma semântica de pequena etapa definiria uma cadeia de redução como . Uma semântica de grande passo seria muito semelhante a uma semântica denotacional: ( ( 2 + 1 ) + 1 ) 3 vs [((2+1)+1)3+14((2+1)+1)3 . O 4 na semântica da etapa principal é o da sintaxe da linguagem, enquanto o 4 na semântica denotacional é o da metateoria, mas a distinção não é visível ou importante neste exemplo simples. [[((2+1)+1)]]=444
Gilles 'SO- stop be evil'
Então, quando você disse, 'Semântica denotacional atribui um “significado” a cada expressão.' você não quis identificar exclusivamente as expressões, mas algum tipo de significado independente da avaliação? Você pode fornecer um exemplo simples que mostra claramente a diferença entre a grande semântica e a semântica denotacional? Além disso, por favor, explique o 3em ((2+1)+1)⇓3Eu estou supondo 'denotacional' é um fim-todo o valor, mas em que instância seria 'grande passo' não necessariamente mapear diretamente para isso? A diferença tem algo a ver com o contexto, como (a + 1)depender do ambiente que contém a?
Timothy Swan
@ TimothySwan Desde que não haja efeitos colaterais, não determinismo e nenhuma função, a semântica denotacional de uma expressão é o valor que ela avalia. O não determinismo é uma boa maneira de ilustrar a diferença entre grande passo e denotacional: a denotação de uma expressão seria o conjunto de valores que ela pode ter: , ao passo que um grande passo semântica teria várias decisões admissíveis: r um n d ( 1 .. n ) 1 e r um n d ( 1 .. n ) 2 e ... Ofoi um erro de digitação. [[rand(1..n)]]={1,2,,n}rand(1..n)1rand(1..n)23
Gilles 'SO- stop be evil'