From f27a7a7fa1f7ab94468c59d85e97e094d908f02d Mon Sep 17 00:00:00 2001 From: De Rais Date: Tue, 21 Jan 2014 14:47:27 -0500 Subject: [PATCH] Initial commit --- COPYING | 13 ++ Makefile | 22 +++ README | 20 +++ examples/truth1.ndq | 10 ++ examples/truth2.ndq | 10 ++ ndeql.c | 454 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 529 insertions(+) create mode 100644 COPYING create mode 100644 Makefile create mode 100644 README create mode 100644 examples/truth1.ndq create mode 100644 examples/truth2.ndq create mode 100644 ndeql.c diff --git a/COPYING b/COPYING new file mode 100644 index 0000000..4a87280 --- /dev/null +++ b/COPYING @@ -0,0 +1,13 @@ + DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE + Version 2, December 2004 + + Copyright (C) 2004 Sam Hocevar + + Everyone is permitted to copy and distribute verbatim or modified + copies of this license document, and changing it is allowed as long + as the name is changed. + + DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. You just DO WHAT THE FUCK YOU WANT TO. \ No newline at end of file diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..7234224 --- /dev/null +++ b/Makefile @@ -0,0 +1,22 @@ +CC=gcc +LD=gcc +CFLAGS=-g -Wall -Werror -pedantic -ansi -O2 +#CFLAGS=-g -Wall -Werror -pedantic -ansi -O2 -DLESS_PROBLEMATIC +LDFLAGS= + +PROG=ndeql + +default:all + +clean: + find -name '*.o' -delete + find -name '*~' -delete + rm -f $(PROG) + +all: $(PROG) + +ndeql: ndeql.o + $(LD) $(LDFLAGS) -o $@ $^ + +%.o : %.c + $(CC) $(CFLAGS) -o $@ -c $< diff --git a/README b/README new file mode 100644 index 0000000..5d5f128 --- /dev/null +++ b/README @@ -0,0 +1,20 @@ +This is an interpreter for Ndeql (see http://esolangs.org/wiki/Ndeql +). It has not been extensively tested, but doesn't seem to have any +terrible bugs. + +$ make +$ ./ndeql examples/truth1.ndq + +Of note to those interested in proving computational class, defining +LESS_PROBLEMATIC while compiling will cause the interpreter to follow +Koen's suggestion + +> Another, less problematic version of the BEGIN instruction could be +> "If no variable is nonzero, skip to the matching END." + +The two variations of truth in the examples directory illustrate this: +truth1.ndq will probably work with the standard interpreter, but +there's always a chance it won't. truth2.ndq will probably not work +with the standard interprete, but there's always a chance it +will. Both files, however, will always work with a less problematic +interpreter. \ No newline at end of file diff --git a/examples/truth1.ndq b/examples/truth1.ndq new file mode 100644 index 0000000..4132fb0 --- /dev/null +++ b/examples/truth1.ndq @@ -0,0 +1,10 @@ +_________ ; This should set all three initial variables to nonzero, yet + ; to values such that the output is invisible when output + +& ; Since the queue is empty, this fills it with whatever the + ; user's input is. + +\*/ ; Every iteration of this loop, there is about a 1|3 chance + ; the selected variable is the one which had the queue's byte + ; stored into it last loop. The remaining 2|3rds of the time, + ; a probably non-printable character is output instead diff --git a/examples/truth2.ndq b/examples/truth2.ndq new file mode 100644 index 0000000..f34d8e7 --- /dev/null +++ b/examples/truth2.ndq @@ -0,0 +1,10 @@ +????????? ; With the LESS_PROBLEMATIC version, this ensures BEGIN will +????????_ ; never skip to beyond END + +& ; Since the queue is empty, this fills it with whatever the + ; user's input is. + +\*/ ; Every iteration of this loop, there is about a 1|3 chance + ; the selected variable is the one which had the queue's byte + ; stored into it last loop. The remaining 2|3rds of the time, + ; a probably non-printable character is output instead diff --git a/ndeql.c b/ndeql.c new file mode 100644 index 0000000..82b09ac --- /dev/null +++ b/ndeql.c @@ -0,0 +1,454 @@ +#include +#include +#include +#include +#include + +#define RD_BLOCK_SZ 4096 + +#define RAND '?' +#define NEXT '=' +#define DEC '-' +#define INC '_' +#define BEGIN '\\' +#define END '/' +#define GROW '!' +#define INPUT '&' +#define OUTPUT '*' + +#define MAKE_ARRAY(arr, arr_sz_var) { \ + arr = malloc(arr_sz_var * sizeof *arr); \ + if (!arr) \ + return errno; \ + } + +#define GROW_ARRAY(arr, arr_sz) { \ + arr_sz *= 2; \ + arr = realloc(arr, arr_sz * sizeof *arr); \ + if (!arr) \ + return errno; \ + } + +char *vars; +size_t vars_num; +size_t vars_storage_sz; + +/* + * queue is implemented as a circularized array with continuously + * advancing head/tail pointers. queue_head shall point to the first + * position at which a `real' value is stored, queue_tail shall point + * to the first position past queue_head at which a `real' value is + * not stored + */ +char *queue; +char *queue_head; +char *queue_tail; +size_t queue_storage_sz; +size_t queue_elem_num; + +/* + * the program source is slurped entirely into this array so that + * BEGIN/END jumping may work correctly, though perhaps in the future + * an option may be added to do this through fseek() calls instead + */ +char *prog; +size_t prog_storage_sz; +size_t prog_len; + +/* + * begin and end points are stored, interleaved, in an array (A[2k] a + * begin, A[2k+1] its matching end) for faster lookup than a linear + * search (about half of the time). jump_pair_num * 2 > + * jump_storage_sz is the condition that must be avoided + * + * TODO: it now seems clear that this should be reversed, so that the + * ends are in monotonic order, with the begins unordered + */ +const char **jumps; +size_t jump_storage_sz; +size_t jump_pair_num; + +/* program handling */ +int read_in(FILE * input) +{ + int read_bytes; + char *c_prog; + + prog_storage_sz = RD_BLOCK_SZ; + MAKE_ARRAY(prog, prog_storage_sz); + c_prog = prog; + + while ((read_bytes = + fread(c_prog, sizeof *prog, RD_BLOCK_SZ, input)) == RD_BLOCK_SZ) { + prog_storage_sz += RD_BLOCK_SZ; + prog_len = prog_storage_sz; + prog = realloc(prog, prog_storage_sz * sizeof *prog); + if (!prog) + return errno; + c_prog = prog + (prog_storage_sz - RD_BLOCK_SZ); + } + + prog_len += read_bytes; + *(prog + prog_len) = '\0'; + + return 0; +} + +int build_jump_list(void) +{ + const char *pc = prog; + + /* + * a stack for where the next end gets stored, so + * ends_storage_stack[ends_num - 1 - 2] is a pointer to within + * jumps that should be filled by a pointer to within prog that + * matches a begin that is two matching levels away from the current + * context + */ + const char ***ends_storage_stack; + size_t ends_num = 0; + size_t ends_storage_sz = 4; + + int lineno = 0; + int charpos = 0; + + MAKE_ARRAY(ends_storage_stack, ends_storage_sz); + + jump_pair_num = 0; + jump_storage_sz = 8; + MAKE_ARRAY(jumps, jump_storage_sz); + + while (*pc != '\0') { + if (*pc == BEGIN) { + if (ends_num + 1 >= ends_storage_sz) { + GROW_ARRAY(ends_storage_stack, ends_storage_sz); + } + + if (2 * (jump_pair_num + 1) >= jump_storage_sz) { + GROW_ARRAY(jumps, jump_storage_sz); + } + + /* + * store this point as a begin, and record the spot at which to + * fill in the matching end + */ + *(ends_storage_stack + ends_num) = jumps + (2 * jump_pair_num) + 1; + *(jumps + 2 * jump_pair_num) = pc; + ends_num++; + jump_pair_num++; + } else if (*pc == END) { + if (ends_num <= 0) { + fprintf(stderr, "Unmatched %c at line %d, char %d\n", END, lineno, + charpos); + return -1; + } + + if (2 * (jump_pair_num + 1) >= jump_storage_sz) { + GROW_ARRAY(jumps, jump_storage_sz); + } + + /* + * store this point as an end in the correct point in the jump + * list, which was precomputed when the begin was seen + */ + **(ends_storage_stack + ends_num - 1) = pc; + ends_num--; + } else if (*pc == '\n') { + lineno++; + charpos = 0; + } else { + charpos++; + } + pc++; + } + + if (ends_num != 0) { + fprintf(stderr, "%lu unmatched %c detected", (unsigned long)ends_num, + BEGIN); + return -1; + } + + return 0; +} + +const char *matching_end_for(const char *begin) +{ + size_t cur_jump; + size_t search_incr; + int diff; + + /* + * quick checks that allow range to be a little sloppy + */ + if (jumps[(2 * 0) + 0] == begin) + return jumps[(2 * 0) + 1]; + if (jumps[(2 * jump_pair_num) + 0] == begin) + return jumps[(2 * jump_pair_num) + 1]; + + /* + * binary search, since it is known that begins are laid out in + * increasing order in jump list + */ + cur_jump = jump_pair_num / 2; + search_incr = jump_pair_num / 4; + + while (search_incr >= 0) { + diff = (int)(jumps[(2 * cur_jump) + 0] - begin); + if (search_incr == 0 || diff == 0) + return jumps[(2 * cur_jump) + 1]; + else if (diff < 0) + cur_jump += search_incr; + else + cur_jump -= search_incr; + + search_incr /= 2; + } + + return NULL; +} + +const char *matching_begin_for(const char *end) +{ + size_t cur_jump = 0; + + /* + * ends are completely unordered, so nothing for it but linear + */ + while (cur_jump < jump_pair_num) { + if (jumps[(2 * cur_jump) + 1] == end) + break; + cur_jump++; + } + return jumps[(2 * cur_jump) + 0]; + +} + +/* queue handling */ +int enqueue(const char c) +{ + queue_elem_num++; + + /* + * store value and advance tail pointer, wrapping if needed + */ + *queue_tail = c; + if (queue_tail - queue + 1 == queue_storage_sz) + queue_tail = queue; + else + queue_tail++; + + /* + * resize the buffer if needed + */ + if (queue_elem_num == queue_storage_sz) { + + queue_storage_sz *= 2; + + if (queue_head == queue) { + /* + * in the easy case, re-use existing memory + */ + queue = realloc(queue, queue_storage_sz * sizeof *queue); + if (!queue) + return errno; + queue_head = queue; + queue_tail = queue + queue_elem_num; + } else { + /* + * in the non-trivial case, neatly re-arrange everything to a + * new buffer. + */ + char *new_queue; + + MAKE_ARRAY(new_queue, queue_storage_sz); + + memcpy(new_queue, queue_head, queue_elem_num - (queue_head - queue)); + memcpy(new_queue, queue, queue_head - queue); + queue_head = queue = new_queue; + queue_tail = queue_head + queue_elem_num; + } + } + + return 0; +} + +char dequeue(void) +{ + char to_ret = *queue_head; + + queue_elem_num--; + + if (queue_head - queue + 1 == queue_storage_sz) + queue_head = queue; + else + queue_head++; + + return to_ret; +} + +/* var handling */ +char *sel_var(void) +{ + return vars + (rand() % vars_num); +} + +/* instruction handling */ +int execute(void) +{ + const char *pc = prog; + char *tvar; + int c; + int ret = 0; + + while (*pc != '\0') { + switch (*pc) { + case RAND: + if (vars_num >= vars_storage_sz) { + GROW_ARRAY(vars, vars_storage_sz); + } + vars_num++; + vars[vars_num - 1] = 0; + break; + case NEXT: + tvar = sel_var(); + if ((ret = enqueue(*tvar)) != 0) + return ret; + *tvar = dequeue(); + break; + case DEC: + tvar = sel_var(); + if (*tvar == -128) + *tvar = 127; + else + (*tvar)--; + break; + case INC: + tvar = sel_var(); + if (*tvar == 127) + *tvar = -128; + else + (*tvar)++; + break; + case BEGIN: + +#ifdef LESS_PROBLEMATIC + c = 0; + { + size_t varidx = 0; + + while (c == 0 && varidx < vars_num) + c = vars[varidx++] != 0; + } + if (c == 0) + pc = matching_end_for(pc); +#else + tvar = sel_var(); + if (*tvar == 0) + pc = matching_end_for(pc); +#endif + + break; + case END: + /* + * this `- 1' may be an error from a faulty reading of the spec + */ + pc = matching_begin_for(pc) - 1; + break; + case GROW: + if ((ret = enqueue(0)) != 0) + return ret; + break; + case INPUT: + c = getchar(); + if (c == EOF) + ret = enqueue(0); + else + ret = enqueue((char)c); + if (ret != 0) + return ret; + break; + case OUTPUT: + tvar = sel_var(); + putchar(*tvar); + if ((ret = enqueue(*tvar)) != 0) + return ret; + *tvar = dequeue(); + break; + } + + pc++; + } + + return 0; +} + +int main(int argc, char **argv) +{ + FILE *input; + + if (argc != 2) { + fprintf(stderr, "Usage: %s INPUT_FILE\n", argv[0]); + return -1; + } + + srand(time(NULL)); + + vars_num = 3; + vars_storage_sz = 16; + if (!(vars = calloc(vars_storage_sz, sizeof *vars))) { + perror("Could not initialize internal state"); + return ENOMEM; + } + + queue_storage_sz = 128; + queue_elem_num = 0; + if (! + (queue_head = queue_tail = queue = + malloc(queue_storage_sz * sizeof *queue))) { + perror("Could not initialize internal state"); + return ENOMEM; + } + + jump_storage_sz = 2; + jump_pair_num = 0; + if (!(jumps = malloc(jump_storage_sz * sizeof *jumps))) { + perror("Could not initialize internal state"); + return ENOMEM; + } + + if (!(input = fopen(argv[1], "r"))) { + perror("Could not open input file"); + return errno; + } + + if (read_in(input) != 0) { + perror("Could not fully read input file"); +#ifdef EFBIG + return EFBIG; +#else + return 1; +#endif + } + + if (build_jump_list() != 0) { + /* + * if errno is set, library error, otherwise syntax error + */ + if (errno != 0) { + perror("Could not initialize jump list"); + return errno; + } +#ifdef EINVAL + return EINVAL; +#else + return 2; +#endif + } + + if (execute() != 0) { + perror("Error during execution"); + return errno; + } + + return 0; +} -- 2.11.4.GIT