...

суббота, 3 апреля 2021 г.

EDSAC (только для самых суровых)

Что приходит Вам в голову, когда Вы слышите “низкоуровневое программирование”? Может быть, C++? Непрекращающийся контроль указателей, попытки оптимизации быстродействия, потребляемой памяти? Или, вероятно, вы представляете инструкции ассемблера какой-нибудь популярной ныне архитектуры?

Если же Вы вспоминаете, как перфоратором прокалывали перфоленту, одно отверстие за другим, в течение многих часов, то эта статья для Вас! Добро пожаловать под кат! :)

Lasciate ogni speranza, voi ch'entrate
— Dante Alighieri, La Divina Commedia

EDSAC — «Electronic Delay Storage Automatic Calculator», был создан в Кембридже в 1949 для военных нужд. Ныне в забвении, вспоминают о нём лишь в образовательных целях в N-й губернии в малоизвестной Alma Mater, дочери Петербурхского государственного унивеситета.
Существует также проект The EDSAC Replica Project, где могучая кучка энтузиастов создаёт эмулятор и гайды по EDSAC для сохранения памяти об этом удивительном устройстве.
One of the nicer features of the EDSAC is that it is conceptually a very simple machine.
— Tutorial Guide to the EDSAC Simulator

Выглядит дрындулет вот так:

Рис 1.1. — EDSAC Simulator вблизи.

Рис 1.2. — EDSAC Simulator вдали.

Скачать его можно здесь.

Слева Вы можете видеть текстовый редактор для инструкций. Инструкции бывают двух типов: Initial Orders 1 (далее IO1) и Initial Orders 2 (мега продвинутые). Измененную строку редактор подсвечивает жёлтым, зелёным — сохранённые. Комментарии заключаются в []. Редактор имеет память на несколько шагов назад, поэтому можно откатывать программу, нажимая Ctrl+Z. Всё это раньше набирали на перфоленте, это новодел. Первая инструкция в IO1 — T N S, где N — адрес последней строки с инструкцией + 1. Простейшая программа на EDSAC имеет вид:

Листинг 1. — EDSAC order code, простейшая программа.

Она не делает ничего. Как и большинство моих программ. Отсчёт начинается с 31, т. к. ячейки с 0..30 изначально используются для запуска самой машины, вспоследствии их можно использовать как ячейки памяти.

Кстати, по умолчанию симулятор настроен на IO2, чтобы переключить его на IO1, нажмите на врехней панели EDSAC -> IO1. Запускается по кнопке Start, останавливается по Stop, Single E. P. — пошаговая отладка, для этого надо написать вначале Z0S/ZS/Z0F/ZF.

Справа Вы можете симулятор и содержимое памяти вычислительной машины. Слова 17-битные, всего 1024 ячеек памяти (или 35-битные, 512 ячеек памяти, как будет удобнее, посередине — таинственный «sandwich-digit»). Еще есть аккумулятор (оперативная память), 71-бит, и 35-битный регистр умножения. Симулятор поддерживает ввод с помощью «дискового телефона», вывод на печать. Включив hints, вы можете смотреть на содержимое ячеек памяти, наводя на них мышкой. Сверху будет появляться число в 10СС. Также можно смотреть содержимое аккумулятора и регистра умножения.


Рис 2. — Формат машинного слова.

Рис 3. — Формат машинной инструкции.

О числах. Число записывается в память в дополнительном коде с помощью инструкции: P N S или P N L, где N — множитель перед двойкой. Например, P0S = 2*0+0=0, P0L = 2*0+1=1, P1S = 2, P1L = 3 и т. д. Отрицательные числа записываются в дополнительном коде, об этом можно почитать в туториале. EDSAC также работает с дробными числами. Символ короткого слова S (F для IO2) и L (D). Не только числа, но и инструкции меняют свой смысл в зависимости от этого.

Есть пара гайдов, основной и сокращённый, рекомендую последний т. к. там меньше буков понятнее изложен материал, работающие примеры. Чтобы сделать приведенный в них код работающим, надо заменить первую строку ZOS/ZS/Z0F/ZF на X0S/X0F. Инструкции смотрите там, либо уже в комментариях к коду.

В течение нескольких месяцев было изготовлено множество версий процедуры печати десятичных чисел. Если программист был непроходимо глуп, или был полным идиотом и совершенным «лозером», то подпрограмма конверсии отняла бы у него около сотни команд. Но любой хакер, стоивший своего имени, мог уместить ее в меньший объем. В конечном счете, попеременно убирая инструкции то в одном, то в другом месте, процедура была уменьшена до примерно пятидесяти инструкций.
— Стивен Леви, Хакеры: Герои компьютерной революции

Итак, моим заданием было написать программу по выводу n-й строки треугольника Паскаля.
Листинг 2. — Kotlin, вывод 3-й строки треугольника Паскаля.
fun main(args: Array<String>) {
    var a = 1
    var row = 3
    row += 1
    for (i in 1..row) {
        print(a)
        print(" ")
        a = a * (row - i) / i
    }
}


Здесь будет вложенный цикл, т. к. деление нужно реализовывать вручную.
Листинг 3. — EDSAC order code, целочисленное деление, округление вниз.
[31] T56S
[32] E37S [безусловный переход через константы]
[33] P3L [делимое = 5]
[34] P1L [делитель = 2]
[35] P0S [ну для подсчета частного, 0]
[36] P0L [1]
[37] A35S [выгружаю ну для подсчета частного]
[38] T2S [частное будет во 2 ячейке]
[39] A33S [загружаю делимое в аккумулятор]
[40] T1S [записываю делимое в 1 ячейку]
[41] A1S [читаю содержимое делимого]
[42] S34S [вычитаю делитель]
[43] T1S [записываю новое значение делимого в ячейку 1]
[44] A2S [загружаю частное]
[45] A36S [прибавляю 1]
[46] T2S [записываю увеличенное на 1 частное]
[47] A1S [выгружаю в аккумулятор делимое]
[48] G50S [если делимое < 0, стоп]
[49] T1S [чищу содержимое аккумулятора]
[50] E41S[иначе повторять цикл]
[51] T0S [чищу содержимое аккумулятора]
[52] A2S [выгружаю частное]
[53] S36S [вычитаю 1]
[54] T2S [загружаю частное обратно]
[55] Z0S [иначе стоп]


Как Вы могли заметить, адресация абсолютная, что доставляет головную боль, агрессию, вызывает скрип зубов, ненависть, разочарование, злобу, сложности (это пофиксили во 2 версии Initial Orders). При сдвиге одной строки сдвигается сразу МНОГО. И надо переписывать адреса всех «поплывших» строк.

Наконец решение:

Листинг 4. — EDSAC order code, IO1, n-я строка треугольника Паскаля.
[31] T154S [указатель на последнюю строку программы +1]
[32] E84S [безусловный переход к 84 строке, начало тела программы]
[33] PS [следующая цифра в десятичной СС]
[34] PS [степень десятки]
[35] P10000S [для корректного вывода чисел, степени 10, 10^4]
[36] P1000S [для корректного вывода чисел, степени 10, 10^3]
[37] P100S [для корректного вывода чисел, степени 10, 10^2]
[38] P10S [для корректного вывода чисел, степени 10, 10^1]
[39] P1S [для корректного вывода чисел, степени 10, 10^0]
[40] QS [для формирования чисел]
[41] #S [перевод на цифровой регистр]
[42] A40S [загрузка в аккумулятор символа формирования чисел]
[43] !S [символ пробела]
[44] &S [символ переноса строки на новую]
[45] @S [символ возврата каретки]
[46] O43S [печать телепринтером пробельного символа]
[47] O33S [печать телепринтером следующей цифры числа в 10СС]
[48] PS [число для вывода]
[49] A46S [загружаю в аккумулятор команду печати пробела для исполнения из 46 ячейки]
[50] T65S [загружаю в ячейку памяти 65, обнуляю аккумулятор]
[51] T300S [обнуляю аккумулятор]
[52] A35S [загружаю в аккумулятор число из ячейки памяти 35, 10000<<1]
[53] T34S [загружаю его в ячейку памяти 34, обнуляю аккумулятор]
[54] E61S [если число в аккумуляторе >= 0, перехожу к строке 61]
[55] T48S [загружаю новое значение числа для вывода в ячейку 48, обнуляю аккумулятор]
[56] A47S [загружаю число из 47 ячейки в аккумулятор]
[57] T65S [загружаю число из аккумулятора в 65, обнуляю аккумулятор]
[58] A33S [загружаю число из 33 ячейки в аккумулятор]
[59] A40S [прибавляю число из 40 ячейки к содержимому аккумулятора]
[60] T33S [загружаю число из аккумулятора в 33, обнуляю аккумулятор]
[61] A48S [загружаю число для вывода из ячейки памяти 48 в аккумулятор]
[62] S34S [вычитаю текущую степень десятки]
[63] E55S [если число >= 0, повторяю, перехожу к строке 55]
[64] A34S [загружаю степень десятки из ячейки 34 в аккумулятор]
[65] PS [цифра или пробел, в зависимости от ситуации]
[66] T48S [загружаю число из аккумулятора в ячейку 48, там число для вывода]
[67] T33S [загружаю число из аккумулятора в ячейку 33, там следующая цифра
десятичной записи числа]
[68] A52S [загружаю инструкцию из ячейки 52 в аккумулятор]
[69] A4S [прибавляю 1]
[70] U52S [записываю содержимое аккумулятора в ячейку 52]
[71] S42S [вычитаю из аккумулятора символ формирования чисел]
[72] G51S [если число в аккумуляторе < 0, перехожу к 51 ячейке]
[73] A103S [загружаю инструкцию из ячейки 103 в аккумулятор]
[74] T52S [загружаю содержимое аккумулятора в ячейку 52, обнуляю аккумулятор]
[75] PS [ячейка памяти для хранения инструкции возврата]
[76] PS [ячейка памяти для хранения индекса цикла]
[77] PS [const = 0]
[78] PS [const = 0]
[79] PS [const = 0]
[80] E100S [переход к строке 100]
[81] E104S [переход к строке 104]
[82] P5S [показатель треугольника Паскаля, вводится просто как число между P и S,
по правилам обычной арифметики в 10СС]
[83] E123S [переход к выводу переноса строки, строка программы 123]
[84] A110S [загружаю в аккумулятор число 2]
[85] T30S [выгружаю в ячейку памяти 30, обнуляю аккумулятор]
[86] O41S [перевод на цифровой регистр телепринтера]
[87] T300S [обнуляю аккумулятор]
[88] O44S [печатаю переноса строки на новую]
[89] O44S [печатаю переноса строки на новую]
[90] A76S [загружаю в аккумулятор индекс цикла]
[91] A4S [увеличиваю его на 1]
[92] T76S [перезаписываю изменённый индекс, обнуляю аккумулятор]
[93] E113S [безусловный переход к ячейке 113]
[94] T300S [обнуляю аккумулятор]
[95] A30S [загружаю в аккумулятор число из 30 ячейки, обнуляю аккумулятор]
[96] T48S [выгружаю в ячейку памяти 48, обнуляю аккумулятор]
[97] A80S [загружаю в аккумулятор инструкцию перехода из ячейки 80]
[98] T75S [загружаю её в 75 ячейку, обнуляю аккумулятор]
[99] E49S [перехожу к печати текущего числа]
[100] A81S [загружаю в аккумулятор инструкцию перехода из ячейки 81]
[101] T75S [выгружаю в ячейку памяти 75, обнуляю аккумулятор]
[102] E49S [перехожу к печати текущего числа]
[103] A35S [перехожу к печати текущего числа]
[104] A76S [загружаю в аккумулятор индекс цикла из ячейки 76]
[105] S82S [вычитаю показатель треугольника Паскаля]
[106] S110S [вычитаю 2]
[107] G87S [если полученное число <0, перехожу к строке 87]
[108] X0S [пустая команда]
[109] ZS [конец программы, сигнальный звонок]
[110] P1S [const = 2]
[111] P2S [const = 4]
[112] P0L [const = 1]
[113] T300S [обнуляю аккумулятор]
[114] A76S [загружаю в аккумулятор содержимое 76 ячейки]
[115] S111S [вычитаю содержимое 111 ячейки, 4]
[116] E124S [если число в аккумуляторе >=0, перехожу к 124 ячейке]
[117] T300S [иначе обнуляю аккумулятор]
[118] A30S [загружаю в аккумулятор число из 30 ячейки]
[119] T48S [загружаю в ячейку памяти 48, число для вывода, обнуляю аккумулятор]
[120] A83S [загружаю в аккумулятор инструкцию из адреса 83]
[121] T75S [загружаю ее в 75 ячейку]
[122] E49S [перехожу к печати числа из памяти]
[123] O44S [печатаю переноса строки на новую]
[124] O44S [печатаю переноса строки на новую]
[125] T300S [обнуляю аккумулятор]
[126] A82S [загружаю в аккумулятор показатель треугольника Паскаля]
[127] A110S [добавляю 2]
[128] S76S [вычитаю индекс цикла]
[129] T29S [записываю содержимое аккумулятора в ячейку 29, обнуляю аккумулятор]
[130] H29S [загружаю в умножающий регистр число из 29 ячейки]
[131] V30S [умножаю на число из 30 ячейки, результат в аккумуляторе]
[132] L64S [сдвигаю аккумулятор влево на 8 ячеек]
[133] L32S [сдвигаю аккумулятор влево на 7 ячеек]
[134] T30S [выгружаю число из аккумулятора в 30 ячейку памяти]
[135] T2S [выгружаю частное в ячейку памяти 2, обнуляю аккумулятор]
[136] A30S [загружаю делимое в аккумулятор из ячейки 30]
[137] T1S [записываю делимое в 1 ячейку, обнуляю аккумулятор]
[138] A1S [читаю содержимое делимого из ячейки памяти 1, начало цикла]
[139] S76S [вычитаю делитель из ячейки памяти 76]
[140] T1S [записываю новое значение делимого в ячейку 1, обнуляю аккумулятор]
[141] A2S [загружаю частное из ячейки 2]
[142] A110S [прибавляю 1 из ячейки памяти 110]
[143] T2S [записываю увеличенное на 1 частное в ячейку 2, обнуляю аккумулятор]
[144] A1S [выгружаю в аккумулятор делимое из ячейки 1]
[145] G147S [если делимое < 0, стоп, переход на строку 147]
[146] T1S [иначе записываю содержимое аккумулятора в ячейку 1, обнуляю аккумулятор]
[147] E138S[если делимое >= 0, повторять цикл деления, переход на 138 строку, конец цикла]
[148] T300S [обнуляю аккумулятор]
[149] A2S [выгружаю частное из ячейки 2]
[150] S110S [вычитаю 1 из ячейки памяти 110]
[151] U2S [загружаю частное обратно в ячейку 2]
[152] T30S [загружаю частное в ячейку 30, обнуляю аккумулятор]
[153] E94S [безусловный переход к строке 94, подготовка к выводу числа]


Что сказать про IO2? Поддерживает подпрограммы, относительную адресацию, набор команд расширен.
Та же программа на IO2:
Листинг 5. — EDSAC order code, IO2, n-я строка треугольника Паскаля.
..PK
T56K
[P6, подпрограмма для вывода чисел из стандартной библиотеки]
GKA3FT25@H29@VFT4DA3@TFH30@S6@T1F
V4DU4DAFG26@TFTFO5FA4DF4FS4F
L4FT4DA1FS3@G9@EFSFO31@E20@J995FJF!F
..PZ
[программа для нахождения n-й строки треугольника Паскаля]
GK [фиксирую абсолютное значение ячейки памяти для относительной индексации]
[0] XF [для отладки, нулевая инструкция]
[1] O34@ [вывод переведён на цифровой регистр, загрузка данных для печати из ячейки 34]
[2] O35@ [вывод новой строки, загрузка данных для печати из ячейки 35]
[3] O36@ [возврат каретки телепринтера, загрузка данных для печати из ячейки 36]
[4] TF [обнуление аккумулятора]
[5] A27@ [значение из ячейки 27 добавляется в аккумулятор]
[6] TF [запись этого значения в 0 ячейку для вывода, обнуление аккумулятора]
[7] A7@ [загрузка замкнутой подпрограммы по выводу числа]
[8] G56F [печать числа с использованием P6]
[9] T20@ [зануляю 20 ячейку памяти]
[10] A28@ [загружаю в аккумулятор индекс цикла]
[11] A31@ [добавляю 1]
[12] U28@ [обновляю значение индекса цикла в ячейке 28]
[13] T20@ [записываю значение индекса цикла в ячейку 20, обнуляю аккумулятор]
[14] A33@ [загружаю показатель в аккумулятор]
[15] A31@ [+1]
[16] S28@ [вычитаю текущий индекс из ячейки 28]
[17] T20@ [записываю значение индекса цикла в ячейку 20, обнуляю аккумулятор]
[18] E37@ [безусловный переход к умножению, ячейка 37]
[19] PD [const = 1]
[20] XF [нулевая инструкция]
[21] XF [нулевая инструкция]
[22] A33@ [загружаю показатель из ячейки 33 в аккумулятор]
[23] A31@ [+1]
[24] S28@ [вычитаю содержимое 28 ячейки, индекс]
[25] E2@ [если >= 0, повторяю цикл, переход к строке 2]
[26] ZF [конец программы, сигнальный звонок]
[27] PD [число для вывода]
[28] PF [индекс цикла]
[29] PD [используется в подпрограмме для печати]
[30] PD [используется в подпрограмме для печати]
[31] PD [const = 1]
[32] P1F [символ перехода на новую строку]
[33] P2D [показатель треугольника Паскаля, записывается по правилам EDSAC]
[34] #F [символ перевода вывода на цифровой регистр]
[35] @F [символ возврата каретки]
[36] &F [символ переноса строки на новую]
[37] H20@ [загружаю в умножающий регистр число из 20 ячейки]
[38] V27@ [умножаю на число из 27 ячейки, результат в аккумуляторе]
[39] L1024F [сдвигаю аккумулятор влево на 12 ячеек]
[40] L4F [сдвигаю аккумулятор влево на 4 ячеек]
[41] T20@ [выгружаю число из аккумулятора в 20 ячейку памяти, обнуляю аккумулятор]
[42] T102@ [выгружаю частное в ячейку памяти 102, обнуляю аккумулятор]
[43] A20@ [загружаю делимое в аккумулятор из ячейки 20]
[44] T101@ [записываю делимое в 101 ячейку, обнуляю аккумулятор]
[45] A101@ [читаю содержимое делимого из ячейки памяти 101, начало цикла]
[46] S28@ [вычитаю делитель из ячейки памяти 28]
[47] T101@ [записываю новое значение делимого в ячейку 101, обнуляю аккумулятор]
[48] A102@ [загружаю частное из ячейки 102]
[49] A31@ [прибавляю 1 из ячейки памяти 31]
[50] T102@ [записываю увеличенное на 1 частное в ячейку 102, обнуляю аккумулятор]
[51] A101@ [выгружаю в аккумулятор делимое из ячейки 101]
[52] G54@ [если делимое < 0, стоп, переход на строку 54]
[53] T101@ [иначе записываю содержимое аккумулятора в ячейку 101, обнуляю аккумулятор]
[54] E45@ [если делимое >= 0, повторять цикл деления, переход на 45 строку, конец цикла]
[55] T200@ [чищу содержимое аккумулятора]
[56] A102@ [выгружаю частное]
[57] S31@ [вычитаю 1 из ячейки памяти 102]
[58] U102@ [загружаю частное обратно в ячейку 102]
[59] T27@ [загружаю частное в ячейку 27, обнуляю аккумулятор]
[60] E22@ [безусловный переход к строке 22, подготовка к выводу числа]
[61] EZPF [указатель на исполнение кода]



Рис 4. — Вывод для показателя = 5.

Надеюсь, Вам понравилась эта статья и Вы прониклись истоками программирования. Когда пишешь подобный код, начинаешь ценить все те уровни абстракции, которые появились впоследствии, понимаешь, какой же большой путь прошли ЯП, чтобы стать такими, какие они есть. Спасибо за Ваше время!

P. S. Милейшие друзья из губернии N, не стоит благодарности за любезно предоставленный мной код, если у Вас совпал со мной вариант. Удачи с RISC-V!

P. P. S. Прекрасные примеры кода для EDSAC IO2 приведены здесь.

P. P. P. S. Код публикую под лицензией MIT.
Copyright 2021, ALEKSEI VASILEV
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the «Software»), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED «AS IS», WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Let's block ads! (Why?)

Комментариев нет:

Отправить комментарий