Předpokládám u čtenáře alespoň minimální znalost Prologu. Jak bychom mohli v C snadno implementovat princip logického programování (tedy zejména deklarativitu, nedeterminismus a unifikaci)? Mějme následující strukturu, která reprezentuje „prologovské“ proměnné (má-li str hodnotu NULL, považujeme proměnnou za volnou).
struct value { char* str; };
Unifikaci s řetězcem (konstantou) provedeme takto:
void unify_str(struct value* val1, char* str2, void (^callback)()) {
if (val1->str != NULL) { if (!strcmp(val1->str, str2)) callback(); }
else { val1->str = str2; callback(); val1->str = NULL; }
}
Všimněte si, že v zájmu jednoduchosti kódu používáme bloky (callback). Pokud nemáte clang, půjde kód přeložit v C++, pokud void (^callback)() nahradíte const std::function<void()>& callback.
Nyní nadefinujme jednoduchý predikát (fakt):
void father(struct value* val1, struct value* val2, void (^callback)()) {
unify_str(val1, "george", ^{ unify_str(val2, "john", callback); });
unify_str(val1, "john", ^{ unify_str(val2, "paul", callback); });
unify_str(val1, "john", ^{ unify_str(val2, "jane", callback); });
unify_str(val1, "paul", ^{ unify_str(val2, "mary", callback); });
}
A další predikát (tentokrát pravidlo):
void grandfather(struct value* val1, struct value* val2, void (^callback)()) {
__block struct value val3 = { .str = NULL };
father(val1, &val3, ^{ father(&val3, val2, callback); });
}
Následuje příklad použití:
__block struct value val1 = { .str = NULL };
__block struct value val2 = { .str = NULL };
grandfather(&val1, &val2, ^{ printf("%s %s\n", val1.str, val2.str); });
Pokud místo NULL při vytváření „proměných“ použijete řetezcovou konstantu, omezí se počet řešení (unifikovat se budou dvě konstanty, což se redukuje na jejich prosté porovnání).
Uvedený kód je založen na velmi jednoduchém principu. Unifikace probíhá přímo přiřazením hodnoty (místo NULL) nebo porovnáním konstant (je-li proměnná již vázaná). Poté se zavolá callback (čili výpočet pokračuje backtrackingem) a nakonec se unifikace zruší (rollback) a pokračuje se v další větvi výpočtu. Procházení seznamu argumentů u predikátu father je samozřejmě implementováno (v zájmu jednoduchosti) naivně a tedy nepříliš efektivně. Není ovšem složité použít nějakou chytrou datovou strukturu (podobně jako v Prologu, který vytváří indexy podle argumentů).
Unifikace s konstantou je jednoduchá a rychlá, ale mnohdy nedostatečná. Pro unifikaci dvou proměnných bychom měli:
void unify_val(struct value** val1, struct value** val2, void (^callback)());
Je nutné vyřešit netriviální případ unifikace dvou volných proměnných.
Výše uvedená metoda je velmi efektivní a svým způsobem nahrazuje WAM. Není obtížné rozšířit strukturu value tak, aby podporovala i složitější hodnoty než jen řetězce.
ČLÁNKY DO MAILU