Baixe o projeto da lista, que está preparado para funcionar tanto com o SBT quanto com o eclipse, para funcionar como base para implementar o que for necessário.
Algumas das questões pedem para extender os interpretadores vistos em sala, para isso use o
código que está nos pacotes subst, para o interpretador de substituição, e env,
para o interpretador de ambientes.
Questões que não são de codificação devem ser respondidas dentro do arquivo README.md do projeto.
Para rodar os interpretadores, veja o screencast (ligue a visualização em full screen):
Uma representação para conjuntos é pela sua função característica, uma função
que diz se um elemento pertence ao conjunto ou não. Em Scala, um conjunto de
elementos de um tipo T pode ser então dado pelo tipo de funções de T para
booleanos:
type Conjunto[T] = T => Boolean
Por exemplo, o conjunto dos inteiros pares pode ser dado por (x: Int) => x % 2 == 0.
Dada essa definição para conjuntos, a definição de uma função que verifica se um
conjunto contém ou não um elemento é trivial:
def contem[T](conj: Conjunto[T], elem: T) = conj(elem)
a) Defina uma função unitario que cria um conjunto unitário:
def unitario[T](elem: T): Conjunto[T] = ???
Resposta:
def unitario[T](elem: T): Conjunto[T] = x => x == elem
b) Defina as funções uniao, intesercao e diferenca, que faz a união,
interseção e diferença de dois conjuntos:
def uniao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ???
def intersecao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ???
def diferenca[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ???
Resposta:
def uniao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = x => c1(x) || c2(x)
def intersecao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = x => c1(x) && c2(x)
def diferenca[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = x => c1(x) && !c2(x)
c) Defina a função filtro que retorna um conjunto contendo apenas os elementos do
conjunto que passam pelo filtro:
def filtro[T](c: Conjunto[T], f: T => Boolean): Conjunto[T] = ???
Resposta:
def filtro[T](c: Conjunto[T], f: T => Boolean): Conjunto[T] = x => c(x) && f(x)
Note que o filtro
fna verdade também é um conjunto, pela nossa definição! Estamos fazendo a interseção desses dois conjuntos.
d) Defina a função map que transforma um conjunto de elementos de tipo T em um
conjunto de elementos de tipo U, dada uma função de mapeamento U => T:
def map[T, U](c: Conjunto[T], f: U => T): Conjunto[U] = ???
Resposta:
def map[T, U](c: Conjunto[T], f: U => T): Conjunto[U] = x => c(f(x))
e) Por que a função de mapeamento para conjuntos tem os tipos trocados em relação à sua
equivalente no map de listas?
Porque uma lista é um “produtor” de elementos, e um conjunto é um “consumidor”, então a função de mapeamento pega os elementos produzidos pela lista e os mapeia em outros, enquanto a função de mapeamento precisa mapear elementos para serem fornecidos com conjunto.
No intrepretador de fun da aula 11 (pacote subst), uma função definida localmente
com let ou letrec precisa ser chamada com parênteses em volta do seu nome, para que o
parser use um nó Ap ao invés de um nó Ap1, que só pode chamar funções globais.
Modifique o interpretador para que isso não seja mais necessário. Para isso, o resultado da
substituição de um nó Ap1 deve ser um nó Ap caso o nome da função esteja no mapa de
substituições. Teste sua modificação com o seguinte programa, que deve ter NumV(120) como
resultado:
fun menor(x, y)
x < y
end
letrec fat = fun (x)
if menor(x, 2) then 1
else x * fat(x-1) end
end
in fat(5) end
Resposta:
case Ap1(n, as) => m.get(n) match {
case Some(f) => Ap(f.subst(m), as.map(e => e.subst(m)))
case None => Ap1(n, as.map(e => e.subst(m)))
}
Retire o caso do nó Let da função eval, e implemente o let como açúcar sintático
para uma chamada de função anônima na função desugar (veja o segundo slide da aula de 15/05).
Você pode fazer essa mudança tanto no interpretador que está no pacote subst quanto no que
está no pacote env, mas indique onde está sua resposta.
Resposta abaixo. Note que precisamos mexer em
LetMtambém:
case Let(n, e, c) => Ap(Fun(List(n), c.desugar), List(e.desugar))
case LetM(es, c) => Ap(Fun(es.map({ case (n, _) => n }), c.desugar),
es.map({ case (_, e) => e.desugar }))
O cálculo lambda é um modelo de computação que é uma das bases da programação funcional, e pode ser visto como uma linguagem de programação bastante simples.
Uma expressão do cálculo lambda pode ser uma variável (um nome), uma aplicação (um par de expressões), ou uma abstração (um par de um nome, o parâmetro da abstração, e uma expressão, o seu corpo). As abstrações também são os valores da linguagem.
a) Defina um tipo algébrico para expressões no cálculo lambda, usando um trait CL e três construtores
Var, Ap, e Abs.
Resposta:
trait CL
case class Var(nome: String) extends CL
case class Ap(exp1: CL, exp2: CL) extends CL
case class Abs(param: String, corpo: CL) extends CL
A semântica do cálculo lambda call-by-value é dada por substituição: o valor de uma variável é um erro; o valor de uma abstração é ela mesma; para obter o valor de uma aplicação obtemos o valor do seu lado esquerdo (que será uma abstração) e seu lado direito, substituímos o parâmetro do lado esquerdo pelo valor do lado direito no corpo do lado esquerdo, e achamos o valor do resultado.
Para evitar capturas, um valor sendo substituído com variáveis livres também é um erro.
b) Escreva o interpretador eval, a substituição subst e a função que dá as variáveis
livres para o cálculo lambda call-by-value:
Respostas:
def eval: Abs = {
case Var(n) => sys.error("variável livre")
case Ap(e1, e2) => e1.eval match {
case Abs(p, c) => c.subst(p, e2.eval).eval
}
case Abs(p, c) => Abs(p, c)
}
def subst(nome: String, valor: Abs): LC = {
case Var(n) => if (n == nome) valor else Var(n)
case Ap(e1, e2) => Ap(e1.subst(nome, valor), e2.subst(nome, valor))
case Abs(p, c) => if (p == nome) Abs(p, c) else Abs(p, c.subst(nome, valor))
}
def fvs: Set[String] = {
case Var(n) => Set(n)
case Ap(e1, e2) => e1.fvs ++ e2.fvs
case Abs(p, c) => c.fvs - p
}
c) Escreva agora as três funções acima para o interpretador call-by-name do cálculo lambda:
Respostas:
def eval: Abs = {
case Var(n) => sys.error("variável livre")
case Ap(e1, e2) => e1.eval match {
case Abs(p, c) => c.subst(p, e2).eval
}
case Abs(p, c) => Abs(p, c)
}
def subst(nome: String, valor: LC): LC = {
case Var(n) => if (n == nome)
if (!valor.fvs.isEmpty)
sys.error("expressão com variáveis livres: " + e + ", fvs: " + e.fvs)
else valor
else Var(n)
case Ap(e1, e2) => Ap(e1.subst(nome, valor), e2.subst(nome, valor))
case Abs(p, c) => if (p == nome) Abs(p, c) else Abs(p, c.subst(nome, valor))
}
def fvs: Set[String] = {
case Var(n) => Set(n)
case Ap(e1, e2) => e1.fvs ++ e2.fvs
case Abs(p, c) => c.fvs - p
}
Implemente os padrões de recursão em listas que usamos em Scala: map, filter,
foldRight, foldLeft e flatMap como funções de fun definidas usando o método
do slide 19 da aula de 15/05
fun Cons(h, t)
fun (v, c)
(c)(h, t)
end
end
fun Vazia()
fun (v, c)
(v)()
end
end
fun map(f, l)
(l)(fun () Vazia() end,
fun (h, t) Cons((f)(h), map(f, t)) end)
end
fun filter(p, l)
(l)(fun () Vazia() end,
fun (h, t)
if (p)(h) then
Cons(h, filter(f, t))
else
filter(f, t)
end
end)
end
fun foldLeft(z, op, l)
(l)(fun () z end,
fun (h, t)
foldLeft(op(z, h), op, t)
end)
end
fun foldRight(z, op, l)
(l)(fun () z end,
fun (h, t)
op(h, foldRight(z, op, t))
end)
end
fun append(l1, l2)
foldRight(l2, fun (a, b) Cons(a, b) end, l1)
end
fun flatMap(f, l)
(l)(fun () Vazia() end,
fun (h, t)
append((f)(h), flatMap(f, t))
end)
end
O ambiente base das funções anônimas de fun com ambientes não precisa ter todas
as entradas do ambiente em que a função anônima foi definida, mas apenas as entradas para
variáveis livres no corpo da função. Implemente essa otimização no interpretador que está
no pacote env.
Reposta:
case Fun(params, corpo) => {
val fvs = this.fvs
FunV(env.filter({ case (n, _) => fvs.contains(n) }), params, corpo)
}
a) Em fun com ambientes e escopo dinâmico a expressão letrec ainda é necessária
para definir funções recursivas locais? E recursão mútua? Justifique.
Não, pois quando chamamos a função recursiva a sua definição vai estar no ambiente usado na chamada de função, pois no escopo dinâmico o ambiente do corpo da função é uma extensão do ambiente do ponto onde ela foi chamada, e não do ambiente onde foi definida.
b) Seria possível definir uma linguagem que mistura variáveis com escopo léxico e variávieis com escopo dinâmico? Justifique dando um esboço de sintaxe abstrata e estratégia de avaliação para essa linguagem.
Sim, para isso precisamos de dois ambientes, um ambiente estático e um ambiente dinâmico, e um “let dinâmico” que introduz variáveis dinâmicas. A primeira prova (e seu gabarito) tem um esboço mais completo do que seria necessário.
c) Implemente uma mudança equivalente à da questão 2 no interpretador de fun com ambientes e escopo
estático (pacote env).
A modificação caso
Ap1deevalé relaticamente simples:
case Ap1(func, args) =>
funs.filter({
case Fun1(nome, _, _) => nome == func
}).headOption match {
case Some(f) => f.apply(funs, args)
case None => sys.error("função " + func + " não existe ")
}
Mas ela interage com a otimização da questão 6, então também precisamos mudar
fvs:
case Ap1(n, es) => es.foldRight[Set[String]](Set())(
(e, s) => e.fvs ++ s)
Use o formulário abaixo para enviar a sua lista. Lembre de enviar apenas o arquivo package.scala que
você modificou. O prazo para envio é domingo, dia 02/06/2013.
Última Atualização: 2016-05-18 10:58