Aula4 - Programação Funcional, Notas de aula de Análise de Sistemas de Engenharia

Baixe Aula4 - Programação Funcional e outras Notas de aula em PDF para Análise de Sistemas de Engenharia, somente na Docsity! INE 5363 - Programação Funcional - Transparência 47 Prof. Dr. Aldo von Wangenheim 2.4.4. Resolução de alguns problemas de redução: 1. Redução direta: (λx.x(xy))N-> N(Ny) aqui N é substituído nos dois x, pois x está livre na subespressão x(xy). 2. Redução direta também: (λx.y)N -> y 3. Menos trivial: (λx.(λy.xy)N)M -> (λy.My)N pois x está livre em (λy.xy)N -> MN 4. Exemplo simples que não termina: (λx.xx)(λx.xx) -> (λx.xx)(λx.xx) -> (λx.xx)(λx.xx) ...etc INE 5363 - Programação Funcional - Transparência 48 Prof. Dr. Aldo von Wangenheim 5. Exemplo catastrofal: (λx.xxy)(λx.xxy)-> (λx.xxy)(λx.xxy)y -> (λx.xxy)(λx.xxy)yy -> (λx.xxy)(λx.xxy)yyy -> (λx.xxy)(λx.xxy)yyyy 6. Exemplo que pode ser simples (λx.z)((λx.xxy)((λx.xxy)) -> z 7. O mesmo exemplo, quando feito de forma errada: (λx.z)((λx.xxy)(λx.xxy)) ->(λx.z)((λx.xxy)(λx.xxy)y) ->(λx.z)((λx.xxy)(λx.xxy)yy) Aqui, ao invés de reduzir o redex mais à esquerda, foi aplicado(λx.xxy) sobre (λx.xxy) INE 5363 - Programação Funcional - Transparência 51 Prof. Dr. Aldo von Wangenheim 2.5. A Semântica Denotacional do Cálculo Lambda •
Denotar (Aurélio): (do latim denotare) Significar, exprimir, simbolizar Há duas maneiras de se olhar para uma função: • como um algoritmo que irá produzir um valor, dado um argu- mento, ou • como um conjunto de pares ordenados argumento-valor.
O primeiro enfoque é dinâmico ou operacional, já que vê uma função como uma seqüência de operações no tempo.
O segundo enfoque é estático ou denotacional: a função é encarada como um conjunto fixo de associações entre argumentos e seus valores de função correspondentes. Nos capitulos anteriores vimos como uma expressão ser avaliada pel aaplicação repetida de regras de redução. Essas regras descrevem somente transformações sintáticas em expressões permitidas, sem fazer referência a o que essas fun- ções significam. O cálculo λ pode ser considerado como um sistema formal para a manipulação de símbolos sintáticos. O desenvolvimento das regras de conversão foi baseado em nos- sas intuições sobre funções abstratas e nos proveu uma semân- tica operacional para o cálculo λ. Ficou em aberto, uma definição de significado. INE 5363 - Programação Funcional - Transparência 52 Prof. Dr. Aldo von Wangenheim 2.5.1. A Função Eval O propósito da semântica denotacional de uma linguagem qual- quer é o de atribuir um valor a toda expressão nesta linguagem. Uma expressão é um objeto sintático, formado de acordo com as regras de sintaxe desta linguagem, o que não diz nada sobre o seu significado. Um valor, em contraste, é um objeto matemático abstrato , como “o número 5” ou “a função que quadra o seu argumento”. Nós podemos, por conseguinte, expressar a semântica de uma lin- guagem como uma função matemática Eval, de expressões para valores: Podemos agora escrever equações da seguinte forma: Eval[[ + 3 4 ]] = 7 Isto diz “o significado (i.é. o valor) da expressão (+ 3 4) é o valor numérico abstrato 7”. Usamos colchetes duplos em negrito para fechar o argumento a Eval para enfatizar que é um objeto sintático. Esta convenção é muito utilizada na descrição de outras semânticas denotacionais. Consideraremos a expressão (+ 3 4) como uma representação ou denotação do valor 7. • Daí o termo semântica denotacional. Expressão Valor Eval INE 5363 - Programação Funcional - Transparência 53 Prof. Dr. Aldo von Wangenheim Agora, um breve desenvovlimento informal da função Eval: • O objetivo da função é o de provêr um valor para Eval[[ E ]] para toda e qualquer expressão lambda E. • Para atingir este objetivo podemos utilizar todos os recursos da sintaxe do cálculo lambda já vistos até agora. Supponhamos, primeiramente, que E seja uma variável x. Que valor deveria Eval[[ x ]] possuir ? Como o valor de uma variável é dado pelo seu contexto circun- dante, não podemos dizer o seu valor isoladamente. Podemos solucionar este problema, dando a Eval[[ ]] um parâme- tro extra ρ, o qual representa a informação contextual de uma variável. O argumento ρ é chamado de ambiente (environment) e é uma função que mapeia nomes de variáveis para seus valores. Assim: Eval[[ x ]] ρ = ρ x A notação (ρ x), no lado direito significa “a função ρ aplicada ao argumento x”. Para tratar aplicações, usamos um raciocínio semelhante: É razoável dizer-se que o o valor de (E1 E2) deveri ser o valor de E1 aplicado ao valor de E2. Eval[[ E1 E2 ]] ρ = (Eval[[ E1 ]] ρ) (Eval[[ E2 ]] ρ) INE 5363 - Programação Funcional - Transparência 56 Prof. Dr. Aldo von Wangenheim 2.5.2. O Símbolo Uma das características mais úteis da teoria descrita nesta seção, é que ela nos permite raciocinar a respeito da terminação ou não terminação de programas. • Descrição da semântica de expressões que não atingem a forma normal: Como foi descrito antes, a redução de uma expressão pode não atingir uma forma normal. • Para descrever o valor de uma expressão dessas, incluímos o elemento , pronunciado “fundo”, no domínio dos valores de expressões, o qual é o valor de uma expressão sem uma forma normal: Eval[[ <expressão sem forma normal>]] = • possui um significado matemático perfeitamente respeitável na Teoria dos Domínios. • À semelhança do símbolo 0 (que também está para “nada”), seu uso muitas vezes nos permite escrever equações sucintas ao invés de montes de palavras obtusas. • Ao invés de dizermos “a evaluação da expressao E falha em ter- minar”, dizemos: Eval[[ E ]] = INE 5363 - Programação Funcional - Transparência 57 Prof. Dr. Aldo von Wangenheim 2.5.3. Definindo a Semântica de Funções Embutidas e Constantes Nesta seção veremos como definir o valor de Eval[[ k ]] onde k é uma constante ou função embutida. Exemplo: Qual é o valor de Eval[[ * ]] ? Certamente é uma função de dois argumentos e nós podemos definí-la dando o valor desta função quando aplicada a argumen- tos arbitrários: Eval[[ ∗ ]] a b = a x b que dá o valor do cálculo lambda * em termos da operação matemática de multiplicação x. A distinção entre ∗ e x é crucial: • ∗ é uma construção sintática do cálculo lambda. • x é uma operação matemática abstrata. No caso da multiplicação a notação matemática x difere da notação de programa ∗. No caso da adição, por exemplo, o sím- bolo + é usado em ambas. É importante notar-se a diferença. A equação anterior é, porém, uma especificação incompleta para ∗. Temos de definir o que ∗ faz para todo argumento possível, inclusive . O conjunto completo de equações ficaria então: Eval[[ ∗ ]] a b = a x b, caso a e b Eval[[ ∗ ]] b = Eval[[ ∗ ]] a = ≠ ≠ INE 5363 - Programação Funcional - Transparência 58 Prof. Dr. Aldo von Wangenheim As duas novas equações complementam a definição de ∗, especi- ficando que, se algum dos argumentos de ∗ falha em terminar, então da mesma forma o fará a aplicação de ∗. Uma outra forma, mais “inteligente” de se definir a multiplicação seria através de um operador de multiplicação #: Eval[[ # ]] a b = a x b, caso a e b e a Eval[[ # ]] b = Eval[[ # ]]
b =
Eval[[ # ]] a
=
• Estas equações implicam que # deveria primeira avaliar o seu primeiro argumento e, caso este retorne 0, retornar o valor zero, sem examinar o segundo argumento de todo. • O uso de # ao invés de ∗ poderia levar à avaliação de algumas expressões que de outra forma não terminariam. O ponto a ser observado nos exemplos acima é o de que o uso de equações “semânticas” para funções embutidas nos permite expressar variações sutis no seu comportamento, o que é muito difícil de se realizar somente através de regras de redução.
As equações semânticas para uma função ao mesmo tempo especificam o significado da função e implicam seu compor- tamento operacional (regras de redução). ≠ ≠ ≠