lisp/lisp.c

#include "lisp.h"

static Scope global_scope = {0};
static LispFunction special_forms[] = {
    {
        .name = (Nob_String_View){.count = 2, .data = "if"},
        .apply = special_form_if,
    },
    {.name = (Nob_String_View){.count = 6, .data = "define"},
     .apply = special_form_define},
    {.name = (Nob_String_View){.count = 3, .data = "let"},
     .apply = special_form_let},
    {
        .name = (Nob_String_View){.count = 6, .data = "lambda"},
        .apply = special_form_lambda,
    },
    {
        .name = (Nob_String_View){.count = 5, .data = "quote"},
        .apply = special_form_quote,
    }};

static int scope_lookup(Scopes *scopes, Nob_String_View name, Node *result) {
    nob_da_foreach(Scope *, scope, scopes) {
        nob_da_foreach(ScopeObject, scope_object, *scope) {
            if (nob_sv_eq(name, scope_object->name)) {
                *result = scope_object->node;
                return 0;
            }
        }
    }

    printf("Undefined symbol: '" SV_Fmt "'!\n", SV_Arg(name));
    return 1;
}

static void scope_add_function(Scope *scope, const char *name,
                               LispFunctionPtr function) {
    Nob_String_View obj_name = nob_sv_from_cstr(name);
    ScopeObject obj = (ScopeObject){
        .name = obj_name,
        .node = (Node){.kind = NODE_KIND_FUNCTION,
                       .as_function = {.name = obj_name, .apply = function}}};
    nob_da_append(scope, obj);
}

void build_scopes(Scopes *scopes) {
    scope_add_function(&global_scope, "+", builtin_add);
    scope_add_function(&global_scope, "-", builtin_sub);
    scope_add_function(&global_scope, "/", builtin_div);
    scope_add_function(&global_scope, "*", builtin_mul);
    scope_add_function(&global_scope, "=", builtin_eq);
    scope_add_function(&global_scope, "<", builtin_lt);
    scope_add_function(&global_scope, ">", builtin_gt);
    scope_add_function(&global_scope, "<=", builtin_lt_eq);
    scope_add_function(&global_scope, ">=", builtin_gt_eq);
    scope_add_function(&global_scope, "floor", builtin_floor);
    scope_add_function(&global_scope, "ceil", builtin_ceil);

    scope_add_function(&global_scope, "list", builtin_list);
    scope_add_function(&global_scope, "append", builtin_append);
    scope_add_function(&global_scope, "length", builtin_length);
    scope_add_function(&global_scope, "null?", builtin_isnull);
    scope_add_function(&global_scope, "nth", builtin_nth);

    scope_add_function(&global_scope, "println", builtin_println);
    scope_add_function(&global_scope, "builtins", builtin_builtins);

    nob_da_append(scopes, &global_scope);
}

const char *token_kind_name(TokenKind kind) {
    switch (kind) {
    case TOKEN_KIND_PAR_LEFT:
        return "PAR_LEFT";
    case TOKEN_KIND_PAR_RIGHT:
        return "PAR_RIGHT";
    case TOKEN_KIND_NUMBER:
        return "NUMBER";
    case TOKEN_KIND_SYMBOL:
        return "SYMBOL";
    default:
        UNREACHABLE("Unknown token type");
    }
}

void node_print(Node node) {
    switch (node.kind) {
    case NODE_KIND_NUMBER: {
        printf("%f", node.as_number);
    } break;
    case NODE_KIND_SYMBOL: {
        printf(SV_Fmt, SV_Arg(node.as_symbol));
    } break;
    case NODE_KIND_LIST: {
        Nodes *children = node.as_list;
        printf("(");
        for (size_t i = 0; i < children->count; i++) {
            Node node = children->items[i];
            node_print(node);
            if (i != children->count - 1) {
                printf(" ");
            }
        }
        printf(")");
    } break;
    case NODE_KIND_FUNCTION: {
        Nob_String_View func_name = node.as_function.name;
        printf(SV_Fmt, SV_Arg(func_name));
    } break;
    case NODE_KIND_LAMBDA: {
        printf("<lambda>");
    } break;
    default:
        UNREACHABLE("Unknown node type");
    }
}

int tokenize(Nob_String_View content, Tokens *tokens) {
    bool ignored = false;
    for (size_t i = 0; i < content.count; i++) {
        char c = content.data[i];

        if (ignored) {
            if (c == '\n')
                ignored = false;
            continue;
        }

        int kind = -1;
        switch (c) {
        case '/': {
            if (i + 1 < content.count && content.items[i + 1] == '/') {
                i++;
                ignored = true;
                continue;
            }
        } break;
        case '(': {
            kind = TOKEN_KIND_PAR_LEFT;
        } break;
        case ')': {
            kind = TOKEN_KIND_PAR_RIGHT;
        } break;
        }

        if (kind != -1) {
            Token tok = (Token){.kind = kind, .data = {0}};
            nob_da_append(tokens, tok);
            continue;
        }

        Nob_String_Builder sb = {0};
        bool condition = isdigit(c);
        while (condition) {
            nob_sb_appendf(&sb, "%c", c);
            c = content.data[++i];
            condition = isdigit(c) || c == '.';
        }

        if (sb.count > 0) {
            i--;

            Token tok =
                (Token){.kind = TOKEN_KIND_NUMBER, .data = nob_sb_to_sv(sb)};
            nob_da_append(tokens, tok);
            continue;
        }

        // symbols shouldn't start with a digit
        condition = isascii(c) && !isdigit(c) && !isblank(c) && !iscntrl(c) &&
                    c != '(' && c != ')';
        while (condition) {
            nob_sb_appendf(&sb, "%c", c);
            c = content.data[++i];
            condition = isascii(c) && !isblank(c) && !iscntrl(c) && c != '(' &&
                        c != ')';
        }

        if (sb.count > 0) {
            i--;

            Token tok =
                (Token){.kind = TOKEN_KIND_SYMBOL, .data = nob_sb_to_sv(sb)};
            nob_da_append(tokens, tok);
        }
    }
    return 0;
}

int parse_one(Tokens *tokens, Node *node) {
    if (tokens == NULL || node == NULL || tokens->count == 0) {
        printf("unexpected end of input");
        return 1;
    }

    // equivalent to queue.poll
    // TODO: implement a 'da_poll' macro
    Token tok = tokens->items[0];
    tokens->items++;
    tokens->count--;

    switch (tok.kind) {
    case TOKEN_KIND_PAR_LEFT: {
        Nodes *nodes = malloc(sizeof(Nodes));
        if (nodes == NULL) {
            printf("Failed to allocate memory, something is very wrong!\n");
            return 1;
        }
        memset(nodes, 0, sizeof(Nodes));

        while (true) {
            if (tokens->count == 0) {
                printf("expected closing ')'");
                return 1;
            }

            if (tokens->items[0].kind == TOKEN_KIND_PAR_RIGHT) {
                tokens->items++;
                tokens->count--;
                break;
            }

            int ret = parse_one(tokens, node);
            if (ret != 0)
                return ret;

            nob_da_append(nodes, *node);
        }

        node->kind = NODE_KIND_LIST;
        node->as_list = nodes;
    } break;
    case TOKEN_KIND_PAR_RIGHT: {
        printf("unexpected ')'");
        return 1;
    }
    case TOKEN_KIND_NUMBER: {
        double num = strtod(tok.data.data, NULL);
        if (errno != 0) {
            printf("Failed to read number!\n");
            return 1;
        }

        node->kind = NODE_KIND_NUMBER;
        node->as_number = num;
    } break;
    case TOKEN_KIND_SYMBOL: {
        node->kind = NODE_KIND_SYMBOL;
        node->as_symbol = tok.data;
    } break;
    default: {
        // unknown token kind, therefore an error
        // should I use UNREACHABLE instead?
        return 1;
    }
    }
    return 0;
}

int parse(Tokens *tokens, Nodes *nodes) {
    if (tokens == NULL || nodes == NULL)
        return 1;

    struct {
        size_t *items;
        size_t count;
        size_t capacity;
    } stack = {0};

    size_t last_idx = 0;
    for (size_t i = 0; i < tokens->count; i++) {
        TokenKind kind = tokens->items[i].kind;
        if (kind == TOKEN_KIND_PAR_LEFT)
            nob_da_append(&stack, i);
        else if (kind == TOKEN_KIND_PAR_RIGHT)
            last_idx = nob_da_pop(&stack);

        if (stack.count == 0) {
            size_t sub_size = tokens->count - last_idx;
            Tokens toks = {.count = sub_size,
                           .capacity = sub_size,
                           .items = tokens->items + last_idx};

            Node result = {0};
            int ret = parse_one(&toks, &result);
            if (ret != 0) {
                return ret;
            }
            nob_da_append(nodes, result);
        }
    }
    return 0;
}

int eval_one(Node input, Scopes *scopes, Node *result) {
    if (scopes == NULL || result == NULL)
        return 1;

    switch (input.kind) {
    case NODE_KIND_NUMBER:
        *result = input;
        return 0;
    case NODE_KIND_SYMBOL: {
        return scope_lookup(scopes, input.as_symbol, result);
    }
    case NODE_KIND_LIST: {
        Nodes *children = input.as_list;
        if (children->count == 0) {
            *result = input;
            return 0;
        }

        Node head_node = children->items[0];
        if (head_node.kind == NODE_KIND_SYMBOL) {
            for (size_t i = 0; i < NOB_ARRAY_LEN(special_forms); i++) {
                LispFunction special_form = special_forms[i];
                if (nob_sv_eq(head_node.as_symbol, special_form.name)) {
                    Nodes args = {.count = children->count - 1,
                                  .items = children->items + 1};
                    int ret = special_form.apply(args, scopes, result);
                    if (ret != 0)
                        return 1;
                    return 0;
                }
            }
        }

        Node head = {0};
        int ret = eval_one(head_node, scopes, &head);
        if (ret != 0) {
            return ret;
        }

        Nodes args = {0};
        for (size_t i = 1; i < children->count; i++) {
            Node n = {0};
            int ret = eval_one(children->items[i], scopes, &n);
            if (ret != 0) {
                return ret;
            }
            nob_da_append(&args, n);
        }

        switch (head.kind) {
        case NODE_KIND_FUNCTION: {
            head.as_function.apply(args, scopes, result);
            return 0;
        }
        case NODE_KIND_LAMBDA: {
            Nodes *lambda_params = head.as_lambda.params;
            if (lambda_params == NULL) {
                printf("Couldn't evaluate lambda, no params!\n");
                return 1;
            }

            if (lambda_params->count != args.count) {
                printf("Invalid amount of arguments to lambda: expected %zu, "
                       "found %zu\n!",
                       lambda_params->count, args.count);
                return 1;
            }

            Node *lambda_body = head.as_lambda.body;
            if (lambda_body == NULL) {
                printf("Couldn't evaluate lambda, no body!\n");
                return 1;
            }

            Scope scope = {0};
            // params->count == args.count
            for (size_t i = 0; i < lambda_params->count; i++) {
                Node param = lambda_params->items[i];
                // this should already be checked when we emit the lambda node
                NOB_ASSERT(param.kind == NODE_KIND_SYMBOL);
                Node value = args.items[i];

                ScopeObject obj = {.name = param.as_symbol, .node = value};
                nob_da_append(&scope, obj);
            }

            Node expression_value = {0};
            {
                nob_da_append(scopes, &scope);

                int ret = eval_one(*lambda_body, scopes, &expression_value);
                if (ret != 0) {
                    return ret;
                }

                UNUSED(nob_da_pop(scopes));
            }

            *result = expression_value;
            return 0;
        } break;
        default: {
            printf("Not a function-like object: '");
            node_print(head);
            printf("'\n");
            return 1;
        }
        }
    }
    case NODE_KIND_LAMBDA: {
        return 0;
    } break;
    default:
        return 1;
    }
}

int eval(Nodes inputs, Scopes *scopes, Nodes *results) {
    nob_da_foreach(Node, input, &inputs) {
        Node result = {0};
        int ret = eval_one(*input, scopes, &result);
        if (ret != 0) {
            return ret;
        }
        nob_da_append(results, result);
    }
    return 0;
}