Elsa Carvalho 28 Universidade da Madeira Departamento de Matemática e Engenharias Programação em Lógica e Funcional (2000/01) (Actualizado em 2005/06)

Elsa Carvalho

Programação em Lógica e Funcional (2000/01)(Actualizado em 2005/06)

1Universidade da Madeira

Departamento de Matemática e Engenharias

Âmbito das definiçõesO âmbito de um nome introduzido por val é o contexto que se segue textualmente à sua definição. Ou seja o âmbito do nome apenas começa depois de terminada a definição.

O âmbito de um nome introduzido por fun é mais lato: inclui a expressão que define a função, ou seja inclui o lado direito da definição. Isto acontece para que se possam definir funções recursivas.

O âmbito de um parâmetro (definição por fun) é o da própria definição.

A redefinição de nomes é possível: um nome é redefinido quando surge uma nova definição para ele num contexto em que ele já era conhecido.

Elsa Carvalho




Âmbito das definiçõesPara definir funções mutuamente recursivas (que estão definidas em termos uma da outra) utiliza-se a palavra chave and que introduz a definição simultânea de dois ou mais nomes.

fun f x = ... g x ...

and g y = ... f y ...

Para definições val usa-se a palavra chave and como outra forma de definir tuplos.

val V1 = E1 and V2 = E2 é equivalente a val(V1, V2) = (E1, E2)

Elsa Carvalho




Definições locaisPodemos fazer definições locais a outras definições. As primeiras serão apenas conhecidas pelas segundas.

Uma das razões para a introdução de funções auxiliares locais é o facto de sabermos que elas apenas serão utilizadas naquela outra função.

Desta forma podemos definir funções locais não robustas (que não estejam definidas para todos os valores do seu domínio) pois sabemos que quando as utilizarmos apenas utilizaremos valores do seu conjunto de partida.

Elsa Carvalho




Definições locaislocal fun potenciaLocal(b, e) = if e=0 then 1 else b*potenciaLocal(b,e-1)

in fun potencia(b, e) = if e<0 then error “potencia indefinida para

expoentes negativos”

else potenciaLocal(b, e)

end

fun quadrado n = potencia(n, 2)

Esta é uma forma de definir potencia tendo como definição local potenciaLocal, cujo âmbito se restringe à definição da 1ª função.

Elsa Carvalho




Definições locaisQualquer definição que se siga (após a palavra chave end), não ‘vê’ a função local.

A construção local é mais genericamente dada por

local DL1 DL2 ... DLn

in D1 D2 ... Dm end

em que DL1, DL2, ..., DLn, D1, D2, ..., Dm são definições (val ou fun). DL1, DL2, ..., DLn são definições locais às definições D1, D2, ..., Dm, só visíveis por estas últimas.

Em relação a DL1, ..., DLn entre si a regra normal para âmbitos aplica-se: DL2 ‘vê’ DL1, etc..

Elsa Carvalho




Definições locaisAs definições efectivamente introduzidas e que são vistas por outras introduzidas após a palavra end são D1, ..., Dm.

É possível encadear definições locais, colocando, por exemplo, no lugar de DLi ou de Dj uma definição local.

Podem-se também fazer definições locais a uma expressão, de forma a simplificar expressões mais complexas. Estas terão como âmbito a expressão a definir.

Estas definições locais são feitas dando nomes a sub-expressões e introduzindo funções temporárias nessas sub-expressões.

Esta característica torna-se importante quando utilizamos várias vezes a mesma sub-expressão dentro de uma expressão.

Elsa Carvalho




Definições locaisAssim, podemos utilizar uma tal expressão numa definição de digit

fun digit d = let val n = ord d in n>=0 codeof0 andalso n<=codeof9 end

Desta forma a expressão ord é avaliada uma só vez enquanto que o valor n é usado por duas vezes na expressão que define a função.

Se não utilizássemos esta definição local, a função digit seria definida como

fun digit d = ord d>=0 codeof0 andalso ord d<=codeof9

em que temos a expressão ord d avaliada duas vezes.

Elsa Carvalho




Definições locaisDe uma forma geral

let DL1 DL2 ... DLnin E end

é uma expressão com o mesmo valor de E, mas que usa as definições tornadas locais DL1, DL2, ..., DLn.

Elsa Carvalho




ExercíciosDiga qual o âmbito de V1 e V2 em cada uma das expressões

let val V1 = E1 O âmbito de V1 é E2 e E in let val V2 = E2 O âmbito de V2 é E

in Eend

end

let val V1 = let val V2 = E2 O âmbito de V1 é E in E1 O âmbito de V2 é E1 end

in E end

Elsa Carvalho




PolimorfismoFunções polimórficas são aquelas que podem ser aplicadas a valores de diferentes tipos.Por exemplo, a função identidade e as projecções:

fun id x = xid 5 = 5id “ola” = “ola”id (1, true, size “ola”) = id (1, true, 3) = (1, true, 3)

primeiro (1, 5) = 1segundo (false, 2) = 2

Elsa Carvalho




Não é necessário fazer várias versões de uma função se a queremos aplicar a valores de diferentes tipos. Tal coisa não acontece em linguagens como o Pascal.

De forma a ser possível designar o tipo de funções como estas, irá agora ser considerada uma extensão ao sistema de tipos. Passaremos a introduzir variáveis como , e para designar tipos genéricos (polimórficos) nos quais a igualdade pode estar ou não definida e =, = e = para designar tipos genéricos nos quais está definida a igualdade.

Polimorfismo

Elsa Carvalho




PolimorfismoAssim temos

id:

primeiro: ( x ) segundo: ( x )

isto significa que id é uma função cujo parâmetro é de um qualquer tipo e cujo resultado é do mesmo tipo que o parâmetro.

O parâmetro da função segundo é um par com componentes de quaisquer tipos e respectivamente e o resultado é um valor do tipo .

Elsa Carvalho




PolimorfismoMais alguns exemplos de funções polimórficas são a função constantemente igual a 5 e a igualdade:

fun const5 x = 5 const5: int

= : (= x =) bool

Relativamente à igualdade tal como é implementada em ML surge uma pequena restrição. Não é possível comparar valores de um qualquer tipo. Há domínios onde não é possível / eficiente e/ou não faz sentido fazer comparações: não se comparam funções, por exemplo.

Elsa Carvalho




PolimorfismoVale a pena neste ponto fazer referência ao caso da sobrecarga de identificadores.

Quando um nome é utilizado para designar duas ou mais funções diferentes, espera-se que o contexto forneça a informação adicional para que o ‘type checker’ consiga inferir qual das funções está em causa.

Assim, por exemplo, as expressões como 5 + 7 e 5.5 + 7.7 envolvem o nome ‘+’ para designar duas funções totalmente distintas: a soma de inteiros e a soma de reais. Note-se porém que esta situação não é, de forma alguma, uma situação de polimorfismo.

Elsa Carvalho




PolimorfismoFalamos em polimorfismo quando está em causa uma única função que pode ser invocada com argumentos de mais do que um tipo.

Falamos em sobrecarga de identificadores quando estão em causa funções diferentes que podem ser designadas por um mesmo nome.

Ao longo das aulas assumimos um sistema de tipos que não dá lugar a casos de sobrecarga de identificadores. Por exemplo não trabalhamos com reais e portanto o problema do ‘+’ não se põe.

Elsa Carvalho




PolimorfismoConvém no entanto notar que, se por exemplo os reais fizessem parte do sistema seríamos obrigados a qualificar expressões como x + y pois esta não fornece contexto suficiente para se saber de que soma se trata. Seria necessário qualificá-la: x + y:int (é a soma de inteiros já que y fica obrigado a ser do tipo int).

Elsa Carvalho




Funções de Ordem SuperiorA programação funcional fornece um nível de abstracção mais elevado, no qual é possível englobar os conceitos de função e de valor num único conceito. A esse nível, as funções podem ser vistas elas próprias como valores.

Para que uma função possa ser usada como qualquer outro valor é necessário que se possa:

aplicar funções a funções, i.e., permitir parâmetros do tipo função. Isto não é novidade pois devido ao operador de tipos passou a fazer sentido falar em tipos como (int int) bool, que é o tipo de todas as funções com domínio (int int) e codomínio bool; o domínio é pois um conjunto de funções.

Elsa Carvalho




Funções de Ordem Superiordar funções como resultado de funções, exº: id aplicado a dobro dá como resultado dobro que é uma função.

formar tuplos tendo funções como componentes. De facto o operador de tipos x permite escrever expressões como

(id, id dobro) cujo tipo é ( ) x (int int).

Uma função é de ordem superior quando aceita argumentos funcionais e/ou quando produz resultados funcionais. Assim, id, primeiro e segundo são funções de ordem superior.

Elsa Carvalho




Funções de Ordem SuperiorO tipo de uma função de ordem superior, envolve, tipicamente, o construtor de tipos ().

Por exemplo, (int int) (int x bool) é o tipo de uma função de ordem superior que espera receber como argumento uma função do tipo int int e retornar o tuplo (int x bool).

Por outro lado bool (int int) é o tipo de uma função de ordem superior que, quando aplicada a um valor do tipo booleano, retorna uma função do tipo (int int).

Elsa Carvalho




Funções de Ordem SuperiorOutro caso é a composição de funções. Em ML é utilizado o operador infixo ° para cômpor funções.

Para qualquer argumento x temos

(f ° g) (x) = f(g x)

Assim, a composição tem como parâmetro um par de funções e como resultado a função composta:

°: ( ) x ( ) ( )

Pode-se agora cômpor funções evitando o parâmetro, e consequentemente, utilizando val em vez de fun

val seisvezes = dobro ° triplo

Elsa Carvalho




Funções de Ordem SuperiorO tipo de ° é algo complicado, mas também interessante.Primeiro podemos verificar que a composição combina um par de funções e retorna ainda uma função. Assim o seu tipo há-de ser algo do género:

((T1 T2) x (T3 T4)) (T5 T6)

No entanto nem todas as funções podem ser compostas e o tipo do resultado não é independente do tipo dos argumentos.Para que f ° g faça sentido é necessário que o tipo do resultado de g coincida com o do argumento de f. Assim T4 = T1.Além disso o tipo do resultado será o mesmo que o do resultado de f e o tipo do argumento da composição será o mesmo que o do argumento de g. Assim T6 = T2 e T5 = T3. Desta forma chegamos ao resultado apresentado acima.

Documents

Elsa Carvalho 28 Universidade da Madeira Departamento de Matemática e Engenharias Programação em Lógica e Funcional (2000/01) (Actualizado em 2005/06)