Parsuje výrazy v infixní notaci s podporou uživatelsky definovaných pomocných funkcí a rekurzivních volání.
Schopná z výrazů za běhu generovat CIL kód - běžící přímo na VM a tedy rychle - volatelný skrze delegáta.
Rovněž zahrnuje programovatelný kalkulátor pro příkazovou řádku sloužící jako demo.

• EN verze Readme  

0. Začínáme
   • NuGet balík
   • Jak zkompilovat
   • Jak používat
   • Koncová rekurze
   • Kešování výsledků
1. Výkon
2. Gramatika
   • Bílé znaky
   • Literály a identifikátory
   • Operátory
   • Volání funkcí
   • Kompilační jednotka
     • Anotace
     • Příklady
3. Kompilace
   • Jak definovat operace
     • Rozlišení konstant
     • Validace identifikátorů
     • Definice operátorů
     • Standardní knihovna
     • Registrace NumberOperatoru
   • Kompilační kontext
     • Signatura funkce
     • Správa definic
   • Kompilátor
4. Demo kalkulačka

• Autorům .NET a jazyka C#
• Autorům knihovny ReadLine
• Autorům knihovny CommandLineParser
• Autorům parser-generátoru ANTLR

• Jakub Hroník

Aktuální sestavení je dostupné jak v místních Github Releases, tak na nuget.org:

PM> Install-Package MarkusSecundus.YoowzxCalc

Otevřte solution v MS Visual Studio 2019 aktuální verze a zkompilujte ho. Napříč projektem je hojně využíváno novinek jazyka C# 9 - .NET 5.0 je tedy vyžadován.

Pro přímočaré použití základní funkcionality slouží fasáda YoowzxCalculator.
Ta zaštiťuje celou pipelinu zpracování výrazu - prvotní zparsování textového zápisu na obecný abstraktní syntaktický strom, následnou generaci spustitelného kódu podle AST a zároveň i správu kontextu s funkcemi, které je možné z výrazů volat. Pro každý z těchto segmentů je možné explicitně dodat vlastní implementaci nebo nechat, aby byla použita ta defaultní.

Instanci kalkulátoru počítajícího nad typem double získáme takto:

IYoowzxCalc<double> calc = IYoowzxCalc<double>.Make(); 

V základu lze vytvořit kalkulátor nad typy double, decimal a long. Pro počítání nad jiným typem je třeba explicitní přidání podpory uživatelem (viz níže NumberOperator).

Jakmile máme instanci kalkulátoru, můžeme vesele kompilovat výrazy:

Func<double> f1 = calc.Compile<Func<double>>("1 + 1");
Console.WriteLine(f1()); //vypíše 2

Func<double, double> f2 = calc.Compile<Func<double, double>>("f(číslo) := číslo * (3 + 4 ** 5e-1)");
Console.WriteLine(f2(0)); //vypíše 0

Func<double, double> fibonacci = calc.Compile<Func<double, double>>("fib(x) := x <= 1 ? x : fib(x-1) + fib(x-2)");
for(int t=0;t<10;++t)
    Console.WriteLine(fibonacci(t));    //vypíše prvních 10 fibonacciho čísel

Takto výraz pouze zkompilujeme, ale ať už byl pojmenovaný nebo ne, nikdy nebude přidán jako volatelná funkce do kontextu. (Jeho jméno však pořád má význam když chceme praktikovat rekurzi.)

Máme-li naopak několik výrazů, které chceme zkompilovat a rovnou přidat do kontextu, můžeme použít metodu AddFunctions():

calc.AddFunctions("fib(x) := x<= 1 ? x : fib(x-1) + fib(x-2)",
                  "Pi := 4",
                  "Fib_10 := fib(10)");

Jakmile je funkce součástí kontextu, můžeme ji volat z jiných výrazů.

Někdy by se ale hodilo moci zpřístupnit k volání sofistikovanější funkci definovanou přímo v C#:

calc.AddFunction<Func<double>>("Pi", () => 4)
    .AddFunction<Func<double, double>>("Sin", Math.Sin)
    .AddFunction<Func<double, double>>("Print", x=> { Console.WriteLine(x); return x; });

Jakmile se funkce jednou nachází v kontextu, ať již do něj byla přidána odkudkoliv, dokážeme ji z něj získat:

Func<double, double> f1 = calc.Get<Func<double, double>>("f");
Func<double, double, double> f2 = calc.Get<Func<double, double, double>>("f");

Pozor - Yoowzx podporuje přetěžování funkcí. V tomto případě pro hodnotu f1 bude hledána funkce s názvem "f" a jedním argumentem, pro f2 jiná funkce "f" s dvěma argumenty. Počet argumentů hledané funkce metoda Get() vykouká z typového parametru.

Yoowzx plně podporuje optimalizaci koncové rekurze. Zadefinujeme-li tedy např. takto výpočet faktorialu, pro libovolně vysoké hodnoty argumentu nehrozí přetečení volacího zásobníku:

calc.AddFunctions("fact(x, accumulator) := x <= 1? accumulator : fact(x-1, x*accumulator)",
                  "fact(x) := fact(x, 1)");

calc.Get<Func<double, double>>("fact")(800000); //doběhne bez pádu

Pomocí anotace "cached" lze kompilátoru nařídit, aby volání funkce pro danou hodnotu argumentů provedl jednou, výsledek uložil do keše, a příště ho z ní už jenom tahal.
Tím pádem např. takto definovaná funkce pro výpočet fibonacciho posloupnosti poběží v lineárním čase (resp. konstantním pro opětovná volání):

calc.AddFunctions("[cached] fib(x) := x <= 1 ? x : fib(x-1) + fib(x-2)");

calc.Get<Func<double, double>>("fib")(1000); //doběhne dříve než skončí vesmír

Kešování je podporováno pro všechny funkce bez ohledu na to, jak mnoho argumentů berou.

Současná implementace kešování na funkcích, jež ji využívají, neumožňuje optimalizaci koncové rekurze. Na řešení se pracuje.

V modulu MarkusSecundus.YoowzxCalc.Benchmarks je umístěno pár jednoduchých benchmarků, porovnávajících produkty YC s ekvivalentními lambdami zkompilovanými přímo jako součást C# zdrojáku.
Z výstupu vidíme, že v současné verzi YC sice je nezanedbatelně pomalejší - ve scénářích, kde velkou roli hraje rekurzivní volání (Fibonacci, Factorial) cca 4krát, ve scénářích, kde důraz leží na aritmetice, již jen o cca 25% - pořád ale jde o mnohonásobné zrychlení oproti neJITovaným interpretovaným jazykům (typu CPython apod.).

Referenční výsledky měřeny na stock-taktovaném Core i7 9700KF.

Překlad textově zapsaného výrazu do počítačem přímočaře zpracovatelné formy (AST) je úkolem modulu MarkusSecundus.YoowzxCalc.DSL.
Podmodul MarkusSecundus.YoowzxCalc.DSL.AST obsahuje definici jednotlivých uzlů AST a mašinérii pro jejich zpracování pomocí visitor patternu.
Sestavení AST z textově zapsaného výrazu je úkolem YCAstBuilderu. Jeho kanonická implementace (která respektuje níže popsanou gramatiku) je bezestavový singleton a lze ji získat jako IYCAstBuilder.Instance.
Máme-li tedy textově zapsaný výraz, AST z něj získáme nějak takto:

string expression;
YCFunctionDefinition root = IYCAstBuilder.Instance.Build(expression);

Narazil-li parser na nějakou lexikální či syntaktickou chybu, vyhodí na konci svého běhu výjimku, nesoucí informace o všech chybách, ke kterým v překládaném textu došlo.

Za bílé jsou považovány všechny znaky s ASCII kódem od 0 do ord(' ') včetně. Z hlediska gramatiky jsou ignorovány, slouží jako oddělovač.

Pro větší flexibilitu nejsou na úrovni gramatiky rozlišovány a jejich definice je velmi volná, s cílem umožnit např. zpracování výrazů nad textovými řetězci apod. bez nutnosti gramatiku přepisovat. Jejich validace a rozlišení jsou ponechány na uživateli v rámci pozdějších fází zpracování výrazu (viz níže YCNumberOperator).

Na úrovni AST je reprezentuje uzel YCLiteralExpression.

Literál je libovolně dlouhý řetězec literálových prvků. Literálový prvek matchuje na jeden z těchto regulárních výrazů:

• libovolný_nespecielní_newhitespace_znak //specielní jsou všechny znaky s přiřazenou konkrétní rolí v gramatice - znaky operátorů apod.
• "([^"]|\")" //textový řetězec v uvozovkách - může obsahovat i specielní a bílé znaky; uvozovky též, pokud jsou odescapované
• '([^']|\')' //textový řetězec v apostrofech - může obsahovat i specielní a bílé znaky; apostrofy též, pokud jsou odescapované
• [0-9]+(\.[0-9]*)?([eE][+-]?[0-9]+)? //reálné číslo, volitelně v exponenciální notaci - může obsahovat specielní znak + nebo -

Příkl. literálů:

• 321.092 (řetězec nespeciálních znaků)
• "Toto je text: \"qw\"""Jiný řetězec" (dvojice řetězců hned vedle sebe, neoddělených bílým znakem)
• @'Další exemplář textu: "REwqefds"' (nespeciální znak následovaný řetězcem)
• Abc1e+32"rew " (řetězec nespeciálních znaků následovaný číslem v exp. notaci následovaný řetězcem)

Yoowzx definuje klasicky používané, unární, binární a ternární, aritmetické a logické operátory s obvyklými prioritami a asociativitou. Každému operátoru odpovídá uzel AST, pro vyčerpávající výčet podporovaných operátorů náhlédněte tedy prosím zde:

• Unární operátory
• Binární operátory
• Ternární operátor

Volání funkcí probíhá klasickým způsobem známým např. z jazyka C:
Jméno funkce je libovolný literál, za ním následují kulaté závorky, obsahující příp. jednotlivé argumenty (libovolně složité výrazy) oddělené čárkami.
Na úrovni AST je reprezentováno uzlem YCFunctioncallExpression.

Výstupem kompilace je objekt typu YCFunctionDefinition.
Jeho zápis vypadá nějak takto:

definice_funkce: list_anotací? jméno_funkce '(' seznam_jmen_argumentů ')' ':=' výraz ;

"Jméno funkce" je libovolný literál, "seznam jmen argumentů" je (příp. prázdný) list literálů oddělených znakem , a "výraz" pak libovolně složitý výraz reprezentující tělo definované funkce.
V případě funkce s nulovým počtem argumentů lze příp. prázdné závorky vynechat.
Popř. lze vynechat i jméno funkce s výrazem přiřadítka a zůstat se samotným (volitelně oanotovaným) výrazem - v takovém případě bude jako jméno funkce použita (zaručeně non-null) hodnota YCFunctionDefinition.AnonymousFunctionName.

Někdy se hodí moci k definici funkce přiložit ještě dodatečná data, sloužící např. jako řidicí direktiva pro kompilátor apod. .
List anotací se zapisuje do hranatých závorek a jednotlivé anotace v něm jsou oddělené čárkami. Anotace může být buď prázdná - samotný literál, nebo může mít hodnotu uvozenou dvojtečkou a danou druhým literálem. Gramatika tedy vypadá takto:

list_anotací: '[' anotace (',' anotace)* ']' ;
anotace: LITERÁL | LITERÁL ':' LITERÁL ;

Validní definice která projde parserem může vypadat např. takto:

• f(x) := x*x + 1
• Funkce1(arg1, arg2, arg3, arg4, arg5) := arg1==1? (arg1 + arg2 - (30 - arg1)*arg4)**((arg4)**2.14e-3) : Funkce1(1,1,1,1,arg3)
• f(a, b, a) := a*b*a //parser netestuje duplicitu funkčních argumentů
• [anotace1, anotace2: něco] f() := 1
• [anotace1, anotace2: něco] f := 1
• [anotace1, anotace2: něco] 1
• [cached] ackermann(m,n) := m == 0 ? n + 1 : n == 0 ? ackermann(m - 1, 1) : ackermann(m-1, ackermann(m, n-1))

Jakmile je postaven abstraktní syntaktický strom, nic už nám nebrání začít se zabývat jeho kompilací na spustitelný kód.
Mašinérii s tím související obsahuje modul MarkusSecundus.YoowzxCalc.Compilation.

Chceme-li být schopni přeložit matematický výraz na spustitelný kód, musíme nejprve vědět, co vůbec která v něm zapsaná operace znamená, a také jak rozlišit konstantu od identifikátoru a jak vypadá platný identifikátor. To všechno kompilátoru řekneme skrze instanci rozhranní IYCNumberOperator.

Pracujeme-li s typem double, decimal nebo long, nemusíme se namáhat - pro ty už je defaultní implementace připravena - jako podtřída statické třídy YCBasicNumberOperators. Tyto výchozí implementace definují operátory intuitivním způsobem - operátor + odpovídá sčítání, % modulení, ** mocnění apod., konstantou je vše, co projde metodou TryParse na odpovídajícím číselném typu při invariantní kultuře, validní identifikátor matchuje na regex [[:alpha:]_][[:alnum:]_]*, operátor pro typ double navíc zahrnuje ve standardní knihovně všechny funkce ze třídy System.Math.

Chcete-li napsat vlastní číselný operátor, doporučuji se podívat pro inspiraci právě na tyto předpřipravené implementace. Celkově to ale je poměrně přímočarý proces.

První metodou, jíž je třeba dodat, je TryParseConstant. Jejím úkolem je z textového zápisu určit, zda reprezentuje konstantu, a její případnou hodnotu. Všechny literály jsou nejprve testovány na konstantu a teprve pokud neprojdou, stanou se kandidátem na identifikátor.

Pokud literál není vyhodnocen jako konstanta, stane se kandidátem na identifikátor. Metoda ValidateIdentifier má pak za úkol rozhodnout, zda identifikátorem vskutku je, příp. lidsky čitelným způsobem popsat odchylky od identifikátorového formátu, jichž se dopouští. Třída YCBasicNumberOperators poskytuje pár statických metod a polí, které by se při její implementaci mohly hodit.

Nyní zbývá už jen doplnit metody odpovídající jednotlivým operátorům definovaným v gramatice, což by měl být naprosto přímočarý proces.

Volitelně ještě můžeme dodat množinu funkcí jakožto standardní knihovnu. Každá funkce v ní definovaná bude kompilátorem automaticky viditelná, aniž by se musela nacházet v kompilačním kontextu. Pokud se v kontextu nachází funkce se stejnou signaturou, zastíní funkci ve standardní knihovně.

Volitelně ještě může mít smysl vytvořený number operator zaregistrovat jako kanonický operátor k použití nad daným číselným typem.
Jejich seznam vede opět třída YCBasicNumberOperators a registrujeme v ní factory dodávající vždy novou instanci. Je-li náš operátor bezestavový singleton, může to vypadat nějak takto:

struct MyNumberType { }
class MyNumberOperator : IYCNumberOperator<MyNumberType> 
{
    ...
    public static MyNumberOperator Instance { get; } = new();
}

class EntryPoint
{
    public static void Main()
    {
        YCBasicNumberOperators.Register<MyNumberType>(() => MyNumberOperator.Instance);
    }
}

Instanci kanonického operátoru nyní získáme takto:

IYCNumberOperator<MyNumberType> op = YCBasicNumberOperators.Get<MyNumberType>();

Přesně takto získává defaultní operátor fasáda YoowzxCalculator, pokud jí žádný nedodáme explicitně. Nyní ji tedy můžeme bez problémů používat pro náš nový typ.

Z našeho výrazu je možné libovolně volat externí pojmenované funkce. Vzniká tedy problém, jak kompilátoru dodat jejich definice, aby mohl ona volání vytvořit.

Nejprve si ale musíme rozmyslet, jak vůbec funkci jednoznačně identifikovat. YoowzxCalc pro větší uživatelské pohodlí podporuje přetěžování funkcí se stejným jménem, ale různými argumenty. K jednoznačné identifikaci tedy slouží struktura YCFunctionSignature<TNumber> - nese jméno funkce, počet a typ (jako generický parametr) argumentů. Ve třídě YCCompilerUtils najdete extension-metody, kterými lze signaturu jednoduše získat z instance System.Delegate nebo z uzlů AST.

Správa seznamu definic je úkolem objektu IYCFunctioncallContext.
Prázdnou instanci jeho kanonické implementace pro funkce nad typem double získáme takto:

IYCFunctioncallContext<double> ctx = IYCFunctioncallContext<double>.Make();

Hešmapu funkcí, jež se v něm již napevno nacházejí, získáme skrze property ctx.Functions.

Ne vždy jsme ale schopni pro všechny funkce, jež chceme volat, mít těla již zkompilovaná a připravená. Představte si např., že pracujeme na umělé inteligenci ke hře a pokoušíme se v kalkulátoru naimplementovat klasickým učebnicovým způsobem algoritmus MiniMax. Máme dvě funkce, které se mají volat vzájemně - první volá druhou, druhá volá první, tedy cyklická závislost.
Zkompilovat obě funkce najednou, aby jedna o druhé vzájemně věděly, není v silách YC - přineslo by to do něj extrémní a zbytečnou komplexitu. Přímočarý způsob, jak takovou situaci rozřešit, je umožnit volání funkcí, jež ještě nebyly definovány - vytvořit prázdný wrapper, na který odkážeme místo toho, a počítat, že příslušná definice do něj bude dodána později. Přesně tak to YC dělá a k tomu slouží ostatek mašinerie, kterou má IYCFunctioncallContext na starosti.
Wrapper pro potencielně nerozřešený symbol s danou signaturou získáme takto:

IYCFunctioncallContext<double> ctx;
YCFunctionSignature<double> signature;
SettableOnce<Delegate> unresolved = ctx.GetUnresolvedFunction(signature);

Přesně toto dělá kompilátor pokaždé, když narazí na funkci, jež není k nalezení v hešmapě Functions ani ve standardní knihovně.
Do unresolved nyní, pokud vskutku je nerozřešena (což není garantováno - zjistíme příp. skrze unresolved.IsSet), pokud bychom vážně chtěli, můžeme ručně uložit delegáta a rozřešit ji tím, normálně takto:

Delegate value;
unresolved.Value = value;

V praxi to ale skoro jistě dělat nebudeme - místo toho využijeme metody ResolveSymbols na kontextu - nějak takto:

ctx = ctx.ResolveSymbols((signature, del));

Ta bere jako varargs libovolný počet dvojic (signatura, delegát), všechny najednou rozřeší a vrátí novou instanci kontextu, jež má všechny rozřešené symboly přidány do svých Functions (včetně symbolů, jež byly vedeny jako unresolved, ale měly hodnotu už nastavenou odjinud než z argumentů ResolveSymbols). Definice předaná sem jako argument bude v pořádku přidána do výsledného kontextu i tehdy, když vůbec nebyla vedena jako unresolved - tímto způsobem tedy jsme schopni do kontextu přímočaře přidávat i úplně nové definice.

Jakmile je symbol jednou rozřešen, pokus o změnu jeho hodnoty vyústí v běhovou chybu - to je záměr. Já, jakožto autor, si jsem plně vědom, že tím zavírám cestu k mnoha zajímavým a zajisté i velmi užitečným trikům, kterých by nebýt toho bylo možné dosáhnout, avšak v důsledku toho, jak je zbytek YC implementován, by to vedlo v některých okrajových případech k velmi komplexnímu chování, které, upřímně, nemám nervy dokumentovat.
Pokud to uživatel opravdu nutně potřebuje, neměl by pro něj být velký problém naimplementovat nad YC další vrstvu, jež mu to umožní, příp. obstarat si na vlastní nebezpečí verzi MarkusSecundus.Util.dll s odebranými checky v SettableOnce, je-li vážně zoufalý.

Někdy by se mohla hodit metoda GetUnresolvedSymbolsList - ta vrací proud těch symbolů, jež jsou vedeny jako unresolved a skutečně ještě rozřešeny nebyly.

Vedlejším efektem tohoto chování je fakt, že volání neexistující funkce zákonitě nemůže ústit v kompilační chybu, ale vždy až běhovou při pokusu onu neexistující funkci zavolat.

Nyní konečně známe vše, co potřebujeme, abychom mohli přistoupit k vlastní kompilaci.
Ta je úkolem objektu IYCCompiler.
Máme-li již instanci operátoru, kompilátor získáme následovně:

IYCNumberOperator<MyNumberType> op;
IYCCompiler<MyNumberType> compiler = IYCCompiler<MyNumberType>.Make(op);

Použití je víceméně přímočaré - zavoláme metodu Compile, jako argumenty jí předáme kontext a AST výrazu, jenž chceme zkompilovat - takto:

IYCFunctioncallContext<MyNumberType> ctx;

YCFunctionDefinition toCompile;
IYCCompilationResult<MyNumberType> result = compiler.Compile(ctx, toCompile);

Z implementačních důvodů takto ještě nezískáme přímo spustitelného delegáta, ale polotovar, který je nutné finalizovat jedním z těchto způsobů:

Delegate weaklyTypedResult = result.Finalize();
Func<MyNumberType> stronglyTypedResult = result.Finalize<Func<MyNumberType>>();

Nyní jsme konečně získali spustitelného delegáta reprezentujícího náš výraz! Ještě zbývá zkontrolovat a příp. doplnit nevyřešené symboly, které se kompilací objevily v kontextu, a můžeme ho vesele začít používat, jak jen se nám zachce.

Balíček MarkusSecundus.YoowzxCalc.Cmd obsahuje spustitelnou kalkulačku pro příkazovou řádku operující v klasické REPL smyčce nad typem double a sloužící jako ukázka demonstrující některé možnosti této knihovny.

Pro podrobnější instrukce k jejímu použití kalkulačku spusťte v interaktivním režimu a zavolejte příkaz help.