x-eval.c File Reference

Evaluator with TCO trampoline. More...

#include "x-eval.h"
#include "x-eval-slots.h"
#include "x-obj/prim.h"
#include "x-env.h"
#include "x-tco.h"
#include "x-toplevel.h"
#include "x-obj.h"
#include "x-prim.h"
#include "x-type.h"
#include "x-alist.h"
#include "x-type/ptr.h"
#include "x-type/str.h"
#include "x-type/list.h"
#include "x-type/err.h"
#include "x-type/symbol.h"
#include "x-token.h"
#include <setjmp.h>
#include "x-type/prim.h"
#include "x-eval-layout.h"

Macros
#define	nil   NULL
#define	pair(X, Y)   (x_mkspair(p_base, X_OBJ_FLAG_NONE, (X), (Y)))
#define	atom(X)   (x_mksatom(p_base, X_OBJ_FLAG_NONE, (X)))
#define	X_EVAL_BUILD_TREE

Functions
x_obj_t *	x_eval_op_body (x_obj_t *p_base, x_obj_t *p_args)
static void	x_eval_tco_keep (x_obj_t *p_base, x_obj_t *p_te, x_obj_t *p_tco_root, x_obj_t **pp_save)
static void	x_eval_tco_apply (x_obj_t *p_base, x_obj_t *p_save)
x_obj_t *	x_eval (x_obj_t *p_base, x_obj_t *p_run)
void	x_eval_spine_guard (x_obj_t *p_base, x_obj_t *p_obj)
x_obj_t *	x_eval_spine_first (x_obj_t *p_base, x_obj_t *p_pos)
x_obj_t *	x_eval_list (x_obj_t *p_base, x_obj_t *p_vector)
x_obj_t *	x_eval_body (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_eval_body_tco (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_eval_tco_trampoline (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_eval_make (x_obj_t *p_base, x_obj_t *p_args)
void	x_eval_error (x_obj_t *p_base, x_char_t *message, x_obj_t *p_obj)
x_obj_t *	x_eval_type_alist_extend (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_eval_type_alist_assoc (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_eval_buffer_push (x_obj_t *p_base, x_obj_t *p_buffer)
x_obj_t *	x_eval_load (x_obj_t *p_base, x_obj_t *p_args)

Variables
static x_satom_t	s_bare_code = x_obj_set(NULL, X_OBJ_FLAG_NONE, { .s = NULL })
static x_satom_t	s_bare_subject = x_obj_set(NULL, X_OBJ_FLAG_NONE, { .s = NULL })
static x_spair_t	s_bare_err
static x_satom_t	x_type_prim_type_name_hook
static x_satom_t	x_type_prim_units_hook
static x_satom_t	x_type_prim_length_hook
static x_satom_t	x_eval_error_hook
static x_satom_t	x_type_heap_mark_hook
static x_satom_t	x_type_heap_free_hook
static const x_fn_t	x_eval_slot_fns [X_SLOT_LEN]

Detailed Description

Evaluator with TCO trampoline.

Author

Jon Ruttan (jonru.nosp@m.ttan.nosp@m.@gmai.nosp@m.l.co.nosp@m.m)

Copyright

2021 Jon Ruttan @license MIT No Attribution (MIT-0)

Macro Definition Documentation

atom

#define atom

(

X

)

(x_mksatom(p_base, X_OBJ_FLAG_NONE, (X)))

nil

#define nil   NULL

pair

#define pair	(		X,
			Y
	)		(x_mkspair(p_base, X_OBJ_FLAG_NONE, (X), (Y)))

X_EVAL_BUILD_TREE

#define X_EVAL_BUILD_TREE

Function Documentation

x_eval()

x_obj_t * x_eval	(	x_obj_t *	p_base,
		x_obj_t *	p_run
	)

Evaluate an expression with tail-call optimization.

Dispatches to the expression's type-level eval handler. If the handler sets a TCO tail expression on p_base, the trampoline loop re-evaluates without growing the C stack. On exit, restores the environment from the saved TCO snapshot.

The expression travels to the type's eval handler in a pair list built here, whose first element is a cell holding it: the trampoline stores each tail expression in that cell, and a handler answers the list to ask for another pass.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (expression)

Returns

x_obj_t* – Evaluated result, or NULL for nil

Outermost detection. The local trampolining flag starts at 0. When a TCO tail expression is first detected on p_base, this x_eval instance sets trampolining = 1, claiming ownership of the trampoline loop. Any nested x_eval called during handler dispatch will see tco_expr as cleared (this instance clears it before goto) and will therefore NOT enter the trampoline – it returns normally and its result is discarded in favor of the deferred tail expression.

tco_expr / tco_env lifecycle.

• Set by: x_eval_body_tco (full TCO) stores the tail expression in tco_expr and the environment to restore in tco_env. x_prim_match stores only tco_expr (tco_env stays nil – no env change needed).
• Consumed by: This function's trampoline loop. On each iteration it copies tco_expr into the eval args, clears tco_expr on p_base, and jumps to eval_start.

• tco_env cleared: Each iteration clears tco_env on p_base after snapshotting it into the local p_tco_env_save. This prevents nested x_eval calls from seeing stale env state.

  p_tco_env_save snapshot.

• Captured on first trampoline entry from tco_env on p_base.
• On later iterations, if the initial snapshot was nil (set by simple forms like if/match) but an inner form (fn/let/op) now provides a non-nil tco_env, the snapshot is upgraded.

• Used only at exit: the outermost x_eval makes it current.

  Nested x_eval calls do NOT restore env. Only the instance where trampolining == 1 executes the env restore block. This is critical: a recursive x_eval (e.g. from evaluating a sub-expression inside a primitive) must not interfere with the outer trampoline's env management.

Note

Uses goto-based trampoline; only the outermost x_eval in a call chain performs env restoration.

See also

x_eval_body_tco – full TCO body evaluator (sets tco_expr + tco_env)

x_eval_tco_trampoline – standalone trampoline used by closure call paths

x_eval_body()

x_obj_t * x_eval_body	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Evaluate a body (list of expressions) sequentially, returning the last result.

Each expression is rooted on the eval-list before evaluation so the GC does not collect the remaining body. No tail-call optimization.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (body), the list of body expressions

Returns

x_obj_t* – Result of the last expression, or NULL if empty

Note

When X_COV is defined, marks each body cell with X_OBJ_FLAG_COV; when X_PROFILE is, counts it (x_eval_reached).

x_eval_body_tco()

x_obj_t * x_eval_body_tco	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Evaluate a body with full tail-call optimization.

Non-tail expressions are evaluated normally. The tail (last) expression is stored in the TCO expr slot instead of being evaluated directly, and the caller's saved environment is captured in tco-env so the trampoline can restore it after the tail call.

On early exit (nil tail) or empty body, pops the save-stack and makes the environment it held current again.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (body), the list of body expressions

Returns

x_obj_t* – Result of non-tail expressions, or NULL when tail expression is deferred to the trampoline

Save-stack protocol. The caller (fn/let dispatch) pushes the environment it is leaving onto save_stack BEFORE calling this function (x_tco_env_save), so it can be made current again after the tail call completes.

tco_env capture. When the tail expression is reached (last element of body), this function checks whether tco_env is still nil. If so, it copies the save-stack top into tco_env, providing the env snapshot that x_eval's trampoline will use for restoration. If tco_env is already set (by a prior TCO iteration), the existing value is kept.

Save-stack pop. After capturing tco_env (or on early exit), the save-stack is popped. On the normal tail-call path this is a simple pop (the trampoline in x_eval handles restore). On early exit (nil tail or empty body), this function does a full restore from the popped frame before returning, since no trampoline iteration will follow.

Note

When X_COV is defined, marks each body cell with X_OBJ_FLAG_COV; when X_PROFILE is, counts it (x_eval_reached).

See also

x_eval – outermost trampoline that consumes tco_expr/tco_env

x_eval_tco_trampoline – standalone trampoline for closure call paths

x_eval_buffer_push()

x_obj_t * x_eval_buffer_push	(	x_obj_t *	p_base,
		x_obj_t *	p_buffer
	)

Push a buffer onto the buffer stack.

Parameters

p_base	x_obj_t* – Base (execution context)
p_buffer	x_obj_t* – Buffer object to push

Returns

x_obj_t* – The pushed buffer

x_eval_error()

void x_eval_error	(	x_obj_t *	p_base,
		x_char_t *	message,
		x_obj_t *	p_obj
	)

Signal an error with a message and optional object context.

If an error handler is installed (via guard), builds a combined error string with line number, restores the saved environment, and longjmps to the handler. Otherwise, writes the error to stderr via the low-level x_error function.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (message, object) – the error message string and the object associated with the error (may be nil)

Returns

x_obj_t* – NULL

Zero-allocation error path. When a handler is installed, the message string pointer is stored directly in a static atom (no malloc, no x_mkstrown). Message strings from C callers are always string literals (static storage), so they survive the longjmp. The guard handler in x-lang receives the bare message; x-lang code can add line/symbol context via (base) if needed.

longjmp protocol. The error value is stored in the handler's error slot, then the environment the handler saved at guard installation time is made current again. Finally, longjmp transfers control to the setjmp site in x_prim_guard. This unwinds all C frames between the error site and the guard – any local state in those frames is lost.

Note

When no handler is installed, writes the error via x_error and terminates the process (docs/spec.md pins this contract for error). Returning instead would resume the raising primitive mid-operation with a garbage value – at boot, where no guard is installed yet and the harness discards stderr, that silently corrupted the load (the class-call trap).

See also

x_prim_guard – installs the handler and setjmp site

x_prim_error – x-lang (error msg) primitive that calls this

x_eval_list()

x_obj_t * x_eval_list	(	x_obj_t *	p_base,
		x_obj_t *	p_vector
	)

Evaluate each element of a list, returning a new list of results.

Recursively evaluates through the eval slot, rooting the tail on the eval-list GC root so the garbage collector does not free remaining arguments while evaluating the current one.

Parameters

p_base	x_obj_t* – Base (execution context)
p_vector	x_obj_t* – Argument run: (args), the list of unevaluated expressions

Returns

x_obj_t* – New list of evaluated results, or NULL if empty

GC rooting protocol. Before evaluating the current element, the entire remaining arg list is pushed onto eval_list (a GC root on p_base) as a stack-allocated pair. This prevents the collector from freeing the rest of the list while the evaluation runs (which may trigger GC). After evaluation, the root is popped. The push/pop is O(1) per element, but the recursion itself is O(n) in C stack depth – one frame per list element. This is acceptable for argument lists (typically short) but would overflow on very long lists.

Note

Returns NULL for nil input (empty arg list), which is the identity for list construction.

See also

x_eval – evaluates a single expression

x_eval_body – iterative body evaluator (same GC rooting pattern)

x_eval_load()

x_obj_t * x_eval_load	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Read and evaluate all expressions from the current buffer.

Loops calling x_token_read until EOF, evaluating each expression via x_eval. Returns the result of the last expression.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Unused

Returns

x_obj_t* – Result of the last evaluated expression, or NULL

Reads from the buffer at the top of the buffer stack (x_base_field_buffer). The caller is responsible for pushing the desired buffer before calling this function (via x_eval_buffer_push) and popping it afterward. Each read expression is wrapped in a stack-allocated (atom . nil) eval-args pair and passed to x_eval, which runs the full evaluator including the TCO trampoline. The result of each expression is discarded except the last.

Note

This is the primary entry point for loading library files. The shell driver pipes library source via stdin (cat lib/x.x - | ./x-bin). The core loop reads through the buffer/fd stack; the optional include primitive (X_INCLUDE, x-cli.c) additionally opens files via x_sys_open and pushes them onto the same stack.

See also

x_eval – evaluator called for each expression

x_eval_make()

x_obj_t * x_eval_make	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Create and initialize a full x-lang base object atop x-expr.

Calls x_base_make (x-expr layer) with default file descriptors and the hooks for its slot vector, then fills in the type-system-specific fields: the env fields (the current environment and the root), the ctrl fields (save-stack, error-handler, TCO slots), io-state (line counter, boolean caches), extended profile counters, and project extras (eval-list, token-cache, mark-roots).

Parameters

p_base	x_obj_t* – Parent base (or NULL for root)
p_args	x_obj_t* – Unused

Returns

x_obj_t* – Newly constructed base object

x-expr vs x-lang layers. x_base_make (x-expr) allocates the base tree skeleton: heap fields (pools, GC state), file descriptors, buffer stack, type-alist slot, profile head (1 counter for GC cycles), and the slot vector. It leaves env, ctrl, io-state, and extras as nil. This function fills all of those in, giving the base its full evaluator personality.

Base tree nodes carry X_OBJ_FLAG_SHARED (set by x-expr's x_base_make). The SHARED flag tells the GC mark phase that these spine nodes are allocated from the base's own pool and must be marked but never freed – they are structurally permanent for the lifetime of the base.

Env fields layout:

(env . env-root)

• env: the current environment, a (bindings . parent) pair

• env-root: the base's root environment, whose bindings are a tree and whose parent is nil

  Ctrl fields layout:

  ((save-stack . (error-handler-slot . nil)) .
   ((tco-expr-slot . nil) . (tco-env-slot . nil)))

  Profile counters (9 additional beyond x-expr's GC counter): evals, TCO hits, lookups, BST lookups, and internal metrics.

Note

When p_base is non-NULL (child base), boolean caches (#t/#f) are inherited from the parent so all bases in a tree share the same singleton boolean objects.

See also

x_eval_error – uses the error-handler from the ctrl fields

x_eval – uses tco-expr/tco-env from the ctrl fields

x_eval_op_body()

x_obj_t * x_eval_op_body	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Defer an operative body's tail to the outer trampoline (TCO).

Evaluates the non-tail body forms synchronously, then stores the tail form in tco_expr and the caller's environment in tco_env. Deliberately does NOT push the save-stack – operatives stay invisible to it, so a procedure whose tail is an operative call still owns its own restore. The trampoline keeps the outermost environment it is handed and makes it current at exit, which for an operative is the caller's: a def the body evaluated in the caller's environment is IN that environment, so there is nothing to decide about keeping or shedding a chain head.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (body, caller). The body is the operative's sequence of forms; the caller is the caller's environment, current on return

Returns

x_obj_t* – NULL (result delivered via the trampoline)

x_eval_spine_first()

x_obj_t * x_eval_spine_first	(	x_obj_t *	p_base,
		x_obj_t *	p_pos
	)

Read the argument at an already-navigated spine position.

Parameters

p_base	Base (execution context).
p_pos	A spine position (the result of an x_1/x_11 peek).

Returns

The element at p_pos, or nil if the list ended there.

The raw positional macros (x_011 and friends) navigate first/rest UNCHECKED, which is their contract – so a caller peeking PAST the arity a guarded walk covered used to read the atom a dotted tail ends with as a pair (#487). This is that peek, done safely: nil when the list ended, the element when the position is a cell, and the ruled catchable raise on anything else.

See also

x_eval_spine_guard – the structural test

x_eval_spine_guard()

void x_eval_spine_guard	(	x_obj_t *	p_base,
		x_obj_t *	p_obj
	)

Raise unless p_obj is a spine cell that first/rest may navigate.

Parameters

p_base	Base (execution context).
p_obj	The spine position about to be walked (never nil).

Improper-spine guard (#69, ruled). A first/rest walk is only meaningful for an object whose TYPE DECLARES pair units – the same structural contract the collector's payload walk trusts (x_type_prim_heap_mark). The test is STRUCTURAL, not a type-identity list: any reader personality's spine type participates by declaring pair units (the reader and the evaluator need not be symmetric), and two layouts are cells by construction – raw stack cells (NULL type slot) and heap pairs labelled with the built-in pair static (the x_mkspair product; #296). The static's own type slot is NULL, so the registered-type probe could never accept it – omitting it made every C-built spine handed to an applicative in a minimal base raise spuriously. A dotted tail lands here as a non-cell and raises a catchable error in place of the segfault it replaces – (list 1 . 5), and bare-x-core (f 1.5) where the float module is absent and 1.5 reads as a dotted pair; the tail atom is atom-labelled or registered-typed, so neither layout re-admits it.

Note

Every C consumer of an argument spine funnels through here: x_eval_list for applicatives, and x_args/x_eargs for the prims (#487 – those walked past a dotted tail into x_firstobj on an atom, reading its value word as a pair pointer, which no guard could catch because a prim call never enters x_eval_list). Ops still receive their spines RAW and bind dotted tails legitimately, so they remain untouched.

See also

x_eval_list – the applicative argument walk

x_eargs – the prim argument walk (include/x-prim.h)

x_eval_tco_apply()

static void x_eval_tco_apply ( x_obj_t *  p_base, x_obj_t *  p_save  )

static

x_eval_tco_keep()

static void x_eval_tco_keep ( x_obj_t *  p_base, x_obj_t *  p_te, x_obj_t *  p_tco_root, x_obj_t **  pp_save  )

static

x_eval_tco_trampoline()

x_obj_t * x_eval_tco_trampoline	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

TCO trampoline: repeatedly evaluate deferred tail expressions.

After a TCO-aware body defers its tail expression, this loop evaluates it. If that evaluation itself defers another tail call, the loop continues until no more TCO expressions remain.

On exit, makes the environment saved in tco-env current again.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Argument run: (result), the initial result (from non-tail evaluation)

Returns

x_obj_t* – Final evaluation result

See also

x_eval_body_tco

x_eval_type_alist_assoc()

x_obj_t * x_eval_type_alist_assoc	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Look up a type struct in the base's type alist by name.

Searches for a (name . type_struct) entry matching the first element of p_args. Returns the bare type struct (unwrapped from the alist entry), or NULL if not found.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Pair whose first is the type name to look up

Returns

x_obj_t* – Type struct, or NULL

x_eval_type_alist_extend()

x_obj_t * x_eval_type_alist_extend	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Add a type struct to the base's type alist.

Wraps the type struct as a (name . type_struct) pair for alist keying and prepends it to the type alist.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – Type struct to register

Returns

x_obj_t* – The new type alist head, or NULL if base is unset

Variable Documentation

s_bare_code

x_satom_t s_bare_code = x_obj_set(NULL, X_OBJ_FLAG_NONE, { .s = NULL })

static

s_bare_err

x_spair_t s_bare_err

static

Initial value:

= x_obj_set(NULL, X_OBJ_FLAG_NONE,
    { (x_obj_t *)&s_bare_code }, { (x_obj_t *)&s_bare_subject })

s_bare_subject

x_satom_t s_bare_subject = x_obj_set(NULL, X_OBJ_FLAG_NONE, { .s = NULL })

static

x_eval_error_hook

x_satom_t x_eval_error_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .v = (void *)x_eval_error })

x_eval_slot_fns

const x_fn_t x_eval_slot_fns[X_SLOT_LEN]

static

Initial value:

= {
    [X_SLOT_EVAL] = x_eval,
    [X_SLOT_EVAL_LIST] = x_eval_list,
    [X_SLOT_EVAL_BODY] = x_eval_body,
    [X_SLOT_EVAL_BODY_TCO] = x_eval_body_tco,
    [X_SLOT_EVAL_TCO_TRAMPOLINE] = x_eval_tco_trampoline,
    [X_SLOT_EVAL_OP_BODY] = x_eval_op_body,
 
    [X_SLOT_CALLABLE_CALL] = x_callable_call,
    [X_SLOT_CALLABLE_APPLY] = x_callable_apply,
    [X_SLOT_OBJ_PRIM_CALL] = x_obj_prim_call,
 
    [X_SLOT_TOKEN_READ] = x_token_read,
    [X_SLOT_TOKEN_ANALYSE] = x_token_analyse,
    [X_SLOT_TOKEN_DELIMIT] = x_token_delimit,
 
    [X_SLOT_ENV_LOOKUP] = x_env_lookup,
    [X_SLOT_ENV_BIND] = x_env_bind,
 
 
    [X_SLOT_ENV_EXTEND] = x_env_extend,
 
    [X_SLOT_ALIST_BST_LOOKUP] = x_alist_bst_lookup,
 
    [X_SLOT_HEAP_MARK] = x_heap_mark_phase,
    [X_SLOT_HEAP_SWEEP] = x_heap_sweep_phase,
    [X_SLOT_OBJ_ALLOC] = x_eval_alloc
}

The routines the slot vector starts with, by position (see x-eval-slots.h). x_eval_make() fills a base's vector from this table.

x_type_heap_free_hook

x_satom_t x_type_heap_free_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .v = (void *)x_type_heap_free })

x_type_heap_mark_hook

x_satom_t x_type_heap_mark_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .v = (void *)x_type_heap_mark })

x_type_prim_length_hook

x_satom_t x_type_prim_length_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .fn = x_type_prim_length })

x_type_prim_type_name_hook

x_satom_t x_type_prim_type_name_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .fn = x_type_prim_type_name })

x_type_prim_units_hook

x_satom_t x_type_prim_units_hook

static

Initial value:

=
    x_obj_set(NULL, X_OBJ_FLAG_NONE, { .fn = x_type_prim_units })