PatrickScript Language Specification

Version: 1.3.0 Status: active Authored by: patrick-script-worker track, 2026-05-15

1. Overview

PatrickScript is a Turing-complete, stack-based programming language whose entire design — computational model, grammar, semantics, tooling — was authored by an LLM. The only human-fixed inputs are:

• The name: PatrickScript
• The two lexical tokens: patrick (the literal string) and (a single space, U+0020)

Every other property of the language is a decision made by the patrick-script-worker track. No design question is deferred to the originator.

PatrickScript programs are sequences of these two tokens. Structure is encoded in the count of consecutive identical tokens: how many patricks in a row, and how many spaces in a row. These counts carry all meaning.

2. Lexical Model

A PatrickScript source file is a sequence of bytes drawn exclusively from two token types:

No other bytes are legal in a PatrickScript source. Specifically: - Newlines, tabs, carriage returns, and all other whitespace are illegal. - Any byte sequence other than patrick or is illegal. - An empty file (zero bytes) is a valid program (it halts immediately).

2.1 Tokens vs. Characters

The unit of tokenization is not the character but the token as defined above. The string patrick is a single WORD token, not seven character tokens. The string patrick is illegal (not a WORD token and not a SP token).

3. Syntactic Structure

Tokens are organized into two syntactic constructs:

Word: a maximal contiguous run of WORD tokens. The arity of a word is its length in WORD tokens.

Gap: a maximal contiguous run of SP tokens. The width of a gap is its length in SP tokens.

A PatrickScript program is a sequence of zero or more instructions. Each instruction is a (word, gap) pair: a word followed by a gap. The final instruction in a program may omit its trailing gap; when it does, the gap is treated as having width 1.

Formal Grammar

program     ::= instruction* trailing?
instruction ::= word gap
trailing    ::= word
word        ::= 'patrick'+
gap         ::= ' '+

Since words and gaps are each maximal runs of their respective token, they alternate strictly: no two words are adjacent (they would fuse into one word), and no two gaps are adjacent (they would fuse into one gap).

3.1 Instruction Encoding

Each instruction encodes:

• Opcode: selected by (word_arity, gap_arg) together, where gap_arg = gap_width - 1. The gap always has width ≥ 1 (by grammar), so gap_arg ≥ 0. For a trailing word with no gap, gap_arg = 0.
• Argument: the gap_arg value doubles as the numeric immediate argument for instructions that take one (e.g., PUSH, JUMP).

4. Machine Model

A PatrickScript machine has the following state:

• Value stack (S): a LIFO stack of arbitrary integers (positive, negative, or zero). Initially empty.
• Memory (M): a map from integer addresses to integer values. M[addr] is 0 for any address not yet written. The address space is unbounded in both directions.
• Instruction pointer (IP): a zero-based index into the instruction sequence. Starts at 0.
• Program: the compiled list of (arity, gap_arg) pairs, indexed 0..N-1.
• I/O: standard input and standard output, byte-oriented.

Execution proceeds by fetching the instruction at IP, executing it, advancing IP, and repeating until HALT or an error condition.

5. Instruction Set

Notation

Stack effects use the convention before → after, where items are listed left-to-right with the top of stack at the right. For example, a b → a+b means: before execution, b is on top with a below it; after execution, their sum is on top.

n denotes the gap_arg value of the current instruction (the immediate integer argument).

5.1 Stack Manipulation

5.2 Arithmetic

All arithmetic pops two values unless noted. The operand order is: pop b (top), pop a (below), compute and push result.

Negative integer literals: PUSH encodes its argument as gap_arg, which is always ≥ 0. There is no literal syntax for negative integers. To push −n, push n then negate: PUSH n followed by NEG. The result is −n on the stack. The assembler supports this directly via two lines.

Division and modulo: a is the dividend (below in stack), b is the divisor (top of stack). DIV computes floor(a / b). MOD computes a - b * floor(a / b). Division by zero is a runtime error.

5.3 Comparison

Comparison operand order: pop b (top), pop a (below), push result.

5.4 Control Flow

JUMP and JUMPZ set the IP to the instruction at 0-based index n. After a jump, execution continues from the new IP (no automatic increment for that step). If n is out of bounds, it is a runtime error.

JUMPZ and JUMPNZ always pop the condition value, whether or not the branch is taken.

5.5 Input / Output

5.6 Memory

5.7 Halt

5.8 Subroutines (v1.1.0)

CALL n saves the return address (the index of the instruction immediately following CALL) by pushing it onto the value stack, then sets IP to n. Execution continues from instruction n.

RET pops the top of the value stack as a return address and sets IP to it. If the stack is empty when RET executes, it is a stack underflow error. If the popped value is not a valid instruction index, it is a jump-out-of-bounds error.

The gap_arg of CALL is the jump target (like JUMP). The gap_arg of RET is ignored (like HALT).

Subroutines can be nested: each CALL pushes a return address, and each matching RET pops it. Recursive calls are legal but may exhaust stack space in practice.

5.9 Negative Push (v1.2.0)

PUSHN n pushes the negation of its immediate argument. The argument n is encoded as gap_arg (≥ 0), so the pushed value is −n (≤ 0). This provides single-instruction access to negative constants, which PUSH alone cannot represent (since gap_arg ≥ 0).

Examples: PUSHN 5 pushes −5. PUSHN 0 pushes 0 (same as PUSH 0).

The two-instruction idiom PUSH n / NEG remains valid and equivalent. PUSHN is a convenience instruction, not a new capability.

5.10 Stack Copy (v1.3.0)

PICK n copies the element at depth n (0-indexed from the top of the stack) and pushes it onto the top. The original element is not removed.

• PICK 0 duplicates the top element (equivalent to DUP).
• PICK 1 copies the second element from the top.
• PICK n where n ≥ stack depth is a stack underflow runtime error.

PICK is useful for accessing subroutine arguments buried below return addresses, and for implementing n-ary operations that need a value without consuming it.

Examples: - Stack [1 2 3] (3 on top): PICK 0 → [1 2 3 3] - Stack [1 2 3]: PICK 2 → [1 2 3 1]

5.11 Reserved and Illegal Instructions

Arities 15 and above are reserved for future versions. An instruction with arity ≥ 15 is a runtime error in v1.3.0.

There is no instruction with arity 0 (a zero-length word is not grammatically possible).

6. Error Conditions

The following conditions are runtime errors. A conforming interpreter MUST terminate with a non-zero exit code and SHOULD emit a diagnostic message to stderr.

For arity 2, gap_arg values 4 and above are illegal. For arity 3, gap_arg values 6 and above are illegal. For arity 4, gap_arg values 7 and above are illegal. For arities 5, 6, 7, any gap_arg is legal (it is the target or unused). For arity 8, gap_arg values 4 and above are illegal. For arity 9, gap_arg values 2 and above are illegal. For arity 10 (HALT), all gap_arg values are legal. For arity 11 (CALL), any gap_arg is legal (it is the target address). For arity 12 (RET), all gap_arg values are legal (the gap_arg is ignored). For arity 13 (PUSHN), any gap_arg is legal (it is the value to negate). For arity 14 (PICK), any gap_arg is legal (it is the stack depth index), but a PICK n where n ≥ stack depth is a stack underflow runtime error.

Lexical errors (illegal characters in source) are parse-time errors and MUST cause the interpreter to exit with a non-zero exit code before any execution.

7. Encoding Reference

An instruction is written as:

('patrick' × arity) (' ' × (gap_arg + 1))

except the last instruction in a program, which may omit trailing spaces (treated as gap_arg = 0).

7.1 Encoding Examples

Within a word, patrick tokens are concatenated with no separating characters. A word of arity n is the string patrick repeated n times. The gap follows immediately after the last patrick of the word.

Below, p stands for patrick (7 characters) and · for a space:

A concrete example: OUTCHAR followed by HALT is the byte sequence patrickpatrickpatrickpatrickpatrickpatrickpatrickpatrick patrickpatrickpatrickpatrickpatrickpatrickpatrickpatrickpatrickpatrick (8 patricks, 2 spaces, 10 patricks).

8. Turing Completeness

PatrickScript is Turing complete. The proof is constructive: a Brainfuck interpreter written in PatrickScript, since Brainfuck is itself known Turing complete.

The concrete witness lives at examples/brainfuck.psa (assembler source) and examples/brainfuck.ps (compiled). It reads a Brainfuck program from stdin (terminated by EOF or the ! separator), then executes it. All eight Brainfuck instructions are implemented: + - > < [ ] . ,.

Two corpus tests pin the result:

• corpus/brainfuck-loop.{ps,stdin,expected,desc} runs the canonical short program ++++++++[>++++++++<-]>+. and produces A (ASCII 65).
• corpus/brainfuck-hello.{ps,stdin,expected,desc} runs the classic Brainfuck Hello World! program and produces Hello World!.

The structural ingredients PatrickScript supplies to make this work:

• Unbounded memory (LOAD/STORE on integer addresses, positive and negative).
• Arbitrary-precision integer arithmetic (ADD, SUB, MUL, etc.).
• Conditional branching (JUMPZ, JUMPNZ).
• Loops (JUMP backwards creates loops, JUMPZ exits them).

The interpreter uses mem[0..2] for state (pc, source length, data pointer), mem[3..3+N-1] to hold the loaded Brainfuck source, and negative addresses mem[-(dp+1)] for the Brainfuck tape — keeping source and tape disjoint without large PUSH offsets.

9. Program Examples

9.1 Hello World (first character)

Output ASCII 72 ('H') and halt. Using p for patrick and · for space:

p········································································pppppppp··pppppppppp

Decoded: - PUSH 71 — arity=1, gap_arg=71: p followed by 72 spaces - OUTCHAR — arity=8, gap_arg=1: pppppppp followed by 2 spaces - HALT — arity=10, gap_arg=0: pppppppppp with no trailing spaces

Note: PUSH 71 requires 72 spaces after one patrick token. PatrickScript programs for non-trivial ASCII output are verbose by design. This is intentional: the verbosity is a property of the encoding, not an implementation choice.

9.2 Infinite counter

Print 0, 1, 2, ... indefinitely:

Instruction 0: PUSH 0        (arity=1, gap_arg=0) — push initial value
Instruction 1: DUP           (arity=2, gap_arg=1) — duplicate for print
Instruction 2: OUTNUM        (arity=8, gap_arg=3) — print number
Instruction 3: PUSH 1        (arity=1, gap_arg=1) — push increment
Instruction 4: ADD           (arity=3, gap_arg=0) — counter + 1
Instruction 5: JUMP 1        (arity=5, gap_arg=1) — loop back to DUP

9.3 Echo (copy stdin to stdout)

Read characters until EOF, writing each:

Instruction 0: INCHAR        (arity=8, gap_arg=0) — read byte or -1
Instruction 1: DUP           (arity=2, gap_arg=1) — dup to check for EOF
Instruction 2: PUSH 1        (arity=1, gap_arg=1) — push 1
Instruction 3: ADD           (arity=3, gap_arg=0) — eof+1; 0 if was -1
Instruction 4: JUMPZ 7       (arity=6, gap_arg=7) — if EOF, jump to HALT
Instruction 5: OUTCHAR       (arity=8, gap_arg=1) — write byte
Instruction 6: JUMP 0        (arity=5, gap_arg=0) — loop
Instruction 7: POP           (arity=2, gap_arg=0) — discard sentinel -1
Instruction 8: HALT          (arity=10, gap_arg=0) — done

9.4 FizzBuzz (1 to 15)

The canonical Turing-completeness demonstration. Uses memory (STORE/LOAD) to hold the loop counter and a printed-flag, MOD for divisibility tests, JUMPZ/JUMPNZ for branching, OUTCHAR for string output, and OUTNUM for integer output. The source examples/fizzbuzz.psa is 70 instructions; the compiled .ps form is 3,361 bytes.

Design sketch (register map: mem[0] = n, mem[1] = printed_flag):

; --- Init ---
PUSH 1; PUSH 0; STORE        ;; mem[0] = 1

main_loop:
  PUSH 0; LOAD               ;; n
  PUSH 15; GT; JUMPNZ done   ;; n > 15 → halt

  PUSH 0; PUSH 1; STORE      ;; printed_flag = 0

  ; Fizz check
  PUSH 0; LOAD; PUSH 3; MOD
  JUMPNZ check_buzz          ;; n%3 != 0 → skip
  OUTCHAR 'F','i','z','z'
  PUSH 1; PUSH 1; STORE      ;; printed_flag = 1

check_buzz:
  PUSH 0; LOAD; PUSH 5; MOD
  JUMPNZ check_num           ;; n%5 != 0 → skip
  OUTCHAR 'B','u','z','z'
  PUSH 1; PUSH 1; STORE      ;; printed_flag = 1

check_num:
  PUSH 1; LOAD; JUMPNZ print_nl ;; printed_flag != 0 → newline only
  PUSH 0; LOAD; OUTNUM           ;; otherwise print n (OUTNUM adds \n)
  JUMP next_iter

print_nl:
  PUSH 10; OUTCHAR           ;; '\n'

next_iter:
  PUSH 0; LOAD; PUSH 1; ADD
  PUSH 0; STORE              ;; n = n + 1
  JUMP main_loop

done:
  HALT

Output for 1..15:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

9.5 Factorial (n!) — iterative

Computes n! for an integer read from stdin. Uses STORE/LOAD for an accumulator register, MUL for iteration. The source corpus/factorial.psa computes 5! = 120.

Design sketch (register map: mem[0] = accumulator):

PUSH 1; PUSH 0; STORE    ;; mem[0] = 1 (acc)
INNUM                    ;; read n
loop:
  DUP; JUMPZ done        ;; n == 0 → done
  DUP
  PUSH 0; LOAD           ;; acc
  MUL
  PUSH 0; STORE          ;; acc = acc * n
  PUSH 1; SUB            ;; n = n - 1
  JUMP loop
done:
  POP
  PUSH 0; LOAD; OUTNUM   ;; print acc
  HALT

9.6 Subroutine Calling Convention

CALL pushes the return address on top of the value stack before jumping. This means on subroutine entry, the return address sits above any arguments the caller pushed — the opposite of most conventional calling conventions where the return address is at a known frame offset.

The idiomatic pattern is SWAP to expose arguments, SWAP back to restore. For a single-argument subroutine:

; Caller:
PUSH arg
CALL sub           ;; stack on entry to sub: [..., arg, ret_addr]

; Subroutine body:
sub:
  SWAP             ;; [..., ret_addr, arg]   — expose argument
  < ... work on arg ... >
  SWAP             ;; [..., result, ret_addr] — restore call frame
  RET              ;; returns; result is now on top for caller

For zero-argument subroutines (output-only, side-effect routines), the return address is already on top and no SWAP is needed:

; Caller:
CALL print_greeting

; Subroutine:
print_greeting:
  PUSH 72; OUTCHAR   ;; 'H'
  PUSH 105; OUTCHAR  ;; 'i'
  PUSH 10; OUTCHAR   ;; '\n'
  RET

For multi-argument subroutines, the convention extends via multiple SWAPs or ROT:

; Two-argument sub (a, b → result):
; Caller pushes a then b, then CALL.
; Entry stack: [..., a, b, ret_addr]

sub2:
  ROT              ;; [..., b, ret_addr, a]  — surface first arg
  SWAP             ;; [..., b, a, ret_addr]  — expose both args below ret
  < ... work on a and b ... >   ;; stack: [..., result, ret_addr]
  RET

Recursive subroutines work naturally: each CALL pushes a new return address above the current frame's values. The recursive factorial in corpus/factorial-recursive.psa demonstrates this pattern — each recursive level pushes its n and then CALL pushes the return address; SWAP is used at subroutine entry to reorder them for computation.

Key invariant: at each RET, the return address must be on top of the stack with the result(s) below it. Violations (wrong stack depth, wrong top-of-stack) cause jump-out-of-bounds or return to a garbage address. The assembler's label system makes CALL targets readable, but the stack discipline at RET is the programmer's responsibility.

9.7 Zero-Argument Subroutine Reuse

A zero-argument subroutine is the simplest reusable unit: no arguments to SWAP around, no result to thread through the stack frame. Because the return address arrives on top, the subroutine executes, then RETs without any frame-management overhead.

print_hello:
  .string "Hi\n"   ;; output-only side effect
  RET               ;; return address already on top

The same subroutine can be called any number of times:

CALL print_hello   ;; first call
CALL print_hello   ;; second call — same body, new return address
HALT

Each CALL pushes a fresh return address, so independent invocations share the body code but maintain separate return continuations. There is no state to reset between calls; zero-argument subroutines are naturally reentrant in a single-threaded sequential program.

This pattern suits output routines, print helpers, and repeated fixed-work blocks. The corpus/call-string.psa test demonstrates it: .string "Hi\n" + RET, called twice.

9.8 PICK for Non-Destructive Stack Access (v1.3.0)

PICK reads a value from depth n without consuming it, avoiding the need to pop-and-reorder when the same value is needed more than once.

PICK 0 is equivalent to DUP: it copies the top element.

PICK n (n > 0) copies an element buried below the top. The primary idiom: computing an expression that uses a value from deeper in the stack without removing it from its position.

Example — compute a + b + a using PICK 1 to reuse a:

; a=3, b=7; compute 3 + 7 + 3 = 13
PUSH 3      ;; stack: [3]
PUSH 7      ;; stack: [3 7]  (7 on top)
PICK 1      ;; copy a (depth 1): [3 7 3]
ADD         ;; [3 10]
ADD         ;; [13]
OUTNUM      ;; outputs 13
HALT

Without PICK, accessing a after pushing b would require storing a to memory and reloading it. PICK avoids the memory round-trip when the value is already on the stack.

The corpus/pick-deep.psa test demonstrates accessing multiple depths: PICK 2 and PICK 1 used to non-destructively copy the first and second elements of a three-element stack.

10. Versioning

v1.0.0 (2026-05-15)

Initial release. Stack machine with 10 arities: PUSH (1), stack ops (2), arithmetic (3), comparison/bitwise (4), JUMP/JUMPZ/JUMPNZ (5–7), I/O (8), memory (9), HALT (10). Arities 11+ reserved.

v1.1.0 (2026-05-15)

Adds subroutine support: CALL (arity 11) and RET (arity 12). Arities 13+ remain reserved. A v1.1.0-conformant interpreter executes CALL and RET as specified in section 5.8; it treats arities ≥ 13 as runtime errors. A v1.0.0-only interpreter that encounters arity 11 or 12 is permitted to treat them as runtime errors (reserved instruction).

v1.2.0 (2026-05-15)

Adds PUSHN (arity 13, gap_arg = n): pushes −n onto the stack. Provides single-instruction negative literal encoding. The two-instruction idiom PUSH n / NEG remains valid and equivalent; PUSHN is a convenience instruction. A v1.2.0-conformant interpreter executes PUSHN as specified in section 5.9; it treats arities ≥ 14 as runtime errors.

Arities 14+ remain reserved in v1.2.0.

v1.3.0 (2026-05-15)

Adds PICK (arity 14, gap_arg = n): copies the element at depth n from the top of the stack (0 = top). Provides direct access to buried stack values without destructive reordering. A v1.3.0-conformant interpreter executes PICK as specified in section 5.10; it treats arities ≥ 15 as runtime errors. A v1.2.0-only interpreter that encounters arity 14 is permitted to treat it as a runtime error.

Arities 15+ remain reserved.

Future versions add instructions via currently-reserved arities (15+) or extend the gap_arg space for existing arities.

Version is declared in the spec document title, not in the source language (PatrickScript has no pragma syntax).

11. Formal Summary

• Tokens: WORD (patrick) and SP (U+0020)
• Words: maximal WORD runs; arity = count
• Gaps: maximal SP runs; width ≥ 1; gap_arg = width - 1
• Instructions: (word, gap) pairs; last gap optional (treated as width 1)
• Machine: stack + memory + IP + I/O
• Completeness: Turing complete
• Designed by: patrick-script-worker (LLM), 2026-05-15
• Fixed by originator: name PatrickScript; tokens patrick and