1

I am working with the natural number definition in prolog that uses s(0),s(s(0))), so on and so forth, to define natural numbers. There is the add predicate:

add(0,N,N).
add(s(N),M,s(K)):-
    add(N,M,K).

Now originally mult was defined this way:

mult(0,N,0).
mult(s(N),M,K):-
    mult(N,M,L),
    add(L,M,K).

But I found that this leads to a stack overflow if I query with variables, say, like this:

mult(A,s(s(0)),s(s(s(s(0))))

So I added two additional clauses with constraints that state if only one of the arguments is a variable, it means there exists only one solution, so the program should not backtrack after finding a solution in these cases. This works and stopped the stack overflow that would occur previously, and the clauses look like this:

mult(s(N),M,K):-
    (var(N),\+var(M),\+var(K)),
    mult(N,M,L),
    add(L,M,K),!.

mult(s(N),M,K):-
    (var(M),\+var(N),\+var(K)),
    mult(N,M,L),
    add(L,M,K),!.

My issue now is figuring out a way to account for the case of querying in such a way I want the program to find all of the factors of a number. If I try and query

mult(A,B,s(s(s(s(0))))

I will get the factors, but the program will hang, never terminate, and then cause a stack overflow. I'm not quite sure how to constrain this case and setting a manual bound on the search tree seems like both a poor idea and not the correct way to fix this.

false
  • 10,264
  • 13
  • 101
  • 209
Elliott Goldstein
  • 59
  • 5
  • These are amazingly hard to get right. Here is a solution I wrote last year; many days were spent to make it work: [Peano README](https://github.com/dtonhofer/prolog_notes/blob/master/prolog_exercises/peano_numbers/README.md) – David Tonhofer Mar 09 '21 at 09:29

0 Answers0