Paradigmas de Linguagens Computacionais
Lista de Exercícios 2
Exercitando conceitos de linguagens computacionais

Data de Entrega: sexta, 20 de junho de 2003

Alunos: Ivanildo José de Sousa Aquino Júnior (IJSAJ)
Mozart Vasconcelos Silva(MVS)

Orientações:
1.	Esta lista deve ser feita em equipe com no máximo 2 membros. Em caso de cópia será atribuída a nota 0 (zero) a todas as listas idênticas.
2.	Para cada dia de atraso 0,5 pontos será abatido da nota final da lista.
3.	A lista deve ser entregue via e-mail para krc@cin.ufpe.br (Klaus).

1.	[0,5] Procure entender os conceitos de sintaxe concreta e sintaxe abstrata. Explique-os e faça uso de exemplos para mostrar o seu entendimento.

A sintaxe concreta define a estrutura das frases da linguagem, a ordem em que sub-frases devem ser escritas, e os símbolos terminais que as delimitam. Ela define como escrever programas sintaticamente bem formados não sendo utilizada para a descrição semântica do programa, sendo definada em termos de expressões regulares de gramáticas livres de contexto.

Exemplo de sintaxe concreta:

d + 10 * n

while b do begin n := 0;  
                 b := false 
           end

let var y: Integer  
in y := y + 1

A sintaxe abstrata de uma linguagem mostra as possíveis expressões e os possíveis comandos, através de uma série de produções utilizando símbolos terminais e não terminais da gramática da linguagem. Usada na descrição semântica do programa. Gera árvores sintáticas abstratas (Abstract Syntax Trees - ASTs) onde cada nó representa uma produção, com uma sub-árvore para cada subfrase.

Exemplo de sintaxe abstrata:

Program ::= Command              Program 
Command ::=  
          V-name := Expression Assignment         
        | Identifier ( Expression ) Call 
        | Command ; Command     Sequential 
        | if Expression        IfCommand  
          then Command  
          else Command 
        | while Expression  WhileCommand 
          do Command 
        | let Declaration     LetCommand  
          in Command 

2.	[0,5] Procure entender a notação BNF. Faça um histórico desta notação dando exemplos do seu uso. Qual a relação entre uma gramática e uma BNF?
	
	BNF é o acrônimo de Backus Naur Form. John Backus e Peter Naur foram os primeiros a introduzir uma gramáticas livre de contexto. Atualmente existem muitas variações de BNF como ABNF.

Abaixo um exemplo interessante da linguagem BNF sendo descrita em BNF: 

syntax     ::=  { rule }
rule       ::=  identifier  "::="  expression
expression ::=  term { "|" term }
term       ::=  factor { factor }
factor     ::=  identifier |
                quoted_symbol |
                "("  expression  ")" |
                "["  expression  "]" |
                "{"  expression  "}"
identifier ::=  letter { letter | digit }
quoted_symbol ::= """ { any_character } """

BNF é uma forma simples de definir uma gramática. É a forma mais comum de expressar linguagens em Ciências da Computação. Ela define o conjunto de todos os símbolos que constituem um programa válido em uma linguagem. Cada regra de produção em uma gramática tem uma regra análoga em BNF.

1.	[0,5] Defina o que você entende por “efeito colateral” em uma linguagem de programação. Dê um exemplo de efeito colateral em C. Formule restrições sobre a linguagem C de modo a eliminar a possibilidade de efeitos colaterais.

Efeito colateral induzem não determinismo na avaliação de expressões tornando os programas mais difíceis de entender e é considerada uma má prática de programação.

Exemplo em C:

int a = 1;

void main()
{
int result = 0;
result = a * func(a) + a;
}

int func( int x )
{
int ret = 0;
a = x + 2;
	ret = a;
	return ret;
	
}

Nesse exempo, não se sabe qual será o valor de result, pois a expressao poderar retornar vários valores como 4,5,6,..,etc. Pois não se sabe se a função func será calculada primeiro. A seguir é feito uma alteração no código para que o efeito colateral não ocorra.

int a = 1;

void main()
{
int result = 0;
int temp = func(a);
result = a * temp + a;
}

int func( int x )
{
int ret = 0;
a = x + 2;
	ret = a;
	return ret;
	
}

Chamando a função func primeiro e armazenando em uma variável temporária, o problema é resolvido, a função será calculada logo retornando 3, e o resultado da expressao result será 12.

2.	[0,5] Diga o que você entende por avaliação preguiçosa. Dê um exemplo que ilustre a avaliação preguiçosa.

	Na avaliação preguiçosa, os argumentos para a função não são avaliados até esses valores serem requisitados e nenhuma expressão partilhada é avaliada mais que uma vez. Se a expressão é sempre avaliada então o resultado é partilhado em todos os lugares em que ela é utilizada.
	A avaliação preguiçosa é uma característica importante das linguagens de programação funcional. Isso traz muitas vantagens , inclusive a habilidade de representar potencialmente estruturas de dados infinitas como o conjunto dos números inteiros.
	Exemplo: O gerenciador VM usa um algoritmo de paginação na demanda para saber quando carregar páginas para a memória. Ele espera até que alguma linha (thread) use um endereço e incorra em uma falha de página para depois recuperar uma página do disco. Este tipo de paginação na demanda é uma forma de avaliação preguiçosa. Os algoritmos de avaliação preguiçosa evitam executar uma operação dispendiosa. como a paginação, até que ela seja absolutamente necessária. 

5.    [0,5] Diga o que você entende por polimorfismo. Para ilustrar o seu entendimento, cite linguagens que possuem polimorfismo e dê exemplos de programas nessas linguagens que implementam o conceito. Explique detalhadamente os exemplos.

·	Com o polimorfismo, é possivel projetar e implementar sistemas que são mais facilmente extensíveis. Os programas podem ser escritos para processar genericamente, onde partes do programa podem ser adicionados com pouca o nenhuma modificação da parte genérica do programa. Variáveis e funções podem aceitar mais de um tipo. Tipos polimórficos podem definir operações que podem ser aplicadas a mais de um tipo. As operações garantidas pela herança em quase todas as linguagens orientadas a objetos são exemplos típicos de polimorfismo. ML, haskell, java, c++ são exemplos de linguagens que possuem polimorfismo.
·	
Exemplo em Haskell:
·	
·	long ls = IF vacia(L) then 0
·	else 1 + long(cola(L)); 
·	
·	O sistema de inferencia de tipos inferiria o tipo long::[x] -> Integer, indicando que tem como argumento uma lista de elementos de um tipo qualquer e que devolve um inteiro. Em uma linguagem sem polimorfismo seria necessario definir uma função long para cada tipo de lista que necessitasse.
·	
·	Exemplo em ML:
·	
·	fun segundo( var1: int , var2: int ) = var2
·	
Esta função é polimórfica pois uma chamada do tipo segundo( 222, false ) poderia ser possível pois nada ocorre no corpo da função então não importaria os argumentos passados como parâmetro.

Obs. As questões que possuem código serão enviadas por e-mail

UFPE | Centro de Informática

Página   3/1