How to write kind of Conditional Planning in Prolog?

Question

I tried to write a prolog code that can understand student program written in C#. Now I'm stuck in the process of recognizing the 'if' statement in student's program. For example: The following is the code that I expect from the student.

int d = int.Parse(Console.ReadLine());  // value d is inputted by user
int s = 0;

if (d>0)
    s = 2;
else if (d==0)
    s = 1;
else
    s = 0;

I defined the goal of this expected code as:

goal:- 
   hasVarName(Vid_s, s),
   hasVarName(Vid_d, d),
   hasVarValue(Vid_d, Vd),
   ((not(gt(Vd,0)); hasVarValue(Vid_s, 2)),           %eq: [Vd>0] -> [val_s = 2]
   ((gt(Vd,0); not(eq(Vd,0)); hasVarValue(Vid_s, 1)), %eq: [~(Vd>0)^(Vd=0)] -> [val_s = 1]
   ((gt(Vd,0); eq(Vd,0); hasVarValue(Vid_s, 0).       %eq: [~(Vd>0)^~(Vd=0)] -> [val_s = 0]

The problem is how can I represent the above student code in prolog facts and rules, to find out that the goal is satisfied for any possible conditions.

I tried to change the first part of the student code to become facts like the following, but don't really know how to represent the student's 'if' statement as facts/rules in prolog (I guess, I should not change it to prolog 'if', right?)

hasVarName(varID_d, d)
hasVarValue(varID_d, val_d)   %it is unknown, so I represent it as symbol 'val_d'

hasVarName(varID_s, s)
hasVarValue(varID_s, 0)

And another one, in my goal, when I have comparison such as gt(Vd,0) I think I cannot use the prolog greater than operator, neither Vd> 0 nor Vd @> 0 cause the value in Vd is actually a certain value entered by user, but it is represented as symbolic value (in this case it is: val_d).

Note: using the above goal, I think the defined goal will be satisfied if student code is changed to the following code.

int d = int.Parse(Console.ReadLine());  // value d is inputted by user
int s = 0;

if (d>0)
    s = 2;
else if (d==0)
    s = 1;

or

int d = int.Parse(Console.ReadLine());  // value d is inputted by user
int s = 10;           // any random initialization

if (d>0)
{
    int x = 2;       // unnecessary step, but still Ok.
    s = x;
}
else if (d==0)
    s = 1;
else
    s = 0;

But again, I need help/idea how this code can be represented in prolog as action/rule/fact to meet the goal.

Any help is really appreciated.

Many thanks

CapelliC CapelliC · Accepted Answer · 2012-10-25T13:16:34

Usually a language implementation requires an abstract syntax tree, where it's convenient to specify the semantic actions that implements the constructs we are allowed to express.

You seem skipping the phase of building the syntax tree, and (by hand?) represent the intermediate level of the program.

If you stick to such medium level representation, you can use a recursive term (an abstract tree, in effect) like if(Condition, Then, Else) where each var it's in turn a syntax tree.

Otherwise, a more practical representation (usually applied for imperative language), use the concepts of basic blocks (an instruction sequence without jumps) and then labels, to describe the execution flow.

The result it's a graph, and the behaviour of the program is determined by the 'topology' of that representation.

goal:- 
   hasVarName(Vid_s, s),
   hasVarName(Vid_d, d),
   hasVarValue(Vid_d, Vd),

   %eq: [Vd>0] -> [val_s = 2]
   ((not(gt(Vd,0)); hasVarValue(Vid_s, 2), goto(label(0))),

   %eq: [~(Vd>0)^(Vd=0)] -> [val_s = 1]
   ((gt(Vd,0); not(eq(Vd,0)); hasVarValue(Vid_s, 1), goto(label(0))),

   %eq: [~(Vd>0)^~(Vd=0)] -> [val_s = 0]
   ((gt(Vd,0); eq(Vd,0); hasVarValue(Vid_s, 0)), % the goto is useless here...

   label(0),
   .....

Note that I didn't pay any attention to describe correctly your sample program, just placed the jumps to show this possibility...

edit I think that the general problem can't be solved, being equivalent to the halting problem for a Turing Machine. For the particular case at hand, without loops, I would attack the problem using abstract interpretation on the AST. I.e. an interpreter that computes what's interesting.

If it's feasible depends on the generality of your target programs. You should be able to partition the integer domain for each variable involved in each condition point. Things become rapidly complex...

Specifically, at the condition point of the IF THEN ELSE attempt to partition the domain. Using such approach, let Prolog execute the IF testing both branches, propagating the values. But, as I said, is not really easy...

How to write kind of Conditional Planning in Prolog?

1 Answers