Dealing with state

Discussion
10

Here is an attempt at a much simplified alternative to edcg. It works on top of normal DCG, assuming a dict to hold the multiple state variables. I used Op<StateName to operate on the various state variables. Op is one of

  • List<StateName for a normal DCG terminal
  • String<StateName for a SWI-Prolog string acting as a terminal
  • Callable<StateName. When found, we call call(Callable, V0, V) to update the state for StateName
goal_expansion(<(On, Name,State0,State), Clause) :-
    expand(On, Name, State0, State, Clause).

expand(Literal,Name,State0,State, Clause), is_list(Literal) =>
    Clause = get_dict(Name, State0, List, State, Tail),
    append(Literal, Tail, List).
expand(String,Name,State0,State, Clause), string(String) =>
    Clause = get_dict(Name, State0, List, State, Tail),
    string_codes(String, Literal),
    append(Literal, Tail, List).
expand(Step,Name,State0,State, Clause), callable(Step) =>
    extend_goal(Step, [V0,V], StepEx),
    Clause = ( get_dict(Name, State0, V0, State, V),
               StepEx
             ).

Here are some examples

Interleave two lists

test_interleave(L) :-
    call_dcg(t, #{a:`abcde`, b:`12345`, c:L}, _).

t -->
    [L]<a,
    [N]<b,
    [L,N]<c,
    t.
t -->
    {true}.

Compute the length of a list

test_len(List, Len) :-
    call_dcg(list_len, #{len:0, list:List}, S),
    Len = S.len.

list_len -->
    [_]<list, !,
    increment<len,
    list_len.
list_len -->
    {true}.

increment(X0, X) :-
    X is X0+1.

Sum the elements in a list

test_sum(List, Sum) :-
    call_dcg(list_sum, #{sum:0, list:List}, S),
    Sum = S.sum.

list_sum -->
    [E]<list, !,
    add(E)<sum,
    list_sum.
list_sum -->
    {true}.

add(E, X0, X) :-
    X is X0+E.

The performance of test_sum/2 is about half of the library sum_list/2.

Comparison

Compared to keeping a state dict somewhere in the environment, this approach is clean in the sense that is does not require destructive update of the state but creates new instances of the state. The price is that GC must deal with these new instances, there is more state copying and we need DCG expansion to thread the state dict through the computation. It performs quite well without the need for any new VM support.

Keeping a state dict in the environment does not require any source code transformation, but requires destructive updates to the state. This would be fine if we know the old state is inaccessible anyway, but otherwise it has dubious properties. It is also slow, but I think it could get comparable performance with more low-level support.

2 Likes