documentation.md (1312198) - rtensor

documentation.md

# RTensor documentation (for v2.1)

*RTensor: the sixth-best formula calculator in the world*

RTensor (previously known as VeCalc, and originally as maths_parser) refers to a set of programs:
1. a parser for a maths-oriented programming language (called "RTensor", or "the RTensor language")
2. an interpreter for the RTensor language
3. an HTML-targeting maths typesetter, using the RTensor language as an input syntax
4. a [browser application](#interface) enabling one to run programs in the RTensor language

dkl9 wrote RTensor, starting in 2021-05, and writes this documentation.
For more history, see `./changelog.md`.

# Concepts

## AST

All valid in code in the RTensor language gets parsed into an AST &mdash; an **a**bstract **s**yntax **t**ree.
Internally, the `AST` class (defined in `./maths_ast.js`) represents such an AST.
Each node of the AST either references subnodes (branch nodes, corresponding to [operations](#operators), [function calls](#function-calls), etc) or does not (leaf nodes, corresponding to [primitives](#primitives)).

## Tensor

Consider the following progression:
- **scalar**: a single number (rank 0)
- **vector**: a list of numbers (rank 1)
- **matrix**: a list of lists of numbers (rank 2)

All items in that progression qualify as **tensors** of various **ranks**;
ranks of tensors continue beyond 2 as far as one wants, though ranks from 0 to 2 occur most commonly.

# Interface

Item 4 in the set of RTensor programs more specifically means `./rtensor.xhtml`, which consists of some documentative content, followed by a space for alternating lines of input (text fields, all but the most recent disabled) and output.

## Running code

To run a line of RTensor code, type (or copy, as appropriate) it into the currently available input line and press `Enter`.
You can also use the up and down arrow keys to navigate through the current session's history of previously entered lines.
Whilst not in the RTensor language, you can combine multiple lines of code into one input by joining them with semicolons (`;`).

## Successful output

When no error occurs whilst processing the input code, RTensor will write as output the return value of the code.
Preceding this return value, RTensor indicates a [variable name](#identifiers) (an underscore followed by a serial number) to which it saved that return value.
If the input code consists of multiple semicolon-separated statements, RTensor will evaluate all of the statements, but will only present the return value of the last one, and the serial variable will only receive the return value of the final statement.

RTensor also silently saves the final return value to the variable `_` (underscore), but leaves its previous value if an error occurred.

## Extra output

Some code (such as [syntactic functions](#syntactic-functions)) produces extra output, in varying forms, before the main output.

## Error messages

When an error occurs whilst parsing or evaluating the input code, RTensor will display a relevant error message.
In some cases, this error message comes directly from JavaScript, and therefore starts with a PascalCase error type &mdash; this qualifies as a bug.

If the error occurs during evaluation, RTensor will skip execution of code after the part that triggered the error;
errors propagate up through a program.

For some code (such as `3+`), RTensor successfully parses and evaluates it, but notices that not all of the code corresponds to part of a valid AST, and so in addition to [typical output](#successful-output), RTensor leaves the message "possible syntax error", which *almost always* means "actual syntax error".

# Primitives

## Numeric literals

A numeric literal directly represents a real number (a [scalar](#tensor)), and consists of one or both of an integer component and a fractional component;
Each component consists of digits (in base ten).
The fractional component, if present, must begin with a dot (`.`).
Valid numeric literals include `0`, `389`, `3.14159`, and `.367`.
RTensor currently accepts `.` (just a dot) to mean `NaN`, but you should not rely on this always remaining true.

## Identifiers

An identifier consists of a sequence of letters, digits, underscores, or (unlike most other languages) apostrophes (akin to prime symbols), and does not start with a digit.
When interpreted for code-evaluation, an identifier references a variable, which can hold a value of any type.
Shadowing/[function scope](#evaluation-process) may affect what variable an identifier references.

# Operators

**Operators** combine one or two subexpressions (making the operation **unary** or **binary**, respectively) and express a computation based on the subexpressions.
When the operator combines two subexpressions, it goes between the subexpressions;
when the operator modifies one subexpression, it goes before that subexpression.

Each operator has a **precedence**, which may group it more tightly or loosely than other operators, and each precedence has an **associativity**.
Unary operators have tighter precedence than binary operators, regardless of their relative precedence as binary operators.
You can use parentheses to group operations differently than what their precedence and associativity would ordinarily require.

In descriptions of operators, `a` and `b` represent subexpressions and their results.

## Basic operators

When used on a scalar and a tensor, the result comes from the tensor, with each element replaced by the result of the operation between the scalar and each scalar in the tensor.
For example, `3 * ((7, 2), (-1, 3), (-8, -2))` returns `[[21, 6], [-3, 9], [-24, -6]]`.

When used on two tensors, the result comes from the elementwise combination of the two tensors, or an error if the tensors have different structures.

### Addition (`+`)

`a + b`, the sum of `a` and `b`, or `+a`, an identity operation.
Addition has precedence between multiplication and equality, and associates to the left.

### Subtraction (`-`)

`a - b`, the difference of `a` and `b`, or `-a`, the negative of `a`.
Subtraction has the same precedence as addition, and thus the same associativity.

### Multiplication (`*`)

`a * b`, the product of `a` and `b`.
`*a` will result in an error as meaningless.
Multiplication has precedence between exponentiation and addition, and associates to the left.

### Division (`/`)

`a / b`, the quotient of `a` and `b`, or `/a`, the reciprocal of `a`.
Division has the same precedence as multiplication.

### Exponentiation (`^`)

`a ^ b`, `a` to the power of `b`, or `^a`, the natural exponential function of `a`.
Exponentiation has precedence between logarithms and multiplication, and associates to the right.

### Logarithms (`\`)

`a \ b`, the base-`a` logarithm of `b`, or `\a`, the natural logarithm of `a`.
Logarithms have the tightest precedence of all operators, and associate to the right.

### Equality (`==`)

`a == b`, a boolean value indicating whether or not `a` equals `b`, or `== a`, equivalent to `0 == a`.
Equality has precedence between addition and appending, and associates to the left.

### Radicals (`-/`)

`a -/b`, the `a`-th root of `b`, or `-/a`, the square root of `a`.
Radicals have the same precedence as exponentiation.

Swapping the characters of a radical turns it into `a /-b`, equivalent to `-(a / b)`, or `/-a`, equivalent to `- / a`.

### Comparison (`<`)

`a < b`, a boolean value indicating whether or not `b` exceeds `a`, or `< a`, equivalent to `a < 0`.
Comparison has the same precedence as equality.

You cannot chain comparisons, as in `a < b < c`;
RTensor will interpret that as `(a < b) < c`, which reduces to either `true < c` or `false < c`.

Notice the absence of a `>` operator;
one may implement it by swapping the operands.

## Tensor operators

### Appending (`,`)

The output of `a, b` depends on the relative [rank](#tensor) of `a` and `b`:
- if `a` has greater rank, RTensor appends `b` to the end of `a`, returning a new tensor
- otherwise, RTensor creates a two-element tensor, consisting of `a` and `b` as its elements

These semantics allow one to chain the appending operator (as in `a, b, c, d`) to construct a many-element tensor.

Appending has precedence between equality and the maplet, and associates to the left.

### Concatenation (`..`)

The output of `a .. b` depends on the [ranks](#tensor) of `a` and `b`:
- if `a` and `b` both have ranks exceeding zero, RTensor concatenates `b` to the end of `a`, returning a new tensor
- if `a` and `b` both have ranks which equal zero, RTensor generates a vector by iterating through the numbers from `a` to `b` (inclusive) with a step size of 1
- if one of `a` or `b` has zero rank, and the other does not, `a .. b` results in an error as meaningless

`.. a` encapsulates `a` as a one-element tensor, effectively incrementing the rank without adding any new data.

When using the concatenation operator, carefully distinguish it from a decimal point;
e.g. `3..5` will result in an error, unlike the valid options `3.5` and `3 .. 5`.

Concatenation has the same precedence as addition.

## Unusual operators

### Maplet (`=>`)

The maplet operation, `a => b`, constructs an [anonymous function](#anonymous-functions).
`a` may consist of a comma-separated list, each of which corresponds to a separate argument for the function;
it gets tranlated into a [pattern](#pattern-matching), but syntactically forms as an expression.
`b` must consist of some expression, possibly using variables defined in `a`.

The maplet has precedence between appending and assignment, and associates to the right.

### Assignment (`=`)

The assignment operation, `a = b`, saves the value from `b` into the location described by `a`, and returns the new value of `a` (or something closely related to `a`, with semantics that remain undocumented).
`a` may consist of an [identifier](#identifiers) &mdash; in which case, `b` replaces the value already stored in that variable.
`a` may have a [function call](#function-calls) or [index](#indexing) suffix (the two have the same form):
- if `a` already references a [function](#function-definitions), the assignment adds a new case (the [pattern](#pattern-matching) consisting of the argument list, the expression coming from `b`) to that function (at top priority)
- if `a` already references a [tensor](#tensor), the assignment replaces the element at the given index with the value of `b`, or [causes an error](#error-messages) if `a` does not already contain an element at that index
- if `a` does not reference anything, or references a scalar, the assignment replaces the value with a new function, adding a single case as if `a` already referenced a function

Assignment has the loosest precedence of all operators, and associates to the right.

# Indexing

An expression suffixed with a parenthesised expression (`v(i)`) forms an **indexing expression** (or a [function call](#function-calls), depending on `v`);
if `v` references a tensor, the index expression returns the `i`th element of `v` (a tensor of [rank](#tensor) at most one less than that of `v`).
Indexing in RTensor starts at 1 and not 0.
Attempts to access `v(i)` where `i` exceeds the length of `v`, `i` does not equal an integer, or `i` subceeds 1 will [cause an error](#error-messages).

The `i` component of the indexing expression can include extra comma-separated indices, but RTensor currently ignores all indices after the first.

# Function calls

An expression suffixed with a parenthesised expression-list (`f(a, b, c, ...)`) forms a **function call** (or an [indexing expression](#indexing), depending on `f`);
if `f` references a [function](#function-definitions), the function call returns the value `f` provides when evaluated with the given argument list.
The argument list may contain any number of arguments, including 0.

Whilst [`,` normally acts as an operator](#appending-), the argument-list syntax suppresses this behaviour;
when in an argument list, `,` only acts as an operator if it occurs in parentheses (as in the first argument of `f((a, b), c)`), and operators with precedence looser than that of `,` will not work at all unless parenthesised.

## Evaluation process

When evaluating a function, RTensor first evaluates all the arguments, then searches for a [pattern](#pattern-matching) (going in descending priority) that matches the arguments.
If RTensor could not find a matching pattern, an [error occurs](#error-messages).
Upon finding a matching pattern, RTensor evaluates the expression or internal function corresponding to that pattern in the function's [definition](#function-definitions), using the argument-name correspondences given from the pattern to create local variables for that expression.

# Function definitions

**Functions**, as objects in RTensor (or **function definitions**), consist of a list (arranged by priority) of [pattern](#pattern-matching)-expression pairs, or **cases**.
Some functions ([those predefined by the code which sets up RTensor](#built-in-functions)) have, in place of an expression defined from RTensor, a function in the language implementing RTensor.

## Pattern matching

A **pattern** consists of a list of zero or more **parameters**.
A parameter consists of either an [identifier](#identifiers) or some other expression:
- in the former case, that parameter matches any value, and will require RTensor to create a local variable with that name to store that value, *even if a variable defined in a scope further out already exists with that name*
- in the latter case, RTensor evaluates the expression (at the time of case-creation), using only variables defined in a scope further out than the [function evaluation](#evaluation-process);
    that parameter matches only values considered equal to the result of the expression

When checking if a pattern matches a list of arguments, the arguments get aligned to the parameters;
if the number of arguments differs from the number of parameters, the pattern does not match without any further checks.

To make a parameter that matches only values which equal an existing variable, wrap the variable identifier in an identity (such as `x + 0` or `x * 1`).

RTensor currently does not provide pattern-matching mechanisms more complex than equality checks against constant values;
you must do so yourself with [explicit checks](#control-flow).

## Anonymous functions

RTensor provides both an [assignment-based syntax](#assignment-) and an anonymous [maplet-based syntax](#maplet-) for defining functions.
The former works with (named) variables, but the latter constructs a function without saving it to a variable (anonymous).
A maplet operation takes its left operand as a [pattern](#pattern-matching) and its right operand as an unevaluated sub-expression, constructing and returning a single-[case](#function-definitions) function, usable in the same contexts as any other function.

In that single case's expression, one can use variables defined in the scope which defines the anonymous function, creating a sort of closure.

If the left operand has [commas](#appending-), RTensor will break it down into a list of patterns, allowing for more than one parameter, rather than a single pattern.

### Currying

Using closures, one can make multi-argument anonymous functions a different way: make a function that returns another function, as a partially-evaluated form of the desired multi-argument function &mdash; for example, `x => (y => x + y)` instead of `x, y => x + y`.
RTensor does not have a special syntax to facilitate the requisite chained method calls, so one would use the curried version not as `f(a, b)` but `f(a)(b)`.

# Built-in functions

The RTensor [browser application](#interface) includes `rtensor_lib.js`, which predefines a set of functions.

In descriptions of functions, identifiers [in parentheses](#function-calls) correspond to arguments for valid ways to call a function.
The exact identifier used indicates the expected type:
- `a`, `b`, `c`: number (in some contexts, specifically integer)
- `f`, `g`: function
- `k`, `m`, `n`: integer
- `t`: tensor (any rank above 0)
- `v`: vector ([rank 1 tensor](#tensor))
- `x`, `y`: number ([rank 0 tensor](#tensor))
- `w`, `z`: any type

Some functions work on a tensor, but only look one rank deep, using the tensor in place of a vector.
In this case, the parameter uses `t` for the identifier.

## Numeric/trigonometric functions

All functions in this list that accept a real number (so not `random`) will accept, in place of that number, a tensor, and will perform the same operation on each number in the tensor, returning an equivalently-structured tensor.

### `abs`

`abs(x)`, the absolute value of `x`.

### `floor`

`floor(x)`, the integer rounded down (towards negative infinity) from `x`.

### `random`

`random()`, a random number in `[0, 1)`, or `random(m, n)`, a random integer in `[m, n]`.

### `sin`

`sin(x)`, the trigonometric sine of `x`.

### `cos`

`cos(x)`, the trigonometric cosine of `x`.

### `arcsin`

`arcsin(y)`, the trigonometric inverse sine of `y`.

### `arccos`

`arccos(y)`, the trigonometric inverse cosine of `y`.

### `arctan`

`arctan(y)`, the trigonometric inverse tangent of `y`, or `arctan(y, x)`, the plane angle between `(0, 0)` and `(x, y)`.

The corresponding `tan(x)` does not exist predefined in RTensor, but one can implement it as `tan(x) = sin(x) / cos(x)`.

## Tensor functions

### `zero`

`zero(n)`, an `n`-element vector of zeroes.
`zero` accepts `0` as an argument, producing, in that case, a zero-element vector.

### `len`

`len(t)`, the number of elements in the top level of `t`.
This does not count the number of numbers in `t`, but merely the number of [tensors of lesser rank](#tensor) immediately composing `t`.
For example, `len(((4, 7), (2, 3), (8, 5)))` return 3 rather than 6.

### `any`

`any(v)`, the first nonzero value in `v`.
If `v` consists of [`true`/`false` values](#booleans-true-and-false), this functions as an inclusive OR.

### `all`

`any(v)`, the first zero-equivalent value in `v`.
If `v` consists of [`true`/`false` values](#booleans-true-and-false), this functions as an AND.

### `map`

`map(t, f)`, a new [tensor (same rank as `t`, greater than 0)](#tensor) with each element `x` from `t` (in the top level) replaced [with `f(x)`](#function-calls).
If `f` accepts two arguments (binary function), `map` will replace `x` with `f(x, i)`, where `i` matches the index of `x` from `t`.
If `f` does not accept any arguments (nullary function), `map` will replace `x` with `f()`.

Notice that `map` *only* acts on top-level elements;
e.g. `map(((4, 7), (2, 3), (8, 5)), f)` applies `f` to `(4, 7)`, `(2, 3)`, and `(8, 5)`, not `4`, `7`, `2`, `3`, `8`, `5`.
To apply a function to replace *every number* in a tensor, [use `deepmap`](#deepmap).

### `filter`

`filter(t, f)`, a new [tensor (same rank as `t`, greater than 0)](#tensor) containing all elements `x` from `t` (in the top level) [for which `f(x)`](#function-calls) returns a value equivalent to [`true`](#booleans-true-and-false).
If `f` accepts two arguments (binary function), `filter` will copy `x` for which `f(x, i)` returns a value equivalent to `true`, where `i` matches the index of `x` from `t`.

As with [`map`](#map), `filter` *only* acts on top-level elements.
RTensor currently does not have any `deepfilter` to check `f(x)` for every number in a tensor.

### `reduce`

`reduce(t, f)`, a value computed by repeatedly applying `x = f(x, y)` for each element `y` of `t` (at the top level).
The initial value of `x` comes from the first element of `t`;
`reduce` does not apply `f(x, y)` using that initial value for `y`.

As with [`map`](#map), `reduce` *only* acts on top-level elements.
RTensor currently does not have any `deepreduce` to combine all individual numbers in a tensor.

### `tail`

`tail(t)`, a new tensor consisting of all the elements of `t`, in the same order, except for the first.

### `trim`

`trim(t)`, a new tensor consisting of all the elements of `t`, in the same order, except for the last.

### `deepmap`

`deepmap(t, f)`, a new tensor with the same structure as `t`, but with every number `x` (down through all ranks) replaced with `f(x)`.

## Control flow

### `if`

`if(c, w, z)`, a selection between `w` and `z` depending on `c`, selecting `w` iff `c` [equates to `true`](#booleans-true-and-false).
`if` accepts up to two extra arguments to automatically apply to the selected value as arguments (assuming that value [has callable behaviour](#function-calls)).
For more than two arguments (and recommended in general, as we may deprecate that feature), we suggest directly calling the result instead, as in `if(c, w, z)(a, b, x, y)`.

### `for`

`for(init, cond, step)`, the final value of `x` &mdash; which starts as `x = init` &mdash; after repeatedly applying `x = step(x)`, until `cond(x)` returns a value [equivalent to `false`](#booleans-true-and-false).

## Other built-in functions

### `clear`

`clear()`, which clears away all the content in the input/output area (but keeps variables and input history), returning 0.

# Other built-ins

RTensor predefines some values other than functions in `rtensor_lib.js`.
These include:
- `pi`, Archimedes' constant, approximately 3.14
- `phi`, the golden ratio, approximately 1.62
- `true`, the affirmative boolean value (distinct from, but usually equivalent to, 1)
- `false`, the negative boolean value (distinct from, but usually equivalent to, 0)
- `null`, a unique null value

This set does *not* include Euler's number `e` (approximately 2.72);
one can already [get it as `^1`](#exponentiation-).

# Typesetting/rendering

Item 3 in the set of RTensor programs &mdash; the HTML-targeting maths typesetter &mdash; consists of a set of functions that convert [valid RTensor ASTs](#ast) into HTML text, intended to use styling from `maths.css`.

## RTensor typesetting as a library

An outside HTML/JavaScript program (such as mdprocess) that includes the right files:
- `maths_parser.js`
- `maths_ast.js`
- `mathsfunc.js`
- `rtensor_lib.js`
- `rtensor_to_html.js`
- `maths.css`

... can get typeset HTML through `ast.toHTML()` for an `AST` object `ast`.
For example:
```js
const p = document.createElement("p");
const l = new TokenStream("x = (-b + pm(-/(b^2 - 4*a*c))) / (2*a)");
const a = NewParser.statement(l);
p.innerHTML = a ? a.toHTML() : "syntax error";
document.body.appendChild(p);
```

## RTensor typesetting in the interface

The [RTensor browser interface](#interface) provides two built-in functions in `rtensor_lib.js` to access this typesetting feature.
Both functions [act on syntax](#syntactic-functions).

### `html`

`html(e)`, which places HTML text depicting `e` provided by `ast.toHTML()` into the output area (as plaintext), returning 0.

### `render`

`render(e)`, which places a rendering of `e` provided by `ast.toHTML()` into the output area, returning 0.

# Syntactic functions

Some functions act on syntax rather than values;
i.e. they interpret each argument as an [AST](#ast) without evaluating it, rather than a [tensor](#tensor) or similar ordinary value.

Some operators (specifically, [appending](#appending) and all looser operators) have looser precedence than the parentheses and commas [of function call syntax](#function-calls), so syntactic arguments using such operators must have delimiting parentheses.

## `tostring`

`tostring(e)`, which places an unambiguous form of `e` into the output area, returning 0.

# Examples

You can paste any of these examples into the [RTensor application](#interface) (line-by-line) to test them.

## Numerical error

```rtensor
(-/10)^2 == 10
```

In the current implementation, this will return `false`, because RTensor &mdash; based upon JavaScript &mdash; uses the imperfect 64-bit floating point system.

## Local variables

```rtensor
f(x) = (\x)^2 + \x
f(x) = (a => a^2 + a)(\x)
f(x) = (a = \x) + a^2
f(x) = (a = \x)*0 + (a^2 + a)
```

All of these functions give the same output:
- the first computes `\x` twice
- the second caches `\x` into a local variable by calling an inner function
- the third stores `\x` into a local variable without a new function
- the fourth discards the result of the assignment, demonstrating a method that works in more general cases

## Factorial, several ways

```rtensor
fact(n) = n * fact(n - 1)
fact(1) = 1

fact(n) = n * if(n == 1, (_x => 1), fact)(n - 1)

((f => (n => (if(n==1,(_=>1),f(f)))(n-1) * n))(
    (f => (n => (if(n==1,(_=>1),f(f)))(n-1) * n)))
)(6)
```

The first pair of assignments creates a function, `fact`, which returns the factorial of a positive integer by recursion.
Swapping the assignments would make the function incorrect;
functions try cases [in reverse order of their definition](#evaluation-process), stopping at the first one that works.

The second assignment implements `fact` recursively, using [`if`](#if) instead of [pattern matching](#pattern-matching).

The final expression uses a Y combinator-like construct and [anonymous functions](#anonymous-functions) to evaluate a factorial recursively without assigning to a variable.

## Ackermann function

```rtensor
A(m, n) = A(m - 1, A(m, n - 1))
A(m, 0) = A(m - 1, 1)
A(0, n) = n + 1
```

Beware that with arguments greater than `A(3, 3)`, this will run very slowly.
Observe that with RTensor's [pattern matching](#pattern-matching), the implementation of the function looks almost identical to [the theoretical definition](https://en.wikipedia.org/wiki/Ackermann_function).

## `Rtensor:Psi` bump function

```rtensor
psi(x) = if(all((-1 < x, x < 1)), ^/-(1 - x^2), 0)
```

An implementation of the [psi bump function](https://en.wikipedia.org/wiki/Bump_function#Examples), again remarkably close to the theoretical definition, and even closer when [presented with `render`](#render).

## Vector dot product

```rtensor
dot(u, v) = u(1) * v(1) + dot(tail(u), tail(v))
dot(zero(0), v) = 0
dot(u, zero(0)) = 0
```

## List of prime numbers

```rtensor
div(a, b) = floor(a / b) == a / b
fp(n, l) = ==len(filter(l, (k => div(n, k))))
last(v) = v(len(v))
fnp(n) = trim(for(
    .. 2,
    (v => len(v) < n + 1),
    (v => if(fp(last(v), trim(v)), (v, last(v)), (trim(v), last(v) + 1)) )
))
fnp(30)
```

`div(a, b)` checks if `b` divides `a`.

`fp(n, l)` checks if `n` has no divisors in `l`.

`last(v)` returns the last element of `v`.

`fnp(n)` uses a [`for` loop](#for) to increment a potential prime and append any actual primes to a list, until the list has the desired length `n`.

## Integer factorisation

```rtensor
div(a, b) = floor(a / b) == a / b
factor(n, g) = if(div(n, g), ..g, zero(0)) ..
    factor(if(div(n, g), n / g, n), if(div(n, g), g, g + 1))
factor(1, g) = zero(0)
factor(n) = factor(floor(n), 2)
```

The `factor(n, g)` function recursively builds up a vector of prime factors of `n`, based on the principle that if `n` has the factor `g`, the factorisation of `n` matches that of `n / g`, except for the addition of `g`.

## Fibonacci sequence

```rtensor
cond(state) = len(state) < 20
next(st) = st, (st(len(st)) + st(len(st) - 1))
for((1, 1), cond, next)
```

## Quicksort

```rtensor
qs(v) = qs(filter(tail(v), (x => x < v(1)))) ..
    (.. v(1)) ..
    qs(filter(tail(v), (x => 1 - (x < v(1)))))
qs(zero(0)) = zero(0)
tv = map(zero(30), (_x => random(1, 100)))
qs(tv)
```

Quicksort sorts a list by recursively collecting elements less than and greater than a pivot into sublists on each side of the pivot, and quicksorting each such sublist, until the process reaches lists of length 0.

This implementation consistently uses the first element of a list as its pivot.

## Hofstadter Q-sequence

```rtensor
a(n) = a(n-a(n-1)) + a(n-a(n-2))
a(1) = 1
a(2) = 1

Qs(v) = v, (v(len(v) + 1 - v(len(v))) + v(len(v) + 1 - v(len(v) - 1)))
Qc(v) = len(v) < 100
for((1, 1), Qc, Qs)
```

The first implementation provides a recursive function to compute any term of the Q-sequence.
This runs very slowly.

The second implementation iteratively generates a list of Q-sequence terms, running much faster.

## Polynomial operations

Each function here works with a polynomial as a little-endian vector of coefficients;
e.g. `(-2, 5, 6)` represents `Rtensor:6*x^2 + 5*x - 2`.

Evaluate a polynomial at an input value by multiplying each coefficient with the corresponding power of the input and summing the results:

```rtensor
pe(x, p) = reduce(map(p, (t, i => t * x^(i - 1))), (a, b => a + b))
```

Differentiate a polynomial (into another polynomial) by multiplying each coefficient by its exponent and shifting all elements down by one:

```rtensor
pd(p) = tail(map(p, (x, i => (i - 1) * x)))
```

Find a root of a polynomial near a given value with Newton's method by subtracting function values divided by derivatives until the approximation matches a zero:

```rtensor
rnr(v) = 1 - ==pe(v(1), v(2))
nrs(v) = (v(1) - pe(v(1), v(2)) / pe(v(1), pd(v(2)))), v(2)
pr(x, p) = (for((x, p), rnr, nrs))(1)
```

## Digits of an integer

```rtensor
digits(n, b) = digits(floor(n / b), b), (n - b * floor(n / b))
digits(0, b) = zero(0)
```

As with [the factoring algorithm](#integer-factorisation), this function works by recursively building up a vector, acting on reduced versions of the input until the input reaches zero.

## Summation

RTensor currently does not provide a built-in summation function, but that doesn't matter;
we can implement it.

```rtensor
sum(a, b, f) = sum(0, b - a, (x => f(x + a)))
sum(0, b, f) = f(b) + sum(0, b - 1, f)
sum(0, 0, f) = f(0)
```

## Euclid's algorithm (GCD)

RTensor currently does not provide a built-in, modulo function, but that doesn't matter;
we can implement it.

```rtensor
mod(a,b) = a - b * floor(a / b)
gcd(m, n) = gcd(n, mod(m, n))
gcd(m, 0) = m
```

rtensor

Import v2.3-dev from a demonic ritual