Pasiphae - интерпретатор языка Brainfuck
Главная / ЭКВМ / Программы для ЭКВМ / Служебные программы

Описание

Запуск Pasiphae на ЭКВМ

Интерпретатор общеизвестного и широкораспространённого языка Brainfuck для платформы ЭКВМ. Может использоваться для изучения основ программирования и решения практических задач.

Разрабатываемый интерпретатор называется Pasiphae (Пасифе) - в честь восьмого спутника планеты Юпитер, наибольшего из ретроградных. Спутник был открыт в 1908 году британским астрономом Филибертом Жаком Мелоттом. Своё название он получил в 1975 году по имени жены критского царя Миноса, до того обозначался как Юпитер-VIII или 1908 CJ.

Язык Brainfuck разработан Урбаном Мюллером (Urban Müller) в 1993 году. Одним из мотивов было создание полноценного языка с как можно меньшим по размеру компилятором*. Авторская реализация является фактическим стандартом языка [1].

Описание предшественника** этого языка P" - первого языка программирования без оператора GOTO - было опубликовано в 1964 году итальянским профессором Corrado Böhm.

Язык Brainfuck использует модель машины, напоминающую машину Тьюринга и состоящую из следующих элементов [1]:

  • программа - последовательность односимвольных команд языка и, возможно, других символов (при обработке игнорируются);
  • указатель инструкций - указывает на команду, которая будет исполнена на следующем шагу, после ее исполнения передвигается на другую (обычно следующую справа) команду;
  • память - моделируется одномерным массивом ячеек, в каждой ячейке хранится один байт; начальное значение ячейки — ноль;
  • указатель данных - указывает на текущую ячейку памяти; начальное значение — самая левая ячейка массива; по команде двигается либо изменяет значение, хранящееся в текущей ячейке;
  • потоки ввода и вывода - последовательности байтов в кодировке ASCII.

Структура памяти ЭКВМ хорошо приспособлена для программирования на Brainfuck: интерпретатор Pasiphae записывается в область памяти программ, в текстовой области размещаются инструкции языка Brainfuck, а область двоичных данных используется для работы интерпретатора в качестве ячеек памяти. Высокое быстродействие интерпретатора, достигаемое за счёт продуманного синтаксиса языка, позволяет применять его на ЭКВМ без лишних затруднений.

Отсутствие явно указываемых адресов и меток, обозначений функций и переменных, а также минимально необходимый набор команд без каких-либо приоритетов и параметров, значительно облегчает процесс изучения языка и последующего написания программ на нём.

Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту и по возможностям не уступает таким языкам, как Си, Паскаль или Форт. О его востребованности говорит то, что для данного языка существуют микрокомпьютеры со встроенным интерпретатором, а также множество диалектов и производных языков. К примеру, Brainsub — с поддержкой подпрограмм и библиотек, многопоточный Brainfork и т.д.

Синтаксис Brainfuck

Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов. Набор команд включает команды сдвига исполнительной каретки влево-вправо, уменьшения-увеличения текущего значения ячейки на единицу, чтения-записи и организации цикла. [2]

Размер ячейки — один байт. В начальном состоянии указатель находится в крайней левой позиции, все ячейки заполнены нулями. Увеличение/уменьшение значений ячеек происходит по модулю 256. Ввод-вывод происходит побайтно, с учётом кодировки ASCII.

Команды языка

Команда Код Действие
+ 43 (2Bh) Увеличить на 1 значение в текущей ячейке
- 45 (2Dh) Уменьшить на 1 значение в текущей ячейке
> 62 (3Eh) Сдвинуть указатель данных на одну ячейку вправо
< 60 (3Ch) Сдвинуть указатель данных на одну ячейку влево
[ 91 (5Bh) "Начало цикла" - если значение в текущей ячейке положительно, сдвинуть указатель инструкций на одну команду вправо, иначе сдвинуть его на команду, следующую за парной командой "]"
] 93 (5Dh) "Конец цикла" - если значение в текущей ячейке нулевое, сдвинуть указатель инструкций на одну команду вправо, иначе иначе сдвинуть его на команду, следующую за парной командой "[".
. 46 (2Eh) Вывести значение в текущей ячейке в поток вывода как символ с соответствующим ASCII-кодом
, 44 (2Ch) Прочитать символ из потока ввода и сохранить его ASCII-код в текущую ячейку

В классической реализации игнорируются все символы, кроме восьми командных. Комментарии, не содержащие этих символов, могут добавляться в любое место программы. [1]

Особенности реализации Pasiphae

Количество ячеек с классических 30000 сокращено до 4096. Ячейки расположены в памяти двоичных данных в области регистров R1000-R5095.

Размер программы ограничен областью текстовых данных. Программы на языке Brainfuck распространяются в виде файлов MKT.

В Pasiphae список дополнен командами '(' с кодом 40(28h) и ')' с кодом 41(29h), которые эквивалентны '[' и ']' соответственно, - для удобства набора программ в текстовом редакторе.

Дополнительно введена команда с кодом 0(00h), завершающая работу интерпретатора. При отсутствии этой команды в программе разбор будет продолжен до конца области текста.

Пример программы

Программа Hallo World на Pasiphae - язык Brainfuck

Следующая программа демонстрирует вывод "Hello World!": 


++++++++++[>+++++++>
++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.
<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

Разбор программы [3]:

Подготовка в памяти (с ячейки 1) массива значений, близких к ASCII-кодам символов, которые необходимо вывести (70, 100, 30, 10), через повторение 10 раз приращения ячеек на 7, 10, 3 и 1, соответственно

"++++++++++" - присваивание ячейке 0 (счетчику) значения 10;

"[" - повторять, пока значение текущей ячейки (ячейки 0) больше нуля;

">+++++++" - приращение ячейки 1 на 7;

">++++++++++" - приращение ячейки 2 на 10;

">+++" - приращение ячейки 3 на 3;

">+" - приращение ячейки 4 на 1;

"<<<<-" - возврат к ячейке 0 (счетчику), и его уменьшение на 1;

"]" - вернуться к началу цикла.

Получение кодов букв и их вывод

">++." - вывод "Н". Получение кода 'H' (72) из 70 в ячейке 1 и вывод;

">+." - вывод "e". Получение кода 'e' (101) из 100 в ячейке 2 и вывод;

"+++++++.." - вывод "ll". Получение кода 'l' (108) из 101 в ячейке 2 и вывод дважды;

"+++." - вывод "o". Получение кода 'o' (111) из 108 в ячейке 2 и вывод;

">++." - вывод пробела. Получение кода пробела (32) из 30 в ячейке 3 и вывод;

"<<+++++++++++++++." - вывод "W". Получение кода 'W' (87) из 72 в ячейке 1 и вывод;

">." - вывод "o". Код 'o' (111) уже находится в ячейке 2, просто его выводим;

"+++." - вывод "r". Получение кода 'r' (114) из 111 в ячейке 2 и вывод;

"------." - вывод "l". Получение кода 'l' (108) из 114 в ячейке 2 и вывод;

"--------." - вывод "d". Получение кода 'd' (100) из 108 в ячейке 2 и вывод;

">+." - вывод "!". Получение кода '!' (33) из 32 в ячейке 3 и вывод;

">." - вывод кода перевода строки (10) из ячейки 4.

Программа для ЭКВМ

.CHARSET 1251

; Pasiphae
; Интерпретатор языка Brainfuck для ЭКВМ
; НПП "СЕМИКО", 2015, GPL
; v1.1 - 01.04.2015
; v1.2 (разбор ПС и ВК) 

; Ячейки в области двоичных данных (1000-5095)
; Программа BF в области текста (5096-8167)

TEK	.EQU 20	; адрес текущей ячейки

ADR	.EQU 23 ; текущий адрес в программе (область текста)
STACK	.EQU 24	; указатель на верх стека
		; (стек для команд "[" и "]" - в адресах 100-999)

POS	.EQU 25 ; текущая позиция вывода в строку
C8168	.EQU 26 ; константа 8168
C5096	.EQU 27 ; константа 5096
C1000	.EQU 28 ; константа 1000


.ORG 0
	; Подготовка к запуску
	CX
	.NUMT TXT0
	PP M 9026	; номер версии в строку комментариев
	CX
	K SCR
	; Инициализация переменных
	P M POS
	100
	P M STACK
	1000
	P M C1000
	P M TEK
	5096
	P M C5096
	P M ADR
	8168
	P M C8168

	; Очистка области ячеек перед запуском
	; заполнение всех регистров двоичных данных нулевым значением
	999 M4
	4096 M0
	CX
A1:	KM4
	FL0 A1

	; Очистка графического экрана 
	; (используется для вывода в stdout)
	2 
	PP M 9010
	56 ENT CX	; позиция вывода - в нижней строке
	PP M 9000

	; Запись адреса таблицы команд в индексный регистр памяти программ
	.NUM TKOM
	PP M 9042

	; основной цикл интерпретатора
A2:
	PK RM ADR
	PP M 9213	; поиск адреса перехода по индексу
	P X<0 A5

	; команда не найдена
A3:	P RM ADR
	1 +
	P M ADR
	P RM C8168
	- 
	P X>=0 A2	; перейти к следующему адресу

	; конец программы
A40:	.NUMT TXT1

A4:	PP M 9026
	CX ENT ENT
	P RM ADR
	R/S
	P GOTO 00

A5:	MA		; записать адрес а RA
	K GOTO A	; перейти к обработке
	

;========================== Таблица команд Brainfuck

TKOM:	.DB 62		; '>'
	.DA TEKI
	.DB 60		; '<'
	.DA TEKD
	.DB 43		; '+'
	.DA ADRI	
	.DB 45		; '-'
	.DA ADRD	
	.DB 46		; '.'
	.DA STDOUT	
	.DB 44		; ','
	.DA STDIN
	.DB 91		; '['
	.DA NTC	
	.DB 93		; ']'
	.DA KTC
			; дополнение для ; Pasiphae
	.DB 40		; '('=='['
	.DA NTC		
	.DB 41		; ')'==']'
	.DA KTC
	.DB 0		; NULL - конец текста
	.DA A40		
	.END

;========================== Обработка команд

; === Перейти к следующей ячейке
TEKI:
	P RM TEK
	1 +
	P M TEK
	P RM C5096
	-
	P X>=0 A3	; вернуться в цикл
	; выход за границы области
TEKIE:
	.NUMT TXT2
	P GOTO A4

; === Перейти к предыдущей ячейке
TEKD:
	P RM TEK
	1 -
	P M TEK
	P X<0 A3	; вернуться в цикл
	; выход за границы области
	P GOTO TEKIE

; === Увеличить значение в текущей ячейке на 1
ADRI:
	PK RM TEK
	1 +
	PK M TEK	; ограничение от 0 до 255 выполняется при записи
	P GOTO A3

; === Уменьшить значение в текущей ячейке на 1
ADRD:
	PK RM TEK
	1 -
	PK M TEK	; ограничение  от 0 до 255 выполняется при записи
	P GOTO A3

; === Напечатать значение из текущей ячейки (в коде ASCII)
STDOUT:
	PK RM TEK
	10 -
	P X=0 STDOUT0
	3 -
	P X=0 STDOUT1
	PK RM TEK
	PP M 9020	; вывод символа
	K GRPH		; обновить экран
	P RM POS
	1 +
	P M POS
	24 -
	P X>=0 A3	; вернуться в цикл
	; перевод строки
STDOUT0:
	CX
	P M POS
	1 
	PP M 9007	; прокрутка экрана на 1 строку
	56 ENT CX
	PP M 9000
	P GOTO A3

STDOUT1:
	; возврат каретки
	CX
	P M POS
	56 ENT CX
	PP M 9000
	P GOTO A3	
	
; === ввести извне значение и сохранить в текущей ячейке (число)
STDIN:
	.NUM TXT3
	PP M 9026
	CX ENT ENT
	P RM TEK
	R/S

	PK M TEK	; ограничение  от 0 до 255 выполняется при записи
	P GOTO A3

; === '['
; если значение текущей ячейки ноль, 
; перейти вперёд по тексту программы на ячейку, 
; следующую за соответствующей ] (с учётом вложенности)
NTC:
	PK RM TEK
	P X!=0 NTC1
	; не ноль
	P RM ADR
	PK M STACK	; записать адрес возврата в стек
	P RM STACK
	1 +
	P M STACK
	P RM C1000
	-
	P X>=0 A3	; вернуться в цикл
NTCE:
	.NUMT TXT4	; ошибка
	P GOTO A4
NTC1:
	; ноль
	; стек не записывать - ибо незачем
	P RM ADR
	1 +
	P M ADR
	P RM C8168
	- 
	P X>=0 NTC2	; перейти к следующему адресу
			; ошибка
	P GOTO NTCE

NTC2:
	PK RM ADR
	41 -
	P X!=0 NTC3
	52 -
	P X!=0 NTC1
NTC3:
	; найдена ']'
	P RM ADR
	1 +
	P M ADR
	P RM C8168
	-
	P X>=0 A3	; перейти к циклу
	P GOTO NTCE	

; === ']'
; если значение текущей ячейки не нуль, 
; перейти назад по тексту программы на символ [ 
; (с учётом вложенности)
KTC:
	PK RM TEK
	P X!=0 KTC1
	; не ноль
	
	P RM STACK
	1 -
	P M STACK
	100
	-
	P X>=0 NTCE	; ошибка
	PK RM STACK	; взять адрес возврата
	P M ADR		; записать его в текущий
	P GOTO A2	; перейти к циклу (без инкремента)

KTC1:	; ноль
	P RM STACK
	1 -
	P M STACK
	100
	-
	P X>=0 NTCE	; ошибка
	P GOTO A3	; перейти к циклу
; ====

TXT0:	.TEXT "\rPasiphae v1.2\0"
TXT1:	.TEXT "\rКонец программы\0"
TXT2:	.TEXT "\rОшибка в < или >\0"
TXT3:	.TEXT "\rВведите код символа\0"
TXT4:	.TEXT "\rОшибка в [ или ]\0" 

.ENDP

Интерпретатор Pasiphae v1.2 занимает 468 байт, из них 88 байт - текстовые сообщения.

  0 1 2 3 4 5 6 7 8 9
0000 Cx 3 7 9 PP П 90 26 Cx K ЭКР P П
0010 25 1 0 0 P П 24 1 0 0 0
0020 P П 28 P П 20 5 0 9 6 P П 27
0030 P П 23 8 1 6 8 P П 26 9 9
0040 9 П 4 4 0 9 6 П 0 Cx K П 4 F L0
0050 48 2 PP П 90 10 5 6 B↑ Cx PP П
0060 90 00 0 1 0 6 PP П 90 42 PK ИП
0070 23 PP П 92 13 P x<0 01 04 P ИП 23 1
0080 + P П 23 P ИП 26 - P x≥0 00 69 3
0090 9 4 PP П 90 26 Cx B↑ B↑ P ИП 23
0100 С/П P БП 00 00 П A K БП A 3Eh 1 П 0 3Ch
0110 1 F L2 2Bh 01 K x≠0 0 2Dh 1 K x≠0 9 2Eh 1
0120 K БП 8 2Ch 2 П 9 5Bh 2 ИП 7 5Dh 3 K OR
0130 28h 2 ИП 7 29h 3 K OR 00h 00h 89h FFh
0140 P ИП 20 1 + P П 20 P ИП 27 - P x≥0
0150 00 77 4 1 1 P БП 00 92 P ИП 20
0160 1 - P П 20 P x<0 00 77 P БП 01 52
0170 PK ИП 20 1 + PK П 20 P БП 00 77 PK ИП
0180 20 1 - PK П 20 P БП 00 77 PK ИП 20
0190 1 0 - P x=0 02 19 3 - P x=0 02
0200 36 PK ИП 20 PP П 90 20 K ГРФ P ИП 25 1
0210 + P П 25 2 4 - P x≥0 00 77 Cx
0220 P П 25 1 PP П 90 07 5 6 B↑ Cx
0230 PP П 90 00 P БП 00 77 Cx P П 25 5
0240 6 B↑ Cx PP П 90 00 P БП 00 77 0
0250 4 2 9 PP П 90 26 Cx B↑ B↑ P ИП
0260 20 С/П PK П 20 P БП 00 77 PK ИП 20 P x≠0
0270 02 94 P ИП 23 PK П 24 P ИП 24 1 +
0280 P П 24 P ИП 28 - P x≥0 00 77 4 5
0290 0 P БП 00 92 P ИП 23 1 + P П 23
0300 P ИП 26 - P x≥0 03 09 P БП 02 88 PK ИП
0310 23 4 1 - P x≠0 03 23 5 2 -
0320 P x≠0 02 94 P ИП 23 1 + P П 23 P ИП
0330 26 - P x≥0 00 77 P БП 02 88 PK ИП 20
0340 P x≠0 03 63 P ИП 24 1 - P П 24 1
0350 0 0 - P x≥0 02 88 PK ИП 24 P П 23
0360 P БП 00 69 P ИП 24 1 - P П 24 1
0370 0 0 - P x≥0 02 88 P БП 00 77 0Dh
0380 50h 'P' 61h 'a' 73h 's' 69h 'i' 70h 'p' 68h 'h' 61h 'a' 65h 'e' 20h ' ' 76h 'v'
0390 31h '1' 2Eh '.' 32h '2' 00h 0Dh 8Ah 'К' AEh 'о' ADh 'н' A5h 'е' E6h 'ц'
0400 20h ' ' AFh 'п' E0h 'р' AEh 'о' A3h 'г' E0h 'р' A0h 'а' ACh 'м' ACh 'м' EBh 'ы'
0410 00h 0Dh 8Eh 'О' E8h 'ш' A8h 'и' A1h 'б' AAh 'к' A0h 'а' 20h ' ' A2h 'в'
0420 20h ' ' 3Ch '<' 20h ' ' A8h 'и' ABh 'л' A8h 'и' 20h ' ' 3Eh '>' 00h 0Dh
0430 82h 'В' A2h 'в' A5h 'е' A4h 'д' A8h 'и' E2h 'т' A5h 'е' 20h ' ' AAh 'к' AEh 'о'
0440 A4h 'д' 20h ' ' E1h 'с' A8h 'и' ACh 'м' A2h 'в' AEh 'о' ABh 'л' A0h 'а' 00h
0450 0Dh 8Eh 'О' E8h 'ш' A8h 'и' A1h 'б' AAh 'к' A0h 'а' 20h ' ' A2h 'в' 20h ' '
0460 5Bh '[' 20h ' ' A8h 'и' ABh 'л' A8h 'и' 20h ' ' 5Dh ']' 00h    

Примечания

** Авторский компилятор имел размер 240 байт, более поздние реализации достигают менее 200 байт [1]. Возможно, существует как минимум один компилятор размером 100 байт [5]. Приведённую здесь программу интерпретатора на ЯМК можно оптимизировать за счёт исключения избыточных проверок и текстовых сообщений.

*** Предполагается, что создателя Brainfuck вдохновил язык FALSE. Этот язык был разработан Wouter van Oortmerssen в том же 1993 году.

В отличие от большинства более поздних языков, FALSE предоставляет достаточно большой набор возможностей, в том числе именованные переменные, строки и лямбда-функции. Многие элементы языка, в том числе стек как основная структура данных, были заимствованы из Forth [6].

Но шесть из восьми команд Brainfuck (за исключением команд ввода-вывода) в точности совпадают с командами языка P". При этом, остается неизвестным, влиял ли последний на разработку.

Литература

  1. http://progopedia.ru/language/brainfuck/
  2. https://lurkmore.to/BrainFuck
  3. https://ru.wikipedia.org/wiki/Brainfuck
  4. http://rsdn.ru/article/philosophy/languages.xml
  5. http://en.wikipedia.org/wiki/Brainfuck
  6. http://progopedia.ru/language/false/
НПП "СЕМИКО" (383) 271-01-25 (многоканальный)