Hlavní navigace

Lambda Prolog

26. 10. 2011 21:08 zboj

Před nějakou dobou jsem narazil na projekt nazvaný Yield Prolog. Jedná se o implementaci Prologu v C# s využitím yield pro emulaci nedeterminismu. Autor uvádí, že výkon je srovnatelný s moderními stroji WAM, na nichž jsou založeny v podstatě všechny současné Prology.

Víceméně z dlouhé chvíle jsem se rozhodl vyzkoušet něco podobného v C++. Protože C++ nemá yield, použil jsem lambda výrazy z nového standardu C++11 (odtud název článku jako analogie k „Yield Prolog“) podle schématu:

C# C++
for (kolekce) { akce } for(kolekce, [](){ akce })
yield něco lambda(něco)

Trik původní implementace spočívá v tom, že yield funguje jako return, ale vstupním bodem dalšího volání je kód za yield. Po unifikaci proměnné tedy výpočet pokračuje do hloubky (podle výpočetního modelu Prologu) a při backtrackingu se unifikace zruší a proměnná je opět volná, aniž by se narušila plynulost výpočtu. Stejného efektu lze dosáhnout lambda výrazem. Kód jsem upravil tak, že po unifikaci volné proměnné se zavolá lambda výraz a po návratu se vazba zruší.

Kód jsem testoval v clangu a ve VS 2010. Místo <chrono> jsem ve VS použil Stopwatch, protože ve VS 2010 <chrono> není (a ve VS 2011 v módu Release překladač spadne). Jinak je vše čisté C++ (konkrétně C++11). Ve VS je kód přeložený s /clr 2–3× pomalejší než kód přeložený s /clr:pure (/clr:safe pochopitelně nejde), jenž je o pár procent pomalejší než kód z clangu.

Pokud Prolog považujete za akademický nesmysl, dosaďte si za Prolog všude rule-based programming. Kromě zajímavé emulace nedeterminismu stojí za zmínku, že „managed“ kód (tedy .NET bajtkód) je 2–3× rychlejší než nativní kód. Nevím, jestli je tak špatná nativní implementace STL nebo kompilátor do nativního kódu, ale JIT ve spojení s STL.NET je evidentně velmi kvalitní (téměř se vyrovná kódu z clangu).

NB: Protože clang nepodporuje lambda výrazy (přesněji řečeno nepodporuje standard, má své s odlišnou syntaxí i vntiřní implementací, jež nejsou typu std::function<…>), je nutné pro portabilitu kódu vytvořit třídu, jež „zabalí“ lambda výraz clangu (něco na způsob ^{…}), a přetížit operator (). I přes tento trik je kupodivu kód přeložený clangem rychlejší.

Sdílet