/* $Id$ */ /* * Copyright (c) 2007 Dimitri Sokolyuk * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ /* TuringMachine */ #include #include #include #include #include #include #include /* tape, head, table, state register */ struct table { struct tulpe *tulpe; char *initstring; }; struct tulpe { char curst; /* current state */ char ssymb; /* symbol scanned */ char psymb; /* print symbol/erase E/none N */ char move; /* move tape left L/none N/right R */ char newst; /* new state */ struct tulpe *next; }; struct tape { struct cell *lvis; /* fist visible cell (lhs) */ struct cell *head; /* head position */ struct cell *rvis; /* last visible cell (rhs) */ int width; /* width of the visible part of tape */ }; struct cell { char symb; struct cell *left; struct cell *right; }; /* * beaver: A01RB A11LC B01LA B11RB C01LB C11NH */ typedef struct tape Tape; typedef struct cell Cell; typedef struct table Table; typedef struct tulpe Tulpe; char blank = '_'; char haltst = '\0'; char initst = '\0'; int width = 21; long counter = 0; int cells = 0; int state = 0; int dflag = 0; int sflag = 0; int nflag = 0; enum {NOMOVE, TOLEFT, TORIGHT}; char *move[] = { [NOMOVE] = " ", [TOLEFT] = "<<<", [TORIGHT] = ">>>" }; int movetape = NOMOVE; Tape *alloctape(char *); Cell *alloccell(void); Table *alloctable(char *); Tulpe *findtulpe(Table *, Cell *); int movehead(Tape *, char); int execute(Tape *, Table *, int); void printtape(Tape *, Tulpe *, int); void die(int); void usage(void); int nonblank(Tape *); Tape * alloctape(char *init) { Tape *t; Cell *c; char *s; t = malloc(sizeof(Tape)); assert(t); c = alloccell(); t->lvis = t->head = t->rvis = c; t->width = 1; if (init) { s = init; while (*s != '\0' && *s != '\n') { t->head->symb = *(s++); movehead(t, 'R'); } while (s-- != init) movehead(t, 'L'); } else t->head->symb = blank; return t; } Cell * alloccell(void) { Cell *c; c = malloc(sizeof(Cell)); assert(c); c->left = NULL; c->right = NULL; c->symb = blank; ++cells; return c; } Table * alloctable(char *fname) { Table *tab; Tulpe *t, **pt; FILE *fd; char buf[256]; size_t len; t = NULL; pt = &t; tab = malloc(sizeof(Table)); assert(tab); tab->initstring = NULL; fd = fopen(fname, "r"); if (!fd) err(1, "%s", fname); while (fgets(buf, sizeof(buf), fd)) { len = strlen(buf); switch (buf[0]) { case '#': /* commentar */ case '\n': /* empty line */ break; case '!': /* initial string */ tab->initstring = calloc(len + 1, sizeof(char)); assert(tab->initstring); memcpy(tab->initstring, &buf[1], len); break; case '%': initst = buf[1]; blank = buf[2]; haltst = buf[3]; break; default: if (len < 5) break; *pt = malloc(sizeof(Tulpe)); assert(*pt); (*pt)->curst = buf[0]; (*pt)->ssymb = buf[1]; (*pt)->psymb = buf[2]; (*pt)->move = buf[3]; (*pt)->newst = buf[4]; pt = &(*pt)->next; break; } } fclose(fd); tab->tulpe = t; state = initst ? initst : t->curst; return tab; } Tulpe * findtulpe(Table *tab, Cell *cell) { Tulpe *t; for (t = tab->tulpe; t; t = t->next) if (state == t->curst && cell->symb == t->ssymb) return t; return NULL; } int movehead(Tape *tape, char move) { Cell *c; switch (move) { case 'L': case 'l': case '<': /* add a new cell on the lhs */ if (!tape->head->left) { c = alloccell(); tape->head->left = c; c->right = tape->head; } /* shift tape to the right */ if (!nflag && tape->head == tape->lvis) { tape->lvis = tape->lvis->left; if (tape->width < width) ++tape->width; else tape->rvis = tape->rvis->left; movetape = TORIGHT; } /* move the head */ tape->head = tape->head->left; break; case 'R': case 'r': case '>': /* add a new cell on the rhs */ if (!tape->head->right) { c = alloccell(); tape->head->right = c; c->left = tape->head; } /* shift tape to the left */ if (!nflag && tape->head == tape->rvis) { tape->rvis = tape->rvis->right; if (tape->width < width) ++tape->width; else tape->lvis = tape->lvis->right; movetape = TOLEFT; } /* move the head */ tape->head = tape->head->right; break; case 'N': case 'n': case ' ': break; case 'H': case 'h': dflag = 1; break; default: break; } return 0; } int execute(Tape *tape, Table *tab, int u) { Tulpe *t = tab->tulpe; if (!nflag && tab->initstring) printtape(tape, t, 0); while (!dflag && state != haltst) { t = findtulpe(tab, tape->head); /* read & find */ if (!t) { putchar('\n'); errx(1, "cannot find proper tulpe"); } if (!nflag) { printtape(tape, t, sflag); usleep(u); } tape->head->symb = t->psymb; /* write */ if (!nflag) { printtape(tape, t, 0); usleep(u); } movehead(tape, t->move); /* move head */ state = t->newst; /* save new state */ ++counter; } if (!nflag) printtape(tape, t, 1); return 0; } void printtape(Tape *t, Tulpe *tulpe, int nl) { Cell *c; printf("(%c,%c) -> (%c,%c) %c %s", tulpe->curst, tulpe->ssymb, tulpe->newst, tulpe->psymb, tulpe->move, move[movetape]); movetape = NOMOVE; putchar('\t'); for (c = t->lvis; c != t->rvis->right; c = c->right) { putchar(c == t->head ? '(' : ' '); putchar(c->symb); putchar(c == t->head ? ')' : ' '); } putchar(nl ? '\n' : '\r'); fflush(stdout); } int main(int argc, char **argv) { Tape *tape; Table *table; int delay = 100; /* miliseconds */ int c; char *columns; while ((c = getopt(argc, argv, "d:nsb:")) != -1) switch (c) { case 'd': /* execution velocity */ delay = atoi(optarg); if (delay < 0) usage(); break; case 's': /* scroll */ sflag = 1; break; case 'n': /* be quite */ nflag = 1; break; case 'b': blank = *optarg; break; default: usage(); /* NOTREACHED */ } delay *= 1000; /* ms -> us */ columns = getenv("COLUMNS"); if (columns) width = (atoi(columns) - 16) / 3; argc -= optind; argv += optind; if (argc != 1) usage(); signal(SIGHUP, die); signal(SIGINT, die); table = alloctable(*argv); tape = alloctape(table->initstring); execute(tape, table, delay); warnx("halted after %ld moves leaving %d non-empty cells of %d used", counter, nonblank(tape), cells); return 0; } void die(int sig) { dflag = 1; } void usage(void) { extern char *__progname; (void) fprintf(stderr, "usage: %s [-b blank] [-d ms] [-ns] \n", __progname); exit(1); } int nonblank(Tape *t) { int n = 0; Cell *c; /* rewind to the left */ for (c = t->head; c; c = c->left) if (c->symb != blank) ++n; /* rewind to the right */ for (c = t->head->right; c; c = c->right) if (c->symb != blank) ++n; return n; }