Concorde

(Analýza prologového programu)

Co program dělá

Concorde tedy zpracuje prologovský program do přehledného seznamu užitých funktorů roztřízených podle jména, arity a výskytu funktoru - zda byl užit jako volání vnořené procedury, zda je právě definován, nebo zda se příslušný funktor používá ve struktuře. Nejlépe toto rozlišení vysvětlí příklad:

Ukázkový vstup:

pravoúhlý(3, 4, 5).              % pravoúhlý je zde v definici
                                 % konstanty 3, 4, 5 a funktor `,' jsou
                                 % chápány jako součást Prologu a
                                 % nepočítají se tedy
infinity(Beg, Inf) :-            % infinity je v definici
   Beg1 is Beg+1,
   infitity(Beg, Inf).           % infinity je ve volání
prolez( strom(T1, U, T2) ) :-    % prolez v definici a strom ve struktuře
   prolez(T1),                   % prolez ve volání
   prolez(T2).                   % prolez ve volání

A výstup programu (při třídění seznamu podle počtu výskytu příslušně použitého funktoru):

Načítám: sample.pl
Třídím slovník...
Funktor             AritaPoužití   Počet
prolez              1    volání    2
+                   2    struktura 1
infinity            2    definice  1
infitity            2    volání    1
is                  2    volání    1
pravoúhlý           3    definice  1
prolez              1    definice  1
strom               3    struktura 1

Seznamu je třeba rozumět takto: dvakrát byla v programu volána procedura prolez/2, +/2 bylo jednou použito jako funktor struktury, procedura infinity/2 byla jednou definována, procedura infitity/2 byla jednou volána, atd.

Shodou okolností již z tohoto seznamu programátor ukázky pozná překlep ve funktoru infinity (voláno jako infitity). Ještě nápadnější by překlep byl, kdyby byla procedura infinity kromě své definice a zkomoleného volání užita i ve volání zapsaném správně - pro daný funktor by ve výsledném seznamu figurovaly tři řádky (definice, správné volání, zkomolené volání), ačkoli programátor očekává jen dva (definice + volání).

Rád bych zdůraznil, že počet výskytů se počítá nezávisle nejen pro funktory týchž jmen a různých arit, ale též pro různé kontexty použití (volání/definice/struktura) funktoru daného jména a arity. V typickém nezkomoleném programu se tedy funktor dané arity vyskytne v seznamu dvakrát - jednou v definici (zřejmě s nižším počtem výskytů) a jednou ve volání (zřejmě s vyšším počtem výskytů).

Omezení programu

Concorde při načítání vstupu ze souboru používá běžný prologovský predikát read, jehož výstupem je syntakticky správný term. Read tedy samozřejmě předpokládá syntaktickou správnost vstupního souboru.

Další omezení vyplývá opět z použití vestaveného read: jména proměnných jsou z hlediska systému Prologu nevýznamná a read je tedy ihned nahrazuje interní číselnou reprezentací. Concorde se tak nedostane původním k názvům proměnných, a neumožní tedy odhalovat překlepy v nich.

Ovládání programu

Concorde se spouští predikátem concordefile nebo concordelist na vstupní soubor (prologovský program) nebo prologovský seznam termů.

Concorde vstup načte do interní reprezentace a vytiskne utřízený seznam funktorů. Další analýza výstupu tak zůstává na uživateli.

Přizpůsobivost chování programu

Snadno lze v proceduře zpracujslovnik určit, podle čeho se má výstupní slovník funktorů utřídit:

zpracujslovnik(Slovnik) :-
  write('Třídím slovník...'),nl,
  quicksort(Slovnik, Setrizeny, byUsage),
  ...

Předem jsou připraveny metody byUsage (třídí nejprve sestupně podle počtu výskytů a dále abecedně podle jmen funktorů, jejich arit a kontextu použití) a byFunctor (třídí jen abecedně podle jmen funktorů, jejich arit a kontextu použití).

Další změny jsou možné v proceduře learnterm, která zpracovává jednotlivé termy a zvažuje, zda je zařadit do slovníku, nebo je považovat za vestavěnou součást Prologu. (Díky tomu např. ve výstupu nefiguruje užití funktoru `:-' v programu).

Například kdybychom chtěli nepočítat výskyty vestavěného is, připojíme do procedury learnterm následující klauzuli:

% learnterm(+Func, +Arity, +Args, +Usage, +Slovnik0, -Slovnik1)

learnterm( is, 2, [OutVar, InTerm], use, Slovnik0, Slovnik2) :-
% learnterm(OutVar, struct, Slovnik0, Slovnik1),
  learnterm(InTerm, struct, Slovnik1, Slovnik2).

Slovy: máš-li se naučit (tj. připočíst výskyt) binární funktor is, který do volné proměnné OutVar vkládá aritmetickou hodnotu termu InTerm, neuč se samotné is (jak by učinila implicitní větev procedury), ale zpracuj samostatně výstupní proměnnou a vstupní term, jako by se vyskytly ve struktuře. A jelikož víme, že se do slovníku volné proměnné tak jako tak nepřidají, můžeme zpracování výstupní proměnné rovněž vynechat.

Jak program pracuje uvnitř

Datové struktury programu

Během načítání vstupního programu potřebujeme zaznamenávat, kolikrát se v programu vyskytl nějaký funktor (k jehož základní charakterizaci patří kromě jména též arita) v definici, ve volání a ve struktuře. Nejjednodušší je tedy pro každou trojici funktor/arita/použití počítat výskyty pomocí asociativní paměti, která této trojici přiřazuje číselnou hodnotu.

Jako slovník tedy slouží asociativní paměť pro začátek uložená v bežném seznamu. V celém zbytku programu se ke slovníku přistupuje výhradně pomocí speciálních predikátů, a bylo by tedy velmi snadné nahradit interní prostý seznam dvojic assoc(jméno,údaje) nějakou chytřejší strukturou asociací.

Nejvýznamnější z procedur pro správu slovníku je predikát freeassoc, který najde hledaný klíč ve slovníku a vrátí jako nový slovník kopii, v níž je na místě dat nalezeného klíče uložena vstupní proměnná NewData (její obsah nebo její reference, je-li dosud proměnná volná).

K slovníkovým operacím je pro potřeby výstupu přiřazen predikát quicksort, který přirozeně slovník utřídí. Je to ten chytřejší quicksort bez lineárního plýtvání na spojování seznamů.

Načítání vstupu

V proceduře loadfile jsou klauzule ze vstupu postupně načítány do slovníku. Není-li dosud načten znak konce souboru, je právě načtený term přidán do slovníku pomocí procedury learnterm a rekurentně se zavolá načtení zbytku souboru pomocí procedury loadterms. V akumulátoru procedur se tak sbírá slovník vstupního programu.

Aby interpret neplýtval paměť na potenciální zpětný průchod procedurami, je po každém úspěšném načtení a zpracování termu použit řez.

Prolézání termu - procedura learnterm

Několik samostatných predikátů procedury learnterm ošetřuje konstanty a interně definované funktory Prologu . Chování následujícího výseku klauzulí programu vysvětluje tabulka:

learnterm( Naboditko, 2, [DefT, UseT], def, Slovnik0, Slovnik2) :-
% zpracuj definici pomocí pravidel
  name(Naboditko, ":-"),
  learnterm(DefT, def, Slovnik0, Slovnik1),
  learnterm(UseT, use, Slovnik1, Slovnik2).

learnterm( ',', 2, [Use1, Use2], Usage, Slovnik0, Slovnik2) :-
% zpracuj posloupnost cílů spojených logickým AND nebo obě složky struktury
% funktor čárka se zkrátka neuč nikdy
  learnterm( Use1, Usage, Slovnik0, Slovnik1),
  learnterm( Use2, Usage, Slovnik1, Slovnik2).

learnterm( '.', 2, [Eq1,Eq2], struct, Slovnik0, Slovnik2) :-
% zpracuj seznam, neuč se funktor seznamu
  learnterm( Eq1, struct, Slovnik0, Slovnik1),
  learnterm( Eq2, struct, Slovnik1, Slovnik2).

Závěrečný výpis slovníku

Při závěrečném výstupu slovníku na obrazovku se opakovaně volá na slovník predikát chop, který odebere první prvek a vrátí též zkrácený slovník. (Kdyby byl slovník třeba binární vyhledávací strom, nedělal by quicksort nic, ale chop by jen ve stromě našel první (nejlevější) prvek a případně strom přesypával).

Každý prvek slovníku je pak vytištěn na obrazovku v zarovnání do pěkných sloupečků, jak je vidět v úvodní ukázce.

Další možná vylepšení programu

Díky důslednému užívání přístupových procedur si lze si více vyhrát s reprezentací asociativní paměti (slovníku), aniž by bylo nutné měnit zbytek programu.

Naopak lze mechanismus asociativního slovníku jako sčítačky výskytů užít na konkordanci jiných dokumentů, třeba slov v obyčejném textu nebo slov v prologovém programu (což by zahrnulo i kontrolu jmen proměnných, které dosud dosahu programu unikají z důvodu užití vestavěného read).

Download

Concorde je k dispozici zde:

concorde.pl

http://www.cuni.cz/~obo/skola/concorde/