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 1Seznamu je třeba rozumět takto: dvakrát byla v programu volána procedura
prolez/2
,+/2
bylo jednou použito jako funktor struktury, procedurainfinity/2
byla jednou definována, procedurainfitity/2
byla jednou volána, atd.Shodou okolností již z tohoto seznamu programátor ukázky pozná překlep ve funktoru
infinity
(voláno jakoinfitity
). 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ů).
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.
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.
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í funktoris
, který do volné proměnnéOutVar
vkládá aritmetickou hodnotu termuInTerm
, 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.
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ů.
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.
learnterm
learnterm
dostane funktor, aritu, seznam argumentů a kontext, v němž byl funktor použit (tj. volání, definice nebo struktura, jak je vysvětleno výše). Do slovníku přičte jedničku ke klíči Funktor/Arita/Užití
a pokračuje na argumenty funktoru, obvykle se změnou kontextu pro argumenty.
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).
Požadavek na interně definovaný funktor | Co si program skutečně zapamatuje |
---|---|
definujF1/arity :- F2/arity.
| F1/arity definovánoF2/arity použito:-/2 pokládám za interní funktor definice
|
použij ... F1/arity , F2/arity ...
| F1/arity použitoF2/arity použito,/2 pokládám za interní funktor řetězení cílů
|
struktura ... F1/arity , F2/arity ...
| F1/arity ve struktuřeF2/arity ve struktuře,/2 pokládám za interní funktor řetězení argumentů funktorů struktury
|
struktura ... .(F1/arity, F2/arity) ...
| F1/arity ve struktuřeF2/arity ve struktuře,/2 pokládám za interní funktor seznamu
|
... |
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.
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
).
Concorde je k dispozici zde:
concorde.pl