The Cairn-Liturgy of Hesketh Tor

Commission of the Cairnwardens of Hesketh Tor. On the bare summit of Hesketh Tor the cairnwardens raise warding-cairns to a written liturgy. Each cairn is a stack of carved tallies, and each word of the liturgy adds a tally or reshapes the top of the cairn. Wardens may also *teach* the liturgy new words partway through. The Cairnwardens pay any reckoner who can read a liturgy and report the cairn it leaves standing, or report that the cairn collapses.

Write cairnChant(chant). chant is a string. Return the final cairn as an array of integers listed bottom to top, or null (None in Python) if the chant is invalid.

Tokens. Read chant left to right: - A space separates tokens and is otherwise ignored. Spaces are optional between tokens: 12+3 is three tokens, and 3dup is two. - A maximal run of digits 0-9 is a number token with its decimal value. Leading zeros are allowed, so 007 is 7. There are no negative literals: - is always the subtraction token. - A maximal run of lowercase letters a-z is a word token. - Each of + - * / : ; is a token on its own. - Any other character, including uppercase letters, tabs and newlines, makes the chant invalid.

The cairn is a stack of integers, empty at the start. Tokens outside definitions are run in order: - A number pushes its value. - +, -, * and / pop the top value b, then the next value a. They push a + b, a - b, a * b, or a / b rounded toward zero. For example, -7 / 2 is -3 and 7 / -2 is -3. - Built-in words: - dup pushes a copy of the top value. - drop removes the top value. - swap exchanges the top two values. - over pushes a copy of the second value from the top. - A defined word runs its stored body.

Definitions. The token :, followed by a word token NAME, then any tokens, then ;, defines NAME. A definition does not change the cairn, and its body is not run when it is defined. The body may be empty.

When the ; is reached, the body is fixed. Each word in it is replaced by the meaning that word has at that moment: either a built-in, or the stored body of an earlier definition. Later definitions never change a body that is already stored.

NAME may be any word, including the name of a built-in or of an earlier definition. After the ;, NAME means the new body and overrides the older meaning. Inside its own body, however, NAME still has its previous meaning.

Invalid chants. The chant is invalid, and you return null / None, if any of the following occurs: - a forbidden character appears; - a : is not immediately followed by a word token; - a : appears inside a definition; - a definition has no closing ;; - a ; appears outside a definition; - a word is neither a built-in nor currently defined, either when it is run outside a definition or when a body containing it is fixed; - an operator or built-in is run while the cairn holds fewer values than it needs. Operators, swap and over need two values; dup and drop need one; - / is run with b equal to 0.

A division by zero or a shortage of values inside a body matters only if that body is actually run. Every value in the tests stays well within the safe integer range.