Full Stack

From Esolang
Jump to navigation Jump to search

Full Stack is a self-modifying esolang created by User:Challenger5 and inspired by ///.

Semantics of Front End

In order to define Full Stack, we must first define a language called Front End. Front End is a deliberately Turing-incomplete stack-based language capable of simple string transformations. For storage, it uses a stack of bytes, as well as 26 variables (one for each English letter), which also hold bytes.

  • +N increments the top byte on the stack by N (mod 256). If the stack is empty, nothing happens.
  • -N decrements the top byte on the stack by N (mod 256). If the stack is empty, nothing happens.
  • :N duplicates the top N stack values (for example, :3 turns foobar into foobarbar). The entire stack is duplicated if it contains fewer than N values.
  • !N deletes the top N stack values. The entire stack is deleted if it contains fewer than N values.
  • / swaps the top two stack values.
  • a (or any lower case letter) pushes the value of the corresponding variable.
  • A (or any upper case letter) pops a value from the stack and stores it to the corresponding variable. If the stack is empty, nothing happens.
  • [...] runs the code inside as long as the value popped from the stack is nonzero.
  • [...) runs the code inside if a value popped from the stack is nonzero.
  • (...] runs the code inside as long as the stack is not empty.
  • (...) runs the code inside if the stack is not empty.
  • {...} pushes its ... to the stack such that the last character ends up at the top. The contents are permitted to contain braces as long as they are properly matched. If it is necessary to push unmatched braces a+123 and a+125 can be used instead.

Whitespace between tokens is ignored, and N can always be omitted, in which case it is assumed to be 1.

The following is an example of a Front End program that clears the stack and pushes the number of elements it had (mod 2):

a+ B
(ab AB !]
a
cc AB

Computational class

Because Front End programs only have access to a single stack, and the stack's values are drawn from a finite alphabet, the language cannot be more powerful than a push-down automaton.

Semantics of Full Stack

Full Stack is a self-modifying language; its core feature is the application of Front End programs to its own source code. In particular, the program file is treated as a queue of bytes (with the first character at the start), and bytes are repeatedly dequeued and executed as follows:

  • ] dequeues another byte and outputs it.
  • [ enqueues a byte from input.
  • < dequeues bytes and parses them as Front End instructions until it finds a matching >, and then executes these instructions. The rest of the program is used to initialize the stack, and the values of variables are preserved from last time.

Computational class

While I am not sure of this, Full Stack is likely capable of simulating cyclic tag, which would make it Turing complete.

Example programs

Hello World is very simple:

Hello, World!

This is also a trivial quine. The following is a nontrivial quine:

<::8>]<::8>]

Truth-machine:

[<:-48[{<:5>1<:5>})>

External links