moby

Три уровня многомерного безумия

Когда программисту нечего делать, или ему просто хочется размять мозги, он начинает придумывать странные вещи. Например, эзотерические языки программирования.

Все наши скучные программы вопиюще одномерны. Память линейна, стек последователен, программа записывается в сериализованном виде. Даже то, что по своей природе двумерно, например, изображение на экране, для программной обработки сводится к линейным структурам. Идея вывести программирование за пределы одномерного пространства не нова и уже успела породить целое семейство эзотерических языков программирования, получивших, вслед за первым в своём роде языком Befunge, общее название fungeoids. Общей чертой этих языков является запись программы в виде двумерной матрицы, содержащей коды операций. Интерпретатор перемещается от ячейки к ячейке в одном из нескольких возможных направлений. Таким образом, цикл на языке Befunge может иметь весьма наглядный «циклический» внешний вид. В некоторых из этих языков запоминающие регистры изолированы от пространства, в котором хранится программа, и адресуются одномерными индексами. Другие имеют фон неймановскую архитектуру, то есть данные хранятся в той же двумерной памяти, что и код, что создаёт, помимо прочего, интересные возможности для написания самомодифицирующихся программ.

Вопросы о том, зачем всё это нужно, действительно ли кому-то нефиг делать, и обкурился ли автор лёгких наркотиков, непременно, уже возникли на языках читателей, так что придётся ответить, зачем всё это придумывается. Низачем. Попросту — для развлечения. Впрочем, спросите некоторых солидных учёных, занимающихся чистой математикой, зачем им нужно изучать такие объекты, как… не то, чтобы просто алгебра, и даже не алгебра алгебр, а прямо-таки алгебра n-го порядка, то есть алгебра алгебр алгебр… n раз. Думаю, их замысловатые ответы будут сводиться по смыслу примерно к следующему: «Так ведь это же интересно!» Вот и эзотерический язык программирования — это интересно. Это одновременно и оригинальная шутка, и замысловатая математическая абстракция для изучения, и головоломка. Доведение некоторой концепции до абсурда само по себе неплохое развлечение, поэтому сегодня мне взбрело в голову довести до абсурда идею многомерного программирования. Доводить до абсурда будем в три этапа. Я буду писать о двумерном случае, однако всё это нетрудно (?) обобщить на n-мерный случай.

Первый уровень. Собственно, на этом уровне обитают языки «программирования стрелочками» из семейства fungeoids. Память двумерна. В более интересных случаях память общая для кода и данных. На этом уровне в каждой ячейке двумерной памяти хранится обычное число, скажем, один байт. Будем называть единицу информации, хранимую в одной ячейке, словом, как и в традиционном программировании. В двумерной памяти уместна двумерная адресация ячеек, то есть адрес имеет вид (ij). Указатель на текущую инструкцию (IP) тоже имеет такой вид. Чаще всего фунгеоиды имеют возможность изменять направление, в котором перемещается этот указатель, на одну из четырёх сторон света, но для полноты по Тьюрингу это не обязательно — достаточно лишь одного направления и набора инструкций условного перехода на двумерный адрес. Впрочем, изменяемое направление выполнения кода — изюминка фунгеоидов, делающая программирование на них особенно непохожим на традиционное, и позволяющая записывать циклы кольцами, а линейные программы — спиралями. Двумерная стуктура памяти наталкивает на мысли о таких единицах измерения, как квадратные килобайты (Кб2), заставляет задуматься о действиях операционной системы, когда у неё запросили широкий блок памяти, а свободными остались только высокие и узкие области, и порождает интересную задачу о дефрагментации прямоугольных файлов в массовых запоминающих устройствах. Компилятор мог бы оптимизировать код не только по скорости, но и по площади, и даже отдельно по ширине или высоте, а хранение растровых изображений стало бы естественным, как никогда. Наконец, языки программирования можно описывать двумерными грамматиками в форме BNF2.

Второй уровень. В отличие от первого уровня, во множестве представленного фунгеоидами, надо сказать, что ничего такого, что могло бы относиться ко второму или третьему уровню, я не встречал. На втором уровне что-то странное делается с самими числами — это уже не простые байты, как на первом уровне, а комплексные числа. Адресация ячеек двумерной памяти становится естественной. Сложение и вычитание почти не отличаются от обычных операций, а вот умножение и деление становятся несколько сложнее; появляется и новая операция — комплексное сопряжение. Можно даже пойти дальше и решить, что в ячейках памяти содержатся двумерные массивы битов. Например, слово может состоять из 16 квадратных бит (4×4). Разумеется, это порождает множество новых арифметических операций. Так, при обычном сложении одномерных байтов перенос происходит в одном направлении — влево; при двумерном сложении переносы бывают и влево, и вверх. Это уже по меньшей мере два вида сложения и вычитания. Битовые сдвиги и циклические сдвиги возможны не в двух, а в четырёх направлениях, кроме того, появляются принципиально новые битовые операции — повороты и транспонирование. При умножении сдвиги происходят в двух направлениях. Правда, не вполне понятно, как интепретировать двумерное слово в качестве обычного числа для целей адресации и организации счётчиков. Что же касается передачи данных по каналам связи, то вместо двух вариантов порядка следования бит — little-endian и big-endian — будет восемь вполне равноценных способов сериализации слов.

Третий уровень. На третьем уровне абсурда двумерным становится время. Ну и что с того, что это не для нашей Вселенной? Нам интересна математическая модель. Момент времени описывается не одной, а двумя переменными (tu). В результате, для всякого момента времени есть не просто моменты, происходящие позже или раьше. По отношению к моменту (tu) одни моменты правее по времени, другие — ниже, а третьи — ниже и правее. Причинно-следственная связь распространяется в обоих направлениях, и происходящее в каждый момент времени определяется тем, что происходило левее, и тем, что происходило выше по времени. Тактовая частота процессора измеряется в квадратных герцах, а состояние машины на такте (tu) определяется её состояниями на тактах (t − 1, u) и (tu − 1). Программа, записанная в двумерной памяти, выполняется и по горизонтали, и по вертикали. На следующем по t такте процессор переходит к инструкции на ячейку правее предыдущей, а на следующем по u — на ячейку ниже. Бициклический алгоритм может иметь топологию тора. За одну квадратную секунду по каналу связи может быть передано определённое число квадратных же бит, поэтому скорость передачи данных измеряется традиционно — в битах в секунду. Тут уж и задача оптимизации алгоритма по скорости может быть уточнена — по какому именно измерению времени важнее ускорить.

Четвёртый уровень. Если кто-нибудь придумает ещё один, четвёртый уровень в дополнение к описанным трём, буду рад это обсудить, пока за нами обоими не пришли.

In English: Three Levels of Multidimensional Insanity
Штампики не принимаются, где мои комментарии? Хочу нормальных комментариев!
Можно попробовать нецелое количество измерений.
Или нецелое количество состояний.
И вообще, что-то у тебя всё какое-то слишком линейное получается. ;)
> И вообще, что-то у тебя всё какое-то слишком линейное получается. ;)

Инерция мышления. ;-)

Но вообще, меня всю жизнь интересовало, чему в реальной жизни могут соответствовать полтора бита.
можно еще одну штуку сделать -- ввести недетерминизм. Но вот потянет ли это на полноценный четвёртый уровень... Не уверен.
4й уровень... мм...
"Варианты"?
Пока программа выполняется одновременно в разные стороны, она, заодно, проходится и по невыполненым условиям, соседним элементам в массивах, другим вызовам методов, etc. По принципу, "выполняем всё, из результатов выберем самый понравившийся". Тут, мне кажется, будут уместны фичи многих современных параллельных, ООП-языков: классы(пройтись по обоим родителям(а заодно и по детям), события, семафоры(вернее "развилки"!) и прочие радости.
Как оно, а? В дверь не стучат? ((=
Re: 4й уровень... мм...
Похоже, так или иначе недетерминизм напрашивается. А может быть, сделать вместо одного состояния в данный момент времени распределение вероятностей по состояниям?
Рекомендую помедитировать над понятием «непрерывный оператор».
Я над ним уже года полтора медитирую :)
В школьные годы мне не давал покоя вот этот вопрос:

Назовём операцию сложения оператором первого порядка:

op1(ab) = a + b.

Тогда умножение можно назвать операцией второго порядка и определить через сложение:

op2(ab) = op1(op1( … op1(aa), … a), a),

где уровень вложенности равен b.

Применяя ту же процедуру к opn(aa) — повторить b раз — мы всякий раз получим opn + 1(ab). Например, op3(ab) = ab.

Сравнительно несложно дополнить эти операторы нецелыми и даже иррациональными значениями операндов. Оператор нулевого порядка (приращение на единичку) тоже получается без труда. А вот что меня интересовало, так это op0,5(ab). Так и не придумал.
Круто блин, но сложно. Толком ниасилил
А вот если уйти от линейности в состояниях бита данных к гармоничности, нипример, ну или к экспоненциальности например. Так, что операции дифферницирования и интегрирования стоновятся сложением/фазовым сдвигом. Слабо, правда понимаю, что это даст, но идея хороша.
Еще можно сюда припаять нечеткую логику - бит находится не в 0 или 1 а с вероятностью p в 0 и с вероятностью q в 1. Причем понятно, что p+q>1. Хм... Тут пора принцип неопределенности вводить.
А вообще, хранить в ячейках памяти не числа (элементы числового пространства), а функции (элементы пространства функций). Естественно, как и числа, функции не представляются абсолютно точно, а аппроксимируются. Конечно, сами числа тоже могут храниться (функция-константа). Базовыми операциями, помимо арифметики, становятся интегрирование, дифференцирование, суперпозиция, обращение.
http://en.wikipedia.org/wiki/FiPL

Когда-то мы разрабатывали "квантовую" модель рыбы, с зависимостью от будущих состояний, найти этот вариант не удалось.
Вот ещё что можно - нет, не придумать, - вспомнил просто одну известную концепцию.

Всё, что рассмотрено, предполагает одно устройство исполнения, т.е. один процессор, ну и, следовательно, конкретный - хоть бы и комплексный - указатель инструкции (IP).

А теперь предположим, что для каждой ячейки памяти есть своё устройство исполнения, которое действует исходя из значения в своей ячейке, а также некоторых (или всех?) окружающих. Дальше можно думать ;)

Т.е. исходная конфигурация ячеек ("программа") уже нелинейна, и нельзя рассматривать никакой "оператор" в отрыве от остальных.

Только это всё, вроде как, реально исследуется. Под названиями "нейросети" и "клеточные автоматы".
Есть даже реальные микросхемы, работающие по такому принципу — так называемые ASIC.
Ну, с двумерной памятью не баловались, но свойства объектов у меня в реальном проекте имеют ось времени, и меняются с его изменением.
Очень полезно.
Это целое направление такое -- назвается "темпоральные базы данных".
Пятый уровень
(Anonymous)
Ну в аналогии с пространством, логичнее было бы заподозрить во времени 3 измерения, а не два. Тогда появляется временное пространство. Есть ось времени: прошлое, настоящее, будущее - это обычное наше время. А перпендикулярная ей ось - это вечное настоящее, расклонированное "сейчас". Чем же различаются клоны этого "сейчас"? А тем, что на одном клоне событие произошло (пометим его красным цветом), а на другом - нет (например, синим). И в зависимости от того, красное это "сейчас" или "синие" мы знаем произошло сейчас некое событие или нет. Можно расширить спектр, тогда разные цвета будут соответсвовать различным аспектам проявления этого события, а не только атрибуту "было/не было". Таким образом, "сейчас" становится многогранным, многовариантным! И мы не течем по прямой времени вперед, а скользим по плоскости времени, выбирая каждый раз свой путь в жизни из различных нюансов... Такое "матричное" представление событий по сравнению с линейными структурами, типа списка, позволяет нам хранить не только то, что было, но и то, что могло быть. Программа может играть с различными реализациями. Параллельные нашей прямой времени прямые - это и есть параллельные миры Шекли. (отступление от темы - видимо, изменение прошлого - это перемещение по второй оси времени, поэтому будущее таким образом изменить нельзя, парадокса времени нет, есть лишь перемещение в параллельное нам время, параллельный мир т.с.).
Ну а еще одна ось времени? Продолжим аналогии с пространством. Есть тело, есть его сканирующая снизу-вверх параллельно полу плоскость. Если смотреть на меняющуюся картинку сечения на ней, то нельзя понять отчего она меняется и почему так, а не иначе. Невозможно также без знания о предмете в 3D мире судить о том, когда сечение исчезнет совсем... Трехмерный предмет накладывает определенные ограничения на вариабельность этого сечения. Это с одной стороны. С другой - оно дает дополнительные свойства бесконечному набору (списку) этих сечений (масса, например, атрибут этого набора сечений). Если представить себе двумерную фигуру на плоскости времени, скажем она переливается всеми цветами радуги, но по краям она темнеет и исчезает, то это могут быть те параллельные миры, где событие так или иначе себя проявляет вблизи момента времени t (линейного времени!). Эта фигура - есть 2D фигура - сечение. Если "сканировать" мысленно его 3D тело, увидим, что рано или поздно все возможные варианты сечений исчерпывают себя и тело заканчивается в пространстве времени. 3D временное тело - есть "закон", ограничивающий все реализации события во всех плоскостях времен. Это фактор-ограничитель. Плюс такая аналогия должна простираться и на новое свойство, аналог массы. Скажем в воздухе взвесь частиц, но это не тело, а еще более разряженное вещество - это газ. На кухне пахнет сильнее, чем в спальне жаренной картошкой. Таки здесь, 3D-тело времени есть полная реализация события, а его 2D-сечения это такая ж абстракция как и "плоские миры". Скопление, 3D-временное тело-это факт существования такой вселенной. Параллельные вселенные, т.о., расплываются, разряжаются и все менее вероятны. Замечание: когда я говорил о "событии", то это была модель. Реально, точка на оси времени-это совокупность всех фактов, явлений, описывающих реальность в данный момент времени (т.е. Вселенная). Для программы же такая модель - раз плюнуть, куб вероятных стечений обстоятельств :))) ну все... надоело заниматься плагиатом... (GNU)
Re: Пятый уровень
Я не очень понял, какова структура измерения альтернативных реальностей. Разумеется, для одного события можно ввести характеристику "было или не было" или более многоступенчатую. Но одновременно (оставим пока относительность одновременности) происходит, а также не происходит множество событий. Каждое событие может произойти или не произойти. Таким образом, у нас должна получиться не линейная ось альтернативных реальностей, а бесконечномерное их пространство.
Двумерное (комплексное) время было, кажется, у физика Хокинга.