%// 
%// This is an example on computing n-th fib number on peano arithmetics
%// 
%{
#include
#include

#define ZERO 0
#define SUC 1
#define PLUS 2
#define FIB 3

struct term {
  int fs;
  int arity;
  struct term **subt;
};

struct term s_zero = {ZERO, 0, NULL};
struct term *zero = &s_zero;

struct term *suc(struct term *x) {
	struct term *res;
	res = malloc(sizeof(struct term));
	res->fs = SUC;
	res->arity = 1;
	res->subt = malloc(sizeof(struct term *));
	res->subt[0] = x;
	return(res);
}


%}

%GET_FUN_SYM<struct term *>(xx) (xx->fs)
%GET_SUBTERM<struct term *>(xx,n) (xx->subt[n])

%sym struct term *zero                                  % ZERO
%sym struct term *suc(struct term *)                    % SUC
%sym struct term *plus(struct term *, struct term *)    % PLUS
%sym struct term *fib(struct term *)                    % FIB

%var struct term *x, *y, *z;

%rule plus(x, zero)     %--> return(x);
%rule plus(x, suc(y))   %--> return(suc(plus(x,y)));

%rule fib(zero)         %--> return(suc(zero));
%rule fib(suc(zero))    %--> return(suc(zero));
%rule fib(suc(suc(x)))  %--> return(plus(fib(x),fib(suc(x))));

%%

void printTerm(struct term *tt) {
	int i;
	static char * fsnames[] = {"zero", "suc", "plus", "fib"};
	printf("%s", fsnames[tt->fs]);
	if (tt->arity!=0) {
		printf("(");
		for(i=0; i<tt->arity; i++) {
			printTerm(tt->subt[i]);
			if (i+1 != tt->arity) printf(",");
		}
		printf(")");
	}
}

static void symbolicFib( int n ) {
  int i;
  struct term  *t;
  t = zero;
  for(i=0; i<n; i++) t = suc(t);
  printf("fib %d == ", n);
  printTerm(fib(t));
  printf("\n");
  fflush(stdout);
}


int main() {
	symbolicFib(2);
	symbolicFib(3);
	symbolicFib(4);
	symbolicFib(5);
	symbolicFib(8);
	symbolicFib(10);
	return(0);
}