Pure BF

Pure BF is a completely functional joke programming language based on brainfuck.

Details

Every first class value is a function of the type

   (Tape, World) -> (Tape, World)

A program technically doesn't have to be run after being compiled, as the language is purely functional, but the interpreter/compiler is encouraged to create an infinite tape, pair it with the world and apply the program to it, as that will make it possible to inspect the results of the code.

Commands

Pure BF only has two commands:

   ab  -- composes the functions a and b in the reverse of normal composition order.
   [a] -- creates the function that works like the identity function if the current cell is
          zero, and works like a[a] if it isn't.

Built-in functions

Pure BF has 6 built-in functions that aren't the identity function:

   > -- copies the input tape, but with the head moved a single cell forwards.
   < -- copies the input tape, but with the head moved a single cell backwards.
   + -- copies the input tape, but with the current cell being 1 higher.
   - -- copies the input tape, but with the current cell being 1 lower.
   . -- copies the world, but with the output containing the value of the current cell.
   , -- copies the world and the input tape, but with one character moved from the input stream to
        the current cell.

Any other character is the identity function.

Computational Class

Pure BF may seem equivalent to brainfuck. For example, here is a Pure BF function that converts any brainfuck program to a Pure BF program:

   ,[.,]

But while Pure BF may seem Turing-complete, it isn't. Pure BF is meta-Turing-complete in some sense, as it allows you to assemble Turing-complete programs, but a Pure BF program doesn't have loops. You might say that [a] is a loop, but it isn't. It creates a new function which loops, but that function cannot be executed in Pure BF. Pure BF is for that reason not very powerful.

Implementation

• Implementation in Haskell
• Implementation in Python which errs on the side of the joke
• Implementation in Ocaml which doesn't execute the computed function