littleLisp.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

void process(char * str); // calls the process fxn and passes str
long interpret(long scope, long first, long last);
#define eps 1e-6

int main() {
	
	// freopen("in.lisp", "r", stdin); //lisp file
	
	FILE *fp;
	char str[80];

	fp = fopen("in.lisp", "r");
	if (fp == NULL) {
		perror("Error opening file");
		return(-1);
	}

	while (fgets(str, 80, fp) != NULL) {
		printf("%s\n", str);
		process(str);
		//break;
	}

	fclose(fp);
	return 0;
}

long count;
char seg[99][99];
long pair[99];
long child[99][99], child_count[99];
enum TYPE{UNKNOWN, LIST, LITERAL, IDENTIFIER} type[99];
long parent[99];

void parse(char * str) {
	long i = 0, j = 0;
	
	//mapping to tokenize function
	char tmp[99];
	while (str[i] != '\0') {
		if (str[i] == '(' || str[i] == ')' || str[i] == '\"') {
			tmp[j++] = ' ';
			tmp[j++] = str[i++];
			tmp[j++] = ' ';
		} else tmp[j++] = str[i++];
	} tmp[j] = 0; 
//	puts(tmp);
	str = tmp;
	count = 1; 
	i = j = 0; 
	while (isspace(str[i]) && str[i] != '\0') i++;
	while (str[i] != '\0') {
		if (str[i] == '\"') {
			j = 0; 
			seg[count][j++] = str[i];
			i+=2;
			while (str[i] != '\0') {
//				puts(str+i);
				seg[count][j++] = str[i++];
				if (str[i]=='\"') break;
			}
			seg[count][j] = 0;
			seg[count][j-1] = '\"';
			
		} else if (isspace(str[i])) {
			if (!isspace(str[i-1])) {
				seg[count][j] = 0;
				count++; j=0;
			} else {
			}
		} else seg[count][j++] = str[i];
		i++;
	}
	if (j) seg[count++][j] = 0;
	count --;
	j = 1;
	while ( j <= count) {
		type[j] = UNKNOWN;
		j++;
	}
}

long local_variable_count[100]; // upto 100 scopes
char local_variable_names[100][100][100]; //# of variable/scope
char local_variable_value[100][100][100]; //1 var val/variable name 

void add_variables(long tar, long src) { // tail cases
//	printf("add_variables %d\n", local_variable_count[src]);
	long i = 0, j;
	while ( i < local_variable_count[src]) {
		j = local_variable_count[tar];
		strcpy(local_variable_names[tar][j], local_variable_names[src][i]);
		strcpy(local_variable_value[tar][j], local_variable_value[src][i]);
		local_variable_count[tar]++;
		i++;
	}
}

char * context_get(long scope, char * s) { // tail for retreiving set var
	if (scope < 0) {
//		puts("Not defined identifier is used!!");
		exit(3);
	}
	long i = 0;
	while ( i < local_variable_count[scope]) {
		if (!strcmp(local_variable_names[scope][i], s)) 
			break;
		i++;
	}
//	printf("%s %s %d %d %d %d\n", s, seg[scope], i, local_variable_count[scope], scope, parent[scope]);
	if ( i < local_variable_count[scope]) 
		return local_variable_value[scope][i];
	return context_get(parent[scope], s);
}

long in_special(long pos) { // helper method
	if (!strcmp(seg[pos], "let")) return 1;
	if (!strcmp(seg[pos+1], "lambda")) return 2;
	if (!strcmp(seg[pos], "if")) return 3;
	if (!strcmp(seg[pos], "define")) return 4;
	return 0;
}

void set_identifier(long scope, char * id, long ref) { 
	printf("set_identifier %s %s in scope %d\n", id, seg[ref], scope);
	long i = local_variable_count[scope];
	strcpy(local_variable_names[scope][i], id);
	strcpy(local_variable_value[scope][i], seg[ref]);
	local_variable_count[scope]++;
}

void set_node(long tar, long src) {
	strcpy(seg[tar], seg[src]);
}

double value_of(char * s) { // tail case converting constant to double
//	printf("value of %s is", s);
	double res = 0, unit;
	long point_count = 0, sign = 1;
	if (*s == '-') sign = -1, s++;
	while (*s) {
		if ((point_count && *s == '.') || 
			(!isdigit(*s) && *s != '.')) break;
		if (point_count) {
			unit /= 10.0;
			res += unit * ((*s)-'0');
		} else if (*s=='.') {
			unit = 1.0;
			point_count++;
		} else {
			res = res * 10;
			res += (*s)-'0';
		}
		s++;
	}
//	printf(" %lf\n", res);
	return res;
}

long is_true(long pos) {
	if (abs(value_of(seg[pos]))<eps) return 0;
	return 1;
}

void special(long scope, long first, long last) {
	if (!strcmp(seg[first], "let")) {
		long i = first + 2, j = first + 2, brace = 0;
		while ( i <= last ) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) {
				interpret(first, j + 2, i - 1);
				set_identifier(scope, seg[j+1], j + 2);
				j = i + 1;
			}
			i++;
			if (brace == -1) break;
		}
		add_variables(scope, first);
		interpret(scope, i, last);
		set_node(scope, i);
		return ;
	}
	if (!strcmp(seg[first], "define")) {
		long i = first + 2, j = first + 2, brace = 0;
		while ( i <= last ) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) {
				interpret(first, j, i);
				j = i + 1;
			}
			i++;
			if (brace == -1) break;
		}
		// if (j+2 > last) {
		// 	j++;
		// } else {
		// 	j = j + 2;
		// }				
		set_identifier(0, seg[first+1], first + 2);
		//add_variables(0, first);
		//interpret(scope, i, last);
		set_node(scope, i);
		return ;
	}
	if (!strcmp(seg[first+1], "lambda")) {
//		puts("OK");
		long i = first, brace = 0;
		while ( i <= last) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) break;
			i++;
		} long p = i - 1;
		long k = first + 3, j = i + 1;
//		printf("%d %d %d %d\n", i, j, k, p);
		i++;
		while ( i <= last) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) {
				interpret(first, j, i);
				set_identifier(first, seg[k], j);
				j = i + 1; k++;
			}
			i++;
		}
		interpret(first, k+1, p);
		set_node(scope, k+1);
		return ;
	}
	if (!strcmp(seg[first], "if")) {
		long i = first + 1, pos[3], brace = 0, pcnt = 0;
		while ( i <= last) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) {
				pos[pcnt++] = i;
			}
		}
		interpret(scope, first + 1, pos[0]);
		if (is_true(first+1)) {
			interpret(scope, pos[0]+1, pos[1]);
			set_node(scope, pos[0]+1);
		} else {
			interpret(scope, pos[1]+1, pos[2]);
			set_node(scope, pos[1]+1);
		}
	}
	return ;
}

long is_function(char * s) { //helper method for calc 
	if (!strcmp(s, "+")) return 1;
	if (!strcmp(s, "*")) return 2;
	if (!strcmp(s, "-")) return 3;
	if (!strcmp(s, "/")) return 4;
	if (!strcmp(s, "sqrt")) return 5;
	return 0;
}

void apply_function(char *s, long scope) {
	if (!strcmp(s, "+")) {
		double res = value_of(seg[child[scope][1]]);
		long i = 2;
		while ( i < child_count[scope] ) {
			res += value_of(seg[child[scope][i]]);
			i++;
		}
		sprintf(seg[scope], "%lf", res);
	}
	if (!strcmp(s, "*")) {
		double res = value_of(seg[child[scope][1]]);
		long i = 2;
		while ( i < child_count[scope] ) {
			res *= value_of(seg[child[scope][i]]);
			i++;
		}
		sprintf(seg[scope], "%lf", res);
	}
	if (!strcmp(s, "-")) {
		double res = value_of(seg[child[scope][1]]);
		long i = 2;
		while ( i < child_count[scope] ) {
			res -= value_of(seg[child[scope][i]]);
			i++;
		}
		sprintf(seg[scope], "%lf", res);
	}
	if (!strcmp(s, "/")) {
		double res = value_of(seg[child[scope][1]]);
		long i = 2;
		while ( i < child_count[scope] ) {
			res /= value_of(seg[child[scope][i]]);
			i++;
		}
		sprintf(seg[scope], "%lf", res);
	}
	if (!strcmp(s, "sqrt")) {
		double res = value_of(seg[child[scope][1]]);
		sprintf(seg[scope], "%lf", sqrt(res));
	}
}

long interpret(long scope, long first, long last);
long interpret_list(long scope, long first, long last) {
	parent[first] = scope;
	printf("interpret_list %d %d %d\n", scope, first, last);
	long i, j, brace;
	if (last>=first && in_special(first)) {
//		puts("OK");
		special(scope, first, last);
	} else {
		child_count[scope] = 0;
		i = j = first; brace = 0;
		while ( i <= last) {
			if (!strcmp(seg[i], "(")) brace++;
			if (!strcmp(seg[i], ")")) brace--;
			if (brace == 0) {
				interpret(scope, j, i);
				child[scope][child_count[scope]++] = j;
				j = i + 1;
			}
			i++;
		}
		if (brace) {
//			puts("Format error!!");
			exit(2);
		}
		if (is_function(seg[first])) {
			apply_function(seg[first], scope);
		} else {
			return scope;
		}
	}
	return 0;
}

long is_identifier(char * s) { //implementation of categorize
	if (is_function(s)) return 0;
	if (isdigit(s[0])) return 0;
	long len = strlen(s);
	if (s[0] == '\"' && s[len-1] == '\"') return 0;
	return 1;
}

long interpret(long scope, long first, long last) {
	parent[first] = scope;
	printf("interpret %d %d %d\n", scope, first, last);
	long i = first, brace = 0; // 333 - 337 tests balance of paren
	while ( i <= last ) {
		if (!strcmp(seg[i], "(")) brace++;
		if (!strcmp(seg[i], ")")) brace--;
		if (brace == 0) break;
//		printf("%d %d %d %d\n", first, last, i, brace);
		i++;
	} //only for close parens not for exissive parens
	if (i < last) {
		puts("Not a valid format!!!");
		exit(1);
	}
	
	if (!strcmp(seg[first], "(")) {  
		local_variable_count[first] = 0;
		return interpret_list(first, first+1, last-1);
	} else if (is_identifier(seg[first])) {
//		printf("context_get result %s\n", context_get(scope, seg[first]));
		strcpy(seg[first], context_get(scope, seg[first]));
		type[first] = LITERAL;
		return first;
	} else {
		return first;
	}
}

void process(char * str) {
	parse(str); // calls parse method and passes str
	long i = 1;
	while (i <= count) {
//		printf("[%d,%s] ", i, seg[i]);
		i++;
	} 
//	puts("");
	interpret(0, 1, count);
	puts(seg[1]);
}