Zpr’(h (#226)
I have designed and implemented a new esoteric programming language called Zpr’(h. It is a language 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 standard library, defining semantics for natural numbers, mappings, lists and logic. Furthermore, I used these semantics to define a lazy computation of all prime numbers — albeit executing at a rather slow pace.
Having finalized the language’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 complete — a useful feature for a programming language to have.
Pondering this question, I thought about how to show that Zpr’(h is indeed Turing complete — driven by hope that I have not created a primitively weak language. I briefly thought about implementing a Turing machine 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 implementation. Interpreting the brainfuck program ++[->+++<]>. — that is, multiplying two by three — takes a respectable twenty seconds at 4.00 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 implementation does not alias any byte sequences if long byte sequences are duplicated, the memory footprint rises to the unmanageable, easily blowing the 1 GiB provided by default. Increasing the available 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 complete, even though my brainfuck implementation 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 implementation, I attempted to fulfil another classical interpretation 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 standard library:
(µ .p) |> (head (filter p |N0))
In conclusio, I am convinced that Zpr’(h is Turing complete, if not very efficient — a common fate of esoteric programming languages.
As a side note, implementing the Ackermann-Peter function is fairly intuitive: zprh_ackermann-peter.zpr
I have also golfed in Zpr’(h; it is not the most terse language out there.