7 ms·

This seems already almost valid Prolog syntax, which is also a syntactic superset of Datalog. The main question I have for implementors of Datalog and Prolog v

by triska 4y ago

This seems already almost valid Prolog syntax, which is also a syntactic superset of Datalog. The main question I have for implementors of Datalog and Prolog variants like this: If you are that close to using Prolog syntax, why not go all the way and rely fully on Prolog, a language for which a well-defined ISO standard and several interesting implementations already exist. One of the key benefits you get in this way is Prolog's strength for meta-programming and reasoning about programs with the same formalism you use to state the specifications and queries. Abstract interpretation, query optimization etc. can be easily implemented in this way, instead of having to parse an additional formalism. It may be possible to implement such Prolog-"variants" entirely within Prolog by defining suitable infix or prefix operators, or adding conforming extensions in implementations. A conforming extension is one that does not conflict with existing ISO syntax. For example, something that would be a syntax error in conforming Prolog implementations could be used as an implementation-specific extension.

tmptmpgo 4y ago
Because syntactic doesn’t mean semantic subset. Datalog uses bottom-up evaluation by default while Prolog uses top-down. As such they are computationally very different.
- triska 4y ago
  Yes well, as you mention, that is only the default execution strategy, and nothing prevents us from using other execution strategies for either language. In fact, the main advantage of using a declarative language such as Prolog or Datalog is precisely that it can be readily interpreted with different execution strategies, and indeed many Prolog implementations already provide alternative execution strategies, the most common of which is currently SLG resolution, also known as tabling. Alternative execution strategies are applicable as long as you keep to the pure monotonic core of the language. The fact that the default execution strategies of Prolog and Datalog differ is not a valid argument for or against using a slightly different syntactic formalism. If, as seems plausible, an alternative execution strategy of Prolog can provide the same semantics as Mangle and other Datalog "variants", then it may be worth considering doing that instead of devising a different syntactic formalism, especially if the alternative syntactic formalism is already so close to valid Prolog syntax as it is in this concrete case.
  - tmptmpgo 4y ago
    Yes, I’m well aware of tabling. But high performance Datalog implementations will fundamentally be very different than the usual Prolog implementations. But sure, it isn’t impossible. Just long a ways from ISO Prolog. Consider Soufflé, designed for large scale program analysis. Or LogiQL, designed for efficient incremental evaluation. You also failed to disclose that you are not exactly unbiased individual here.
    - deleted 4y ago
      [deleted]
    - triska 4y ago
      > Consider Soufflé, designed for large scale program analysis. Or LogiQL, designed for efficient incremental evaluation. I have now looked up these systems: They are far removed from standard Prolog syntax, much farther than the system outlined in the posted article, which uses almost Prolog syntax to such an extreme extent that one of the given examples is already valid Prolog syntax and even a valid Prolog program without any changes. Therefore, the question I posted above ("If you are that close to using Prolog syntax, ...") does not apply to the same extent to these systems. > You also failed to disclose that you are not exactly unbiased individual here. Personally, I believe I have a solid grasp on the benefits of using standard Prolog syntax and the disadvantages of so slightly deviating from it, and I also believe that the question I asked is justified and what I stated in this thread is true. If you see a need for any disclosure beyond what I stated above, please add it and what you believe to be the nature of my bias as your reply to this post for everyone to see. Thank you a lot!
  - rad_gruchalski 4y ago
    Datalog programs guarantee termination while Prolog programs do not.
    - triska 4y ago
      Yes, the subset of Prolog that is called Datalog can be interpreted in such a way that termination is guaranteed, and that is a nice and valuable property of this specific subset, i.e., the functor-free subset, of Prolog. This is a good example to illustrate why it can be useful to interpret specific Prolog programs and fragments in specific ways, which may also differ from the default execution strategy. As a specific instance of such an execution strategy, we can again consider SLG resolution: If we interpret any pure Prolog program that does not use compound terms with SLG resolution, then every query we post terminates universally.
PaulHoule 4y ago
Prolog is not purely logical in that you can write imperative programs by taking advantage of the fixed order of search and also alter the executing with cuts. One of the great disasters of symbolic AI in the 1980s was the discovery that you can’t parallelize Prolog.
- egl2021 4y ago
  "...you can write imperative programs...". It's worse than that: you have to look carefully at the order of the alternatives to understand the computation. I re-read Clocksin and Mellish during a recent programming language binge and realized that an imperative core lurks under the logical veneer.
philzook 4y ago
I agree this would be very useful. There are a number of datalog idioms (demand transformations is a big one for encoding functional programs, adding provenance, inlining relations, doing some light compile time backwards proof search) that it would be nice to have a good meta-programming/macro language to express. Prolog seems like a natural choice. I briefly tried going this route programming in prolog syntax so prolog could parse it, but generating souffle syntax out of the prolog metaprogram.

by triska 4y ago

tmptmpgo 4y ago

Because syntactic doesn’t mean semantic subset. Datalog uses bottom-up evaluation by default while Prolog uses top-down. As such they are computationally very different.

triska 4y ago
Yes well, as you mention, that is only the default execution strategy, and nothing prevents us from using other execution strategies for either language. In fact, the main advantage of using a declarative language such as Prolog or Datalog is precisely that it can be readily interpreted with different execution strategies, and indeed many Prolog implementations already provide alternative execution strategies, the most common of which is currently SLG resolution, also known as tabling. Alternative execution strategies are applicable as long as you keep to the pure monotonic core of the language. The fact that the default execution strategies of Prolog and Datalog differ is not a valid argument for or against using a slightly different syntactic formalism. If, as seems plausible, an alternative execution strategy of Prolog can provide the same semantics as Mangle and other Datalog "variants", then it may be worth considering doing that instead of devising a different syntactic formalism, especially if the alternative syntactic formalism is already so close to valid Prolog syntax as it is in this concrete case.
- tmptmpgo 4y ago
  Yes, I’m well aware of tabling. But high performance Datalog implementations will fundamentally be very different than the usual Prolog implementations. But sure, it isn’t impossible. Just long a ways from ISO Prolog. Consider Soufflé, designed for large scale program analysis. Or LogiQL, designed for efficient incremental evaluation. You also failed to disclose that you are not exactly unbiased individual here.
  - deleted 4y ago
    [deleted]
  - triska 4y ago
    > Consider Soufflé, designed for large scale program analysis. Or LogiQL, designed for efficient incremental evaluation. I have now looked up these systems: They are far removed from standard Prolog syntax, much farther than the system outlined in the posted article, which uses almost Prolog syntax to such an extreme extent that one of the given examples is already valid Prolog syntax and even a valid Prolog program without any changes. Therefore, the question I posted above ("If you are that close to using Prolog syntax, ...") does not apply to the same extent to these systems. > You also failed to disclose that you are not exactly unbiased individual here. Personally, I believe I have a solid grasp on the benefits of using standard Prolog syntax and the disadvantages of so slightly deviating from it, and I also believe that the question I asked is justified and what I stated in this thread is true. If you see a need for any disclosure beyond what I stated above, please add it and what you believe to be the nature of my bias as your reply to this post for everyone to see. Thank you a lot!
- rad_gruchalski 4y ago
  Datalog programs guarantee termination while Prolog programs do not.
  - triska 4y ago
    Yes, the subset of Prolog that is called Datalog can be interpreted in such a way that termination is guaranteed, and that is a nice and valuable property of this specific subset, i.e., the functor-free subset, of Prolog. This is a good example to illustrate why it can be useful to interpret specific Prolog programs and fragments in specific ways, which may also differ from the default execution strategy. As a specific instance of such an execution strategy, we can again consider SLG resolution: If we interpret any pure Prolog program that does not use compound terms with SLG resolution, then every query we post terminates universally.

PaulHoule 4y ago

Prolog is not purely logical in that you can write imperative programs by taking advantage of the fixed order of search and also alter the executing with cuts. One of the great disasters of symbolic AI in the 1980s was the discovery that you can’t parallelize Prolog.

egl2021 4y ago
"...you can write imperative programs...". It's worse than that: you have to look carefully at the order of the alternatives to understand the computation. I re-read Clocksin and Mellish during a recent programming language binge and realized that an imperative core lurks under the logical veneer.

philzook 4y ago

I agree this would be very useful. There are a number of datalog idioms (demand transformations is a big one for encoding functional programs, adding provenance, inlining relations, doing some light compile time backwards proof search) that it would be nice to have a good meta-programming/macro language to express. Prolog seems like a natural choice. I briefly tried going this route programming in prolog syntax so prolog could parse it, but generating souffle syntax out of the prolog metaprogram.