Prova DCC024 Linguagens de Programação

Prévia do material em texto

DCC024 Linguagens de Programação Prova 1 15 dezembro, 2021
Nome: Matŕıcula:
1. Na primeira página das suas respostas deve constar seu nome. Todas as respos-
tas deverão ser manuscritas com suas próprias palavras. Não serão aceitas
respostas digitadas.
2. O exame deverá ser conclúıdo e entregue em até 24h. As respostas devem ser enviadas
via Moodle em único arquivo PDF digitalizado. Você deve se certificar de que o
arquivo enviado esteja completamente leǵıvel. Para isto as respostas devem ser
feitas de caneta.
3. A prova é individual, feita apenas por você, sem consultas a outras pessoas pre-
sencial ou virtualmente. Qualquer ind́ıcio de fraude será comunicado às instâncias
competentes da UFMG.
4. Se você acredita que alguma pergunta esteja subespecificada, anote as suposições
que você teve que fazer para chegar à sua resposta e justifique-as como parte de sua
resposta à pergunta.
5. Suas respostas serão avaliadas em sua clareza e concisão. Cada resposta deve ser
completa e devidamente justificada, e todas as etapas intermediárias de suas
soluções devem ser apresentadas com clareza. Note que as questões abaixo não neces-
sariamente pedem justificativas, mas deixar de provê-las acarretará na questão
ser zerada.
1. (10 points) Determine, para cada asserção, se ela é verdadeira ou falsa.
a. Não é necessário o uso de closures, ou abstrações similares para valores funcionais, para a
implementação de linguagens sem funções de ordem superior.
b. A semântica de uma linguagem de programação é uma descrição precisa de todos os seus
programas gramaticamente corretos.
c. Em linguagens com escopo estático é posśıvel avaliar, sem valores pré-definidos, expressões
com variáveis livres.
d. Uma vantagem de escopo dinâmico sobre escopo estático é que facilita, em geral, a análise
dos programas.
e. Funções de ordem-superior podem tomar outras funções como argumentos.
f. Uma função polimórfica tem, em prinćıpio, uma famı́lia infinita de tipos.
g. O propósitico de semânticas formais é descrever como uma linguagem de programação
pode ser implementada eficientemente.
h. Existem programas em SML cuja funcionalidade não pode ser codificada em cálculo
lambda.
i. A semântica operacional de uma linguagem de programação define, através de um conjunto
de regras de inferência, como a execução de um programa acontece passo a passo.
j. Em linguagens com polimorfismo paramétrico qualquer função pode ser definida sem res-
trições nos tipos de seus argumentos.
2. (16 points) Apresente uma explicação curta (1 a 3 linhas) para cada uma das questões abaixo.
a. Descreva duas vantagens de tipagem estática sobre tipagem dinâmica em linguagens de
programação.
b. Apresente um benef́ıcio, e contextualize sua importância, de prover uma semântica formal
para partes de uma linguagem de programação.
c. Argumente, informal mas precisamente, porque a a execução da função abaixo, para qual-
quer entrada, termina.
datatype btree = L of int | Node of btree * int * btree;
fun f (t: btree) =
case t of
(L n) => [t]
| (Node(l, n, r)) => t :: l :: r :: (f l) @ (f r);
d. Explique, de maneira curta (1-3 linhas), o que a função g abaixo faz. Sua explicação
deve descrever o comportamento de g relativo a como é sua sáıda dada sua entrada. A
explicação não deve descrever como g é executada.
fun f l1 l2 =
case l1 of
nil => l2
| (h::t) => f t ([h] @ l2);
fun g l = f l [];
3. (4 points) Usando recursão e casamento de padrões escreva em SML uma função f : int list
-> bool que recebe uma lista l de inteiros e retorna true se e somente se um dos elementos de
l é par.
Page 2
4. (6 points) Escreva em SML, utilizando combinadores e sem chamadas recursivas, uma função
equivalente a vconc.
fun vconc (l: (string * string) list) =
case l of
nil => ("","")
| (h::t) =>
let val headValue1 = #1 h;
val headValue2 = #2 h;
val recValue = vconc t;
val recValue1 = #1 recValue;
val recValue2 = #2 recValue
in
(headValue1 ^ recValue1, headValue2 ^ recValue2)
end;
5. (8 points) Considere um tipo de dado abstrato expr que represente a árvore de sintaxe abstrata
de uma mini-linguagem como a abordada nas nossas aulas, contendo operações aritméticas, Bo-
oleanas, declaração de variáveis (funcionais ou não) e chamadas de função. Considere também
uma função de avaliação eval que tome como entrada uma expressão expr e produza o inteiro
correspondente à sua avaliação.
...
| (LetFun(f, x, e1, e2)) => eval e2 ((f, Closure(f, x, e1, st))::st)
| (Call(Var f, e)) =>
let val fv = (lookup st f) in
case fv of
(Closure(f, x, e1, fSt)) =>
let
val ev = Int(eval e st);
val st’ = (x, ev) :: (f, fv) :: fSt
in
eval e1 st’
end
| _ => raise EvalError
end
...
Dado o trecho acima da função eval, que é usado para avaliar os componentes de expr para
declaração de funções e suas chamadas, descreva:
a. que tipo de escopo (estático ou dinâmico) está sendo implementado, e por que, para as
chamadas de função;
b. que modificações, e por que, devem ser feitas para mudar o tipo de escopo para a chamada
de função?
Page 3