HashHell

From Esolang
Jump to: navigation, search
The title of this article is incorrect because of technical limitations. The correct title is #hell.

#hell is a minimalist subset of Lua designed by User:iconmaster. It is designed to force the programmer to use Lua tables (essentially hash maps) for all computation, proving that all you need for Turing completeness is the hash map and some control flow. All #hell programs are also Lua programs; but not all Lua programs are #hell programs (due to the fact that you can use primitive types in normal Lua, such as numbers or strings).

Grammar

A valid #hell program is a series of statements, with optional Lua comments. A #hell statement is either:

  • An assignment,
  • An output statement,
  • Or a while loop.


An assignment is the standard Lua assignment (the `=` operator). The right-hand side of an assignment is limited to an index (the Lua `[]` operator) of a valid #hell expression. The right-hand side can be any valid #hell expression, which includes:

  • `{}`, a constructor of a new Lua table.
  • The global table constant, `_G`.
  • An index (the `[]` operator) of any valid #hell expression.


An output statement is of the following form:

io.write("string")

Where string is any Lua string constant.


A while loop is a standard Lua `while ... end` loop. The condition on the loop is limited to valid #hell expressions, in addition to the input condition. The loop body is zero or more #hell statements.


The input condition is only allowed in while loops, and is of this form:

io.read()


No other parts of Lua are allowed in #hell.

Constructing Programs

Writing in #hell generally means using chains of _G to build up a table of constants, and then use those constants to create areas where you can store tables for actual computation.

The first step usually is to build the constant chain, one constant for each variable you need to store. It generally looks like this:

_G[_G] = {}
_G[_G[_G]] = {}
_G[_G[_G[_G]]] = {}
...

Then, you can index all the constants you made to store variable data, like so:

_G[_G][_G] = ...
_G[_G][_G[_G]] = ...
_G[_G[_G[_G]]][_G[_G[_G]]] = ...
...

We probably want to do math at some point. One way to count in #hell is to encode a number as a table of tables, where the amount of tables deep is the number. Either nil can be 0, or a table with no nests can be 0. We'll use the latter here. Here's a snippet that increments the variable `_G[_G][_G]`, using `_G[_G][_G[_G]]` as temporary storage and `_G` as the index for counting nests:

_G[_G][_G[_G]] = _G[_G][_G]
_G[_G][_G] = {}
_G[_G][_G][_G] = _G[_G][_G[_G]]

Decrementation is simpler:

_G[_G][_G] = _G[_G][_G][_G]

To store data structures, linked lists are the best in #hell. We can choose one index (e.g. `_G`) for the value of a list node, and another index (e.g. `_G[_G]`) for the next node in the chain. Here's an prepend function, taking `_G[_G][_G]` as the existing list and `_G[_G][_G[_G]]` as the new value (with `_G[_G][_G[_G[_G]]]` as a temporary):

_G[_G][_G[_G[_G]]] = {}
_G[_G][_G[_G[_G]]][_G] = _G[_G][_G[_G]]
_G[_G][_G[_G[_G]]][_G[_G]] = _G[_G][_G]
_G[_G][_G] = _G[_G][_G[_G[_G]]]

Assuming the list is still in `_G[_G][_G]`, the value of the front of the list can be retrieved like so:

_G[_G][_G][_G]

Here's a snippet that traverses a list in `_G[_G][_G]` (clobbering the variable in the process, so copy it over first if you need to):

while _G[_G][_G][_G[_G]] do
	_G[_G][_G] = _G[_G][_G][_G[_G]]
	-- your code here
end

Computation Class

#hell is a Turing-complete language. You can take an arbitrary brainfuck program (minus the I/O operators) and convert it to a #hell program.

First, this code needs to be before everything else:

_G[_G] = {}
_G[_G[_G]] = {}
_G[_G[_G[_G]]] = {}
_G[_G][_G] = {}
_G[_G][_G][_G] = {}

Then, take your BF program and transcribe it according to this table:

BF symbol #hell code
+
_G[_G][_G[_G]] = _G[_G][_G][_G][_G]
_G[_G][_G][_G] = {}
_G[_G][_G][_G][_G] = _G[_G][_G[_G]]
-
_G[_G][_G[_G]] = _G[_G][_G][_G][_G]
while _G[_G][_G[_G]] do
	_G[_G][_G][_G] = _G[_G][_G[_G]]
	_G[_G][_G[_G]] = _G[_G][_G[_G[_G[_G]]]]
end
<
_G[_G][_G[_G[_G]]] = {}
_G[_G][_G[_G]] = _G[_G][_G][_G[_G]]
while _G[_G][_G[_G]] do
	_G[_G][_G[_G[_G]]] = _G[_G][_G[_G[_G[_G]]]]
	_G[_G][_G[_G]] = _G[_G][_G[_G[_G[_G]]]]
end
while _G[_G][_G[_G[_G]]] do
	_G[_G][_G][_G[_G]] = {}
	_G[_G][_G][_G[_G]][_G] = {}
	_G[_G][_G[_G[_G]]] = _G[_G][_G[_G[_G[_G]]]]
end
_G[_G][_G] = _G[_G][_G][_G[_G]]
>
_G[_G][_G[_G[_G]]] = {}
_G[_G][_G[_G]] = _G[_G][_G][_G[_G[_G]]]
while _G[_G][_G[_G]] do
	_G[_G][_G[_G[_G]]] = _G[_G][_G[_G[_G[_G]]]]
	_G[_G][_G[_G]] = _G[_G][_G[_G[_G[_G]]]]
end
while _G[_G][_G[_G[_G]]] do
	_G[_G][_G][_G[_G[_G]]] = {}
	_G[_G][_G][_G[_G[_G]]][_G] = {}
	_G[_G][_G[_G[_G]]] = _G[_G][_G[_G[_G[_G]]]]
end
_G[_G][_G] = _G[_G][_G][_G[_G[_G]]]
[
while _G[_G][_G][_G][_G] do
]
end

This is a BF implementation with an infinite tape in both directions, but only arbitrarily large unsigned values are allowed in memory cells.

Examples

Hello World

io.write("Hello, World!")

Truth-machine

This program interprets no input as a 0, and some input as a 1.

while io.read() do
	_G[_G] = {}
end
while _G[_G] do
	io.write("1")
end
io.write("0")