Tabling of cyclic terms

Is it possible to table a term with cycles? Say I have the followig DCG:


Without wanting to go into too much length how this is called and so on, tabling ‘S’/2 and then running a program that calls it taises a type error with "acyclic_term expected, found … " and so on.

ERROR: Type error: `acyclic_term' expected, found `@(ret('S',S_1),[S_1=[a,b|S_1]])' (a cyclic)

Is there a way to avoid this?

As yet, no. I’m not saying this is impossible, but it is not trivial either. Tables are based on tries, which requires a serialization of a term where two variant terms produce the same serialization. This for example means that T in X=f(1), T=g(X,X) and simple T=g(f(1),f(1)) must produce the same serialization.

For a cyclic term we could have some “cycle N” element in the serialization. This requires some bookkeeping as the above says we cannot simply use sharing from the input term. We do not want two passes over a term to be placed in a table, so the current implementation happily walks the term until it reaches some threshold depth. If that is reached it does a cycle test and either raises and exception or proceeds. An additional issue with cyclic terms is that we need a canonical serialization and thus
'S'([a|A],A) and 'S'([a,a|A],A) should produce the same serialization.

I don’t see this happening anytime soon. Of course, unless something is willing to sort this out.

1 Like

Thanks- unfortunately I don’t understand tabling well enough to even begin thinking about how this could be sorted out, especially if it’s not something trivial! More to the point, it’s not a huge issue for me. I can just “close” my difference lists before using them, for now. Sorry :confused:

I noticed that Swi added restraints to tabling. Is it possible to apply a max-size restraint to handle cyclc terms, somehow?

I confess I’m a bit confused by how restraints should be used and I’d welcome an example showing some code, e.g. for the tripwire/2 hook etc.

This really needs more documentation. As is, best refer to the papers by Theresa Swift and Benjamin Grosof, the XSB documentation and the test suite (in src/Tests/xsb). For this one you need Restraint answer size

1 Like