From 859c33f37f0174a7b9d76cdcbe889ff12047c99c Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Sat, 9 Oct 2021 19:00:17 +0200 Subject: Split main into separate files --- src/bootstrap/environment.c | 23 ++ src/bootstrap/lexer.c | 207 ++++++++++++++ src/bootstrap/main.c | 674 +------------------------------------------- src/bootstrap/objects.c | 156 ++++++++++ src/bootstrap/parser.c | 78 +++++ src/bootstrap/primitives.c | 151 ++++++++++ src/bootstrap/readline.c | 28 ++ src/bootstrap/string_view.c | 25 ++ 8 files changed, 675 insertions(+), 667 deletions(-) create mode 100644 src/bootstrap/environment.c create mode 100644 src/bootstrap/lexer.c create mode 100644 src/bootstrap/objects.c create mode 100644 src/bootstrap/parser.c create mode 100644 src/bootstrap/primitives.c create mode 100644 src/bootstrap/readline.c create mode 100644 src/bootstrap/string_view.c (limited to 'src') diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c new file mode 100644 index 0000000..4eda2ad --- /dev/null +++ b/src/bootstrap/environment.c @@ -0,0 +1,23 @@ +// +// Environment. +// + +typedef struct EnvSymbol { + Object *symbol; + Object *value; +} EnvSymbol; + +#define ENV_SIZE 256 +static EnvSymbol environment[ENV_SIZE]; +static size_t env_n = 0; + +Object * +find_environment_symbol(Object *symbol) { + for (size_t i = 0; i < env_n; i++) { + if (symbol_eq(environment[i].symbol, symbol)) { + return environment[i].value; + } + } + return NULL; +} + diff --git a/src/bootstrap/lexer.c b/src/bootstrap/lexer.c new file mode 100644 index 0000000..dd5c0f2 --- /dev/null +++ b/src/bootstrap/lexer.c @@ -0,0 +1,207 @@ +typedef enum TokenType { + TOKEN_UNKNOWN = 0, + TOKEN_LPAREN, + TOKEN_RPAREN, + TOKEN_FIXNUM, + TOKEN_SYMBOL, + TOKEN_BOOL, + TOKEN_STRING, +} TokenType; + +typedef struct Token { + TokenType type; + StringView value; +} Token; + +typedef struct Tokens { + Token *start; + size_t n; +} Tokens; + +#define TRUE_TOKEN (StringView){"true", 4} +#define FALSE_TOKEN (StringView){"false", 5} +#define LPAREN_TOKEN (StringView){"(", 1} +#define RPAREN_TOKEN (StringView){")", 1} + +TokenType +find_token_type(StringView value) { + bool is_fixnum = true; + for (size_t i = 0; i < value.n; i++) { + char c = value.start[i]; + if (i == 0 && c == '-' && value.n > 1) { + continue; + } + if (!isdigit(c)) { + is_fixnum = false; + break; + } + } + if (is_fixnum) { + return TOKEN_FIXNUM; + } + + if (sv_equal(value, TRUE_TOKEN) || sv_equal(value, FALSE_TOKEN)) { + return TOKEN_BOOL; + } + + return TOKEN_SYMBOL; +} + +Tokens +tokenize(StringView sv) { + // NOTE: Not allocating any memory for now, but we are limited by a maximum + // number of tokens we can process. + #define TOKENS_BUF_SIZE 1024 + static Token tokens_buf[TOKENS_BUF_SIZE]; + + // Clear buffer. + for (size_t i = 0; i < TOKENS_BUF_SIZE; i++) { + tokens_buf[i] = (Token){0}; + } + + size_t n = 0; + size_t token_n = 0; + for (size_t i = 0; i < sv.n; i++) { + switch (sv.start[i]) { + case ' ': + case '\f': + case '\n': + case '\r': + case '\t': + case '\v': { + if (token_n != 0) { + Token token = (Token){ + .type = TOKEN_UNKNOWN, + .value = (StringView){ + .start = &sv.start[i - token_n], + .n = token_n, + } + }; + token.type = find_token_type(token.value); + tokens_buf[n++] = token; + token_n = 0; + } + } break; + case ';': { + if (token_n != 0) { + Token token = (Token){ + .type = TOKEN_UNKNOWN, + .value = (StringView){ + .start = &sv.start[i - token_n], + .n = token_n, + } + }; + token.type = find_token_type(token.value); + tokens_buf[n++] = token; + token_n = 0; + } + + // Advance until the next newline. + do { + i++; + } while (i < sv.n && sv.start[(i + 1)] != '\n'); + } break; + case '"': { + if (token_n != 0) { + fprintf(stderr, "error: string started inside symbol\n"); + return (Tokens){0}; + } + + // Find end delimiter. + size_t string_start = i + 1; + size_t string_end = i + 1; + while (true) { + if (sv.start[string_end] == '"' && sv.start[string_end - 1] != '\\') { + break; + } + if (string_end >= sv.n) { + fprintf(stderr, "error: string delimiter not found\n"); + return (Tokens){0}; + } + string_end++; + } + + Token token = (Token){ + .type = TOKEN_STRING, + .value = (StringView){ + .start = &sv.start[string_start], + .n = string_end - string_start, + } + }; + tokens_buf[n++] = token; + token_n = 0; + i += string_end - string_start + 1; + } break; + case '(': { + if ((i + 1) < sv.n) { + char next_c = sv.start[i + 1]; + if (isspace(next_c)) { + fprintf(stderr, "error: lparen delimiter followed by space\n"); + return (Tokens){0}; + } + } + + if (token_n != 0) { + fprintf(stderr, "error: lparen delimiter within symbol name\n"); + return (Tokens){0}; + } + + Token token = (Token){ + .type = TOKEN_LPAREN, + .value = LPAREN_TOKEN, + }; + tokens_buf[n++] = token; + } break; + case ')': { + if ((i + 1) < sv.n) { + char next_c = sv.start[i + 1]; + if ((next_c != ')' && !isspace(next_c))) { + fprintf(stderr, "error: rparen delimiter within symbol name\n"); + return (Tokens){0}; + } + } + + if (token_n != 0) { + // Push previous token. + Token token = (Token){ + .type = TOKEN_UNKNOWN, + .value = (StringView){ + .start = &sv.start[i - token_n], + .n = token_n, + } + }; + token.type = find_token_type(token.value); + tokens_buf[n++] = token; + token_n = 0; + } + + Token token = (Token){ + .type = TOKEN_RPAREN, + .value = RPAREN_TOKEN, + }; + tokens_buf[n++] = token; + } break; + case EOF: { + break; + } break; + default: { + token_n++; + } break; + } + } + if (token_n != 0) { + // End of line encountered. + Token token = (Token){ + .type = TOKEN_UNKNOWN, + .value = (StringView){ + .start = &sv.start[sv.n - token_n], + .n = token_n, + } + }; + token.type = find_token_type(token.value); + tokens_buf[n++] = token; + } + + return (Tokens){.start = (Token *)&tokens_buf, .n = n}; +} + diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c index f5653d6..419ce91 100755 --- a/src/bootstrap/main.c +++ b/src/bootstrap/main.c @@ -5,644 +5,20 @@ #include #include "shorthand.h" - +#include "string_view.c" +#include "readline.c" +#include "lexer.c" +#include "objects.c" +#include "parser.c" +#include "environment.c" +#include "primitives.c" // FIXME: We are not worried right now about freeing memory, but we should in // the future. // TODO: Better error messages. -typedef struct StringView { - char *start; - size_t n; -} StringView; - -void -sv_write(StringView sv) { - for (size_t i = 0; i < sv.n; i++) { - putchar(sv.start[i]); - } -} - -bool -sv_equal(StringView a, StringView b) { - if (a.n == b.n) { - for (size_t i = 0; i < a.n; i++) { - if (a.start[i] != b.start[i]) { - return false; - } - } - return true; - } - return false; -} - -#define READLINE_VALID_CHAR(C) (((u8)(C) >= 0x20 && (u8)(C) < 0x7F) || (C) == '\n') - -StringView -read_line(FILE *fd, char delimiter) { - #define RL_BUF_SIZE 1024 - static char readline_buf[RL_BUF_SIZE]; - - // Clear buffer. - for (size_t i = 0; i < RL_BUF_SIZE; i++) { - readline_buf[i] = 0; - } - - // Barebones readline implementation. - size_t n = 0; - char c; - while ((c = getc(fd)) != delimiter) { - if (c == '\b') { - readline_buf[n] = '\0'; - n--; - } else if (READLINE_VALID_CHAR(c) && n < RL_BUF_SIZE) { - readline_buf[n] = c; - n++; - } - } - - return (StringView){.start = (char *)&readline_buf, .n = n}; -} - -typedef enum TokenType { - TOKEN_UNKNOWN = 0, - TOKEN_LPAREN, - TOKEN_RPAREN, - TOKEN_FIXNUM, - TOKEN_SYMBOL, - TOKEN_BOOL, - TOKEN_STRING, -} TokenType; - -typedef struct Token { - TokenType type; - StringView value; -} Token; - -typedef struct Tokens { - Token *start; - size_t n; -} Tokens; - -#define TRUE_TOKEN (StringView){"true", 4} -#define FALSE_TOKEN (StringView){"false", 5} -#define LPAREN_TOKEN (StringView){"(", 1} -#define RPAREN_TOKEN (StringView){")", 1} - -TokenType -find_token_type(StringView value) { - bool is_fixnum = true; - for (size_t i = 0; i < value.n; i++) { - char c = value.start[i]; - if (i == 0 && c == '-' && value.n > 1) { - continue; - } - if (!isdigit(c)) { - is_fixnum = false; - break; - } - } - if (is_fixnum) { - return TOKEN_FIXNUM; - } - - if (sv_equal(value, TRUE_TOKEN) || sv_equal(value, FALSE_TOKEN)) { - return TOKEN_BOOL; - } - - return TOKEN_SYMBOL; -} - -Tokens -tokenize(StringView sv) { - // NOTE: Not allocating any memory for now, but we are limited by a maximum - // number of tokens we can process. - #define TOKENS_BUF_SIZE 1024 - static Token tokens_buf[TOKENS_BUF_SIZE]; - - // Clear buffer. - for (size_t i = 0; i < TOKENS_BUF_SIZE; i++) { - tokens_buf[i] = (Token){0}; - } - - size_t n = 0; - size_t token_n = 0; - for (size_t i = 0; i < sv.n; i++) { - switch (sv.start[i]) { - case ' ': - case '\f': - case '\n': - case '\r': - case '\t': - case '\v': { - if (token_n != 0) { - Token token = (Token){ - .type = TOKEN_UNKNOWN, - .value = (StringView){ - .start = &sv.start[i - token_n], - .n = token_n, - } - }; - token.type = find_token_type(token.value); - tokens_buf[n++] = token; - token_n = 0; - } - } break; - case ';': { - if (token_n != 0) { - Token token = (Token){ - .type = TOKEN_UNKNOWN, - .value = (StringView){ - .start = &sv.start[i - token_n], - .n = token_n, - } - }; - token.type = find_token_type(token.value); - tokens_buf[n++] = token; - token_n = 0; - } - - // Advance until the next newline. - do { - i++; - } while (i < sv.n && sv.start[(i + 1)] != '\n'); - } break; - case '"': { - if (token_n != 0) { - fprintf(stderr, "error: string started inside symbol\n"); - return (Tokens){0}; - } - - // Find end delimiter. - size_t string_start = i + 1; - size_t string_end = i + 1; - while (true) { - if (sv.start[string_end] == '"' && sv.start[string_end - 1] != '\\') { - break; - } - if (string_end >= sv.n) { - fprintf(stderr, "error: string delimiter not found\n"); - return (Tokens){0}; - } - string_end++; - } - - Token token = (Token){ - .type = TOKEN_STRING, - .value = (StringView){ - .start = &sv.start[string_start], - .n = string_end - string_start, - } - }; - tokens_buf[n++] = token; - token_n = 0; - i += string_end - string_start + 1; - } break; - case '(': { - if ((i + 1) < sv.n) { - char next_c = sv.start[i + 1]; - if (isspace(next_c)) { - fprintf(stderr, "error: lparen delimiter followed by space\n"); - return (Tokens){0}; - } - } - - if (token_n != 0) { - fprintf(stderr, "error: lparen delimiter within symbol name\n"); - return (Tokens){0}; - } - - Token token = (Token){ - .type = TOKEN_LPAREN, - .value = LPAREN_TOKEN, - }; - tokens_buf[n++] = token; - } break; - case ')': { - if ((i + 1) < sv.n) { - char next_c = sv.start[i + 1]; - if ((next_c != ')' && !isspace(next_c))) { - fprintf(stderr, "error: rparen delimiter within symbol name\n"); - return (Tokens){0}; - } - } - - if (token_n != 0) { - // Push previous token. - Token token = (Token){ - .type = TOKEN_UNKNOWN, - .value = (StringView){ - .start = &sv.start[i - token_n], - .n = token_n, - } - }; - token.type = find_token_type(token.value); - tokens_buf[n++] = token; - token_n = 0; - } - - Token token = (Token){ - .type = TOKEN_RPAREN, - .value = RPAREN_TOKEN, - }; - tokens_buf[n++] = token; - } break; - case EOF: { - break; - } break; - default: { - token_n++; - } break; - } - } - if (token_n != 0) { - // End of line encountered. - Token token = (Token){ - .type = TOKEN_UNKNOWN, - .value = (StringView){ - .start = &sv.start[sv.n - token_n], - .n = token_n, - } - }; - token.type = find_token_type(token.value); - tokens_buf[n++] = token; - } - - return (Tokens){.start = (Token *)&tokens_buf, .n = n}; -} - -Token * -consume_token(Tokens *tokens) { - if (tokens->n == 0) { - return NULL; - } - Token *ret = tokens->start; - tokens->start = &tokens->start[1]; - tokens->n--; - return ret; -} - -typedef enum ObjectType { - OBJ_TYPE_FIXNUM, - OBJ_TYPE_BOOL, - OBJ_TYPE_NIL, - OBJ_TYPE_SYMBOL, - OBJ_TYPE_STRING, - OBJ_TYPE_PAIR, - OBJ_TYPE_PROCEDURE, -} ObjectType; - -typedef struct Object { - ObjectType type; - union { - // OBJ_TYPE_FIXNUM - ssize_t fixnum; - - // OBJ_TYPE_BOOL - bool boolean; - - // OBJ_TYPE_STRING - struct { - char *string; - size_t string_n; - }; - - // OBJ_TYPE_PAIR - struct { - struct Object *car; - struct Object *cdr; - }; - - // OBJ_TYPE_SYMBOL - struct { - char *symbol; - size_t symbol_n; - }; - - // OBJ_TYPE_PROCEDURE - struct Object *(*proc)(struct Object *args); - }; -} Object; - -// -// Singletons. -// - -Object *obj_nil; -Object *obj_true; -Object *obj_false; - -// -// Environment. -// - -typedef struct EnvSymbol { - Object *symbol; - Object *value; -} EnvSymbol; - -#define ENV_SIZE 256 -static EnvSymbol environment[ENV_SIZE]; -static size_t env_n = 0; - -Object * -make_fixnum(ssize_t num) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_FIXNUM; - obj->fixnum = num; - return obj; -} - -Object * -make_boolean(bool b) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_BOOL; - obj->boolean = b; - return obj; -} - -Object * -make_empty_string(void) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_STRING; - obj->string = NULL; - obj->string_n = 0; - return obj; -} - -void -append_string(Object *string, StringView sv) { - assert(string != NULL); - assert(string->type == OBJ_TYPE_STRING); - - if (sv.n == 0) { - return; - } - - string->string = realloc(string->string, (string->string_n + sv.n) * sizeof(char)); - memcpy(string->string + string->string_n, sv.start, sv.n); - string->string_n += sv.n; -} - -Object * -make_symbol(const char *str, size_t n) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_SYMBOL; - obj->string = malloc(sizeof(char) * n); - memcpy(obj->string, str, n); - obj->string_n = n; - return obj; -} - -Object * -make_empty_list(void) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_NIL; - return obj; -} - -Object * -make_procedure(Object *(*proc)(struct Object *args)) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_PROCEDURE; - obj->proc = proc; - return obj; -} - -Object * -make_pair(Object *car, Object *cdr) { - Object *obj = malloc(sizeof(Object)); - obj->type = OBJ_TYPE_PAIR; - obj->car = car; - obj->cdr = cdr; - return obj; -} - -Object * -parse(Tokens *tokens) { - while (tokens->n > 0) { - Token *token = consume_token(tokens); - if (token == NULL) { - return NULL; - } - - switch (token->type) { - case TOKEN_FIXNUM: { - ssize_t num = 0; - int sign = 1; - for (size_t i = 0; i < token->value.n; i++) { - char c = token->value.start[i]; - if (c == '-') { - sign = -1; - continue; - } - num = num * 10 + (c - '0'); - } - return make_fixnum(num * sign); - } break; - case TOKEN_BOOL: { - if (sv_equal(token->value, TRUE_TOKEN)) { - return obj_true; - } - if (sv_equal(token->value, FALSE_TOKEN)) { - return obj_false; - } - } break; - case TOKEN_RPAREN: { - return NULL; - } break; - case TOKEN_LPAREN: { - if (tokens->n > 0 && tokens->start[0].type == TOKEN_RPAREN) { - return obj_nil; - } - - Object *next_obj = parse(tokens); - if (next_obj == NULL) { - return NULL; - } - Object *root = make_pair(next_obj, obj_nil); - Object *list = root; - while (tokens->n > 0 && (next_obj = parse(tokens)) != NULL) { - list->cdr = make_pair(next_obj, obj_nil); - list = list->cdr; - } - return root; - } break; - case TOKEN_STRING: { - Object *obj = make_empty_string(); - append_string(obj, token->value); - return obj; - } break; - case TOKEN_SYMBOL: { - return make_symbol(token->value.start, token->value.n); - } break; - default: { - fprintf(stderr, "error: unknown token\n"); - } break; - } - } - - return NULL; -} - -void display(Object *root); - -void -display_pair(Object *root) { - display(root->car); - if (root->cdr->type == OBJ_TYPE_PAIR) { - printf(" "); - display_pair(root->cdr); - } else if (root->cdr->type == OBJ_TYPE_NIL) { - return; - } else { - printf(" . "); - display(root->cdr); - } -} - -void -display(Object *root) { - if (root == NULL) { - return; - } - - switch (root->type) { - case OBJ_TYPE_FIXNUM: { - printf("%zd", root->fixnum); - } break; - case OBJ_TYPE_BOOL: { - if (root->boolean) { - printf("true"); - } else { - printf("false"); - } - } break; - case OBJ_TYPE_NIL: { - printf("()"); - } break; - case OBJ_TYPE_STRING: { - printf("\"%.*s\"", (int)root->string_n, root->string); - } break; - case OBJ_TYPE_SYMBOL: { - printf(":%.*s", (int)root->symbol_n, root->symbol); - } break; - case OBJ_TYPE_PAIR: { - printf("("); - display_pair(root); - printf(")"); - } break; - default: { - printf("TYPE NOT IMPLEMENTED FOR DISPLAY."); - } break; - } -} - #define REPL_PROMPT "bdl> " -Object * eval(Object *root); - -Object * -proc_add(Object *args) { - ssize_t tot = 0; - while (args->type == OBJ_TYPE_PAIR) { - Object *car = eval(args->car); - if (car->type != OBJ_TYPE_FIXNUM) { - fprintf(stderr, "addition not supported for type %d\n", car->type); - return NULL; - } - tot += car->fixnum; - args = args->cdr; - } - return make_fixnum(tot); -} - -Object * -proc_sub(Object *args) { - if (args->type != OBJ_TYPE_PAIR) { - fprintf(stderr, "substraction not supported for type %d\n", args->type); - return NULL; - } - - // Extract first parameter. - Object *car = eval(args->car); - args = args->cdr; - ssize_t tot = car->fixnum; - - while (args->type == OBJ_TYPE_PAIR) { - Object *car = eval(args->car); - if (car->type != OBJ_TYPE_FIXNUM) { - fprintf(stderr, "substraction not supported for type %d\n", car->type); - return NULL; - } - tot -= car->fixnum; - args = args->cdr; - } - return make_fixnum(tot); -} - -Object * -proc_mul(Object *args) { - ssize_t tot = 1; - while (args->type == OBJ_TYPE_PAIR) { - Object *car = eval(args->car); - if (car->type != OBJ_TYPE_FIXNUM) { - fprintf(stderr, "multiply not supported for type %d\n", car->type); - return NULL; - } - tot *= car->fixnum; - args = args->cdr; - } - return make_fixnum(tot); -} - -Object * -proc_div(Object *args) { - if (args->type != OBJ_TYPE_PAIR) { - fprintf(stderr, "substraction not supported for type %d\n", args->type); - return NULL; - } - - // Extract first parameter. - Object *car = eval(args->car); - args = args->cdr; - ssize_t tot = car->fixnum; - - while (args->type == OBJ_TYPE_PAIR) { - Object *car = eval(args->car); - if (car->type != OBJ_TYPE_FIXNUM) { - fprintf(stderr, "div not supported for type %d\n", car->type); - return NULL; - } - tot /= car->fixnum; - args = args->cdr; - } - return make_fixnum(tot); -} - -bool -symbol_eq(Object *a, Object *b) { - if (a->type != b->type || a->type != OBJ_TYPE_SYMBOL || a->symbol_n != b->symbol_n) { - return false; - } - for (size_t i = 0; i < a->symbol_n; i++) { - if (a->symbol[i] != b->symbol[i]) { - return false; - } - } - return true; -} - -Object * -find_environment_symbol(Object *symbol) { - for (size_t i = 0; i < env_n; i++) { - if (symbol_eq(environment[i].symbol, symbol)) { - return environment[i].value; - } - } - return NULL; -} - void init(void) { // Clear env. @@ -662,42 +38,6 @@ init(void) { environment[env_n++] = (EnvSymbol){make_symbol("/", 1), make_procedure(proc_div)}; } -Object * -eval(Object *root) { - if (root == NULL) { - return NULL; - } - - switch (root->type) { - case OBJ_TYPE_FIXNUM: - case OBJ_TYPE_BOOL: - case OBJ_TYPE_NIL: - case OBJ_TYPE_STRING: - case OBJ_TYPE_SYMBOL: { - return root; - } break; - case OBJ_TYPE_PAIR: { - if (root->car->type == OBJ_TYPE_SYMBOL) { - Object *value = find_environment_symbol(root->car); - if (value == NULL) { - printf("error: symbol not found: `"); - display(root->car); - printf("`\n"); - return NULL; - } - if (value->type == OBJ_TYPE_PROCEDURE) { - return value->proc(root->cdr); - } - } - } break; - default: { - printf("error: can't eval type %d.\n", root->type); - } break; - } - - return NULL; -} - void eval_line(FILE *fd, char delimiter) { StringView line = read_line(fd, delimiter); diff --git a/src/bootstrap/objects.c b/src/bootstrap/objects.c new file mode 100644 index 0000000..985709a --- /dev/null +++ b/src/bootstrap/objects.c @@ -0,0 +1,156 @@ +typedef enum ObjectType { + OBJ_TYPE_FIXNUM, + OBJ_TYPE_BOOL, + OBJ_TYPE_NIL, + OBJ_TYPE_SYMBOL, + OBJ_TYPE_STRING, + OBJ_TYPE_PAIR, + OBJ_TYPE_PROCEDURE, +} ObjectType; + +typedef struct Object { + ObjectType type; + union { + // OBJ_TYPE_FIXNUM + ssize_t fixnum; + + // OBJ_TYPE_BOOL + bool boolean; + + // OBJ_TYPE_STRING + struct { + char *string; + size_t string_n; + }; + + // OBJ_TYPE_PAIR + struct { + struct Object *car; + struct Object *cdr; + }; + + // OBJ_TYPE_SYMBOL + struct { + char *symbol; + size_t symbol_n; + }; + + // OBJ_TYPE_PROCEDURE + struct Object *(*proc)(struct Object *args); + }; +} Object; + +// +// Singletons. +// + +Object *obj_nil; +Object *obj_true; +Object *obj_false; + +// +// Constructors. +// + +Object * +make_fixnum(ssize_t num) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_FIXNUM; + obj->fixnum = num; + return obj; +} + +Object * +make_boolean(bool b) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_BOOL; + obj->boolean = b; + return obj; +} + +Object * +make_empty_string(void) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_STRING; + obj->string = NULL; + obj->string_n = 0; + return obj; +} + +void +append_string(Object *string, StringView sv) { + assert(string != NULL); + assert(string->type == OBJ_TYPE_STRING); + + if (sv.n == 0) { + return; + } + + string->string = realloc(string->string, (string->string_n + sv.n) * sizeof(char)); + memcpy(string->string + string->string_n, sv.start, sv.n); + string->string_n += sv.n; +} + +Object * +make_symbol(const char *str, size_t n) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_SYMBOL; + obj->string = malloc(sizeof(char) * n); + memcpy(obj->string, str, n); + obj->string_n = n; + return obj; +} + +Object * +make_empty_list(void) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_NIL; + return obj; +} + +Object * +make_procedure(Object *(*proc)(struct Object *args)) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_PROCEDURE; + obj->proc = proc; + return obj; +} + +Object * +make_pair(Object *car, Object *cdr) { + Object *obj = malloc(sizeof(Object)); + obj->type = OBJ_TYPE_PAIR; + obj->car = car; + obj->cdr = cdr; + return obj; +} + +bool +symbol_eq(Object *a, Object *b) { + if (a->type != b->type || a->type != OBJ_TYPE_SYMBOL || a->symbol_n != b->symbol_n) { + return false; + } + for (size_t i = 0; i < a->symbol_n; i++) { + if (a->symbol[i] != b->symbol[i]) { + return false; + } + } + return true; +} + +void display(Object *root); + +void +display_pair(Object *root) { + display(root->car); + if (root->cdr->type == OBJ_TYPE_PAIR) { + printf(" "); + display_pair(root->cdr); + } else if (root->cdr->type == OBJ_TYPE_NIL) { + return; + } else { + printf(" . "); + display(root->cdr); + } +} + diff --git a/src/bootstrap/parser.c b/src/bootstrap/parser.c new file mode 100644 index 0000000..7a5b516 --- /dev/null +++ b/src/bootstrap/parser.c @@ -0,0 +1,78 @@ +Token * +consume_token(Tokens *tokens) { + if (tokens->n == 0) { + return NULL; + } + Token *ret = tokens->start; + tokens->start = &tokens->start[1]; + tokens->n--; + return ret; +} + +Object * +parse(Tokens *tokens) { + while (tokens->n > 0) { + Token *token = consume_token(tokens); + if (token == NULL) { + return NULL; + } + + switch (token->type) { + case TOKEN_FIXNUM: { + ssize_t num = 0; + int sign = 1; + for (size_t i = 0; i < token->value.n; i++) { + char c = token->value.start[i]; + if (c == '-') { + sign = -1; + continue; + } + num = num * 10 + (c - '0'); + } + return make_fixnum(num * sign); + } break; + case TOKEN_BOOL: { + if (sv_equal(token->value, TRUE_TOKEN)) { + return obj_true; + } + if (sv_equal(token->value, FALSE_TOKEN)) { + return obj_false; + } + } break; + case TOKEN_RPAREN: { + return NULL; + } break; + case TOKEN_LPAREN: { + if (tokens->n > 0 && tokens->start[0].type == TOKEN_RPAREN) { + return obj_nil; + } + + Object *next_obj = parse(tokens); + if (next_obj == NULL) { + return NULL; + } + Object *root = make_pair(next_obj, obj_nil); + Object *list = root; + while (tokens->n > 0 && (next_obj = parse(tokens)) != NULL) { + list->cdr = make_pair(next_obj, obj_nil); + list = list->cdr; + } + return root; + } break; + case TOKEN_STRING: { + Object *obj = make_empty_string(); + append_string(obj, token->value); + return obj; + } break; + case TOKEN_SYMBOL: { + return make_symbol(token->value.start, token->value.n); + } break; + default: { + fprintf(stderr, "error: unknown token\n"); + } break; + } + } + + return NULL; +} + diff --git a/src/bootstrap/primitives.c b/src/bootstrap/primitives.c new file mode 100644 index 0000000..50a2dfb --- /dev/null +++ b/src/bootstrap/primitives.c @@ -0,0 +1,151 @@ +void +display(Object *root) { + if (root == NULL) { + return; + } + + switch (root->type) { + case OBJ_TYPE_FIXNUM: { + printf("%zd", root->fixnum); + } break; + case OBJ_TYPE_BOOL: { + if (root->boolean) { + printf("true"); + } else { + printf("false"); + } + } break; + case OBJ_TYPE_NIL: { + printf("()"); + } break; + case OBJ_TYPE_STRING: { + printf("\"%.*s\"", (int)root->string_n, root->string); + } break; + case OBJ_TYPE_SYMBOL: { + printf(":%.*s", (int)root->symbol_n, root->symbol); + } break; + case OBJ_TYPE_PAIR: { + printf("("); + display_pair(root); + printf(")"); + } break; + default: { + printf("TYPE NOT IMPLEMENTED FOR DISPLAY."); + } break; + } +} + +Object * +eval(Object *root) { + if (root == NULL) { + return NULL; + } + + switch (root->type) { + case OBJ_TYPE_FIXNUM: + case OBJ_TYPE_BOOL: + case OBJ_TYPE_NIL: + case OBJ_TYPE_STRING: + case OBJ_TYPE_SYMBOL: { + return root; + } break; + case OBJ_TYPE_PAIR: { + if (root->car->type == OBJ_TYPE_SYMBOL) { + Object *value = find_environment_symbol(root->car); + if (value == NULL) { + printf("error: symbol not found: `"); + display(root->car); + printf("`\n"); + return NULL; + } + if (value->type == OBJ_TYPE_PROCEDURE) { + return value->proc(root->cdr); + } + } + } break; + default: { + printf("error: can't eval type %d.\n", root->type); + } break; + } + + return NULL; +} + +Object * +proc_add(Object *args) { + ssize_t tot = 0; + while (args->type == OBJ_TYPE_PAIR) { + Object *car = eval(args->car); + if (car->type != OBJ_TYPE_FIXNUM) { + fprintf(stderr, "addition not supported for type %d\n", car->type); + return NULL; + } + tot += car->fixnum; + args = args->cdr; + } + return make_fixnum(tot); +} + +Object * +proc_sub(Object *args) { + if (args->type != OBJ_TYPE_PAIR) { + fprintf(stderr, "substraction not supported for type %d\n", args->type); + return NULL; + } + + // Extract first parameter. + Object *car = eval(args->car); + args = args->cdr; + ssize_t tot = car->fixnum; + + while (args->type == OBJ_TYPE_PAIR) { + Object *car = eval(args->car); + if (car->type != OBJ_TYPE_FIXNUM) { + fprintf(stderr, "substraction not supported for type %d\n", car->type); + return NULL; + } + tot -= car->fixnum; + args = args->cdr; + } + return make_fixnum(tot); +} + +Object * +proc_mul(Object *args) { + ssize_t tot = 1; + while (args->type == OBJ_TYPE_PAIR) { + Object *car = eval(args->car); + if (car->type != OBJ_TYPE_FIXNUM) { + fprintf(stderr, "multiply not supported for type %d\n", car->type); + return NULL; + } + tot *= car->fixnum; + args = args->cdr; + } + return make_fixnum(tot); +} + +Object * +proc_div(Object *args) { + if (args->type != OBJ_TYPE_PAIR) { + fprintf(stderr, "substraction not supported for type %d\n", args->type); + return NULL; + } + + // Extract first parameter. + Object *car = eval(args->car); + args = args->cdr; + ssize_t tot = car->fixnum; + + while (args->type == OBJ_TYPE_PAIR) { + Object *car = eval(args->car); + if (car->type != OBJ_TYPE_FIXNUM) { + fprintf(stderr, "div not supported for type %d\n", car->type); + return NULL; + } + tot /= car->fixnum; + args = args->cdr; + } + return make_fixnum(tot); +} + diff --git a/src/bootstrap/readline.c b/src/bootstrap/readline.c new file mode 100644 index 0000000..dfd8285 --- /dev/null +++ b/src/bootstrap/readline.c @@ -0,0 +1,28 @@ +#define READLINE_VALID_CHAR(C) (((u8)(C) >= 0x20 && (u8)(C) < 0x7F) || (C) == '\n') + +StringView +read_line(FILE *fd, char delimiter) { + #define RL_BUF_SIZE 1024 + static char readline_buf[RL_BUF_SIZE]; + + // Clear buffer. + for (size_t i = 0; i < RL_BUF_SIZE; i++) { + readline_buf[i] = 0; + } + + // Barebones readline implementation. + size_t n = 0; + char c; + while ((c = getc(fd)) != delimiter) { + if (c == '\b') { + readline_buf[n] = '\0'; + n--; + } else if (READLINE_VALID_CHAR(c) && n < RL_BUF_SIZE) { + readline_buf[n] = c; + n++; + } + } + + return (StringView){.start = (char *)&readline_buf, .n = n}; +} + diff --git a/src/bootstrap/string_view.c b/src/bootstrap/string_view.c new file mode 100644 index 0000000..3cf275a --- /dev/null +++ b/src/bootstrap/string_view.c @@ -0,0 +1,25 @@ +typedef struct StringView { + char *start; + size_t n; +} StringView; + +void +sv_write(StringView sv) { + for (size_t i = 0; i < sv.n; i++) { + putchar(sv.start[i]); + } +} + +bool +sv_equal(StringView a, StringView b) { + if (a.n == b.n) { + for (size_t i = 0; i < a.n; i++) { + if (a.start[i] != b.start[i]) { + return false; + } + } + return true; + } + return false; +} + -- cgit v1.2.1