/ˈæmbiːɛf/
/ˈæmbiːɛf/ is a brainfuck derivative created by User:ais523 in 2012. It was based on its author's like for the concept of Java2K but huge dislike of its actual execution, and also because it's nontrivial to determine its computational class. Its name exists only when pronounced; /ˈæmbiːɛf/ is how its name is rendered in IPA (and thus is used as the name of this article). It officially cannot be spelt, however (it's intentionally ambiguous between "Ambi-F" and "Am-BF", and as such both are incorrect). As a result of this, it is also impossible to determine whether or not its name starts with a capital letter.
Language definition
/ˈæmbiːɛf/ has 4 commands:
| Command | Meaning |
|---|---|
[ |
Jump to the matching ] if the current tape cell is 0
|
] |
Jump to the matching [ if the current tape cell is not 0
|
+ or - |
Randomly either increment or decrement the current tape cell |
< or > |
Randomly move the current tape cell pointer either left or right |
Any other character is a comment; two of the commands have two characters to represent them. There is no obvious reason to use one or the other in input programs, in keeping with the spirit of the language.
The tape used is similar to brainfuck's; however, every cell can contain a bignum value, and the tape is infinite in both directions.
Discussion
It's easy to write code to set the current cell to 0, or to ±1, with probability 1: [+] and [+]+ respectively. It is probably also possible (but difficult) to reliably set a cell to ±2. (Odd numbers cannot reliably be distinguished from each other, though; nor can nonzero even numbers reliably be distinguished from each other.) Just with 0 and ±1, though, the addition of arbitrary control flow (say, by adding a goto-if-nonzero instruction and jump targets to the language) would make the language Turing-complete, by simulation of a Minsky machine. The idea is to represent two counters (here, "3 4") on the tape like this:
0 0 ±1 0 ±1 0 ±1 ±1 0 ±1 0 ±1 0 ±1 0 0 0
It's possible to (via dead-reckoning) always determine whether you're on an odd or an even tape element, and therefore to seek to a random end of one or the other counter (by moving to that parity, then doing << until you get a 0, then << until you don't get a 0. You can then do > twice in order to determine which end you're on and where you are with a reasonable probability; if you get a 0 then a 0, you're beyond the outside end, if you get a ±1 then anything, you're near the inside end (and know exactly where you are), if you get a 0 then a ±1 you don't know where you are but you can repeat this process until you do. This allows for a reliable increment.
For a decrement-and-zero-test, seek to the ±1 at the outside end of the relevant counter, then zero it, then seek to the nearest ±1 (by repeatedly moving 1 space until you reach it), tracking the parity. The parity of the cell you were at reveals whether you set the counter to 0 or not.
If one of the counters is 0, the above rules don't work. That counter can be incremented by seeking to two spaces beyond a random end of the other counter (obtained by doing [<<] when on the counter), moving one space randomly, changing that cell, then moving another space; if the result is ±1, it worked, otherwise seek to the cell you just changed (it's the only one on that parity, so you can find it easily), zero it, and try again. Meanwhile, if one of the counters is 0, you can increment or decrement-and-zero-test the other counter by incrementing the counter at 0, operating on the other counter, then decrementing the original counter again.
Finally, if both counters are 0, the tape must be blank, so you can increment one simply by treating the current tape location as the new origin and starting from there.
Despite the above construction, though, there are still doubts about the Turing-completeness of the language. The problem is that, with the very limited arithmetic and storage capabilities available, it's not obviously possible to construct arbitrary control flow out of [] loops; the standard method of reserving alternate cells on the tape as temporaries doesn't work, as doubling all horizontal movement changes the semantics of an /ˈæmbiːɛf/ program. It may be possible to do it some other way, though.
Implementation
An exemplary implementation in Common Lisp constitutes the following. Please note that the memory, with the language wanting in an output facility, is at the end of the program printed to the standard output in unspecified order.
(defun interpret-/ˈæmbiːɛf/ (code &aux (position 0))
"Interprets the /ˈæmbiːɛf/ CODE and returns NIL."
(declare (type string code) (type fixnum position))
(symbol-macrolet ((character (the character (char code position))))
(let ((pointer 0)
(memory (make-hash-table :test #'eql)))
(declare (type integer pointer) (type hash-table memory))
(setf *random-state* (make-random-state T))
(loop while (< position (length code)) do
(case character
(#\[ (when (zerop (gethash pointer memory 0))
(loop with level of-type fixnum = 0 do
(incf position)
(when (>= position (length code))
(error "No matching ']' found."))
(case character
(#\[ (incf level))
(#\] (if (zerop level)
(loop-finish)
(decf level)))
(otherwise NIL)))))
(#\] (unless (zerop (gethash pointer memory 0))
(loop with level of-type fixnum = 0 do
(decf position)
(when (minusp position)
(error "No matching '[' found."))
(case character
(#\] (incf level))
(#\[ (if (zerop level)
(loop-finish)
(decf level)))
(otherwise NIL)))))
((#\+ #\-) (if (zerop (random 2))
(incf (gethash pointer memory 0))
(decf (gethash pointer memory 0))))
((#\< #\>) (if (zerop (random 2))
(incf pointer)
(decf pointer)))
(otherwise NIL))
(incf position))
;; As no output facility exists, print the memory.
(maphash
#'(lambda (cell-index cell-value)
(declare (type integer cell-index cell-value))
(format T "~&cell[~d] = ~d" cell-index cell-value))
memory))))