PricK
| Paradigm(s) | Concatenative |
|---|---|
| Designed by | User:Olus2000 |
| Appeared in | 2023 |
| Memory system | Stack-based |
| Computational class | Total, primitive recursive |
| Reference implementation | Python |
| Influenced by | BlooP |
| File extension(s) | .prick |
PricK is a minimalistic stack language equivalent in power to primitive recursive functions. Its only looping construct is a bounded loop, which makes sure every PricK program always terminates on any input, making it a total language. It was designed to prove that a bounded loop language can be capable of interpreting itself.
Language overview
PricK's memory consists of an unbounded stack and an unbounded random access memory, both capable of holding natural numbers which are the sole data type in the language. Like most concatenative languages it has very simple syntax based on whitespace-separated tokens:
<program> ::= <definition> <program> | <body> <definition> ::= <body> ':' <identifier> <body> ::= <empty> | <identifier> <body> | <loop> <body> <loop> ::= '[' <body> '|' <body> ']'
Body of the program is the one after the last definition.
PricK memory is initialised with zeros, and PricK stack yields zeros when empty so it can also be viewed as initialised with infinite zeros.
Words
Valid identifiers are all non-whitespace strings other than :, [, | and ]. Some identifiers initially correspond to builtin functions:
| Identifier | Operation |
|---|---|
@
|
Replace the number at the top of the stack with the contents of the cell at that address |
!
|
Pop an address and a value from the stack and set the contents of the cell at that address to that value |
#
|
Push a zero to the stack |
++
|
Increment number at the top of the stack |
Loops
The main means of flow control in PricK are bounded while loops. They consist of two code blocks: predicate (between [ and |) and body (between | and ]). Execution of a loop proceeds as follows:
0. One number is popped from the stack and set as the loop's bound;
1. Predicate is executed;
2. One number is popped from the stack as a condition for step 3;
3. If either the condition or the bound is zero execution continues after the loop;
4. Otherwise the body is executed;
5. Bound is decremented and loop execution continues from step 1.
Definitions
Definition is a body followed by an identifier assignment with :. Code following a definition can use the assigned identifier to call the body of the definition. The body of a definition isn't available under any identifier to itself or the code before it, making it impossible to use recursion which would break the bounded loop restriction. Definitions may redefine identifiers, including the builtin identifiers @, !, # and ++, but not syntax elements :, [, | and ] (though these characters are allowed as parts of longer identifiers).
Computational class
PricK is Total and its programs are equivalent to primitive recursive functions.
BlooP translation
PricK's computational class can be shown by showing its equivalence to BlooP. Unlike for Turing Complete languages a translation both ways is required to prove equivalence.
PricK to BlooP
The main hardship in this part is to encode the potentially infinite memory and stack in BlooP, which only allows storage in cells that are explicitly mentioned in code. Fortunately the cells are unbounded, so it is possible to encode series of values as a product of powers of primes, and pairs of numbers using a pairing function.
DEFINE PROCEDURE ''MINUS'' [M,N]:
BLOCK 0: BEGIN
LOOP AT MOST M TIMES:
BLOCK 1: BEGIN
IF NOT OUTPUT + N < M, THEN:
ABORT LOOP 1;
OUTPUT <= OUTPUT + 1;
BLOCK 1: END;
BLOCK 0: END.
DEFINE PROCEDURE ''DIVISIBLE?'' [M,N]:
BLOCK 0: BEGIN
CELL(0) <= 0;
LOOP AT MOST M TIMES:
BLOCK 1: BEGIN
IF NOT CELL(0) < M, THEN:
ABORT LOOP 1;
CELL(0) <= CELL(0) + N;
BLOCK 1: END;
IF CELL(0) = M, THEN:
BLOCK 1: BEGIN
OUTPUT <= YES;
BLOCK 1: END
BLOCK 0: END.
DEFINE PROCEDURE ''DIV'' [M,N]:
BLOCK 0: BEGIN
CELL(0) <= 0;
LOOP AT MOST M TIMES:
BLOCK 1: BEGIN
IF CELL(0) + N > M, THEN:
ABORT LOOP 1;
CELL(0) <= CELL(0) + N;
OUTPUT <= OUTPUT + 1;
BLOCK 1: END;
BLOCK 0: END.
DEFINE PROCEDURE ''GET'' [ENCODED,PRIME]:
BLOCK 0: BEGIN
CELL(0) <= ENCODED;
LOOP AT MOST ENCODED TIMES:
BLOCK 1: BEGIN
IF NOT DIVISIBLE? [CELL(0),PRIME], THEN:
ABORT LOOP 1;
CELL(0) <= DIV [CELL(0),PRIME];
OUTPUT <= OUTPUT + 1;
BLOCK 1: END;
BLOCK 0: END.
DEFINE PROCEDURE ''POW'' [M,N]:
BLOCK 0: BEGIN
OUTPUT <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
OUTPUT <= OUTPUT * M;
BLOCK 1: END;
BLOCK 0: END.
DEFINE PROCEDURE ''SQRT'' [N]:
BLOCK 0: BEGIN
LOOP AT MOST N TIMES:
BLOCK 1: BEGIN
IF (OUTPUT + 1) * (OUTPUT + 1) > N, THEN:
ABORT LOOP 1;
OUTPUT <= OUTPUT + 1;
BLOCK 1: END;
BLOCK 0: END.
The stack can be represented as a cons list, with head (top of stack) and rest (stack without the top) encoded using Szudzik's ElegantPair function.
DEFINE PROCEDURE ''REST'' [STACK]:
BLOCK 0: BEGIN
OUTPUT <= SQRT [STACK];
CELL(0) <= MINUS [STACK,OUTPUT * OUTPUT];
IF NOT CELL(0) < OUTPUT, THEN:
BLOCK 1: BEGIN
OUTPUT <= MINUS [CELL(0),OUTPUT];
BLOCK 1: END
BLOCK 0: END.
DEFINE PROCEDURE ''TOP'' [STACK]:
BLOCK 0: BEGIN
OUTPUT <= SQRT [STACK];
CELL(0) <= MINUS [STACK,OUTPUT * OUTPUT];
IF CELL(0) < OUTPUT, THEN:
BLOCK 1: BEGIN
OUTPUT <= CELL(0);
BLOCK 1: END
BLOCK 0: END.
DEFINE PROCEDURE ''PUSH'' [STACK,ELT]:
BLOCK 0: BEGIN
OUTPUT <= STACK + ELT + ELT * ELT;
IF ELT < STACK, THEN:
BLOCK 1: BEGIN
OUTPUT <= (STACK * STACK) + ELT;
BLOCK 1: END
BLOCK 0: END.
Memory can be encoded as a product of powers of primes, with nth prime encoding nth cell and 0th prime being 2. The hard part of this is to find the nth prime, which the following code accomplishes naively by checking each number up to (n+2)^2 for primality and taking the nth one of those. This is a very generous upper bound based on the one listed on wikipedia.
DEFINE PROCEDURE ''PRIME?'' [N]:
BLOCK 0: BEGIN
CELL(0) <= 2;
LOOP AT MOST N TIMES:
BLOCK 1: BEGIN
IF DIVISIBLE? [N,CELL(0)], THEN:
QUIT BLOCK 0;
IF CELL(0) * CELL(0) > N, THEN:
ABORT LOOP 1;
CELL(0) <= CELL(0) + 1;
BLOCK 1: END;
OUTPUT <= YES;
BLOCK 0: END.
DEFINE PROCEDURE ''NTH-PRIME'' [N]:
BLOCK 0: BEGIN
CELL(0) <= 0;
OUTPUT <= 2;
LOOP AT MOST (N + 2) * (N + 2) TIMES:
BLOCK 1: BEGIN
IF NOT CELL(0) < N, THEN:
ABORT LOOP 1;
OUTPUT <= OUTPUT + 1;
IF PRIME? [OUTPUT], THEN:
BLOCK 2: BEGIN
CELL(0) <= CELL(0) + 1;
BLOCK 2: END
BLOCK 1: END;
BLOCK 0: END.
DEFINE PROCEDURE ''GET-AT'' [MEMORY,INDEX]:
BLOCK 0: BEGIN
OUTPUT <= GET [MEMORY,NTH-PRIME [INDEX]];
BLOCK 0: END.
DEFINE PROCEDURE ''SET'' [MEMORY,INDEX,VALUE]:
BLOCK 0: BEGIN
OUTPUT <= DIV [MEMORY,POW [NTH-PRIME [INDEX],GET-AT [MEMORY,INDEX]]]
* POW [NTH-PRIME [INDEX],VALUE];
BLOCK 0: END.
With all of this out of the way a translation can be defined. Cells 0 and 1 will hold stack and memory respectively. Cell 2 will be used for a stack of loop bounds. User-defined words will be called with these as arguments, and return a pairing of memory and stack.
| Feature of PricK | Translation to BlooP |
|---|---|
Definition of word x
|
DEFINE PROCEDURE ''x'' [STACK,MEMORY]:
BLOCK 0: BEGIN
CELL(0) <= STACK;
CELL(1) <= MEMORY;
CELL(2) <= 0;
...
OUTPUT <= PUSH [CELL(1),CELL(0)];
BLOCK 0: END.
|
| Main body of the program | DEFINE PROCEDURE ''UNUSED-IDENTIFIER'' [STACK,MEMORY]:
BLOCK 0: BEGIN
CELL(0) <= STACK;
CELL(1) <= MEMORY;
CELL(2) <= 0;
...
OUTPUT <= PUSH [CELL(1),CELL(0)];
BLOCK 0: END.
|
Call to a user-defined word x
|
CELL(3) <= x [CELL(0),CELL(1)]; CELL(0) <= TOP [CELL(3)]; CELL(1) <= REST [CELL(3)]; |
Call to builtin @
|
CELL(3) <= TOP [CELL(0)]; CELL(0) <= REST [CELL(0)]; CELL(3) <= AT [CELL(1),CELL(3)]; CELL(0) <= PUSH [CELL(0),CELL(3)]; |
Call to builtin !
|
CELL(3) <= TOP [CELL(0)]; CELL(0) <= REST [CELL(0)]; CELL(4) <= TOP [CELL(0)]; CELL(0) <= REST [CELL(0)]; CELL(1) <= SET [CELL(1),CELL(3),CELL(4)]; |
Call to builtin #
|
CELL(0) <= PUSH [CELL(0),0]; |
Call to builtin ++
|
CELL(0) <= PUSH [REST [CELL(0)],TOP [CELL(0)] + 1]; |
[ .pred. | .body. ]
|
CELL(2) <= PUSH [CELL(2),TOP [CELL(0)]];
CELL(0) <= REST [CELL(0)];
.pred.
CELL(3) <= TOP [CELL(0)];
CELL(0) <= REST [CELL(0)];
CELL(4) <= TOP [CELL(2)];
CELL(2) <= REST [CELL(2)];
LOOP AT MOST CELL(4) TIMES:
BLOCK N: BEGIN
IF CELL(3) = 0, THEN:
ABORT LOOP N;
.body.
.pred.
CELL(3) <= TOP [CELL(0)];
CELL(0) <= REST [CELL(0)];
BLOCK N: END;
|
This completes the first half of the proof: BlooP is at least as powerful as PricK.
BlooP to PricK
For the sake of this translation availability of all extensions mentioned in the Language Extensions section is assumed, that is: stack shuffling and math primitives, decimal number support, and auxiliary stack. Main hardship in this part is handling the arbitrary breaking out of loops and blocks. To do that each bock, loop, and if will return a status output of 0 or N 1 indicating that it should break out of block N. Then the rest of the code after the block will be executed or not based on the status output.
Because each procedure in BlooP uses a predefined amount of CELLs and an OUTPUT variable, it is possible to assign each of them a base offset such that ranges [base,base+max_cell_num+1] don't overlap for any two procedures. This allows allocation of PricK memory cells to those variables in a way that never has to be saved because no two procedures overlap and a procedure can't call itself.
| Feature of BlooP | Translation to PricK |
|---|---|
DEFINE PROCEDURE ''X'' [ARG1,ARG2,...,ARGN]:
BLOCK M: BEGIN
.body.
BLOCK M: END.
|
N [ 1 | >aux ] 0 base ! 0 .body. 1 [ | drop 0 ] base @ N [ 1 | aux> drop ] : X |
IF EXPR, THEN:
BLOCK N: BEGIN
.body.
BLOCK N: END
.after.
|
1 [ EXPR | .body. ] 1 swap 1 [ | drop dup N != 1 swap 1 [ | 0 0 0 ] swap drop 0 ] 1 [ | 0 .after. 0 ] |
LOOP AT MOST EXPR TIMES:
BLOCK N: BEGIN
.body.
BLOCK N: END;
.after.
|
EXPR
[ 1 swap 1 [ | drop dup N !=
dup 1 [ | 0 swap 0 ] swap drop 0 0 ]
| 0 .body. ]
1 swap 1 [ | drop dup N !=
1 swap 1 [ | 0 0 0 ] swap drop 0 ]
1 [ | 0 .after. 0 ]
|
LOOP EXPR TIMES:
BLOCK N: BEGIN
.body.
BLOCK N: END;
.after.
|
EXPR
[ 1 swap 1 [ | drop dup N !=
dup 1 [ | 0 swap 0 ] swap drop 0 0 ]
| 0 .body. ]
1 swap 1 [ | drop dup N !=
1 swap 1 [ | 0 0 0 ] swap drop 0 ]
1 [ | 0 .after. 0 ]
|
IF EXPR, THEN: QUIT BLOCK N; .after. |
1 [ EXPR | drop N 1 ] 1 swap 1 [ | 0 0 ] 1 [ | 0 .after. 0 ] |
IF EXPR, THEN: ABORT LOOP N; .after. |
1 [ EXPR | drop N 1 ] 1 swap 1 [ | 0 0 ] 1 [ | 0 .after. 0 ] |
CELL(N) <= EXPR |
EXPR N base + ++ ! |
OUTPUT <= EXPR |
EXPR base ! |
X [EXPR1,EXPR2,...,EXPRN] |
EXPR1 EXPR2 ... EXPRN X |
EXPR1 + EXPR2 |
EXPR1 EXPR2 + |
EXPR1 * EXPR2 |
EXPR1 EXPR2 * |
EXPR1 OR EXPR2 |
EXPR1 EXPR2 + |
EXPR1 AND EXPR2 |
EXPR1 EXPR2 * |
EXPR1 > EXPR2 |
EXPR1 EXPR2 - |
EXPR1 = EXPR2 |
EXPR1 EXPR2 != 1 swap 1 [ | drop 0 0 ] |
Access to argument number N, 1-indexed
|
N [ 1 | aux> ] dup N [ 1 | swap >aux ] |
Access to CELL(N)
|
N base + ++ @ |
Access to OUTPUT
|
base @ |
Literal number N
|
N |
YES |
1 |
NO |
0 |
This completes the second part of the proof: PricK is at least as powerful as BlooP, thus proving the equivalence.
Self interpreter
Because there is no universal primitive recursive function PricK and equivalent languages aren't capable of self-interpretation.
Language extensions
Implementations may provide additional builtin functions to make computation more efficient. Here are some propositions for such additions, along with proofs that they don't increase PricK's power.
Basic stack shuffling
By delegating specific cells in memory as scratch variables it is possible to shuffle values on the stack. Basic stack shuffling commands common in other stack languages can be implemented in PricK:
# ++ : tmp0 # ++ ++ ++ : tmp1 # ++ ++ ++ ++ ++ : tmp2 tmp0 ! tmp0 @ : id id tmp0 @ : dup tmp0 ! : drop tmp0 ! tmp1 ! tmp0 @ tmp1 @ : swap tmp1 ! id tmp1 @ tmp0 @ : over tmp2 ! swap tmp2 @ swap : rot
Maths
Base PricK provides only the incrementation operator, but many other mathematical functions are well within its power, although at a cost of significant performance loss which is why they are expected to be provided as builtin optimised functions:
[ # ++ | ++ ] : + # swap # swap [ # ++ | swap drop dup ++ ] drop : -- [ # ++ | -- ] : - tmp0 ! tmp1 ! # tmp0 @ [ # ++ | tmp1 @ + ] : * tmp2 ! # swap id ++ tmp0 @ [ tmp2 @ - dup | swap ++ swap ] drop : / over over swap - rot rot - + : !=
An interesting side effect of totality of PricK is that the slightly altered naive division algorithm presented here won't loop forever on division by zero but instead will return the dividend as if division by one occured.
Numbers
An expected convenience feature is defining all numeric identifiers to be functions that push the corresponding numbers to the stack. There's no way to define an infinite amount of identifiers in base PricK, but the following defintions facilitate a sort of space-separated decimal notation:
# ++ ++ ++ ++ ++ dup + * : 0 0 ++ : 1 0 ++ ++ : 2 0 ++ ++ ++ : 3 0 ++ ++ ++ ++ : 4 0 ++ ++ ++ ++ ++ : 5 0 ++ ++ ++ ++ ++ ++ : 6 0 ++ ++ ++ ++ ++ ++ ++ : 7 0 ++ ++ ++ ++ ++ ++ ++ ++ : 8 0 ++ ++ ++ ++ ++ ++ ++ ++ ++ : 9 # 2 1 3 7 : 2137
Auxiliary stack
To facilitate arbitrary stack shuffling it's useful to have a second stack where data is stored temporarily. Addition of such stack in an implementation won't expand PricK's capabilities since it can be emulated in memory, for example by using even memory cells for it, and leaving odd memory cells for normal RAM use. This way RAM remains unbounded and the new stack is unbounded as well.
# 7 : asp asp @ dup -- -- asp ! @ : aux> asp @ ++ ++ dup asp ! ! : >aux asp @ @ : aux@ dup + ++ @ : @ dup + ++ ! : ! # : tmp0 # ++ : tmp1 # 2 : tmp2 # 3 : asp
Code examples
For clarity examples in this section assume that facilities implemented in the Language Extensions section are implemented.
Fibonacci numbers
The naive recursive implementation requires some significant changes to turn it into a bounded loop which makes it non-trivial, so a different approach is presented here. Input and output is one number on the stack.
tmp0 ! # # ++ tmp0 @ [ # ++ | over + swap ] drop
Compact variant
To make parsing and interpretation simpler a compact version of PricK was conceived: in it each character is a separate token no matter if it's whitespace or not, and the builtin increment function is represented by the character +. Undefined tokens (characters) are treated as no-ops, so whitespace can still be used for code clarity until it's assigned a body.
Definitions from Stack shuffling, Maths and Numbers sections translated to compact PricK:
#+:a #+++:b #+++++:c a!a@:i ia@:% a!:. a!b!a@b@:~ b!ib@a@:o c!~c@~:r [#+|+]:p #~#~[#+|~.%+].:- [#+|-]:m a!b!#a@[#+|b@+]:* c!#~i+a@[c@-%|~+~].:/ #+++++%p*:0 0+:1 0++:2 0+++:3 0++++:4 0+++++:5 0++++++:6 0+++++++:7 0++++++++:8 0+++++++++:9 #2137:J