Implementacao de Linguagens Logicas ----------------------------------- Historico: Pesquisador Local Ano Tipo Tecnica Battani & Meloni Marselha 1973 interpretador compartilhamento de estruturas em Fortran David H.D.Warren Edimburgo 1977 DEC-10 Prolog compartilhamento de estuturas comp. codigo + multiplas pilhas + TRO nativo David H.D.Warren SRI 1983 comp. maquina copia de estruturas abstrata + goal stacking + emulador David H.D.Warren SRI 1984 comp. maquina copia de estruturas abstrata + environment stacking WAM + emulador Implementacaoes baseadas na WAM: Quintus Prolog, Berkeley machine (PLM), NEC machine (HPM), ECRC machine (KCM). Sistemas Prolog comerciais e academicos: SICStus Prolog, Arity Prolog, Mac Prolog, LPA Prolog, SWI Prolog, IC-Prolog, Turbo-Prolog, etc. -- Diferencas entre compilacao Prolog e de linguagens convencionais: -- variavel logica (somente pode assumir um unico valor durante a execucao para a frente). -- backtracking (nao remove espaco na pilha se o backtracking nao for para a ultima clausula do procedimento). -- em programacao imperativa, remove-se o topo da pilha de execucao, na saida de uma chamada (call-empilha, exit-desempilha). Em Prolog, so' ha' desempilhamento na saida do procedimento e nao na saida de uma clausula. WAM (Warren Abstract Machine) ----------------------------- -- Tipos de termos Prolog na WAM: constante (inteiros ou atomos), variavel, estrutura, lista, ponto flutuante. -- Procedimento: conjunto de clausulas com mesmo nome e aridade. +---+---+ -- Representacao de Termos: |TAG| N | +---+---+ +---+---+ . variavel: |VAR|REF|, onde REF pode ser um ponteiro para outra +---+---+ variavel, para uma estrutura ou lista na heap, ou para ela mesma (no caso de ser primeira ocorrencia e nao ter sido instanciada ainda). +---+---+ . constante |CTE| N |, onde N geralmente e' um indice para uma tabela +---+---+ de simbolos (normalmente implementada como uma tabela hash). . estrutura: +---+---+ |STR| P | P aponta para a estrutura +---+---+ +---+---+ P: |FN |ARI| nome do funtor e' encontrado em tabela com +---+---+ indice FN, ARI representa aridade. . lista: +---+---+ |LIS| P | +---+---+ -- Classificacao de variaveis: quanto `a localizacao durante a execucao: -- locais: nao aparecem em termos compostos -- globais: aparecem sempre em termos compostos Ex: p(X,f(X,a),Y). % X e' global, Y e' local quanto ao tempo de vida: -- temporarias: somente aparecem na cabeca e/ou no primeiro literal do corpo da clausula . -- permanentes: podem aparecer na cabeca e a partir do segundo literal da clausula. Ex: d((U*V),X,((DU*V)+(U*DV))) :- d(U,X,DU), % V, X e DV sao permanentes d(V,X,DV). % U e DU sao temporarias quanto `a criacao: -- condicional: criada e nao instanciada antes de um ponto de escolha. Podem receber calores diferentes dependendo das clausulas alternativas do ponto de escolha. -- incondicional: ja' vem instanciada quando o ponto de escolha e' criado. Portanto, nao pode mudar de valor. -- Componentes da maquina: - Conjunto de instrucoes - Conjunto de registradores - areas de memoria: -- codigo + dados -- pilha local armazena informacoes de gerenciamento de ambientes e pontos de escolha e variaveis locais -- Heap (global) armazena estruturas (termos compostos) e variaveis que aparecem em estruturas (globais) -- trilha (trail) armazena enderecos de variaveis condicionais que precisam ser "de-instanciadas" quando ocorre a falha de alguma clausula de um procedimento. - algoritmos: desreferenciamento, unificacao e backtracking -- Compartilhamento de Estruturas Estruturas nao sao copiadas para a heap, apenas variaveis. Ha' ponteiros do ambiente de execucao para a area de codigo. -- Copia de estruturas: nao ha' ponteiros do ambiente de execucao para a area de codigo. -- Compartilhamento x Copia de Estruturas: Compartilhamento gasta menos espaco, mas pode perde em localidade, por causa das cadeias de ponteiros. Copia gasta mais espaco, mas pode ganhar em localidade. -- Goal Stacking: -- Registradores: P contador de programa (aponta para o codigo) CP ponteiro de continuacao (aponta para o codigo) E topo da local (pilha de ambientes) B aponta para o ultimo ponto de escolha criado na pilha local TR aponta pata o topo da trilha H topo da heap HB aponta para o ultimo ponto de escolha criado na heap S aponta para estrutura na heap sendo unificada Xi armazena ponteiros para argumentos de segundo nivel em diante Ai armazena ponteiros para argumentos de primeiro nivel Yi armazena ponteiros para variaveis locais -- Conjunto de instrucoes: Controle: allocate usada para alocar espaco para variaveis locais call P/n, N desvia para label P/n indicando que ha' N variaveis locais execute P/n desvia para label P/n Instrucões para argumentos na cabeca da cláusula: ------------------------------------------------ Unificacao de nivel 0: get_variable Ri,Aj cria um slot para variavel na heap (se Ri for Xi) ou na local (se Ri for Yi), desreferencia o que vem em Aj e unifica com Ri get_value Ri,Aj desreferencia Ri e Aj e unifica Ri com Aj get_constant c,Ai desreferencia Ai e unifica com c get_structure F/n,Ai desreferencia Ai e unifica com F/n ---------------------------------------------------------- Unificacao de nivel maior ou igual a 1: unify_variable Ri desreferencia o que e' apontado por S, cria slot na heap, faz Ri apontar para la', unifica S com Ri unify_constant c desreferencia o que e' apontado por S, unifica com c unify_structure F/n desreferencia o que e' apontado por S, unifica com F/n e chama o algoritmo de unificacao Instrucões para argumentos de predicados no corpo da cláusula: --------------------------------------------------------------- Instrucoes PUT: transfere valores de argumentos para registradores put_variable Ri,Aj put_constant c,Aj put_structure F/n,Aj Instrucoes *_variable sao geradas para a primeira ocorrencia de uma variavel. As demais ocorrencias sao traduzidas por *_value. Instrucoes *_constant sao geradas quando constantes sao encontradas no codigo. Instrucoes *_structure sao geradas quando encontramos termos compostos de primeiro ou maior que segundo nivel no codigo. Instrucoes de pontos de escolha: geradas na entrada de cada clausula de um procedimento e somente executadas se o argumento real for desreferenciado como sendo uma variavel (neste caso, nao da' para indexar e desviar direto para uma clausula especifica). try_me_else L retry_me_else L trust_me Instrucoes de Indexacao: primeiro nivel: switch_on_term Lv,Lc,Ll,Ls desreferencia registrador A1 (primeiro argumento). Se for -- variavel, desvia para Lv -- constante, desvia para Lc -- lista, desvia para Ll -- estrutura, desvia para Ls segundo nivel: switch_on_constant N, {c1:L1, c2:L2,...,cn:LN} switch_on_structure N, {s1:L1, s2:L2,...,sn:LN} terceiro nivel: try L retry L trust L Instrucoes de indexacao sao geradas pelo compilador, apos este ter gerado codigo para todas as clausulas de um procedimento. Somente neste momento, e' possivel verificar como fazer a indexacao dependendo do valor do primeiro argumento. Indexacao tb pode ser feita atraves de dois ou mais argumentos. Modos de Escrita e Leitura nas instrucoes de unificacao: ------------------------------------------------------- -- Leitura: para unificacao de estrutura ja' existente. -- Escrita: para construir uma nova estrutura. Em modo leitura: unify_variable X X := prox. arg. de S unify_value X unifica X com prox. arg. de S unify_constant C unifica C com prox. arg. de S Em modo escrita: unify_variable X X := ref. para prox. arg de H := indefinido unify_value X prox. arg. de H := X unify_constant C prox. arg. H := C Formato geral de traducao de Prolog para WAM: -------------------------------------------- p :- q, r, s. p :- q allocate get args de p get args de P put args de q put args de q execute q call q, n put args de r p. call r, n1 put args de s get args de P deallocate proceed execute s Compilacão especializada para cada cláusula para permitir otimizacões: Ex: concat([X|L1],L2,[X|L3]) :- ... Term := Arg[1]; if Term é uma lista não vazia X := Term[1]; L1 := Term[2]; else if Term é uma variável Term é inicializado com uma estrutura de lista; X := Term[1] := unbound; L1 := Term[2] := unbound; else fail; L2 := Arg[2]; Term := Arg[3]; if Term é uma lista não vazia unifica X com Term[1]; L3 := Term[2]; else if Term é uma variável Term é inicializado com uma estrutura de lista; Term[1] := X; L3 := Term[2] := unbound else fail Exemplos: -------- Familia: ------- gf(X,Z) :- parent(X,Y), parent(Y,Z). parent(joao,maria). parent(joao,jose). parent(jose,maria). ?- gf(joao,X). consulta/0: allocate % codigo da consulta put_constant joao,A1 % gf(joao, put_variable Y1,A2 % X call gf/2,1 % proceed % ). parent/2: parent/2_1: try_me_else parent/2_2 % codigo do primeiro fato get_constant joao, A1 get_constant maria, A2 proceed parent/2_2: retry_me_else parent/2_3 % codigo do segundo fato get_constant joao, A1 get_constant jose, A2 proceed parent/2_3: retry_me_else parent/2_3 % codigo do terceiro fato get_constant jose, A1 get_constant maria, A2 proceed gf/2_1: allocate get_variable Y1,A1 get_variable Y2,A2 put_value Y1,A1 put_variable Y3,A2 call parent/2,2 put_value Y3,A1 put_value Y2,A2 deallocate execute parent/2 Estruturas: ----------- ?-p(Z,h(Z,W),f(W)). % primeiro nivel: A1 = Z, A2 = h(Z,W), A3 = f(W), % segundo nivel: X4 = Z, X5 = W p(f(X),h(Y,f(a)),Y). % primeiro nivel: A1 = f(X), A2 = h(Y,f(a)), A3 = Y % segundo nivel: X4 = X, X5 = Y, X6 = f(a) % terceiro nivel: X7 = a consulta/0: put_variable X4,A1 % p(Z, Z foi renomeada para X4 put_structure h/2,A2 % h set_value X4 % (Z, set_variable X5 % W), put_structure f/1,A3 % f( set_value X5 % W call p/3,0 % ). p/3: get_structure f/1,A1 % p(f unify_variable X4 % (X), get_structure h/2,A2 % h unify_variable X5 % (Y, unify_variable X6 % X6), get_value X5,A3 % Y), get_structure f/1,X6 % X6 = f unify_variable X7 % (X7) get_structure a/0,X7 % X7 = a proceed Concatenacao de listas: ---------------------- app([],L,L). app([X|L1],L2,[X|L3]) :- app(L1,L2,L3). app/3: switch_on_term C1a,C1,C2,fail C1a: try_me_else C2a % app( C1: get_constant nil,A1 % [], get_value A2,A3 % L, L proceed % ). C2a: trust_me % app( C2: get_list A1 % [ unify_variable X4 % X| unify_variable A1 % L1], L2, get_list A3 % [ unify_value X4 % X| unify_variable A3 % L3]) :- execute app/3 % app(L1,L2,L3). NB: Este codigo esta' extremamente otimizado. Notem que algumas instrucoes que seriam normalmente geradas sem otimizacao nao aparecem neste codigo. Quicksort: --------- qs([],R,R). qs([X|L],R0,R) :- split(L,X,L1,L2), qs(L1,R0,[X|R1]), qs(L2,R1,R). qs/3: switch_on_term C1a,C1,C2,fail C1a: try_me_else C2a % qs( C1: get_constant nil,A1 % [], get_value A2,A3 % R, R proceed % (. C2a: trust_me % qs( C2: allocate get_list A1 % [ unify_variable Y6 % X| unify_variable A1 % L], get_variable Y5,A2 % R0, get_variable Y3,A3 % R) :- put_value Y6,A2 % split(L,X, put_variable Y4,A3 % L1, put_variable Y1,A4 % L2 call split/4,6 % ), put_unsafe_value Y4,A1 % qs(L1, put_value Y5,A2 % R0, put_list A3 % [ unify_value Y6 % X| unify_variable Y2 % R1] call qs/3,3 % ), put_unsafe_value Y1,A1 % qs(L2, put_value Y2,A2 % R1, put_value Y3,A3 % R deallocate execute qs/3 % ). NB: Novamente este codigo esta' extremamente otimizado, inclusive minimizando numero de registradores utilizado. A instrucao put_unsafe_value e' utilizada para salvar as variaveis locais do ambiente corrente na heap por causa de uma futura reutilizacao de espaco (execute, ultimo objetivo pode reutilizar o ambiente corrente).