Befunge
| Befunge | |
|---|---|
| Парадигма | Імперативна |
| Дата появи | 1993 |
| Розробник | Кріс Пресі |
| Діалекти | Befunge-93, Befunge-98 |
| Під впливом від | Forth, Brainfuck і FALSE |
| Операційна система | стекова |
| Ліцензія | 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 long 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, у якому програміст може оточити блок тексту, який не використовується безпосередньо у програмі, символами ;, що дасть компілятору зрозуміти, що далі слідує фрагмент коментарів.
Дивитися також[ред. | ред. код]
- Brainfuck
- Carnage Heart[en] - гра, що написана подібною мовою
- INTERCAL
- Whitespace
- Екзотеричні мови програмування
- Приклади програм на Befunge [Архівовано 4 грудня 2019 у Wayback Machine.]
Список літератури[ред. | ред. код]
- ↑ Ais523 (18 грудня 2008). Chris Pressey. Esolang. Архів оригіналу за 2 грудня 2021. Процитовано 23 січня 2014.
- ↑ Oerjan (18 січня 2014). Talk:Befunge. Esolang. Архів оригіналу за 30 березня 2022. Процитовано 23 січня 2014.
Посилання[ред. | ред. код]
- Специфікація Befunge-93 [Архівовано 29 листопада 2019 у Wayback Machine.]
- Реалізація довідника Befunge-93 [Архівовано 7 січня 2019 у Wayback Machine.]
- Специфікація Funge-98 [Архівовано 8 серпня 2020 у Wayback Machine.]