Hacker News Reader

Comment by andrewcooke | Hacker News Reader

so can you define something like

  transitive(X) :- [ X(A,C) :- X(A,B), X(B,C) ]

(which generalises the decendent example)? more generally, i guess i am asking whether those horn clause things are first class.

View on HN

A different problem to the 'non-first-class-ness' of clauses that others have mentioned is that Prolog is really just a unification engine, not a reasoning engine. Thus, even a manual definition

    x(A, C) :- x(A, B), x(B, C).

is not always a good idea. For example, if you put this clause first (in the definition of `x`), it'll always try to reason by transitivity, rather than ever checking directly. The sub-clauses will then be checked by transitivity, &c. This is easy to fix by not putting this clause first; but then you run into further problems if `x` is reflexive; consider

    le(1, 1).
    le(A, C) :- le(A, B), le(B, C).

Now

    ?- le(1, 0).

will unify with `le(A, C)` by `A = 1`, `C = 0`, and then search for `B` such that `le(A, B)`. It'll put `B = 1`, and then try to solve `le(B, C)`, i.e., just `le(1, 0)` --and you're at the first stage of an infinite loop.

Unfortunately, no. The names of predicates---functors in Prolog-speak---have to be symbols, not variables, and Horn clauses themselves aren't first-class either.

You can do it via metaprogramming; a functor can be converted to a list [name, param1, param2, ...], and then you can write normal Prolog operations on the list that bind variables and such, and then convert back. This page shows how to use that to build a higher-order map function: http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming

Here's a paper on other approaches; I'm not sure if any of the higher-order Prolog approaches ever caught on, though: http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf

There are also Prolog-derived languages that support higher-order programming 'natively', such as Teyjus (http://teyjus.cs.umn.edu) and Curry (http://www-ps.informatik.uni-kiel.de/currywiki).

Do you use either of these personally? Would you recommend them?

I had a terrible time getting Teyjus up and running. I played around with Curry a while ago (using PAKCS (http://www.informatik.uni-kiel.de/~pakcs), if I recall correctly), but didn't explore enough to say anything about it.

Nope, in vanilla Prolog you'd have to type "X(A,C) :- X(A,B), X(B,C)." for every single X you want to be transitive.

In formal logic, "A if B" is just syntactic sugar for "(B && A) || (!B)" or in English: when B is true, A is true. (But when B is false, A could be either true or false.) So you could rewrite your expression as (edit: fixed):

  transitive(X, A, B, C) :- (X(A,B), X(B,C), X(A,C)); not(X(A,B), X(B,C)).

Prolog also has syntax for if-then, so

    x(A, C), x(A, B), x(B, C); not(x(A, C)).

can essentially be re-written as

    x(A, C) -> x(A, B), x(B, C); true.

(This saves testing `x(A, C)` twice. Also, `->` implicitly cuts, presenting backtracking over `x(A, C)`; but that shouldn't matter here.) However, this set-up mistakenly has `x(A, C)` as the antecedent; I think you actually want it as the consequent.

though be careful how you do this -- it's easy to end up with a divergent program, as prolog tries to:

* prove X(A,B)

* realizes that it can prove this if it can prove transitive(X, A, B, C), and then prove X(B,A)

* realizes that it can prove this if it can prove transitive(X, B, A, C), and then prove X(A,B)

* ...

Such behavior is easily avoided with tabling.

There are a couple of ways around this -- all of which fall under "be careful". :-)

The problem is that transitive builds up a relationship between a functor and it's variables by trying to unify them with already known facts. But no new fact is generated.

     transitive(Functor) :-
       Rel1 =.. [Functor,A,B],
       Rel2 =.. [Functor,B,C],
       Rel3 =.. [Functor,A,C],
       call(Rel1),call(Rel2),call(Rel3).
 
     descendant(a,b).  #fact1
     descendant(b,c).  #fact2
     transitive(descendant) ;; says 'no'
     descendant(a,c).
     transitive(descendant) ;; says 'yes'

This functor only tells us if the database has a transitive relationship recorded.

If one wants the truth to be derived from the first two facts one would have to say

     transitive(F,A,B,C) :-
       R1 =.. [F,A,B],
       R2 =.. [F,B,C],
       call(R1),call(R2).

which derives transitivity from the first two facts, the last relationship (R3) is what we want to conclude, not what we want to find in the database.

Neither call though, will derive from fact1 and fact2 that "descendant(a,c)." is true. To arrive there you would have to "assert" these (new) facts explicitly in the transitive(...) definition.

But Prolog is not my comfort zone, there might be (and probably is) a way out of that dilemma.

Note that there's another flaw: `transitive` as defined only checks if there's one instance of transitivity that works. If you wanted to check (rather than assert) transitivity, you'd need something more like

    transitive(Functor) :-
        not(
            call(Functor,A,B),
            call(Functor,B,C),
            not(call(Functor,A,C))
        ).

(It's been a while since I've Prologged, so I may be forgetting something subtle about why you'd need to use the dribble `=..` to build something callable; but that's not the point, of course!)

Right, I see this as the third way: stating transitivity which must not be asserted explicitly. The question arises what one would want to reach with a call to transitive(descendant).

(aside: the X =.. [F,A,B] is the prolog way of saying eval("F(A,B)"). and make it callable)

As far as I recall you can add new facts easily enough using asserta or assertz but I'm pretty sure this approach doesn't work for rules.

Reply on news.ycombinator.com