Три уровня многомерного безумия
Когда программисту нечего делать, или ему просто хочется размять мозги, он начинает придумывать странные вещи. Например, эзотерические языки программирования.
Все наши скучные программы вопиюще одномерны. Память линейна, стек последователен, программа записывается в сериализованном виде. Даже то, что по своей природе двумерно, например, изображение на экране, для программной обработки сводится к линейным структурам. Идея вывести программирование за пределы одномерного пространства не нова и уже успела породить целое семейство эзотерических языков программирования, получивших, вслед за первым в своём роде языком Befunge, общее название fungeoids. Общей чертой этих языков является запись программы в виде двумерной матрицы, содержащей коды операций. Интерпретатор перемещается от ячейки к ячейке в одном из нескольких возможных направлений. Таким образом, цикл на языке Befunge может иметь весьма наглядный «циклический» внешний вид. В некоторых из этих языков запоминающие регистры изолированы от пространства, в котором хранится программа, и адресуются одномерными индексами. Другие имеют фон неймановскую архитектуру, то есть данные хранятся в той же двумерной памяти, что и код, что создаёт, помимо прочего, интересные возможности для написания самомодифицирующихся программ.
Вопросы о том, зачем всё это нужно, действительно ли кому-то нефиг делать, и обкурился ли автор лёгких наркотиков, непременно, уже возникли на языках читателей, так что придётся ответить, зачем всё это придумывается. Низачем. Попросту - для развлечения. Впрочем, спросите некоторых солидных учёных, занимающихся чистой математикой, зачем им нужно изучать такие объекты, как… не то, чтобы просто алгебра, и даже не алгебра алгебр, а прямо-таки алгебра n-го порядка, то есть алгебра алгебр алгебр… n раз. Думаю, их замысловатые ответы будут сводиться по смыслу примерно к следующему: «Так ведь это же интересно!» Вот и эзотерический язык программирования - это интересно. Это одновременно и оригинальная шутка, и замысловатая математическая абстракция для изучения, и головоломка. Доведение некоторой концепции до абсурда само по себе неплохое развлечение, поэтому сегодня мне взбрело в голову довести до абсурда идею многомерного программирования. Доводить до абсурда будем в три этапа. Я буду писать о двумерном случае, однако всё это нетрудно (?) обобщить на n-мерный случай.
Первый уровень. Собственно, на этом уровне обитают языки «программирования стрелочками» из семейства fungeoids. Память двумерна. В более интересных случаях память общая для кода и данных. На этом уровне в каждой ячейке двумерной памяти хранится обычное число, скажем, один байт. Будем называть единицу информации, хранимую в одной ячейке, словом, как и в традиционном программировании. В двумерной памяти уместна двумерная адресация ячеек, то есть адрес имеет вид (i, j). Указатель на текущую инструкцию (IP) тоже имеет такой вид. Чаще всего фунгеоиды имеют возможность изменять направление, в котором перемещается этот указатель, на одну из четырёх сторон света, но для полноты по Тьюрингу это не обязательно - достаточно лишь одного направления и набора инструкций условного перехода на двумерный адрес. Впрочем, изменяемое направление выполнения кода - изюминка фунгеоидов, делающая программирование на них особенно непохожим на традиционное, и позволяющая записывать циклы кольцами, а линейные программы - спиралями. Двумерная стуктура памяти наталкивает на мысли о таких единицах измерения, как квадратные килобайты (Кб2), заставляет задуматься о действиях операционной системы, когда у неё запросили широкий блок памяти, а свободными остались только высокие и узкие области, и порождает интересную задачу о дефрагментации прямоугольных файлов в массовых запоминающих устройствах. Компилятор мог бы оптимизировать код не только по скорости, но и по площади, и даже отдельно по ширине или высоте, а хранение растровых изображений стало бы естественным, как никогда. Наконец, языки программирования можно описывать двумерными грамматиками в форме BNF2.
Второй уровень. В отличие от первого уровня, во множестве представленного фунгеоидами, надо сказать, что ничего такого, что могло бы относиться ко второму или третьему уровню, я не встречал. На втором уровне что-то странное делается с самими числами - это уже не простые байты, как на первом уровне, а комплексные числа. Адресация ячеек двумерной памяти становится естественной. Сложение и вычитание почти не отличаются от обычных операций, а вот умножение и деление становятся несколько сложнее; появляется и новая операция - комплексное сопряжение. Можно даже пойти дальше и решить, что в ячейках памяти содержатся двумерные массивы битов. Например, слово может состоять из 16 квадратных бит (4×4). Разумеется, это порождает множество новых арифметических операций. Так, при обычном сложении одномерных байтов перенос происходит в одном направлении - влево; при двумерном сложении переносы бывают и влево, и вверх. Это уже по меньшей мере два вида сложения и вычитания. Битовые сдвиги и циклические сдвиги возможны не в двух, а в четырёх направлениях, кроме того, появляются принципиально новые битовые операции - повороты и транспонирование. При умножении сдвиги происходят в двух направлениях. Правда, не вполне понятно, как интепретировать двумерное слово в качестве обычного числа для целей адресации и организации счётчиков. Что же касается передачи данных по каналам связи, то вместо двух вариантов порядка следования бит - little-endian и big-endian - будет восемь вполне равноценных способов сериализации слов.
Третий уровень. На третьем уровне абсурда двумерным становится время. Ну и что с того, что это не для нашей Вселенной? Нам интересна математическая модель. Момент времени описывается не одной, а двумя переменными (t, u). В результате, для всякого момента времени есть не просто моменты, происходящие позже или раьше. По отношению к моменту (t, u) одни моменты правее по времени, другие - ниже, а третьи - ниже и правее. Причинно-следственная связь распространяется в обоих направлениях, и происходящее в каждый момент времени определяется тем, что происходило левее, и тем, что происходило выше по времени. Тактовая частота процессора измеряется в квадратных герцах, а состояние машины на такте (t, u) определяется её состояниями на тактах (t − 1, u) и (t, u − 1). Программа, записанная в двумерной памяти, выполняется и по горизонтали, и по вертикали. На следующем по t такте процессор переходит к инструкции на ячейку правее предыдущей, а на следующем по u - на ячейку ниже. Бициклический алгоритм может иметь топологию тора. За одну квадратную секунду по каналу связи может быть передано определённое число квадратных же бит, поэтому скорость передачи данных измеряется традиционно - в битах в секунду. Тут уж и задача оптимизации алгоритма по скорости может быть уточнена - по какому именно измерению времени важнее ускорить.
Четвёртый уровень. Если кто-нибудь придумает ещё один, четвёртый уровень в дополнение к описанным трём, буду рад это обсудить, пока за нами обоими не пришли.
In English: Three Levels of Multidimensional Insanity
Все наши скучные программы вопиюще одномерны. Память линейна, стек последователен, программа записывается в сериализованном виде. Даже то, что по своей природе двумерно, например, изображение на экране, для программной обработки сводится к линейным структурам. Идея вывести программирование за пределы одномерного пространства не нова и уже успела породить целое семейство эзотерических языков программирования, получивших, вслед за первым в своём роде языком Befunge, общее название fungeoids. Общей чертой этих языков является запись программы в виде двумерной матрицы, содержащей коды операций. Интерпретатор перемещается от ячейки к ячейке в одном из нескольких возможных направлений. Таким образом, цикл на языке Befunge может иметь весьма наглядный «циклический» внешний вид. В некоторых из этих языков запоминающие регистры изолированы от пространства, в котором хранится программа, и адресуются одномерными индексами. Другие имеют фон неймановскую архитектуру, то есть данные хранятся в той же двумерной памяти, что и код, что создаёт, помимо прочего, интересные возможности для написания самомодифицирующихся программ.
Вопросы о том, зачем всё это нужно, действительно ли кому-то нефиг делать, и обкурился ли автор лёгких наркотиков, непременно, уже возникли на языках читателей, так что придётся ответить, зачем всё это придумывается. Низачем. Попросту - для развлечения. Впрочем, спросите некоторых солидных учёных, занимающихся чистой математикой, зачем им нужно изучать такие объекты, как… не то, чтобы просто алгебра, и даже не алгебра алгебр, а прямо-таки алгебра n-го порядка, то есть алгебра алгебр алгебр… n раз. Думаю, их замысловатые ответы будут сводиться по смыслу примерно к следующему: «Так ведь это же интересно!» Вот и эзотерический язык программирования - это интересно. Это одновременно и оригинальная шутка, и замысловатая математическая абстракция для изучения, и головоломка. Доведение некоторой концепции до абсурда само по себе неплохое развлечение, поэтому сегодня мне взбрело в голову довести до абсурда идею многомерного программирования. Доводить до абсурда будем в три этапа. Я буду писать о двумерном случае, однако всё это нетрудно (?) обобщить на n-мерный случай.
Первый уровень. Собственно, на этом уровне обитают языки «программирования стрелочками» из семейства fungeoids. Память двумерна. В более интересных случаях память общая для кода и данных. На этом уровне в каждой ячейке двумерной памяти хранится обычное число, скажем, один байт. Будем называть единицу информации, хранимую в одной ячейке, словом, как и в традиционном программировании. В двумерной памяти уместна двумерная адресация ячеек, то есть адрес имеет вид (i, j). Указатель на текущую инструкцию (IP) тоже имеет такой вид. Чаще всего фунгеоиды имеют возможность изменять направление, в котором перемещается этот указатель, на одну из четырёх сторон света, но для полноты по Тьюрингу это не обязательно - достаточно лишь одного направления и набора инструкций условного перехода на двумерный адрес. Впрочем, изменяемое направление выполнения кода - изюминка фунгеоидов, делающая программирование на них особенно непохожим на традиционное, и позволяющая записывать циклы кольцами, а линейные программы - спиралями. Двумерная стуктура памяти наталкивает на мысли о таких единицах измерения, как квадратные килобайты (Кб2), заставляет задуматься о действиях операционной системы, когда у неё запросили широкий блок памяти, а свободными остались только высокие и узкие области, и порождает интересную задачу о дефрагментации прямоугольных файлов в массовых запоминающих устройствах. Компилятор мог бы оптимизировать код не только по скорости, но и по площади, и даже отдельно по ширине или высоте, а хранение растровых изображений стало бы естественным, как никогда. Наконец, языки программирования можно описывать двумерными грамматиками в форме BNF2.
Второй уровень. В отличие от первого уровня, во множестве представленного фунгеоидами, надо сказать, что ничего такого, что могло бы относиться ко второму или третьему уровню, я не встречал. На втором уровне что-то странное делается с самими числами - это уже не простые байты, как на первом уровне, а комплексные числа. Адресация ячеек двумерной памяти становится естественной. Сложение и вычитание почти не отличаются от обычных операций, а вот умножение и деление становятся несколько сложнее; появляется и новая операция - комплексное сопряжение. Можно даже пойти дальше и решить, что в ячейках памяти содержатся двумерные массивы битов. Например, слово может состоять из 16 квадратных бит (4×4). Разумеется, это порождает множество новых арифметических операций. Так, при обычном сложении одномерных байтов перенос происходит в одном направлении - влево; при двумерном сложении переносы бывают и влево, и вверх. Это уже по меньшей мере два вида сложения и вычитания. Битовые сдвиги и циклические сдвиги возможны не в двух, а в четырёх направлениях, кроме того, появляются принципиально новые битовые операции - повороты и транспонирование. При умножении сдвиги происходят в двух направлениях. Правда, не вполне понятно, как интепретировать двумерное слово в качестве обычного числа для целей адресации и организации счётчиков. Что же касается передачи данных по каналам связи, то вместо двух вариантов порядка следования бит - little-endian и big-endian - будет восемь вполне равноценных способов сериализации слов.
Третий уровень. На третьем уровне абсурда двумерным становится время. Ну и что с того, что это не для нашей Вселенной? Нам интересна математическая модель. Момент времени описывается не одной, а двумя переменными (t, u). В результате, для всякого момента времени есть не просто моменты, происходящие позже или раьше. По отношению к моменту (t, u) одни моменты правее по времени, другие - ниже, а третьи - ниже и правее. Причинно-следственная связь распространяется в обоих направлениях, и происходящее в каждый момент времени определяется тем, что происходило левее, и тем, что происходило выше по времени. Тактовая частота процессора измеряется в квадратных герцах, а состояние машины на такте (t, u) определяется её состояниями на тактах (t − 1, u) и (t, u − 1). Программа, записанная в двумерной памяти, выполняется и по горизонтали, и по вертикали. На следующем по t такте процессор переходит к инструкции на ячейку правее предыдущей, а на следующем по u - на ячейку ниже. Бициклический алгоритм может иметь топологию тора. За одну квадратную секунду по каналу связи может быть передано определённое число квадратных же бит, поэтому скорость передачи данных измеряется традиционно - в битах в секунду. Тут уж и задача оптимизации алгоритма по скорости может быть уточнена - по какому именно измерению времени важнее ускорить.
Четвёртый уровень. Если кто-нибудь придумает ещё один, четвёртый уровень в дополнение к описанным трём, буду рад это обсудить, пока за нами обоими не пришли.
In English: Three Levels of Multidimensional Insanity