Mercurial > lbo > hg > ylisp
changeset 181:3ec2b2edb977
-- last work state before rewrite --
| author | Lewin Bormann <lbo@spheniscida.de> |
|---|---|
| date | Fri, 27 Sep 2019 14:30:38 +0200 |
| parents | 6eb17b273514 |
| children | 8cd4314a144f |
| files | src/built-ins.c src/built-ins_test.c src/eval.c src/eval.h src/eval_test.c src/func.h src/preprocess.c src/preprocess.h src/preprocess_test.c src/sizes_test.c src/types.h src/value.c src/value.h |
| diffstat | 13 files changed, 387 insertions(+), 92 deletions(-) [+] |
line wrap: on
line diff
--- a/src/built-ins.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/built-ins.c Fri Sep 27 14:30:38 2019 +0200 @@ -47,10 +47,11 @@ }; static const char* YBUILTIN_ENUM_STR[] = { - "BUILTIN:UNDEF", "BUILTIN:FOR", "BUILTIN:LET", "BUILTIN:DEFN", - "BUILTIN:+", "BUILTIN:-", "BUILTIN:*", "BUILTIN:/", - "BUILTIN:IF", "BUILTIN:PRINT", "BUILTIN:EQ", "BUILTIN:LT", - "BUILTIN:CAR", "BUILTIN:CDR", "BUILTIN:PUSH", "BUILTIN:RAISE", "BUILTIN:RECOVER", "BUILTIN:_MKCLSR", + "BUILTIN:UNDEF", "BUILTIN:FOR", "BUILTIN:LET", "BUILTIN:DEFN", + "BUILTIN:+", "BUILTIN:-", "BUILTIN:*", "BUILTIN:/", + "BUILTIN:IF", "BUILTIN:PRINT", "BUILTIN:EQ", "BUILTIN:LT", + "BUILTIN:CAR", "BUILTIN:CDR", "BUILTIN:PUSH", "BUILTIN:RAISE", + "BUILTIN:RECOVER", "BUILTIN:_MKCLSR", }; /// Ownership of msg is transferred to this function, ownership of offending is @@ -211,10 +212,35 @@ if (ref->typ != YEXPR_REF) TYPEFAIL(LET, let, _pattern); assert(counter == 2); - yvalue_t newvalue = { - .typ = YVALUE_EXPR, - .value.expr = yeval_list_return_last(state, letlist, counter)}; - yvalue_set(ref->value.ref, &newvalue); + + // Add or update reference in local scope. + + // Check if ref refers to a captured variable. + for (size_t i = 0; i < state->current_closure->captured.len; i++) { + ycaptured_t* candidate = YVEC_AT(&state->current_closure->captured, i, ycaptured_t); + if (yref_eq(&ref->value.ref, &candidate->ref)) { + yexpr_destroy(&candidate->expr); + candidate->expr = yeval_list_return_last(state, letlist, counter); + return yexpr_new(); + } + } + + // Else, find local slot created by previous `let`. + for (size_t i = state->locals.len-1; i > 0; i--) { + yeval_local_def_t* candidate = YVEC_AT(&state->locals, i, yeval_local_def_t); + if (yref_eq(&ref->value.ref, &candidate->ref)) { + // Found, update. + yexpr_destroy(&candidate->val); + candidate->val = yeval_list_return_last(state, letlist, counter); + return yexpr_new(); + } + if (yref_type(&candidate->ref) == YREF_UNDEF) + break; + } + + // Not found, push onto locals stack. + yeval_local_def_t new = {.ref = ref->value.ref, .val = yeval_list_return_last(state, letlist, counter)}; + YVEC_PUSH(&state->locals, &new); return yexpr_new(); #undef _pattern @@ -404,7 +430,11 @@ } yexpr_t ybuiltin_fn_mkclsr(yeval_state_t* state) { -#define _pattern "(_mkclsr function-ref)" // Returns a yexpr_t of type YEXPR_FUNC, with captured values. +#define _pattern \ + "(_mkclsr function-ref captured1 captured2 ...)" // Sets function-ref to a + // yexpr_t of type + // YEXPR_FUNC, with + // captured values. yexpr_t mkclsr; yexpr_t closure = yexpr_new(); @@ -412,17 +442,18 @@ if (mkclsr.typ != YEXPR_LIST) BADEXPRFAIL(INTERNAL_MKCLSR, mkclsr); if (mkclsr.value.list.len != 2) BADEXPRFAIL(INTERNAL_MKCLSR, mkclsr); - yexpr_t *head = YVEC_AT(&mkclsr.value.list, 0, yexpr_t), *tail = YVEC_AT(&mkclsr.value.list, 1, yexpr_t); - if (head->typ != YEXPR_BUILTIN || head->value.builtin != YBUILTIN_INTERNAL_MKCLSR) BADEXPRFAIL(INTERNAL_MKCLSR, mkclsr); + yexpr_t *head = YVEC_AT(&mkclsr.value.list, 0, yexpr_t), + *tail = YVEC_AT(&mkclsr.value.list, 1, yexpr_t); + if (head->typ != YEXPR_BUILTIN || + head->value.builtin != YBUILTIN_INTERNAL_MKCLSR) + BADEXPRFAIL(INTERNAL_MKCLSR, mkclsr); if (tail->typ != YEXPR_REF) BADEXPRFAIL(INTERNAL_MKCLSR, mkclsr); - yvalue_t *funcval = yvalue_get(tail->value.ref); - if (funcval->typ != YVALUE_FUNC) TYPEFAIL(INTERNAL_MKCLSR, mkclsr, _pattern); - yfunc_t *func = &funcval->value.func; - // Vector of yref_t. - yvec_t *to_capture = &func->captured; + yvalue_t* funcval = yvalue_get(tail->value.ref); + if (funcval->typ != YVALUE_FUNC) + TYPEFAIL(INTERNAL_MKCLSR, mkclsr, _pattern); + yfunc_t* func = &funcval->value.func; - does-not-compile // TODO: continue implementation #undef _pattern } @@ -432,10 +463,24 @@ * * TODO: write built-ins. */ -static const ybuiltin_fn YBUILTIN_FNS[] = { - ybuiltin_fn_undef, ybuiltin_fn_for, ybuiltin_fn_let, NULL, - ybuiltin_fn_plus, ybuiltin_fn_minus, ybuiltin_fn_times, NULL, - ybuiltin_fn_if, ybuiltin_fn_print, ybuiltin_fn_eq}; +static const ybuiltin_fn YBUILTIN_FNS[] = {ybuiltin_fn_undef, + ybuiltin_fn_for, + ybuiltin_fn_let, + NULL, + ybuiltin_fn_plus, + ybuiltin_fn_minus, + ybuiltin_fn_times, + NULL, + ybuiltin_fn_if, + ybuiltin_fn_print, + ybuiltin_fn_eq, + NULL, + NULL, + NULL, + NULL, + NULL, + NULL, + ybuiltin_fn_mkclsr}; const char* ybuiltin_name(YBUILTIN_TYPE t) { assert(t * sizeof(const char*) < sizeof(YBUILTIN_ENUM_STR));
--- a/src/built-ins_test.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/built-ins_test.c Fri Sep 27 14:30:38 2019 +0200 @@ -50,6 +50,7 @@ yexpr_debug(&program); yeval_state_t state = {.call_stack = YVEC_NEW(NULL, 0, yexpr_t)}; + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); YVEC_PUSH(&state.call_stack, for_expr); yexpr_t result = ybuiltin_run(YBUILTIN_FOR, &state); @@ -58,6 +59,7 @@ yexpr_debug(&result); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&program); yexpr_destroy(&result); ystr_destroy(&input); @@ -77,6 +79,7 @@ yexpr_debug(for_expr); yeval_state_t state = {.call_stack = YVEC_NEW(NULL, 0, yexpr_t)}; + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); YVEC_PUSH(&state.call_stack, for_expr); yexpr_t result = ybuiltin_run(YBUILTIN_FOR, &state); @@ -87,6 +90,7 @@ assert(4 == YVEC_AT(&result.value.list, 0, yexpr_t)->value.n); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&program); yexpr_destroy(&result); ystr_destroy(&input); @@ -107,6 +111,7 @@ yexpr_debug(for_expr); yeval_state_t state = {.call_stack = YVEC_NEW(NULL, 0, yexpr_t)}; + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); YVEC_PUSH(&state.call_stack, for_expr); yexpr_t result = ybuiltin_run(YBUILTIN_FOR, &state); @@ -114,6 +119,7 @@ assert(result.value.list.len == 0); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&program); ystr_destroy(&input); yexpr_destroy(&result); @@ -196,6 +202,7 @@ yeval_state_t state; YVEC_INIT(&state.call_stack, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); YVEC_PUSH(&state.call_stack, let_expr); yexpr_t result = ybuiltin_run(YBUILTIN_LET, &state); assert(result.typ == YEXPR_UNDEF); @@ -213,6 +220,7 @@ yexpr_destroy(&program); yref_destroy(&my_var_ref); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); ystr_destroy(&input); ystr_destroy(&error); } @@ -231,6 +239,7 @@ ypreprocess_resolve_builtins(&program); yeval_state_t state = {.call_stack = YVEC_NEW(NULL, 0, yexpr_t)}; + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); // Evaluate whole program yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); @@ -242,6 +251,7 @@ assert(0 == ystr_cmp_str(&inner->value.str, "cd")); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&result); ystr_destroy(&error); ystr_destroy(&input); @@ -269,6 +279,7 @@ yeval_state_t state; YVEC_INIT(&state.call_stack, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_LIST); yexpr_debug(&result); @@ -283,6 +294,7 @@ ystr_destroy(&input); ystr_destroy(&error); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); } void test_builtin_print(void) { @@ -308,6 +320,7 @@ yeval_state_t state; YVEC_INIT(&state.call_stack, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_UNDEF); @@ -322,6 +335,7 @@ ystr_destroy(&input); ystr_destroy(&error); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); } int main(void) {
--- a/src/eval.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/eval.c Fri Sep 27 14:30:38 2019 +0200 @@ -86,6 +86,21 @@ state->call_stack.len - 1 - yref_cix(&expr->value.ref), yexpr_t)); return result; + } else if (yref_type(&expr->value.ref) == YREF_LOCAL) { + // First look for locally defined variables, then for captured ones. + for (size_t i = state->locals.len - 1; i > 0; i--) { + yeval_local_def_t* candidate = YVEC_AT(&state->locals, i, yeval_local_def_t); + if (yref_type(&candidate->ref) == YREF_UNDEF) + break; + if (yref_eq(&expr->value.ref, &candidate->ref)) + return candidate->val; + } + // Look for captured variables. + for (size_t i = 0; i < state->current_closure->captured.len; i++) { + ycaptured_t* candidate = YVEC_AT(&state->current_closure->captured, i, ycaptured_t); + if (yref_eq(&expr->value.ref, &candidate->ref)) + return candidate->expr; + } } yvalue_t* val = yvalue_get(expr->value.ref); if (val == NULL) return yeval_undef_ref(&expr->value.ref); @@ -115,6 +130,10 @@ return ybuiltin_run(first->value.builtin, state); } + // Push "separator" frame onto locals stack. + yeval_local_def_t sep = {.ref = yref_new_undef() }; + YVEC_PUSH(&state->locals, &sep); + // Is function call? if (first->typ == YEXPR_REF) { yexpr_t ref = yeval(state, first, false); @@ -122,16 +141,16 @@ if (ref.typ == YEXPR_REF) { yvalue_t* val = yvalue_get(ref.value.ref); if (val == NULL) { - return yeval_undef_ref(&expr->value.ref); + result = yeval_undef_ref(&expr->value.ref); + goto clean_up; } // Call function. if (val->typ == YVALUE_FUNC) { result = yeval_call_func(state, &val->value.func, expr); if (in_place) { yexpr_destroy(&result); - return result; } - return result; + goto clean_up; } else if (val->typ == YVALUE_EXPR) { assert(val->typ == YVALUE_FUNC /* yeval() should have returned a copy of the expression if first element was a reference to an expression */); } @@ -150,16 +169,25 @@ yeval(state, elem, /* in_place= */ true); yexpr_destroy(&elem_result); } - return result; + } else { + // Store results; input list is copied shallowly, and assigned + // with copied values from yeval. + result.value.list = yvec_clone(&expr->value.list); + for (size_t i = 0; i < result.value.list.len; i++) { + yexpr_t* elem = YVEC_AT(&result.value.list, i, yexpr_t); + yexpr_t elem_result = yeval(state, elem, /* in_place= */ false); + *elem = elem_result; + } } - // Store results; input list is copied shallowly, and assigned - // with copied values from yeval. - result.value.list = yvec_clone(&expr->value.list); - for (size_t i = 0; i < result.value.list.len; i++) { - yexpr_t* elem = YVEC_AT(&result.value.list, i, yexpr_t); - yexpr_t elem_result = yeval(state, elem, /* in_place= */ false); - *elem = elem_result; +clean_up: + // Clean up locals. + for (size_t i = state->locals.len - 1; i > 0; i--) { + yeval_local_def_t* def = YVEC_AT(&state->locals, i, yeval_local_def_t); + if (yref_type(&def->ref) == YREF_UNDEF) + break; + yexpr_destroy(&def->val); + yvec_pop(&state->locals, NULL); } return result; default:
--- a/src/eval.h Thu Sep 12 08:25:27 2019 +0200 +++ b/src/eval.h Fri Sep 27 14:30:38 2019 +0200 @@ -11,6 +11,12 @@ * @{ */ +typedef struct { + // if ref's type is YREF_UNDEF, this element marks a scope border. + yref_t ref; + yexpr_t val; +} yeval_local_def_t; + /// Evaluation state passed to invocations of `yeval`. There only exists one /// instance of this value per program, so per-eval-call information should be /// passed directly to yeval. @@ -19,8 +25,10 @@ /// a quick way (push/pop is fast on pre-allocated memory). yvec_t call_stack; - // TODO: Maybe move value and atom tables in here? For now, it doesn't make - // a difference. + /// Values captured by the closure we are currently evaluating. + yclosure_t* current_closure; + /// Values defined in functions. Grows; every scope has a contiguous sequence and different scopes are separated by YREF_UNDEF entries. + yvec_t /* <yeval_local_def> */ locals; } yeval_state_t; /**
--- a/src/eval_test.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/eval_test.c Fri Sep 27 14:30:38 2019 +0200 @@ -16,6 +16,7 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 4, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_LIST); assert(result.value.list.len == 0); @@ -24,6 +25,7 @@ ystr_destroy(&input); ystr_destroy(&error); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&result); } @@ -43,6 +45,7 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 4, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_EXCEPTION); assert(0 == ystr_cmp_str(&result.value.str, @@ -54,6 +57,7 @@ ystr_destroy(&input); ystr_destroy(&error); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&result); } @@ -73,6 +77,7 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 4, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); yexpr_debug(&result); assert(YEXPR_LIST == result.typ); @@ -80,6 +85,7 @@ yexpr_destroy(&program); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); ystr_destroy(&error); yexpr_destroy(&result); ystr_destroy(&input); @@ -100,10 +106,12 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 4, yexpr_t); + state.locals = YVEC_NEW(NULL, 4, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(YEXPR_NUMBER == result.typ && 4 == result.value.n); yexpr_destroy(&program); + yvec_destroy(&state.locals); yvec_destroy(&state.call_stack); ystr_destroy(&error); yexpr_destroy(&result); @@ -125,11 +133,14 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 4, yexpr_t); + yvec_destroy(&state.locals); + state.locals = YVEC_NEW(NULL, 4, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(YEXPR_EXCEPTION == result.typ); yexpr_destroy(&program); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); ystr_destroy(&error); yexpr_destroy(&result); ystr_destroy(&input);
--- a/src/func.h Thu Sep 12 08:25:27 2019 +0200 +++ b/src/func.h Fri Sep 27 14:30:38 2019 +0200 @@ -39,12 +39,6 @@ /// Vector of yarg_desc_t values, each describing an argument, in order of /// appearance. yvec_t args; - /// Vector of yref_t values, each describing a value to be captured in - /// a closure. When defining the function, the interpreter should copy the - /// values of these references into the closure yexpr_t value (via the - /// to-be-implemented _mkclsr built-in). / When calling a function, the - /// captured values are pushed onto the stack before the function arguments. - yvec_t captured; } yfunc_t; /**
--- a/src/preprocess.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/preprocess.c Fri Sep 27 14:30:38 2019 +0200 @@ -132,14 +132,14 @@ yvec_t refs; } ypreprocess_scope_t; -static yref_t ypreprocess_find_or_create_ref( - ystr_t* symbol, yvec_t* /* of ypreprocess_scope_t* */ scope_stack) { +static yref_t ypreprocess_find_or_create_ref(ystr_t* symbol, + ypreprocess_state_t* state) { // Search for symbol in stack, starting at top-most scope (enclosing list) // and working upwards. - for (size_t i = 0; i < scope_stack->len; i++) { - size_t index = scope_stack->len - 1 - i; + for (size_t i = 0; i < state->scopes.len; i++) { + size_t index = state->scopes.len - 1 - i; ypreprocess_scope_t* scope = - *YVEC_AT(scope_stack, index, ypreprocess_scope_t*); + *YVEC_AT(&state->scopes, index, ypreprocess_scope_t*); // If found: Add reference to closure captured list for (size_t ref = 0; ref < scope->refs.len; ref++) { @@ -152,18 +152,52 @@ } // No existing reference found! Create one in the current scope. - yref_t ref = yref_new(); + yref_t ref = yref_new_local(); // For all new references, we define them in the scope above the current // list (thus "- 2"), e.g. in let, defn ypreprocess_scope_t* topscope = - *YVEC_AT(scope_stack, scope_stack->len - 2, ypreprocess_scope_t*); + *YVEC_AT(&state->scopes, state->scopes.len - 2, ypreprocess_scope_t*); ypreprocess_existing_t newref = {.sym = ystr_clone(symbol), .ref = ref}; YVEC_PUSH(&topscope->refs, &newref); return ref; } -static void ypreprocess_refs_recursive( - yvec_t* /* of ypreprocess_scope_t* */ scope_stack, yexpr_t* expr) { +/// Mark the given reference for capture in all function descriptions up to the +/// function defining it. Returns true if a definition of the reference was +/// found somewhere in the lexical stack. +/// TODO: Merge with ypreprocess_find_or_create_ref(). +static bool ypreprocess_set_capture(yref_t ref, ypreprocess_state_t* state) { + // If we are at the top level definition, we don't need to look further up. + if (state->defn_scopes.len < 1) return false; + + // Find innermost function defining the reference, and add it to the capture + // list of all functions inside it. + for (size_t i = state->defn_scopes.len - 1; i > 0; i--) { + size_t scopeix = *YVEC_AT(&state->defn_scopes, i, size_t); + yvec_t* defined_refs = + &YVEC_AT(&state->scopes, scopeix, ypreprocess_scope_t)->refs; + + // Check if function defines this reference. + for (size_t j = 0; j < defined_refs->len; j++) { + ypreprocess_existing_t* candidate = + YVEC_AT(defined_refs, j, ypreprocess_existing_t); + if (yref_eq(&candidate->ref, &ref)) { + // Found function defining it! We are done here. + return true; + } + } + // This is not the defn defining the reference. Mark the reference to be + // captured by it. + assert(yref_type(&ref) == YREF_LOCAL || yref_type(&ref) == YREF_STACK); + yvec_t* captured = YVEC_AT(&state->capture, i, yvec_t); + YVEC_PUSH(captured, &ref); + } + return false; +} + +/** Assign unique IDs to every reference. */ +static void ypreprocess_refs_recursive(ypreprocess_state_t* state, + yexpr_t* expr) { // Abort cheaply for types we don't want to resolve anyway. switch (expr->typ) { case YEXPR_UNDEF: @@ -178,21 +212,25 @@ } ypreprocess_scope_t scope; - ypreprocess_scope_t* scopep = &scope; switch (expr->typ) { case YEXPR_REF: if (yref_type(&expr->value.ref) == YREF_SYM) { ystr_t* sym = &expr->value.ref.ref.sym; - yref_t resolved = - ypreprocess_find_or_create_ref(sym, scope_stack); + yref_t resolved = ypreprocess_find_or_create_ref(sym, state); + bool found = ypreprocess_set_capture(resolved, state); yexpr_set_ref(expr, resolved); + } else if (yref_type(&expr->value.ref) == YREF_STACK) { + bool found = ypreprocess_set_capture(expr->value.ref, state); } break; case YEXPR_LIST: // Create new scope for list. scope.refs = YVEC_NEW(NULL, 4, ypreprocess_existing_t); - YVEC_PUSH(scope_stack, &scopep); + + ypreprocess_scope_t* scopep = &scope; + yvec_t* scope_stack = &state->scopes; + YVEC_PUSH(&state->scopes, &scopep); // Handle functions. if (expr->value.list.len >= 4) { @@ -201,9 +239,20 @@ head->value.builtin == YBUILTIN_DEFN) { // Compile and store function. Push symbol->reference // mapping onto scope stack. + + // Set up closure support: + // List of references that this function depends on. + yvec_t captured; + size_t stackix = scope_stack->len - 1; + YVEC_INIT(&captured, 4, yref_t); + + YVEC_PUSH(&state->defn_scopes, &stackix); + YVEC_PUSH(&state->capture, &captured); + yref_t new_ref; // TODO: handle errors better - bool compile_defn_ok = ypreprocess_compile_defn(expr, &new_ref); + bool compile_defn_ok = + ypreprocess_compile_defn(expr, &new_ref); assert(compile_defn_ok); yvalue_t* func = yvalue_get(new_ref); assert(func != NULL); @@ -215,13 +264,57 @@ ypreprocess_scope_t*)) ->refs, &funcref); - // TODO: Build in references to captured args here (for closures) and give to subsequent functions + yvec_t* func_body = &func->value.func.body; for (size_t i = 0; i < func_body->len; i++) { ypreprocess_refs_recursive( - scope_stack, YVEC_AT(func_body, i, yexpr_t)); + state, YVEC_AT(func_body, i, yexpr_t)); } + // Now we know which references are used by inner functions. + // We can replace the `defn` list with a `(let name (_mkclsr ...))` expression. + + ypreprocess_find_or_create_ref(&func->value.func.name, state); + + yvec_t* to_capture = YVEC_AT( + &state->capture, state->capture.len - 1, yvec_t); + + yvec_t mkclsr_list; + YVEC_INIT(&mkclsr_list, 2 + to_capture->len, yexpr_t); + yexpr_t mkclsr_bi = yexpr_new(); + yexpr_set_builtin(&mkclsr_bi, YBUILTIN_INTERNAL_MKCLSR); + yexpr_t funcrefex = yexpr_new(); + yexpr_set_ref(&funcrefex, new_ref); + + YVEC_PUSH(&mkclsr_list, &mkclsr_bi); + YVEC_PUSH(&mkclsr_list, &funcrefex); + for (size_t i = 0; i < to_capture->len; i++) { + yexpr_t refex = yexpr_new(); + yexpr_set_ref(&refex, *YVEC_AT(to_capture, i, yref_t)); + YVEC_PUSH(&mkclsr_list, &refex); + } + yexpr_t mkclsr = yexpr_new(); + yexpr_set_list(&mkclsr, mkclsr_list); + + yvec_t let_list; + YVEC_INIT(&let_list, 3, yexpr_t); + yexpr_t let_bi = yexpr_new(); + yexpr_set_builtin(&let_bi, YBUILTIN_LET); + + YVEC_PUSH(&let_list, &let_bi); + yexpr_t let_expr = yexpr_new(); + yexpr_set_list(&let_expr, &let_list); + + *expr = mkclsr; + + yvec_pop(&state->defn_scopes, NULL); + yvec_t capt; + yvec_pop(&state->capture, &capt); + yvec_destroy(&capt); + + fprintf(stderr, "defined function %s: ", + ystr_str(&func->value.func.name)); + yexpr_debug(expr); goto cleanup; } } @@ -231,12 +324,13 @@ // Resolve list elements recursively. for (size_t i = 0; i < expr->value.list.len; i++) { yexpr_t* elem = YVEC_AT(&expr->value.list, i, yexpr_t); - ypreprocess_refs_recursive(scope_stack, elem); + ypreprocess_refs_recursive(state, elem); } cleanup: // Clean up. - yvec_pop(scope_stack, NULL); + yvec_pop(&state->scopes, NULL); + for (size_t i = 0; i < scope.refs.len; i++) { ypreprocess_existing_t* ex = YVEC_AT(&scope.refs, i, ypreprocess_existing_t); @@ -250,25 +344,35 @@ } } -// Initial invocation must be of type YEXPR_LIST. +// Initial invocation must be of type YEXPR_LIST and represent the top-level +// program. void ypreprocess_refs(yexpr_t* expr) { + ypreprocess_state_t state; yvec_t scope_stack = YVEC_NEW(NULL, 16, ypreprocess_scope_t*); - ypreprocess_refs_recursive(&scope_stack, expr); + state.scopes = scope_stack; + state.capture = YVEC_NEW(NULL, 16, yvec_t); + state.defn_scopes = YVEC_NEW(NULL, 16, size_t); + + ypreprocess_refs_recursive(&state, expr); assert(scope_stack.len == 0); yvec_destroy(&scope_stack); } -void ypreprocess_refs_repl(yexpr_t* repl_expr, yvec_t** scope_stack) { - if (*scope_stack == NULL) { - *scope_stack = malloc(sizeof(yvec_t)); - **scope_stack = YVEC_NEW(NULL, 16, ypreprocess_scope_t*); +void ypreprocess_refs_repl(yexpr_t* repl_expr, ypreprocess_state_t** state) { + if (*state == NULL) { + *state = malloc(sizeof(ypreprocess_state_t)); + yvec_t scope_stack = YVEC_NEW(NULL, 16, ypreprocess_scope_t*); + (*state)->scopes = scope_stack; + (*state)->capture = YVEC_NEW(NULL, 16, yvec_t); + (*state)->defn_scopes = YVEC_NEW(NULL, 16, size_t); + ypreprocess_scope_t* root = malloc(sizeof(ypreprocess_scope_t)); root->refs = YVEC_NEW(NULL, 4, ypreprocess_existing_t); - YVEC_PUSH(*scope_stack, &root); + YVEC_PUSH(&(*state)->scopes, &root); } assert(YEXPR_LIST == repl_expr->typ); for (size_t i = 0; i < repl_expr->value.list.len; i++) { yexpr_t* elem = YVEC_AT(&repl_expr->value.list, i, yexpr_t); - ypreprocess_refs_recursive(*scope_stack, elem); + ypreprocess_refs_recursive(*state, elem); } }
--- a/src/preprocess.h Thu Sep 12 08:25:27 2019 +0200 +++ b/src/preprocess.h Fri Sep 27 14:30:38 2019 +0200 @@ -10,6 +10,21 @@ * @{ */ +typedef struct { + yvec_t /* <ypreprocess_scope_t> */ scopes; + + // The following two vecs are in "lock-step", each element corresponds to + // the same index in the other. + + /// Each `defn` pushes a new vector onto this stack. It contains the index + /// of the scope frame belonging to that function. + yvec_t /* <size_t> */ defn_scopes; + /// Each `defn` pushes a new vector onto this stack. Every time a reference + /// is encountered, it is pushed onto all stacks down to the function + /// defining it. yref_ts must be of type YREF_LOCAL. + yvec_t /* <yvec_t<yref_t>> */ capture; +} ypreprocess_state_t; + /** * @brief Apply preprocessing stages, listed as individual functions below. */ @@ -29,7 +44,7 @@ */ void ypreprocess_refs(yexpr_t* expr); -void ypreprocess_refs_repl(yexpr_t* repl_expr, yvec_t** scope_stack); +void ypreprocess_refs_repl(yexpr_t* repl_expr, ypreprocess_state_t** state); /** * @} */
--- a/src/preprocess_test.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/preprocess_test.c Fri Sep 27 14:30:38 2019 +0200 @@ -43,6 +43,7 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 0, yexpr_t); + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_NUMBER); assert(252 == result.value.n); @@ -51,6 +52,7 @@ ystr_destroy(&input); yexpr_destroy(&program); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); yexpr_destroy(&result); } @@ -77,6 +79,7 @@ yeval_state_t state; state.call_stack = YVEC_NEW(NULL, 0, yexpr_t); + state.locals = YVEC_NEW(NULL, 0, yeval_local_def_t); yexpr_t result = yeval_list_return_last(&state, &program.value.list, 0); assert(result.typ == YEXPR_NUMBER); assert(45 == result.value.n); @@ -86,11 +89,32 @@ ystr_destroy(&input); ystr_destroy(&error); yvec_destroy(&state.call_stack); + yvec_destroy(&state.locals); +} + +void test_preprocess_closure(void) { + fprintf(stderr, "test_preprocess_closure ==============\n"); + + ystr_t input = ystr_new("(defn outer (x) (defn inner () (+ x 1)))"); + yexpr_t program = yexpr_new(); + ystr_t error = ystr_new(NULL); + assert(yparse_str(&input, &program, &error)); + + yexpr_debug(&program); + ypreprocess_resolve_builtins(&program); + yexpr_debug(&program); + ypreprocess_refs(&program); + yexpr_debug(&program); + + yexpr_destroy(&program); + ystr_destroy(&input); + ystr_destroy(&error); } int main(void) { test_preprocess_defn(); test_preprocess_refs(); + test_preprocess_closure(); fprintf(stderr, "global destroy ===========\n"); yvalue_free_all(); yatom_free_all();
--- a/src/sizes_test.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/sizes_test.c Fri Sep 27 14:30:38 2019 +0200 @@ -33,7 +33,7 @@ assert(8 == sizeof(yatom_t)); assert(24 == sizeof(yexpr_t)); assert(16 == sizeof(yref_t)); - assert(64 == sizeof(yfunc_t)); + assert(48 == sizeof(yfunc_t)); assert(32 == sizeof(yclosure_t)); }
--- a/src/types.h Thu Sep 12 08:25:27 2019 +0200 +++ b/src/types.h Fri Sep 27 14:30:38 2019 +0200 @@ -18,15 +18,17 @@ /** * @brief Type of a reference: Symbolic or numeric. - * - * Symbolic references can be resolved to a numeric one, creating a "value slot" - * (see `value.h`). */ typedef enum { + /// An uninitialized reference. YREF_UNDEF = 0, + /// A reference into the global value table - deprecated. YREF_ID = 1, + /// An unresolved reference consisting of a string in the `ref.sym` field. YREF_SYM = 2, + /// A stack-relative reference YREF_STACK = 3, + YREF_LOCAL = 4, } YREF_TYPE; /** @@ -42,20 +44,11 @@ ystr_t sym; /// An ID pointing to a slot in the values table (see value.c) yvalue_id_t id; - /// An index relative to the top of the call_stack, describing a - /// function argument. - uint64_t cix; + /// An ID pointing to a position on the call stack. + yvalue_id_t sid; } ref; } yref_t; -typedef struct { - /// Reference to function code. - yref_t id; - /// List of yexpr_t in the order of the `captured` field of the function - /// pointed to by id. - yvec_t captured; -} yclosure_t; - /** * @brief A yexpr_t can be a builtin (which looks like an ID), described by the * `builtin` field. @@ -90,7 +83,7 @@ YBUILTIN_RAISE = 15, YBUILTIN_RECOVER = 16, - YBUILTIN_INTERNAL_MKCLSR = 100, + YBUILTIN_INTERNAL_MKCLSR = 17, } YBUILTIN_TYPE; /** @@ -121,6 +114,13 @@ YEXPR_EXCEPTION = 8, } YEXPR_TYPE; +typedef struct { + /// Reference to function code. + yref_t id; + /// List of ycaptured_t. + yvec_t captured; +} yclosure_t; + /** * A value. Can be either a fundamental value (number, string, atom) or a list * of values. @@ -149,6 +149,12 @@ typedef struct yexpr_t yexpr_t; +/// Mapping of ID -> value. +typedef struct { + yref_t ref; + yexpr_t expr; +} ycaptured_t; + /** * @} */
--- a/src/value.c Thu Sep 12 08:25:27 2019 +0200 +++ b/src/value.c Fri Sep 27 14:30:38 2019 +0200 @@ -30,6 +30,12 @@ // 1. Every symbol has a corresponding place in the value table once it has // been created. +// Marker bytes to distinguish yref_t without an extra field. +static const yvalue_id_t YVALUE_ID_MARKER = 0xff00000000000000; +static const yvalue_id_t YVALUE_CALL_STACK_MARKER = 0xfe00000000000000; +static const yvalue_id_t YVALUE_LOCAL_MARKER = 0xfd00000000000000; +static const yvalue_id_t YVALUE_INVALID_MARKER = 0xee00000000000000; + static bool yvalue_table_initialized = false; static struct hsearch_data yvalue_name_table; static yvec_t yvalue_table; // vector of yvalue_t @@ -37,10 +43,7 @@ // TODO: Enable garbage collection/reuse instead of monotonic counter. (e.g. // reference-counting in different table) static yvalue_id_t yvalue_counter = YVALUE_COUNTER_OFFSET; - -// Marker bytes to distinguish yref_t without an extra field. -static const yvalue_id_t YVALUE_ID_MARKER = 0xff00000000000000; -static const uint64_t YVALUE_CIX_MARKER = 0xfe00000000000000; +static yvalue_id_t yvalue_local_counter = YVALUE_LOCAL_MARKER; static inline void yvalue_init_tables(void) { if (yvalue_table_initialized) return; @@ -58,9 +61,15 @@ if ((ref->ref.id & YVALUE_ID_MARKER) == YVALUE_ID_MARKER) { return YREF_ID; } - if ((ref->ref.id & YVALUE_CIX_MARKER) == YVALUE_CIX_MARKER) { + if ((ref->ref.id & YVALUE_CALL_STACK_MARKER) == YVALUE_CALL_STACK_MARKER) { return YREF_STACK; } + if ((ref->ref.id & YVALUE_LOCAL_MARKER) == YVALUE_LOCAL_MARKER) { + return YREF_LOCAL; + } + if ((ref->ref.id & YVALUE_INVALID_MARKER) == YVALUE_INVALID_MARKER) { + return YREF_UNDEF; + } return YREF_SYM; } @@ -88,7 +97,23 @@ } yref_t yref_new_cix(size_t ix) { - yref_t ref = {.ref.cix = ix | YVALUE_CIX_MARKER}; + yref_t ref = {.ref.id = ix | YVALUE_CALL_STACK_MARKER}; + return ref; +} + +yref_t yref_new_local(void) { + yref_t ref = {.ref.id = yvalue_local_counter++}; + return ref; +} + +yref_t yref_new_local_from_id(yvalue_id_t id) { + yref_t ref = {.ref.id = id}; + assert(yref_type(&ref) == YREF_LOCAL); + return ref; +} + +yref_t yref_new_undef(void) { + yref_t ref = {.ref.id = YVALUE_INVALID_MARKER}; return ref; } @@ -99,15 +124,16 @@ case YREF_SYM: return 0 == ystr_cmp(&a->ref.sym, &b->ref.sym); case YREF_ID: + case YREF_LOCAL: return a->ref.id == b->ref.id; case YREF_STACK: - return a->ref.cix == b->ref.cix; + return a->ref.sid == b->ref.sid; default: return false; } } -uint64_t yref_cix(yref_t* ref) { return ref->ref.cix ^ YVALUE_CIX_MARKER; } +uint64_t yref_cix(yref_t* ref) { return ref->ref.id ^ YVALUE_CALL_STACK_MARKER; } yref_t yref_clone(yref_t* ref) { switch (yref_type(ref)) { @@ -116,6 +142,8 @@ return yref_new_c(ystr_str(&ref->ref.sym)); case YREF_ID: case YREF_STACK: + case YREF_LOCAL: + case YREF_UNDEF: return *ref; default: assert(yref_type(ref) == YREF_SYM || yref_type(ref) == YREF_ID || @@ -152,6 +180,10 @@ ystr_t s = ystr_new(NULL); ystr_build(&s, "id:<stackrel:%lld>", -(int64_t)yref_cix(ref)); return s; + } else if (typ == YREF_LOCAL) { + ystr_t s = ystr_new(NULL); + ystr_build(&s, "id:<local:%lld>", ref->ref.sid); + return s; } return ystr_new("id:INVALID"); } @@ -221,7 +253,6 @@ yvalue_init_tables(); YREF_TYPE typ = yref_type(ref); - if (typ == YREF_ID) return; if (typ == YREF_SYM) { yvalue_id_t id = yvalue_resolve_or_create_symbol(&ref->ref.sym); // CAREFUL: This may cause double-frees if `ref` is copied from another
--- a/src/value.h Thu Sep 12 08:25:27 2019 +0200 +++ b/src/value.h Fri Sep 27 14:30:38 2019 +0200 @@ -78,6 +78,21 @@ yref_t yref_new_cix(size_t ix); /** + * Create a new unique "local" reference. + */ +yref_t yref_new_local(void); + +/** + * Create a local reference from a value. `id` must have been generated by yref_new_local(). + */ +yref_t yref_new_local_from_id(yvalue_id_t id); + +/** + * Create a reference of type YREF_UNDEF. + */ +yref_t yref_new_undef(void); + +/** * Return the stack-relative index of ref. */ uint64_t yref_cix(yref_t* ref);