Jonathan. Frech’s WebBlog

Zpr⁠’⁠(⁠h (#226)

Jonathan Frech

I have designed and implemented a new esoteric programming lan­guage called Zpr⁠’⁠(⁠h. It is a lan­guage built upon iterated symbolic pattern matching, requiring the user to define their own semantics and interpreting them as computations.
Whilst developing Zpr⁠’⁠(⁠h, I implemented a rudimentary stan­dard library, defining semantics for natural numbers, mappings, lists and logic. Furthermore, I used these semantics to define a lazy com­pu­ta­tion of all prime numbers — albeit executing at a rather slow pace.
Having finalized the lan­guage’s specifications I began investigating its computational bounds. After all, testing primality is a primitive recursive relation. Thus, it a priori is not even clear if Zpr⁠’⁠(⁠h is Turing com­plete — a useful feature for a programming lan­guage to have.

Pondering this ques­tion, I thought about how to show that Zpr⁠’⁠(⁠h is indeed Turing com­plete — driven by hope that I have not created a primitively weak lan­guage. I briefly thought about im­ple­ment­ing a Turing ma­chine but quickly opted to implement a brainfuck interpreter — equivalent, since both can simulate each other.
After having written said brainfuck interpreter (zprh_brainfuck.zpr), I proceeded to test it only to realize that using byte-based pattern matching to implement a brainfuck interpreter in a functional manner does not lead to the most efficient im­ple­men­ta­tion. Interpreting the brainfuck program ++[->+++<]>. — that is, multiplying two by three — takes a respectable twenty seconds at 𝟦.𝟢𝟢 GHz. Yet more excruciatingly, adhering to commutativity and interpreting +++[->++<]>. yields the same correct numerical result, although at a steep slowdown to over three minutes.
Time constraints are not the only factor — since the current Zpr⁠’⁠(⁠h im­ple­men­ta­tion does not alias any byte sequences if long byte sequences are duplicated, the memory footprint rises to the unmanageable, easily blowing the 𝟣 GiB provided by default. Increasing the avail­able memory most likely not make much of a difference given the aforementioned exponential behavior.
Thus, testing larger brainfuck programs appears not to be feasible due to computational resource limitations. Nevertheless, I am now fairly certain of Zpr⁠’⁠(⁠h being Turing com­plete, even though my brainfuck im­ple­men­ta­tion may not be correct.
To input brainfuck source code into the above interpreter, I used this translator.

Not being satisfied with a nigh untestable brainfuck im­ple­men­ta­tion, I attempted to fulfil another classical in­ter­pre­ta­tion of computability; recursive functions. As seen above, primitive recursive functions can already be modelled, leaving only the existence of µ-recursion open; a one-liner using the stan­dard library:

(µ .p) |> (head (filter p |N0))

In conclusio, I am convinced that Zpr⁠’⁠(⁠h is Turing com­plete, if not very efficient — a common fate of esoteric programming languages.

As a side note, im­ple­ment­ing the Ackermann-Peter function is fairly intuitive: zprh_ackermann-peter.zpr
I have also golfed in Zpr⁠’⁠(⁠h; it is not the most terse lan­guage out there.