Metatape

From Esolang
Jump to: navigation, search
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 most 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.

The interpreter linked in this article (and the language specification in its README) is currently outdated; this should hopefully be resolved sometime in the next week or so. HactarCE (talk) 17:54, 21 January 2018 (UTC)

Language overview

Metatape's data space consists of two universes, each containing a pointer and a tape. These universes are sometimes called A and B, with A being the default. Changes to the tape in one universe never immediately affect the other. 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 the it. The ! instruction switches between universes; until ! (or :) is executed again, the other pointer remains unchanged. The instruction ^ "sends" a copy of the current cell to the other universe, replacing the cell under its pointer.

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 )
| Else Skip forward to the matching | or )
) 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)
! Swap Swap between parallel universes
: Swap next Execute the next instruction or subroutine in the other universe
^ Send Send the current cell to the other universe
Pattern Description
# ... \n Inline comment
$ ... ~ Multiline comment
@ sub { ... } Subroutine definition
{ sub } Subroutine call

Comments

All characters between # and the next newline are ignored.

All characters between $ and ~ are ignored. This can be used to construct multiline comments.

If # or $ appears within a comment, it is ignored.

Program structure

A Metatape program consists of either a single block of code, or a series of subroutines. Any characters between subroutines are ignored; these are effectively comments. A subroutine is defined as such:

@ subroutine name { subroutine code }

Subroutines can be called as such:

{ subroutine name }

If a file contains any subroutine definitions, execution begins with the unnamed subroutine (defined with `@{ code }`); if this subroutine does not exist, but others do, a syntax error is raised. When the end of this subroutine is reached, execution halts and the program exits.

If a file does not contain any subroutine definitions, it is treated as a single code block, and execution begins at the top of the file. When the bottom of the file is reached, execution halts and the program exits.

Metatape is entirely case-insensitive; compilers and interpreters are advised to convert all code to lowercase internally. 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 (leading and trailing whitespace is ignored completely)

Unrecognized instructions produce a syntax error during compilation, or before program execution.

Examples

Hello, world!

A simple program that prints "Hello, world!"

@ { ex<
{h}{e}{l}{l}{o}{_}{w}{o}{r}{l}{d}{!}
}

@ _ { oo>o<ooooo }
@ ! { oo>o<oooo>o< }
@ d { o>oo<oo>o<oo }
@ e { o>oo<oo>o<o>o< }
@ h { o>o<oo>o<ooo }
@ l { o>oo<o>oo<oo }
@ o { o>oo<o>oooo< }
@ r { o>ooo<oo>o<o }
@ w { o>ooo<o>ooo< }

Cat

A cat program writes its input directly to its output.

Non-terminating

[exio]

Terminates after EOF

[
:n
ex<<<<<<<<
[eexix>(|])
n[<(])
[>(eo(:x)x])
xn:(])

The same program, in minified form:

[:nex<<<<<<<<[eexix>(|])n[<(])[>(eo(:x)x])xn:(])

Computational class

Metatape is Turing-complete, meaning that it is in the same computational class as universal Turing machines. A proof is in progress, and will be posted soon.

In theory, even restricting Metatape to just <, >, e, x, n, (, ), [, and ] should maintain Turing-completeness; in fact, this restricted instruction set belonged to the first iteration of Metatape, but it was later expanded for ease of use.

Implementation difficulties

Since the tape must be dynamically allocated, a simple array or list is insufficient. A linked list seems to work, but modifications must be made in order to store both a "parent" and "child" cell. This solution, however, runs into problems with the ^ instruction, which must make a copy of an entire tape structure; something that a linked list (with nested linked lists, furthermore) could only accomplish in O(n) time at best, by traversing the entire structure. The current reference implementation uses Clojure's immutable data structures, specifically a customized version of a zipper, to allow all instructions to complete 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 condition that they are independently balanced. In other words, [(]) is valid Metatape code. A proper Metatape parser must be able to parse brackets and parentheses completely separately.

External resources