Re: Extended DCG? (and state)

(If there was a way merge two discussion threads that's what I'd do here)

I've just read a paper called 'Backtrackable State with Linear Affine
Implication and Assumption Grammars' by Tarau, Dahl and Fall

	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.3382

and it touches on both the extended DCG dicussion and the mutable
state more generally. The authors address part of the design space
that Jan described that we have not discussed yet

>  - Sharing between threads
>  - Thread safety (for shared state)
>  - Name space and scoping
>  - Identity (sharing of variables)
> ...
>  - Backtrackable global variables
>    lobal name space (bug, should be module), both store and
>    load shares.  One value per key, thread local, backtracks.


The authors propose backtrackable operator assumel/1 
which temporarily add a read-once clause to the database
and assumed/1 which reads and destroys the clause, also
backtrackable.
(btw this linear behaviour reminds me of constraint handling
rules, which are yet another way of handling a dynamic database.
Jan was right - it's a very messy design space!)

Tarau et al use it to write DCG like code without code transformation
and potentially with multiple streams. It crucially relies on
variable sharing. I tried implementing something similar,
modelled on their example, with b_setval/2 and b_getval/2, which
have the right variable sharing behaviour. Here it is:
------------------------------------------------------
% Assumption Grammars, after Tarau et al.
% We need backtrackable state with variable sharing.

:- op(800,fy,#).
:- op(800,xfy,#).

% [] is empty value for b_setval, so @/1 and []/0 work like Maybe type.
put(Name,Value) :- b_setval(Name,@Value).
get(Name,Value) :- b_getval(Name,@Value), b_setval(Name,[]).

% extended DCG with multiple streams
edcg_phrase(Names, Goal, S1, S2) :-
   maplist(put, Names, S1), call(Goal),
   maplist(get, Names, S2).

Name#X :- get(Name,[X|XS]), put(Name,XS).

% DCG, one stream.
dcg_phrase(Goal,S1,S2) :- edcg_phrase([dcg],Goal,[S1],[S2]).
#X :- dcg#X.
   
% example transducer
star(_).
star(G) :- call(G), star(G).
copy :- in#X, out#X.
dup  :- in#X, out#X, out#X.
   
test(1,Out) :- edcg_phrase([in,out],star(copy),[[1,2,3,4],Out],[[],[]]).
test(2,Out) :- edcg_phrase([in,out],star(dup),[[1,2,3,4],Out],[[],[]]).
------------------------------------------------------

I'm not sure if there's any advantage to doing it this way, but Tarau
et al argue for the expressiveness of the general assumel/assumed
framework, eg for a loop avoiding graph walker.

Samer.



On 11 Feb 2014, at 16:51, Alan Baljeu wrote:

> I have a scenario where I'm mapping a list to a second list, but it's not 1 to 1.  For this, it would be nice to use an extended DCG, that supports two independent lists.  Does such a thing exist?
>  
> Alan Baljeu
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>