Metatape
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:HactarCE |
| Appeared in | 2017 |
| Memory system | cell-based |
| Computational class | Turing complete |
| Reference implementation | Metatape |
| File extension(s) | .mt |
Metatape is an imperative esoteric programming language with just two data types: null and tape. A pointer moves along an infinite tape, which is initialized to null values. The pointer can then "enter" a cell, replacing the null value with a new tape, which is also initialized to null values. While many esoteric programming languages feature a minimalist instruction set while allowing such high-level abstractions as integers or strings, Metatape only allows data to be encoded in the structure of nested tapes.
Language overview
The tape is infinite (or dynamically allocated), with all cells initialized to null. The pointer can move left and right using the < and > instructions respectively. The e instruction "enters" the current cell, positioning the pointer at the most recently-pointed-to cell of that tape; if the current cell is null, it is replaced with an empty tape. The x instruction "exits" the current tape, first saving the pointers position on it; if there is no "outer" tape, a new one is created and the current tape is placed inside it.
Conditional statements are created using ( and ), with | as an optional "else" between them. Unconditional loops are created using [ and ]. Loops and conditions can be interwoven; e.g. [...(]) is a common "do ... while" construct.
Instructions
Metatape's instructions are fairly primitive, so each is assigned a single character.
| Char | Mnemonic | Description |
|---|---|---|
.
|
No-op | No operation |
<
|
Left | Move the pointer one cell to the left |
>
|
Right | Move the pointer one cell to the right |
e
|
Enter | Enter the current cell |
x
|
Exit | Exit the current cell |
n
|
Null | Set the current cell to null |
?
|
Random | Generate a random bit; if that bit is `0`, do `n` |
(
|
If | If the current cell is null, skip forward to the matching | or ). If not, then no-op.
|
|
|
Else | If not reached via (, skip forward to the matching )
|
)
|
End If | No operation |
[
|
Loop | No operation |
]
|
End Loop | Skip backward to the matching [
|
i
|
Input | Read a single bit from the input buffer; if that bit is 0, do n
|
o
|
Output | If the current cell is null, append 0 to the output buffer; otherwise append 1
|
h
|
Halt | Halt the program (breakpoint) |
| Pattern | Description |
|---|---|
// ...
|
Line comment |
/* ... */
|
Block comment |
@ sub { ... }
|
Subroutine definition |
{ ... }
|
Block |
!{ sub }
|
Call |
f{ ... }
|
Fork |
Comments
Metatape has C-like comments; all characters between // and the next newline are ignored, and all characters between /* and the next */ are ignored.
Blocks
Code may be surrounded by braces {} for logical grouping, or to pass a sequence of instructions as a single instruction to a command like f. Conditions and loops may not cross a { or } boundary, and subroutines cannot be defined inside a block.
Subroutines
A subroutine is defined using the following pattern:
@ subroutine name { subroutine code }
Subroutines can be called using the ! instruction:
!{ subroutine name }
The surrounding braces {} may be omitted if the subroutine name consists of only a single character:
!a
Forks
The f{ ... } instruction saves the current state of the tape (call this "state A") before executing the instructions inside the braces. After the instructions have been completed (call the resulting tape "state B"), the saved state A is restored, except that the current cell of state A is replaced with the current cell from state B.
For example, this code copies the cell inside the cell that is two spaces to the left into the current one.
f{<<e}
The f instruction is mostly useful for copying data and sandboxing destructive subroutines.
Similar to !{ ... }, the surrounding braces {} may be omitted if there is only a single instruction inside the fork:
f>
Program structure
A Metatape program consists of a single block of code, which may contain subroutine definitions.
Execution begins at the top of the file. At the end of a subroutine, execution resumes from the call point. When the end of the file is reached, execution halts and the program exits.
Metatape is case-sensitive. All whitespace is ignored, with the following exceptions:
- An inline comment (starting with
#) terminates at the end of a line - Consecutive whitespace within subroutine names is replaced with a single space, and all leading and trailing whitespace is removed
Unrecognized instructions and calls to nonexistent subroutines produce an error, preferably before execution.
Examples
Hello, world!
// A simple program that prints "Hello, world!"
ex>
// The tape head is now pointing to a null cell, with a non-null cell to the
// left.
!H !e !l !l !o !_ !w !o !r !l !d !!
// Each of these functions moves left for a 0 bit and right for a 1 bit to
// output the ASCII value for the given character.
@ H { o<o>oo<o>ooo }
@ e { o<oo>oo<o>o<o> }
@ l { o<oo>o<oo>oo }
@ o { o<oo>o<oooo> }
@ _ { oo<o>ooooo }
@ w { o<ooo>o<ooo> }
@ r { o<ooo>oo<o>o }
@ d { o<oo>oo<o>oo }
@ ! { oo<o>oooo<o> }
Cat
A cat program writes its input directly to its output.
Non-terminating
This cat prints null characters `0x00` forever after the input ends.
[exio]
Terminates with null after EOF
This cat prints a null character `0x00` and then exits at the end of the input or at the first null.
// For each byte ...
[
// Leave a flag up and to the left. We'll reset this flag if we see a 1
// anywhere in the input byte, so it will only remain set if the byte was
// all zeros.
ex>e
// Leave a marker eight cells to the right.
ex<<<<<<<<
[eexix>(n|])
// Input bits until you reach that marker, and then set the marker to null.
// Go back to the first bit that was inputted.
[<(])
// For each bit ...
[>(
// Output it and reset the flag if the bit is 1.
eo(xx<n>e|x)
])
// Loop again if the flag was reset (i.e. the last byte was null).
xn<(|])
The same program, in minified form:
[ex>eex<<<<<<<<[eexix>(n|])[<(])[>(eo(xx<n>e|x)])xn<(|])
Terminates with no null after EOF
This cat exits at the end of the input or the first null but does _not_ print a null character. This is the behavior of Unix `cat`.
// For each byte ...
[
// Leave a flag up and to the left. We'll reset this flag if we see a 1
// anywhere in the input byte, so it will only remain set if the byte was
// all zeros.
ex>e
// Leave a marker eight cells to the right.
ex<<<<<<<<
// For each bit (eight times) ...
[
// Input a bit.
eexi
// Reset the flag if the bit is 1.
(xx<n>e|x)
// Repeat if we haven't reached the marker.
>(n|])
// Check the flag. If it is still set, then the current byte is null, so
// exit the program (break out of the loop).
x<(|>e
// Return to the start of the byte.
[<(])
// Output each bit.
[>(eox])
// Return to the start of the program (and close the condition on line 19).
xn<])
The same program, in minified form:
[ex>eex<<<<<<<<[eexi(xx<n>e|x)>(n|])x<(|>e[<(])[>(eox])xn<])
99 Bottles
Printing the lyrics to "99 Bottles of Beer" is the archetypal esoteric programming language challenge.
Here is a mostly-minified version of the program; the full program, including comments, can be found in the GitHub repository.
!{=9}>!{=9}>[
!{print bottle count}!{" bottles of beer on the wall"}!{newline}
!{print bottle count}!{" bottles of beer"}!{newline}
!{"Take one down, pass it around"}!{newline}
>(n<|<!{dec bottles}>f{ << !{=1?} ( < !{=0?} ) }<
!{print bottle count}!{" bottles of beer on the wall"}!{newline}
!{newline}
])
!N!o!{" bottles of beer on the wall"}!{newline}
!{newline}
!N!o!{" bottles of beer on the wall"}!{newline}
!N!o!{" bottles of beer"}!{newline}
!G!o!_!t!o!_!t!h!e!_!s!t!o!r!e!,!_!b!u!y!_!s!o!m!e!_!m!o!r!e!{newline}
!9!9!{" bottles of beer on the wall"}!{newline}
@ dec bottles { f{<!{=0?}}(<<!{dec}>!{=9}>|<!{dec}>)n }
@ print bottle count { f{<<!{=0?}}(n|<<!{printdigit}>>)<!{printdigit}> }
@ " bottles of beer" {
!_!b!o!t!t!l!e >(<|<!s) !_!o!f!_!b!e!e!r
}
@ " bottles of beer on the wall" {
!{" bottles of beer"}!_!o!n!_!t!h!e!_!w!a!l!l
}
@ "Take one down, pass it around" {
!T!a!k!e!_ >(<!i!t|<!o!n!e) !_!d!o!w!n!,!_!p!a!s!s!_!i!t!_!a!r!o!u!n!d
}
@printdigit { e>oo<oo<<<(eox|o)>(eox|o)>(eox|o)>(eox|o)x }
@ dec { e>f{<x!{=0?}}(n<|<[(e(x|exx<]))enx!{_trim leading zeros})x }
@ _ trim leading zeros { [<(])[>(e(x|xn])[>(])<|ex) }
@ =0? { f{ee(|x<(|nx|n)|n)} }
@ =1? { f{ee(x<(|nx|n)|n)} }
@ =9 { eeexx>ex>ex>eexxx }
@ , { oo<o>o<oo>oo }
@ 9 { oo<ooo>oo<o> }
@ newline { oooo<o>o<o>o }
@ _ { oo<o>ooooo }
@ a { o<oo>oooo<o> }
@ b { o<oo>ooo<o>o }
@ c { o<oo>ooo<oo> }
@ d { o<oo>oo<o>oo }
@ e { o<oo>oo<o>o<o> }
@ f { o<oo>oo<oo>o }
@ G { o<o>ooo<ooo> }
@ h { o<oo>o<o>ooo }
@ i { o<oo>o<o>oo<o> }
@ k { o<oo>o<o>o<oo> }
@ l { o<oo>o<oo>oo }
@ m { o<oo>o<oo>o<o> }
@ N { o<o>oo<ooo>o }
@ n { o<oo>o<ooo>o }
@ o { o<oo>o<oooo> }
@ p { o<ooo>oooo }
@ r { o<ooo>oo<o>o }
@ s { o<ooo>oo<oo> }
@ T { o<o>o<o>o<o>oo }
@ t { o<ooo>o<o>oo }
@ u { o<ooo>o<o>o<o> }
@ w { o<ooo>o<ooo> }
@ x { o<oooo>ooo }
@ y { o<oooo>oo<o> }
Computational class
Metatape is Turing-complete, meaning that it is in the same computational class as universal Turing machines. Even restricting Metatape to just <, >, e, x, n, (, ), [, and ] maintains Turing-completeness; in fact, this restricted instruction set belonged to the first iteration of Metatape, but it was later expanded for ease of use. Here is a minified version of a Bitwise Cyclic Tag emulator, proving Metatape to be Turing-complete:
// Usage: Input program as ASCII '0's and '1's, then a single space,
// and then input the initial data-string as ASCII '0's and '1's. The
// program may not be empty.
ex<<ex>[e[iiiexi>iiiexi<(x<e>exx>e>(x<eeexxx>e)])x>(>])<n<e[<(])>x<<e[
x>>e(x<<e[<(])[>(x>>e(x<<ee({xx>ex<e>(x>n<e)x>(n<e[<(])>x>)<ee}xx>>ee(
x[>(])exx<<ee(xx>>eeexxx<<ee)xx>>e[<(])>e)x<exx<<ee)xx>>en>([x>oo<oo>o
oo<eeox>(])x>oooo<o>o<o>o<e[<(])>x<<e)]))])
(253 characters minified)
An unminified and commented version can be found in the official repository.
Implementation difficulties
Since the tape must be dynamically allocated, a simple array or list is insufficient. The tape structure must also be immutable, or else the f instruction may have to perform a computationally expensive copy of the entire program data. The ideal data structure is a sort of 2D zipper, described in more detail on the GitHub repository for the reference implementation, which completes any primitive Metatape instruction in O(1) time.
There are also some technical troubles regarding parsing Metatape code; unlike most programming languages with matching parentheses and brackets, Metatape allows weaving of delimiters, with only the restriction being that they are independently balanced. For example, [(]) is valid Metatape code. A proper Metatape parser must be able to parse nested pairs of brackets and parentheses completely separately. Thus Metatape cannot be totally parsed by any traditional PEG or EBNF parser lacking lookahead/lookbehind; in practice it is of course sufficient to parse matching parentheses and brackets in raw code after the initial parsing phase.