--- stack/stack.c 2002/02/04 21:47:26 1.28 +++ stack/stack.c 2002/02/07 05:24:19 1.49 @@ -8,6 +8,8 @@ #include /* assert */ #include +/* strcat */ +#include #define HASHTBLSIZE 65536 @@ -18,8 +20,6 @@ enum { integer, string, - ref, /* Reference (to an element in the - hash table) */ func, /* Function pointer */ symb, list @@ -58,6 +58,8 @@ typedef struct { stackitem *head; /* Head of the stack */ hashtbl symbols; /* Hash table of all variable bindings */ + int err; /* Error flag */ + int non_eval_flag; } environment; /* A type for pointers to external functions */ @@ -67,17 +69,65 @@ /* Initialize a newly created environment */ void init_env(environment *env) { - long i; + int i; + env->err= 0; + env->non_eval_flag= 0; for(i= 0; isymbols[i]= NULL; } +void printerr(const char* in_string) { + fprintf(stderr, "Err: %s\n", in_string); +} + +/* Throw away a value */ +void free_val(value *val){ + stackitem *item, *temp; + + val->refcount--; /* Decrease the reference count */ + if(val->refcount == 0){ + switch (val->type){ /* and free the contents if necessary */ + case string: + free(val->content.ptr); + break; + case list: /* lists needs to be freed recursively */ + item=val->content.ptr; + while(item != NULL) { /* for all stack items */ + free_val(item->item); /* free the value */ + temp=item->next; /* save next ptr */ + free(item); /* free the stackitem */ + item=temp; /* go to next stackitem */ + } + free(val); /* Free the actual list value */ + break; + default: + break; + } + } +} + +/* Discard the top element of the stack. */ +extern void toss(environment *env) +{ + stackitem *temp= env->head; + + if((env->head)==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + free_val(env->head->item); /* Free the value */ + env->head= env->head->next; /* Remove the top stack item */ + free(temp); /* Free the old top stack item */ +} + /* Returns a pointer to a pointer to an element in the hash table. */ symbol **hash(hashtbl in_hashtbl, const char *in_string) { - long i= 0; - unsigned long out_hash= 0; + int i= 0; + unsigned int out_hash= 0; char key= '\0'; symbol **position; @@ -103,15 +153,23 @@ } /* Generic push function. */ -int push(stackitem** stack_head, stackitem* in_item) +void push(stackitem** stack_head, stackitem* in_item) { in_item->next= *stack_head; *stack_head= in_item; - return 1; +} + +/* Push a value onto the stack */ +void push_val(stackitem **stack_head, value *val) +{ + stackitem *new_item= malloc(sizeof(stackitem)); + new_item->item= val; + val->refcount++; + push(stack_head, new_item); } /* Push an integer onto the stack. */ -int push_val(stackitem **stack_head, int in_val) +void push_int(stackitem **stack_head, int in_val) { value *new_value= malloc(sizeof(value)); stackitem *new_item= malloc(sizeof(stackitem)); @@ -122,11 +180,10 @@ new_value->refcount=1; push(stack_head, new_item); - return 1; } /* Copy a string onto the stack. */ -int push_cstring(stackitem **stack_head, const char *in_string) +void push_cstring(stackitem **stack_head, const char *in_string) { value *new_value= malloc(sizeof(value)); stackitem *new_item= malloc(sizeof(stackitem)); @@ -138,23 +195,73 @@ new_value->refcount=1; push(stack_head, new_item); - return 1; +} + +/* Mangle a symbol name to a valid C identifier name */ +char *mangle_(const char *old_string){ + char validchars[] + ="0123456789abcdef"; + char *new_string, *current; + + new_string=malloc(strlen(old_string)+4); + strcpy(new_string, "sx_"); /* Stack eXternal */ + current=new_string+3; + while(old_string[0] != '\0'){ + current[0]=validchars[old_string[0]/16]; + current[1]=validchars[old_string[0]%16]; + current+=2; + old_string++; + } + current[0]='\0'; + + return new_string; /* The caller must free() it */ +} + +extern void mangle(environment *env){ + value *new_value; + char *new_string; + + if((env->head)==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + if(env->head->item->type!=string) { + printerr("Bad Argument Type"); + env->err=2; + return; + } + + new_string= mangle_((const char *)(env->head->item->content.ptr)); + + toss(env); + if(env->err) return; + + new_value= malloc(sizeof(value)); + new_value->content.ptr= new_string; + new_value->type= string; + new_value->refcount=1; + + push_val(&(env->head), new_value); } /* Push a symbol onto the stack. */ -int push_sym(environment *env, const char *in_string) +void push_sym(environment *env, const char *in_string) { stackitem *new_item; /* The new stack item */ /* ...which will contain... */ value *new_value; /* A new symbol value */ /* ...which might point to... */ - symbol *new_symbol; /* (if needed) A new actual symbol */ + symbol **new_symbol; /* (if needed) A new actual symbol */ /* ...which, if possible, will be bound to... */ value *new_fvalue; /* (if needed) A new function value */ /* ...which will point to... */ void *funcptr; /* A function pointer */ static void *handle= NULL; /* Dynamic linker handle */ + const char *dlerr; /* Dynamic linker error */ + char *mangled; /* Mangled function name */ /* Create a new stack item containing a new value */ new_item= malloc(sizeof(stackitem)); @@ -166,19 +273,20 @@ new_value->refcount= 1; /* Look up the symbol name in the hash table */ - new_value->content.ptr= *hash(env->symbols, in_string); + new_symbol= hash(env->symbols, in_string); + new_value->content.ptr= *new_symbol; - if(new_value->content.ptr==NULL) { /* If symbol was undefined */ + if(*new_symbol==NULL) { /* If symbol was undefined */ /* Create a new symbol */ - new_symbol= malloc(sizeof(symbol)); - new_symbol->val= NULL; /* undefined value */ - new_symbol->next= NULL; - new_symbol->id= malloc(strlen(in_string)+1); - strcpy(new_symbol->id, in_string); + (*new_symbol)= malloc(sizeof(symbol)); + (*new_symbol)->val= NULL; /* undefined value */ + (*new_symbol)->next= NULL; + (*new_symbol)->id= malloc(strlen(in_string)+1); + strcpy((*new_symbol)->id, in_string); /* Intern the new symbol in the hash table */ - new_value->content.ptr= new_symbol; + new_value->content.ptr= *new_symbol; /* Try to load the symbol name as an external function, to see if we should bind the symbol to a new function pointer value */ @@ -186,61 +294,23 @@ handle= dlopen(NULL, RTLD_LAZY); funcptr= dlsym(handle, in_string); /* Get function pointer */ - if(dlerror()==NULL) { /* If a function was found */ + dlerr=dlerror(); + if(dlerr != NULL) { /* If no function was found */ + mangled=mangle_(in_string); + funcptr= dlsym(handle, mangled); /* try mangling it */ + free(mangled); + dlerr=dlerror(); + } + if(dlerr==NULL) { /* If a function was found */ new_fvalue= malloc(sizeof(value)); /* Create a new value */ new_fvalue->type=func; /* The new value is a function pointer */ new_fvalue->content.ptr=funcptr; /* Store function pointer */ - new_symbol->val= new_fvalue; /* Bind the symbol to the new - function value */ + (*new_symbol)->val= new_fvalue; /* Bind the symbol to the new + function value */ new_fvalue->refcount= 1; } } push(&(env->head), new_item); - return 1; -} - -void printerr(const char* in_string) { - fprintf(stderr, "Err: %s\n", in_string); -} - -/* Throw away a value */ -void free_val(value *val){ - stackitem *item, *temp; - - val->refcount--; /* Decrease the reference count */ - if(val->refcount == 0){ - switch (val->type){ /* and free the contents if necessary */ - case string: - free(val->content.ptr); - case list: /* lists needs to be freed recursively */ - item=val->content.ptr; - while(item != NULL) { /* for all stack items */ - free_val(item->item); /* free the value */ - temp=item->next; /* save next ptr */ - free(item); /* free the stackitem */ - item=temp; /* go to next stackitem */ - } - free(val); /* Free the actual list value */ - break; - default: - break; - } - } -} - -/* Discard the top element of the stack. */ -extern void toss(environment *env) -{ - stackitem *temp= env->head; - - if((env->head)==NULL) { - printerr("Stack empty"); - return; - } - - free_val(env->head->item); /* Free the value */ - env->head= env->head->next; /* Remove the top stack item */ - free(temp); /* Free the old top stack item */ } /* Print newline. */ @@ -249,15 +319,42 @@ printf("\n"); } -/* Prints the top element of the stack. */ -void print_h(stackitem *stack_head) -{ +/* Gets the type of a value */ +extern void type(environment *env){ + int typenum; - if(stack_head==NULL) { - printerr("Stack empty"); + if((env->head)==NULL) { + printerr("Too Few Arguments"); + env->err=1; return; } + typenum=env->head->item->type; + toss(env); + switch(typenum){ + case integer: + push_sym(env, "integer"); + break; + case string: + push_sym(env, "string"); + break; + case symb: + push_sym(env, "symbol"); + break; + case func: + push_sym(env, "function"); + break; + case list: + push_sym(env, "list"); + break; + default: + push_sym(env, "unknown"); + break; + } +} +/* Prints the top element of the stack. */ +void print_h(stackitem *stack_head) +{ switch(stack_head->item->type) { case integer: printf("%d", stack_head->item->content.val); @@ -266,15 +363,34 @@ printf("\"%s\"", (char*)stack_head->item->content.ptr); break; case symb: - printf("'%s'", ((symbol *)(stack_head->item->content.ptr))->id); + printf("%s", ((symbol *)(stack_head->item->content.ptr))->id); + break; + case func: + printf("#", (funcp)(stack_head->item->content.ptr)); + break; + case list: + /* A list is just a stack, so make stack_head point to it */ + stack_head=(stackitem *)(stack_head->item->content.ptr); + printf("[ "); + while(stack_head != NULL) { + print_h(stack_head); + printf(" "); + stack_head=stack_head->next; + } + printf("]"); break; default: - printf("%p", (funcp)(stack_head->item->content.ptr)); + printf("#", (stack_head->item->content.ptr)); break; } } extern void print_(environment *env) { + if(env->head==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } print_h(env->head); } @@ -282,6 +398,7 @@ extern void print(environment *env) { print_(env); + if(env->err) return; toss(env); } @@ -295,17 +412,14 @@ nl(); } - - /* Prints the stack. */ extern void printstack(environment *env) { - if(env->head != NULL) { - print_st(env->head, 1); - nl(); - } else { - printerr("Stack empty"); + if(env->head == NULL) { + return; } + print_st(env->head, 1); + nl(); } /* Swap the two top elements on the stack. */ @@ -313,13 +427,9 @@ { stackitem *temp= env->head; - if((env->head)==NULL) { - printerr("Stack empty"); - return; - } - - if(env->head->next==NULL) { - printerr("Not enough arguments"); + if(env->head==NULL || env->head->next==NULL) { + printerr("Too Few Arguments"); + env->err=1; return; } @@ -328,49 +438,138 @@ env->head->next= temp; } -stackitem* copy(stackitem* in_item) +/* Recall a value from a symbol, if bound */ +extern void rcl(environment *env) { - stackitem *out_item= malloc(sizeof(stackitem)); + value *val; - memcpy(out_item, in_item, sizeof(stackitem)); - out_item->next= NULL; + if(env->head == NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } - return out_item; + if(env->head->item->type!=symb) { + printerr("Bad Argument Type"); + env->err=2; + return; + } + + val=((symbol *)(env->head->item->content.ptr))->val; + if(val == NULL){ + printerr("Unbound Variable"); + env->err=3; + return; + } + toss(env); /* toss the symbol */ + if(env->err) return; + push_val(&(env->head), val); /* Return its bound value */ } +void stack_read(environment*, char*); -/* If the top element is a reference, determine if it's a reference to a - function, and if it is, toss the reference and execute the function. */ +/* If the top element is a symbol, determine if it's bound to a + function value, and if it is, toss the symbol and execute the + function. */ extern void eval(environment *env) { funcp in_func; - stackitem* temp= env->head; + value* temp_val; + stackitem* iterator; + char* temp_string; - if(temp==NULL) { - printerr("Stack empty"); + if(env->head==NULL) { + printerr("Too Few Arguments"); + env->err=1; return; } - if(temp->item->type==symb - && ((symbol *)(temp->item->content.ptr))->val != NULL - && ((symbol *)(temp->item->content.ptr))->val->type == func) { - in_func= (funcp)(((symbol *)(temp->item->content.ptr))->val->content.ptr); - toss(env); + switch(env->head->item->type) { + /* if it's a symbol */ + case symb: + rcl(env); /* get its contents */ + if(env->err) return; + if(env->head->item->type!=symb){ /* don't recurse symbols */ + eval(env); /* evaluate the value */ + return; + } + break; + + /* If it's a lone function value, run it */ + case func: + in_func= (funcp)(env->head->item->content.ptr); + toss(env); + if(env->err) return; (*in_func)(env); + break; + + /* If it's a list */ + case list: + temp_val= env->head->item; + env->head->item->refcount++; + toss(env); + if(env->err) return; + iterator= (stackitem*)temp_val->content.ptr; + while(iterator!=NULL && iterator->item!=NULL) { + push_val(&(env->head), iterator->item); + if(env->head->item->type==symb + && strcmp(";", ((symbol*)(env->head->item->content.ptr))->id)==0) { + toss(env); + if(env->err) return; + eval(env); + if(env->err) return; + } + iterator= iterator->next; + } + free_val(temp_val); + break; + + /* If it's a string */ + case string: + temp_val= env->head->item; + env->head->item->refcount++; + toss(env); + if(env->err) return; + temp_string= malloc(strlen((char*)temp_val->content.ptr)+5); + strcpy(temp_string, "[ "); + strcat(temp_string, (char*)temp_val->content.ptr); + strcat(temp_string, " ]"); + stack_read(env, temp_string); + eval(env); + if(env->err) return; + free_val(temp_val); + free(temp_string); + break; + + default: + } +} + +/* Reverse (flip) a list */ +extern void rev(environment *env){ + stackitem *old_head, *new_head, *item; + + if((env->head)==NULL) { + printerr("Too Few Arguments"); + env->err=1; return; } - - if(temp->item->type==func) { - in_func= (funcp)(temp->item->content.ptr); - toss(env); - (*in_func)(env); + if(env->head->item->type!=list) { + printerr("Bad Argument Type"); + env->err=2; return; } - push(&(env->head), copy(temp)); - swap(env); - toss(env); + old_head=(stackitem *)(env->head->item->content.ptr); + new_head=NULL; + while(old_head != NULL){ + item=old_head; + old_head=old_head->next; + item->next=new_head; + new_head=item; + } + env->head->item->content.ptr=new_head; } /* Make a list. */ @@ -413,21 +612,27 @@ temp->item= pack; push(&(env->head), temp); + rev(env); } /* Parse input. */ -int stack_read(environment *env, char *in_line) +void stack_read(environment *env, char *in_line) { char *temp, *rest; int itemp; size_t inlength= strlen(in_line)+1; int convert= 0; - static int non_eval_flag= 0; temp= malloc(inlength); rest= malloc(inlength); do { + /* If comment */ + if((convert= sscanf(in_line, "#%[^\n\r]", rest))) { + free(temp); free(rest); + return; + } + /* If string */ if((convert= sscanf(in_line, "\"%[^\"\n\r]\" %[^\n\r]", temp, rest))) { push_cstring(&(env->head), temp); @@ -435,7 +640,7 @@ } /* If integer */ if((convert= sscanf(in_line, "%d %[^\n\r]", &itemp, rest))) { - push_val(&(env->head), itemp); + push_int(&(env->head), itemp); break; } /* Escape ';' with '\' */ @@ -445,14 +650,14 @@ break; } /* If symbol */ - if((convert= sscanf(in_line, "%[^][ ;\n\r_]%[^\n\r]", temp, rest))) { + if((convert= sscanf(in_line, "%[^][ ;\n\r]%[^\n\r]", temp, rest))) { push_sym(env, temp); break; } /* If single char */ if((convert= sscanf(in_line, "%c%[^\n\r]", temp, rest))) { if(*temp==';') { - if(!non_eval_flag) { + if(!env->non_eval_flag) { eval(env); /* Evaluate top element */ break; } @@ -464,31 +669,29 @@ if(*temp==']') { push_sym(env, "["); pack(env); - if(non_eval_flag!=0) - non_eval_flag--; + if(env->non_eval_flag) + env->non_eval_flag--; break; } if(*temp=='[') { push_sym(env, "["); - non_eval_flag++; + env->non_eval_flag++; break; } } } while(0); - free(temp); if(convert<2) { free(rest); - return 0; + return; } stack_read(env, rest); free(rest); - return 1; } /* Relocate elements of the list on the stack. */ @@ -497,11 +700,22 @@ stackitem *temp, *new_head; /* Is top element a list? */ - if(env->head==NULL || env->head->item->type!=list) { - printerr("Stack empty or not a list"); + if(env->head==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + if(env->head->item->type!=list) { + printerr("Bad Argument Type"); + env->err=2; return; } + rev(env); + + if(env->err) + return; + /* The first list element is the new stack head */ new_head= temp= env->head->item->content.ptr; @@ -525,7 +739,8 @@ int result; if((env->head)==NULL || env->head->next==NULL) { - printerr("Not enough elements to compare"); + printerr("Too Few Arguments"); + env->err=1; return; } @@ -535,7 +750,7 @@ result= (left==right); toss(env); toss(env); - push_val(&(env->head), result); + push_int(&(env->head), result); } /* Negates the top element on the stack. */ @@ -543,14 +758,21 @@ { int val; - if((env->head)==NULL || env->head->item->type!=integer) { - printerr("Stack empty or element is not a integer"); + if((env->head)==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + if(env->head->item->type!=integer) { + printerr("Bad Argument Type"); + env->err=2; return; } val= env->head->item->content.val; toss(env); - push_val(&(env->head), !val); + push_int(&(env->head), !val); } /* Compares the two top elements on the stack and return 0 if they're the @@ -567,9 +789,15 @@ symbol *sym; /* Needs two values on the stack, the top one must be a symbol */ - if(env->head==NULL || env->head->next==NULL - || env->head->item->type!=symb) { - printerr("Define what?"); + if(env->head==NULL || env->head->next==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + if(env->head->item->type!=symb) { + printerr("Bad Argument Type"); + env->err=2; return; } @@ -600,6 +828,59 @@ toss(env); } +/* List all defined words */ +extern void words(environment *env) +{ + symbol *temp; + int i; + + for(i= 0; isymbols[i]; + while(temp!=NULL) { + printf("%s\n", temp->id); + temp= temp->next; + } + } +} + +/* Forgets a symbol (remove it from the hash table) */ +extern void forget(environment *env) +{ + char* sym_id; + stackitem *stack_head= env->head; + symbol **hash_entry, *temp; + + if(stack_head==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + if(stack_head->item->type!=symb) { + printerr("Bad Argument Type"); + env->err=2; + return; + } + + sym_id= ((symbol*)(stack_head->item->content.ptr))->id; + toss(env); + + hash_entry= hash(env->symbols, sym_id); + temp= *hash_entry; + *hash_entry= (*hash_entry)->next; + + if(temp->val!=NULL) { + free_val(temp->val); + } + free(temp->id); + free(temp); +} + +/* Returns the current error number to the stack */ +extern void errn(environment *env){ + push_int(&(env->head), env->err); +} + int main() { environment myenv; @@ -611,8 +892,58 @@ while(fgets(in_string, 100, stdin) != NULL) { stack_read(&myenv, in_string); + if(myenv.err) { + printf("(error %d) ", myenv.err); + myenv.err=0; + } printf("okidok\n "); } + quit(&myenv); + return EXIT_FAILURE; +} - exit(EXIT_SUCCESS); +/* + */ +extern void sx_2b(environment *env) { + int a, b; + size_t len; + char* new_string; + value *a_val, *b_val; + + if((env->head)==NULL || env->head->next==NULL) { + printerr("Too Few Arguments"); + env->err=1; + return; + } + + if(env->head->item->type==string + && env->head->next->item->type==string) { + a_val= env->head->item; + b_val= env->head->next->item; + a_val->refcount++; + b_val->refcount++; + toss(env); if(env->err) return; + toss(env); if(env->err) return; + len= strlen(a_val->content.ptr)+strlen(b_val->content.ptr)+1; + new_string= malloc(len); + strcpy(new_string, b_val->content.ptr); + strcat(new_string, a_val->content.ptr); + free_val(a_val); free_val(b_val); + push_cstring(&(env->head), new_string); + free(new_string); + return; + } + + if(env->head->item->type!=integer + || env->head->next->item->type!=integer) { + printerr("Bad Argument Type"); + env->err=2; + return; + } + a=env->head->item->content.val; + toss(env); + if(env->err) return; + b=env->head->item->content.val; + toss(env); + if(env->err) return; + push_int(&(env->head), a+b); }