Concurso/Encontro Nacional de Programação Lógica CeNPL'2003

Universidade de Évora

29--31 de Maio de 2003


Referências Trocadas

Dicionário Errado!

Um dicionário contem definições (ou entradas) para expressões de uma língua, podendo essas definições conter referências a outras expressões. Se uma referência numa das definições estiver errada é necessário corrigir o dicionário de uma forma eficiente.

O autor do dicionário de que aqui se trata é muito propenso a erros do tipo: dar como referência a expressão E se o que deveria referir é uma expressão E' que aparece referida numa das definições de E. Por exemplo, referir gato em vez de felino, que aparece referido numa definição de gato --- é claro que na definição de gato como marosca (aqui há gato!), felino não consta.

Supõe-se que o autor do dicionário não é tão incompetente que crie definições contendo referências para a própria expressão a definir.

Tarefa

Escreva um programa que resolva problemas do tipo anterior, em que um dicionário é representado por uma lista de entradas da forma e(X,Defs) com X um termo único que descreve a expressão, e Defs uma lista não vazia de definições. Cada definição é representada por um termo d(N,Descr) com N o número da definição e Descr uma lista de termos de duas formas: p(P) para palavras e ref(R) para referências.

Os Dados

O programa a escrever tem como dados o dicionário errado D e uma expressão E, passados como argumentos ao predicado de topo.

Os Resultados

Para um dicionário errado D e uma expressão E pretende-se obter um dicionário corrigido C substituíndo todas as referências a E por referências a Ec, que é (segundo o autor do dicionário!) a única expressão referida nas definições de E. Para evitar problemas futuros com o referido autor, o programa deve falhar se houver mais que uma referência nas definições de E, bem como em situações de: mais de uma entrada para a expressão dada, ou não existência de referência que se possa usar.

Por questões de eficiência, o dicionário errado só pode ser visitado (explicita ou implicitamente a nível do programa Prolog) uma única vez.

O predicado de topo do programa deve ser refsx(D,E,C).

Exemplos usando o seguinte dicionário: 
  [e(autor,[d(1,[p(criador)]),
            d(2,[p(escritor)]),
            d(3,[p(compositor)])]),
   e(ave,[d(1,[p(comida),p(de),ref(gato)])]),
   e(gato,[d(1,[ref(felino),p(pequeno)]),
           d(2,[p(marosca)])]),
   e(leao,[d(1,[p(especie),p(de),ref(gato)])]),
   e(marosca,[d(1,[p(tramoia)])]),
   e(rato,[d(1,[p(comida),p(de),ref(gato)]),
           d(2,[p(esperto)]),
           d(3,[p(alvo),p(para),ref(gato)])]),
   e(terminal,[d(1,[p(fim)])])]

 ?- teste_dic(D), refsx(D,gato,C).
D = ...
C = [e(autor,[d(1,[p(criador)]),
            d(2,[p(escritor)]),
            d(3,[p(compositor)])]),
   e(ave,[d(1,[p(comida),p(de),ref(felino)])]),
   e(gato,[d(1,[ref(felino),p(pequeno)]),
           d(2,[p(marosca)])]),
   e(leao,[d(1,[p(especie),p(de),ref(felino)])]),
   e(marosca,[d(1,[p(tramoia)])]),
   e(rato,[d(1,[p(comida),p(de),ref(felino)]),
           d(2,[p(esperto)]),
           d(3,[p(alvo),p(para),ref(felino)])]),
   e(terminal,[d(1,[p(fim)])])] ? ;
no

 ?- teste_dic(D),
    refsx([e(leao,[d(1,[p(mau)])])|D],leao,C).
Mais de uma entrada para :leao
no
 ?- teste_dic(D), refsx(D,rato,C).
Mais de uma referencia na definicao de :rato
no
 ?- teste_dic(D), refsx(D,felino,C).
Nao existe referencia na definicao de :felino
no
   ?- teste_dic(D), refsx(D,lixo,C).
Nao existe referencia na definicao de :lixo
no
This document was translated from LATEX by HEVEA.