logfuck
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Palaiologos |
| Appeared in | 2025 |
| Computational class | Turing-complete |
| Reference implementation | Unimplemented |
| Influenced by | Brainfuck |
| File extension(s) | .lf |
Synopsis
Brainfuck where things are O(log n) rather than O(n). An interesting way of solving the problem of Brainfuck's relative verbosity not by introducing RLE or similar operations (which make Brainfuck still struggle with linear-time copy and addition) but by changing the underlying data structures and their exposed format.
Spec
The language operates on an infinitely downwards-growing binary tree. The state of the program is the tree, the currently seen node and the 16-bit unsigned numbers associated with each node. The following instructions are supported:
- ^ - Go to the parent node.
- < - Descend to the left child, creating with zero if necessary.
- > - Descend to the right child, creating with zero if necessary.
- v - Pop out the lowest bit of the current node's value.
- . - Take lowest 8-bits of the node's value and print it as an US-ASCII character.
- , - Input a byte and consider it the current node's value. On EOF writes 0xFFFE.
- [A;B] - If the lowest bit of the current node is zero, execute A. Otherwise execute B.
- (A) - Execute A until the current node's value is non-zero.
- 0 - Shift in a zero in the current node's value.
- 1 - Shift in an one in the current node's value.
Interpreters
Initial attempt in Perl by Kamila Szewczyk. Non-spec behaviour is printing the current node's value at exit.
#!/usr/bin/perl
use strict;
use warnings;
sub n{my$v=shift//0;{v=>$v,l=>undef,r=>undef,p=>undef}}
sub l{my$n=shift;$n->{l}//=n(0);$n->{l}{p}=$n;$n->{l}}
sub r{my$n=shift;$n->{r}//=n(0);$n->{r}{p}=$n;$n->{r}}
sub pd{my($c,$s)=@_;my($p,$d,$m)=($s,1,-1);while(++$p<@$c&&$d){$d+=($c->[$p]eq'[')-($c->[$p]eq']');$m=$p if$c->[$p]eq';'&&$d==1&&$m<0}die"Parse error"if$d||$m<0;(join'',@$c[$s..$m-1]),(join'',@$c[$m+1..$p-2]),$p-1}
sub pl{my($c,$s)=@_;my($p,$d)=($s,1);$d+=($c->[++$p]eq'(')-($c->[$p]eq')')while$p<@$c&&$d;die"Parse error"if$d;(join'',@$c[$s..$p-2]),$p-1}
sub ex{my($s,$pr)=@_;local$_;my@c=split//,$pr;for(my$p=0;$p<@c;$p++){$_=$c[$p];/^(\^|<|>|0|1|\[|\(|\.|,)$/||next;/^(\^)/&&do{$s->{c}=$s->{c}->{p}if$s->{c}->{p};next};/^</&&do{$s->{c}=l($s->{c});next};/^>/&&do{$s->{c}=r($s->{c});next};/^0/&&do{$s->{c}->{v}=($s->{c}->{v}<<1)&0xFFFF;next};/^1/&&do{$s->{c}->{v}=((($s->{c}->{v}<<1)|1)&0xFFFF);next};/^\[/&&do{my($a,$b,$e)=pd(\@c,++$p);ex($s,($s->{c}->{v}&1)?$b:$a);$p=$e;next};/^\(/&&do{my($co,$e)=pl(\@c,++$p);ex($s,$co)while$s->{c}->{v};$p=$e;next};/^\./&&do{print chr($s->{c}->{v}&0xFF);next};/^,/&&do{my$i=getc STDIN;$s->{c}->{v}=defined$i?ord($i)&0xFFFF:0xFFFE;next}}}
my$r=n(0);my$s={c=>$r,r=>$r};ex($s,$ARGV[0]||die"Usage: $0 '<program>'\n");print$s->{c}->{v},"\n"