CODEWITHSUNDEEP
prolog
Emilio Platzer
Emilio Platzer

Reputation: 2479

How to limit depths structures in prolog

I trying to write a grammar that generates expresions. If I do not set a depth limit the recursion goes throw the last variable and be infinity. I do not know how to limit depth branching the tree recursion.

I try this:

constant('c1').
variable('v1').
operator('+').

expresion(C) :- constant(C).
expresion(V) :- variable(V).
expresion(bin(E1,O,E2)) :- 
    expresion(E1), 
    operator(O), 
    expresion(E2).

expresionL(C, 0) :- constant(C).
expresionL(V, 0) :- variable(V).
expresionL(bin(E1,O,E2), N) :- 
    N_1 is N-1, 
    expresionL(E1, N_1), 
    operator(O), 
    expresionL(E2, N_1).

Here is a live online version.

If I query Expresion(X) y obtain:

X = c1
X = v1
X = bin(c1, (+), c1)
X = bin(c1, (+), v1)
X = bin(c1, (+), bin(c1, (+), c1))
X = bin(c1, (+), bin(c1, (+), v1))
X = bin(c1, (+), bin(c1, (+), bin(c1, (+), c1)))

...to infiniy and beyond! (recursing over the las expresion). I never see v1.

I write expresionL to be a depth limited version of expression.

If I query expresion(bin('v1','+','c1')). or query expresion(bin('v1','+','c1')). I get true.

If I query expresionL(X,1). I get:

X = bin(c1, (+), c1)
X = bin(c1, (+), v1)
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 51.1Mb, trail: 1Kb
  Stack depth: 1,673,655, last-call: 0%, Choice points: 13
  Possible non-terminating recursion:
    [1,673,655] expresionL(_1404, -1673622)
    [1,673,654] expresionL(<compound bin/3>, -1673621)

I do not see v1 in the first parameter of bin of any answers. The inifite recursion does not stops.

How can I write a expresion(E, N) version that limit recursion to N steps?

Notes:

Upvotes: 0

Views: 156

Answers (1)

jf_
jf_

Reputation: 3489

The problem is that you allow the expression to be evaluated recursively even if N <= 0, because while backtracking, the last rule is a viable option even if N becomes zero or even less. You need to rule that out in the last rule using N > 0.

Adding that to the code:

expresionL(C, 0) :- constant(C).
expresionL(V, 0) :- variable(V).
expresionL(bin(E1,O,E2), N) :- 
    N > 0, # select this rule only when the others fail
    N_1 is N-1, 
    expresionL(E1, N_1), 
    operator(O), 
    expresionL(E2, N_1).

results in:

?- expresionL(X,1).
X = bin(c1, +, c1) ;
X = bin(c1, +, v1) ;
X = bin(v1, +, c1) ;
X = bin(v1, +, v1) ;
false.

Upvotes: 2

Related Questions