Aubergine

Aubergine

Paradigm(s)	imperative
Designed by	User:Boily
Appeared in	2008
Computational class	Turing complete
Reference implementation	See below
Influenced	Aubergine derivatives
File extension(s)	.aub

Aubergine is a minimalist language with 4 instructions, 4 variables, and a single constant, created by User:Boily in 2008.

General syntax

An Aubergine program mixes instructions and data in the same space, as a list of integers. Before execution by an interpreter, the script is split character-wise, then their ASCII integer value is taken.

Each cell can hold any integer value, even negative ones.

Instructions consist of three consecutive integers, where the first indicates which kind of instruction is to be executed, and the rest tells what is to be manipulated.

Variables

a and b

"a" and "b" are two multi-purpose variables. They initially are set to zero.

These variables can be used as pointers. When written "A" and "B", they point to cells in the program space. For example: if a equals 3, then A equals the integer at the program's fourth space. If a is negative or greater than the length of the program, using A is a fatal error.

Instruction pointer

The letter "i" represents the instruction pointer. It is automatically incremented by 3 after every instruction execution. Initially, "i" equals zero, which is also the first program cell.

You can use "i" in the same manner as "a" and "b". Note that there is no indirection with "i", i.e. "I" is not valid.

Outside world

"o" -- short for Outside -- is only valid with the assignment instruction. When used as first parameter, it outputs an integer converted to a character to the screen. As a second parameter, it inputs a single character converted to an integer.

One

The "1" constant returns the integer 1. It cannot be used as an instruction's first parameter!

Instructions

Assignment

Equal (=) puts the second parameter's value into the first parameter.

Putting either a negative value, or one which is greater than the program's length, into "i" halts the program without error.

Increment

Plus (+) increments the first parameter by the second parameter's value.

Decrement

Minus (-) acts as plus, but decrements the first parameter.

Conditional jump

Colon (:) is a conditional jump. If the second parameter's value is different from zero, then the instruction pointer is set to the value of the first parameter. Otherwise, it does nothing.

Even if the jump was successful, "i" is still incremented by 3 after the instruction.

Examples

Hello, world!

=aA-a1=oA=bi+b1-Ab-bb:bA+B1=iBGolf by Quintopia
!dlroW ,olleH

(Ensure it is exactly 62 bytes long by adjusting the length of the non-code part in the middle before running it.)

Quine

-a1+a1=oA=Bi-BA:bB=ia	

The tab character at the end is part of the program. Be sure to copy it when testing this example.

Truth-machine

=Ao-b1+bi=oA=bB-bA:Ab=ia

Cat

=ii=oo=ib

Count up forever (in unary)

=A1+i1
=bi-b1-b1:Ba+b1=oB+A1=aA-a1-ii               =oB-a1-ii

(Ensure it is exactly 61 bytes long by adjusting spaces in the middle before running it.)

Computational Class

If we take "each cell can hold any integer" to mean that the registers and program cells are unbounded, which seems quite reasonable, then we can translate any 2-register Minsky machine to an Aubergine program, showing that the language is therefore Turing-complete.

Turing-completeness proof sketch

(Note, the following is untested. There may very well be bugs in it.)

For concreteness, we will say that the instructions of our Minsky machine are:

INC R0
IF R0 == 0 THEN GOTO label ELSE DEC R0
INC R1
IF R1 == 0 THEN GOTO label ELSE DEC R1

The two registers of the Minsky machine (R0 and R1) will be stored at locations 0 and 1 in the program. Start the program with:

=Ab=a1=Ab

This sets R0 and R1 both initially to zero. (Just don't jump back to the beginning, because the initial =A is now gone.) Then translate as follows:

• INC R1 becomes =b1+B1.

• IF R1 == 0 THEN GOTO <label> ELSE DEC R1 is translated in two phases; first it becomes:

   =a1+aa+aa+aa+aa+aa+aa+aa+aa-a1+ai=b1:aB=ia...GOTO label...=b1-B1

This puts g+249 into a, where g is the location of the :. If R1 is not zero, execution will continue at g+249. The space between g+6 and g+249, indicated by ...GOTO label... in the schema above, should be used to jump to the desired label. There will be 81 instructions' worth of space there to compute the label and jump to it, which should be plenty for most labels (and more room can be obtained simply by making the initial a a bigger multiple of three.) For example, to jump unconditionally to location 33 (the 11th instruction), we can fill that ...GOTO label... gap with

   =a1+aa+aa+aa+aa+aa+a1=ia

padded with a sufficient number of spaces (or whatever else you like.)

• INC R0 becomes =b1-b1+B1.

• IF R0 == 0 THEN GOTO label ELSE DEC R0 is identical to its R1 counterpart, with =b1 replaced with -bb.

Implementations

• Reference interpreter in Ruby. Buggy: the or on line 15 should be an and, and against all logic, the < on line 44 should be a <=.
• Aubergine/aubergine.hs, an interpreter in Haskell by Chris Pressey.
• Aubergine/aubergine.py, an interpeter in Python by User:Quintopia.
• aubers, an interpreter in Rust by User:Challenger5.