primitive recursive driven programming

Prequel Primer

Each Prequel program is created to operate in a context given by the particular input variables and procedures available.

Begining programmers can start by calculating the factorial of a number or by sorting a list of numbers, or even by animating a line of 8 pixels.
As they get to know the language and the debugger, they can try to escape from a labirinth. Or try out an inductive programming game.
It is also possible to play a match with up to four PrequelBots in a cyclic arena.

With this in mind, this primer can help people who know other programming languages understand the differences to Prequel.

Prequel is a primitive recursive driven imperative language with two datatypes (lists and numbers) and two control structures (conditionals and bounded loops).
If you know other imperative languages, such as C or Python, there are only a few features worth noting.


Comments start with symbol '#' and continue until the end of the line.

  # This line is a comment.
  # Comments start with symbol '#'
  #  and continue until the end of the line.

Input Variables and Procedures

There are two types of input to a Prequel program: input variables and procedures.
Syntactically, they are both sequences of alphanumeric characters (usually capital letters) separated by dots (symbol '.').

In the factorial example, FACTORIAL.INPUT is an input variable containing the argument to the factorial function.
After calculating the result, the procedure FACTORIAL.RETURN should be called to terminate the program with the correct value.

It is important to note that input variables and procedures are read-only and thus cannot be changed directly by the programmer.

Variables and Assignment

Variables are sequences of alphanumeric characters (usually lower-case; without dots) and can be created or updated with the assignment operator (symbol ':=').

For example,

assigns to variable n the contents of input variable FACTORIAL.INPUT.


All numbers in Prequel are signed 32-bit fixed point with 16 fraction bits.

Arithmetic Operators

Six arithmetic operators are available: addition (symbol '+'), subtraction (symbol '-'), multiplication (symbol '*'), division (symbol '/'), integer division (symbol '//'), and modulo (symbol '%').

Shorthands for these operations are also available to combine with assignments. For example,

  n++    # same as n += 1
  n += 1 # same as n := n + 1

Bitwise Operators

The following bitwise operators are available: and (symbol '&'), or (symbol '|'), not (symbol '~'), xor (symbol '^'), shift left (symbol '<<'), and shift right (symbol '>>').

Shorthands for these operations are also available to combine with assignments. For example,

  n~~    # same as n ~= n
  n ~= n # same as n := ~n

Random Numbers

Prequel has built-in support for random numbers through the random operator (symbol ':~').

Given a positive integer n, we can obtain a random index, an integer between 0 and n-1.

  r :~ 10 # r gets a random number
          #   between 0 and 9

If a random number in the full range is needed, the keyword RANDOM can be used instead of the arithmetic expression.

  r :~ RANDOM # r gets a random number
              #   between -32768
              #        and 32767.99998474121


Structured data can be expressed through lists.
List elements can be numbers or lists themselves.

For example,

  xs := [1, 2, [3, 4], 5, []]

List access

Individual elements can be accessed through list subscripts.
For example,

  n := xs[2][0] # n gets value 3

List length

The length of a variable of type list can be obtained with the suffix .LENGTH.
For example,

  n := xs[2].LENGTH # [3, 4] has length 2

List search

The suffix .INDEXOF can be used to search for elements in variables of type list.
If the element is found, it returns its index position in the list. Otherwise, it returns -1.
For example,

  n := xs.INDEXOF 5 # 5 is found at index 3
Note that it does not continue the search inside nested lists:
  n := xs.INDEXOF 4    # not found (n gets value -1)
  n := xs[2].INDEXOF 4 # 4 is found at index 1

List manipulation

It is possible to add an element to a variable of type list using a PUSH instruction.
Similarly, it is possible to remove an element from a variable of type list using a POP instruction.
For example,

  xs.PUSH 6 5 # xs change to [1, 2, [3, 4], 5, [], 6]
  n := xs.POP # if the list index if omitted,
              #   it defaults to the end of the list

Note that this does not apply to input variables since those are read-only.

List copy

Assignment copies lists.
For example,

  ys := xs   # ys get a copy of xs
  ys[0] := 0 # xs remain unchanged


An IF instruction can be followed by one or more ELSIF, an optional ELSE, and terminates with ENDIF.
For example,

   n := 0
  ELSIF n = 1 OR n >= 3
   n := 1
  ELSIF n <> 0
   n := 2
   n := 3
Note that the blocks of instructions are defined by their indentation.

Relational Operators

Relational operators can be used to check whether two numbers are: equal (symbol '='), different (symbol '<>'), relatively less than (symbol '<'), less than or equal to (symbol '<='), greater than (symbol '>'), and greater than or equal to (symbol '>=').

Logical Operators

The three operators, AND, OR, and NOT, can be used in the logical expressions of instructions IF and ELSIF.

Bounded Iteration

A variable containing a number n can be used to repeat a block of instructions n times.
The variable is decremented each time the program counter enters the repeat block and the programmer cannot modify the variable while inside the repeat block.
For example, in

  total := 0
  n := 4
   total += n
after repeating the sum four times, variable n is equal to zero and variable total is equal to six (3+2+1+0).

Early-Terminating Iteration

Analogous to break and continue of other programming languages, in Prequel we have REPSTOP and REPNEXT, respectively.

Infinite Loops

Prequel imposes a programming discipline that prohibits recursive calls and unbounded loops.
The runtime system derives its Turing completeness from re-entering a module whenever the execution slips past its last instruction.
You can imagine each Prequel module being contained inside a while true loop.

The Ackermann example was created to illustrate this feature of Prequel.

More Documentation

Although there is more to be said about Prequel, hopefully this is enough to get you started.
Try the examples and have a look at their links to GitHub repositories for more Prequel code.
AlgoDeduce has more code examples.
There are also slides providing some context and the theoretical underpinnings of Prequel.
Every valid source code in Prequel conforms to this BNF grammar.

Keep in touch, check out the author's website.
Happy Prequel programming!