StructSheet - jazyk na popis tabulek ------------------------------------ Motivace: Programátoři stále dokola píší různé varianty kódů, které někde získají data a vyprodukují nějakou tabulku. Připravme nástroj, kterému se pouze popíše, *jak* má tabulka vypadat a *kde* se berou data, a nástroj sám napíše hledaný program, program generující z daných zdrojů danou tabulku. Příklad: Chceme vytvářet tabulku, kde pro dané IP a daný den bude uvedeno, kolik hitů toto IP udělalo na našem serveru. Později si zadavatel vzpomene, že k počtu hitů je třeba uvést též procento denní zátěže serveru a pod tabulku údaj s celkovou zátěží. den1 den2 ... den31 IP1 hitů (%) hitů (%) ... hitů (%) IP1 hitů (%) hitů (%) ... hitů (%) ... ... ... ... ... IPn hitů (%) hitů (%) ... hitů (%) Celkem hitů (100 %) hitů (100 %) ... hitů (100 %) Přitom IP a hity se berou z databáze a dny jsou pro jednoduchost příkladu pevně dány. Popis pomocí structsheetu má dvě oddělené části. První říká, jaké údaje tabulka potřebuje (a kde je bere), a druhá část říká, jak se tyto údaje mají poskládat na *rovinu* papíru/HTML/textu. Kompilátor tento dvoufázový popis převede na kód, např. v Perlu nebo Javě. Po spuštění kódu se provede sběr dat, získají a dopočtou se všechny potřebné údaje, a nakonec se údaje vykreslí v požadovaném formátu na rovinu papíru. 1. Jaké údaje tabulka potřebuje Popíšeme *stromovitou datovou strukturu*, konkrétní údaje v této struktuře se naplní až při získání dat ze zdroje. Aby bylo možné popsat tabulku obecněji, musíte začít uvažovat v jednorozměrných seznamech, místo ve dvojrozměrných tabulkách. V naší tabulce jsou dva hlavní seznamy: seznam IP a seznam dní. Kořen naší stromovité struktury bude tedy obsahovat právě tyto dva seznamy: root: @ips, @days. Seznam IP adres je jednoduchý. Každá jeho položka je struktura s jedinou proměnnou 'ip' obsahující konkrétní adresu. Seznam IP adres je tak dlouhý, kolik IP adres jsme získali dotazem do databáze. Strukturu seznamu @ips tedy popíšeme takto: (detaily syntaxe jindy) ips: generator sql( ip = "select ip from ..." ). Seznam dní bude složitější. Pro každý den budeme uchovávát nejen pořadové číslo dne (1 až 31, tj. celkem 31 položek v seznamu dní), ale též seznam hitů, které jednotlivé IP adresy na našem serveru vykázaly. days: generator day = 1..31, @hits. Pro další pochopení si tedy naši výslednou tabulku musíte představit takto "uzávorkovanou": Na stejné úrovni jsou seznam IP a seznam dní. V každé položce seznamu dní je pak jako vnořená struktura seznam hitů. (Závorkování šlo udělat i opačně: Jednoduchý seznam dní a na stejné úrovni seznam IP. V každé položce seznamu IP pak seznam hitů, které toto IP v jednotlivých dnech vygenerovalo.) +---------------------------------------------------------------+ | den1 den2 ... den31 | +---+ | +--------+ +--------+ +--------+ | |IP1| | |hitů (%)| |hitů (%)| ... |hitů (%)| | |IP1| | |hitů (%)| |hitů (%)| ... |hitů (%)| | |...| | |... | |... | ... |... | | |IPn| | |hitů (%)| |hitů (%)| ... |hitů (%)| | +---+ | +--------+ +--------+ +--------+ | Celkem | hitů hitů ... hitů | +---------------------------------------------------------------+ V kýžené dvourozměrné tabulce je však něco navíc: je zde vyjádřena vazba mezi hity v daném dni a IP adresou, která tyto hity způsobila -- vodorovné řádky sedí. Ve structsheetu říkáme, že seznam hitů (pro kterýkoli den) je *závislý*, nebo *řízen* seznamem IP adres. Je tedy stejně dlouhý jako seznam IP adres. Seznam hitů tedy není generován, ale je odvozen, ovládán (controlled) seznamem ips, který lze v hierarchické struktuře structsheetu najít na kořenové úrovni, nebo lépe: o dvě úrovně výš pod názvem ips. (Oddělovačem není jako u adresářové struktury znak /, ale dvojtečka :.) hits: controlled ..:..:ips hit = ... perc = ... output = concat( hit, " (", perc, "%)" ) Ve struktuře položky seznamu hits, jak jsme ji právě definovali, jsme zároveň naznačili, že tu bude proměnná hit obsahující počet hitů (které v daném dni dané IP provedlo) a procento z celkového počtu hitů. Konečně si předpočítejme, jak bude vypadat finální výstup z této struktury: bude to zřetězení absolutního počtu hitů a procenta, ovšem uvedeného v závorce. Jak ale získat hodnoty proměnných hit a perc? hit = sql("select count(*) from ... where ip = ..:..:ips:ip and day = ..:day") Dotaz SQL nyní použijme jako *operátor*, nikoli generátor (měl by tedy pro daný vstup vrátit právě jeden řádek výstupu). Vstupem SQL dotazu je jednak "daný den", tj. ta hodnota, která je ve struktuře uložena o úroveň výš, v položce den, a jednak "daná IP adresa", tj. ta adresa, která je uložena v položce ip *odpovídajícího záznamu* seznamu ips, který je definován na kořenové úrovni. O "odpovídajícím" záznamu můžeme hovořit jen díky tomu, že je tento seznam definován jako odvozenina seznamu ips. Právě zde je tedy vyjádřena ta vazba, kterou v dvojrozměrné tabulce vyjádříme zapsáním údajů na stejné vodorovné úrovni, na jednom řádku. A jak se počítá procento? Počet hitů z daného IP lomeno počtem hitů celkem za daný den, krát 100. hits: perc = hit / ..:total_hits_in_day * 100 Počet hitů celkem za daný den samozřejmě nemůžeme uchovávat v proměnné *v rámci jedné položky seznamu hitů v daném dni*, protože je to údaj popisující seznam hitů v daném dni jako celek. Připravme si proto tuto hodnotu "o úroveň výš", již v položce seznamu dní: days: ... total_hits_in_day = sum(hits, hit) Celkový počet hitů v daném dni se počítá snadno: jde o součet proměnných 'hit' ve všech položkách seznamu hits. Povšimněte si toho, že ve struktuře jste udělali špagety tam a zpět. Kompilátor za vás tyto špagety narovná: "napřed" vygeneruje pro každý den seznam hitů z různých IP adres v tomto dni, "potom" spočítá součet hitů ze všech IP adres, a "nakonec" dopočte procento příspěvků jednotlivých IP adres k celkovému počtu hitů v daném dni. Právě tohle kompilátor řeší. Celkem tedy potřebné údaje pro tabulku (a též pomocné údaje) popíšeme ve struktuře: root: @ips, @days. ips: generator sql( ip = "select ip from mytable1" ). days: generator day = 1..31, @hits, total_hits_in_day = sum(hits, hit). hits: controlled ..:..:ips, hit = sql("select count(*) from mytable2 where ip = ..:..:ips:ip and day = ..:day"), perc = hit / ..:total_hits_in_day * 100, output = concat( hit, " (", perc, "%)" ). Kód vytvořený kompilátorem pracuje, jak jsme již naznačili, dopočítáváním toho, co už dopočítat může, rozvíjením seznamů, které už rozvinout může. (I generátor seznamu se může opírat o nějakou proměnnou, kterou je třeba napřed vypočíst.) Až výpočet doběhne, bude mít program v paměti strukturu seznamů struktur a konkrétních hodnot. Tuto strukturu je třeba napsat na papír. 2. Jak strukturu vykreslit Musíme uvést, které části stromové struktury chceme vypsat. Zapíšeme to výrazem, který se opírá o strukturu dat: layout = ( nil \/ fold( \/, ips, ip) \/ "Celkem" ) > fold( >, days, day \/ fold( \/, hits, output) \/ total_hits_in_day ) nil je tabulka o jediné prázdné buňce \/ je operátor "tabulky pod sebe" > je operátor "tabulky vedle sebe" "Celkem" je buňka, v níž je vypsán řetězec "Celkem". day je buňka, v níž je vypsána hodnota proměnné day ap. fold( Operátor, Seznam, PředpisVýstupu ) je funkce vracející tabulku, která vznikne, když každý prvek seznamu Seznam zobrazíme podle PředpisuVýstupu a výsledné dílčí výstupy spojíme operátorem Operátor (pod/vedle sebe). Jak je z příkladu zřejmé, Předpis vnořeného výstupu může samozřejmě rekurzivně obsahovat další fold ap. Další dodatky ke structsheetu: - syntax požadavků na setřídění seznamů (spojené seznamy, controlled lists, se třídí paralelně, tj. "řádky" tabulky se drží pohromadě) - "prohazování sum" - generování výběrů ze seznamu, například limit, nebo where (nejde o nic jiného, než o nový seznam na stejné úrovni hierarchické struktury, jehož generátor se opírá a seznam, nikoli pouze o hodnoty) - načítání dat ze strukturovaného dokumentu, podle layoutu - podmíněný výstup v layoutu (např. řádek "Ostatní" uvádět jen pokud nějací ostatní jsou) Interní poznámky: ----------------- Příklad, námět syntaxe pro "limit": stejná tabulka, ale chceme uvést jen prvních pět konkrétních IP adres (pro jednoduchost je nám jedno, které to budou), procenta však chceme dopočítat normálně, z celku, a Celkem taky. Uděláme to tedy tak, že ze seznamu IP a seznamu hitů v rámci každého dne prostě zkopírujeme prvních pět záznamů do seznamů limited_ips/hits. Celá struktura ips resp. hits. už tou dobou musí být dopočtena, tj. i procenta. Řešení má především nevýhodu horší efektivity -- nemusel jsem detailně generovat pro všechna IP, když mi šlo jen o součet. Ovšem optimalizace tohoto druhu je už hodně drsná. root: @ips, @days, @limited_ips = limit(ips, 5). ### Nový řádek days: generator day = 1..31, @hits, @limited_hits = limit(hits, 5), ### Nový řádek total_hits_in_day = sum(hits, hit). hits: controlled ..:..:ips, hit = sql("select count(*) from mytable2 where ip = ..:..:ips:ip and day = ..:day"), perc = hit / ..:total_hits_in_day * 100, output = concat( hit, " (", perc, "%)" ). ### V layoutu jsou taky jen 2 malé změny. layout = ( nil \/ fold( \/, limited_ips, ip) \/ "Celkem" ) > fold( >, days, day \/ fold( \/, limited_hits, output) \/ total_hits_in_day ) Příklad, námět syntaxe pro "ostatní": stejná tabulka, jen 5 IP adres, chceme řádek "ostatní" ve tvaru jako u jednotlivých IP. Samozřejmě můžeme přidat: days: ostatni = total_hits_in_day - limited_hits_in_day limited_hits_in_day = sum(limited_hits, hit) A kapičku komplikovanější layout: layout = ( nil \/ fold( \/, limited_ips, ip) \/ "Ostatní" \/ "Celkem" ) > fold( >, days, day \/ fold( \/, limited_hits, output) \/ ostatni \/ total_hits_in_day ) Toto řešení je vlastně docela chytré, ne vždy je však možné (použitelnost závisí na možnosti udělat rozdíl, odečíst od celku). Obecné řešení už spadá do oblasti filtrů na seznamy a ty si ještě musím rozmyslet. Prohození sum: Chtějme tabulku, kde bude také součet v řádku -- kolik hitů celkem udělalo dané IP ve všech dnech. root: @ips, @days. ips: generator sql( ip = "select ip from ..." ), total_hits_for_ip = sum(..:days, "hits:hit"). days: generator day = 1..31, @hits, total_hits_in_day = sum(hits, hit). hits: controlled ..:..:ips, hit = sql("select count(*) from mytable2 where ip = ..:..:ips:ip and day = ..:day"), perc = hit / ..:total_hits_in_day * 100, output = concat( hit, " (", perc, "%)" ). V příkazu sumace se udává napřed, podle jakého seznamu se má sčítat. Logicky tento seznam musí být dohledatelný, tj. cesta k němu musí být zcela řízená. Naopak sám tento seznam již řízený být nesmí, jinak není podle čeho sčítat. Ve výrazu, který je pak pro každý prvek sčítaného seznamu vyhodnocován, se mohou objevit i proměnné hlouběji ve struktuře, ale musejí být již řízeny. Trik na prohození dvou sum: *oba indexy musejí být definovány již na společné kořenové úrovni* Ověření, že sum(a in A, sum(b in B, a*b)) = sum(b in B, sum(a in A, a*b)) realizujeme takto: root: @As, @Bs, % indexové množiny pro A a B @ABelems, % seznam pro sčítání prvním způsobem ABsum = sum(ABelems, sumb), % výsledek prvním způsobem @BAelems, % seznam pro sčítání druhým způsobem BAsum = sum(BAelems, suma). % výsledek druhým způsobem As: generator a = 0..10 Bs: generator b = 0..20 ABelems: controlled ..:As @Belems, sumb = sum(Belems, val). Belems: controlled ..:..:Bs val = ..:..:Bs:b * ..:..:As:a BAelems: controlled ..:Bs @Aelems, suma = sum(Aelems, val). Aelems: controlled ..:..:As val = ..:..:Bs:b * ..:..:As:a Stejným způsobem lze realizovat prohození libovolného počtu sum. Trikem je umístit všechny indexové množiny na jedné společné hladině.