Введение

2-мерный эзотерический язык программирования

Befunge — это двухмерный язык программирования, основанный на стеке, рефлексивный и эзотерический. Он отличается от традиционных языков тем, что программы располагаются на двухмерной сетке. "Стрелочные" команды управляют потоком выполнения влево, вправо, вверх или вниз, а циклы создаются путем направления потока выполнения по замкнутому контуру. Его описывают как "нечто среднее между Forth и Lemmings". Befunge был создан Крисом Пресси в 1993 году для платформы Amiga. Язык был разработан таким образом, чтобы его было максимально сложно компилировать, с использованием самомодифицирующегося кода и многомерного игрового поля. Однако, несмотря на это, для него было разработано несколько компиляторов. Изначальная спецификация Befunge 93 ограничивала размер программ сеткой 80x25, и хотя язык не был полностью Тьюринг-полным, последующие расширения, такие как Funge 98, расширили его возможности до Тьюринг-полноты. Название "Befunge" произошло из-за опечатки в онлайн-дискуссии. Несмотря на то, что язык был задуман как сложный для компиляции, компиляторы, такие как bef2c и Betty, смогли реализовать его, используя различные техники. Программы на Befunge характеризуются использованием стрелок для изменения потока управления и могут генерировать такие результаты, как последовательности случайных чисел или классическое сообщение "Hello, World!".

История

Язык был первоначально создан Крисом Пресси в 1993 году для Amiga, как попытка разработать язык, который было бы максимально сложно компилировать. Обратите внимание, что команда `p` позволяет осуществлять самомодифицирующийся код. Тем не менее, впоследствии было написано несколько компиляторов. Существует также ряд расширений оригинальной спецификации "Befunge 93", наиболее заметным из которых является Funge 98, который расширяет концепцию до произвольного числа измерений и может быть многопоточным, с несколькими указателями инструкций, одновременно работающими в одном и том же адресном пространстве. Расширения и варианты Befunge называются Fungeoids или просто Funges. Спецификация Befunge 93 ограничивает каждую допустимую программу сеткой размером 80 инструкций по горизонтали и 25 инструкций по вертикали. Выполнение программы, выходящее за эти пределы, "переносится" в соответствующую точку на противоположной стороне сетки; таким образом, программа Befunge топологически эквивалентна тору. Поскольку программа Befunge 93 может иметь только один стек и её область хранения ограничена, язык Befunge 93 не является полным по Тьюрингу (однако было показано, что Befunge 93 становится полным по Тьюрингу при неограниченном размере слова стека). Более поздняя спецификация Funge 98 обеспечивает полноту по Тьюрингу, снимая ограничения на размер программы; вместо обертывания в фиксированном пределе, движение указателя инструкций Funge 98 следует модели, получившей название "пространство Лахея" в честь её создателя, Криса Лахея. В этой модели сетка ведёт себя как торус конечного размера при обёртывании, при этом позволяя ей расширяться бесконечно.

Этимология

Слово Befunge произошло от опечатки в онлайн-дискуссии, где планировалось написать слово "before".

Сборник

Как уже было сказано, целью разработки Befunge было создание языка, который сложно компилировать. Это было попыткой реализовать самомодифицирующийся код (инструкция 'p' может записывать новые инструкции в игровое поле) и многомерное игровое поле (одна и та же инструкция может выполняться в четырех различных направлениях). Тем не менее, эти препятствия были преодолены, по крайней мере частично, и компиляторы для Befunge были созданы с использованием подходящих методов. Компилятор bef2c, входящий в стандартный дистрибутив Befunge 93, использует потоковый код: каждая инструкция компилируется в фрагмент кода на C, и управление переходит между фрагментами так же, как и в интерпретаторе Befunge (то есть, в зависимости от значения регистра "направления"). Это не дает значительного преимущества по сравнению с хорошим интерпретатором. Следует отметить, что компилятор bef2c некорректен, поскольку он не обрабатывает ни инструкцию 'p', ни строковый режим, но реализовать это было бы возможно (хотя язык C может быть не самым подходящим для этой задачи). Например, компилятор etty рассматривает каждую возможную прямую линию инструкций как подпрограмму, и если инструкция 'p' изменяет эту подпрограмму, то подпрограмма перекомпилируется. Эта разновидность компиляции "just in time" обеспечивает гораздо большее преимущество перед интерпретатором, поскольку многие инструкции могут выполняться в машинном коде без принятия промежуточных решений на основе регистра "направления".

Список инструкций Befunge-93

0 9 Поместить это число в стек. + Сложение: извлечь a и b, затем поместить a+b Вычитание: извлечь a и b, затем поместить b-a * Умножение: извлечь a и b, затем поместить a*b / Целочисленное деление: извлечь a и b, затем поместить b/a, округленное к 0. % Модуль: извлечь a и b, затем поместить остаток от целочисленного деления b/a. ! Логическое НЕ: извлечь значение. Если значение равно нулю, поместить 1; иначе, поместить нуль. ` Больше: извлечь a и b, затем поместить 1, если b>a, иначе – нуль. > Начать движение вправо < Начать движение влево ^ Начать движение вверх v Начать движение вниз ? Начать движение в случайном кардинальном направлении Извлечь значение; двигаться вправо, если значение=0, иначе – влево | Извлечь значение; двигаться вниз, если значение=0, иначе – вверх " Начало строки: поместить ASCII-код каждого символа до следующего " : Дублировать значение на вершине стека \ Поменять два значения на вершине стека $ Извлечь значение из стека и отбросить его Извлечь значение и вывести как целое число, за которым следует пробел , Извлечь значение и вывести как ASCII-символ # Мост: пропустить следующую ячейку p Вызов "поместить" (способ сохранить значение для последующего использования). Извлечь y, x и v, затем изменить символ в позиции (x,y) в программе на символ с ASCII-кодом v g Вызов "получить" (способ извлечь данные из хранилища). Извлечь y и x, затем поместить ASCII-код символа в этой позиции в программе & Запросить у пользователя число и поместить его в стек ~ Запросить у пользователя символ и поместить его ASCII-код в стек @ Конец программы (пробел) Операция без действия. Ничего не делает

Большинство одномерных языков программирования требуют некоторого синтаксического различия между текстом комментария и исходным кодом — хотя это различие может быть столь же тривиальным, как правило Brainfuck, что любой символ, не входящий в набор +[]<>,. является комментарием. Языки, такие как Lisp и Python, рассматривают строки как комментарии в контексте, где значения не используются. Аналогично, в Befunge нет синтаксиса комментариев: для встраивания документации в код программист просто направляет поток управления вокруг области "комментария", так что текст в этой области никогда не выполняется.