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

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

File attachments: 
Прикрепленный файлРазмер
Binary Data quinemk.mkl465 байтов
Метки публикаций: 
Undefined

Комментарии

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

.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

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

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

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

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

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

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 шага).

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

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

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

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

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

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

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

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

Применил все обсуждавшиеся выше оптимизации и ещё несколько моих фирменных. Сократил код примерно на четверть (на 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

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

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

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

Это кажется невозможным, но с помощью ещё одного грязного трюка удалось сократить и эту программу на один шаг: 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.