Язык 4DL был изобретён в 2001 г. автором Cliff L. Biffle. Как он сам объяснил, придумал он его во-первых, потому, что до этого языков с четырехмерными программами не существовало, а во-вторых, потому что четырёхмерное пространство довольно сложно для понимания, и надо же дать людям возможность потренировать .
Русская Википедия относит этот язык к семейству «фунгеоидных». Это языки, ведущие свой род от языка Befunge, программы в котором записываются в виде символов на прямоугольной решётке и могут выполняться в произвольном направлении. В 4DL для представления программы используется четырёхмерная решётка, и направлений её выполнения, соответственно, 8.
Программа на 4DL может выглядеть, например, вот так:
X , B / B + 2 B - < ? T B - T
y __ 10 __ __ 7 __ __ A __ __ __ __ 07 __ __
------------------------------------------------------------------
__ Y __ __ __ __ __ __ __ __ . __ x __ __ x || __ __ __ __ __ __ __ __ __ __ 20 __ __ __ __ __
t X __ __ __ q + 2 q - < ? Z q - Z || z __ __ __ __ __ __ __ __ . b . x __ __ x
Эта программа написана не на «базовом» языке, а на его расширении, но об этом позже.
Кроме того, что язык 4DL фунгеоидный, он ещё и стековый. Единственным объектом данных, с которым может работать программа, является стек целых чисел. В него кладутся числа, вводимые символы, и из него берутся символы для печати.
Программы на 4DL
Вот как выглядит система команд, предложенная автором:
| X | Повернуть указатель на команду в направлении X+ |
| x | Повернуть указатель на команду в направлении X- |
| Y | Повернуть указатель на команду в направлении Y+ |
| y | Повернуть указатель на команду в направлении Y- |
| Z | Повернуть указатель на команду в направлении Z+ |
| z | Повернуть указатель на команду в направлении Z- |
| T | Повернуть указатель на команду в направлении T+ |
| t | Повернуть указатель на команду в направлении T- |
| P | Положить на стек символ из соседней клетки со стороны X+ |
| p | Положить на стек символ из соседней клетки со стороны X- |
| B | Положить на стек символ из соседней клетки со стороны Y+ |
| b | Положить на стек символ из соседней клетки со стороны Y- |
| D | Положить на стек символ из соседней клетки со стороны Z+ |
| d | Положить на стек символ из соседней клетки со стороны Z- |
| Q | Положить на стек символ из соседней клетки со стороны T+ |
| q | Положить на стек символ из соседней клетки со стороны T- |
| + | Взять сумму двух чисел на вершине стека, положить результат на стек |
| — | Взять разность двух чисел на вершине стека, положить результат на стек |
| , | Ввести символ с клавиатуры и положить его на стек |
| . | Снять символ с вершины стека и вывести на экран |
| # | Перепрыгнуть через следующую клетку программы |
| ? | Снять число с вершины стека, и если оно ненулевое, то перепрыгнуть через следующую клетку программы |
| 0 | Положить на стек число 0 |
| 2 | Положить на стек копию числа на его вершине |
| % | Закончить выполнение программы |
В качестве примера программы автор приводит «Hello, World!» (по меньшей мере, с тремя ошибками). К сожалению, ни на что заметно более серьёзное язык с такими командами не способен (если не увеличивать размер программы во много раз), поэтому, для начала я решил добавить к нему еще парочку команд:
| Поменять содержимое двух ячеек на вершине стека | |
| ^ | Снять число с вершины стека и ничего с ним не делать (эквивалентно 2-+ или ?XX — в случае движения вправо) |
Жизнь стала гораздо веселее. Например, вот как выглядит программа, печатающая сумму чисел из входной строки:
0 X , D - 2 ? T D - 2 ? T D - Y || __ z __ 0D __ __ __ __ 13 __ __ __ __ 10
__ __ Y D T ? 2 - D T ? 2 - D , x || __ __ __ 10 __ __ __ __ 13 __ __ __ __ 0D
__ __ X - 2 2 + 2 + + 2 + + __ y
-------------------
T t __ __ __ __ __ ^ __ __ __ __ x || __ t
+ y + ^ x __ __ __ __ ^ || __ y __ __ . B . B x
D || 01 __ __ __ __ 0A __ 0D
y + x
__ X __ y
-------------------
Y 0 x 0 ^ , x + x || __ __ __ __ __ Y __ __ . x
__ y Z ? 2 - x y || __ __ __ X + X 2 ? t y
D __ __ __ X + D y || 0A __ __ __ __ __ 3A
X 2 ? y D - Y || __ __ __ __ __ 01
y t ? 2 - D x || __ __ __ __ __ 01
Несколько слов о записи программы (это уже мои фантазии — автор никак не описывал входной синтаксис).
Пространство, в котором находится программа, делится на двумерные слои, в которых координаты Z и T постоянны. Символы каждого слоя записываются в виде прямоугольной таблицы, начиная с угла X=Y=0. Если это символ из ASCII-7 (с кодом от 33 до 126), он пишется явно. Если нет — записывается его двузначный 16-ричный код. Пробел можно обозначать как 20 или как двойное подчёркивание. Символы пишутся через любое число пробелов, строчка с ними начинается с пробела.
Прямоугольники объединяются в двумерную таблицу. По горизонтали идут слои с одинаковым значением T (последовательно: Z=0, Z=1, ...), по вертикали — столбцы с одинаковым значением Z. Длины строчек в слоях, число строчек в слое, число слоёв в строке таблицы могут различаться — недостающие клетки будут заполнены символами с кодом 0. Слои в строке таблицы разделяются символами || а сами строки — строчками, начинающимися с минуса.
По умолчанию выполнение начинается с ячейки (0,0,0,0) в направлении X+. Стартовую точку можно переопределить, вставив в программу строку >x,y,z,t (числа x,y,z и t десятичные).
Траектория выполнения приведённой выше программы в 4-мерном пространстве выглядит примерно так:
Кроме ячеек, через которые проходит красная линия, есть ещё некоторое количество ячеек с данными, но их я решил не показывать.
Тьюринг-полный или нет?
Довольно быстро оказывается понятно, что мощность языка 4DL целиком определяется мощностью лежащей в его основе стековой машинки. Так, если разрядность числа, лежащего в стеке, ограничена, то можно реализовать те и только те алгоритмы, которые реализуются на конечных автоматах со стековой памятью. Если в стеке разрешено размещать сколь угодно длинные числа, и у нас есть операция обмена двух ячеек в вершине стека, язык становится Тьюринг-полным — но реализация машины Тьюринга на нём была бы чересчур медленной (одна операция выполнялась бы не меньше 2^2^N шагов, где N — размер используемой памяти). Если размер числа в стеке ограничен, но есть операция чтения и модификации ячеек в глубине стека (смещение от вершины берётся также из стека), то получим почти ТП-язык — доступная память прямого доступа будет ограничена.
В любом случае, четырёхмерность программы почти не используется, и любую программу на 4DL можно вложить в двумерное пространство. Причём строку Y=0 оставить для исполняемого кода, Y=1 — для данных, а остальную часть плоскости использовать для реализации команд перехода. Этот вариант кажется неинтересным.
Авторы языка Befunge наткнулись у себя на ту же проблему ограничения мощности. Для её решения они добавили в язык механизм модификации ячеек памяти (что правильно), но сделали это, разрешив обращаться к ячейкам — как для чтения, так и для записи — по явным координатам. Мне это показалось слишком сильным решением.
4DL+ и машина Тьюринга
Более умеренный вариант предложен автором одной из реализаций языка 4DL — Bernhard Stoeckner. В «расширенной» системе команд своей реализации он предлагает, помимо прочего, такие команды:
| N | Положить символ из стека в соседнюю клетку со стороны X+ |
| n | Положить символ из стека в соседнюю клетку со стороны X- |
| F | Положить символ из стека в соседнюю клетку со стороны Y+ |
| f | Положить символ из стека в соседнюю клетку со стороны Y- |
| G | Положить символ из стека в соседнюю клетку со стороны Z+ |
| g | Положить символ из стека в соседнюю клетку со стороны Z- |
| H | Положить символ из стека в соседнюю клетку со стороны T+ |
| h | Положить символ из стека в соседнюю клетку со стороны T- |
Оказывается, что этих команд достаточно, чтобы сделать язык Тьюринг-полным даже при 8-битной ячейке стека (не говоря уже о 32-битной). Чтобы доказать это, пойдём по самому простому пути — реализуем машину Тьюринга :)
Основная проблема у нас в том, что мы можем читать и менять содержимое только ячеек памяти, соседних с текущей точкой выполнения программы. Для машины Тюринга нужна бесконечная, или хотя бы полубесконечная лента, а значит, для общения с далёкими ячейками программа должна быть самомодифицирующейся.
Первой идеей было реализовать ленту в виде «небоскрёба», в котором каждый этаж мог поддерживать команды «прочитать ячейку ленты», «изменить содержимое ячейки», «сдвинуться вверх» и «сдвинуться вниз», а когда дойдёт до самого верха — запустить «строительную площадку», которая растёт в параллельном слое реальности, для строительства нового этажа. Задача оказалась разрешимой, но довольно быстро удалось обнаружить гораздо более простой путь.
Оказывается, если взять строчку программы, например, в направлении X+, левую её часть заполнить пробелами, а где-то поместить команду «N» (взять символ из стека и записать его в ячейку справа), потом положить в стек определённые последовательности команд и данных, и отправить программу выполнять эту строчку, то программа может сделать то, что вам необходимо, и вернуться обратно.
Например, последовательность [N,x,x,N] превратит строчку
__ __ __ __ N
в строчку
__ __ __ __ N N x
А если после этого отправить в эту строчку последовательность [n,n,n,N,n], то получится строка
__ __ __ N n n x
— самая левая команда «N» сдвинется на ячейку левее. Аналогично, в два приёма можно выполнить команды «сдвинуться вправо», «записать символ в соседнюю строчку» и «прочитать символ из соседней строчки». Удобнее всего работать с ячейкой, находящейся на две позиции правее ячейки, в которой находится команда «N».
Программа, реализующая машину Тьюринга, будет состоять из трёх частей. Слой T=0 будем использовать для коммуникации между программой и лентой. Программа будет находиться в области T>0, Z=0 и представлять собой конечный автомат (с памятью), преобразующий текущий символ на ленте в пару (новый символ, направление сдвига). Ленту поместим на прямую Y=Z=T=1, а программа управления будет занимать область T>0, Z=1. Интерфейс ленты дополняет интерфейс программы: по паре (символ, направление сдвига) она меняет содержимое ленты, сдвигает каретку, и возвращает новый символ, на который указывает каретка.
Назначение слоя коммуникации — передача управления от программы к ленте и обратно, а также отладочная печать. Кроме того, этот слой выполняет старт программы (издержки реализации: для начала выполнения надо явно положить в стек содержимое ячейки, на которую указывает каретка).
Текущее состояние программы хранится с помощью модификации кода. Для выполнения обработки управление передаётся в точку (2,3,0,1) в направлении T+, и идёт по прямой, заполненной командами «T» за исключением одной клетки, соответствующей текущему состоянию. В этой клетке находится команда «x» (пойти влево). Программа «выходит на нужном этаже», меняет команду «x» на «T», потом анализирует символ в вершине стека, кладёт в стек желаемые направление движения и новый символ, после чего боковыми дорожками добирается до «этажа», соответствующего новому состоянию, там кладёт в ячейку (2,3,0,T) команду «x» и уходит на плоскость Z=T=0, где её переправляют на управление лентой.
Собственно, всё. Вот пример программы, реализующей удвоение числа, записанного на ленте. В программе 7 состояний, на ленте сейчас число 2 (две единицы).
B __ Y || T X 2 Y
01 __ __ || __ __ __ P 0
__ __ __ || y . + b 2 x
__ __ T . B x || __ __ 0 X . z __
Z __ __ __ __ || X 2 b + . y
--------------------------------------------------------------------------------
__ __ __ __ __ 02 01 __ __ __ __ || Y t X # ? __ # __ __ N __ __ __
__ T __ __ X b b __ __ __ Y || __ __ T __ __ __ __ __ __ __ FF 00 01 01 00
X b F ? y B B Y __ __ __ || N __ p
y __ x x __ 02 00 T __ Y T || __ __ y
t __ f b __ __ __ __ __ x __ || __ __ T
|| N __ p
|| __ __ y __ __ __ __ __ __ __ __ x
|| X Q Q Q Q Q Q Q Q Q Q y
--------------------------------------------------------------------------------
__ __ __ __ __ 02 00 __ __ __ __ || __ __ t __ __ __ __ __ __ __ __ x
__ T __ __ X b b __ Y __ __ || __ __ X B B B B B B B B y
X b F ? y B B Y __ __ __ || __ __ __ 01 # # F x x N N
y __ T x __ 02 01 Y T __ __ || __ __ __
t __ f b __ __ __ x __ __ __ || __ __ 2
|| __ __ __
|| __ __ __
|| __ 00 01 # # B x x N 01 N
--------------------------------------------------------------------------------
__ __ __ __ __ 01 01 __ __ __ __ ||
__ T __ __ X b b Y __ __ __ ||
X b F ? y B B __ Y __ __ ||
y __ T x __ 02 01 T Y __ __ || __ __ __
t __ f b __ __ __ __ x __ __ || __ __ ?
--------------------------------------------------------------------------------
__ __ __ __ __ 01 00 __ __ __ __ ||
__ T __ __ X b b __ Y __ __ ||
X b F ? y B B Y __ __ __ ||
y __ T x __ 01 01 Y T __ __ || __ __ t __ x
t __ f b __ __ __ x __ __ __ || __ __ X ^ y
--------------------------------------------------------------------------------
__ __ __ __ __ 02 01 __ __ __ __ ||
__ T __ __ X b b __ __ Y __ ||
X b F ? y B B __ Y __ __ ||
y __ T x __ 01 01 __ Y t __ || __ __ __
t __ f b __ __ __ __ x __ __ || __ __ P 01
--------------------------------------------------------------------------------
__ __ __ __ __ 01 00 __ __ __ __ ||
__ T __ __ X b b Y __ __ __ ||
X b F ? y B B __ __ __ Y ||
y __ T x __ 02 01 T __ __ Y || __ __ __
t __ f b __ __ __ __ __ __ x || __ __ -
--------------------------------------------------------------------------------
__ __ __ __ __ __ __ __ __ __ __ ||
__ T __ __ % __ __ __ __ __ __ ||
X b F ? y B B Y __ __ __ ||
y __ T x __ 00 00 Y __ __ __ || __ __ __
t __ f b __ __ __ x __ __ __ || __ __ ?
--------------------------------------------------------------------------------
||
||
|| __ __ __ __ N 01 x x N
|| __ __ t __ b b b b b x
|| __ __ X B B B B B B y
|| __ __ __ n N n n 01 n
--------------------------------------------------------------------------------
||
||
|| __ __ __ __ N 01 N x x n
|| __ __ t __ b b b b b b x
|| __ __ X B B B B B B B y
|| __ __ __ N N N __ 01 n n
Если эту программу запустить, она напечатает
021 120 020 110 011 110 121 020 021 120 111 110 010 120 121 121 120 011 000
Каждая тройка символов — это новый символ, который нужно оставить на ленте (0 или 1), направление, куда сдвинуться (0 — на месте, 1 — влево, 2 — вправо) и символ, который оказался под новым положением каретки. Можно проверить, что программа всё сделала правильно, и получилось число 4.
С некоторыми усилиями, эту реализацию тоже можно уместить в 2D. Но в 4 измерениях работать несколько приятнее — гораздо больше свободы.
Что дальше?
Можно слегка расширить язык — добавить команды умножения, деления с остатком, и занесения на стек числа 256 (для более удобного разделения числа на байты для записи в память). Правда, возникнут проблемы с отрицательными числами. Можно вместо 256 добавить команды «отщепить младший байт» ([x] => [x&0xff,x>>8]) и «приклеить младший байт» ([x,y] => [x+(y<<8)]). Но это только сделает язык удобнее, не изменив его сути. Интереснее посмотреть, что в языке лишнее, и как лучше использовать многомерную память.
Например:
- можно ли убрать стек и оставить только 8- или 32-битный аккумулятор?
- а если после этого добавить fork (каждый процесс со своим аккумулятором)?
- а если вместо аккумуляторов реализовать параллельный слой данных, так, что в каждой ячейке будет одна команда и один байт данных?
- … и заставить все ячейки работать параллельно и одновременно каждый такт?
- Это уже получились схемы из Майнкрафта, или пока ещё нет?
А если нет, тогда я выпью ещё...
Кстати, на esolang обнаружилась ещё парочка четырёхмерных (точнее, многомерных) языков. Оба — диалекты BrainFuck. Но в одном каретка блуждает по многомерной памяти, а программа выглядит, как строчка на BF, а в другом наоборот — программа многомерна, зато память линейна. Отличие от 4DL — что в обоих случаях управление и работа с памятью разделены.
Ссылки.
Страничка 4DL на esolang
Страничка из блога автора
Сайт с интерпретатором
Befunge и его диалекты
Brainfuck с многомерной памятью
Brainfuck с многомерной программой
Автор: Mrrl
