Smallest compiler possible in a turing complete language?

Question

Brainfuck is known for its extremely small compilers. I have a VERY small device that probably couldn't fit even the smallest of brainfuck compilers in its data. Is there an esoteric programming language that has even smaller compilers than brainfuck AND is a turing complete language? This is getting old, but feel free to still bring in your own answers, I will be checking

Quietus

Why do you need a compiler in the device? – Rationalize

it admittedly is not necessary – Quietus

a Turing-complete system is one that can simulate a Turing machine. Turing machine assumes unlimited memory capacity. You can't have unlimited memory capacity on your device, so even if language is turing complete in general, it will not be turing complete in your limited environment. – Merino

Have ever looked at URISC or the OISC page on esolang, with only one single instruction? I don't know you you can make a compiler with that ... :) – Bargello

@Merino correct me if I am wrong, but it seems the simpler a programming language is, the more memory it needs to get the job done. I appreciate your comment. – Quietus

@Quietus it's true. More complex instruction set we got, less memory we waste. – Merino

possible duplicate of How small can we make a compiler? – Acuna

Answer 1

I looked at the size of the Brainfuck compiler (~240 bytes in it's original form) and I doubt you're going to get smaller than that, it was designed to produce the smallest possible compiler (admittedly many years ago).

Although, from Wikipedia:

Except for its two I/O commands, brainfuck is a minor variation of the formal programming language P′′ created by Corrado Böhm in 1964. In fact, using six symbols equivalent to the respective brainfuck commands +, -, <, >, [, ], Böhm provided an explicit program for each of the basic functions that together serve to compute any computable function. So in a very real sense, the first "brainfuck" programs appear in Böhm's 1964 paper – and they were programs sufficient to prove Turing-completeness.

From the P'' page:

P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete.

So a compiler for P'', or a altered version of brainfuck that's equivalent, would be smaller and still turning complete.

However, if I don't follow the spirit of the question then the devices native instruction set will be Turing complete. An assembler will probably be too big but you could directly write the opcode values either into an executable file or a text file that is 'compiled' to an executable. That 'compiler' would probably be smaller. Although it's not a compiler in any real sense of the word, hence not following the spirit of the question.

Is this a real world question? If you don't have space for the compiler then where are your source and binaries going to go?

Related Question: What is the *conceptually* smallest *compiler* that can compile itself?

Katzir

Thank you! I will probably use P" I would vote up, but I cant because I don't have enough rep ;) – Quietus

its just a few bytes of storage I made, I don't know what I can do with it yet... – Quietus

Got twice smaller than this ;) – Sigmatism

An is realtively easy way to reduce the size of most brainfuck interpreters and still remain turing complete: Remove either the - or +. As long as the cells a wraping, you only need one of them (255 + are the same as a single - when you use 8 bit cells). And you can remove , and . when you don't need output and input handling (turing machine doesn't have input nor output). – Warship

Answer 2

I have found the smallest BF compiler expressed using lambda expressions in a Binary form (BLC).

The interpreter is exactly 112 bytes (which is iirc. the exact amount of bytes for the Hello World program in BF itself).

Sigmatism

Answer 3

MiniMAX

MiniMAX specification

Here is a complete DOS .COM executable interpreter for MiniMAX:

MOV SI,010E  # 3 bytes; 010E is the byte after the RET line
MOV DI,SI    # 2 bytes
MainLoop:    # assembler directive, 0 bytes
MOVSW        # 1 byte
LODSW        # 1 byte
ADD SI,AX    # 2 bytes
XCHG SI,DI   # 2 bytes
JNZ MainLoop # 2 bytes
RET          # 1 byte
<append program to interpret here>
             # Total: 14 bytes

Your device probably doesn't have exactly the same instruction set, but I can't imagine it being so very different. Probably less than 20 bytes still.

The downside is that MiniMAX programs that do anything useful are quite long, but if your only goal is to fit a TC interpreter on the chip, this'll do it for you.

Quarterdeck

Answer 4

Firstly, if your device has very limited memory to the point where it can not store a BF compiler, there's a very good chance that the instructions of any tiny Turing complete language would not have enough space to exist.

Regardless, you might want to look into OISCs (One-Instruction Set computers), not all of which are Turing complete, but most of them are. For instance, you could do something like this (Psuedocode):

# have memory of a certain size, M, set all to 1
SUBW a, b, i
    do {
        M[a] -= M[b]
    } while (--M[i] > 0)

that would be Turing complete. But again, using this is very counterintuitive, and instructions would take a lot of space.

Fox

Answer 5

TinyBF has half as many instructions as BF, so it should be simpler to create a compiler for it.

=   Switch direction (- <-> +) (default: +)
+   Change data in selected direction. BF equivalents: - +
>   Change cell in selected direction. BF equivalents: < >
|   Jump in selected direction. BF equivalents: ] [
==  Output. BF equivalent: .
|=| if switch is positive, =|=| if switch is negative.  Input. BF equivalents: ,

There are many other languages similar to BF that might also be viable choices.

Loree

Answer 6

An other candidate would be the Infinite Abacus of J. Lambek (1961). A predecessor of P"-machine with conditional jump.

An infinite number of counters and two instructions:

• n+ : increment counter at position n.
• n- else p : if counter at position n is positive decrement, else jump to instruction p.

You could easily replace the address n with Böhm's the > and <, but I think it will take more byte for the compiler (less instruction implies less cases).

Also you could replace the > and < of P" with direct addressing to reduce the compiler size.

An other candidate would be H. Wang's B-machine: a Turing machine with a non-erasable infinite tape.

Four instruction:

• Move tape head right and proceed to next instruction
• Move tape head left and proceed to next instruction
• Mark current tape cell and proceed to next instruction
• If current tap cell is marked then jump else proceed to next instruction

You can certainly define a variant using conditional loops rather than conditional jumps without loosing Turing completeness.

I do not know the size of these compilers in C, but interpreters in assembly are definitively smaller.

The draw back is the memory size, especially with Wang's write once tape.

Reparation

Answer 7

If you need something usable, check out a small FORTH implementation.

You can fit an entire operating system in 16 KB, but depending on your needs, you can go as small as you want: there exists an (extreme) 3-line implementation.

Chuck Moore, who continued to evolve the concept, claimed that he can write 1000 times less code than a typical C program for the same application.

At one time, he created a windowed operating system to fit into a mouse, to be connected to a TV (without a computer, that is).

Invented in the 70s, because punching cards was tedious and time consuming, Forth it is still in use by NASA nowadays.

Free books: Starting Forth and Thinking Forth

You can use AmForth on Arduino. Other Forth implementations.

Ardin