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 починається у верхньому лівому куті і рухатиметься праворуч, якщо не буде перенаправлений за іншим напрямком. Слідом за стрілками навколо ?
інструкції надсилають свій вказівник у випадкових напрямках, поки він не потрапить на цифру, помістивши її у стек. Після цього стрілки переходять до .
, щоб вивести цифру зі стека та повернути вказівник до першого спрямованого рандомайзера. Оскільки відсутній символ @
для припинення роботи програми, даним кодом генерується нескінченний потік випадкових чисел від 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
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.]
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.