Квайн? Это просто (МК-161)

Submitted by Дробышев on сб, 23/09/2017 - 00:56

Для ПМК МК-61 и подобных написать квайн (программу, выводящую саму себя) невозможно, однако это не так для ЭКВМ. Разумеется, здесь не обойтись без функций, адресуемых через регистры памяти. И всё вмещается в страницу памяти, точнее, в 98 шагов. Кто меньше?

File attachments: 
Прикрепленный файлРазмер
Binary Data quinemk.mkl465 байтов
Демонстрационные
Электроника МК и Б3

Комментарии

Submitted by AtH on ср, 27/09/2017 - 04:01

Понял, почему вы опубликовали программу в таком странном виде. Но всё же беру на себя смелость опубликовать декомпиляцию вашего труда для тех, кто захочет побить ваш рекорд. :-)

.CHARSET 1251

; Программа quinemk, опубликована Дробышевым 22 сентября 2017 на сайте pmk.arbinada.com

	.ORG 0
	ENT 3 F10^X M5 M4	; R4, R5 := 1000
;	.NUMT A13		; Адрес 13 фиксирован, являясь кодом очищения строки комментариев
	13 MB
	CX M6 PPM 9030		; Индексный регистр 0 (Универсальный байтовый буфер)
A13:
	RM6 PPM 9039		; Преобразование кода команды в мнемонику (Универсальный байтовый буфер)
	CX PPM 9031		; Индексный регистр 1 (Универсальный байтовый буфер)

A21:	PPRM 9034		; Запись и чтение по индексному регистру 1, автоинкремент (Универсальный байтовый буфер)
	MA  255 - FX!=0 A35
	RMA  KM5  GOTO A21	; Копируем мнемонику

A35:	32  KM5  KM5		; Два пробела
	RM6  KPRGM		; Считываем КОП из ячейки R6
	KRM6  FR		; Inc(R6)
	80 - MA  KX>=0B		; 50 С/П
	FX!=0 A67		; С/П завершает вывод
	5 - KX!=0B		; 55 К ЭКР
	RMA 16 -  FX>=0 A65	; 60 ИП0
	144 - KX>=0B		; F0 начало трёхшаговых команд (РРП, РРИП)
	KRM6			; Пропуск 2 шагов (трёхшаговая команда)
A65:	KRM6  KGOTOB		; Пропуск 1 шага (двухшаговая команда)

A67:	KM5			; Завершаем исходный текст кодом 0

A68:	KRM4 FR			; Inc(R4)
	RM4 PPM 9027		; Вывод строки из памяти данных (Строка комментариев)
	CX ENT ENT KSCR		; Обновление экрана
	18 PPM 9050		; Формирование интервалов (таймер 0) (Функции реального времени)
A83:	PPRM 9050		; Формирование интервалов (таймер 0) (Функции реального времени)
	FX=0 A83		; Таймер 0 выполнил полный цикл?

	RMB PPM 9025		; Вывод символа CR (Строка комментариев)
	RM5 RM4 - FX=0 A68	; Весь исходный код вывели?
	R/S			; Остановка
	.ENDP

Submitted by Дробышев on ср, 27/09/2017 - 09:02

Да, всё верно - именно так программа и работает, как вы прокомментировали :) Можно, конечно, выводить ее текст на графический экран, а не в строку комментариев, но это увеличит размер квайна.

Submitted by AtH on ср, 27/09/2017 - 15:30

1. Проверку на 255 (рядом с меткой A21) в МК-161 выполняет команда KNOT. Исходное число после проверки достаётся командой FВх. (4 шага)

2. В строке A68 не уверен, что нужен FR. Похоже на фортовскую привычку убирать за собой в стеке. (1 шаг)

3. Cx В↑ В↑ перед КЭКР стоят для красоты. Если мы работаем над минимальным размером программы, они не нужны. (3 шага)

4. В этом же жёстком жанре красивая временная задержка A83 меняется на FL0 с R0, заточенным под скорость железки. Конечно же, это потребует реальную МК-161, а не эмулятор. (около 5 шагов)

Submitted by Дробышев on ср, 27/09/2017 - 17:08

AtH wrote:
1. Проверку на 255 (рядом с меткой A21) в МК-161 выполняет команда KNOT. Исходное число после проверки достаётся командой FВх. (4 шага)

Согласен, здорово.

AtH wrote:
2. В строке A68 не уверен, что нужен FR. Похоже на фортовскую привычку убирать за собой в стеке. (1 шаг)

Из той же оперы, что и Cx В↑ В↑ перед К ЭКР. А именно, для того, чтобы в регистре T стека при выводе отображалось количество оставшихся символов. Жертвуя красотой, можно убрать.

AtH wrote:
4. В этом же жёстком жанре красивая временная задержка A83 меняется на FL0 с R0, заточенным под скорость железки. Конечно же, это потребует реальную МК-161, а не эмулятор. (около 5 шагов)

Но при этом в R0 нужно предварительно загонять константу задержки типа 9 F 10^X П0. Не спорю, сокращение здесь возможно.

Добавлю, что можно убрать в начале программы обнуление РР П9030 индексного регистра 0 универсального байтового буфера, если заранее известно, что там ноль (3 шага).

Изображение пользователя Serguei_Tarassov.
Submitted by Serguei_Tarassov on ср, 27/09/2017 - 14:55

Как это невозможно написать квайн для МК54/61? Возможно, если поупражняться в комбинаторике. Программа будет состоять из 3 или 4 шагов максимум, последняя команда - С/П. На экран должно выводится число IJKLMN50, где IJ, KL и MN - коды соответствующих команд ПМК. Желающие могут взять таблицу команд МК61 и написать программу перебора комбинаций.

Submitted by AtH on ср, 27/09/2017 - 15:32

ИП0 С/П, где в R0 записано число 6050 или даже видеосообщение "60 50".

Но это выведет код программы, а предложенный «квайн» выводит исходный текст.

Изображение пользователя Serguei_Tarassov.
Submitted by Serguei_Tarassov on ср, 27/09/2017 - 19:14

Такие "решения" не могут быть всерьез рассмотрены, как и однокомандное "решение" LIST для Бейсика. Если используются регистры, то программа должна сама их заполнять.

Конкурс "Программа печатает сама себя" проводился в НиЖ №6 1988. У языка МК нет исходного текста, есть внутреннее представление команд, есть их коды и есть многочисленные варианты мнемоник. Вывод кода при отсутствии алфавитного отображения ничем не хуже вывода его мнемоники.

Submitted by Дробышев on ср, 27/09/2017 - 17:12

Serguei_Tarassov wrote:
Как это невозможно написать квайн для МК54/61? Возможно, если поупражняться в комбинаторике. Программа будет состоять из 3 или 4 шагов максимум, последняя команда - С/П. На экран должно выводится число IJKLMN50, где IJ, KL и MN - коды соответствующих команд ПМК. Желающие могут взять таблицу команд МК61 и написать программу перебора комбинаций.

Как отметил AtH, здесь действительно предполагается вывод исходного текста, а не кода.

Изображение пользователя Serguei_Tarassov.
Submitted by Serguei_Tarassov on ср, 27/09/2017 - 19:16

У языка МК нет исходного текста, есть внутреннее представление команд, есть их коды и есть многочисленные варианты мнемоник. Например, команда с кодом 60 может записываться как ИП0, П-х0, RCL0 и т.д, включая собственно "60". Одна из систем записей программ для МК использовала именно коды, т.к. в те времена мнемоники были сложны для типографий и пиш.машинок.

Submitted by AtH on сб, 07/10/2017 - 13:32

Применил все обсуждавшиеся выше оптимизации и ещё несколько моих фирменных. Сократил код примерно на четверть (на 25 шагов), теперь «квайн» занимает 73 ячейки памяти программ.

Алгоритм не менял, разве что перестал использовать регистр A и вывожу два пробела перед мнемоникой, а не после. Это позволяет подольше подержать на экране первую команду CX и упрощает очищение строки комментария. Некоторые оптимизации весьма суровы, ведь подобные конкурсы безжалостны. При желании нужные недокументированные сервисные возможности можно ввести обратно, всё равно код будет меньше исходной программы.

Выложил программу в виде файла quinemk8.mkl, но в обфусцированный вид (абсолютно совпадающий с выводом, без комментариев и с адресами) программу не приводил. Запишите с экрана, если нужно. :-)

.CHARSET 1251

; Оптимизация программы quinemk, опубликованной Дробышевым на сайте pmk.arbinada.com
; Занимает ячейки 0..72, 73 шага

	.ORG 0
	Cx M6
;	PPM 9030		; Индексный регистр 0 (Универсальный байтовый буфер) считаем равным нулю
	EE 3 M5 M4		; R4, R5 := 1000
;	.NUMT A8
	8 MB			; Для экономии места адрес A8 рассчитан вручную
A8:
	RM6 PPM 9039		; Преобразование кода команды в мнемонику (Универсальный байтовый буфер)
	CX PPM 9031		; Индексный регистр 1 (Универсальный байтовый буфер)
	32 KM5 +		; Записываем два пробела перед мнемоникой
CopyM:
	FANS KM5		; Копируем мнемонику
	PPRM 9034		; Чтение по индексному регистру 1, автоинкремент (Универсальный байтовый буфер)
	KNOT FX=0 CopyM		; Проверка на 255

	RM6 KPRGM		; Считываем КОП из ячейки R6
	KRM6			; Inc(R6)
	Cx 80 - KX>=0B		; 50 С/П
	FX!=0 Done		; С/П завершает вывод
	5 - KX!=0B		; 55 К ЭКР
	11 - FX>=0 TwoBytes	; 60 ИП0
	144 - KX>=0B		; F0 начало трёхшаговых команд (РРП, РРИП)
	KRM6			; Пропуск ещё 2 шагов (трёхшаговая команда)
TwoBytes:
	KRM6 KGOTOB		; Пропуск ещё 1 шага (двухшаговая команда)
Done:
	KM5			; Завершаем исходный текст кодом 0
Print:	6 FEXP M0		; R0 := 403
Delay:	FL0 Delay		; Задержка 180 мс (плохо сработает на эмуляторе)
	10 KM4			; LF, Inc(R4)
	RM4 PPM 9027		; Вывод строки из памяти данных (Строка комментариев)
	KSCR			; Обновление экрана
	RM5 - Fx=0 Print	; Весь исходный текст вывели?
	R/S			; Остановка
	.ENDP

Submitted by Дробышев on пт, 06/10/2017 - 20:45

AtH wrote: Применил все обсуждавшиеся выше оптимизации и ещё несколько моих фирменных. Сократил код примерно на четверть (на 25 шагов), теперь «квайн» занимает 73 ячейки памяти программ.

Да, оптимизация существенная. Браво!

Submitted by AtH on пн, 09/10/2017 - 14:58

Да, оптимизация существенная. Браво!

Это кажется невозможным, но с помощью ещё одного грязного трюка удалось сократить и эту программу на один шаг: quinemk9.mkl

.CHARSET 1251

; Оптимизация программы quinemk, опубликованной Дробышевым на сайте pmk.arbinada.com
; Занимает ячейки 0..71, 72 шага

	.ORG 0
	Cx M6
;	PPM 9030		; Индексный регистр 0 (Универсальный байтовый буфер) считаем равным нулю
	EE 3 M5 M4		; R4, R5 := 1000
;	.NUMT A8
	8 MB			; Для экономии места адрес A8 рассчитан вручную
A8:
	RM6 PPM 9039		; Преобразование кода команды в мнемонику (Универсальный байтовый буфер)
	CX PPM 9031		; Индексный регистр 1 (Универсальный байтовый буфер)
	32 KM5 +		; Записываем два пробела перед мнемоникой
CopyM:
	FANS KM5		; Копируем мнемонику
	PPRM 9034		; Чтение по индексному регистру 1, автоинкремент (Универсальный байтовый буфер)
	KNOT FX=0 CopyM		; Проверка на 255

	RM6 KPRGM		; Считываем КОП из ячейки R6
	KRM6			; Inc(R6)
	Cx 80 - KX>=0B		; 50 С/П
	FX!=0 Done		; С/П завершает вывод
	5 - KX!=0B		; 55 К ЭКР
	11 - FX>=0 TwoBytes	; 60 ИП0
	FANS FX^2 - KX>=0B	; f0 (d9) начало трёхшаговых команд (РРП, РРИП)
	KRM6			; Пропуск ещё 2 шагов (трёхшаговая команда)
TwoBytes:
	KRM6 KGOTOB		; Пропуск ещё 1 шага (двухшаговая команда)
Done:
	KM5			; Завершаем исходный текст кодом 0
Print:	6 FEXP M0		; R0 := 403
Delay:	FL0 Delay		; Задержка 180 мс (плохо сработает на эмуляторе)
	10 KM4			; LF, Inc(R4)
	RM4 PPM 9027		; Вывод строки из памяти данных (Строка комментариев)
	KSCR			; Обновление экрана
	RM5 - Fx=0 Print	; Весь исходный текст вывели?
	R/S			; Остановка
	.ENDP

Интересный факт. Благодаря тому, что метка TwoBytes равна 51, новосибирский декомпилятор на этом варианте сбоит. Думает, что по адресу 15 использована кодово-адресная связка. Она действительно была в одном из старых вариантов программы, но здесь её роль хорошо выполняет команда + перед меткой CopyM.