5

The Wikipedia article for Prolog states:

Higher-order programming style in Prolog was pioneered in HiLog and λProlog.

The motivation for HiLog includes its ability to implement higher-order predicates like maplist:

maplist(F)([],[]).
maplist(F)([X|Xs],[Y|Ys]) <- F(X,Y), maplist(F)(Xs,Ys).

The paper that describes HiLog assumes that Prolog only has call/1, not call/3.

However, since Prolog (now) has call/3, maplist can be easily implemented in it:

maplist(_, [], []).
maplist(P, [X|Xs], [Y|Ys]) :- call(P, X, Y), maplist(P, Xs, Ys).

Is HiLog mostly of historical interest, or is its "higher-order" logic more general that what's available in Prolog now?

MWB
  • 11,740
  • 6
  • 46
  • 91
  • 2
    Now that I look back at this question, I should have given it a close vote for not being objective. I have been in a few other forums this morning and not putting on the SO hat of objective questions only. – Guy Coder Nov 14 '20 at 13:08
  • @GuyCoder I edited the title to better reflect the actual question. I think it's objective and answerable. See my [answer](https://stackoverflow.com/a/64836818/1937197) – MWB Nov 14 '20 at 18:31

3 Answers3

4

From wiki

Although syntactically HiLog strictly extends first order logic, HiLog can be embedded into this logic.

Any HiLog term can be translated into a Prolog term (HiLog: A foundation for higher-order logic programming - Weidong Chen, Michael Kifer, David S.Warren - 1993). So in a sense yes, it is not more general than Prolog.

Let me quote a few conclusions from the paper

Firstly, programming in HiLog makes more logic programs logical. We all admonish Prolog programmers to make their programs as pure as possible and to eschew the evils of Prolog’s nonlogical constructs. In Prolog, the intermixing of predicate and function symbols, in particular in the predicate, call/ 1, is nonlogical, whereas in HiLog, it is completely logical and is a first-class citizen. So in HiLog, programmers need not avoid using call/l, and thus have more flexibility in their task of writing pure logic programs.

Secondly, even though one might say that HiLog is simply a syntactic variant of Prolog, syntax is important when one is doing meta-programming. Since in meta-programming the syntax determines the data structures to be manipulated, a simpler syntax means that meta-programs can be much simpler.

rajashekar
  • 3,460
  • 11
  • 27
  • That's true, in a sense, but you must agree to only use one predicate (`apply`) for all your facts, rules and queries. – MWB Nov 14 '20 at 08:46
  • 1
    The "higher-order" in the paper is actually the "meta" used generally, "Higher-order predicate"/"Meta predicate" - you can write statements dealing with other predicates, in particular call them or look for syntactic solutions in the database. It is not really the "higher order" of logic ["higher-order logic"](https://plato.stanford.edu/entries/logic-higher-order/) which is ... complex. – David Tonhofer Nov 14 '20 at 08:54
  • 1
    @DavidTonhofer @MaxB : I am talking about the expressiveness of the language itself(not syntax niceness). There are some statements not expressible in first-order logic, for which we need quantization over set-of-sets etc. While HiLog extends(strictly) first-order logic, it is not more expressive. Any expression in it's language can be translated to an equivalent expression in prolog(and yes it will have a lot of `call` and `apply`). Look at Section 3.3 of the paper. – rajashekar Nov 14 '20 at 10:40
  • @rajashekar Agree with that. – David Tonhofer Nov 14 '20 at 10:55
3

A bit vaguely:

HiLog is not in Prolog (Prolog stays Prolog) but is used in Flora, which is basically an logic-based object-oriented database. It has its own syntax and runs on XSB Prolog.

If I understand correctly, the idea of HiLog is to have a defined practical syntax for "higher-order" predicates, by allowing variables in predicate name positions. This is the difference between the two maplist examples.

This looks as if this was 2-nd order logic (which becomes uncomputable/untractable as there is no way to find out whether a predicate F is related to a predicate G in general as you may be forced to compare their extent, all the points where they succeed) but is flattened down to 1-st order (computable) by restriction to syntactic equality (F and G are the same if the name the same predicate, foo/2) at which point one can deploy call/N to generate Prolog code.

So, yes, currently you have to jump through hoops to express statements in Prolog that may be a one-liner in HiLog (I have no examples though, not having though too deeply about this). It's the difference between C and ... uh ... Prolog!

Similar to a host of other ideas for extensions/modifications to Prolog into various X-logs, not all of which were implemented (I once tried to make a an overview image here), "HiLog syntax" (or something similar to it) may be found in a specialized X-log of the future that breaks out of its niche.

David Tonhofer
  • 14,559
  • 5
  • 55
  • 51
  • `may be found in a specialized X-log of the future` XSB includes it (which is why I suspect it's useful), but I can't think of any examples either. – MWB Nov 14 '20 at 08:28
  • @MaxB Indeed, it's in XSB - page 80 of [the manual](http://xsb.sourceforge.net/manual1/manual1.pdf) (PDF). I thought it was only in Flora. – David Tonhofer Nov 14 '20 at 08:38
  • Example, I think: `foo(X) :- P(X), P(-X).` "`foo(X)` is true if there exists a predicate P such that `P(X)` and `P(-X)`". I don't think this can be expressed with `call`. – MWB Nov 14 '20 at 08:54
  • 1
    @MaxB Well, on the lowest level, you would have to go through the Prolog database, find all predicates `P` of arity 1, try to find out what arguments they take, then for all arguments `X` collected, call `P(X),P(-X)` to check whether you have a solution. Yeah, that's _serious_ combinatorial explosion. It's also semidecidable I think: If there is a solution, you will find it (sadly, the universe may not live long enough fro you to profit from that little mathematical fact), but if there is none, you will never be sure. – David Tonhofer Nov 14 '20 at 09:00
  • No explosion. It's linear. But anyway, it's just an example of something `call` can not do, AFAIK. – MWB Nov 14 '20 at 09:05
  • It looks like I answered my own question `is its "higher-order" logic more general that what's available in Prolog now`, but your post inspired me to think – MWB Nov 14 '20 at 09:12
1

Since I answered my own question in the comments, I'll post it here:

There are things you can do in HiLog, that can not be done with call in Prolog, for example:

Queries like:

?- X(dog, 55, Y).

Assertions like:

foo(X, Y) :- Z(X), Z(Y(X)).

As stated in the aforementioned HiLog paper and the HiLog Wikipedia page, Prolog can emulate HiLog. However, this requires converting the whole program and all queries into a single predicate.

MWB
  • 11,740
  • 6
  • 46
  • 91
  • You can achieve the effect of the first of these using something like `query(P, Args) :- length(Args, Arity), current_predicate(P/Arity), Goal =.. [P | Args], catch(Goal, _, false). ` (call as `query(X, [dog, 55, Y]).`). The second is harder but should also be possible using such techniques. – Isabelle Newbie Nov 14 '20 at 20:04
  • 1
    could you please add links to "the paper" and "the WP page" into the answer proper, so it is self-sufficient? – Will Ness Nov 18 '20 at 13:10