Declarativa |
|
|
|
Depuração Declarativa de Programas Prolog
Descreve-se uma nova metodologia para depuração ("debugging") de programas Prolog, assente em informação declarativa prestada pelo utilizador. Este trabalho constitui um melhoramento às abordagens anteriores no campo de depuração declarativa, a vários níveis: diminuição substancial do número necessário de perguntas ao utilizador; primeiro tratamento específico para impurezas extra-lógicas, como o operador de corte e efeitos colaterais internos; tratamento uniforme para todos os tipos de erro, excepto não-terminação; uma arquitectura de implementação capaz de suportar programas do mundo real; e um protótipo experimental incorporando estes melhoramentos.
Este documento constitui um resumo alargado dum relatório
para tese de doutoramento, actualmente em fase de conclusão,
e onde é feita uma descrição mais detalhada
e completa da abordagem exposta.
1. Introdução Independentemente dos esforços com metodologias e ambientes de programação, verificação estática de programas, desenho de linguagens estruturadas, etc., a actividade de depuração de programas é um dos factos da vida de qualquer informático. Se aqueles desenvolvimentos permitem o desenvolvimento mais rápido e robusto de aplicações, é certo que existirão sempre erros que ultrapassam as tentativas de os prevenir à partida. A Programação em Lógica, e a linguagem Prolog em particular, teve uma primeira implementação sem dispôr de ferramentas para depuração de programas [23]. A primeira implementação com maior divulgação [21] começou por ter um mecanismo simples, para mostrar ou não todos os golos executados. Mais tarde Byrd [3] acrescentou-lhe o primeiro depurador manual Prolog, inspirado num modelo de execução contemplando o mecanismo de retrocesso da linguagem - a "caixa de 4 portas"; isto permitiu-lhe adaptar os conceitos presentes nos depuradores de linguagens imperativas. Na sequência do trabalho de Byrd foram desenvolvidos diversos melhoramentos, relacionados com ergonomia, acesso a informação mais detalhada sobre a execução dos programas, etc. Os depuradores manuais têm satisfeito as necessidades mínimas de depuração de programas, e são standard em todas as implementações Prolog. Mas esta abordagem de depuração pouco se diferencia da usada em linguagens imperativas, não capitalizando nas vantagens da programação em lógica. Pelo contrário, sofre pelo facto de os aspectos operacionais da execução Prolog serem mais complicados, dado o não-determinismo da linguagem e consequente recurso a estratégias de execução usando retrocesso. Sumarizando, os depuradores manuais não capitalizam nas características positivas do Prolog, como por exemplo a sua semântica declarativa, mas antes toleram as suas desvantagens (um modelo de execução mais complicado). Isto afecta tanto os programadores experientes como sobretudo os programadores menos experientes, como por exemplo técnicos especializados num domínio que não propriamente a programação: linguístas desenvolvendo gramáticas de linguagem natural, engenheiros de conhecimento desenvolvendo sistemas periciais, etc. No âmbito do seu trabalho em síntese de programas, Ehud Shapiro [24] introduziu a noção de depuração algorítmica, ou depuração declarativa.. A ideia base consiste em usar um oráculo, uma entidade (tipicamente o autor do programa) com conhecimento àcerca da semântica declarativa desejada para um programa, e assim um depurador declarativo poder localizar na árvore de execução uma instância do erro no programa:
Enquanto com um depurador manual um utilizador navega na árvore de execução usando comandos que implicam uma consciência dos aspectos operacionais, com um depurador declarativo a navegação é feita baseada em informação declarativa (por ex. "p(1) é falso", "p(2) é verdadeiro"), independente dos aspectos operacionais, e fornecida pelo utilizador no seu papel de oráculo. Sendo a navegação agora feita de forma sistemática e optimizada, e sendo dada informação declarativa sobre resultados do programa, consegue garantir-se que um erro seja encontrado, tipicamente com menos esforço. Esta abordagem trouxe esperança de melhores depuradores, e originou vários trabalhos académicos subsequentes (entre outros [20], [22], [15], [10], [18], [17], [14], [11], [13], [12], [8], [7], [9]). O presente trabalho segue esta linha, tentando construir a melhor abordagem possível melhorando os trabalhos anteriores, e esperando-se que decisiva para originar a aparição duma nova geração de depuradores. As suas contribuições principais são: Os primeiros algoritmos de depuração declarativa de programa-fonte, mais "inteligentes" do que os de depuração declarativa clássica: em condições típicas o número de perguntas feitas ao utilizador é de complexidade O( log (nº de componentes do programa) ), em vez de O( log (nº de golos executados) ). Algoritmos melhorados para "depuração declarativa clássica", em especial para o tratamento do caso de conjuntos incompletos de soluções. O primeiro tratamento específico de "impurezas" Prolog, como o operador de corte, efeitos colaterais internos e de saída. Isto reflecte-se simplesmente em extensões aos conceitos desenvolvidos para programas puros. Uma abordagem uniforme, usando a noção de "árvore de suspeitos", definida para todos os tipos de erro considerados. Isto permite também uniformidade na implementação. Um mecanismo de "árvore de execução virtual", um uso misto de espaço de armazenamento e recomputação automática. Permite depurar grandes computações em tempo útil, e parametrizar o balanço entre espaço gasto e tempo de resposta. O "HyperTracer", um protótipo incorporando o essencial da teoria, e usando uma interface gráfica sofisticada, permitindo um misto de depuração manual/declarativa. Está contudo ainda implementado em Prolog, sem suporte a baixo nível, pelo que é ineficiente e estritamente experimental. Na próxima secção demonstra-se o nosso protótipo. Em seguida definem-se os conceitos necessários para na secção seguinte se descrever o método base para "depuração declarativa clássica". Depois introduz-se a nova abordagem "depuração declarativa do programa-fonte", e passa-se a uma descrição sumária da implementação. Conclui-se com um "ponto de situação" e perspectivas para o futuro. Assume-se alguma familiaridade com a linguagem Prolog (por exemplo [6], e [16] para a teoria). 2. Uma sessão de depuração
Comecemos num passeio com o HyperTracer, o nosso protótipo
experimental. Veja-se o seguinte pré-processador para regras
de gramática lógica, que contém um erro,
como descobriremos mais tarde. O seu papel é transformar
uma lista de regras de gramática em cláusulas Prolog,
guardando-as com chamadas a assert
(aqui assert_user): transform( (A-->B), (NA :- NB), L1,Ln) :- !, transform(A,NA,L1,Ln), transform(B,NB,L1,Ln). transform( (A,B), (NA,NB), L1,Ln) :- !, transform(A,NA,L1,L2), transform(B,NB,L2,Ln). transform( [Terminal] ,true, [Terminal|L], L ) :- !. transform( A, NA, L1, Ln ) :-
A=..[Functor|Args], my_append(Args,[L1,Ln],NArgs),
NA=..[Functor|NArgs]. my_append([],L,L) :- !.
my_append([X|L1],L2,[x|L]) :- my_append(L1,L2,L).
%ERRO: x em vez de X load_grammar([Rule|Rules]) :- !,
transform(Rule,Clause,_,_), assert_user(Clause),
load_grammar(Rules).
load_grammar([]). a_phrase(G,L,Remaining) :- transform(G,NG,L,Remaining), NG.
Tome-se agora uma pequena gramática, que analisa frases
e produz as respectivas árvores sintácticas. A gramática
é carregada lançando o seguinte golo sob controle
do HyperTracer: ?- tg( % Comando HyperTracer para lançar um golo load_grammar([
(s(sentence(N,V)) --> np(N),vp(V)), (np(noun_phrase(D,N,R)) --> det(D), n(N), optrel(R)),
(np(noun_phrase(P)) --> pn(P)), (vp(verb_phrase(V,N)) --> tv(V),np(N)),
(vp(verb_phrase(V)) --> iv(V)), (optrel(relative)),
(optrel(relative(V)) --> [that], vp(V)), (pn(garfield) --> [miguel]),
(pn(jody) --> [luis]),
(iv(debug) --> [debugs]), (tv(use) --> [uses]), (tv(debug) --> [debugs]),
(tv(contain) --> [contain]), (det(a) --> [a]), (det(a) --> [some]),
(det(all) --> [all]), (n(debugger) --> [debugger]), (n(program) --> [programs]), (n(bug) --> [bugs]) ]) ).
Estando a gramática carregada com o pré-processador,
vejamos se ela aceita a seguinte frase, usando para isso o predicado
a_phrase, através dum golo novamente executado sob o HyperTracer:
?- tg( a_phrase(s(Semantics),[miguel,uses,a,debugger,that,debugs],[]) ).
A frase é aceite, mas mal: o argumento que devia devolver
uma árvore sintáctica contém em vez disso
uma variável livre: Semantics = _106 yes É altura de recorrer ao HyperTracer. Um aviso importante: a sua cosmética é experimental e provisória, pelo que as imagens de écran seguintes são algo deselegantes. Eis a sua janela com os golos que foram executados sob seu controle (em forma resumida, com '…' em lugar de termos grandes):
 Fazendo um "duplo-clique" com o rato no golo erróneo (a_phrase), obtem-se a sua janela de comportamento de golo:
 Tratemos de saber porque é que a solução errada foi produzida, usando o algoritmo SECURE (cf. secções seguintes), dando simplesmente um comando de menu descendente, "Why, SECURE" (outros comandos existem para outros algoritmos). O HyperTracer analisa a árvore de suspeitos suportando a solução, e "pergunta ao oráculo" (isto é, selecciona numa nova janela):
 Novamente se trata duma solução, por a árvore sintáctica produzida estar incorrecta. Repetindo-se o comando "WHY, SECURE" mais duas vezes sobre golos diferentes, o HyperTracer consegue isolar uma cláusula culpada… mas que não foi directamente produzida pelo utilizador. Onde outros depuradores param, o HyperTracer continua:
 E após premir "OK" acima:
 O HyperTracer levou-nos automáticamente até um golo suspeito, mas contido na primeira execução (do golo que carregou a gramática). O golo é inadmissível, porque optrel devia ter o 2º e 3º argumentos iguais, e 'x' não é uma árvore sintáctica. Após mais dois comandos "WHY, SECURE":
 A solução para append está correta. Após usar o comando "Correct & Continue":
 Esta solução está errada: a 3ª lista devia conter 'relative' em vez de 'x'. Após um último comando "WHY, SECURE" o HyperTracer mostra-nos o erro no programa:
 Um total de 7 "perguntas" foram necessárias, usando um algoritmo de "depuração declarativa de programa-fonte" (cf. abaixo). Usando um dos algoritmos de "depuração declarativa clássica", também disponível no HyperTracer, teriam sido necessárias 10 perguntas. Naturalmente que para programas e execuções maiores a diferença de comportamento entre as duas abordagens aumenta. Todas as janelas acima permanecem acessíveis em qualquer momento, permitindo por exemplo retirar (refazer) declarações, examinar árvores de derivação, executar outros golos, depurá-los e prosseguir com este, etc. Fica como exercício para o leitor imaginar o que teria sido esta sessão com um depurador manual convencional. 3. Definições básicas Neste capítulo introduzem-se as definições principais que suportam a nossa teoria. 3.1. Programa Um programa é um conjunto de definições de predicado. Uma definição de predicado é uma sequência de 0 ou mais cláusulas, com uma regra de completude. Todos os símbolos de predicado no programa têm uma definição de predicado. Uma cláusula é uma implicação da forma H:-B, onde H é um átomo, a cabeça da cláusula, e B é uma conjunção de literais ou operadores de corte, o corpo da cláusula. Cláusulas com corpo vazio são factos, e as outras são regras. A regra de completude dum predicado está sintácticamente implícita, e significa "este predicado não tem mais cláusulas". Cláusulas e regras de completude são os componentes do programa, e têm nomes únicos. 3.2. Computações Um golo é uma conjunção de literais e operadores de corte. Um golo atómico é um golo isolado (ou átomo). Uma chamada é um golo atómico seleccionado para execução. A substituição duma chamada é a composição das substituições acumuladas desde o golo inicial até à chamada. Uma instância de cláusula é uma cópia duma cláusula do programa com uma substituição aplicada. Cada instância de cláusula tem um nome único, mesmo que seja sintácticamente idêntica a outra. Uma instância de predicado é um par <G,P>, onde P é a definição de predicado que emparelha com o golo G. Uma instância de corpo de predicado é o conjunto de todas as chamadas nos corpos de cláusulas numa instância de predicado, resultando das várias instanciações (activações) das chamadas textuais no programa. Note-se que um literal numa instância de cláusula pode originar várias chamadas numa instância de corpo de predicado. 3.3. Comportamentos de golo Um comportamento de golo denota o resultado duma computação para um golo atómico. Dado um comportamento de golo, uma faceta de comportamento de golo (ou faceta de golo) é uma das suas partes - uma solução, a chamada, ou o conjunto de todas as soluções por inteiro. Diz-se que uma instância de componente de programa CI emparelha com uma faceta de golo F se: F é uma solução, e CI a instância de cláusula cuja cabeça unifica com a chamada do golo. F é um conjunto de soluções para o golo G, e CI a instância de predicado para G. F é uma chamada, e CI a instância de cláusula que a contém no seu corpo. Todas as facetas de golo têm nomes únicos. 3.4. Oráculo Um oráculo é uma entidade com conhecimento àcerca da semântica pretendida para o programa: é capaz de caracterizar o programa pretendido (i.e., sem erros), por contraposição ao programa presente (com erros), classificando como correctos ou incorrectos quaisquer facetas do comportamento de golos do programa presente. Declarações do oráculo são tuplos da relação o_s( Correcção, Faceta ). O 1º argumento é "correcto" ou "incorrecto", e o 2º é a faceta de golo respectiva. O oráculo classifica as facetas de golo que lhe são apresentadas, sempre integradas dentro dum comportamento de golo, e fá-lo de forma completamente independente de outros golos, ou de quaisquer aspectos operacionais (como ordem de execução, etc.). Por outras palavras, as declarações do oráculo são completamente livres de contexto, e expressam apenas a semântica declarativa do programa pretendido.
Segue-se uma tabela com os casos possíveis de resposta
do oráculo a perguntas sobre os vários tipos de
facetas de golos:
O oráculo inclui ainda um conjunto de regras próprias independentes do programa: preservação da sua consistência, inclusão lógica relativamente a declarações prévias, relação entre a correccão de golos negados e a dos golos não negados, etc. Pode também conter uma parte dependente do programa, caso este tenha uma especificação definida, mesmo que parcial. A este conjunto de regras e da relação o_s acima chama-se a "teoria do oráculo".
Preferiu-se desenvolver este conjunto de conceitos, em alternativa
a usar simplesmente os conceitos clássicos de semântica
declarativa, por se pretender mais flexibilidade e potência
para tratar as impurezas extra-lógicas do Prolog. No entanto
é possível estabelecer algumas analogias:
3.5. Erros Uma manifestação de erro é uma faceta de golo para qual existe uma declaração do oráculo classificando-a como incorrecta. Do nosso ponto de vista, um programa tem erros se e só se tem uma manifestação de erro. Admitindo que a computação termina, as únicas manifestações de erro a considerar são soluções incorrectas (ou "soluções erradas"), conjunto de soluções incorrecto (ou "solução ausente"), e chamada incorrecta ("inadmissível"). Intuitivamente, uma instância de erro é uma instância dum componente de programa que produz uma manifestação de erro independente de outras manifestações de erro. Um erro é um componente do programa com uma instância errada. Passam-se a definir os vários tipos de instância de erro. Uma instância de cláusula errada define-se como se segue. Seja H uma solução para a chamada G, emparelhando com uma instância de cláusula H:-B1…Bn. Esta é uma instância de cláusula errada se: o_s(incorrecto, H) é verdade, e para as soluções dos literais Bi no corpo, o_s(correcto,Bi) é verdade. E ainda, por causa do uso do operador de corte: Seja PB a instância de corpo de predicado para G. Para todas as chamadas Gi em PB, que estão textualmente à esquerda dum operador de corte, falharam completamente (i.é, não estão na árvore de prova de H), e que ocorrem nesta cláusula ou noutra anterior na definição de predicado, o_s(correct, "Conjunto de soluções de Gi") é verdade. Se não tivessem falhado, as chamadas Gi poderiam impedir o uso da cláusula.
Eis um exemplo dum mau diagnóstico obtido por outros
depuradores declarativos. (1) h(X,a)
:- c(X), !. A chamada h(1,X) tem uma solução errada h(1,b). Outros depuradores apontariam como errada a cláusula (2). Usando a nossa definição de cláusula errada, a cláusula (2) não seria apontada como erro - este seria sim "definição de predicado para c(1) está incompleta" (ver abaixo). Um subgolo inadmissível define-se como se segue. Seja A uma chamada unificando com uma instância de cláusula (H :- B1…,Bi,…Bn). Bi é um subgolo inadmissível se: o_s( correcto, A ) e o_s(incorrecto,Bi) são verdade. Para todas as soluções de literais Bj no corpo à esquerda de Bi, o_s(correcto,Bj)) é verdade. E agora uma condição adicional motivada pelo uso de operadores de corte: Seja PB a instância de corpo de predicado para A. Para todas as chamadas Gi em PB, que estão textualmente à esquerda dum operador de corte, falharam completamente (i.é, não estão na árvore de prova de H), e que ocorrem nesta cláusula ou noutra anterior na definição de predicado, o_s(correct,"Conjunto de soluções de Gi") é verdade. A noção de instância de predicado incompleta denota um predicado que falha em produzir uma solução, sem que a culpa disso seja atribuível aos seus subgolos. Só está definida para golos que falharam completamente, isto é que não tiveram alternativas cortadas por um tio na árvore de execução. É uma instância de predicado <G,P> para a qual o_s(incorrecto, conjunto de soluções de G) é verdade, e tal que para todas as chamadas Gi no seu corpo de instância de predicado: se Gi falhou completamente, então o_s(correcto,conjunto de soluções de Gi) é verdade. se Gi não falhou completamente, por ocorrer à esquerda dum operador de corte que foi atingido durante a execução, então o_s(correcto,Gi') é verdade para cada solução Gi' de Gi.
Exemplo Para a chamada h(2,Y), o seguinte programa não
produz a solução esperada h(2,b): (1)
h(X,a) :- c(X), !, b(X). O golo c(2) tem a sua execução cortada pelo corte na cláusula (1), e por isso não falha completamente - é "saltado em retrocesso". Outros depuradores declarativos indicariam o predicado h como incompleto. Usando a nossa definição, um depurador pode localizar o erro certo: "cláusula (3) errada". 4. Depuração Declarativa Clássica Passa-se agora à descrição do método de depuração, assente na ideia de "árvore de suspeitos". A ideia base é executar o golo inicial até ao fim, para em seguida analisar a sua árvore de execução congelada, e então efectuar o processo de depuração (interacção com o oráculo). Nesta secção descreve-se o método-base, que localiza uma instância de erro na árvore de execução. À perseguição deste objectivo chama-se "depuração declarativa clássica", por ser o objectivo também almejado por outros autores até hoje, e por oposição à nossa nova abordagem intitulada "depuração declarativa do programa-fonte", descrita na secção seguinte. 4.1. Árvore de suspeitos A árvore de suspeitos ST(F) para uma faceta de golo F (que não tem necessariamente que ser uma manifestação de erro) é definida como se segue: Cada nó tem o nome duma faceta de golo (solução, chamada, conjunto de soluções), e está etiquetado com a instância de componente de programa emparelhando com a faceta. A raiz é o nó F. Cada nó solução S tem um filho ST(Bi) para a solução Bi de cada chamada no corpo da instância da cláusula C emparelhada com S Pode ter ainda filhos adicionais devido aos operadores de corte: Seja PB a instância de corpo de predicado para o golo que produz a solução S. Para cada chamada Gi em PB, que esteja textualmente à esquerda dum operador de corte, tenha falhado completamente e que ocorra em C ou em cláusulas anteriores na definição de predicado, o nó S tem um filho ST("Conjunto de soluções de Gi"). Cada nó chamada G, ocorrendo na instância de chamada C, tem os seguintes filhos: ST(A), em que A é a chamada unificando a cabeça de C. Para cada solução de golo Bi no corpo de C, à esquerda de G, um filho ST(Bi). Pode ter ainda filhos adicionais devido aos operadores de corte: Seja PB a instância de corpo de predicado para o golo A. Para cada chamada Gi em PB, que esteja textualmente à esquerda dum operador de corte, tenha falhado completamente e que ocorra em C ou em cláusulas anteriores na definição de predicado, o nó G tem um filho ST("Conjunto de soluções de Gi"). Cada nó conjunto de soluções para um golo G tem os seguintes filhos. Seja PB a instância de corpo de predicado para G. O nó tem um filho ST("Conjunto de soluções de Gi") para cada golo Gi em PB que falhou completamente. Pode ter ainda filhos adicionais devido aos operadores de corte: para cada golo Gi em PB que não falhou completamente, por estar textualmente à esquerda dum operador de corte que foi atingido durante a execução, o nó tem um filho ST(Gi') para cada solução Gi' de Gi. O conjunto de suspeitos para uma faceta de golo F, SS(F), é o conjunto de todas as instâncias de componente de programa etiquetando nós em ST(F). Note-se que instâncias "semelhantes" de componentes (por exemplo, cláusulas sintacticamente idênticas a menos de mudança de variáveis) correspondem a suspeitos diferentes. Pode demonstrar-se a seguinte proposição: Proposição 1 Dada uma manifestacão de erro T, SS(T) contém uma instância de erro. 4.2. Refinando conjuntos de suspeitos O processo de depuração passará por um refinamento dum conjunto de suspeitos inciais, enquanto aumenta o conhecimento na teoria do oráculo. Este processo deve ser tal que preserve a existência duma instância de erro no conjunto restante. Proposição 2 Considere-se uma manifestação de erro F, uma teoria de oráculo OT, e um nó F' em ST(F), para o qual o_s(correcto,F') seja verdade em OT. Então o novo conjunto de suspeitos obtido de SS(F) removendo todos os suspeitos em SS(F') ainda contém uma instância de erro. Por outras palavras, se a raiz duma subárvore suspeita é declarada correcta pode-se eliminá-la do conjunto de suspeitos, porque se consegue sempre encontrar uma instância de erro noutro sítio. O caso dual consiste no uso de declarações de incorrecção, usando simplesmente a proposição 1 acima. Um conjunto de suspeitos refinado, RSS(F,OT), é um subconjunto mínimo de SS(F), obtido deste aplicando as proposições 2 e 1, usando a teoria de oráculo OT. Em geral poderá não ser único, devido às regras do oráculo que verificam a inclusão de declarações. Um árvore de suspeitos refinada, RST(F,OT), é obtida de ST(F) excluindo todos os nós cujas etiquetas (instâncias de componentes de programa) não estejam em RSS(F,OT). 4.3. O algoritmo de depuração O processo de depuração ou diagnóstico assenta na ideia de começar com uma manifestação de erro no topo duma árvore de suspeitos, e manter uma "manifestação de erro corrente" que vai sendo cada vez mais baixa na árvore, até um nó cujos filhos não sejam manifestação de erro. Em paralelo mantêm-se uma "teoria de oráculo corrente", que vai incorporando as declarações do utilizador sobre nós suspeitos. Implicitamente, o conjunto de suspeitos associado à manifestação de erro corrente vai sendo refinado. O problema a resolver é pois escolher os nós sobre os quais se interroga o oráculo. Pode encarar-se como um problema de pesquisa, ou se se quiser de jogo entre dois "opositores": a instância de erro posiciona-se no sítio mais recôndito da árvore de suspeitos, tentando aumentar o número de perguntas necessárias até a identificar; o depurador escolhe nós que minimizem o número de perguntas a fazer no caso mais desfavorável. Para a escolha da pergunta (nó) utiliza-se uma função de estimativa, assumindo que não existe informação adicional sobre a probabilidade das respostas do utilizador. Dada uma manifestação de erro T e uma teoria de oráculo OT, a função estimativa do custo de diagnóstico, hf(T,OT), define-se como se segue: o menor (b logb n) (para todas as árvores de suspeitos refinadas RST(T,OT)), em que b é o máximo número de filhos de qualquer nó na árvore, e n o número de nós na árvore. Esta função é um majorante do verdadeiro custo. Segue-se o algoritmo GD&Q. Dada uma manifestação de erro ME, e uma teoria de oráculo inicial OT (que poderá ser vazia, ou conter uma especificação parcial do programa, respostas de sessões anteriores, etc.), faz uma sequência de perguntas ao utilizador e termina localizando uma instância de erro. Em cada iteração escolhe o nó que "melhor divide" a árvore de suspeitos, relativamente ao nº de perguntas subsequentes necessárias. 1. OTcorrente = OT; MEcorrente = ME; 2. Se RSS(MEcorrente,OTcorrente) tiver um só elemento I, termina com I como instância de erro. 3. Para cada nó F em RST(MEcorrente,OTcorrente), computar a diferença | hf( MEcorrente, OTcorrente » {o_s(correcto,F)} ) - hf( F, OTcorrente » {o_s(incorrecto,F)} ) |. Escolher o nó F' com a menor diferença. 4. Perguntar ao utilizador se F' é correcto. Se F' estiver correcto, fazer OTcorrente = OTcorrente » {o_s(correcto,F')}, e continue-se no passo 2. Senão, fazer MEcorrente=F', OTcorrente = OTcorrente » {o_s(incorrecto,F')}, e continue-se no passo 2. O diagnóstico obtido é necessariamente correcto, como segue da definição de conjunto de suspeitos refinado (cf. acima). O algoritmo termina sempre, uma vez que se assumem execuções finitas, e consequentemente árvores de suspeitos finitas, e cada iteração iliba pelo menos um suspeito. Nos piores casos GD&Q precisa de fazer hf(ME,OT) perguntas. Quanto à complexidade computacional, cada iteração de GD&Q, correspondendo ao tempo entre uma resposta do utilizador e a próxima pergunta, é O(n), n sendo o número de suspeitos inicial. Isto assumindo a disponibilidade directa da árvore de suspeitos, e custo constante para o uso das regras próprias do oráculo (por exemplo, verificar se existe uma resposta anterior que sirva à pergunta actual), o que em termos práticos é razoável. 4.4. Efeitos colaterais na base de dados interna Para maior clareza da exposição anterior, relegaram-se para esta secção as particularidades relacionadas com o tratamento de efeitos colaterais na base de dados interna, resultado de "chamadas de efeito colateral" (assert, retract, abolish, etc.). Em [4] apresenta-se também o tratamento para efeitos colaterais de saída (consequência de write, etc.), que é bastante diferente. Começa-se por assumir que os erros em programas que usam chamadas de efeito colateral se manifestam da mesma forma que anteriormente, ou seja pela presença duma manifestação de erro no golo inicial ou num golo intermédio (por exemplo no caso duma chamada inadmissível por violar o tipo dum predicado de sistema). Caso contrário teria que se estender a nossa noção de "comportamento de golo" para incluir todas as mudanças de estado na base de dados interna. A ideia-base consiste em estender os conjuntos e árvores de suspeitos, de execuções que usem definições de predicado afectadas por efeitos colaterais, com os suspeitos suportando as (potencialmente inadmissíveis) respectivas chamadas. A extensão é a seguinte: A árvore de suspeitos estendida é definida relativamente a uma árvore de suspeitos normal (cf. acima), da seguinte forma: Seja F um nó numa árvore de suspeitos, etiquetado com uma instância dum componente dum predicado P. O mesmo nó na árvore de suspeitos estendida tem um filho adicional ST(G) para cada chamada de efeito colateral G executada antes de F e que altera a definição de predicado P. O conjunto de suspeitos estendido é definido como antes, mas a partir da árvore estendida. Para uma execução que não use efeitos colaterais, a árvore e o conjunto de suspeitos estendidos reduzem-se ao normal. Esta extensão traz uma novidade interessante: os conjuntos de suspeitos para uma manifestação de erro num golo podem agora incluir suspeitos noutras execuções (como se pôde apreciar na sessão exemplo inicial). O algoritmo de depuração continua a ser o mesmo, simplesmente passando a trabalhar com a versão estendida da árvore de suspeitos. Há no entanto dois "pormenores" a ter em conta: Uma pergunta àcerca da correcção (admissibilidade) duma chamada de efeito colateral apenas se refere à possibilidade dela violar um tipo. Isto é, o utilizador poderá por exemplo detectar um subgolo errado numa cláusula argumento dum assert, e classificar a chamada como inadmissível, mas caso contrário não se pode assumir que a chamada seja "admissível" (no sentido de se poderem ignorar manifestações de erro suportando a chamada). Mais ainda, a nossa abordagem não leva em conta a ordem temporal entre as chamadas de efeito colateral, uma vez que isso exigiria interrogar o utilizador referindo essa ordem, e assim violar a nossa postura declarativa. Consequentemente é possível em alguns casos obter-se um diagnóstico vacuoso. Por exemplo, considere-se um predicado cuja implementação requer que uma série de termos seja armazenada como cláusulas segundo uma certa ordem. Quando mais tarde se depuram os problemas causados pelo predicado, as perguntas sobre admissibilidade das chamadas que armazenam os termos não levam em conta a sua ordem: as chamadas serão dadas como admissíveis pelo oráculo, e o depurador não consegue ir além do assinalar uma cláusula errada (um dos termos guardados). De qualquer forma, mesmo com esta limitação a abordagem parece-nos um melhoramento relativamente aos depuradores tradicionais. Especialmente porque as situações em que a limitação se verifica são raras, e normalmente consideradas de evitar atendendo ao (mau) estilo de programação nelas implícito. 5. Depuração Declarativa do Programa-fonte Até agora o objectivo foi encontrar uma instância de erro no programa. Vai agora adoptar-se um objectivo diferente, e procurar um erro no programa, ou seja um componente que tenha uma instância errada, independentemente de qual esta seja. À abordagem baseada nesta ideia chama-se Depuração Declarativa do Programa-fonte, por oposição à anterior "Depuração Declarativa Clássica". A correspondente "equação" passa a ser:
Como se verá, em geral é possível localizar um erro (no programa-fonte) com muito menos perguntas do que as necessárias para localizar uma instância de erro (na árvore de execução). O que é natural se se atender a que se obtém menos informação: o diagnóstico passa a ser a simples localização dum componente errado, em vez duma instância do componente com as substituições aplicadas ao golo com que emparelha. O "Ovo de Colombo" reside no facto dessa informação adicional ser normalmente pouco importante, em contraste com o enorme interesse em se poder assinalar numa janela de edição o componente errado, pronto a corrigir. Esta nova abordagem combina-se naturalmente com a anterior, herdando todos os seus conceitos, conseguindo por isso tratar os mesmos tipos de erro e também suportar programas com impurezas extra-lógicas. 5.1. Motivação Começa-se com um exemplo que ilustra a utilidade da ideia acima.
Exemplo Eis o habitual predicado para concatenar listas,
com um erro que o faz produzir (entre outras) a solução
errada append( [1,2,3,4,5], [6], [1,2,3,4,5,6,7,8]
):(c1) my_append([],L,K). %
Erro: K_L Segue-se a árvore de suspeitos da solução, estando os nós anotados à esquerda com o nome da cláusula do programa de que uma instância emparelha com a solução no nó:
 Sem informação adicional, um algoritmo de depuração declarativa clássica não poderia fazer melhor do que escolher o "nó do meio", assinalado com "D&Q", seguindo-se uma ou 2 perguntas adicionais até localizar a instância de erro. Ora convirá notar que debaixo do nó my_append([],[6],[6,7,8]) só há instâncias de cláusulas (na circunstância uma, c2) que não têm instâncias em nós acima: acima só há instâncias da cláusula c1, correspondentes aos sucessivos passos recursivos da execução do predicado. Um depurador declarativo de programa fonte deveria fazer a pergunta àcerca daquele nó. Se o oráculo o desse como correcto, a árvore de suspeitos refinada (a parte de cima) passaria a conter apenas instâncias da mesma cláusula (c1). Se o oráculo o der como incorrecto (como sucede neste caso), a árvore de suspeitos refinada (a parte de baixo, com um só nó) também passaria a conter apenas instâncias da mesma cláusula (c2). Em qualquer dos casos, não seriam necessárias perguntas adicionais, uma vez que o erro está localizado! Passa-se agora a apresentar um algoritmo que usa a ideia ilustrada neste exemplo. 5.2. O algoritmo "SECURE" Começa-se por definir a noção de "conjunto de suspeitos no programa-fonte", a partir do conjunto de suspeitos anterior. O conjunto de suspeitos no programa-fonte para uma faceta de golo F, SSS(F), é o conjunto de todos os componentes de programa que têm instâncias em SS(F). O conjunto de suspeitos no programa-fonte refinado, RSSS(F,OT), é o conjunto de todos os componentes de programa que têm instâncias em RSS(F,OT). O algoritmo SECURE baseia-se em começar com uma suposição que simplifica o processo de depuração, para de seguida obter um diagnóstico, ou no caso mais desfavorável apenas um "diagnóstico suposto". Neste caso o algoritmo procede à validação do diagnóstico encontrado, e caso este seja inválido (por a suposição inicial ser inadequada) recai no algoritmo GD&Q acima. Ou seja, a fase final garante a "segurança" do algoritmo e do uso da suposição base, daí o seu nome. A referida suposição SECURE é a seguinte. Seja F uma faceta de golo declarada correcta pelo oráculo; então todos os componentes de programa em SSS(F) são supostos correctos, e omitidos dos conjuntos de suspeitos no programa-fonte considerados pelo algoritmo. Por outras palavras, qualquer componente de programa com uma instância que suporte uma faceta de golo correcta é suposto correcto. Por conveniência, usa-se abaixo ACC para denotar o conjunto de componentes de programa supostos correctos, devido à suposição SECURE, atendendo às declarações na teoria de oráculo corrente (OTcorrente). Segue-se o algoritmo SECURE, que localiza um erro no programa após uma sequência de perguntas: 1. OTcorrente = OT; MEcorrente = ME; 2. Se RSSS(MEcorrente,OTcorrente) tiver um só elemento C, termina com o componente C como diagnóstico. 3.1 Se ACC RSSS(MEcorrente,OTcorrente), (a suposição SECURE não serve) então: escolha-se um nó F em RST( MEcorrente, OTcorrente ) seguindo o critério do algoritmo GD&Q (passo 3) e passe-se ao passo 4 abaixo. 3.2 senão, se #(RSSS(MEcorrente,OTcorrente)\ACC)=1 então: (Caso do "diagnóstico suposto") Seja D o (único) componente em RSSS( MEcorrente, OTcorrente ) \ ACC; D é um "diagnóstico suposto". De seguida procede-se à sua validação: Considere-se a instância DI de D em RSS(MEcorrente,OTcorrente), para a qual faltem menos declarações para ser considerada errada (por exemplo, se DI fôr uma instância de cláusula, que tenha poucos literais ainda não classificados pelo oráculo). Pergunte-se ao oráculo àcerca dos literais ainda não classificados, actualizando OTcorrente, até uma das seguintes condições se verificar: - DI é comprovada como instância de erro, e o algoritmo termina; - Uma nova manifestação de erro B é assinalada, e então continua-se no passo 2 com MEcorrente=B. 3.3 senão ( Caso em que RSSS( MEcorrente, OTcorrente ) \ ACC tem sempre mais que um elemento) Escolha-se o nó F em RST(MEcorrente,OTcorrente) para o qual a diferença | #( RSSS( F, OTcorrente)\ACC ) - #(RSSS( MEcorrente, OTcorrente ) \ ACC ) / 2 | seja mínima; se este critério indicar mais do que um nó, escolha-se o melhor de acordo com o critério do passo 3 do algoritmo GD&Q. 4. Perguntar ao utilizador se F é correcto. Se F estiver correcto, fazer OTcorrente = OTcorrente » {o_s(correcto,F)}, e continue-se no passo 2. Senão, fazer MEcorrente=F, OTcorrente = OTcorrente » {o_s(incorrecto,F)}, e continue-se no passo 2. Para um utilizador impaciente e experiente, e quando é necessário proceder à validação dum diagnóstico suposto (passo 3.2), SECURE poderá mostrá-lo antes de prosseguir com as perguntas adicionais. Mostra-se agora um exemplo justificando a necessidade de em geral fazer as perguntas adicionais para validação dum diagnóstico suposto:
Exemplor(X,Y) :- p(X), p(Y).
Para a solução errada r(a,b) há uma instância de erro p(b):-q(b), uma instância da 2ª cláusula. Ora quando o oráculo declara a solução p(a) correcta, SECURE assume que a 2ª cláusula está correcta - uma suposição inválida, o que SECURE descobre mais tarde ao confirmar o diagnóstico e o oráculo o informar que a solução p(b) está incorrecta. Quanto à complexidade de SECURE relativamente ao número de perguntas feitas, e prevendo o caso em que ele conclui com o algoritmo GD&Q, é O( b log(C)+k log(n-C)), em que C é o número de componentes do programa no conjunto de suspeitos inicial, b o máximo número de filhos de qualquer nó na árvore de suspeitos e k uma constante. A segunda componente contempla o caso em que o diagnóstico só é obtido depois da suposição SECURE ser inválida. Não temos ainda uma estimativa formal da qualidade da suposição SECURE, especialmente quando os componentes têm instâncias espalhadas por diferentes regiões da árvore de suspeitos (caso contrário pode mostrar-se que só se obtêm diagnósticos legítimos, que não necessitam validação, e a complexidade é O(b log C)). Nos exemplos testados (cf. [5]) a suposição revelou-se francamente acertada, conseguindo assim localizarem-se erros com um número de perguntas O(b log C) em vez de O(b log n). 6. Arquitectura da Implementação Efectuámos uma implementação experimental da nossa abordagem, o já referido "HyperTracer", suportando entre outros os algoritmos descritos (GD&Q, SECURE). Eis a sua arquitectura global:
 Os golos lançados pelo utilizador são executados pela "máquina de execução", que armazena uma descrição parcial de cada árvore de execução. Os algoritmos de depuração, e outras facilidades de inspecção do HyperTracer, utilizam aquela descrição da execução, ignorando os detalhes da computação. Quando é necessária uma descrição mais completa duma região duma árvore de execução, pedem à máquina de execução para completar a informação armazenada, recomputando um dos golos armazenados. Durante as recomputações não são repetidas chamadas de efeito colateral, nem subárvores de execução cujas raízes estejam já armazenadas, que são usadas como lemas. O desenho deste mecanismo de recomputação constituiu um dos principais esforços da nossa implementação, e é descrito na secção que se segue. 7. Árvores de execução virtuais Em [5] discutem-se as opções possíveis para armazenar árvores de execução Prolog, e conclui-se ser o uso de "árvores de execução virtuais" a mais interessante para a depuração declarativa clássica de grandes computações. Está em aberto a questão de existir ou não uma opção mais interessante e específica para os novos métodos de depuração declarativa do programa-fonte. Na conclusão esboça-se um esquema de implementação nessa direcção. Aqui limitamo-nos a resumir as conclusões relevantes de [5], para onde remetemos o leitor interessado nos detalhes de implementação. A ideia básica de árvore de execução virtual consiste em armazenar uma descrição parcial da árvore de execução. Nós (facetas de golo) não armazenados podem ser acedidos por uma recomputação da execução, a pedido e mais curta, e a partir de nós (chamadas) já armazenadas. A escolha das facetas de golo a guardar é feita usando simples contagens de nós durante a execução inicial. A quantidade de nós armazenados, bem como o (inversamente proporcional) tempo de recomputação máximo para recomputar nós não armazenados, são parametrizáveis por um valor limite global WMAX, o tempo máximo necessário para obter por recomputação qualquer faceta de golo. Consegue assim estipular-se um compromisso entre espaço de armazenamento e tempo de resposta, e cujo valor dependerá sobretudo da velocidade da combinação (máquina de execução + implementação Prolog) a usar, e do espaço de memória disponível. Para que o espaço de armazenamento seja O(n/WMAX), n sendo o número de facetas de golo na árvore de execução, esta deverá ter número de filhos por nó bastante inferior a WMAX. Caso contrário pode cair-se em situações de "saturação" em que o espaço gasto é O(n). Ou seja, a implementação da máquina de execução necessita ser bastante eficiente (rápida). Analisaram-se as operações necessárias para a máquina de execução do HyperTracer, contrapondo-as com as operações tipicamente efectuadas por uma implementação de Prolog standard usando compilador. Note-se que para os golos cujas facetas não são armazenadas (a maioria) as operações efectuadas são de custo constante por golo, em espaço e tempo, independentemente do programa. Isto constituiu um dos requisitos para desenho da implementação. Assim constatou-se que em princípio é possível implementar a máquina de execução com um custo adicional de no máximo cerca de 150% para a velocidade, e 200% para o espaço nas pilhas da máquina abstrata Prolog. Isto dependendo dos programas, sendo o custo adicional proporcionalmente menor para programas que passam como argumentos muitos ou grandes termos, e assumindo suporte ao nível do compilador e da máquina abstrata Prolog. Por exemplo, numa implementação Prolog com uma velocidade de 50Klips, já realista mesmo em estações de trabalho de baixo de gama, para garantir um tempo de recomputação máximo de 0,1 segundos fazia-se WMAX = 2000. Ficaria-se assim bem acima do número de filhos por nó em árvores de execução típicas, evitando-se os fenómenos de "saturação" referidos acima. Para fazer depuração declarativa de programa-fonte WMAX deverá ser 0, para obrigar ao armazenamento de todos os nós e assim não se omitirem componentes. Isto porque enquanto que a passagem duma representação parcial da árvore de execução para uma mais completa, ou seja uma "focagem" sobre uma subárvore, se pode fazer por forma a corresponder a um refinamento duma árvore de suspeitos, em geral não corresponde a um refinamento dum conjunto de suspeitos no programa-fonte. Estes têm instâncias espalhadas arbitrariamente pela árvore de execução, pelo que refinamentos feitos a árvores parciais serão tipicamente sem fundamento. 8. Conclusões Apresentou-se o que se espera seja uma contribuição útil para o campo de depuração declarativa na programação em lógica, e especialmente para a linguagem Prolog. Os métodos desenvolvidos poderiam em princípio ser aplicados a outras linguagens, mas com menor interesse dada a semântica menos composicional doutras linguagens. Embora o Prolog contenha impurezas extra-lógicas, e use efeitos colaterais, estes são proporcionalmente em muito menor quantidade do que os golos "puros", o que permite "mantê-los sob controle" como foi feito acima. Em [4] efectuam-se comparações com outros autores, e cobrem-se outros pontos aqui omissos por falta de espaço: depuração de programas pré-processados e meta-interpretados, e também de programas com efeitos colaterais de saída, uso da tecnologia de depuração declarativa para suporte à actualização de bases de conhecimento, outros algoritmos, facilidades para inspecção manual da execução e do programa, etc. Embora não tenham sido desenvolvidos métodos específicos para execuções que não terminam, estas são interrompíveis pelo utilizador, que pode usar todos os mecanismos descritos sobre a execução parcial. Em muitos casos uma execução "infinita" é causada por um dos erros tratados aqui. Tal como se referiu acima, a abordagem exposta é passível de implementação eficaz, requerendo no entanto algum esforço que até agora concentrámos nos desenvolvimentos experimentais. A técnica apresentada de depuração declarativa do programa-fonte coloca novos desafios de implementação: existirá uma implementação melhor do que o uso das árvores de execução virtuais, que foram desenvolvidas essencialmente para suportar depuração declarativa clássica de grandes programas ? Estamos em crer que sim. Uma direcção que se nos afigura promissora assenta na seguinte ideia: para uma execução, armazenar as primeiras N (N constante) facetas de golo que emparelham com cada componente, juntamente com alguma informação sobre a sua árvore de suspeitos; ou seja, no fim da execução haverá CN facetas de golo guardadas (C sendo o número de componentes suspeitos), incluindo pelo menos uma por componente. Em seguida aplicar a fase inicial do algoritmo SECURE, usando apenas a informação guardada. Esta alternativa terá a vantagem duma implementação simples e eficiente, podendo beneficiar ainda de informação estática do programa (grafo de chamadas) para melhor dimensionar as estruturas de dados necessárias. O ponto crucial a explorar é saber se, na prática, a falta de informação devido a não se guardarem todas as facetas de golo é ou não relevante. Em suma, apontamos duas grandes questões em aberto: a realização duma implementação a baixo nível da nossa abordagem, em particular do mecanismo de árvores de execução virtuais, e o estudo formal ou estatístico da suposição SECURE e seu uso em novas implementações dedicadas.
Referências 1. S.P. Abreu, "The ALPES Prolog Programming Environment" in Proceedings of Workshop on Logic Programming Environments (eds. D. Bowen) (Cleveland. 2. J. Alegria, A. Dias and L. Caires, "Towards Distributed Tools for Heterogeneous Logic Programming Environments" in Proceedings of the 6th International Conference on Logic Programming (eds. Levi and Martelli), MIT Press, , 1989. 3. L. Byrd, "Understanding the control flow of Prolog programs" in Proceedings of the 1980 Logic Programming Workshop (eds. S.-A. Tarnlund), , 1980. 4. M. Calejo, A Framework for Declarative Prolog Debugging, Universidade Nova de Lisboa, PhD, 1990. 5. M. Calejo and L.M. Pereira, "Declarative Source Debugging" in Proceedings of Workshop on Logic Programming Environments (eds. T. Kusalik and J. Levy) (Eilat, Israel. 6. W. Clocksin and C. Mellish, Programming in Prolog, Springer Verlag, 1981. 7. Dershowitz and Y. Lee, "Deductive Debugging" in Proceedings of the Fourth Symposium on Logic Programming , IEEE Computer Society Press, San Francisco, 1987. 8. W. Drabent, S. Nadjm-Tehrani and J. Maluszynski, "Algorithmic Debugging with Assertions" in Meta-programming in Logic Programming (eds. J. Lloyd), MIT Press, Bristol, 1988. 9. M. Ducassé and A.-M. Emde, Automated debugging of real Prolog programs using symptom-driven abstraction. The non-termination analysis., ECRC, München, Technical Report, TR-LP-41, July 1989. 10. G. Ferrand, "Error diagnosis in logic programming, an adaptation of E.Y. Shapiro's method," Journal of Logic Programming, 4:3, 177-198. 11. M. Huntbach, Interactive Program Debugging and Synthesis, University of Sussex, PhD, 1990. 12. K.Y. Koh, Debugging Prolog Programs, Imperial College of Science and Technology, MSC, 1985. 13. Komorowski, "A Declarative Logic Programming Environment," Journal of System Software, 2:8. 14. Y. Lichtenstein and E. Shapiro, "Abstract algorithmic debugging" in 5 th International Conference and Symposium on Logic Programming (eds. K. Bowen and R.A. Kowalski), MIT Press, Seattle, 1315--1336, 1988. 15. J. Lloyd, "Declarative Error Diagnosis," New Generation Computing, 5:2, 133-154. 16. J. Lloyd, Foundations of Logic Programming, 2, Springer Verlag, 1987. 17. J. Lloyd and A. Takeuchi, A framework for debugging GHC, ICOT,Tokyo, Japan, TR-186. 18. L. Naish, P.W. Dart and J. Zobel, "The NU-Prolog Debugging Environment" in Logic Programming - Procs. of the 6th Intl. Conf. (eds. G. Levi and M. Martelli), MIT Press, Lisbon, 1989. 19. F. Pereira and e. al., C-Prolog User's Manual, Dept. of Architecture, University of Edinburgh, UK. 20. L.M. Pereira, "Rational debugging in Logic Programming" in Procs. Third International Conference in Logic Progamming (eds. E. Shapiro), Lecture Notes in Computer Science, Springer-Verlag, , 1986. 21. L.M. Pereira, F. Pereira and D. Warren, User's Guide to DECsystem-10 Prolog, Laboratório Nacional de Engenharia Civil, Lisboa. 22. D.A. Plaistead, "An Efficient Bug Location Algorithm" in Proceedings of 2nd. Int'l Conf. on Logic Programming (Uppsala, Sweden, 151-157. 23. P. Roussel, Prolog: Manuel de reference et d'utilization, Groupe d'Intelligence Artificielle, Marseille-Luminy. 24. E. Shapiro, Algorithmic Program Debugging, MIT Press,, 1983. 25. M. Weiser, "Programmers Use Slices When Debugging," Communications of the ACM, 25:7, 446-452. |
Declarativa - Serviços de Informática, Lda. |