Re: Unification algorithm in C/C++

I would really appreciate if you can mail me the entire code. Thank you
very much. My id is lsunanda@xxxxxxxxx
Sunanda.

Carlo Capelli wrote:
I wrote a simple PROLOG interpreter many years ago (my first C++ program).
It uses a very simple unification algorithm, but of course the real
complexity stay in variables handling...
If you need the full code, I can send it to you...
The code I pasted here has lost any formatting, but sources are more
readable...

//-----------------------------------------------------
// generate MGU of terms t1, t2
// return 0 if failure (t1, t2 don't unify)
//
// the simple stacked, abstract algorithm is keep from
// 'The Art Of Prolog' by Sterling & Shapiro
//
int UnifyStack::work(Term t1, stkpos envp1, Term t2, stkpos envp2)
{
termPair *tp;
for ( ; ; )
{
if (t1.type(f_VAR)) // here be dragons!
{
if (Var(t1) == ANONYM_IX)
goto next;
stkpos ix1 = Var(t1) + envp1;
if ((t1 = vs->getvar(ix1, &envp1, &ix1)).type(f_NOTERM))
{
if (t2.type(f_VAR))
{
if (Var(t2) == ANONYM_IX)
goto next;
ts->bind(ix1);
stkpos ix2 = Var(t2) + envp2;
if ((t2 = vs->getvar(ix2, &envp2, &ix2)).type(f_NOTERM))
{
if (ix1 != ix2)
vs->setshare(ix1, ix2);
}
else
vs->setvar(ix1, t2, envp2);
}
else
{
ts->bind(ix1);
vs->setvar(ix1, t2, envp2);
}
goto next;
}
}
if (t2.type(f_VAR))
{
if (Var(t2) == ANONYM_IX)
goto next;
stkpos ix2 = Var(t2) + envp2;
if ((t2 = vs->getvar(ix2, &envp2, &ix2)).type(f_NOTERM)) {
ts->bind(ix2);
vs->setvar(ix2, t1, envp1);
goto next;
}
}
if (!t2.type(t1.type()))
return 0;
switch (t1.type())
{
case f_ATOM:
case f_INT:
if (TermData(t1) != TermData(t2))
return 0;
break;
case f_DOUBLE:
if (Double(t1) != Double(t2))
return 0;
break;
case f_STRUCT:
{
Term *pa1, *pa2;
int na1, na2;
if (t1.structData(&pa1, &na1) != t2.structData(&pa2, &na2) ||
na1 != na2)
return 0;
for (int i = na1 - 1; i >= 0; i--)
{
tp = push();
tp->t1 = pa1[i];
tp->i1 = envp1;
tp->t2 = pa2[i];
tp->i2 = envp2;
}
check_overflow();
}
break;
case f_LIST:
if (t1.LNULL() && t2.LNULL())
goto next;
if (!t1.LNULL() && !t2.LNULL())
{
const List& l1 = t1, &l2 = t2;
tp = push();
tp->t1 = l1.tail();
tp->i1 = envp1;
tp->t2 = l2.tail();
tp->i2 = envp2;
tp = push();
tp->t1 = l1.head();
tp->i1 = envp1;
tp->t2 = l2.head();
tp->i2 = envp2;
check_overflow();
}
else
return 0;
break;
case f_SYSDATA:
if (!SysDataPtr(t1)->unify(t2))
return 0;
break;
default:
ASSERT(0);
}
next:
if (free == 0)
return 1;
tp = v + --free;
t1 = tp->t1;
envp1 = tp->i1;
t2 = tp->t2;
envp2 = tp->i2;
}
}


<LSunanda@xxxxxxxxx> ha scritto nel messaggio
news:1145991408.835096.126270@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I am looking for an efficient implementation of Unification algorithm
in C/C++ for my research. No functional languages please.
I would appreciate any kind of help.

Thanks in advance,
Sunanda.


.

Relevant Pages

  • Re: Unification algorithm in C/C++
    ... I wrote a simple PROLOG interpreter many years ago. ... It uses a very simple unification algorithm, ... complexity stay in variables handling... ... goto next; ...
    (comp.lang.prolog)
  • Re: Prolog Execution Algorithm
    ... > algorithm, but I'm looking for a more elaborate version (with ... Some 20 years ago I wrote a simple Prolog interpreter, not using the WAM, ... You will see than query() procedure has more than three labels inside, ... goto A1; ...
    (comp.lang.prolog)
  • Re: using exceptions to implement backjumping?
    ... >> This is bad software engineering. ... >> handle exceptional situations and not to be used as "generalzied ... In Prolog, Ada, Java in whatever. ... >What should we use in Prolog if we want "generalized goto" (and the only ...
    (comp.lang.prolog)