Tagging terms leads to: How to go down cyclic terms? How to write the dict functor?

Help!
1

I have written a simple set of predicates to “tag” elements in a term according to their “type”.

Efficiency is not a factor, the goal was to keep to the “decision tree of types” and not use cuts.

So you can ask things like:

?- once(tag(X,S)).
S = var(X).   % X is a variable

?- once(tag(100,S)).
S = int(100).  % Yup, 100 is an integer

?- once(tag(100.1,S)).
S = float(100.1).   % That's a float

?- once(tag(1/3,S)).
S = compound(/, [gnd], [int(1), int(3)]).   % Evidently a compound term, ground, with two integers 

?- once(tag(d{x:1,y:1,z:Z},S)).
S = dict(d, [nongnd], [atom(x)-int(1), atom(y)-int(1), atom(z)-var(Z)]).

?- once(tag([1,X,2],S)).
S = lbox([list, nongnd], int(1), lbox([list, nongnd], var(X), lbox([list, gnd], int(2), emptylist))).

?- once(tag(p(X,[1,2]),S)).
S = compound(p, [nongnd], [var(X), lbox([list, gnd], int(1), lbox([list, gnd], int(2), emptylist))]).

Two questions:

  • Is there a way to write down the dict functor? Currently I retrieve one for comparison purposes. For example, in case I want to detect a dict:
dict_functor(F) :- compound_name_arity(_{},F,_Arity).

tag_nonzero_arity_compound(T,dict(DictTag,Marks,TgDictArgs)) :-
   dict_functor(F),  % retrieve
   compound_name_arguments(T,F,[DictTag|DictArgs]),  % is it a dict?
   marks(T,Marks),  % find out about non-local properties, like ground-ess, cyclic-ness,...
   re_pair(DictArgs,TgDictArgsUnsorted), % transform key-vals into pairs
   keysort(TgDictArgsUnsorted,TgDictArgs). % impose order!
  • Is there a way to find out when a cycle has been traversed when going down a cyclic structure? One would have to label the terms somehow and stop traversel when a labeled term is encountered. Otherwise, how to know when to stop?

Umm… yeah, that’s it for today. On to reading Indexing dif/2.

2

Re: cycles. Can you carry a SeenItems set object with you:

f(X, A,B,C, SeenItems, SeenItems_ ) :-
   set_contains(X, SeenItems),
   set_put(X, SeenItems, SeenItems__),
   g(X, X_, A,B,C), % Do your work
   f(X_, SeenItems__, SeenItems_ ).

SWI has a its nb_set object which I guess could implement the set predicates:
https://www.swi-prolog.org/pldoc/man?section=nb_set
This would allow you to prevent recursion, but not retrieve-already found results. The library doesn’t say what non-backtrackable means. Can anyone clarify?

Alternatively, making a predicate tabled is an simple and effective way of breaking cycles. I don’t know enough about the SWI implementation to recommend it. For example, is it reasonably efficient where dicts and other datastructures are the table’s key? (I imagine so, but worth checking).

Depending on what non-backtrackable means, tabling might have additional benefits if the search space is a DAG, and not a simple tree.

1 Like