Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Anybody here know prolog?

  1. Oct 31, 2004 #1
    This is supposed to recursively define a function sum(X,Y,Z) meaning X + Y = Z. how could anything be simpler, right?

    Code (Text):

    sum(0,Y,Y).
    sum(s(X),Y,s(Z)) :- sum(X,Y,Z).
     
    It's very good at telling that 0+1=1 or 0+2=2, etc. But give it anything other than 0 for the first variable and it's lost. What's wrong? :mad:
     
  2. jcsd
  3. Oct 31, 2004 #2
    I don't have a Prolog interpreter at hand to check this, but I can make a few suggestions that you can try yourself; at least they will give some clues.

    0) I hope a successor predicate is implemented in your interpreter!

    1) Prolog works by unifying your query to the head (left-side) of clauses; and unifying is NOT evaluating. So the most probable reason is that compound terms like s(X) or s(Z) in the head of the second clause won't unify with atomic entities such as numbers, in a query like sum(1,2,3).

    Try this alternate to your second clause:

    sum(X1,Y,Z1) :- X1 is s(X), Z1 is s(Z), sum(X,Y,Z).

    (Syntax might vary for the evaluation operator "is"; it might be implemented as "=".)

    Hope this helps.

    ---
    Edit:
    I fail to recall if s(X) will be at all evaluable. But something that will work in most interpreters is

    sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z).

    As for the behavior of the s() predicate, I'm not sure. You can try... and tell us.

    ---
    Edit 2:
    Of course, having the ability to evaluate expression you can write a single-clause sum() as

    sum(X,Y,Z) :- X is Y+Z.

    But I suppose the former has an exercising value. Sorry for the multiple edits, to me it's "long time no see" for Prolog.
     
    Last edited: Oct 31, 2004
  4. Oct 31, 2004 #3
    Thanks for the suggestions, but I still don't have the answer.

    0) yes, there is a successor function. For example this program:
    Code (Text):
    int2s(0,0).
    int2s(N,s(S)) :- N>0, N1 is N-1, int2s(N1,S).
    works this way:
    | ?- int2s(5,T)
    T = s(s(s(s(s(0)))))?
    yes

    1) sum(X1,Y,Z1) :- X1 is s(X), Z1 is s(Z), sum(X,Y,Z).
    doesn't compile; gives
    error: wrong arithmetic expression : s(_570b34)
    error: wrong arithmetic expression : s(_570ba8)

    2) sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z).
    sort of defeats the purpose, which was to understand how the successor function works, but I tried it anyway in the interest of science. :smile:
    It compiles, and responds reasonably to queries involving addition of 0 to a number, but other queries result in errors I don't understand. For example, this series of queries and responses:
    Code (Text):
    | ?- compile(math)
    Compiling...math.pl
    compiled in 0 milliseconds

    yes
    | ?- load(math)
    loading....math.out

    yes
    | ?- sum(0,1,1)

    yes
    | ?- sum(X,1,1)
    X = 0?
    yes
    | ?- sum(X,1,2)
    ** Error ** number_expected:_570828+1
    | ?- sum(1,1,2)
    ** Error ** number_expected:_570828+1
    | ?-
     
  5. Oct 31, 2004 #4
    Hmmm...

    It turns out that the original program
    Code (Text):
    sum(0,Y,Y).
    sum(s(X),Y,s(Z)) :- sum(X,Y,Z).
    does work. I just wasn't forming the queries correctly. Here's an example of what it gives:
    Code (Text):
    | ?- sum(s(s(0)),s(s(s(s(s(0))))),T)
    T = s(s(s(s(s(s(s(0)))))))?
    yes
    Guess it'll take a while to figure out how to do something useful with that.
     
  6. Oct 31, 2004 #5
    Hmmm... and note that this DOESN'T mean that s() is something built-in into your Prolog interpreter. The s() is interpreted symbolically; the whole thing would've equally worked if representing 2 as after(after(0)), where of course after() is nothing special. (And substituting after() for s() accordingly in your clauses, of course.)

    As for the failure in " sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z). ",
    1) I assume you did include the initial clause too, "sum(0,Y,Y)."
    2) _<number> is the construct the interpreter is using to refer to an unbound variable; the error is saying, "I can't add 1, in X+1 (or Z+1), if X (or Z) has no value". A possible test is to change the order of the second clause (again, experimenting) as
    sum(X1,Y,Z1) :- sum(X,Y,Z), X1 is X+1, Z1 is Z+1.
    so it'll recurse before the evaluation. (Strange, though.)

    Another interesting test is to combine your original problem with the given predicates for int2s() (which "translate" an integer into a symbolic form made of s's). Something like

    ... int2s as above...

    sum(0,Y,Y).
    sum(X,Y,Z) :- int2s(X,Xs), int2s(Z,Zs), Xs is s(X0), Zs is s(Z0), sum(X0,Y,Z0).

    or, alternatively,

    sum(0,Y,Y).
    sum(X,Y,Z) :- int2s(X,s(X0)), int2s(Z,s(Z0)), sum(X0,Y,Z0).

    and check if it accepts integers now.
     
    Last edited: Oct 31, 2004
  7. Oct 31, 2004 #6
    >>.. and note that this DOESN'T mean that s() is something built-in into your Prolog interpreter.
    Thanks for pointing that out. Now it makes more sense that it doesn't produce a numerical result.


    >>1) I assume you did include the initial clause too, "sum(0,Y,Y)."
    Of course.

    >>A possible test is to change the order of the second clause (again, experimenting) as
    >>sum(X1,Y,Z1) :- sum(X,Y,Z), X1 is X+1, Z1 is Z+1.
    Interestingly, that almost works. It seems to be a case of yes/maybe. Here are some sample queries to that:
    Code (Text):
    | ?- sum(0,1,T)
    T = 1?
    yes
    | ?- sum(1,1,T).........(
    T = 2?
    yes
    | ?- sum(4,6,T)
    T = 10?
    yes
    | ?- sum(5,2,7)..........(here I supplied all 3 literals & it responded correctly)

    yes
    | ?- sum(1,2,3)..........(same here)

    yes
    | ?- sum(T,2,5)..........(here I supply a variable for the first term; response is appropriate)
    T = 3?
    yes
    | ?- sum(2,T,5)..........(but it can't deal with the variable as the 2nd term)
    ** Error ** number_expected:_570828+1
    | ?- sum(4,2,7)..........(and if I supply 3 literals that don't add correctly, instead of saying "no" it hangs
    | ?-..........................(I had to use ctrl-c to get out of that loop)
    Your last two suggestions are interesting, but they didn't work. The first one
    Code (Text):
    sum(0,Y,Y).
    sum(X,Y,Z) :- int2s(X,Xs), int2s(Z,Zs), Xs is s(X0), Zs is s(Z0), sum(X0,Y,Z0).
     
    doesn't compile, giving two "wrong arithmetic expression" errors on the s(X0) and s(Z0) expressions.
    The last one
    Code (Text):
    sum(0,Y,Y).
    sum(X,Y,Z) :- int2s(X,s(X0)), int2s(Z,s(Z0)), sum(X0,Y,Z0).
     
    compiles but doesn't do what we wanted. It gives good responses to queries in the form (T,4,4) or (0,4,4) for example, but any other format gives "error : number expected".

    Still, there should be some way to combine the predicates. I'll work on it some more as time permits.

    PS: If you want to play around with small prolog programs, here's a link to a cute online prolog implementation. It's not what I've been using (I'm using B-prolog) but it seems to work the same for these little programs.
    http://kti.ms.mff.cuni.cz/~bartak/prolog/testing.html
     
  8. Nov 1, 2004 #7
    "Don't give a man a fish, but a fishing rod." Thanks for the link!

    Edit: After some sleep :), I can see I forgot, in the second variant of the last example, to convert the s's back to numbers, before recursing...
     
    Last edited: Nov 1, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?