Befunge

Befunge — це стекова езотерична мова програмування. Вона відрізняється від звичайних мов тим, що код програми, написаної на Befunge, розташований у двовимірному просторі інструкцій, а виконання програми може відбуватись у будь-якому напрямку. Кріс Пресі, творець Befunge, мав за мету створити мову з якнайскладнішим процесом компіляції. Befunge вважається двовимірною, оскільки програма, написана нею, записується в таблицю, по якій в різних напрямках переміщується вказівник інструкцій, виконуючи команди, розміщені в клітинках даної таблиці. Дана таблиця має можливість згортатись у тор на випадок виходу вказівника інструкцій за межі рядка, причому напрямок вказівника буде збережено, а процес виконання програми продовжиться.

Мова була створена Крісом Пресі^[1] у 1993 році як одна з перших двовимірних мов програмування загального призначення, основою яких є таблиця символів ASCII. Також існує низка розширень до оригінальної специфікації «Befunge-93», серед яких варто виділити Funge-98, яка розширює концепцію до довільної кількості вимірів і дозволяє багатопотокове виконання, використовуючи декілька вказівників інструкцій, що працюють одночасно в одному просторі. Розширення та різновиди Befunge називаються Fungeoids або просто Funges.

Специфікація Befunge-93 обмежує кожну дійсну програму сіткою з 80 інструкцій по горизонталі на 25 інструкцій по вертикалі. Виконання програми, що перевищує ці межі, «завертається» до відповідної точки з іншого боку сітки. Програма Befunge таким чином топологічно еквівалентна тору. Оскільки програма Befunge-93 може мати лише один стек, а значення чисел у ньому мають обмеження за розміром, мова Befunge-93 не є повною за Тюрінгом (однак, було показано, що Befunge-93 може бути повною за Тюрінгом при умові довільної довжини числа у стеку, а не такої, що обмежена типом даних signed long int, як вказано у документації до Befunge-93).^[2] Пізніша специфікація Funge-98 забезпечує повноту Тюрінга шляхом зняття обмежень щодо розміру програми: замість того, щоб загортатись поза фіксованої межі, рух вказівника інструкцій Funge-98 працює за моделлю, яка отримала назву «Lahey-space» (на честь його автора, Кріса Лахея). У цій моделі сітка поводиться як тор обмеженого розміру стосовно згортки, але при цьому дозволяє йому розширюватись нескінченно.

Як зазначалося, основною причиною створення Befunge було бажання створити мову, яку складно компілювати. Це було зроблено за допомогою впровадження мінливого коду (інструкція p може записувати нові вказівки на поле) та багатовимірного поля (одна і та ж інструкція може виконуватися в чотирьох різних напрямках).

Згодом ці перешкоди були певною мірою подолані за допомогою компіляторів Befunge, написаних за новими відповідними методиками.

Компілятор bef2c, що входить до стандартного дистрибутиву Befunge-93, використовує потоковий код. Кожна інструкція компілюється в фрагмент коду С, а управління протікає через фрагменти так само, як це робиться в інтерпретаторі Befunge. Зауважте, що компілятор bef2c є невірним, оскільки він не обробляє ані інструкції p, ані рядкового режиму, попри те, що реалізувати не було є неможливо (мова С може просто бути непідходящою для цього).

Іншим прикладом може бути компілятор Betty. Цей компілятор розглядає всі можливі прямі вказівки як підпрограму, і якщо інструкція p змінює цю підпрограму, ця підпрограма перекомпілюється. Це цікавий варіант JIT-компіляції, оскільки багато вказівок можна виконувати в готовому коді, не втручаючись при цьому у рішення щодо реєстру напрямків.

Нижче наведений код для генерування випадковий чисел, що може слугувати ілюстрацією техніки використання стрілок для зміни керуючого потоку. Вказівник інструкції Befunge починається у верхньому лівому куті і рухатиметься праворуч, якщо не буде перенаправлений за іншим напрямком. Слідом за стрілками навколо ? інструкції надсилають свій вказівник у випадкових напрямках, поки він не потрапить на цифру, помістивши її у стек. Після цього стрілки переходять до ., щоб вивести цифру зі стека та повернути вказівник до першого спрямованого рандомайзера. Оскільки відсутній символ @ для припинення роботи програми, даним кодом генерується нескінченний потік випадкових чисел від 1 до 9.

 v>>>>>v
 12345
 ^?^
 > ? ?^
 v?v
 6789
 >>>> v
 ^  .<

Наступний код є прикладом стандартної програми «Hello World!». Спочатку букви «olleH» записуються на вершину стеку як числа ASCII. Потім вони виходять зі стеку в порядку LIFO і виводяться як текстові символи, щоб вивести слово «Hello». Пробіл, символ з кодом 32 у таблиці ASCII, тут будується множенням чисел 4 і 8, перш ніж виводитись як текст. Неважко помітити, що синтаксис операцій реалізовано постфіксно, тобто спочатку кладуться числа, які беруть участь в операції, а тоді сам знак операції (у цьому випадку — множення). Решта коду виводить слово «World» аналогічним чином: вийшовши зі стрічкового режиму, оператор , послідовно виводить значення з верхівки стеку на екран та забирає їх зі стеку, після чого символ з кодом 10 у таблиці ASCII (символ переміщення курсору на новий рядок) реалізується множенням чисел 2 і 5 та виводиться на екран користувача за допомогою оператора ,. Інструкція @ завершує виконання програми.

>              v
v  ,,,,,"Hello"<
>48*,          v
v,,,,,,"World!"<
>25*,@

Наступний код є дещо ускладненою версією попереднього. Він додає символ з кодом 10 у таблиці ASCII до стеку, а потім кладе «! Dlrow, olleH» до стеку. Знову ж таки, принцип LIFO означає, що «H» зараз є на вершині стеку і буде виведена на екран першою, «e» — другою, «l» — третьою, і так допоки стек не стане порожнім. Для друку символів програма розпочинає цикл, який спочатку дублює верхнє значення на стеку (тому тепер стек виглядатиме як « \n! Dlrow, olleHH»). Тоді операція _ видасть дубльоване значення і піде праворуч, якщо це нуль, у іншому випадку — ліворуч. Коли значення рухається ліворуч, верхнє значення виводиться як символ ASCII . Потім він дублює наступний символ і циклічно повертається до тесту _ , продовжуючи друкувати решту стеку, поки він не є порожнім, і тому наступне значення, що з'явилося, дорівнює нулеві, після чого @ закінчує програму.

 >25*"!dlrow ,olleH":v
         v:,_@
         > ^

Наступний код ілюструє виведення символів у циклі. Тут за допомогою символу ` відбувається порівняння чисел, на кожному кроці додаючи 1, щоб збільшити кількість символів «*», які виведуться на екран. Інструкцією | ми вказуємо компілятору рухатись вниз, якщо поточне значення числа рівне нулеві, а в іншому випадку — вгору. Це — класичний приклад застосування циклів у мові Befunge. Слід зауважити, що, на відміну від більшості мов програмування, тут цикл дійсно виглядає, як кругове повторення інструкцій з перенаправленням, яке здійснюється за певної умови.

1>:5`#@_:>"*",v
         | :-1<
 ^+1,+5+5<

Програма-гра, у якій потрібно відгадати число, маючи підказки у вигляді менше/більше щоразу, коли користувач намагається вгадати число. Головний концепт випадковості тут реалізовано за допомогою інструкції ? , яка продовжує рух вказівника у випадковому напрямку.

vv <<                                                                   
    2                                                                          
    ^ v <                                                                      
 v1 <?> 3v4                                                                      
    ^ ^                                                                      
>>?>?> 5 ^                                                                   
    vv                                                                      
 v9 <?> 7v6                                                                      
    v v <                                                                      
    8                                                                          
    >> ^                                                                   
 vv <<                                                                  
     2                                                                         
     ^ v <                                                                     
  v1 <?> 3v4                                                                     
     ^ ^                                                                     
 >>?>?> 5 ^                                                                  
     vvv, * 25 <<                                     
  v9 <?> 7v6 ,,                                     
     v v <""                                     
     8> <                                     
     >> ^ "" v                                    
  > * :.> 0 "! Rebmun tupnI">: #, _ $ 25 *,: &: 99p` | ^ <_0 "! Niw uoY">: #, _ $ 25 *, @      
      ^ <>: 99g01 - * + ^

Програма, що виконує перевірку числа на парність. За рахунок простоти виконання цього завдання, головними операціями тут є ділення за модулем % , яке ставить залишок від ділення на вершину стеку, власне число 2, яке знаходиться у стеку з початку виконання програми для виконання перевірки на парність, а також літера «Е» (від «Even» — англ. парне), яка виведеться у випадку підтвердження парності числа.

&2%52**"E"+,@

Приклад програми з коментарями (Befunge-93). Слід зауважити, що компілятор пропускатиме усі символи, які не є командами, але видаватиме користувачеві повідомлення із попередженням, що дана інструкція не підтримується

& read a number 4+ add four .@ display result
  ^- inline comment -^     <-^- block comment

Більшість одновимірних мов програмування вимагають певного синтаксичного розрізнення тексту коментаря та вихідного коду — ця відмінність присутня у Befunge, адже, згідно з правилом Brainfuck, будь-який символ, який не знаходиться у наборі +-[]<>,. це коментар. Такі мови як Lisp та Python трактують рядки як коментарі в контекстах, де значення не використовуються. Для вбудовування документації в код програміст просто скеровує контрольний потік навколо області з коментарем, щоб текст у цій області ніколи не виконувався. Принципи коментування змінились із виходом Befunge-98, у якому програміст може оточити блок тексту, який не використовується безпосередньо у програмі, символами ;, що дасть компілятору зрозуміти, що далі слідує фрагмент коментарів.

• Brainfuck
• Carnage Heart^[en] - гра, що написана подібною мовою
• INTERCAL
• Whitespace
• Екзотеричні мови програмування
• Приклади програм на Befunge [Архівовано 4 грудня 2019 у Wayback Machine.]

• Специфікація Befunge-93 [Архівовано 29 листопада 2019 у Wayback Machine.]
• Реалізація довідника Befunge-93 [Архівовано 7 січня 2019 у Wayback Machine.]
• Специфікація Funge-98 [Архівовано 8 серпня 2020 у Wayback Machine.]