BFI

BFI is a esoteric programming language invented by User:Morex in 2009, and can be defined as a Brainfuck with procedures and recursion but without square brackets. BFI is the acronym of "BrainFuck Itself", as a reference to its recursive nature.

Description

Inspiration for creating BFI was taken from the Brainfuck and GASOIL languages.

As in GASOIL, the main idea is to test a language (and interpreter) which instead of loading the program in a fixed memory, loads the program in a "program stack". This way the program is freeing memory as it is executed (instructions are not available anymore once they are executed (except calling a subroutine more than once)). There is no "Instruction Pointer". Recursion is the only way to have loops. BFI has recursion without a call stack or return stack (Infinite recursive loops do not overflow).

Environment

The runtime environment should have the following:

• Program stack: Procedures are loaded backwards on this stack. Initially only the first procedure is loaded.
• Array of memory cells, each initially set to zero.
• Data Pointer: A pointer to memory cells initially set to zero.
• Routine pointer, initially set to zero, pointing to the main procedure.

Commands

• > Move the data pointer to the right
• < Move the data pointer to the left
• + Increment the memory cell under the data pointer
• - Decrement the memory cell under the data pointer
• . Output the character signified by the cell at the data pointer
• , Input a character and store it in the cell at the data pointer
• } Increment the routine pointer
• { Decrement the routine pointer
• ? Load to program stack the procedure pointed to by the routine pointer if the cell under the data pointer is not 0

It should be noted that the commands "[" and "]" of brainfuck are not available.

In a program file, subprograms (procedures) are delimited by semicolon. The rest of the characters are ignored. Procedures are referenced by their relative position in the file, with zero corresponding to the first one, one to the second one, and so on.

When running, in each step the interpreter pops an instruction from the program stack and executes it. The execution stops when the program stack is empty.

Computational class

The BFI language is Turing-complete, meaning that it is in the same computational class as universal Turing machines. This is true because it is easy to convert every Brainfuck program to BFI (a Brainfuck to BFI translator was implemented) and Brainfuck is Turing-complete.

This, plus its dearth of commands, makes it a Turing tarpit.

Examples

Hello, world!

++}}??{?>++.>+.+++}?..+++.>++.<<+++???.>.+++.------.--------.>+.>.;
>+++}?>++??{>+++>+<<<<-?;
++++ 

Bubble sort

 ***Here is a program that bubblesorts its input and spits it out
 ***This BFI program is a translation of an uncredited Brainfuck program from The Brainfuck Archive
 >>>>>,+}?<<<}?;
 >>>,+?;
 <<<}?>>>}?>>>}}?{{{{<<<?;
 >>>}}}}?<<<}?>>}?<}?{{{{{{{<<?;
 -.}?{?;
 -?;
 >>>?;
 -<<<-<+>}}}}?{{{{>>?;
 <?;
 >>>+<<<-?;
 >+>>>+<<<<-?;
 >?;
 ***This is the original Brainfuck code:
 ***from http://esoteric.sange.fi/brainfuck/bf-source/prog/SORT.BF
 ***>>>>>,+[>>>,+]<<<[<<<[>>>[-<<<-<+>[>]>>]<<<[<]>>[>>>+<<<-]<[>+>>>+<<<<-]<<]>>>[-.[-]]>>>[>>>]<<<] 

External resources

• BFI 0.81 - a BFI interpreter in Excel.
• BF2BFI 0.81 - a Brainfuck to BFI translator in Excel.