I want to use Prolog to order some things, and I keep getting stack overflow errors

Question

For my physics class, we're racing various rolling things down a track and trying to figure out what makes the fastest ones fastest.

I want to save time and not race everything against everything. For example, the can of chicken soup beats the can of clams, and the can of clams beats the can of tomatoes. So, the chicken soup must beat the tomatoes.

Here is everything I've written so far:

% Define everything we know
outspeeds(chicken_soup, clams). % This represents "chicken_soup outspeeds clams."
outspeeds(beef, clams).
outspeeds(chicken_soup, beef).
outspeeds(chicken_soup, tomatoes).
outspeeds(clams, tomatoes).

% Now define inter-relationships
% A outspeeds B if A outspeeds some 3rd party "X" and they outspeed B.
outspeeds(A, B) :- outspeeds(A, X), outspeeds(X, B).

The problem is when I try to ask questions about it. Here is what happens if I try to find everything that chicken_soup outspeeds:

?- outspeeds(chicken_soup, X).
X = clams ;
X = beef ;
X = tomatoes ;
X = tomatoes ;
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1.0Gb, global: 4Kb, trail: 0Kb
ERROR:   Stack depth: 12,197,875, last-call: 0%, Choice points: 5
ERROR:   Probable infinite recursion (cycle):
ERROR:     [12,197,875] user:outspeeds(tomatoes, _1098)
ERROR:     [12,197,874] user:outspeeds(tomatoes, _1118)

Why is it doing this? What additional clause do I need in the last outspeeds to keep it from a stack overflow?

I'm new to Prolog so if there's anything horribly wrong with the project as whole please tell me.

Answer 1

"Calvin, are you sure this is for the actual physics class?"

But maybe this will help:

Professor Wirth has inoculated me with a lifetime hate of debuggers, and I like printout statements:

outspeeds_s(chicken_soup, clams, Sd, Sd)    :- format("Fact: outspeeds(~w, ~w)\n",[chicken_soup,clams]).
outspeeds_s(beef, clams, Sd, Sd)            :- format("Fact: outspeeds(~w, ~w)\n",[beef,clams]).
outspeeds_s(chicken_soup, beef, Sd, Sd)     :- format("Fact: outspeeds(~w, ~w)\n",[chicken_soup,beef]).
outspeeds_s(chicken_soup, tomatoes, Sd, Sd) :- format("Fact: outspeeds(~w, ~w)\n",[chicken_soup,tomatoes]).
outspeeds_s(clams, tomatoes, Sd, Sd)        :- format("Fact: outspeeds(~w, ~w)\n",[clams,tomatoes]).

outspeeds_s(A, B, Sd_in, Sd_max) :- 
    format("Stack ~w: The question is outspeeds(~w, ~w)?\n",[Sd_in,A,B]),
    format("Stack ~w: ~w is fresh variable, we will now try outspeeds(~w, ~w)?\n",[Sd_in,X,A,X]),
    Sd_next is Sd_in+1,
    % can't ask the user in SWISH, so we sleep 3 seconds instead
    sleep(3),
    outspeeds_s(A, X, Sd_next, Sd_max_1),
    format("Stack ~w: We found that outspeeds(~w, ~w)!\n",[Sd_in,A,X]),
    format("Stack ~w: But does outspeeds(~w, ~w)?\n",[Sd_in,X,B]),
    % can't ask the user in SWISH, so we sleep 3 seconds instead
    sleep(3),       
    outspeeds_s(X, B, Sd_next, Sd_max_2),
    Sd_max is max(Sd_max_1, Sd_max_2),
    format("Stack ~w: We also found that outspeeds(~w, ~w)!\n",[Sd_in,X,B]),
    format("Stack ~w: So we can conclude that outspeeds(~w, ~w)!\n",[Sd_in,A,B]).

outspeeds(X,Y) :-
    format("outspeeds(~w, ~w)?\n",[X,Y]),
    outspeeds_s(X,Y,0,Ss_max),
    format("Found that outspeeds(~w, ~w) with max stack depth ~w\n",[X,Y,Ss_max]).

You can distinguish the infinite recursion asking for outspeeds(tomatoes,_)

Try it in SWISH.

(SWISH sadly does not accept user input via get/1, this needs to be added.)

For actually solving the problem, several options are open to you to make the potential tripmine outspeeds(A, B) :- outspeeds(A, X), outspeeds(X, B). harmless. Read this recent question for an idea or two:

Recursive loop exit statement needed