Exercício 2.29. De forma sucinta, discuta as diferenças intuitivas entre os esquemas da especificação e da substituição.
Passo 1
O enunciado pede: “De forma sucinta, discuta as diferenças intuitivas entre os esquemas da especificação e da substituição.”
Informações fornecidas: nenhuma fórmula ou exemplo específico — só a solicitação de uma discussão sucinta sobre as duas abordagens.
Informações fornecidas: nenhuma fórmula ou exemplo específico — só a solicitação de uma discussão sucinta sobre as duas abordagens.
Passo 2
O que é, intuitivamente, o esquema da substituição.
- Idéia básica: raciocinar substituindo expressões pelos seus corpos ou valores, passo a passo, como se “troca-se” o nome pelo conteúdo. É um modelo operacional: mostra como a computação acontece.
- Modo de operação (exemplo simples): suponha a definição
. Para calcular pelo esquema da substituição, substitui-se por no corpo de , obtendo , e depois avalia-se essa expressão para . - Observação prática: esse esquema enfatiza a sequência de reduções (passos), é excelente para traçar execução e entender “como” o resultado aparece.
Passo 3
Detalhes e armadilhas do esquema da substituição.
- Avaliação de argumentos: o esquema pode aparecer em duas variantes intuitivas:
- aplicative-order (avaliar argumentos antes de substituir): primeiro calcula-se
e depois substitui-se por ; aqui vira e então . - normal-order (substituir sem avaliar argumentos): como no exemplo anterior, pode duplicar subexpressões.
- aplicative-order (avaliar argumentos antes de substituir): primeiro calcula-se
- Consequências práticas:
- duplicação de trabalho: se o argumento é pesado, a substituição pode copiá-lo várias vezes e reavaliá-lo;
- efeitos colaterais e estado: se o argumento tem efeito (por ex. uma atribuição ou I/O), duplicá‑lo muda o comportamento — o esquema de substituição dá uma visão enganosa quando há efeitos;
- não-terminação: em normal-order, algumas expressões podem convergir quando avaliadas por substituição diferentemente de avaliá-las primeiro — há sutilezas sobre ordem que importam.
Passo 4
O que é, intuitivamente, o esquema da especificação.
- Idéia básica: descrever o que a função/procedimento deve produzir em termos de propriedade ou equação, sem mostrar os passos de cálculo. É um modelo declarativo/abstrato: foca no “o quê”, não no “como”.
- Exemplo: para fatoriais, a especificação pode ser
isso diz qual valor
deve produzir para cada
, sem descrever redução por redução como chegar lá.
- Uso prático: útil para provar correção, comparar implementações, ou raciocinar sobre propriedades (monotonia, limites, invariantes).]
Passo 5
Comparação direta — diferenças intuitivas e consequências (resumidas).
- Perspectiva:
- substituição = operacional, mostra passos concretos da execução;
- especificação = declarativa, descreve relação entrada→saída.
- Nível de detalhe:
- substituição é de baixo nível (reduções, ordens de avaliação, cópias);
- especificação é de alto nível (equações, invariantes, propriedades).
- Quando cada uma é apropriada:
- usar substituição para traçar execução, depurar, entender desempenho e ordem de avaliação;
- usar especificação para provar que um programa faz o que se espera, para projetar ou comparar algoritmos independentemente de implementação.
- Limitações:
- substituição pode ser ineficiente e enganosa se houver efeitos colaterais ou se o argumento for pesado (duplicação);
- especificação não mostra como implementar nem dá uma contagem de passos — para questões práticas de execução precisa-se do modelo operacional.
- Conexões: implementações reais costumam usar mecanismos (ambiente, referências, memoização) que realizam a intenção da especificação evitando as ineficiências da substituição pura.
Passo 6
Exemplos curtos para fixar a intuição.
- Exemplo de comportamento idêntico e fácil: com funções puras e pequenos argumentos, ambos os esquemas dão a mesma resposta; substituição mostra o caminho, especificação diz o objetivo.
- Exemplo onde divergem na prática: considere uma função que sempre retorna
ignorando um segundo argumento não-terminante,
Chamar
(onde
nunca termina) — pelo raciocínio de especificação fica claro que o resultado deve ser
; no esquema de substituição a ordem de avaliação pode levar a não-terminação se os argumentos forem avaliados antes (aplicative-order) ou a terminar se a substituição descartar o segundo argumento (normal-order). Isso mostra por que é importante escolher o modelo adequado ao que se quer raciocinar.
Passo 7
Dica prática para a prova (resumida e amigável).
- Se o enunciado pede “trace a execução” ou “mostre os passos”, use o esquema da substituição e escreva as reduções passo a passo.
- Se o enunciado pede “o que a função calcula” ou “provar corretude”, escreva a especificação (equações/definição) e raciocine com ela.
- Se aparecerem efeitos colaterais ou performance, comente sobre duplicação e sobre como um ambiente/memoização resolveria o problema da substituição pura.
Resposta
Substituição: modelo operacional e passo a passo — troca nomes por expressões e mostra como a computação se dá (útil para traçar execução), mas pode duplicar trabalho e falhar como intuição quando há efeitos colaterais.
Especificação: modelo declarativo e abstrato — diz o que a função deve produzir (entrada→saída) sem descrever passos; é ideal para provar correção e raciocínio de alto nível, mas não mostra como implementar nem quantos passos a execução toma.
Especificação: modelo declarativo e abstrato — diz o que a função deve produzir (entrada→saída) sem descrever passos; é ideal para provar correção e raciocínio de alto nível, mas não mostra como implementar nem quantos passos a execução toma.