Re: [Potassco-users] question about scanning and parsing by Gringo/Clasp

[Roland K. <kam...@cs...>]

Hello Xudong,

now I think understand where your problem is. Your are feeding a large pre-
grounded program into gringo. First of all, gringo was not made for this use-
case. It is designed to work well with a small intensional database (non-
ground rules) and a large extensional database (facts).

When given a ground program, gringo performs a dependency analysis based on 
predicate names. Afterwards, it uses semi-naïve evaluation to instantiate the 
problem. The grounding of gr.lp becomes slower because gringo performs said 
semi-naïve evaluation on the program (and as indicated above gringo is *not* 
designed for this use-case). There is still a little dependency information to 
exploit and hence it still is able to ground it in acceptable time. But in 
your "generalized" program, you removed all dependency information. And as is 
to be expected, performance degrades.

You should avoid regrounding pre-grounded problems. One approach to do so 
could be using meta-encoding. Have a look at the following URL:
http://www.cs.uni-potsdam.de/wv/metasp/

Regards, Roland

On Monday, April 02, 2012 02:55:28 PM Xudong Liu wrote:
> Thank you Roland for your response. Here is the experiment I did having
> read your reply.
> 
> To compute an answer set for gr.lp (a big ground file of 331 thousand
> lines), I tried "gringo gr.lp | clasp" and "gringo -g gr.lp | clasp" in
> command line. The former one cost me 12.1s and the latter 2.8s. To compute
> an answer set for g.lp (a big generalised ground file), I tried "gringo
> g.lp | clasp" and "gringo -g g.lp | clasp" in command line. The former one
> cost me 231.8s (acceptable?) and the latter 2.18s.
> 
> And the generalisation I used is basically like what gringo does:
> constructing a hash table and iterate through it. So my g.lp looks like a
> collection of "atom(1). atom(2). ...... atom(n)." where n is the number of
> distinct predicates in the program. (for instance, predicate
> "edge(kentucky,iowa)" may be generalised to "atom(45)", predicate
> "edge(ohio,indianna)" to "atom(103)", etc.)
> 
> So is it like the way you guys did it in gringo? Also, the scanning and
> parsing parts of gringo are libgringo/src/parser.r2c and
> libgringo/src/parser_impl.y. Is there a tester to compile and run them?
> > https://lists.sourceforge.net/lists/listinfo/potassco-users

No there isn't there are tightly interwoven into gringo and cannot easily be 
used separately. But as mentioned above, the parsing is probably not the 
problem.

Regards, Roland