Primality in HPR + macros

// Primality tester in HPR + macros
// Takes input as the unary version of a list [p, p-1, ..., 2, 1]
// For example, input 4 is encoded as 111101110110100
// Prints 1 is p is a prime, otherwise an empty line

// No numbers
def no_nums 0 #(-)()

// No non-empty lists
def no_list 0 #(*)()

// Delete numbers
def del_nums 0 !(-)(<no_nums>)

// Delete lists
def del_list 0 #(<del_nums>)()

// Do until no change (optimized)
def fix 1 !({0})(#({0})())

// Do until condition holds
def until 2 !({1})({0})

// True condition / empty environment
def true/empty 0 <del_nums><del_list>

// Logical not of condition
def not 1 <until>({0},<true/empty>)

// Empty or revert
def bool 1 <not>(<not>({0}))

// Logical or of two conditions
def or 2 <bool>({0}){1}

// Splat list to environment
def splat 0 #(<until>(<no_list>,*)<del_list>)(<del_nums>)

// Take all up to maximum
def upto_max 0 <del_nums><fix>(-<splat>)

// Take only maximum
def max 0 <upto_max>#(-)(<del_list>)

// Head is maximal
def max_head 0 <del_nums>#(*)(<max>)<del_list>

// Head of list is in evironment
def has_head 0 #(*)()<del_list>

// Add first element without popping list
def peek 0 #(*<del_list>)(<del_nums>)

// Only the number zero
def zero 0 <del_nums>*<del_list><until>(-,-)

// Only the number one
def one 0 <del_nums>*<del_list><until>(--,-)

// Head is 1
def is_one 0 <del_nums>#(<one>)(*<del_list>)

// Delete one number from the environment that's also in the list:
// Rotate until head is in the environment, then delete it using symmetric differences
def del_any 0 #(#(<until>(<has_head>,$)<del_nums>*)()<del_list>)(<del_nums>)

// Delete all but zero
def del_pos 0 <until>(-<del_list>,<del_any>)

// The number zero is in the environment
def has_zero 0 <not>(<del_pos><del_list>)

// The environment has a positive value strictly below head (doesn't work for maximal head):
// Rotate list (at least once) until head is found in environment
// or is maximal, check that it's not maximal
def has_below 0 $<until>(<or>(<has_head>,<max_head>),$)<not>(<max_head>)

// Head divides maximum: Take maximum value, then keep taking the head value and
// decrementing (at least once) until the lowest value reaches 0, stop when there's only 0 or
// something between the head value and 0, check that it's the former
def head_divides 0 <max><until>(<or>(<has_below>,-<del_list>),<peek>-<until>(<has_zero>,-))-<del_list>

// Main program: rotate until head divides maximum, then check that head equals 1
$<until>(<or>(<is_one>,<head_divides>),$)<not>(<is_one>)<one>