interpret.c is meant to implement a bytecode interpreter for a custom bytecode made for prolog. However, it has a bug when dealing with and. Basically, it needs to store the variable vars and call (and maybe other variables) on the continuation stack to restore these values. Also, it stores some information on stack that is freed upon backtracking. Memory leaks are possible. test.S contains a program that doesn't work as exected and test.pl is the program it was compiled from. Step through the bytecode to see where it went wrong. Then, think through the problem step by step to find what information to push to the continuation stack and backtracking stack to work and avoid memory leaks. interpret.c: #include <stdlib.h>
/* #include <string.h> */
/* #include <stdio.h> */

/* #include "interpret.h" */

#include "types.h"
/* #include "symbols.h" */

/**** Symbols ****/
struct SymbolTableEntry {
  intptr_t arity;
  char *name;
};
extern struct SymbolTableEntry *symbol_table;

int functor_arity(symbol s) {
  return symbol_table[(s-1)/2].arity;
}

/**** Machine definition ****/
/* The program counter */
term pc = NULL;

/* The program stack */
List *stack = NULL;

/* Stack of success continuations */
List *scont = NULL;

/* The current call */
term call = NULL;

/* The current matching vars */
term* vars = NULL;

/* Whether the last call succeeded */
char status = 1;

enum Operation {
  /* push a value */
  PUSH = 11,
  /* push a delimiter */
  DELINEATE = 13,
  /* push the current environemnt */
  RECORD = 15,
  /* undo bindings if the last action was a failure */
  UNDO = 17,
  /* backtrack if the last action was a failure */
  BACKTRACK = 19,
  /* branch if the last action was a failure */
  BRANCH = 21,
  /* go to the address and push the next instruction to the
   *  continuation stack */
  CALL = 23,
  /* go to the address */
  JUMP = 25,
  /* return to the continuation at the top of the stack */
  RET = 27,
  /* match a magmoid and store the bindings */
  MATCH_CALL = 29
};

/**** Helpers ****/
#define IS_TERM(T) *(T) % 2
#define IS_VAR(T) *(T) % 2 == 0
#define IS_MAG(M) IS_TERM(M) && (M) >> 63
#define MAG_VARS(M) *(M) >> 1 & 0x7fff
#define MAG_TERMS(M) *(M) >> 16 & 0x7fffffffff

/* Add an element to the stack */
void push(void *i) {
  List *this = malloc(sizeof(List));
  this->item = i;
  this->next = stack;
  stack = this;
}

/* Remove and return the element at the top of the stack */
void *pop(void) {
  if (stack) {
    void *i = stack->item;
    List *old_stack = stack;
    stack = stack->next;
    free(old_stack);
    return i;
  }
  return NULL;
}

/* Undo bindings on the stack until the last choicepoint
 * 
 * Side Effects: removes all bindings and the NULL marker
 *  on the stack
 */
void undo_bindings(void) {
  for (term addr = pop(); addr; addr = pop()) {
    *addr = (symbol)NULL;
  }
}

/* Find the representative of a term
 *
 * Note: unlike some Prolog implementations that use a
 *  self-pointer to represent an unbound variable, we
 *  use a null-pointer
 */
term rep(term t) {
  while (*t && IS_VAR(t)) {
    t = (term)*t;
  }
  return t;
}

/**** Matching and copying ****/

/* Copies template with the variables requested
 *
 * Preconditions: template one element of a magmoid
 */
term copy_template(term template,
                   term *vars) {
  term copy;
  if (IS_TERM(template)) {
    int arity = functor_arity(*template);
    copy = malloc(sizeof(symbol)*(arity+1));
    copy[0] = *template;
    for (int i = 1; i <= arity; i++) {
      copy[i] =
	(symbol)copy_template((term)*(template+i), vars);
    }
  } else {
    copy = malloc(sizeof(symbol));
    *copy = (symbol)(vars+*template/2);
  }
  return copy;
}

/* Unify arbitrary terms a and b
 *
 * Side effects: modifies variables a and b so they are
 *  equal, adds to stack
 */
int unify(term a, term b) {
  a = rep(a);
  b = rep(b);
  if (*a == *b) {
    /* Either a and b have the same functor or are the
       same variable */
    int arity = functor_arity(*a);

    /* Unify children (or do nothing for variables) */
    for (int i = 1; i <= arity; i++) {
      if(!unify(a+i, b+i)) {
	return 0;
      }
    }
    return 1;
  } else if (IS_VAR(a)) {
    push(a);
    *a = (symbol)b;
    return 1;
  } else if (IS_VAR(b)) {
    push(b);
    *b = (symbol)a;
    return 1;
  } 
  /* Failure */
  return 0;
}

/* Match the template with the term, unifying as
 * necessary
 *
 * Preconditions: template is represented as returned by
 *  variable_replace, vars contains enough space for
 *  all variables in template
 * Side effects: modifies t to unify with the template
 */
int match(term template, term t,
	  term *vars) {
  t = rep(t);
  if (IS_TERM(template)) {
    /* template is a term */
    if (IS_TERM(t)) {
      /* t is also a term */
      if (*template == *t) {
	/* same functor, so match children */
	int arity = functor_arity(*t);
	for (int i = 1; i <= arity; i++) {
	  if (!match((term)*(template+i),
		     (term)*(t+i),
		     vars)) {
	    return 0;
	  }
	}
	return 1;
      } else {
	/* functor is different, so this is a failure */
	return 0;
      }
    } else {
      /* copy the template into t */
      push(t);
      *t = (symbol)copy_template(template, vars);
      return 1;
    }
  } else {
    term *var = vars+*template/2;
    if (*var) {
      /* the variable is set already, so unify */
      return unify(*var, t);
    } else {
      /* set the variable */
      *var = t;
      return 1;
    }
  }
}

/**** Machine loop ****/
int execute(term entrypoint, symbol main_symbol) {
  pc = entrypoint;
  call = &main_symbol;
  while (1) {
    switch (*pc) {
    case PUSH:
      push(pc+1);
      pc += 2;
      break;
    case DELINEATE:
      push(NULL);
      pc++;
      break;
    case RECORD:
      if (status) {
        push(vars);
        push(scont);
        push(pc+1);
        push(call);
      }
      pc++;
      break;
    case UNDO:
      if (!status) {
        undo_bindings();
      }
      pc++;
      break;
    case BACKTRACK:
      if (!status) {
        if (!stack) {
          return 0;
        }
        while (!(call = pop())) {
          undo_bindings();
        }
        pc = pop();
        scont = pop();
        term *vars = pop();
        free(vars);
      } else {
        pc++;
      }
      break;
    case BRANCH:
      if (!status) {
        pc = (term)*(pc+1);
      } else {
        pc += 2;
      }
      break;
    case CALL:
      {
        List *this = malloc(sizeof(List));
        this->item = pc+3;
        this->next = scont;
        scont = this;
      }
      /* continue */
    case JUMP:
      call = copy_template((term)*(pc+1), vars);
      pc = (term)*(pc+2);
      break;
    case RET:
      status = 1;
      if (!scont) {
        return 1;
      }
      pc = scont->item;
      List *old = scont;
      scont = scont->next;
      free(old);
      break;
    case MATCH_CALL:
      vars = malloc(sizeof(symbol)*MAG_VARS(pc+1));
      status = match(*((term *)*(pc+1)+1), call, vars);
      pc += 2;
      break;
    /* case MATCH: */
    }
  }
}

/* void print_term(term p) { */
/*   p = rep(p); */
/*   if (*p % 2 == 0) { */
/*     printf("%p", (void *)p); */
/*   } else { */
/*     printf("%s", functor_name(*p)); */
/*     int a = functor_arity(*p); */
/*     if (a > 0) { */
/*       putc('(', stdout); */
/*       for (int i = 1; i <= a; i++) { */
/* 	print_term(p+i); */
/* 	if (i != a) { */
/* 	  putc(',', stdout); */
/* 	  putc(' ', stdout); */
/* 	} */
/*       } */
/*       putc(')', stdout); */
/*     } */
/*   } */
/* } */

/**** Main function ****/
extern term entrypoint;
extern symbol main_symbol;

int main(int argc, char* argv[]) {
  return !execute(entrypoint, main_symbol);
}
test.S:	.balign 8
	.data
	.global _symbol_table
_symbol_table: .quad _table
_table:
	.quad 2, _str1
	.quad 2, _str3
	.quad 2, _str5
	.quad 0, _str7
	.quad 0, _str9
	.quad 1, _str11
	.quad 0, _str13
	.quad 0, _str15
	.quad 0, _str17
	.quad 0, _str19
	.quad 0, _str21
	.quad 2, _str23
	.quad 2, _str25
	.quad 0, _str27
	.quad 1, _str29
	.quad 0, _str31
	.quad 1, _str33
	.quad 2, _str35
	.quad 2, _str37
	.quad 1, _str39
	.quad 2, _str41
	.quad 1, _str43
	.quad 0, _str45
	.quad 0, _str47
	.quad 2, _str49
	.quad 1, _str51
	.quad 1, _str53
	.quad 2, _str55
_str1: .asciz ":-"
	.balign 8
_str3: .asciz ","
	.balign 8
_str5: .asciz "."
	.balign 8
_str7: .asciz "[]"
	.balign 8
_str9: .asciz "main"
	.balign 8
_str11: .asciz "push"
	.balign 8
_str13: .asciz "delineate"
	.balign 8
_str15: .asciz "record"
	.balign 8
_str17: .asciz "undo"
	.balign 8
_str19: .asciz "backtrack"
	.balign 8
_str21: .asciz "branch"
	.balign 8
_str23: .asciz "call"
	.balign 8
_str25: .asciz "jump"
	.balign 8
_str27: .asciz "ret"
	.balign 8
_str29: .asciz "match_call"
	.balign 8
_str31: .asciz "b"
	.balign 8
_str33: .asciz "ha"
	.balign 8
_str35: .asciz "+"
	.balign 8
_str37: .asciz "*"
	.balign 8
_str39: .asciz "hello"
	.balign 8
_str41: .asciz "="
	.balign 8
_str43: .asciz "fact"
	.balign 8
_str45: .asciz "c"
	.balign 8
_str47: .asciz "a"
	.balign 8
_str49: .asciz "member"
	.balign 8
_str51: .asciz "test"
	.balign 8
_str53: .asciz ":-"
	.balign 8
_str55: .asciz "|"
	.balign 8
_vt0: .quad 0
_vt2: .quad 2
_t7:
	.quad 31
_t6:
	.quad 33
	.quad _t7
_t4:
	.quad 35
	.quad _vt2
	.quad _t6
_t2:
	.quad 37
	.quad _vt0
	.quad _t4
_t1:
	.quad 35
	.quad _t2
	.quad _t7
_t0:
	.quad 39
	.quad _t1
_h0: .quad -9223372036854710271, _t0
_vt4: .quad 4
_t12:
	.quad 35
	.quad _vt2
	.quad _vt4
_t11:
	.quad 37
	.quad _vt0
	.quad _t12
_vt6: .quad 6
_t10:
	.quad 35
	.quad _t11
	.quad _vt6
_vt8: .quad 8
_t9:
	.quad 41
	.quad _t10
	.quad _vt8
_t8:
	.quad 43
	.quad _t9
_h1: .quad -9223372036854710268, _t8
_t18:
	.quad 47
_t20:
	.quad 45
_t19:
	.quad 5
	.quad _t7
	.quad _t20
_t17:
	.quad 5
	.quad _t18
	.quad _t19
_t16:
	.quad 33
	.quad _t17
_h2: .quad -9223372036854710272, _t16
_t22:
	.quad 5
	.quad _vt0
	.quad _vt2
_t21:
	.quad 49
	.quad _vt0
	.quad _t22
_h3: .quad -9223372036854710271, _t21
_t24:
	.quad 5
	.quad _vt4
	.quad _vt2
_t23:
	.quad 49
	.quad _vt0
	.quad _t24
_t25:
	.quad 49
	.quad _vt0
	.quad _vt2
_h4: .quad -9223372036854710270, _t23
_t26:
	.quad 41
	.quad _vt0
	.quad _vt0
_h5: .quad -9223372036854710272, _t26
_t27:
	.quad 33
	.quad _t18
_h6: .quad -9223372036854710272, _t27
_h7: .quad -9223372036854710272, _t6
_t31:
	.quad 33
	.quad _vt0
_t32:
	.quad 41
	.quad _vt0
	.quad _t18
_t30:
	.quad 3
	.quad _t31
	.quad _t32
_t29:
	.quad 51
	.quad _t30
_t28:
	.quad 53
	.quad _t29
_h8: .quad -9223372036854710272, _t28
_t36:
	.quad 41
	.quad _vt0
	.quad _t7
_t35:
	.quad 3
	.quad _t31
	.quad _t36
_t34:
	.quad 51
	.quad _t35
_t33:
	.quad 53
	.quad _t34
_h9: .quad -9223372036854710272, _t33
_t40:
	.quad 55
	.quad _t18
	.quad _t7
_t42:
	.quad 55
	.quad _vt0
	.quad _vt0
_t44:
	.quad 55
	.quad _vt2
	.quad _vt2
_t46:
	.quad 55
	.quad _vt0
	.quad _vt2
_t47:
	.quad 7
_t45:
	.quad 5
	.quad _t46
	.quad _t47
_t43:
	.quad 5
	.quad _t44
	.quad _t45
_t41:
	.quad 5
	.quad _t42
	.quad _t43
_t39:
	.quad 49
	.quad _t40
	.quad _t41
_t38:
	.quad 51
	.quad _t39
_t37:
	.quad 53
	.quad _t38
_h10: .quad -9223372036854710271, _t37
_t48:
	.quad 9
_t49:
	.quad 41
	.quad _vt2
	.quad _t7
_h11: .quad -9223372036854710271, _t48
	.macro .push
	.quad 11
	.endm
	.macro .delineate
	.quad 13
	.endm
	.macro .record
	.quad 15
	.endm
	.macro .undo
	.quad 17
	.endm
	.macro .backtrack
	.quad 19
	.endm
	.macro .branch l
	.quad 21, \l
	.endm
	.macro .call c, a
	.quad 23, \c, \a
	.endm
	.macro .jump c, a
	.quad 25, \c, \a
	.endm
	.macro .ret
	.quad 27
	.endm
	.macro .match_call m
	.quad 29, \m
	.endm
_c43:
_c43_0:
	.delineate
	.match_call _h1
	.undo
	.backtrack
	.delineate
	.ret
_c33:
_c33_0:
	.delineate
	.match_call _h2
	.undo
	.branch _c33_1
	.delineate
	.ret
_c33_1:
	.delineate
	.match_call _h6
	.undo
	.branch _c33_2
	.delineate
	.ret
_c33_2:
	.delineate
	.match_call _h7
	.undo
	.backtrack
	.delineate
	.ret
_c39:
_c39_0:
	.delineate
	.match_call _h0
	.undo
	.backtrack
	.delineate
	.ret
_c9:
_c9_0:
	.delineate
	.match_call _h11
	.record
	.undo
	.backtrack
	.call _t39, _c49
	.jump _t49, _c41
_c49:
_c49_0:
	.delineate
	.match_call _h3
	.undo
	.branch _c49_1
	.delineate
	.ret
_c49_1:
	.delineate
	.match_call _h4
	.record
	.undo
	.backtrack
	.jump _t25, _c49
_c53:
_c53_0:
	.delineate
	.match_call _h8
	.undo
	.branch _c53_1
	.delineate
	.ret
_c53_1:
	.delineate
	.match_call _h9
	.undo
	.branch _c53_2
	.delineate
	.ret
_c53_2:
	.delineate
	.match_call _h10
	.undo
	.backtrack
	.delineate
	.ret
_c41:
_c41_0:
	.delineate
	.match_call _h5
	.undo
	.backtrack
	.delineate
	.ret
	.global _entrypoint
_entrypoint: .quad _c9
	.global _main_symbol
_main_symbol: .quad 9
test.pl:hello(A*(B + ha(b)) + b).
fact(A * (X+Y)+W=Z).
ha([a, b|c]).
member(X, [X|Y]).
member(X, [W|Z]) :- member(X, Z).
X = X.
ha(a).
ha(b).
:-(test((ha(Z), Z = a))).
:-(test((ha(Z), Z = b))).
:-(test(member((a|b), [(X|X), (Y|Y), (X|Y)]))).
main :- (member((a|b), [(X|X), (Y|Y), (X|Y)]), Y = b).