--- stack/stack.c	2002/01/31 23:09:07	1.17
+++ stack/stack.c	2002/02/04 21:47:26	1.28
@@ -6,50 +6,80 @@
 #include <stddef.h>
 /* dlopen, dlsym, dlerror */
 #include <dlfcn.h>
+/* assert */
+#include <assert.h>
 
 #define HASHTBLSIZE 65536
 
-typedef struct stack_item
-{
+/* First, define some types. */
+
+/* A value of some type */
+typedef struct {
   enum {
-    value,			/* Integer */
-    string, 
-    ref,	    /* Reference (to an element in the hash table) */ 
+    integer,
+    string,
+    ref,			/* Reference (to an element in the
+                                   hash table) */
     func,			/* Function pointer */
-    symbol, 
+    symb, 
     list
-  } type;			/* Tells what kind of stack element */
-  
+  } type;			/* Type of stack element */
+
   union {
-    void* ptr;			/* Pointer to the content */
+    void *ptr;			/* Pointer to the content */
     int val;			/* ...or an integer */
   } content;			/* Stores a pointer or an integer */
 
-  char* id;			/* Symbol name */
-  struct stack_item* next;	/* Next element */
-} stackitem;
+  int refcount;			/* Reference counter */
+
+} value;
 
+/* A symbol with a name and possible value */
+/* (These do not need reference counters, they are kept unique by
+   hashing.) */
+typedef struct symbol_struct {
+  char *id;			/* Symbol name */
+  value *val;			/* The value (if any) bound to it */
+  struct symbol_struct *next;	/* In case of hashing conflicts, a */
+} symbol;			/* symbol is a kind of stack item. */
 
-typedef stackitem* hashtbl[HASHTBLSIZE]; /* Hash table declaration */
-typedef void (*funcp)(stackitem**); /* Function pointer declaration */
+/* A type for a hash table for symbols */
+typedef symbol *hashtbl[HASHTBLSIZE]; /* Hash table declaration */
+
+/* An item (value) on a stack */
+typedef struct stackitem_struct
+{
+  value *item;			/* The value on the stack */
+  struct stackitem_struct *next; /* Next item */
+} stackitem;
 
+/* An environment; gives access to the stack and a hash table of
+   defined symbols */
+typedef struct {
+  stackitem *head;		/* Head of the stack */
+  hashtbl symbols;		/* Hash table of all variable bindings */
+} environment;
+
+/* A type for pointers to external functions */
+typedef void (*funcp)(environment *); /* funcp is a pointer to a void
+					 function (environment *) */
 
-/* Initiates a newly created hash table. */
-void init_hashtbl(hashtbl out_hash)
+/* Initialize a newly created environment */
+void init_env(environment *env)
 {
   long i;
 
   for(i= 0; i<HASHTBLSIZE; i++)
-    out_hash[i]= NULL;
+    env->symbols[i]= NULL;
 }
 
-/* Returns a pointer to an element in the hash table. */
-stackitem** hash(hashtbl in_hashtbl, const char* in_string)
+/* 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;
-  char key= 0;
-  stackitem** position;
+  char key= '\0';
+  symbol **position;
   
   while(1){			/* Hash in_string */
     key= in_string[i++];
@@ -61,11 +91,11 @@
   out_hash= out_hash%HASHTBLSIZE;
   position= &(in_hashtbl[out_hash]);
 
-  while(1){			/* Return position if empty */
-    if(*position==NULL)
+  while(1){
+    if(*position==NULL)		/* If empty */
       return position;
     
-    if(strcmp(in_string, (*position)->id)==0) /* Return position if match */
+    if(strcmp(in_string, (*position)->id)==0) /* If match */
       return position;
 
     position= &((*position)->next); /* Try next */
@@ -80,85 +110,92 @@
   return 1;
 }
 
-/* Push a value on the stack. */
-int push_val(stackitem** stack_head, int in_val) 
+/* Push an integer onto the stack. */
+int push_val(stackitem **stack_head, int in_val) 
 {
-  stackitem* new_item= malloc(sizeof(stackitem));
-  new_item->content.val= in_val;
-  new_item->type= value;
+  value *new_value= malloc(sizeof(value));
+  stackitem *new_item= malloc(sizeof(stackitem));
+  new_item->item= new_value;
+  
+  new_value->content.val= in_val;
+  new_value->type= integer;
+  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)
+int push_cstring(stackitem **stack_head, const char *in_string)
 {
-  stackitem* new_item= malloc(sizeof(stackitem));
-  new_item->content.ptr= malloc(strlen(in_string)+1);
-  strcpy(new_item->content.ptr, in_string);
-  new_item->type= string;
+  value *new_value= malloc(sizeof(value));
+  stackitem *new_item= malloc(sizeof(stackitem));
+  new_item->item=new_value;
+
+  new_value->content.ptr= malloc(strlen(in_string)+1);
+  strcpy(new_value->content.ptr, in_string);
+  new_value->type= string;
+  new_value->refcount=1;
 
   push(stack_head, new_item);
   return 1;
 }
 
-/* Create a new hash entry. */
-int mk_hashentry(hashtbl in_hashtbl, stackitem* in_item, const char* id)
-{
-  in_item->id= malloc(strlen(id)+1);
-
-  strcpy(in_item->id, id);
-  push(hash(in_hashtbl, id), in_item);
-
-  return 1;
-}
-
-/* Define a function a new function in the hash table. */
-void def_func(hashtbl in_hashtbl, funcp in_func, const char* id)
+/* Push a symbol onto the stack. */
+int push_sym(environment *env, const char *in_string)
 {
-  stackitem* temp= malloc(sizeof(stackitem));
+  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 */
+  /* ...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 */
+
+  /* Create a new stack item containing a new value */
+  new_item= malloc(sizeof(stackitem));
+  new_value= malloc(sizeof(value));
+  new_item->item=new_value;
+
+  /* The new value is a symbol */
+  new_value->type= symb;
+  new_value->refcount= 1;
+
+  /* Look up the symbol name in the hash table */
+  new_value->content.ptr= *hash(env->symbols, in_string);
+
+  if(new_value->content.ptr==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);
 
-  temp->type= func;
-  temp->content.ptr= in_func;
+    /* Intern the new symbol in the hash table */
+    new_value->content.ptr= new_symbol;
 
-  mk_hashentry(in_hashtbl, temp, id);
-}
-
-/* Define a new symbol in the hash table. */
-void def_sym(hashtbl in_hashtbl, const char* id)
-{
-  stackitem* temp= malloc(sizeof(stackitem));
-  
-  temp->type= symbol;
-  mk_hashentry(in_hashtbl, temp, id);
-}
-
-/* Push a reference to an entry in the hash table onto the stack. */
-int push_ref(stackitem** stack_head, hashtbl in_hash, const char* in_string)
-{
-  static void* handle= NULL;
-  void* symbol;
-
-  stackitem* new_item= malloc(sizeof(stackitem));
-  new_item->content.ptr= *hash(in_hash, in_string);
-  new_item->type= ref;
-
-  if(new_item->content.ptr==NULL) { /* If hash entry empty */
+    /* Try to load the symbol name as an external function, to see if
+       we should bind the symbol to a new function pointer value */
     if(handle==NULL)		/* If no handle */
-      handle= dlopen(NULL, RTLD_LAZY);    
+      handle= dlopen(NULL, RTLD_LAZY);
 
-    symbol= dlsym(handle, in_string); /* Get function pointer */
-    if(dlerror()==NULL) 	/* If existing function pointer */
-      def_func(in_hash, symbol, in_string); /* Store function pointer */
-    else
-      def_sym(in_hash, in_string); /* Make symbol */
-      
-    new_item->content.ptr= *hash(in_hash, in_string); /* XXX */
-    new_item->type= ref;
+    funcptr= dlsym(handle, in_string); /* Get function pointer */
+    if(dlerror()==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_fvalue->refcount= 1;
+    }
   }
-
-  push(stack_head, new_item);
+  push(&(env->head), new_item);
   return 1;
 }
 
@@ -166,21 +203,44 @@
   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(stackitem** stack_head)
+extern void toss(environment *env)
 {
-  stackitem* temp= *stack_head;
+  stackitem *temp= env->head;
 
-  if((*stack_head)==NULL) {
+  if((env->head)==NULL) {
     printerr("Stack empty");
     return;
   }
   
-  if((*stack_head)->type==string)
-    free((*stack_head)->content.ptr);
-
-  *stack_head= (*stack_head)->next;
-  free(temp);
+  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. */
@@ -190,86 +250,179 @@
 }
 
 /* Prints the top element of the stack. */
-void print_(stackitem** stack_head)
+void print_h(stackitem *stack_head)
 {
-  if((*stack_head)==NULL) {
+
+  if(stack_head==NULL) {
     printerr("Stack empty");
     return;
   }
 
-  switch((*stack_head)->type) {
-  case value:
-    printf("%d", (*stack_head)->content.val);
+  switch(stack_head->item->type) {
+  case integer:
+    printf("%d", stack_head->item->content.val);
     break;
   case string:
-    printf("%s", (char*)(*stack_head)->content.ptr);
+    printf("\"%s\"", (char*)stack_head->item->content.ptr);
     break;
-  case ref:
-    printf("%s", ((stackitem*)(*stack_head)->content.ptr)->id);
+  case symb:
+    printf("'%s'", ((symbol *)(stack_head->item->content.ptr))->id);
     break;
-  case symbol:
   default:
-    printf("%p", (*stack_head)->content.ptr);
+    printf("%p", (funcp)(stack_head->item->content.ptr));
     break;
   }
 }
 
+extern void print_(environment *env) {
+  print_h(env->head);
+}
+
 /* Prints the top element of the stack and then discards it. */
-extern void print(stackitem** stack_head)
+extern void print(environment *env)
 {
-  print_(stack_head);
-  toss(stack_head);
+  print_(env);
+  toss(env);
 }
 
 /* Only to be called by function printstack. */
-void print_st(stackitem* stack_head, long counter)
+void print_st(stackitem *stack_head, long counter)
 { 
   if(stack_head->next != NULL)
     print_st(stack_head->next, counter+1);
-
   printf("%ld: ", counter);
-  print_(&stack_head);
+  print_h(stack_head);
   nl();
 }
 
+
+
 /* Prints the stack. */
-extern void printstack(stackitem** stack_head)
+extern void printstack(environment *env)
 {
-  if(*stack_head != NULL) {
-    print_st(*stack_head, 1);
-    printf("\n");
+  if(env->head != NULL) {
+    print_st(env->head, 1);
+    nl();
   } else {
     printerr("Stack empty");
   }
 }
 
+/* Swap the two top elements on the stack. */
+extern void swap(environment *env)
+{
+  stackitem *temp= env->head;
+  
+  if((env->head)==NULL) {
+    printerr("Stack empty");
+    return;
+  }
+
+  if(env->head->next==NULL) {
+    printerr("Not enough arguments");
+    return;
+  }
+
+  env->head= env->head->next;
+  temp->next= env->head->next;
+  env->head->next= temp;
+} 
+
+stackitem* copy(stackitem* in_item)
+{
+  stackitem *out_item= malloc(sizeof(stackitem));
+
+  memcpy(out_item, in_item, sizeof(stackitem));
+  out_item->next= NULL;
+
+  return out_item;
+}
+
+
 /* 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. */
-extern void eval(stackitem** stack_head)
+extern void eval(environment *env)
 {
   funcp in_func;
+  stackitem* temp= env->head;
 
-  if((*stack_head)==NULL || (*stack_head)->type!=ref) {
-    printerr("Stack empty or not a reference");
+  if(temp==NULL) {
+    printerr("Stack empty");
     return;
   }
 
-  if(((stackitem*)(*stack_head)->content.ptr)->type==func) {
-    in_func= (funcp)((stackitem*)(*stack_head)->content.ptr)->content.ptr;
-    toss(stack_head); 
-    (*in_func)(stack_head);
+  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);
+    (*in_func)(env);
     return;
-  } else
-    printerr("Not a function");
+  }
+    
+
+  if(temp->item->type==func) {
+    in_func= (funcp)(temp->item->content.ptr);
+    toss(env); 
+    (*in_func)(env);
+    return;
+  }
+
+  push(&(env->head), copy(temp));
+  swap(env);
+  toss(env);
+}
+
+/* Make a list. */
+extern void pack(environment *env)
+{
+  void* delimiter;
+  stackitem *iterator, *temp;
+  value *pack;
+
+  delimiter= env->head->item->content.ptr; /* Get delimiter */
+  toss(env);
+
+  iterator= env->head;
+
+  if(iterator==NULL || iterator->item->content.ptr==delimiter) {
+    temp= NULL;
+    toss(env);
+  } else {
+    /* Search for first delimiter */
+    while(iterator->next!=NULL
+	  && iterator->next->item->content.ptr!=delimiter)
+      iterator= iterator->next;
+    
+    /* Extract list */
+    temp= env->head;
+    env->head= iterator->next;
+    iterator->next= NULL;
+    
+    if(env->head!=NULL)
+      toss(env);
+  }
+
+  /* Push list */
+  pack= malloc(sizeof(value));
+  pack->type= list;
+  pack->content.ptr= temp;
+  pack->refcount= 1;
+
+  temp= malloc(sizeof(stackitem));
+  temp->item= pack;
+
+  push(&(env->head), temp);
 }
 
 /* Parse input. */
-int stack_read(stackitem** stack_head, hashtbl in_hash, char* in_line) 
+int 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);
@@ -277,29 +430,50 @@
   do {
     /* If string */
     if((convert= sscanf(in_line, "\"%[^\"\n\r]\" %[^\n\r]", temp, rest))) {
-      push_cstring(stack_head, temp);
+      push_cstring(&(env->head), temp);
       break;
     }
-    /* If value */
+    /* If integer */
     if((convert= sscanf(in_line, "%d %[^\n\r]", &itemp, rest))) {
-      push_val(stack_head, itemp);
+      push_val(&(env->head), itemp);
       break;
     }
     /* Escape ';' with '\' */
     if((convert= sscanf(in_line, "\\%c%[^\n\r]", temp, rest))) {
-      temp[1]= '\0'; 
-      push_ref(stack_head, in_hash, temp);
+      temp[1]= '\0';
+      push_sym(env, temp);
       break;
     } 
     /* If symbol */
-    if((convert= sscanf(in_line, "%[^ ;\n\r]%[^\n\r]", temp, rest))) {
-	push_ref(stack_head, in_hash, temp);
+    if((convert= sscanf(in_line, "%[^][ ;\n\r_]%[^\n\r]", temp, rest))) {
+	push_sym(env, temp);
 	break;
     }
-    /* If ';' */
-    if((convert= sscanf(in_line, "%c%[^\n\r]", temp, rest)) && *temp==';') {
-      eval(stack_head);		/* Evaluate top element */
-      break;
+    /* If single char */
+    if((convert= sscanf(in_line, "%c%[^\n\r]", temp, rest))) {
+      if(*temp==';') {
+	if(!non_eval_flag) {
+	  eval(env);		/* Evaluate top element */
+	  break;
+	}
+	
+	push_sym(env, ";");
+	break;
+      }
+
+      if(*temp==']') {
+	push_sym(env, "[");
+	pack(env);
+	if(non_eval_flag!=0)
+	  non_eval_flag--;
+	break;
+      }
+
+      if(*temp=='[') {
+	push_sym(env, "[");
+	non_eval_flag++;
+	break;
+      }
     }
   } while(0);
 
@@ -311,177 +485,134 @@
     return 0;
   }
    
-  stack_read(stack_head, in_hash, rest);
+  stack_read(env, rest);
   
   free(rest);
   return 1;
 }
 
-/* Make a list. */
-extern void pack(stackitem** stack_head)
-{
-  void* delimiter;
-  stackitem *iterator, *temp, *pack;
-
-  if((*stack_head)==NULL) {
-    printerr("Stack empty");
-    return;
-  }
-
-  delimiter= (*stack_head)->content.ptr; /* Get delimiter */
-  toss(stack_head);
-
-  iterator= *stack_head;
-
-  /* Search for first delimiter */
-  while(iterator->next!=NULL && iterator->next->content.ptr!=delimiter)
-    iterator= iterator->next;
-
-  /* Extract list */
-  temp= *stack_head;
-  *stack_head= iterator->next;
-  iterator->next= NULL;
-  
-  if(*stack_head!=NULL && (*stack_head)->content.ptr==delimiter)
-    toss(stack_head);
-
-  /* Push list */
-  pack= malloc(sizeof(stackitem));
-  pack->type= list;
-  pack->content.ptr= temp;
-
-  push(stack_head, pack);
-}
-
 /* Relocate elements of the list on the stack. */
-extern void expand(stackitem** stack_head)
+extern void expand(environment *env)
 {
   stackitem *temp, *new_head;
 
   /* Is top element a list? */
-  if((*stack_head)==NULL || (*stack_head)->type!=list) {
+  if(env->head==NULL || env->head->item->type!=list) {
     printerr("Stack empty or not a list");
     return;
   }
 
   /* The first list element is the new stack head */
-  new_head= temp= (*stack_head)->content.ptr;
-  toss(stack_head);
+  new_head= temp= env->head->item->content.ptr;
+
+  env->head->item->refcount++;
+  toss(env);
 
-  /* Search the end of the list */
+  /* Find the end of the list */
   while(temp->next!=NULL)
     temp= temp->next;
 
-  /* Connect the the tail of the list with the old stack head */
-  temp->next= *stack_head;
-  *stack_head= new_head;	/* ...and voila! */
-}
+  /* Connect the tail of the list with the old stack head */
+  temp->next= env->head;
+  env->head= new_head;		/* ...and voila! */
 
-/* Swap the two top elements on the stack. */
-extern void swap(stackitem** stack_head)
-{
-  stackitem* temp= (*stack_head);
-  
-  if((*stack_head)==NULL) {
-    printerr("Stack empty");
-    return;
-  }
-
-  if((*stack_head)->next==NULL)
-    return;
-
-  *stack_head= (*stack_head)->next;
-  temp->next= (*stack_head)->next;
-  (*stack_head)->next= temp;
-} 
+}
 
 /* Compares two elements by reference. */
-extern void eq(stackitem** stack_head)
+extern void eq(environment *env)
 {
   void *left, *right;
   int result;
 
-  if((*stack_head)==NULL || (*stack_head)->next==NULL) {
+  if((env->head)==NULL || env->head->next==NULL) {
     printerr("Not enough elements to compare");
     return;
   }
 
-  left= (*stack_head)->content.ptr;
-  swap(stack_head);
-  right= (*stack_head)->content.ptr;
+  left= env->head->item->content.ptr;
+  swap(env);
+  right= env->head->item->content.ptr;
   result= (left==right);
   
-  toss(stack_head); toss(stack_head);
-  push_val(stack_head, (left==right));
+  toss(env); toss(env);
+  push_val(&(env->head), result);
 }
 
 /* Negates the top element on the stack. */
-extern void not(stackitem** stack_head)
+extern void not(environment *env)
 {
-  int value;
+  int val;
 
-  if((*stack_head)==NULL || (*stack_head)->type!=value) {
-    printerr("Stack empty or element is not a value");
+  if((env->head)==NULL || env->head->item->type!=integer) {
+    printerr("Stack empty or element is not a integer");
     return;
   }
 
-  value= (*stack_head)->content.val;
-  toss(stack_head);
-  push_val(stack_head, !value);
+  val= env->head->item->content.val;
+  toss(env);
+  push_val(&(env->head), !val);
 }
 
 /* Compares the two top elements on the stack and return 0 if they're the
    same. */
-extern void neq(stackitem** stack_head)
+extern void neq(environment *env)
 {
-  eq(stack_head);
-  not(stack_head);
+  eq(env);
+  not(env);
 }
 
 /* Give a symbol some content. */
-extern void def(stackitem** stack_head)
+extern void def(environment *env)
 {
-  stackitem *temp, *value;
+  symbol *sym;
 
-  if(*stack_head==NULL || (*stack_head)->next==NULL 
-     || (*stack_head)->type!=ref) {
+  /* 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?");
     return;
   }
 
-  temp= (*stack_head)->content.ptr;
-  value= (*stack_head)->next;
-  temp->content= value->content;
-  value->content.ptr=NULL;
-  temp->type= value->type;
+  /* long names are a pain */
+  sym=env->head->item->content.ptr;
 
-  toss(stack_head); toss(stack_head);
+  /* if the symbol was bound to something else, throw it away */
+  if(sym->val != NULL)
+    free_val(sym->val);
+
+  /* Bind the symbol to the value */
+  sym->val= env->head->next->item;
+  sym->val->refcount++;		/* Increase the reference counter */
+
+  toss(env); toss(env);
 } 
 
 /* Quit stack. */
-extern void quit()
+extern void quit(environment *env)
 {
   exit(EXIT_SUCCESS);
 }
 
+/* Clear stack */
+extern void clear(environment *env)
+{
+  while(env->head!=NULL)
+    toss(env);
+}
+
 int main()
 {
-  stackitem* s= NULL;
-  hashtbl myhash;
+  environment myenv;
   char in_string[100];
 
-  init_hashtbl(myhash);
+  init_env(&myenv);
 
   printf("okidok\n ");
 
   while(fgets(in_string, 100, stdin) != NULL) {
-    stack_read(&s, myhash, in_string);
+    stack_read(&myenv, in_string);
     printf("okidok\n ");
   }
 
   exit(EXIT_SUCCESS);
 }
-
-/* Local Variables: */
-/* compile-command:"make CFLAGS=\"-Wall -g -rdynamic -ldl\" stack" */
-/* End: */