/* whileloop.c * * I claim that this is a counterexample to the while loop question. * * What does this program do ? * Why does it always terminate ? (Remember, we are discussing only * terminating programs here, since a * while-loop-free program must terminate.) * Why can't we eliminate while loops ? * * Some of the arrays below have magic numbers for their sizes, but that's * only because I didn't feel like doing dynamic allocation for them. * Assume that they could get arbitrarily big. (After all, for the kind of * question we're considering, we assume as usual that we are running on * an idealized machine with an infinite amount of memory, with some * infinite array Mem[] used to access any memory location, but since I * can't do that on a real machine ... :) * * -- Ted */ #include #include /* just for I/O and memory allocation. irrelevant to while loop issue */ #include /* since the length of a string is assumed known, all functions here _could_ be implemented without while loops */ typedef struct for_list { struct for_list *next; struct for_list *prev; char index[10]; int start; int counter; } for_list; typedef struct if_list { struct if_list *next; struct if_list *prev; int executing; } if_list; typedef struct var { struct var *next; char name[10]; int value; } var; char pr[500][80]; int lines; var *var_list = NULL; var *findvar (char *str) { var *v = var_list; for (v = var_list; v != NULL; v = v->next) if (!strcmp(v->name, str)) return v; return NULL; } void setval(char *str, int val) { var *v, *var_new; v = findvar(str); if (v != NULL) v->value = val; else { var_new = malloc(sizeof(var)); strcpy(var_new->name, str); var_new->value = val; var_new->next = NULL; if (var_list == NULL) var_list = var_new; else { for (v = var_list; v->next != NULL; v = v->next) ; v->next = var_new; } } } int getval(char *str) { var *v; if ((*str >= 'a' && *str <= 'z') || (*str>='A' && *str<='Z')) { v = findvar(str); if (v != NULL) return v->value; return 0; } return atoi(str); /* converts string to number */ } void go() { int done = 0; int pc = 0, j, k, l, to_execute; char *t1, *t2, *t3, *t4, curinst[80]; for_list *for_stack = NULL, *for_new ; if_list *if_stack = NULL, *if_new ; while (1) /* WHILE LOOP WHILE LOOP WHILE LOOP */ { if (pc >= lines) break; strcpy(curinst, pr[pc]); t1 = strtok(curinst, " \n\t\r"); /* read up to whitespace */ if (!strcmp(t1, "end")) break; /* BREAK BREAK BREAK */ if (!strcmp(t1, "for")) { for_new = malloc(sizeof(for_list)); for_new->next = NULL; for_new->prev = for_stack; if (for_stack != NULL) for_stack->next = for_new; if ((if_stack != NULL && !(if_stack->executing)) || (for_stack != NULL && for_stack->counter <= 0)) for_new->counter = 0; else { t1 = strtok(NULL, " \n\t\r"); t2 = strtok(NULL, " \n\t\r"); t3 = strtok(NULL, " \n\t\r"); strcpy(for_new->index, t1); setval(for_new->index, getval(t2)); for_new->counter = getval(t3) - getval(t2) + 1; for_new->start = pc; } for_stack = for_new; } else if (!strcmp(t1, "endfor")) { for_stack->counter--; if (for_stack->counter <= 0) { if (for_stack->prev !=NULL) for_stack->prev->next = NULL; for_new = for_stack; for_stack = for_stack->prev; free(for_new); } else { j = getval(for_stack->index); setval(for_stack->index, j+1); pc = for_stack->start; } } else if (!strcmp(t1, "if")) { to_execute = 0; if ((if_stack == NULL || if_stack->executing) && (for_stack == NULL || for_stack->counter > 0)) { t1 = strtok(NULL, " \n\t\r"); t2 = strtok(NULL, " \n\t\r"); t3 = strtok(NULL, " \n\t\r"); j = getval(t1); k = getval(t3); if (strchr(t2,'<') && j') && j>k) to_execute = 1; } if_new = malloc(sizeof(if_list)); if_new->next = NULL; if_new->prev = if_stack; if_new->executing = to_execute; if (if_stack != NULL) if_stack->next = if_new; if_stack = if_new; } else if (!strcmp(t1, "endif")) { if (if_stack->prev !=NULL) if_stack->prev->next = NULL; if_new = if_stack; if_stack = if_stack->prev; free(if_new); } else if ((if_stack == NULL || if_stack->executing) && (for_stack == NULL || for_stack->counter > 0)) { t2 = strtok(NULL, " \n\t\r"); t2 = strtok(NULL, " \n\t\r"); t3 = strtok(NULL, " \n\t\r"); t4 = strtok(NULL, " \n\t\r"); j = getval(t2); if (t3 == NULL) setval(t1, j); else { k = getval(t4); if (*t3 == '+') l = j + k; if (*t3 == '-') l = j - k; if (*t3 == '*') l = j * k; if (*t3 == '/') l = j / k; setval(t1, l); } } pc++; } printf("%d\n",getval("out")); } int main() { int i; scanf("%d", &lines); gets(pr[0]); for (i=0; i