5 ms·

Prolog provides this with so called dynamic predicates. For example, if we declare the predicate f/1 dynamic using the standard directive dynamic/1: :- dy

by triska 6y ago

Prolog provides this with so called dynamic predicates. For example, if we declare the predicate f/1 dynamic using the standard directive dynamic/1: :- dynamic(f/1). then we can assert new clauses for f/1 using the standard predicates asserta/1 and assertz/1: ?- asserta(f(a)), assertz(f(b)). true. We then get: ?- f(X). X = a ; X = b. Rules can also be asserted: ?- use_module(library(lists)), asserta((f(X):-length(_,X))). true. yielding: ?- f(X). X = 0 ; X = 1 ; X = 2 ; X = 3 ; ... I used Scryer Prolog to run these examples. Dynamic changes to the database have advantages and drawbacks. On the plus side, they let us incorporate new knowledge and rules, and we automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and we can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions.

YeGoblynQueenne 6y ago
>> Dynamic changes to the database have advantages and drawbacks. On the plus side, they let you incorporate knew knowledge and rules, and you automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and you can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions. I wonder if that is part of the benefits advertised by DDlog, the ability to update a program without having to worry about clause ordering (which one does not have to, with datalog and bottom-up evaluation) or generally side effects. Very tentatively, I'm guessing that, since datalog programs lack negation, any new facts or rules added to the (extensional) database will update the "output" of the database (its Herbrand model) monotonically, i.e. you'll see new facts comeing out but no facts will "disappear". I'm a bit unsure because the DDlog github is talking about functions and typed datalog and I'm not really sure how that works now.
- dkjaudyeqooe 6y ago
  Most modern datalogs, this one included, support negation, with some limitations.
  - YeGoblynQueenne 6y ago
    Well, of course you can have negation and functions in "a" datalog language (there are different variants) but the point is that bottom-up evaluation is not then decidable. Out of curiosity, what kind of negation do you mean? Negation as failure or classical negation? And what do you mean about limitations?
    - kragen 6y ago
      Hmm, I thought stratifying Datalog allowed bottom-up evaluation to remain decidable despite the presence of negation? And surely there are at least some kinds of functions that would also preserve deciability, even without stratification? I admit I don't know very much about Datalog, and I know you know a substantial amount, so maybe I'm just confused. But I'd like to understand how.
      - YeGoblynQueenne 6y ago
        Eh, to be honest I don't really know a substantial amount about Datalog. My specialty is Inductive Logic Programming and I'm interested in Datalog because it's decidability makes it a convenient represantation language for machine-learned logic programs. A very simple version of Datalog is sufficient for my purposes so I haven't really dabbled much in variations or more modern versions. So I might well be wrong about decidability depending on the absence of negation. Now that I think of it again, the problem with negation, in particular the negation-as-failure (NAF) in Prolog, is that it breaks the monotonicity of inference. Monotonicity in this context means that the model of a logic program (the set of facts that are immediate consequences of the facts and rules in the program, and that are derived in a bottom-up fashion with a TP operator, in let's say "traditional" Datalog) can only increase with the introduction of new facts. With NAF, this is not the case -introduction of a new fact may make a previously derived true fact now false. So maybe the problem with negation, at least NAF, is that it breaks the soundness of the inference procedure because facts already derived as true become false when new facts are derived. I give a (very crude, sorry) example of how Datalog's bottom-up evaluation works in an earlier comment: https://news.ycombinator.com/item?id=26522737 https://news.ycombinator.com/item?id=26522737 In short, bottom-up evaluation proceeds in discrete steps where at each step a new set of facts is derived from the facts and rules known so-far. Newly derived facts are added to the program so the set of facts in the program increases until no new facts can be derived. Without NAF, when a new set of facts is derived and added to the program, the truth value of already derived facts cannot change. But _with_ NAF, bottom-up evaluation may introduce a new fact in step k that makes a fact derived in step k - j false. So now we have an unsound derivation procedure. I wonder if this unsoundness actually translates to undecidability. Suppose the above happens - we introduce a new fact A and some existing fact B becomes false. What can we do to avoid this? Well, we can't know the truth value of B after the derivation of A before actually deriving A (because we don't know the truth of A before we can derive it), so we can't avoid deriving A. What we can do is go back and re-evaluate the truth of each derived fact, find that B is now false, and remove it from the program. But what if removing B allows a new fact, C, to be derived which was previously false because of B, and C is such that A is now false? Well, A cannot be derived given C, and without A we must derive B. Which means we have to get rid of C again and allow A back in. So now we're stuck in a loop. I don't know if this is actually something that can happen or not, I was just thinking through the problem right now given your question, so I may be talking nonsense. In any case, if there is such a problem with NAF, then maybe modern datalogs have a different negation scheme, allowing classical negation (as does Answer Set Programming). But I really don't know about that, hence my question to the OP about the kind of negation they mean. Which was a genuine question btw! I really don't know how modern Datalogs work. Anyway I'll go check a few sources and see if my sketch proof of undecidability above makes any sense and I'll come back to let you know what I find :)
kybernetikos 6y ago
This is interesting and Scryer Prolog looks like a great project. I wonder if it's possible to run it in a DB-like mode - with durable changes, and accessible as a server.

by triska 6y ago

YeGoblynQueenne 6y ago

>> Dynamic changes to the database have advantages and drawbacks. On the plus side, they let you incorporate knew knowledge and rules, and you automatically benefit from built-in features such as argument indexing. However, running the same query twice can lead to different results, changes in the order of goals can affect the meaning of the conjunction, and you can no longer reason about different predicates in isolation. Dynamic changes of the database are said to be side-effects, since they affect the program in a way that is outside the logical interpretation of the given definitions. I wonder if that is part of the benefits advertised by DDlog, the ability to update a program without having to worry about clause ordering (which one does not have to, with datalog and bottom-up evaluation) or generally side effects. Very tentatively, I'm guessing that, since datalog programs lack negation, any new facts or rules added to the (extensional) database will update the "output" of the database (its Herbrand model) monotonically, i.e. you'll see new facts comeing out but no facts will "disappear". I'm a bit unsure because the DDlog github is talking about functions and typed datalog and I'm not really sure how that works now.

dkjaudyeqooe 6y ago
Most modern datalogs, this one included, support negation, with some limitations.
- YeGoblynQueenne 6y ago
  Well, of course you can have negation and functions in "a" datalog language (there are different variants) but the point is that bottom-up evaluation is not then decidable. Out of curiosity, what kind of negation do you mean? Negation as failure or classical negation? And what do you mean about limitations?
  - kragen 6y ago
    Hmm, I thought stratifying Datalog allowed bottom-up evaluation to remain decidable despite the presence of negation? And surely there are at least some kinds of functions that would also preserve deciability, even without stratification? I admit I don't know very much about Datalog, and I know you know a substantial amount, so maybe I'm just confused. But I'd like to understand how.
    - YeGoblynQueenne 6y ago
      Eh, to be honest I don't really know a substantial amount about Datalog. My specialty is Inductive Logic Programming and I'm interested in Datalog because it's decidability makes it a convenient represantation language for machine-learned logic programs. A very simple version of Datalog is sufficient for my purposes so I haven't really dabbled much in variations or more modern versions. So I might well be wrong about decidability depending on the absence of negation. Now that I think of it again, the problem with negation, in particular the negation-as-failure (NAF) in Prolog, is that it breaks the monotonicity of inference. Monotonicity in this context means that the model of a logic program (the set of facts that are immediate consequences of the facts and rules in the program, and that are derived in a bottom-up fashion with a TP operator, in let's say "traditional" Datalog) can only increase with the introduction of new facts. With NAF, this is not the case -introduction of a new fact may make a previously derived true fact now false. So maybe the problem with negation, at least NAF, is that it breaks the soundness of the inference procedure because facts already derived as true become false when new facts are derived. I give a (very crude, sorry) example of how Datalog's bottom-up evaluation works in an earlier comment: https://news.ycombinator.com/item?id=26522737 https://news.ycombinator.com/item?id=26522737 In short, bottom-up evaluation proceeds in discrete steps where at each step a new set of facts is derived from the facts and rules known so-far. Newly derived facts are added to the program so the set of facts in the program increases until no new facts can be derived. Without NAF, when a new set of facts is derived and added to the program, the truth value of already derived facts cannot change. But _with_ NAF, bottom-up evaluation may introduce a new fact in step k that makes a fact derived in step k - j false. So now we have an unsound derivation procedure. I wonder if this unsoundness actually translates to undecidability. Suppose the above happens - we introduce a new fact A and some existing fact B becomes false. What can we do to avoid this? Well, we can't know the truth value of B after the derivation of A before actually deriving A (because we don't know the truth of A before we can derive it), so we can't avoid deriving A. What we can do is go back and re-evaluate the truth of each derived fact, find that B is now false, and remove it from the program. But what if removing B allows a new fact, C, to be derived which was previously false because of B, and C is such that A is now false? Well, A cannot be derived given C, and without A we must derive B. Which means we have to get rid of C again and allow A back in. So now we're stuck in a loop. I don't know if this is actually something that can happen or not, I was just thinking through the problem right now given your question, so I may be talking nonsense. In any case, if there is such a problem with NAF, then maybe modern datalogs have a different negation scheme, allowing classical negation (as does Answer Set Programming). But I really don't know about that, hence my question to the OP about the kind of negation they mean. Which was a genuine question btw! I really don't know how modern Datalogs work. Anyway I'll go check a few sources and see if my sketch proof of undecidability above makes any sense and I'll come back to let you know what I find :)

kybernetikos 6y ago

This is interesting and Scryer Prolog looks like a great project. I wonder if it's possible to run it in a DB-like mode - with durable changes, and accessible as a server.