Jonathan. Frech’s WebBlog

In­ter­pret­ing brain­fuck in C (#202)

Jonathan Frech,

Esoteric pro­gram­ming languages come in an as­ton­ish­ing magnitude of variety — golfing languages, Turing tarpits, obfuscation languages, one-time joke languages and plenty more. How­ev­er, among all of them, brain­fuck is by far one of the most in­trigu­ing to me — an elegant combination of syn­tac­tic brevity, apparent lack of func­tion­al­i­ty and the theorectical might of a Turing ma­chine.
Combined with its seemingly trivially realizable im­ple­men­ta­tion, I have im­ple­ment­ed brain­fuck in Python 2, a brain­fuck flavour in Python 2, and even writ­ten an in­ter­pret­er in DrRacket.
How­ev­er, like Cristofani writes in their The Epistle to the Implementors, writ­ing a sat­is­fac­to­ry brain­fuck in­ter­pret­er is no easy task.
Therefore I have designed another brain­fuck command-line in­ter­pret­er, writ­ten in pure C (brain­fuck.c).

Key features of this im­ple­men­ta­tion are a large tape size, source code pre-processing — in­struc­tion condensing and loop matching —, apt command-line flags and C ex­e­cu­tion speed.
For further de­tail on the in­ter­pret­er’s usage, com­pile the in­ter­pret­er (e. g. gcc -O2 brainfuck.c -o brainfuck) and run ./brainfuck -h.

To better demonstrate brain­fuck’s true power, I wrote a non-Kolmogorov-com­plex­i­ty pro­gram; a palindrome tester.

[ A palindrome tester written in brainfuck. ]
[ Jonathan Frech, 21st of August 2018.      ]
[ Tape layout: (STR ... STR NUL FLG ACC)    ]

,[>,]             read in STR
>+                set FLG to true
<<<[              while STR is of length at least two
 [<]>             go to the first byte
 [[>]>>+<<<[<]>-] transfer first byte to ACC
 >[>]<            go to last byte
 [->>>-<<<]       subtract last byte from ACC
 >>>[             if ACC is not zero
  <[-]            set FLG to false
  >-]             clear ACC
 <[<+>-]          move FLG over
 <<<<             go to last byte
]>>>.             output FLG

% echo ",[>,]>+<<<[[<]>[[>]>>+<<<[<]>-]>[>]<[->>>-<<<]>>>[<[-]>-]<[<+>-]<<<<]>>>.\!existence" > palindrome.b
% ./brainfuck -x palindrome.b
00000000: 00                                       .               

% echo ",[>,]>+<<<[[<]>[[>]>>+<<<[<]>-]>[>]<[->>>-<<<]>>>[<[-]>-]<[<+>-]<<<<]>>>.\!hubbibbuh" > palindrome.b
% ./brainfuck -x palindrome.b
00000000: 01                                       .