Vlastnosti operátorové notace

Už jsme si zvykli na to, že při definicích parserů lze používat namísto standardního zápisu predikátů notaci operátorovou. Stejně jako u všech ostatních námi definovaných operátorů, i v případě operátoru :-> bylo hlavní motivací pro jeho zavedení umožnit pohodlnější a přehlednější zapisování parserů. Operátorová notace tohoto predikátu nám však navíc umožní práci parserů zefektivnit.

V parserech, které jsme dosud vytvořili, vystupoval :-> vždy jako predikát v operátorové notaci, jenž v rámci svého volání svazuje parser s vstupně/výstupním termem a provádí jeho aplikaci. Cílem této části je ukázat, že po vhodném rozšíření knihovny nebude volání predikátu :-> v určitých případech vůbec nutné.

Myšlenkou výše zmíněného zlepšení je návrh použít operátor :-> nikoli jako cíl, ale pouze jako funktor vytvářející term a to vše při zachování možnosti operátorového zápisu konstruktorů.

Způsob, jakým této úpravy dosáhnout, si demonstrujme na příkladu mutátoru <**> pro iterovanou aplikaci daného parseru:

<**>(P,W):-
 W :->
        ((P <&> P<**>)
          <:>
         epsilon).

Přepis těla mutátoru vzhledem k definicím priorit použitých operátorů by vypadal takto:

 :->( W, 
      <:>( <&>( P, 
                <**>(P)), 
           epsilon))

Pokud odstraníme uzávorkování parseru z těla definice mutátoru -- bude interpretován odlišně:

W :->
(P <&> P<**>)
<:>
epsilon

$\Rightarrow$

<:>( :->( W,
<&>( P,
<**>(P))),
epsilon)

Operátor :-> zde vystupuje jako funktor struktury, který svazuje vstupně/výstupní term s prvním parserem v alternativní kompozici. Přestává tedy být cílem a ukazuje se, že by mohl být schopen za určitých okolností plnit svou úlohu staticky. Tento odlišný způsob interpretace nás přivádí k myšlence zavedení další varianty kombinátoru alternativní kompozice:

% I+L :-> P1<:>P2
<:>(I+L :-> P1,P2) :-	
        I+L1 :-> P1,
        I+L2 :-> P2,
        append(L1,L2,L).

Co jsme výše uvedeným postupem vlastně získali? Odpoví nám na to inovovaná definice mutátoru:

<**>(P,W):-
 W :->
        (P <&> P<**>)
          <:>
         epsilon.

Z definice je vidět, že při zachování původního způsobu zápisu nyní v každé iteraci ubylo jedno volání predikátu :->. Volá se totiž místo něj a kombinátoru <:>/3 pouze nová verze <:>/2. Díky tomu dojde k nezanedbatelnému zrychlení.

Stejným způsobem, jakým jsme upravili mutátor pro iterovanou aplikaci parseru <**>, lze upravit samozřejmě nejen ostatní iterátory, ale i konstruktory parserů. Aby to bylo možné, musíme definovat další varianty konstruktorů -- stejně jako v případě kombinátoru <:>. O tom, jaká z verzí toho kterého konstruktoru se použije rozhoduje operátorové okolí :->. Je asi zbytečné zmiňovat, že definování alternativních variant má smysl pouze v případech konstruktorů, jenž jsou definovány rovněž jako operátory. V příkladu další alternativní varianty zůstaňme u našeho mutátoru:

<**>(W :-> P):-
 W :->
        (P <&> P<**>)
          <:>
         epsilon.

Jak si lze povšimnout, arita nově definovaných variant konstruktorů je menší než arita jejich původních definic. Držíme se konvence v níž vstupně/výstupní term již není samostatným argumentem, ale je vždy připojen k prvnímu parametru daného konstruktoru operátorem :->. Díky tomuto jednoznačnému odlišení je volána vždy správná varianta predikátu přímo -- tj. verze s aritou o 1 menší.

V knihovně konstruktorů parserů jsou připraveny alternativní verze všech nejběžnějších kombinátorů a mutátorů, jenž jsou definovány jako operátory. Vnitřně se v jejím jádře využívá takřka výhradně zápis představený v této části, aby bylo dosaženo větší efektivity. Cenou za dosažené zrychlení je nutnost definování alternativních verzí konstruktorů.

Původní verze jsou v knihovně zachovány, aby se programátor nemusel detailně zabývat precedenčními vztahy mezi jednotlivými operátory, je nově zavedená notace navržena tak, aby původní zápis, kdy je parser explicitně uzávorkován, bylo možné použít vždy. Pokud však máme přehled o prioritách operátorů (viz příloha ), můžeme upravit výraz tak, aby se volala efektivnější varianta daného konstruktoru. Nový způsob zápisu parserů ale není možné použít za všech okolností přímo -- někdy je nutné provést explicitní uzávorkování. Rovněž v případech složitějších parserů musí být programátor pozorný, aby byl parser interpretován přesně tak, jak zamýšlel. Ukažme si proto nyní ještě jeden příklad, v němž poukážeme na záludnosti, které použití operátorové notace může skrývat. Zatímco definice klasickým zápisem:

W :->
(P<**> <&> Q <@ F)

$\Rightarrow$

:->( W,
<@( <&>( <**>(P),
Q)
F))

bude v pořádku. Pokud použijeme novou notaci, bude parser interpretován nesprávně:

W :->
P<**> <&> Q <@ F

$\Rightarrow$

<@( <&>(W :-> P<**>,
Q),
F)

Aby byla dodržena konvence, je nutné provést explicitní uzávorkování (podobně jako jsme to učinili v mutátoru <**> v úvodu této části):

W :->
(P<**> <&> Q) <@ F

$\Rightarrow$

<@( W :-> (P<**> <&> Q),
F)

Tato verze je již korektní. Využívá alternativní variantu mutátoru <@, volání :-> již neobsahuje a je tedy efektivnější.

Rozšíření knihovny, které jsme si představili v této části, je spíše technického rázu. Programátor využívající knihovnu nemusí tento způsob zápisu používat a zabývat se precedenčními vztahy operátorů a uzávorkováním, aby jeho parsery byly korektní. Může zůstat u běžné konvence, v níž parser stojí uzávorkován napravo od operátoru :-> -- tak jako tomu bylo v předchozích kapitolách. I když totiž definuje parser obvyklým způsobem a je zavolána standardní verze konstruktoru, z jejího těla se již volání typicky dostává do kódu jádra knihovny a setrvá v něm. Zde se využívají efektivnější verze (jak se lze přesvědčit i na příkladu mutátoru <**>) a ztráta je tedy minimální.

Záleží tedy pouze na programátorovi, zda půjde standardní cestou nebo využije efektivnější, ale záludnosti skrývající notaci.

Pozorný čtenář si jistě také povšiml, že pokud by byla tato úprava dotažena skutečně do krajnosti, mohli by jsme se úplně obejít bez programování vyššího řádu. To by však vyžadovalo změnu celkového návrhu knihovny, nárůst jejího zdrojového kódu a nutnost definovat množství dalších operátorů. Proto se v této práci budeme i nadále držet programování vyššího řádu.