JollyScript

JollyScript is an enterprise-grade language for intelligent elves. It's so festive, that every JollyScript program is shaped like a Christmas tree!
Programming in JollyScript is difficult as it requires intelligent thought to deal with the tree-shaped structure of the program.
== Language overview ==
JollyScript operates on a global stack of 4-bit integers, also known as nibbles. It also has a global variable ret, a return location.
The program is executed via a cursor on a 2-dimensional grid. Execution begins at the asterisk symbol * on the first line of the program, and the cursor moves downwards diagonally. It can go either left or right, but its initial direction is left.
After the cursor encounters a command, it continues in the same direction as before, unless the command changes the direction.
== Commands ==
Here are the commands for JollyScript:
Command 	Description
* 	Start the program here, going in the left direction.
/ 	Set the direction to left.
\ 	Set the direction to right.
^ 	Run the left branch completely. When everything from that branch has terminated, run the right branch.
~ 	Terminate this branch.
+ 	Pop a, then pop b. Push a + b onto the stack.
- 	Pop a, then pop b. b - a onto the stack.
: 	Duplicate the top of the stack.
% 	Swap the top two values of the stack.
$ 	Pop and discard the top of the stack.
? 	Look at the top of the stack. If it is zero, set the direction to left. Otherwise, decrement the top of the stack, and set the direction to right.
0-9, A-F	Push a hexadecimal digit onto the stack.
. 	Print the top of the stack as an uppercase hexadecimal digit.
# 	Read a hexadecimal digit from standard input and push it onto the stack.
" 	Toggle printing mode. Characters encountered will instead be printed until printing mode is turned off.
n 	Print a newline.
, 	Print the top two values of the stack as an ASCII character.
& 	Read a character from standard input and push two values onto the stack corresponding to its ASCII code.
{ 	Set the global variable ret to the current cursor location.
} 	Set the cursor location to ret, going in the same direction as before this command.
All characters should be considered comments and ignored.
== Implementation details ==
* JollyScript programs must be in the shape of a Christmas tree.
* All integers are 4 bits, and wrap around on overflow.
* Only 0–9 and uppercase A–F are considered valid hexadecimal digits.
* When considering an ASCII character as two 4 bit values on the stack, the least significant 4 bits lie on top of the most significant 4 bits.
* If the cursor encounters &, and it is EOF, 0 is pushed onto the stack twice.
* If the cursor encounters #, and it is EOF, 0 is pushed onto the stack.
=== Undefined behaviour ===
* If the cursor encounters #, and the character is not a hexadecimal digit, the behaviour is undefined.
* When the standard input contains characters that do not fit in a byte, the behaviour is undefined.
* If there are not enough values on the stack to perform a command, the behaviour is undefined.
* If there is no * character on the first line, or if there are multiple, the behaviour is undefined.
* If the cursor goes out of bounds, the behaviour is undefined.
* If the cursor enounters } before ret is set with a { command, the behaviour is undefined.
== Examples ==
The following are examples of programs in JollyScript.
=== Hello World! ===
 + *
 ^
 ^ ^
 " " "
 H W l l
 e o @ o d
 l r O @ !
 " " @ @ O " "
~~~~~~|_|~~~~~~
Hello World!
=== Truth-machine ===
For the input 0, the program prints 0 and halts. Otherwise, the program prints 1111111111111111... infinitely.
 *
 ^
 { ?
 # . 1
 / / } }
~~~/-\~~~
=== Cat program ===
The cat program copies its standard input to its standard output. Characters are read via &, and the program detects EOF as the null character.
 *
 {
 ^ 0
 & ? %
 : + / ?
 ~ + $ \ /
 ^ , $
 : } , \
~~~~{_}~~~~
=== FizzBuzz ===
This program prints the integers from 1 to 100, with multiples of 3 replaced with "Fizz", multiples of 5 replaced with "Buzz", and multiples of 15 replaced with "FizzBuzz". 
 @ *
 {
 0 ?
 1 ^ ?
 1 " X ?
 / F ^ X \
 / i / X $ \
 \ z ^ ^ \ \ /
 z / ^ \ \ \
 " X + ? ^ ^ ^
 ^ / : + X X X 1
 + X / % \ X X 2 /
 : + ? \ $ \ X 0 / \
 ~ ? \ 4 : } \ $ \ O ~
 ^ 1 \ - \ O : ~ n \
 + ? + \ ? ? O 9 O } \
 A 0 / / ^ $ ^ O - O O \
 - { B 0 ^ O 0 % O ? O O \
 ~ / + O " " + ~ . ^ $ O \ ~
 / 0 ~ B " z 1 O O 1 1 O \
 / 0 O u % $ z ~ + O + + O \
 / O O " . . O " $ O O 0 O O \
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 ///^\\\
 /// \\\
 \/___\/
1
2
Fizz
4
Buzz
...
=== 99 glasses of milk ===
This program is heavily golfed.
 + *
 {
 9 ^
 9 / ?
 \ : ^ ^
 / X \ X \
 / ? } / ^ ^
 \ $ / ^ \ X /
 % $ ^ ^ " ^
 : 0 $ X " T 1
 ? ~ / / " " a ^
 $ ^ \ / " " 0 k ~
 1 $ / / / ? 2 / " /
 \ ~ % / / + / ^ ^ /
 { 0 / / 1 / " ^ \ "
 ^ ~ \ / - / " ^ " 
 " ^ X 9 / g s / ^ e a
 " / " X / l s / " ? n
 s r " G % / a " / " ^ a d
 t e m o ^ % " % $ o l / ^ "
 o , e / ? \ ? ~ f k " " ? s ^
 " t / % 1 ~ / . l h " / " ^
 ~ b m o / ? / " m " k e . " " ^
 / u o / " / + e i n " , a k " ^
 \ y r t 1 N : . " " ~ o w n " i o " /
 e h + o ^ \ \ ~ n a n n c e p i
 s , e ? " 1 + % " l $ $ o d , + p
 o " " 9 1 ~ @ . . s t l \ ~ o t i " / @ ,
 " n } + / $ @ @ % 1 " " } " " " n / @ @ "
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 |/// \\\|
 |// \\|
 /_______\
99 glasses of milk on the wall,
99 glasses of milk.
Take a sip, and a cookie to dip,
98 glasses of milk on the wall.
...
1 glass of milk on the wall,
1 glass of milk.
Take a sip, and a cookie to dip,
No glasses of milk on the wall.
No glasses of milk on the wall,
No glasses of milk.
Go to the store, buy some more,
99 glasses of milk on the wall.
=== The Twelve Days of Christmas ===
 *
 {
 B ^
 / " ^
 / O " ^
 / n t " ?
 / r a ^ ?
 / t u v " ^ ?
 / h e e T " ^ ?
 / e w E " ^ ?
 / l t e l T " ^ ?
 / " o o l e e N " ^ ?
 / : v v v n i E " ^ ?
 / B e m e e n i S " ^ ?
 / % e n l e g e S " ^ ?
 / - g , d o h v i F " ^ ?
 \ / " " r p r l t e x i F " ^ "
 / X ~ n u i d a n v o T " ^ A
 / ^ } : m p s d m g e u h T / \ "
 / ^ " ~ " " " " " " " " " " " / O \ /
 \ ? " a \ \ \ \ \ \ \ \ \ \ \ \ O O /
 " ? s " " " " " " " " " " " " O ^ \
 f " ? d , m e i a s e r r w A \ " \
 i s " ^ a " e r a e i w e g e o n " \
 r e t ? " y n r s - s d " s o c e d t \
 s c h " ? t " s l s ^ e l a t p r \
 t o i f " ? h o M p e d " d l F u a a e \
 " n r o f " ? " f y d i a a a a a l r r " " e \
 / d d u i s " ? $ r p p n - - - r i e t ~ ^ . \
 \ " " r f i s " ? ~ C " u i i c m s l i n n l \ " " /
 ^ " " x e e " ? " ~ m n n i i w a n g c e " i \
 / $ O / " v i n " ? / " m g g n l i y g h r n \
 ^ O / O / e g i t " / " a O i , , g k m i s g d t \
 / \ O / O n h n e e " h n / ^ n " " , i m n , e h o r a \
 / \ O / " " " n l t r s O / \ g O \ " n i g " e e v i $
 / \ O / O / " e w i / / \ , \ O \ g n , \ s n e d p n
 / /\/\ \ O / O / v e s " O / \ " O \ O , g " O e s s g e ?
 / (==) \ O / O e l t O / / <| \ O \ O \ " , O \ , , , e a n
 / / \ \ O / n f m / O / /\/\ | \ \ O \ O \ " \ O " " " r \
 / (_( UU ) \ O " " " O / / (==)| \ n n n n n n n n n n n " " }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 \^^/^\^^/
 |// \\|
 \/_____\/
On the first day of Christmas,
My true love gave to me,
A partridge in a pear tree.
...
On the twelfth day of Christmas,
My true love gave to me,
Twelve drummers drumming,
Eleven pipers piping,
Ten lords a-leaping,
Nine ladies dancing,
Eight maids a-milking,
Seven swans a-swimming,
Six geese a-laying,
Five gold rings,
Four calling geese,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.
== Interpreters ==
=== Haskell ===
import Data.Char (chr, digitToInt, intToDigit, ord, toUpper)
import Data.List (elemIndex)
import Data.Maybe (fromMaybe, fromJust)
import System.Environment (getArgs)
import System.Exit (die)
import System.IO (isEOF)
hexDigits :: String
hexDigits = "0123456789ABCDEF"
data Direction = LeftD | RightD
data ProgState = ProgState {ret :: (Int, Int), stack :: [Int], print_mode :: Bool}
execute :: [[Char]] -> (Int, Int) -> Direction -> ProgState -> IO ProgState
execute prog (x, y) d state@ProgState {ret, stack, print_mode} =
 case prog !! y !! x of
 '"' -> continue state {print_mode = not print_mode}
 c | print_mode -> putChar c >> continue state
 '/' -> left state
 '\\' -> right state
 '^' -> left state >>= right
 '~' -> return state
 '{' -> continue state {ret = (x, y)}
 '}' -> execute prog ret d state
 'n' -> putChar '\n' >> continue state
 c | c `elem` hexDigits -> continue state {stack = digitToInt c : stack}
 '&' -> do
 c <- getCharDefault '\x00'
 let (q, r) = divMod (ord c `mod` 256) 16
 continue state {stack = r : q : stack}
 '#' -> do
 c <- getCharDefault '0'
 let x = fromMaybe 0 (elemIndex c hexDigits)
 continue state {stack = x : stack}
 c -> case (c, stack) of
 ('+', x : y : xs) -> continue state {stack = (x + y) `mod` 16 : xs}
 ('-', x : y : xs) -> continue state {stack = (y - x) `mod` 16 : xs}
 (':', x : xs) -> continue state {stack = x : x : xs}
 ('%', x : y : xs) -> continue state {stack = y : x : xs}
 ('$', _ : xs) -> continue state {stack = xs}
 ('?', x : xs) -> if x == 0 then left state else right state {stack = (x - 1) `mod` 16 : xs}
 ('.', x : _) -> putChar (toUpper $ intToDigit x) >> continue state
 (',', x : y : _) -> putChar (chr $ 16 * y + x) >> continue state
 _ -> continue state
 where
 left = execute prog (x - 1, y + 1) LeftD
 right = execute prog (x + 1, y + 1) RightD
 continue = case d of
 LeftD -> left
 RightD -> right
 getCharDefault def = isEOF >>= \eof -> if eof then return def else getChar
main :: IO ()
main = do
 args <- getArgs
 case args of
 [] -> die "Intelligence error: no JollyScript program specified"
 x : _ -> do
 content <- readFile x
 let prog = lines content
 let x0 = fromJust $ elemIndex '*' $ head prog
 execute prog (x0, 0) LeftD $ ProgState {ret = (-1, -1), stack = [], print_mode = False}
 return ()
=== Python ===
from sys import argv, stdin, stdout, exit
HEX_DIGITS = "0123456789ABCDEF"
def execute(prog: list[str]):
 x0 = prog[0].index("*")
 call_stack = [(x0, 0, -1)]
 ret = (-1, -1)
 stack: list[int] = []
 print_mode = False
 while call_stack:
 x, y, d = call_stack.pop()
 match prog[y][x]:
 case '"': print_mode = not print_mode
 case c if print_mode: stdout.write(c)
 case "/": call_stack.append((x - 1, y + 1, -1)); continue
 case "\\": call_stack.append((x + 1, y + 1, 1)); continue
 case "^": call_stack.append((x + 1, y + 1, 1)); call_stack.append((x - 1, y + 1, -1)); continue
 case "~": continue
 case "+": stack.append((stack.pop() + stack.pop()) % 16)
 case "-": stack.append((-stack.pop() + stack.pop()) % 16)
 case ":": stack.append(stack[-1])
 case "%": stack[-2], stack[-1] = stack[-1], stack[-2]
 case "$": stack.pop()
 case "?":
 if stack[-1]:
 stack[-1] = (stack[-1] - 1) % 16
 call_stack.append((x + 1, y + 1, 1))
 else:
 call_stack.append((x - 1, y + 1, -1))
 continue
 case c if c in HEX_DIGITS: stack.append(HEX_DIGITS.index(c))
 case ".": stdout.write(HEX_DIGITS[stack[-1]])
 case "#": stack.append(HEX_DIGITS.index(stdin.read(1) or "0"))
 case "n": stdout.write("\n")
 case ",": stdout.write(chr(stack[-2] * 16 + stack[-1]))
 case "&": stack.extend(divmod(ord(stdin.read(1) or "\x00") % 256, 16))
 case "{": ret = (x, y)
 case "}": call_stack.append((*ret, d)); continue
 case ",": stdout.write(HEX_DIGITS[stack[-1]])
 call_stack.append((x + d, y + 1, d))
if __name__ == "__main__":
 if len(argv) < 2:
 exit("Intelligence error: no JollyScript program specified")
 with open(argv[1]) as f:
 prog = f.read().splitlines()
 execute(prog)
== Computational class ==
JollyScript can probably simulate a push-down automaton. It is probably Turing-complete.