Befunge

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Befunge
Парадигма:Імперативна
Дата появи:1993
Розробник:Кріс Пресі
Діалекти:Befunge-93, Befunge-98
ОС:Стекова
Ліцензія:BSD-compatible
Звичайні розширення файлів:.be, .bf, .b93, .b98, .befunge
Сторінка інтернет:catseye.tc/article/Languages.md#befunge-93

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 logn int, як вказано у документації до Befunge-93).[2] Пізніша специфікація Funge-98 забезпечує повноту Тюрінга шляхом зняття обмежень щодо розміру програми: замість того, щоб загортатись поза фіксованої межі, рух вказівника інструкцій Funge-98 працює за моделлю, яка отримала назву "Lahey-space" (на честь його автора, Кріса Лахея). У цій моделі сітка поводиться як тор обмеженого розміру стосовно згортки, але при цьому дозволяє йому розширюватись нескінченно.

Компіляція[ред. | ред. код]

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

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

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

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

Зразок коду Befunge-93[ред. | ред. код]

Нижче наведений код для генерування випадковий чисел, що може слугувати ілюстрацією техніки використання стрілок для зміни керуючого потоку. Вказівник інструкції 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-93[ред. | ред. код]

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

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

Дивитися також[ред. | ред. код]

Список літератури[ред. | ред. код]

  1. Ais523 (2008-12-18). Chris Pressey. Esolang. Процитовано 2014-01-23. 
  2. Oerjan (2014-01-18). Talk:Befunge. Esolang. Процитовано 2014-01-23. 

Посилання[ред. | ред. код]