@page Execution Execution

## Execution model.

Names are scoped and visible in the scope they are defined in, after being
defined, and in child scopes.

The execution runs on the tree of `yexpr_t` after some preprocessing, like
resolution of symbolic references (to values, functions, etc.).

## Scoping.

**Example**:

```
-- This is the top level program.

-- SCOPE 0
(defn f1
 -- SCOPE 1
 (a b)
 (+ (* a a) b))

(defn f2
 -- SCOPE 2
 (a b)
 (defn inner-fn
  -- SCOPE 3
  (x)
  (* x x))
 -- scope 2 again
 (+ (inner-fn a) (inner-fn b)))

-- scope 0 again
(let x 33)

(print "The result is" (f1 5 x))
```

## Preprocessing

This section describes how the parsed syntax tree is processed before
evaluation. It consists of several stages, described in `preprocess.h` and
`preprocess.c`.

### Variable/reference resolution

Symbols in the source code ("symbolic references") are translated into
numeric references (using `yvalue_id_t`) to refer to value slots. This has the
potential to greatly enhance performance as referencing values does not invoke a
potentially expensive hash table lookup anymore but instead a cheap array
dereference. (The third type of reference is "stack-ref", a reference relative
to the head of the stack, used in function calls).

The challenge is identifying each scope uniquely so that there are no reference
conflicts, but possibly also trying to recycle references. The current `value`
implementation doesn't support recycling.

**Value allocation algorithm**: For uniquely allocating references using
`yvalue_create()`.

The value allocation runs as third stage after resolving built-ins and
processing function definitions. Only symbolic references, i.e. ones defined by
the parser, are resolved.

The algorithm uses a stack of lists, each list represents the list of
already-allocated values in a scope, and for each new scope, a new list is
pushed onto the stack. Each `let` or `defn` results in pushing a new reference
to the list or redefining an existing one; each reference to a value results in
looking up the value in the top-most list, then the list below, etc. until a
reference could be found (at which point the symbolic reference is translated
into a numeric reference).

A new scope is started for every list.

* Scan program tree
    * Encounter symbolic reference (an ID)? -> Look up in stack of scope-lists by
    walking each list in the stack until one is found. If none is found, this is
    an error.
    * Encounter new list: Push new scope onto stack.
    * Leave scope: Pop scope list from stack.

(see `preprocess.c`)

TODO: Garbage collection, slot recycling (free-slot-list), reference counting?

### Built-in functions and constructs

Built-in functions or constructs such as `let` and `for` are represented by a
normal `yexpr_t` value of type `YEXPR_BUILTIN` with the `builtin` field in the
inner union being set. Refer to `expr.h` for the complete list of built-ins.

Built-ins are resolved in the first preprocessor step, before symbols are
resolved.

Note that `defn` is a built-in, but is not expected to be present in the
processed program tree. All function definitions should be stored immutably and
be referenced from the program as IDs. They are not defined during execution
phase. See the section below on how `ypreprocess_defn()` handles `defn`
expressions.

## Function calls

`ypreprocess_refs()` extracts function definitions, stores them as values in the
value table, and replaces them with `undef` expressions.

The source code contains references to the arguments by name; the `defn`
preprocessing resolves all references to function arguments to "stack-refs",
meaning `yref_t` values of type `YREF_STACK`. Those references contain a number
referencing the function argument relative to the top of the stack (0 is the
top-most stack value, 1 the one below, etc.).

`yeval()` detects when an expression should be a function call. It is evaluated
as such if the first element of a list is a reference to a function or a
reference to a value containing a reference to a function:

```
(defn f (a) (+ a a))
(let g f)
(g 3)
-- 6
(f 3)
-- 6
```

For function calls, `yeval_call_func()` evaluates each argument and pushes it
onto the call stack (which is part of the `yeval_state_t` struct given to
evaluation functions). When the function body is evaluated from there, the
stack-refs will be resolved by `yeval` to the respective stack values. The
values on the stack are freed after the function body has been evaluated.

Built-ins are a different story; they are called with the whole built-in
expression on the stack as only value.

## Evaluation

-> see `yeval()` in `eval.h`.

Evaluation happens recursively. Each evaluation results in a new `yexpr_t`
value.

### In-place evaluation

Often, the result of an evaluation is not needed afterwards, because all that
was wanted are the side effects. In this case, it is not sensible to allocate
memory for the resulting expression.

The `in_place` option can be set in `yeval()` to avoid allocating memory to
store the result in. The evaluated expression remains untouched.

It may ONLY be set if

* `yeval()` evaluates expressions within a function that are not the last
expression (and thus don't need to be returned to the caller).
* `yeval()` is called with `in_place` already set.

## REPL

You can use the REPL binary `src/repl` to test out ylisp for yourself.