Unification algorithm in C/C++ - PROLOG

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@gmail.com> ha scritto nel messaggio
news:1145991408.835096.126270@y43g2000cwc.googlegroups.com...
> 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.
>

I would really appreciate if you can mail me the entire code. Thank you
very much. My id is lsunanda@gmail.com
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@gmail.com> ha scritto nel messaggio
> news:1145991408.835096.126270@y43g2000cwc.googlegroups.com...
> > 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.
> >

I need an implementation of Unification Algorithm in C++ for a research. Is it possible to email me your code for Unification Algorithm. I would really appreciate if you can email me the entire code. Thank you
in advance. My email is ramtin_khan2004@yahoo.com

Ramtin

I need an implementation of Unification Algorithm in C++ for a research.
Is it possible to email me your entire code for Unification Algorithm.
I would really appreciate if you can.

Thank You

Cátia Simões