Esoteric Programming Languages

Dr. Mathias Elsner

Remaining sane in insane times

A Masterpiece of Theory!

If INTERCAL is the jocular mother of all esoteric programming languages, P'' with its cryptic radicalism, can be described as their grandmother. This holds true, however, not merely with regard to the esolangs, but to a certain extent to all modern productive programming languages. While being tersely reductionistic, it is nevertheless Turing-complete. As the very first 'goto-less' language, it was the conceptual pioneer of the paradigm of 'structured programming'. The design of P'' represents a milestone in theoretical computer science.


My humble implementation of P'' tries to adhere as closely as possible to the syntactic and semantic rules layed out by Corrado Böhm in his seminal 1964 paper "On a family of Turing machines and the related programming languages" [1].


P'' is a language that was devised for theoretical purposes. It was never meant for practical programming. Thus, implementing it strictly, will inevitably be associated with significant drawbacks from a practical perspective. Most previous implementations of P'' try to circumvent these shortcomings (more on those below). Any 'augmented' implementations might, however, not be considered 'true' implementations of P''.


The conceptual environment for P'' is a Turing Machine with a one way infinite tape, and any finite aphabet {c0, c1, ..., cn} where n ≥ 1 and c0 is the blank symbol of the tape. The tape is scanned and/or written to via a read/write head positioned over a given memory cell. P'' (double prime) is a context-free, drastically sparse sub-language of the general programming language P' (single prime) which respectively is equivalent to the entire Turing Machine family.


Böhm's paper goes on to prove, that even this reduced language has the faculty of computing all the partial recursive functions. By using bijective base-k notation for the tape alphabet, Böhm could construe his proving formulas to be independent of the number n of symbols in the tape memory alphabet.


P'' is defined by the following formation rules:

  1. λ, R are words of P'' (axiom of atoms);
  2. if α, β are words of P'' so is αβ (composition rule);
  3. if α is a word of P'' so is (α) (iteration rule).

The finite alphabet Ω'' (of P'') consists of only four characters, i.e Ω'' = { λ, R, (, ) }. These correspond to the instructions:

  • R : Shift the head one square to the right, if any.
  • λ : Replace the scanned symbol ci with ci+1 mod (n+1) and shift the head one square to the left.
  • ( : Enter a cycle inside the parenthesis, if current cell ≠ c0.
  • ) : Exit the cycle, if current cell = c0, and continue to execute the next instruction outside the parenthesis.

It is important to keep in mind that the numerical contents of a cell 'wrap-around'. Thus cn+1 = c0.


Now let us take a look at three major practical limitations implied by this restricted ruleset of P'':

  1. To decrement the current cell containing ci , the program has to execute [λR]n, i.e. n-times λR in order to wrap around to ci-1. If the machine's cells were meant, for example, to store one byte, decrementing the current cell would result in the necessity for 255 repetitions of λR, which is computationally ineffective to implement, and a chore to code.
  2. The cumbersome way of decrementing a cell in P'' moreover renders one of the language's most noteable features, i.e. the 'while' loop for directing program flow, rather verbose to employ in actual code. Many applications of '(' ... ')' presuppose an iterator in a neighbouring cell, which is decremented by code within the parentheses until '0' is reached for exiting. With 'decrement by 1' amounting to 255 x 'λR' this will not be readily embraced during coding.
  3. Since P'' was devised within a mathematical proof in the field of theoretical computer science, there was no need for input / output functions. Thus, in P'' as originally devised, there is neither a method for user interaction, nor for displaying a program's result.

Urs Müller's much later language Brainfuck, dating from 1993, often is described as a simple homologue to P''. However, this is merely true on a conceptual level, yet untrue with regard to syntactical construction. Although there are equivalents to elements of Ω'' in the Brainfuck instruction alphabet, i.e.:

  • ' [ ' ≡ ' ( '
  • ' ] ' ≡ ' ) '
  • ' > ' ≡ ' R ' ,

three other Brainfuck instructions need composite equivalents in P'', i.e.:

  • ' + ' ≡ ' λR '
  • ' - ' ≡ ' [λR]n '
  • ' < ' ≡ ' [λR]nλ ' ,

For the sake of readability, even Böhm himself used what he called 'sub-programmes' in his code examples for preparing his proof, which effectively amount to the "missing" Brainfuck instructions, i.e.

  • r ≡ λR ,
  • r' ≡ [λR]n ,
  • L ≡ r'λ .

Thus a routine of P'' code might read in shorthand » T- ≡ (r) R2 ( (r' L r R) R) L «.


Moreover, equivalents of the Brainfuck input/output instructions ' , ' and ' . ' are entirely absent from P''. In consequence, strictly implemented P'' would be rather useless, even for demonstration purposes. Impractical, as it may be in it's own right, Brainfuck is a highly 'practified' descendant of P'', which remains a theoretical masterpiece, nonetheless.


Bear in mind, that, for any given program in any other programming language, there will exist a program Pf ∈ P'' with the equivalent computational capabilities, while this is being achieved allowing for only four instructions!




[1] ICC Bulletin, Vol. 3, No. 3, July 1964



P'' implemented:

Some compromises...

  1. Böhm's Turing machine has a left-infinite, right-bounded storage tape. Due to the cultural convention of reading from left to right, the indexing of the memory in the current implementation is carried out in mirror image.
  2. To simplify the display of ASCII characters, a memory alphabet of 8 bits (0-255) was chosen.
  3. P'' actually has no output function. However, I implemented an output command in analogy to Brainfuck, because otherwise you would not be able to comprehend and check program behavior. With the instruction 'ô' the content of the current memory cell is output as an ASCII / UTF-8 character. Purists may do without this command ;-)

The very restricted instruction set of P '' was otherwise fully maintained. No further instructions were generated from possible subroutines. No one will come up with the idea of ​​using P'' for productive programming anyway...


If you actually want to see a 'larger' program at work, you can check out my P'' version of »99 bottles of beer« But maybe only after running the example program below. Or maybe after a few beers.


Write your own code here:

Sample code can be found further down on this page.


    

; or

; or

ms



◀ Memory tape (excerpt)

Output ▼


    

Sample Code:

(Click Button ▼ to copy sample code to RUN area ▲)

λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRô
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRô
λRλRλRλRλRλRλRô
ô
λRλRλRô
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRô

Playful to the max:

P'' may even be implemented in 'Scratch', the symbolic programming language designed at MIT for teaching computer science to youths:


Scratch

Click thumbnail to view video.

Impressum ©2020 mathias.elsner

Sorry, these pages don't scale well on mobile devices...

Valid XHTML | CSS

I'm en route to extinction