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
Штампики не принимаются, где мои комментарии? Хочу нормальных комментариев!
Можно попробовать нецелое количество измерений.
Или нецелое количество состояний.
И вообще, что-то у тебя всё какое-то слишком линейное получается. ;)
> И вообще, что-то у тебя всё какое-то слишком линейное получается. ;)

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

Но вообще, меня всю жизнь интересовало, чему в реальной жизни могут соответствовать полтора бита.
(Anonymous)
легко. плюс или минус 1.5 спина какого-нибудь лептона. :)



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

        DO .5 <- #5
        DO .1 <- #1
        DO .2 <- #2
        PLEASE IGNORE .1 WHILE REMEMBERING IT
        DO NOT REMEMBER .1 WHILE IGNORING IT
(1)     DO .1 <- #0
        DO COME FROM (4)
(5)     PLEASE COME FROM .5
        DO .5 <- #5
        DO WRITE IN .3
(8)     DO .4 <- #2 A╒ "'.3 ~ .3' ~ #1"
(4)     DO .2 <- #0

        PLEASE COME FROM (3)
        DO .2 <- #2
        PLEASE COME FROM .1
        DO .5 <- #0
(2)     DO COME FROM .2

        DON'T WORRY THAT I'M REPEATING A LABEL - YOU CAN NOW QUITE
        GET AWAY WITH IT AS LONG AS YOU ARE VERY CAREFUL ABOUT WHAT
        EVIDENCE YOU LEAVE AROUND. SO, WITHOUT FURTHER DELAY, HERE
        FOLLOWS THE REPEATED LABEL:
(8)     PLEASE DO NOT PRODUCE AN ERROR

(3)     DO READ OUT .3


If this chunk of INTERCAL code was a cat confined in a box with a geiger counter, a radioactive source, and a vial of cyanide contrived to shatter if an atom in the source decays, it would at least be able to die. The INTERCAL code can't do that; so instead it exists in a superposition of quantum states. In fact, merely reading this listing and trying to understand it is likely to leave the programmer in some doubt as to whether or not they really exist.
Re: 4й уровень... мм...
обожемой
боюсь, надо пыхнуть, чтобы это полноценно понять
пойду рыть код на предмет преобразования адамара=)
Я понял. Это не 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. Хм... Тут пора принцип неопределенности вводить.
А вообще, хранить в ячейках памяти не числа (элементы числового пространства), а функции (элементы пространства функций). Естественно, как и числа, функции не представляются абсолютно точно, а аппроксимируются. Конечно, сами числа тоже могут храниться (функция-константа). Базовыми операциями, помимо арифметики, становятся интегрирование, дифференцирование, суперпозиция, обращение.
Это проблему производители 3d железа решили давно. Per-Pixel Shaders собственно какарз вполне может претендовать на четвертый уровень.
То есть там как бы во-первых нелинейность плоскости - потому то биже к вьювпоинту точки чаше, то есть (x,y) это некие пирбилжения, и небитовость данных - потому что у тебя там некий код залит вместо растра.
Не желаеш покодить под DirectX 9 ? :)
Желаю видеть, как в этой парадигме выражаются "Hello world", традиционная считалочка и программа, печатающая себя.
http://en.wikipedia.org/wiki/FiPL

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

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

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

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

Только это всё, вроде как, реально исследуется. Под названиями "нейросети" и "клеточные автоматы".
Есть даже реальные микросхемы, работающие по такому принципу — так называемые ASIC.
А почему двоичная система?
(Anonymous)
Сначала сделать нечётную сбалансированную систему.
Ну а потом прикрутить не дискертый вариант :)
Re: А почему двоичная система?
Система, где -1, 0 и 1, уже где-то реально применяется, поэтому не годится. ;-)
Ну, с двумерной памятью не баловались, но свойства объектов у меня в реальном проекте имеют ось времени, и меняются с его изменением.
Очень полезно.
Это целое направление такое -- назвается "темпоральные базы данных".
Пятый уровень
(Anonymous)
Ну в аналогии с пространством, логичнее было бы заподозрить во времени 3 измерения, а не два. Тогда появляется временное пространство. Есть ось времени: прошлое, настоящее, будущее - это обычное наше время. А перпендикулярная ей ось - это вечное настоящее, расклонированное "сейчас". Чем же различаются клоны этого "сейчас"? А тем, что на одном клоне событие произошло (пометим его красным цветом), а на другом - нет (например, синим). И в зависимости от того, красное это "сейчас" или "синие" мы знаем произошло сейчас некое событие или нет. Можно расширить спектр, тогда разные цвета будут соответсвовать различным аспектам проявления этого события, а не только атрибуту "было/не было". Таким образом, "сейчас" становится многогранным, многовариантным! И мы не течем по прямой времени вперед, а скользим по плоскости времени, выбирая каждый раз свой путь в жизни из различных нюансов... Такое "матричное" представление событий по сравнению с линейными структурами, типа списка, позволяет нам хранить не только то, что было, но и то, что могло быть. Программа может играть с различными реализациями. Параллельные нашей прямой времени прямые - это и есть параллельные миры Шекли. (отступление от темы - видимо, изменение прошлого - это перемещение по второй оси времени, поэтому будущее таким образом изменить нельзя, парадокса времени нет, есть лишь перемещение в параллельное нам время, параллельный мир т.с.).
Ну а еще одна ось времени? Продолжим аналогии с пространством. Есть тело, есть его сканирующая снизу-вверх параллельно полу плоскость. Если смотреть на меняющуюся картинку сечения на ней, то нельзя понять отчего она меняется и почему так, а не иначе. Невозможно также без знания о предмете в 3D мире судить о том, когда сечение исчезнет совсем... Трехмерный предмет накладывает определенные ограничения на вариабельность этого сечения. Это с одной стороны. С другой - оно дает дополнительные свойства бесконечному набору (списку) этих сечений (масса, например, атрибут этого набора сечений). Если представить себе двумерную фигуру на плоскости времени, скажем она переливается всеми цветами радуги, но по краям она темнеет и исчезает, то это могут быть те параллельные миры, где событие так или иначе себя проявляет вблизи момента времени t (линейного времени!). Эта фигура - есть 2D фигура - сечение. Если "сканировать" мысленно его 3D тело, увидим, что рано или поздно все возможные варианты сечений исчерпывают себя и тело заканчивается в пространстве времени. 3D временное тело - есть "закон", ограничивающий все реализации события во всех плоскостях времен. Это фактор-ограничитель. Плюс такая аналогия должна простираться и на новое свойство, аналог массы. Скажем в воздухе взвесь частиц, но это не тело, а еще более разряженное вещество - это газ. На кухне пахнет сильнее, чем в спальне жаренной картошкой. Таки здесь, 3D-тело времени есть полная реализация события, а его 2D-сечения это такая ж абстракция как и "плоские миры". Скопление, 3D-временное тело-это факт существования такой вселенной. Параллельные вселенные, т.о., расплываются, разряжаются и все менее вероятны. Замечание: когда я говорил о "событии", то это была модель. Реально, точка на оси времени-это совокупность всех фактов, явлений, описывающих реальность в данный момент времени (т.е. Вселенная). Для программы же такая модель - раз плюнуть, куб вероятных стечений обстоятельств :))) ну все... надоело заниматься плагиатом... (GNU)
Re: Пятый уровень
Я не очень понял, какова структура измерения альтернативных реальностей. Разумеется, для одного события можно ввести характеристику "было или не было" или более многоступенчатую. Но одновременно (оставим пока относительность одновременности) происходит, а также не происходит множество событий. Каждое событие может произойти или не произойти. Таким образом, у нас должна получиться не линейная ось альтернативных реальностей, а бесконечномерное их пространство.
Re: Пятый уровень
(Anonymous)
Процитируюсь :) ::"...Замечание: когда я говорил о "событии", то это была модель. Реально, точка на оси времени-это совокупность всех фактов, явлений, описывающих реальность в данный момент времени (т.е. Вселенная)...". Вобщем для примера я начал с одного события. Но на самом деле имеем ввиду не столько одно событие (а это все-таки проще для восприятия), а множество событий, описывающее данную "версию" Вселенной в данный момент времени. Это своего рода слепок со Вселенной. Это в качестве пояснения своей мысли. Что касается плагиатства, то не удержусь добавить еще кое-что: сейчас время (я не физик!) принято рассматривать как характеристику тела/термодинамич. системы. Т.е. время локально для каждой системы. За это была присуждена Нобелевская премия. Время течет с разной скоростью для каждой системы (вроде как эта скорость зависит от внутр. энергии системы). Так вот, возвращаясь к первоисточнику (а это, если кто еще не догадался Успенский), отмечу, что там же изложена еще одна модель времени - это наличие у каждого тела (термодинам. системы) своего локального времени, которое "параллельно" временам соседствующих с ней систем. Только чье-то время длинне, чье-то короче, начинаются они не с одного "старта" и бегут они с разной скоростью. Самое интересное - это кавычки вокруг слова ПАРАЛЛЕЛЬНО. Они там, так как автор считает, что у систем локальные времена не есть отрезки прямых, а окружности! Т.о. локальные времена бесконечны, зацикленны. Автор приводит пример с жизнью человека: после смерти человек возвращается к своему рождению (вспомним известный коан: "Где ты был ДО рождения? Кем ты был ДО рождения?"). Это "Вечное Возвращение". Однако, почему мы не наблюдаем этих циклов на телах/организмах, время жизни которых меньше нашего? Возможно, каждый новый цикл "распараллеливает" Вселенную. Есть у фантастов такая тема: возврат в прошлое тут же распараллеливает Вселенную, точнее помещает человека в параллельную Вселенную.
Чувствуется некая спекулятивность в таких теориях, но с теорией многомерности времени я согласен. Пример приводит все тот же Успенский. Для одномерного существа все, что он может увидеть на своей прямой - есть или до него или после. Так же и мы видим события на прямой времени: до - в прошлом и после - в будущем. А настоящее ускользает с огромной скоростью...
Тема ужасно длинная и интересная, хотел бы обсудить с Вами, если есть встречный интерес. Очевидно, что она вышла за рамки как программирования, так и эзотерического программирования:)) , но никак не за рамки эзотеризма, как такового, ибо является, пожалуй, его центральной темой :)
Re: Пятый уровень
(Anonymous)
Кстати, что касается "двумерных" эзотерических языков, я не понял следующее: если память двумерна, то можно сказать, что она давно уже перешагнула такой рубеж абстракции. Многомерные массивы давным давно используются в практике программирования, а многомерные "кубы", хранящие данные тоже не вчера появились, упорно пытаясь вытеснить традиционные реляциооные модели хранения данных. Так что, многомерность памяти - это, вероятно, спекуляция :)
В примере данного языка я видел изображение некой блок-схемы в виде стрелочек. Но ведь это линейная модель исполнения. Многомерность в модели исполнения, по крайней мере такая модель, которая не может быть очевидно, структурно описана на языке программирования - это многопоточность и сопрограммы. И те и другие используют конструкции языка либо системные/библиотечные вызовы, без знания семантики которых "увидеть" параллельно исполняющуюся ветку сложно. Чтобы проиллюстрировать мысль, напомню, как обрабатывается код завершения сист. вызова fork() :) Пока человек не знает как работает fork, понять что та же самая программа вдруг "раздвоилась" невозможно. Это не линейное перемещение по тексту программы вверх, вниз, обратно к месту вызова и т.п. (jump, return, if/else/for и т.п.).
В этом смысле параллелизм двумерен и не может быть изображен интуитивно понятными средствами экранной строки, ибо набор экранных строк - есть линейная модель исполнения программы, по которой программа скачет взад-вперед (прям как в пошаговом исполнении в дебагере:))
Что тогда есть трехмерная модель исполнения? Может быть тут можно провести аналогию с менеджерами процессов, типа как в Erlang? Распараллеливание менеджеров процессов? Или все-таки это все еще плоскость? :) (GNU)
Двумерное (комплексное) время было, кажется, у физика Хокинга.
(Anonymous)
http://www.x-libri.ru/elib/chern011/00000063.htm