Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yes, but there's more to it than just that. It's possible to write Prolog programs which never derive new atoms yet still fail to terminate.

It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate.

EDIT: Thinking about this more, I'm not sure why Prolog couldn't also use breadth-first search. So maybe both are necessary: Datalog not only disallows creating new atoms, but it also has a better search strategy; the combination of the two results in guaranteed termination.



Datalog does not have a search strategy per se. The general "strategy" (or definition) is the fixpoint of the T_p operator that derives all one-step-derivable facts from the facts and the rules.

The minimal model (result of derivation) is defined as the fixpoint of this operation. And the minimal model is finite because of the fixed number of atoms.

Every other evaluation strategy must be equivalent to this. Both in terms of termination and minimal model.

Prolog could use breadth first instead of SLD (and there are other Prolog evaluation strategies that, for example, use tabling for derived facts) but then you might get an infinite number of backtracking points instead of terms of infinite depth. You haven't really won anything by doing that.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: