Re: Unification algorithm in C/C++

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: whats the prob with goto
    ... >> plz help me out of this dilemma, coz i use a lot of goto in my codes.... ... Programming paradigms like structured programming, functional programming, ... complexity, as program size increases so does complexity. ... A loop like: ...
    (comp.lang.c)
  • Re: Unification algorithm in C/C++
    ... Carlo Capelli wrote: ... It uses a very simple unification algorithm, ... // 'The Art Of Prolog' by Sterling & Shapiro ... goto next; ...
    (comp.lang.prolog)
  • Re: nested while - how to go to the beginning of the first while?
    ... > I think it is instructive that you need labels and a precise definition ... > which lacks the clarity and simplicity of the goto version. ... complexity is often overlooked. ...
    (comp.lang.c)