Interpreting brainfuck in C

Esoteric programming languages come in an astonishing magnitude of variety — golfing languages, Turing tarpits, obfuscation languages, one-time joke languages and plenty more. However, among all of them brainfuck is by far one of the most intriguing to me — an elegant combination of syntactic brevity, apparent lack of functionality and the theorectical might of a Turing machine.
Combined with its seemingly trivially realizable implementation, I have implemented brainfuck in Python 2, a brainfuck flavour in Python 2, and even written an interpreter in DrRacket.
However, like Cristofani writes in their The Epistle to the Implementors, writing a satisfactory brainfuck interpreter is no easy task.
Therefore I have designed another brainfuck command-line interpreter, written in pure C (brainfuck.c).

Key features of this implementation are a large tape size, source code pre-processing — instruction condensing and loop matching –, apt command-line flags and C execution speed.
For further detail on the interpreter’s usage, compile the interpreter (e.g. gcc -O2 brainfuck.c -o brainfuck) and run ./brainfuck -h.

To better demonstrate brainfuck’s true power, I wrote a non-Kolmogorov-complexity program; 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                                       .
Advertisements

Heapsort

Introduction

Continuing my journey implementing various sorting algorithms in C, in this post I am departing from the most well-known algorithms and implementing one of my personal favourites — heapsort.
Download the C source file here: heapsort.c.

Contrary to algorithms like quicksort which immediately jump into action sorting the given array, heapsort operates on a data structure called a heap which it efficiently transforms into a sorted list. However, as most arrays are not of the heap structure, heapsort first needs to transform a given array into a heap. Thus heapsort is a two-step process — first creating a heap and then sorting said heap.

Sorting can be applied to an infinite number of objects provided there is an order defined among them. However, not much is gained from changing the underlying value one is sorting which is why in this post I will only focus on sorting integers — technically even only integers in the C type sense; n\in\mathbb{Z},-2^{31} \leq n < 2^{31}.

The heap

A heap is a special type of binary tree that satisfies the heap property — every parent node’s value is not less than its child node’s (if existent) values. Furthermore, a heap is maximally filled at every level but possibly the last where the elements are as far left as possible.
From these properties it follows that the greatest value will be located at the root node.

One can also define a heap such that the root node will house the smallest element; such a heap would lead to a list sorted in descending order (more on that later).

      ( 86 )      
     /      \     
  (31)      (64)  
  /  \      /     
(20)(-4)  (17)    

A heap containing integers.

Continue reading

Tau Day MMXVIII

                                     int
        O=19,I=19;typedef long double f 
    ;long fac(long n){return n?n--*fac( 
  n):1;}f pow(f x,int p){return p--?x   
 *pow(x,p):1;}f sin(f x){f v=0;for      
(int           k=~0;++k                 
<=             O;)k%2&&                 
              (v+=(~-k                  
             %4?-1:1)*                  
             pow(x,k)                   
            /fac(k));                   
            return v                    
           ;}main()                     
           {f a=6,b                     
          =7, tau;                      
          for (int                      
         j=~0;++j                       
         <I;)sin(           tau         
        =a+(b-a)           /2           
        )>0? (b=          tau           
        ):(a=tau        )  ;            
        printf (      "%ca"             
        "u ~ %.*Lf",116,                
           O,tau);}                     

Try it online!

Happy tau day.