Interpreting brainfuck in C

2018-09-08, post № 202

brainfuck, C, programming, #interpreter

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                                       .

Extra assets: interpreting-brainfuck-in-c_development-version.c, interpreting-brainfuck-in-c_palindrome.b

Heapsort

2018-08-11, post № 201

C, programming, #algorithms, #sorting

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.

Read further …

Snippet #1

2018-07-14, post № 200

mathematics, #analysis, #formal calculation, #symbolic

$\nabla=\frac{\Delta}{\nabla}$

Read further …

Tau Day MMXVIII

2018-06-28, post № 199

C, programming,

                                     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.

Truth

2018-06-16, post № 198

mathematics, programming, Python, #logic, #proposition calculus

Proposition calculus deals with statements and the relation between statements, where each of them can only be in one of two states; $\vdash p\lor\lnot p$ . Therefore, when working with finitely many connected propositions, one can algorithmically determine all possible truth values of all atomic and thus connected propositions.

Truth is command-line tool which was written to precisely perform those computations; computing a logical expression’s truth value. Download link: truth.py
A list of all supportet operators can be seen by invoking the tool with a --help flag.
This project was inspired by Albert Menne’s Einführung in die Logik^[1]; the operator syntax used is similar to his, translated to be 7-bit-ASCII-compatible.

Truth can be used to either verify universally true statements, e. g. tertium non datur and a property of the replication, verum sequitur ex quodlibet.

-(p&-p) <-> 1  ,  1 <- p
1 0010   1  1     1 1  0
1 1001   1  1     1 1  1

Though not only absolute truth, but also complete relational equivalence between two expressions can be shown.

(p->q)|(r>-<s) <-> q|(r|s)&-(r&s)|-p
 01 0 1 0 0 0   1  00 000 01 000 110
 10 0 0 0 0 0   1  00 000 01 000 001
 01 1 1 0 0 0   1  11 000 01 000 110
 11 1 1 0 0 0   1  11 000 01 000 101
 01 0 1 1 1 0   1  01 110 11 100 110
 10 0 1 1 1 0   1  01 110 11 100 101
 01 1 1 1 1 0   1  11 110 11 100 110
 11 1 1 1 1 0   1  11 110 11 100 101
 01 0 1 0 1 1   1  01 011 11 001 110
 10 0 1 0 1 1   1  01 011 11 001 101
 01 1 1 0 1 1   1  11 011 11 001 110
 11 1 1 0 1 1   1  11 011 11 001 101
 01 0 1 1 0 1   1  00 111 00 111 110
 10 0 0 1 0 1   1  00 111 00 111 001
 01 1 1 1 0 1   1  11 111 00 111 110
 11 1 1 1 0 1   1  11 111 00 111 101

Complete contravalence can also be shown.

-(p/-p>-<0)|p->q<-r >-< p&-q&r
0 0110 1 0 101 01 0  1  001000
0 1101 1 0 110 01 0  1  111000
0 0110 1 0 101 11 0  1  000100
0 1101 1 0 111 11 0  1  100100
0 0110 1 0 101 01 1  1  001001
0 1101 1 0 010 00 1  1  111011
0 0110 1 0 101 11 1  1  000101
0 1101 1 0 111 11 1  1  100101

Extra assets: truth_example-logic-table.txt, truth_development-version-1.py, truth_development-version-2.py, truth_development-version-3.py, truth_development-version-4.py, truth_development-version-5.py, truth_development-version-6.py, truth_development-version-7.py