Specify AST evaluation

1 files changed, 30 insertions, 0 deletions

diff --git a/spec/evaluate.md b/spec/evaluate.md
new file mode 100644
index 00000000..3224cbc9
--- /dev/null
+++ b/spec/evaluate.md
@@ -0,0 +1,30 @@
+This page describes the semantics of the code constructs whose grammar is given in [grammar.md](grammar.md). The formation rules there are not named, and here they are identified by either the name of the term or by copying the rule entirely if there are several alternative productions.
+
+Here we assume that the referent of each identifier, or equivalently the connections between identifiers, have been identified according to the [scoping rules](scope.md).
+
+A `PROGRAM` or `BRACED` block is a list of `STMT`s (for `BRACED`, the last must be an `EXPR`, a particular kind of `STMT`), which are evaluated in program order. The statement `nothing` does nothing when evaluated, while `EXPR` evaluates some APL code and possibly assigns the results, as described below.
+
+One additional rule for `BRACED` blocks makes it easier to define ambivalent functions. Each such block that contains `𝕨` at the top level is parsed normally to give a dyadic function, but is also parsed a second time with all instances of `𝕨` replaced by `·` to give a monadic function (as the only effect is to change some instances of `arg` to `nothing`, this can be achieved efficiently by annotating parts of the AST that depend on `𝕨` as conditionally-nothing). When called, the dyadic function is used if both arguments are given and the monadic one is used if there is only one. This applies to modifiers and compositions written with `𝕨` as well, where the choice of which version to use is made when the derived function is called.
+
+An *assignment* is one of the four rules containing `ASGN`. It is evaluated by first evaluating the right-hand-side `valExpr`, `FuncExpr`, `_modExpr`, or `_cmpExp_` expression, and then storing the result in the left-hand-side identifier or identifiers. The result of the assignment expression is the result of its right-hand side. Except for values, only a lone identifier is allowed on the left-hand side and storage is obvious. For values, *multiple assignment* with a list left-hand side is also allowed. Multiple assignment is performed recursively by assigning right-hand-side values to the left-hand-side targets, with single-identifier (`v`) assignment as the base case. When matching the right-hand side to a list left-hand side, the left hand side is treated as a list of `lhs` targets. The evaluated right-hand side must be a list (rank-1 array) of the same length, and is matched to these targets element-wise.
+
+*Modified assignment* is the value assignment rule `lhs Derv "↩" valExpr`. In this case, `lhs` should be evaluated as if it were a `valExpr` (the syntax is a subset of `valExpr`), and the result of the function application `lhs Derv valExpr` should be assigned to `lhs`, and is also the result of the modified assignment expression.
+
+We now give rules for evaluating an `atom`, `Func`, `_mod` or `_comp_` expression (the possible options for `ANY`). A literal `vl`, `Fl`, `_ml`, or `_cl_` has a fixed value defined by the specification ([value literals](literal.md) and [built-ins](primitive.md)). An identifier `v`, `F`, `_m`, or `_c_` is evaluated by returning its value; because of the scoping rules it must have one when evaluated. A parenthesized expression such as `"(" _modExpr ")"` simply returns the result of the interior expression. A braced construct such as `BraceFunc` is defined by the evaluation of the statements it contains after all parameters are accepted. Finally, a list `"⟨" ⋄? ( ( EXPR ⋄ )* EXPR ⋄? )? "⟩"` or `ANY ( "‿" ANY )+` consists grammatically of a list of expressions. To evaluate it, each expression is evaluated in source order and their results are placed as elements of a rank-1 array. The two forms have identical semantics but different punctuation.
+
+Rules in the table below are function and operator evaluation.
+|  L  | Left                   | Called   | Right              |  R  | Types
+|-----|------------------------|----------|--------------------|-----|-----------
+| `𝕨` | `( value | nothing )?` | `Derv`   | `arg`              | `𝕩` | Function, value
+| `𝕗` | `Operand`              | `_mod`   |                    |     | Modifier
+| `𝕗` | `Operand`              | `_comp_` | `( value | Func )` | `𝕘` | Composition
+In each case the constituent expressions are evaluated in reverse source order: Right, then Called, then Left. Then the expression's result is obtained by calling the Called value on its parameters. A left argument of `nothing` is not used as a parameter, leaving only a right argument in that case. The data type of the Called value must be appropriate to the expression type, as indicated in the "Types" column. For function application, a value type (number, character, or array) is allowed. It is called simply by returning itself. Although the arguments are ignored in this case, they are still evaluated. A braced construct is evaluated by binding the parameter names given in columns L and R to the corresponding values. Then if all parameter levels present have been bound, its body is evaluated to give the result of application.
+
+The following rules derive new functions or operators from existing ones.
+| Left      | Center   | Right              | Result
+|-----------|----------|--------------------|--------------
+|           | `_comp_` | `( value | Func )` | `{𝔽 _C_ R}`
+| `Operand` | `_comp_` |                    | `{L _C_ 𝔽}`
+| `Operand` |  `Func`  | `Fork`             | `{(𝕨L𝕩)C(𝕨R𝕩)}`
+|           |  `Func`  | `Fork`             | `{     C(𝕨R𝕩)}`
+As with applications, all expressions are evaluated in reverse source order before doing anything else. Then a result is formed without calling the center value. Its value in BQN is given in the rightmost column, using `L`, `C`, and `R` for the results of the expressions in the left, center, and right columns, respectively. For the first two rules (*partial application*), the given operand is bound to the composition: the result is a modifier that, when called, calls the center composition with the bound operand on the same side it appeared on and the new operand on the remaining side. A *train* is a function that, when called, calls the right-hand function on all arguments, then the left-hand function, and calls the center function with these results as arguments. In a composition partial application, the result will fail when applied if the center value does not have the composition type, and in a fork, it will fail if any component has a modifier or composition type (that is, cannot be applied as a function). BQN implementations are not required to check for these types when forming the result of these expressions, but may give an error on formation even if the result will never be applied.