Lorry

Lorry

Lorry is a minimalistic programming language operating via a head on a tape of non-negative integers. It gets its name from the unique feature that the head (the conceptual lorry) also has an associated non-negative integers which is decreased on instructions that move the head or enter an iteration of a loop (conceptual fuel consumption). These instructions are not performed if the value of the head is zero, being the only way of implementing conditionals in the language.

Setup

A lorry program operates via a pointer (called the lorry) on an infinite, one-sided tape of memory cells (called depots) holding non-negative integers. The depots are all initially empty, except for the first one, which (always) contains an infinite amount of fuel. The lorry, starting at the first depot, also has an associated non-negative integer (its tank), initially 0 as well.

Execution

A valid lorry program is any finite string consisting of the characters

> < + - [ ]

where the brackets are matching. To execute a lorry program, the characters are read one by one, starting at the left end. Each character corresponds to different instruction, which might depend on the fuel level (and position) of the lorry:

> : if the tank is not empty, move the lorry one step to the right and remove 1 from the tank
< : if the tank is not empty (and the lorry is not at the first depot), move the lorry one step to the left and remove 1 from the tank
+ : if the tank is not empty, move 1 from the tank to the current depot
- : if the current depot is not empty, move 1 from the current depot to the tank
[ : if the tank is empty, jump ahead in the program to the matching closing bracket, else remove 1 from the tank 
] : if the tank is not empty, jump back in the program to the matching opening bracket and remove 1 from the tank

The program halts when the end of he string is reached.

Input and output

We index the depots by the non-negative integers. A lorry program can take as input a sequence of non-negative integers, which determine the initial values of the first few depots after depot 0. The output of a halting lorry program are the (first few) final values of the depots, excluding depot 0.

Computational power

With a few simple observations it is easy to show that any program for a register machine can be translated into an equivalent lorry program. It follows that lorry is Turing complete.

Examples

Lorry program that computes the function f(x,y) = x+y:

-[----->>-<+<]->-<