docs/spec/evaluate.html


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

<head>
  <link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
  <link href="../style.css" rel="stylesheet"/>
  <title>Specification: BQN evaluation</title>
</head>
<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">spec</a></div>
<h1 id="specification-bqn-evaluation">Specification: BQN evaluation</h1>
<p>This page describes the semantics of the code constructs whose grammar is given in <a href="grammar.html">grammar.md</a>. 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.</p>
<p>Here we assume that the referent of each identifier, or equivalently the connections between identifiers, have been identified according to the <a href="scope.html">scoping rules</a>.</p>
<p>Evaluation is an ordered process, and any actions required to evaluate a node always have a specified order unless performing them in any order would have the same effect. Side effects that are relevant to ordering are setting and getting the value of a variable, causing an error, and returning (with <code><span class='Gets'>→</span></code>) from a block. Errors described in this page are &quot;evaluation errors&quot; and can be caught by the Catch (<code><span class='Modifier2'>⎊</span></code>) modifier. For caught errors and returns, evaluation halts without attempting to complete any in-progress node, and is restarted by Catch (for errors) or at the end of the appropriate block evaluation (for returns).</p>
<h3 id="programs-and-blocks">Programs and blocks</h3>
<p>The result of parsing a valid BQN program is a <code><span class='Function'>PROGRAM</span></code>, and the program is run by evaluating this term.</p>
<p>A <code><span class='Function'>PROGRAM</span></code> or <code><span class='Function'>BODY</span></code> is a list of <code><span class='Function'>STMT</span></code>s, which are evaluated in program order. A result is always required for <code><span class='Function'>BODY</span></code> nodes, and sometimes for <code><span class='Function'>PROGRAM</span></code> nodes (for example, when loaded with <code><span class='Function'>•Import</span></code>). If any identifiers in the node's scope are exported, or any of its statements is an <code><span class='Function'>EXPORT</span></code>, then the result is the namespace created in order to evaluate the node. If a result is required but the namespace case doesn't apply, then the last <code><span class='Function'>STMT</span></code> node must be an <code><span class='Function'>EXPR</span></code> and its result is used. The statement <code><span class='Function'>EXPR</span></code> evaluates some APL code and possibly assigns the results, while <code><span class='Value'>nothing</span></code> evaluates any <code><span class='Value'>subject</span></code> or <code><span class='Function'>Derv</span></code> terms it contains but discards the results. An <code><span class='Function'>EXPORT</span></code> statement performs no action.</p>
<p>A block consists of several <code><span class='Function'>BODY</span></code> terms, some of which may have an accompanying header describing accepted inputs and how they are processed. An immediate block <code><span class='Value'>brImm</span></code> can only have one <code><span class='Function'>BODY</span></code>, and is evaluated by evaluating the code in it. Other types of blocks do not evaluate any <code><span class='Function'>BODY</span></code> immediately, but instead return a function or modifier that obtains its result by evaluating a particular <code><span class='Function'>BODY</span></code>. The <code><span class='Function'>BODY</span></code> is identified and evaluated once the block has received enough inputs (operands or arguments), which for modifiers can take one or two calls: if two calls are required, then on the first call the operands are simply stored and no code is evaluated yet. Two calls are required if there is more than one <code><span class='Function'>BODY</span></code> term, if the <code><span class='Function'>BODY</span></code> contains the special names <code><span class='Value'>𝕨𝕩𝕤</span><span class='Function'>𝕎𝕏𝕊</span></code>, or if its header specifies arguments (the header-body combination is a <code><span class='Modifier'>_mCase</span></code> or <code><span class='Modifier2'>_cCase_</span></code>). Otherwise only one is required.</p>
<p>To evaluate a block when enough inputs have been received, first the correct case must be identified. To do this, first each special case (<code><span class='Function'>FCase</span></code>, <code><span class='Modifier'>_mCase</span></code>, or <code><span class='Modifier2'>_cCase_</span></code>), excluding <code><span class='Function'>FCase</span></code> nodes containing <code><span class='Function'>UndoHead</span></code>, is checked in order to see if its arguments are strucurally compatible with the given arguments. That is, is <code><span class='Value'>headW</span></code> is a <code><span class='Value'>subject</span></code>, there must be a left argument matching that structure, and if <code><span class='Value'>headX</span></code> is a <code><span class='Value'>subject</span></code>, the right argument must match that structure. This means that <code><span class='Value'>𝕨</span></code> not only matches any left argument but also no argument. The test for compatibility is the same as for multiple assignment described below, except that the header may contain constants, which must match the corresponding part of the given argument. If no special case matches, then an appropriate general case (<code><span class='Function'>FMain</span></code>, <code><span class='Modifier'>_mMain</span></code>, or <code><span class='Modifier2'>_cMain_</span></code>) is used: if there are two, the first is used with no left argument and the second with a left argument; if there are one, it is always used, and if there are none, an error results.</p>
<p>The only remaining step before evaluating the <code><span class='Function'>BODY</span></code> is to bind the inputs and other names. Special names are always bound when applicable: <code><span class='Value'>𝕨𝕩𝕤</span></code> if arguments are used, <code><span class='Value'>𝕨</span></code> if there is a left argument, <code><span class='Value'>𝕗𝕘</span></code> if operands are used, and <code><span class='Modifier'>_𝕣</span></code> and <code><span class='Modifier2'>_𝕣_</span></code> for modifiers and combinators, respectively. Any names in the header are also bound, allowing multiple assignment for arguments.</p>
<p>If there is no left argument, but the <code><span class='Function'>BODY</span></code> contains <code><span class='Value'>𝕨</span></code> at the top level, then it is conceptually re-parsed with <code><span class='Value'>𝕨</span></code> replaced by <code><span class='Nothing'>·</span></code> to give a monadic version before application; this modifies the syntax tree by replacing some instances of <code><span class='Value'>arg</span></code> with <code><span class='Value'>nothing</span></code>. However, it also causes an error if, in a function that is called with no left argument, <code><span class='Value'>𝕨</span></code> is used as an operand or list element, where <code><span class='Value'>nothing</span></code> is not allowed by the grammar. The same effect can also be achieved dynamically by treating <code><span class='Nothing'>·</span></code> as a value and checking for it during execution. If it is used as a left argument, then the function should instead be called with no left argument (and similarly in trains); it it is used as a right argument, then the function and its left argument are evaluated but rather than calling the function <code><span class='Nothing'>·</span></code> is &quot;returned&quot; immediately; and if it is used in another context then it causes an error.</p>
<h3 id="assignment">Assignment</h3>
<p>An <em>assignment</em> is one of the four rules containing <code><span class='Function'>ASGN</span></code>. It is evaluated by first evaluating the right-hand-side <code><span class='Value'>subExpr</span></code>, <code><span class='Function'>FuncExpr</span></code>, <code><span class='Modifier'>_m1Expr</span></code>, or <code><span class='Modifier2'>_m2Exp_</span></code> 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 subjects, only a lone identifier is allowed on the left-hand side and storage sets it equal to the result. For subjects, <em>destructuring assignment</em> is performed when an <code><span class='Value'>lhs</span></code> is <code><span class='Value'>lhsList</span></code> or <code><span class='Value'>lhsStr</span></code>. Destructuring assignment is performed recursively by assigning right-hand-side values to the left-hand-side targets, with single-identifier assignment as the base case.</p>
<p>The right-hand-side value, here called <code><span class='Value'>v</span></code>, in destructuring assignment must be a list (rank 1 array) or namespace. If it's a list, then each <code><span class='Function'>LHS_ENTRY</span></code> node must be an <code><span class='Function'>LHS_ELT</span></code>. The left-hand side is treated as a list of <code><span class='Value'>lhs</span></code> targets, and matched to <code><span class='Value'>v</span></code> element-wise, with an error if the two lists differ in length. If <code><span class='Value'>v</span></code> is a namespace, then the left-hand side must be an <code><span class='Value'>lhsStr</span></code> where every <code><span class='Function'>LHS_ATOM</span></code> is an <code><span class='Function'>LHS_NAME</span></code>, or an <code><span class='Value'>lhsList</span></code> where every <code><span class='Function'>LHS_ENTRY</span></code> is an <code><span class='Function'>LHS_NAME</span></code> or <code><span class='Value'>lhs</span> <span class='String'>&quot;⇐&quot;</span> <span class='Function'>LHS_NAME</span></code>, so that it can be considered a list of <code><span class='Function'>LHS_NAME</span></code> nodes some of which are also associated with <code><span class='Value'>lhs</span></code> nodes. To perform the assignment, the value of each name is obtained from the namespace <code><span class='Value'>v</span></code>, giving an error if <code><span class='Value'>v</span></code> does not define that name. The value is assigned to the <code><span class='Value'>lhs</span></code> node if present (which may be a destructuring assignment or simple subject assignment), and otherwise assigned to the same <code><span class='Function'>LHS_NAME</span></code> node used to get it from <code><span class='Value'>v</span></code>.</p>
<p><em>Modified assignment</em> is the subject assignment rule <code><span class='Value'>lhs</span> <span class='Function'>Derv</span> <span class='String'>&quot;↩&quot;</span> <span class='Value'>subExpr</span></code>. In this case, <code><span class='Value'>lhs</span></code> should be evaluated as if it were a <code><span class='Value'>subExpr</span></code> (the syntax is a subset of <code><span class='Value'>subExpr</span></code>), and the result of the function application <code><span class='Value'>lhs</span> <span class='Function'>Derv</span> <span class='Value'>subExpr</span></code> should be assigned to <code><span class='Value'>lhs</span></code>, and is also the result of the modified assignment expression.</p>
<h3 id="expressions">Expressions</h3>
<p>We now give rules for evaluating an <code><span class='Value'>atom</span></code>, <code><span class='Function'>Func</span></code>, <code><span class='Modifier'>_mod1</span></code> or <code><span class='Modifier2'>_mod2_</span></code> expression (the possible options for <code><span class='Function'>ANY</span></code>). A literal or primitive <code><span class='Value'>sl</span></code>, <code><span class='Function'>Fl</span></code>, <code><span class='Modifier'>_ml</span></code>, or <code><span class='Modifier2'>_cl_</span></code> has a fixed value defined by the specification (<a href="literal.html">literals</a> and <a href="primitive.html">built-ins</a>). An identifier <code><span class='Value'>s</span></code>, <code><span class='Function'>F</span></code>, <code><span class='Modifier'>_m</span></code>, or <code><span class='Modifier2'>_c_</span></code>, if not preceded by <code><span class='Value'>atom</span> <span class='String'>&quot;.&quot;</span></code>, must have an associated variable due to the scoping rules, and returns this variable's value, or causes an error if it has not yet been set. If it is preceded by <code><span class='Value'>atom</span> <span class='String'>&quot;.&quot;</span></code>, then the <code><span class='Value'>atom</span></code> node is evaluated first; its value must be a namespace, and the result is the value of the identifier's name in the namespace, or an error if the name is undefined. A parenthesized expression such as <code><span class='String'>&quot;(&quot;</span> <span class='Modifier'>_modExpr</span> <span class='String'>&quot;)&quot;</span></code> simply returns the result of the interior expression. A braced construct such as <code><span class='Function'>BraceFunc</span></code> is defined by the evaluation of the statements it contains after all parameters are accepted. Finally, a list <code><span class='String'>&quot;⟨&quot;</span> <span class='Separator'>⋄</span><span class='Value'>?</span> <span class='Paren'>(</span> <span class='Paren'>(</span> <span class='Function'>EXPR</span> <span class='Separator'>⋄</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>EXPR</span> <span class='Separator'>⋄</span><span class='Value'>?</span> <span class='Paren'>)</span><span class='Value'>?</span> <span class='String'>&quot;⟩&quot;</span></code> or <code><span class='Function'>ANY</span> <span class='Paren'>(</span> <span class='String'>&quot;‿&quot;</span> <span class='Function'>ANY</span> <span class='Paren'>)</span><span class='Function'>+</span></code> 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.</p>
<p>A <code><span class='Function'>Return</span></code> node creates a return function. As <a href="scope.html#returns">discussed</a> in the scoping rules, its identifier indicates a namespace from a particular block evaluation. When called, the function causes an error if that block has finished execution, or if the call includes a left argument <code><span class='Value'>𝕨</span></code>. Otherwise, evaluation stops immediately, and resumes at the end of the block where it returns the right argument <code><span class='Value'>𝕩</span></code> from that block.</p>
<p>Rules in the table below are function and modifier evaluation.</p>
<table>
<thead>
<tr>
<th>L</th>
<th>Left</th>
<th>Called</th>
<th>Right</th>
<th>R</th>
<th>Types</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Value'>𝕨</span></code></td>
<td><code><span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Paren'>)</span><span class='Value'>?</span></code></td>
<td><code><span class='Function'>Derv</span></code></td>
<td><code><span class='Value'>arg</span></code></td>
<td><code><span class='Value'>𝕩</span></code></td>
<td>Function, subject</td>
</tr>
<tr>
<td><code><span class='Value'>𝕗</span></code></td>
<td><code><span class='Function'>Operand</span></code></td>
<td><code><span class='Modifier'>_mod1</span></code></td>
<td></td>
<td></td>
<td>1-Modifier</td>
</tr>
<tr>
<td><code><span class='Value'>𝕗</span></code></td>
<td><code><span class='Function'>Operand</span></code></td>
<td><code><span class='Modifier2'>_mod2_</span></code></td>
<td><code><span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Function'>Func</span> <span class='Paren'>)</span></code></td>
<td><code><span class='Value'>𝕘</span></code></td>
<td>2-Modifier</td>
</tr>
</tbody>
</table>
<p>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 <code><span class='Value'>nothing</span></code> is not used as a parameter, leaving only a right argument in that case. The type of the Called value must be appropriate to the expression type, as indicated in the &quot;Types&quot; column. For function application, a data 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.</p>
<p>The following rules derive new functions or modifiers from existing ones.</p>
<table>
<thead>
<tr>
<th>Left</th>
<th>Center</th>
<th>Right</th>
<th>Result</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td><code><span class='Modifier2'>_mod2_</span></code></td>
<td><code><span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Function'>Func</span> <span class='Paren'>)</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>𝔽</span> <span class='Modifier2'>_C_</span> <span class='Function'>R</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>Operand</span></code></td>
<td><code><span class='Modifier2'>_mod2_</span></code></td>
<td></td>
<td><code><span class='Brace'>{</span><span class='Function'>L</span> <span class='Modifier2'>_C_</span> <span class='Function'>𝔽</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>Operand</span></code></td>
<td><code><span class='Function'>Derv</span></code></td>
<td><code><span class='Function'>Fork</span></code></td>
<td><code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>L</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>C</span><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>R</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Value'>nothing?</span></code></td>
<td><code><span class='Function'>Derv</span></code></td>
<td><code><span class='Function'>Fork</span></code></td>
<td><code><span class='Brace'>{</span>     <span class='Function'>C</span><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>R</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Brace'>}</span></code></td>
</tr>
</tbody>
</table>
<p>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 <code><span class='Function'>L</span></code>, <code><span class='Function'>C</span></code>, and <code><span class='Function'>R</span></code> for the results of the expressions in the left, center, and right columns, respectively. For the first two rules (<em>partial application</em>), the given operand is bound to the 2-modifier: the result is a 1-modifier that, when called, calls the center 2-modifier with the bound operand on the same side it appeared on and the new operand on the remaining side. A <em>train</em> 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 modifier partial application, the result will fail when applied if the center value does not have the 2-modifier type, and in a fork, it will fail if any component has a modifier 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.</p>