Is adaptive parsing possible in Prolog?

Question

I am attempting to write an adaptive parser in Prolog: in other words, a parser that can modify its own parsing rules at runtime.

In order to do this, I'll need to generate new predicates at runtime, but I'm not sure if this is possible. Would it be possible to write a predicate that takes a list like this one:

generate_dcg_rule([A," is greater than ",B]).

...and then generates a new predicate like this one?

expr(A," is greater than ",B) -->
    symbol(A)," is greater than ",symbol(B).

Answer 1

Yes, that's easily possible.

Prolog is a very dynamic language, and you can assert arbitrary clauses at runtime using for example assertz/1.

You can expand DCG rules to ordinary Prolog rules using your Prolog's term expansion mechanism that is usually used to do this.

For example, using expand_term/2:

?- expand_term((expr(A," is greater than ",B) -->
    symbol(A)," is greater than ",symbol(B)), Clause).
Clause =  (expr(A, [' ', i, s, ' ', g, r, e|...], B, _G242, _G253):-symbol(A, _G242, _G264), _G264=[' ', i, s, ' ', g|...], symbol(B, _G275, _G253)).

You can assert such clauses with assertz/1:

?- expand_term((Head --> Body), Clause), assertz(Clause).

Note that I am using double_quotes set to chars in this example, i.e., use:

:- set_prolog_flag(double_quotes, chars).

in your source files. This is a good idea in any case.

Note also that I am assuming that you have already found a way to translate the lists you give in your generate_dcg_rule/1 example to actual DCGs. For this translation, I rather recommend a predicate like list_dcg/2 that declaratively describes the relation between such lists and DCG rules. The advantage is clear: You can for example test such relations interactively and with test cases etc. For your concrete example, one clause that defines this relation could be similar to:

list_dcg([A,Ls,B], DCG) :-
        Ls = "is greater than ",
        DCG = (expr(A, Ls, B) --> symbol(A), Ls, symbol(B)).

I leave generalizing this to your other use cases as an exercise. In total, one way to assert such clauses dynamically is thus:

?- list_dcg(List, DCG), expand_term(DCG, Clause), assertz(Clause).

Note how we benefit from Prolog's homoiconic nature in such examples: Prolog rules and DCG rules have a natural representation as Prolog terms, and we can simply write them down and reason about them like any other terms also within goals.