search

photonlines / Python-Prolog-Interpreter

A simple Prolog Interpreter written in a few lines of Python 3. It runs a limited subset of Prolog and uses backtracking and generators in order to perform its magic.
MIT License
246 stars 25 forks source link

Does recursion find all the solutions? #4

Open stefan-c-kremer opened 4 years ago

stefan-c-kremer commented 4 years ago

This project is great. I have been working on some examples and came across what I think may be an issue. I would like some feedback whether I'm wrong in my thinking...

I have the following Prolog code:

predecessor( one, zero ).
predecessor( two, one ).
plus( two, zero, two ).
plus( two, one, three ).
plus( two, two, four ).

times( X, zero, zero ).
times( X, Y, Z ) :- predecessor( Y, Y1 ), times( X, Y1, P ), plus( X, P, Z ).

I am issuing the query:

times( two, Y, Z )

I was expecting to get:

Y = [zero, one, two]
Z = [zero, two, four]

but only the first two answers appear.

Any ideas why?

Stefan

robwalton commented 4 years ago

Hi @stefan-c-kremer,

I also see only the first two answers: the solver misses X=two, Z=four. swi-prolog does find them:

?- times( two, Y, Z ).

Y = Z, Z = zero ;
Y = one,
Z = two ;
Y = two,
Z = four ;
false.
stefan-c-kremer commented 4 years ago

@robwalton Hi Rob. Thanks for confirming my observation and comparing it to swi-prolog.

robwalton commented 4 years ago

So I drafted an interpreter from scratch that finds these solutions but is didn't solve the Einstein problem. My feeling when I was working on this was that the issue with @photonlines code might be with the way variables which have been instantiated with each other are handled. I don't remember why I thought this though!