MC346 - Prova Lisp

Criada: 2014-07-27
Modificada: 2015-01-07

Enunciado distribuído na sala.

Gabarito

Questão 1

Exista herança múltipla em Common Lisp. Herança múltipla é a possibilidade de definir classes que tenham mais de uma classe mãe.

Questão 2

1. ((λx . (x(yx))(λy . z))) → ((λy . z)(y(λy . z))) → z
2. ((λw . (ww))(λz . x)) → ((λz . x)(λz . x)) → x
3. (λp . λq . ppq) (λz . λx . z)(λy . λx . x) → (λz . λx . z)(λz . λx . z) (λy . λx . x) → (λz . λx . z)

Questão 3

Variante com acumulador:

(defun separa (lista)
  (separa-acc lista () ())
  )

(defun separa-acc (lista pos nopos)
  (cond
   ((null lista) (list pos nopos))
   ((> (car lista) 0)
    (separa-acc (cdr lista) (cons (car lista) pos) nopos))
   (t
    (separa-acc (cdr lista) pos (cons (car lista) nopos)))
   )
  )

Variante sem acumulador:

(defun separa (lista)
  (if (null lista)
   (list () ())
   (let* ((res (separa (cdr lista)))
	  (pos (first res))
	  (nopos (second res)))
     (if (> (car lista) 0)
	 (list (cons (car lista) pos) nopos)
       (list pos (cons (car lista) nopos))
       )
     )
   )
  )

Questão 4

A solução a seguir é bem direta, usando a técnica de map-reduce, que tem recebido muita atenção ultimamente. Note que reduce não pode ser chamado com lista vazia, por isso foi necessário o if, e consequentemente o let, para evitar de chamar (pais x) duas vezes.

(defun ancestrais (x)
  (let ((p (pais x)))
    (if (null p)
	(list x)
      (cons x (reduce #'union (mapcar #'ancestrais p)))
      )
    )
  )

Questão 5

(defun perfeito (n)
  (and (> n 1)
       (= n (somadiv n))
       )
  )

(defun somadiv (n)
  (somadiv-ateh (1- n) n)
  )

(defun somadiv-ateh (k n)
  (cond
   ((<= k 0) 0)
   ((= 0 (mod n k)) (+ k (somadiv-ateh (1- k) n)))
   (t (somadiv-ateh (1- k) n))
   )
  )

Critérios de correção

Questão 1

Na Questão 1, que valia 0,5, a nota de cada aluna(o) foi 0,0 ou 0,5. Quem acertou e justificou apropriadamente ganhou 0,5. Os demais ficaram com 0,0. Ficou com 0,0 também quem disse que Lisp é uma linguagem orientada a objetos. Ficou com 0,0 quem não justificou nem explicou corretamente sua resposta.

Questão 2

Na Questão 2, os itens tiveram os seguintes valores:

• item (a): 0,5
• item (b): 0,5
• item (c): 1,0

Critérios adicionais para a Questão 2:

• Achou que λy . z → z: -0,5
• Achou que λx . x → x: -0,5
• Simplesmente passou as expressões para Lisp: vale 0,0
• Errou associatividade, ou seja, achou que abc significa a(bc): -0,5
• Mostrou que sabe aplicar termo lambda em argumento: +0,5

Questões 3, 4 e 5

Exceto pelas Questões 1 e 2, o critério de correção começou por decidir como seria a pontuação: de cima para baixo ou de baixo para cima. Se a resposta estava bem escrita, com sintaxe Lisp correta, resolução do problema pedido (e não de outro) e com comprimento proporcional à complexidade da questão, então a correção procedeu de cima para baixo, ou seja, parte-se do valor integral e vão sendo subtraidas frações de pontos para cada defeito encontrado.

Por outro lado, se a resposta estava mal escrita, com sintaxe errada, resolvendo o problema errado ou incompleta, então a correção procedeu de baixo para cima: parte-se de zero e vão sendo adicionadas frações de pontos a cada indício de conhecimento importante encontrado. Embora em geral a correção de cima para baixo resulte em notas maiores numa questão, é possível ter exceções a esta tendência.

Nas questões de escrita de código Lisp, os seguintes critérios foram universalmente aplicados. Os valores negativos se aplicam à correção de cima para baixo, e os valores positivos se aplicam à correção de baixo para cima.

• COND - inverteu condição e resultado: -0,5
• COND - não colocou t na cláusula default: -0,5
• COND - não cercou pares condição-resultado com parênteses: -0,5
• Confusão entre CONS, LIST e APPEND: -0,5
• Confusão com backqoute (`), vírgula (,) e quote ('): -0,5
• Uso de "." para indicar CONS ou APPEND: -0,5
• Confusão entre EQ, EQL, EQUAL e =: -0,5
• Recursão - erro em caso base: -0,5
• Recursão - loop infinito: -0,5
• Recursão - dupla recursão: -0,5
• Recursão - só fez caso base: +0,5
• Recursão - um pouco mais que caso base: +0,5
• Recursão - esqueceu caso base ou caso geral: -0,5
• Recursão - misturou com e sem acumulador: -0,5
• Discrepância no número de argumentos, nome dos argumentos ou ordem dos argumentos entre definição e chamada de função: -0,5
• Tentou usar let e/ou efeitos colaterais sem sucesso em DOLIST: -1,0
• Esqueceu CAR ou usou CAR demais: -0,5
• Esqueceu LIST ou usou LIST demais: -0,5
• Usou LET em lugar de LET*: -0,5
• Deixou CAR ou APPEND serem aplicados em átomos: -0,5
• Confusão entre CAR, CDR, CADR, etc.: -0,5
• Faltou APPLY: -0,5
• Faltou #' em expressão LAMBDA dada como argumento de MAPCAR: -0,5
• Função não definida (FLATTEN, INTP, INTEGER) ou definida erroneamente: -0,5
• Outros erros de sintaxe: -0,5

A seguir, critérios específicos para cada questão. Novamente, os valores negativos se aplicam à correção de cima para baixo, e os valores positivos se aplicam à correção de baixo para cima.

Questão 3

• Colocou zero entre os positivos ou esqueceu dele: -0,5
• Supôs argumentos inteiros: -0,5
• Confusão entre "<" e ">": -0,5

Questão 4

• Repetição de elementos: -0,5
• Intenção mal realizada de fazer a função receber tanto átomos como listas: -0,5
• Supôs que UNION retorna os elementos da primeira lista antes dos da segunda, ou vice-versa: -0,5
• Supôs máximo de dois pais por elemento: -1,0
• Só funciona para argumentos sem pais: +0,5
• Só inclui argumento e seus pais: +1,0
• Não incluiu argumento entre seus ancestrais: -0,5

Questão 5

• Somou N também entre seus divisores para efeito de testar perfeição: -0,5
• Só funciona para N par: -0,5
• Não incluiu o possível divisor N/2: -0,5
• Não evitou divisão por zero: -0,5
• Confusão entre \, /, %, MOD, FLOOR, etc.: -0,5
• Esqueceu de comparar soma de divisores próprios com N: -0,5

MC346 Home

© 2014 João Meidanis