Programação Funcional em Haskell

Programação Funcional em Haskell

(Parte 7 de 9)

2.5 λ-abstracoes

As funcoes embutidas no λ-calculo sao formalizadas como ja mostrado anteriormente. No entanto, deve existir uma forma de construir funcoes que nao sejam embutidas. Isto ef eito atraves de um construtor (λ). Uma λ-abstracao e um tipo particular de expressao que denota uma funcao. Por exemplo,(λx . + x 1) eu ma λ-abstracao que deve ser interpretada da seguinte forma:

λ indica que se trata de uma funcao x sobre a variavel x .q ue + x 1a diciona x ao numero 1.

Uma λ-abstracao tem sempre estes 4 (quatro) elementos: o construtor (λ), o parametro formal (uma variavel, no caso, x)op onto( .) eo corpod a funcao (+ x 1). Uma λ-abstracao pode ser comparada com as funcoes em uma linguagem de programacao imperativa. Por exemplo, a λ-abstracao anterior pode ser representada em C pelo seguinte fragmento de codigo:

int inc (x) int x; { return (x + 1) };

Deve ser observado que as funcoes em uma linguagem de programacao convencional tem de ter um nome, enquanto, no λ-calculo, as λ-abstracoes sao funcoes anonimas.

2.6 A semantica operacional do λ-calculo

As emantica operacional do λ-calculo diz respeito as regras utilizadas para converter uma λexpressao em outra. Na realidade, existem 3 (tres) regras de conversao. Antes de serem mostradas estas regras, devemos definir alguns termos que sao utilizados na aplicacao destas regras.

Uma ideia central no estudo das linguagens de programacao, da notacao matematica e da logica simbolica ea de ocorrencia livre e ocorrencia ligada (ou conectada) de uma variavel. Esta ideia, normalmente, provoca confusao em quem esta vendo o tema pela primeira vez. Assim, ele sera introduzido de forma gradual e intuitiva, utilizando exemplos ja conhecidos da Matematica. Assim, vamos considerar o somatorio:

Nesta expressao, a variavel i eu ma variavel ligada, ou seja, ela esta fortemente atrelada ao somatorio. Diz-se que ela ocorre ligada nesta expresssao. Uma das caracterısticas inerentes as variaveis ligadas e que elas podem ser renomeadas sem que o significado da expressao seja alterado. Por exemplo, o mesmo somatorio anterior pode tambem ser representado da seguinte forma, sem haver qualquer modificacao em seu significado:

De forma identica, a integral

com respeito a x, representa a mesma integral

agora relacionada a variavel t. Nat eoriad os conjuntos, oc onjunto de todos x tal que x ≥ 0eo mesmo conjunto de todos os y tal que y ≥ 0, ou seja,

Tambem a proposicao “parat odox , x+1>x” e quivalente ap roposicao “para todo y, y+1>y”,o u seja,

∀x[x +1 >x ] ≡∀ y[y +1 >y ] Vejamos agora, uma outra expressao, tambem envolvendo somatorio:

Nesta expressao, a ocorrencia da variavel j e ligada. Isto pode ser verificado pelo fato de que ela pode ser trocada por qualquer outra variavel, desde que nao seja i ou a, sem mudar em nada o significado da expressao. Por exemplo, a expressao

tem, exatamente, o mesmo significado da anterior. Em uma expressao, uma ocorrencia nao ligada de uma variavel ed ita ser “livre”.A s variaveis i, a e n ocorrem livre nesta expressao. Se uma ocorrencia de uma variavel livre for trocada, o significado da expressao tambem sera trocado. Alem disso, uma ocorrencia de uma variavel pode ser ligada em uma expressao e livre em outra. Por exemplo, a variavel i e livre em

e m n∑

mas e ligada na expressao

O local da vinculacao (binding site) de um identificador determina seu escopo,q ue ear egiao da expressao na qual o identificador ocorre ligado. Esta regiao, normamente, e indicada por alguma convencao lexica, como os parenteses, colchetes ou chaves. Ainda nesta secao, serav isto que esta regiao eo corpo da expressao.

Como visto, a troca de variaveis ligadas nao interfere no significado da expressao. No entanto, esta troca nao pode ser feita para uma variavel que ocorra livre na expressao, caso contrario a expressao muda seu significado. Por exemplo, a expressao que representa a soma dos elementos da linha i de uma matriz Am×n eos omatorio

j=1 Aij

Av ariavel j ocorre ligada nesta expressao e, neste caso, pode ser trocada por outra, por exemplo, k.

k=1 Aik cujo significado e o mesmo da expressao anterior. No entanto, observemos que a variavel j nao pode ser trocada pela variavel i. Neste caso, a expressao se tornaria o somatorio de Aii,q ue representa o somatorio dos elementos da diagonal da matriz e nao mais dos elementos da linha i, como inicialmente. Este fenomeno e conhecido como “colisao de identificadores” ed eves er evitado.

Fazendo um paralelo com as linguagens de programacao comuns, as variaveis ligadas das expressoes correspondem exatamente aos parametros formais das funcoes. Na Matematica, a funcao f(x) ≡ x2 − 3x tem x como variavel ligada e como seu parametro formal.

2.6.1 Formalizacao das ocorrencias livres ou ligadas

Apos termos visto as nocoes de ocorrencias ligada e livre, como tambem a nocao de colisao de identificadores de maneira totalmente informal, vamos agora formalizar estes conceitos.

Seja a λ-expressao (λx . + xy ) 4. Esta expressao informa que se trata de uma funcao sobre av ariavel x, onde o corpo desta funcao e( + xy ).

Av ariavel x pode ser pensada como um local onde o argumento 4 deve ser colocado. Ja para a variavel y, este mesmo raciocınio nao pode ser aplicado, uma vez que nao existe este local sinalisado pela variavel y seguida apos um λ. Isto implica que as duas variaveis (x e y) tem status distintos.

Formalmente, define-se: “uma ocorrencia de uma variavel e ligada se existir uma λ-abstracao aq uale sta variavel esteja ligada. Em caso contrario, a ocorrencia e livre.” A Figura 2.1 mostra um exemplo detalhado de variaveis livres e ligadas.

ocorrencias:ligada livre ligada

λ x . +((λ y . + y z) 7) x

Figura 2.1: Exemplos de ocorrencias livres e de ocorrencias ligadas de variaveis.

Deve ser observado que uma mesma variavel pode ter uma ocorrencia livre e outra(s) ligada(s). Por exemplo, na λ-expressao + x ((λx . + x 1) 4), a primeira ocorrencia de x e livre e a segunda e ligada ou conectada.

Podemos dizer, sendo x e y duas variaveis e θ e δ duas λ-expressoes, que:

a) x e livre em y se x = y.S e x = y,a ocorrencia de x e ligada. b) x e livre em λy . θ se (x for livre em θ)E (x = y) c) x e livre em θδ se (x for livre em θ)O U( x for livre em δ)

Exemplos

1. x ocorre livre em x,e m xy,e m λa . xy e m( λa . xy)( λx . xy). 2. x ocorre ligada em y,e m λx . xy,e m (λx . ax)( y), em λx . abbx e m( λa . xy)(λx . xy). 3. Nao existem variaveis livres nos combinadores I, K, S, ∆,Y , Θ( ver secao 2.7).

2.7 Combinadores

Uma λ-expressao que nao apresenta variaveis livres e chamada fechada ou combinador.E xistem alguns combinadores que desempenham um papel especial no estudo do λ-calculo, conforme foi afirmado na Introducao desta Apostila, onde foi feita referencia aos combinadores S, K e I,n os quais eb aseada a maquina de reducao-SK de Turner. Podemos tambem citar:

I = λx.x Identidade K = λx.λy.x Projecao S = λx.λy.λz.xz(yz)C omposicao ∆= λx.x Duplicacao Y = λf.(λy.f(y))(λy.f(y)) Usado na representacao de funcoes recursivas Θ= λa.λb.b(aab)T ambem usadon ar epresentacao de funcoes recursivas

Tabela 2.1: Resumo Uma ocorrencia de uma variavel deve ser livre ou ligada.

Definicao de ocorrencia li-vre: x ocorre livre em x x ocorre livre em (EF ) ⇔ x ocorre livre em E ou x ocorre livre em F x ocorre livre em λy . E ⇔ x e y sao variaveis distintas e x ocorre livre em E

Definicao de ocorrencia ligada: x ocorre ligada em (EF ) ⇔ x ocorre ligada em E ou x ocorre ligada em F x ocorre ligada em λy . E ⇔ (x e y saoam esma variavel e x ocorre livre em E)o u x ocorre ligada em E.

Exercıcios resolvidos

1. Identifique nas expressoes abaixo aquelas que sao, ou nao, λ-expressoes: a) a Sim, a eu ma variavel; b) 9 Sim, 9 e uma constante; c) ((λb.b)(λa.ab)N ao, os parenteses nao estao aninhados corretamente; d) (λx.)a Nao, λx. nao eu m termo; e) ((λx.λy.y)(λy.y))((λi.i)(λa.b)) Sim, porque contem apenas aplicacoes, abstracoes e variaveis.

2. Identifique nas expressoesa baixo aso correncias livres e as ligadas das variaveis a) λx.x As duas ocorrencias da variavel x sao conectadas b) (λx.λy.x)x Oultimo x ocorre livre c) (λx.λy.x)xa As duas ultimas variaveis ocorrem livres d) (x(λx.y))x Todas as variaveis ocorrem livres

Exercıcios propostos

1. Justifique porque as expressoes abaixo nao sao λ-expressoes:

2. Identifique as ocorrencias livres e as ocorrencias ligadas das variaveis nas expressoes abaixo:

3. Quais das seguintes expressoes sao combinadores?

(Parte 7 de 9)

Comentários