Немного компьютерной лингвистики

[spamsink]

Если бы я знал ответ на более или менее ретрокомпьютерный вопрос, который хочу задать, из него могла бы получиться неплохая задачка для олимпиад по лингвистике. А пока это только вопрос в воздух.



Имеется двоичный код (считай, "черный ящик"), реализующий функциональность хранилища данных, позволяющий работать с массивами пар "ключ-данные", хранящихся на внешних устройствах, адресуемых по "логический номер устройства-номер блока"

Известен неполный интерфейс к нему (мелкие детали опущены):

• создать новый каталог верхнего уровня, задавая Номер Устройства/Начальный Номер Блока/Число Блоков для каталога
  
• создать в каталоге верхнего уровня массив, задавая имя массива и НУ/ННБ/ЧБ, где массив будет храниться
  
• открыть массив по имени, он становится текущим
  
• занести в текущий массив запись "ключ-данные" (если запись с таким ключом уже есть, возвращается ошибка)
  
• считать из текущего массива данные по ключу
  
• удалить из текущего массива запись по ключу
  
• модифицировать новыми данными в текущем массиве запись по ключу (если записи с таким ключом не было, выполняется как "занести")
  

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

• создать каталог: 10-21
  
• создать массив: 31-11-15-21-26-11-14-12-10-21
  
• открыть массив: 31-11-14-12-25
  
• занести запись: 11-15-21-26 (в случае ошибки отрабатывает только 11-15)
  
• считать данные: 11-14-22
  
• удалить запись: 11-14-23-27
  
• модифицировать: 11-15-00-21-26-40 (подаётся на вход и выполняется, если такой записи не было); если была, то вместо этого выполняется 11-15-20
  

Предлагается, используя навыки логического мышления, вывести из этого смысл и назначение использованных микрокоманд, насколько это возможно. У меня есть несколько идей, но полной ясности я не достиг.

Comments

[dijifi]

00 начало модификации
10 каталог
11 поиск
12 открыть массив
14 выборка для чтения или удаления
15 выборка для модификации
20 запись данных
21 запись
22 чтение данных
23 удаление
26 обновить индексацию
27 обновить индексацию при удалении
31 массив
40 конец модификации

[spamsink]

Грубо, так. Более точно, что я понял,

31 - выбор корневого каталога в качестве текущего массива

20 - копирование данных в массив в уже отведенное место
22 - копирование данных из массива в память

поэтому 21, видимо, не просто запись, а "malloc+запись"

С механизмом условного перехода (откуда берётся команда 20 и зачем нужна команда 40) я ещё не разобрался.

Хак "31-11-14-22" позволил прочитать запись в корневом каталоге. Там 2 слова - адрес массива, указанный при создании, и какие-то служебные данные, включающие дату то ли создания, то ли модификации.

[sassa_nf]

> откуда берётся команда 20

interrupt handler?

[spamsink]

Что делают 12 и 25, пока не очень ясно. 25, возможно - установка массива в качестве текущего; 12 - ???

[dijifi]

Скорее 12 текущий, 25 первоначальная индексация

[sassa_nf]

12 - read "НУ/ННБ/ЧБ", and position "reader/writer" at that location.

as in: 11-14 - locate slot for key as "it", 12 - load "its" "НУ/ННБ/ЧБ" as "it", then 25 - "make it current", or 10-21 - "создать каталог"

then:

31-11-15-21-26-11-14-12-10-21 is:

31 - cd / - load "НУ/ННБ/ЧБ" of the root
11-15 - create slot for key
21-26 - write there "НУ/ННБ/ЧБ" of the array
11-14 - locate slot for key again (so perhaps 11-15 leaves something on the stack, and 21-26 consumes it)
12 - position writer at "НУ/ННБ/ЧБ" of the array in the previously located slot (so perhaps 11-14 also leaves something on the stack, and 12 consumes it)
10-21 - "создать каталог"

[sassa_nf]

how do you know all these have distinct functions manipulating high level abstractions like catalogue or array?

what if 11 is "push r0 onto operand stack"

what I find "inconsistent" in your description, is:

> создать массив: 31-11-15-21-26-11-14-12-10-21
> занести запись: 11-15-21-26

From the second line we conclude 11-15-21-26 refers to "key" and "value" to store somewhere. But there is no apparent "value" to store in 31-11-15-21-26, if we choose 31 to only be "cd /".

If we assume that the creation of array is the remainder of the clause, "11-14-12" followed by "создать каталог" "10-21" (which possibly means arrays are associative), then "11-14-12" seems to be a read-only part of the statement, as it is also used in "открыть массив", where we don't expect any modification operations.

> подаётся на вход и выполняется, если такой записи не было

it is unclear why in this case it would be different from "занести запись", of which we see "11-15" and "21-26". So one would expect "00" to be a "conditional", but it would need executing, wouldn't it, whereas you say "11-15-20" gets executed.

[sassa_nf]

for example, one might say "11-15" is "create a slot for a key", and "11-14" is "locate the slot for a key", but "модифицировать" shouldn't need to create it, if it exists - and yet, you say "11-15" is executed in both cases, when the entry exists and when it doesn't exist.

[spamsink]

The top catalog is a key-value store for data arrays and their locations + some meta-info; their structure is the same. Thus, creating a data array is writing a (name-location) pair in the top catalog + initializing the array.

which possibly means arrays are associative

Duh. That's what позволяющий работать с массивами пар "ключ-данные" implies.

The mechanism of conditionals is still unclear. It could be that command 00 reads some flags and constructs an opcode to execute based on them. Like
opcode = (entry_exists << 5) | .... ; if (opcode) execute(opcode); else continue;

And opcode 20 does whatever is necessary to fulfill the request.

[spamsink]

My mistake, I misread the octal dump. For modification the sequence of instructions given is
11-15-00-21-26-40-20

so 40 means stop, and 00 means "conditionally skip the next 3 instructions".