Hilog in XSB, Ciao, etc

[David_Warren]

We had an interesting discussion oi Hilog syntax and semantics this morning. I’d like to summarize what I understood.
Syntax issues: XSB extends Prolog term syntax to allow the functor position to be an arbitrary (hilog) term. Ciao extends Prolog term syntax to allow the functor position to be a variable.
In each case a term like X(A,B) is syntactic sugar for the Prolog term $$(X,A,B), where the $$ is some atom. In Ciao it is call/n; in XSB it is apply/n.
Semantic issues: The question is what is the semantics of the $$. In XSB it is an uninterpreted symbol (i.e., not the semantics of the Prolog predicate apply/2; i.e., apply was probably a poor choice for this symbol by the XSB implementers). In Ciao the semantics of $$ (call/n) is, appropriately, the Prolog semantics of call/n.

An important implication of this difference is shown by the example (thanks, Manuel):

?- P=append([1,2,3]), P([4,5,6],X).

In Ciao semantics, with the usual definition of append/3, this would be equivalent to::

?- append([1,2,3],[4,5,6],X).

In XSB semantics, the above call with P (with the irrelevant definition of append/3) would be failure. One would have to give a definition of the apply/3 predicate, maybe like:

append()(L,L).
append([X|L1])(L2,[X|L3]) :- append(L1)(L2,L3).

to get the same answer as Ciao gets to that query (with P).

I suspect that Ciao does not allow a term with a variable functor in the head of a rule. When one gives definitions of predicates, one must use the “unfactored” version I suspect. XSB does allow definitions to be given directly in hilog syntax. Allowing that is Ciao seems non straightforward. E.g., XSB allows a definition:
X(a,b),
and query ?- Y(Z,b). which will bind Y to X and Z to a. (How useful this is may be questioned:-).
Or similarly
p(a,b).
and a call of ?- X(a,b). with X being bound to p. I don’t see how to do either of these in Ciao. Of course these may seem unreasonable uses, and the reasonable uses of hilog terms in the heads of rules may be appropriated compiled for Ciao’s semantics with some restriction and translation.

Another thought: I assume Ciao allows embedded terms to have variable functor symbols. (Is this true?) Assuming so, then consider:
?- X = Y(a), X = p(a).
This would seem to fail since the first X would be call(Y,a) and the second would be p(a). This would succeed in XSB and is why XSB needs to know that p is a hilog symbol. But maybe Ciao doesn’t allow embedded terms with variable functor, or just defines this to fail?

Thoughts?
-David

[JanWielemaker]

@David_Warren

append()(L,L).
append([X|L1])(L2,[X|L3]) :- append(L1)(L2,L3).

Thanks for the writeup. The above was the part of the puzzle I didn’t get.

It seems the call/N based approach is way simpler and faster, but sacrifices the ability to use a variable relation to infer possible relations between arguments. Now the question is how useful this is? And, if it is useful, whether we can get it back somehow?

[herme]

Yes, thanks David for the writeup, I also got to understand more about Hilog!

@David_Warren

Semantic issues: The question is what is the semantics of the $$. In XSB it is an uninterpreted symbol (i.e., not the semantics of the Prolog predicate apply/2; i.e., apply was probably a poor choice for this symbol by the XSB implementers). In Ciao the semantics of $$ (call/n) is, appropriately, the Prolog semantics of call/n.

An important implication of this difference is shown by the example (thanks, Manuel):

?- P=append([1,2,3]), P([4,5,6],X).

In Ciao semantics, with the usual definition of append/3, this would be equivalent to:

?- append([1,2,3],[4,5,6],X).

Yep.

@David_Warren

In XSB semantics, the above call with P (with the irrelevant definition of append/3) would be failure. One would have to give a definition of the apply/3 predicate, maybe like:

append()(L,L).
append([X|L1])(L2,[X|L3]) :- append(L1)(L2,L3).

to get the same answer as Ciao gets to that query (with P).

I suspect that Ciao does not allow a term with a variable functor in the head of a rule. When one gives definitions of predicates, one must use the “unfactored” version I suspect. XSB does allow definitions to be given directly in hilog syntax. Allowing that is Ciao seems non straightforward. E.g., XSB allows a definition: X(a,b), and query ?- Y(Z,b). which will bind Y to X and Z to a.

Actually, Ciao (or, more precisely, Ciao’s hiord package) also allows a variable functor in the head:

:- module(_, _). 
:- use_package(hiord).

Q(X,Y) :- atom_codes(X,Y). 

This introduces a definition:

call(Q,X,Y) :- atom_codes(X,Y).

Now, since the hiord package also loads call/n, they clash and you cannot really call Q/2. However, you can do instead:

:- module(_, _, []). 
:- push_prolog_flag(read_hiord,on).

Q(X,Y) :- atom_codes(X,Y). 

i.e, turn on only the transformation of hiord terms to call terms. This does not load call/N, and then one can do those queries:

?- call(_,a,Y).
Y = [97] ? 
yes

?- push_prolog_flag(read_hiord,on).
yes

?- Q(a,Y).
Y = [97] ? 

@David_Warren

(How useful this is may be questioned:-).

@David_Warren

Or similarly p(a,b). and a call of ?- X(a,b). with X being bound to p.

This one indeed will not work directly, because of the semantics of call/n which the hiord package uses for efficiency: call/n of course needs to have its first argument instantiated.

We have discussed including several optional alternatives to call/n for this case when the first argument is a variable, including for example residuation (delaying until the first argument is bound), or backtracking instantiating the first argument over the predicates in the program, but did not get around to implementing it yet.

Or, one can always do the standard trick of generating all the apply clauses, which I think is essentially what Hilog does, except that they are user-provided, correct?

@David_Warren

Of course these may seem unreasonable uses, and the reasonable uses
of hilog terms in the heads of rules may be appropriated compiled
for Ciao’s semantics with some restriction and translation.

Another thought: I assume Ciao allows embedded terms to have
variable functor symbols. (Is this true?)

Yes, hiord allows this.

@David_Warren

Assuming so, then consider:
?- X = Y(a), X = p(a).
This would seem to fail since the first X would be call(Y,a) and the second
would be p(a).
This would succeed in XSB and is why XSB needs to know that p
is a hilog symbol. But maybe Ciao doesn’t allow embedded terms with variable
functor, or just defines this to fail?

Yes, this does fail in Ciao’s (current) hiord package, which is actually older than the hiord paper.

Btw, in the hiord paper the higher-order terms are marked with curly brackets. This is something that we are implementing/expanding currently.

Great discussion!

[jfmc]

Thanks David for the summary of the hiord/hilog discussion!
Manuel’s answer is great from the Ciao side
I just want to add some more examples and thoughts.

Here is a more complex example with partial applications:

?- P = append, call(P, [1],[2],Z).

P = append,
Z = [1,2] ? 

yes
?- P = append, call(call(P, [1]),[2],Z).

P = append,
Z = [1,2] ? 

yes
?- P = append, call(call(call(P, [1]),[2]),Z).

P = append,
Z = [1,2] ? 

All the calls are equivalent. Things get hairy when dealing with the
module system anyway. When predicate symbols belong to different
modules we currently need some ‘meta_predicate’ declarations around.

In Ciao these three terms:

Ga = call(call(foo, X1, ..., Xn), Y1, ..., Ym)
Gb = call(foo, X1, ..., Xn, Y1, ..., Ym)
Gc = foo(X1, ..., Xn, Y1, ..., Ym)

are clearly different (do not unify) but as goals the are equivalent,
e.g., when doing call(Ga), call(Gb), or call(Gc).

I understand that hilog apply is similar to use one symbol for applying
one argument (like “blank” in haskell), that is used for parenthesis
after a variable or after a hilog declared symbol. E.g., if ‘foo’
is a hilog symbol then due to associativity, abusing unicode notation:

?- op(400,yfx,(␣)).

then all Ga,Gb,Gc correspond to the same term:

Ga = foo␣X1␣...␣Xn␣Y1␣...␣Ym

and this works:

?- X = Y␣a, X = p␣a.

X = p␣a,
Y = p ? 

yes

With something like it is possible to emulate hilog style:

callify(G, G2) :- nonvar(G), G = X␣Y, !,
    G2 = call(X2, Y),
    callify(X, X2).
callify(X, X).

X␣Y :- callify(X␣Y,G), call(G).

You can click here to load the example (of course this is just toy to check if my understanding of hilog is correct ).

[jasonhemann]

Tangentially related SO post: module - Are HiLog terms still useful in modern Prolog? - Stack Overflow

[herme]

Thanks Jason, I put a link there so that people can also see this discussion.

[David_Warren]

Jose suggested how to turn Ciao’s hiord treatment into hilog treatment. I’m not completely clear on the infix operator since that only works for binary hilog terms. But the idea is clear.

I was thinking that maybe an extension of Ciao’s hiord would be interesting. We (they) would extend the syntax to allow an arbitrary hiord term in functor position. And we would then allow (some) of these terms as heads of rules. If such a hilog term appeared as the head of a rule, it would be transformed into a “flattened” version and that would be compiled. The “flatten” would unwind the predicate position complex terms. E.g. (using hilog syntax) with a simple predicate:

unwind(Apply,FlatApply) :-
(functor(Apply,apply,_N)
→ Apply =… [apply,Pred|Args],
unwind(Pred,Flat),
Flat =… FlatList,
append(FlatList,Args,FlatApplyList),
FlatApply =… FlatApplyList
; FlatApply = Apply
).

This might (should) fail if the main functor symbol turns out to be a variable. Otherwise, this should give the user the expected behavior for hilog terms with the apply/n treated as call/n (as hiord). This is my understanding of what Teri was suggesting (I think) in the zoom.

I kind of like this. Ciao’s hiord call/n semantics, but allowing hilog terms to be heads of rules in many (most?) cases.

-David

[JanWielemaker]

Thanks. B.t.w. could you add code blocks between ``` (triple backquote) lines? That renders them nicely as code … And possible Manuel can give a greater selected group or in general regulars edit rights over posts? Note that edited posts are marked as such, you can quickly see the changes and revert if necessary. If someone misbehaves just deny this right. That is unlikely anyway.

Maybe we should give hilog a priority as PIP? Is seems this could be fairly easy and it would be a nice achievement.