Tetra

Tetra

Paradigm(s)	String-rewriting
Designed by	User:Hakerh400
Appeared in	2022
Computational class	Total
Major implementations	Implemented
File extension(s)	.txt

Tetra is a string-rewriting esolang invented by User:Hakerh400 in 2022.

Definitions

A group is a list of other groups.

Syntax

Group is represented by parentheses encapsulating its content (the list of groups).

List of groups is represented by the concatenation of the groups from the list (no separators between them).

Source code consists of a list of groups. It represents the main list that gets rewritten.

Rewriting rules

In each step, find the first (left-most, outer-most) group g from the main list that contains an empty group as its first element. Replace g by two copies of itself with the first inner group (the empty one) removed.

Repeat this step until no more replacements are possible.

The output of a program is the total number of groups in the final list.

Example

We show the computation steps of the program (()(()())). We omit the leading empty groups of the main list for simplicity. Each time an empty group appears at the beginning of the main list, it stays there and adds to the number of the groups that will be counted at the end.

(()(()()))
((()()))((()()))
((())(()))((()()))
(()()(()))((()()))
(()(()))(()(()))((()()))
((()))((()))(()(()))((()()))
(()())((()))(()(()))((()()))
(())(())((()))(()(()))((()()))
(())((()))(()(()))((()()))
((()))(()(()))((()()))
(()())(()(()))((()()))
(())(())(()(()))((()()))
(())(()(()))((()()))
(()(()))((()()))
((()))((()))((()()))
(()())((()))((()()))
(())(())((()))((()()))
(())((()))((()()))
((()))((()()))
(()())((()()))
(())(())((()()))
(())((()()))
((()()))
((())(()))
(()()(()))
(()(()))(()(()))
((()))((()))(()(()))
(()())((()))(()(()))
(())(())((()))(()(()))
(())((()))(()(()))
((()))(()(()))
(()())(()(()))
(())(())(()(()))
(())(()(()))
(()(()))
((()))((()))
(()())((()))
(())(())((()))
(())((()))
((()))
(()())
(())(())
(())

The output is 32, because that many empty groups appeared at the beginning of the main string (we do not show them to save space).

Implementation

Implementation in Haskell:

type N = Integer
infixr 0 #
(#) = id

src :: String
src = "(()(()()))"

run' :: [N] -> N
run' xs = case xs of
  [] -> 0
  (x:xs) -> let
    (ys, _:zs) = break (== x - 1) xs
    in 2 ^ run' ys + run' zs

run :: String -> N
run = run' . tail . scanl
  (\n c -> n + if c == '(' then 1 else -1) 0

main :: IO ()
main = print # run src