From 337044f77dc491459e798625972cd83bed1e72bc Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 6 Jan 2021 21:53:45 -0500 Subject: Specify Insert identity behavior --- docs/spec/inferred.html | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'docs/spec') diff --git a/docs/spec/inferred.html b/docs/spec/inferred.html index 724014c9..c8bf6bc0 100644 --- a/docs/spec/inferred.html +++ b/docs/spec/inferred.html @@ -9,8 +9,9 @@

For the specified cases, the given functions and modifiers refer to those particular representations. It is not necessary to detect equivalent representations, for example to reduce (+-×)⁼ to ∨⁼. However, it is necessary to identify computed functions and modifiers: for example F⁼ when the value of F in the expression is ∨, or (1⊑∧‿∨)⁼.

Identities

When monadic Fold (´) or Insert (˝) is called on an array of length 0, BQN attempts to infer a right identity value for the function in order to determine the result. A right identity value for a dyadic function 𝔽 is a value r such that e≡e𝔽r for any element e in the domain. For such a value r, the reduction r 𝔽´ l is equivalent to 𝔽´ l for a non-empty list l, because the first application (¯1⊑l) 𝔽 r gives ¯1⊑l, which is the starting point when no initial value is given. It's thus reasonable to define 𝔽´ l to be r 𝔽´ l for an empty list l as well, giving a result r.

-

More specifically, the identity of a dyadic function 𝔽 is defined to be a right identity value for the range of 𝔽, if exactly one such value exists. Otherwise, there is no identity and 𝔽´ or 𝔽˝ on an argument with length 0 results in an error.

-

Identity values for the arithmetic primitives below must be recognized.

+

For Fold, the result of 𝔽´ on an empty list is defined to be a right identity value for the range of 𝔽, if exactly one such value exists. If an identity can't be proven to uniquely exist, then an error results.

+

For Insert, 𝔽˝ on an array of length 0 is defined similarly, but also depends on the cell shape 1↓≢𝕩. The required domain is the arrays of that shape that also lie in the range of 𝔽 (over arbitrary arguments, not shape-restricted ones).

+

Identity values for the arithmetic primitives below must be recognized. Under Fold, the result is the given identity value, while under Insert, it is the identity value reshaped to the argument's cell shape.

@@ -65,6 +66,7 @@
+

Additionally, the identity of ∾˝ must be recognized: if 0=≠𝕩, then ∾˝𝕩 is (0∾2↓≢𝕩)⥊𝕩.

Undo

The Undo 1-modifier ⁼, given an operand 𝔽 and argument 𝕩, and possibly a left argument 𝕨, finds a value y such that 𝕩≡𝕨𝔽y, that is, an element of the pre-image of 𝕩 under 𝔽 or 𝕨𝔽⊢. Thus it satisfies the constraint 𝕩 ≡ 𝕨𝔽𝕨𝔽⁼𝕩 (𝕨𝔽⁼⊢ is a right inverse of 𝕨𝔽⊢) provided 𝔽⁼ and 𝔽 both complete without error. 𝔽⁼ should of course give an error if no inverse element exists, and can also fail if no inverse can be found. It is also preferred for 𝔽⁼ to give an error if there are many choices of inverse with no clear way to choose one of them: for example, 0‿0⍉m returns the diagonal of matrix m; 0‿0⍉⁼2‿3 requires values to be chosen for the off-diagonal elements in its result. It is better to give an error, encouraging the programmer to use a fully-specified approach like 2‿3⌾(0‿0⊸⍉) applied to a matrix of initial elements, than to return a result that could be very different from other implementations.

When working with limited-precision numbers, it may be difficult or impossible to exactly invert the operand function. Instead, it is generally acceptable to perform a computation that, if done with unlimited precision, would exactly invert 𝔽 computed with unlimited precision. This principle is the basis for the numeric inverses specified below. It is also acceptable to find an inverse by numeric methods, provided that the error in the inverse value found relative to an unlimited-precision inverse can be kept close to the inherent error in the implementation's number format.

-- cgit v1.2.3