Wirth N. SET: A neglected data type, and its compilation for the ARM / Вирт Н. SET: Недооцениваемый тип данных и его компиляция для ARM

Оригинал: Wirth N. SET: A neglected data type, and its compilation for the ARM, 08.08.2007 (копия)

Перевод: Темиргалеев Е.Э. (.odc) / коррекция: Ткачёв Ф.В.

Библиотека, Wirth N., Темиргалеев Е.Э., Ткачёв Ф.В.

SET: Недооцениваемый тип данных и его компиляция для ARM

Хотя тип данных SET был введён в 1970 году в Паскале и остался в Модуле и Обероне, похоже, что он остается недооцененным. Идею предложил Ч. Э. Р. Хоор, пытавшийся придать типам вроде Bits и Bitset более привлекательный вид, согласующийся с математическими абстракциями. Ключевая идея была в том, чтобы рассматривать биты машинного слова как множество целых чисел — номеров отдельных битов. В Паскале объявление типа множество явно указывало тип элементов множества. Обычно это были перечислимые типы и типы-диапазоны. Для Оберона вместо общих множеств были выбраны множества небольших целых чисел в диапазоне от 0 до n¹⁾, где n — размер машинного слова. Рассмотрим примеры для n = 8:

0	00000000	{}
1	00000001	{0}
5	00000101	{0, 2}
55	01010101	{0, 2, 4, 6}

Игнорирование данного типа большинством программистов может быть связано с ограничением элементов малыми целыми. Более того, я полагаю, здесь может быть замешана боязнь тяжеловесного механизма реализации, сокрытого понятием множества, возможно задействующего динамические, связные структуры данных, приводящие к его медленной реализации. Следует понимать, что SET означает «множество небольших целых».

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

(n = 2) OR (n = 3) OR (n = 5) OR (n = 7) OR (n = 11) OR (n = 13) OR (n = 17)

которая может быть выражена гораздо проще:

n IN {2, 3, 5, 7, 11, 13, 17}

Цель этой заметки — поощрить использование этого типа данных (Оберон) программистами, и показать, что он не просто удобный, но и очень эффективный.

В языке Оберон, значение типа SET представляется 32-битным словом. Операции — объединение множеств (+), пересечение (*), разность (-) и симметрическая разность (/). Ещё имеются операции дополнения (унарный минус) и отношений — равенство и подмножество. Простой пример покажет, насколько легко обеспечить здесь эффективную реализацию.²⁾ Пусть s0 = {0, 1} и s1 = {0, 2}. Тогда

s0 + s1 = {0, 1, 2}	s0 – s1 = {1}
s0 * s1 = {0}	s0 / s1 = {1, 2}

Очевидно, что такие операции с множествами можно непосредственно выразить через простые и быстрые побитовые операции, доступные на любой машине, соответственно

union	or	0011 or 0101 = 0111
intersection	and	0011 and 0101 = 0001
difference	and not (bic)	0011 and 1010 = 0010
sym. difference	xor	0011 xor 0101 = 0110

Дополнение множества реализуется инструкцией not, а отношение подмножества выражается через разность

s0 ⊆ s1 ≡ s0 – s1 = {}

Таким образом, как приводимый ниже модуль, так и результат его компиляции для процессора ARM, состоят всего лишь из нескольких инструкций. Заметим, что здесь используется механизм размещения переменных в регистрах (здесь: s0 в R0, s1 в R1, и s2 в R2).

	MODULE M;
		PROCEDURE* P;
			VAR s0, s1, s2: SET;
		BEGIN s0 := s1 + s2; s0 := s1 * s2; s0 := s1 - s2; s0 := s1 / s2;
			s0 := -s1; s0 := s0*s1 + s0/s1;
		END P;
	END M.

	3	E1810002	OR	R0 R1 R2	s0 := s1 + s2
	4	E0010002	AND	R0 R1 R2	s0 := s1 * s2
	5	E1C10002	BIC	R0 R1 R2	s0 := s1 - s2
	6	E0210002	XOR	R0 R1 R2	s0 := s1 / s2
	7	E1E00001	MVN	R0 R0 R1	s0 := -s1
	8	E0009001	AND	R9 R0 R1
	9	E0208001	XOR	R8 R0 R1
	10	E1890008	OR	R0 R9 R8

Вычисление значений типа множество по-возможности выполняется во время компиляции, т.е. когда элементы — константы.

	MODULE M;
		PROCEDURE* P;
			VAR s0: SET;
		BEGIN s0 := {}; s0 := {0}; s0 := {8, 10 .. 12, 15};
		END P;
	END M.

	11	E3A00000	MOV	R0 R0 0	s0 := {}
	12	E3A00001	MOV	R0 R0 1	s0 := {0}
	13	E3A09C9D	MOV	R9 R0 40192	s0 := {8, 10 .. 12, 15}
	14	E1A00009	MOV	R0 R0 R9

Случаи, когда элементы множества являются общими выражениями, более затруднительны. Фактически, они ставят перед разработчиком компилятора по-настоящему сложную задачу. К счастью, процессор ARM предоставляет эффективный, систематический набор инструкций. Его выдающимся свойством является возможность выполнения в рамках одной инструкции и за один такт арифметической или побитовой операции одновременно со сдвигом второго операнда. Последнее ведёт к удивительно короткому коду для показанных ниже операторов. (Замечание: LSL означает “логический сдвиг влево”. m в регистре R11, n в R10).

	MODULE M; (*sets*)
		PROCEDURE* P(m, n: INTEGER);
			VAR s0, s1, s2: SET;
		BEGIN s0 := {m}; s0 := {0 .. n}; s0 := {m .. n}; s0 := {m+n .. m-n};
			IF n IN s0 THEN s0 := {0} END ;
			IF s1 <= s2 THEN s0 := {4} END
		END P;
	END M.

	3	E3A08001	MOV	R8 R0 1 
	4	E1B00B18	MOV	R0 R0 R8 LSL R11	s0 := {m}

	5	E3E09001	MVN	R9 R0 1 
	6	E1E00A19	MVN	R0 R0 R9 LSL R10	s0 := {0 .. n}

	7	E3E09001	MVN	R9 R0 1 
	8	E1E09A19	MVN	R9 R0 R9 LSL R10 
	9	E3E08000	MVN	R8 R0 0 
	10	E0090B18	AND	R0 R9 R8 LSL R11	s0 := {m .. n}

	11	E09B900A	ADD	R9 R11 R10	R9 := m+n
	12	E05B800A	SUB	R8 R11 R10	R8 := m-n
	13	E3E07001	MVN	R7 R0 1 
	14	E1E07817	MVN	R7 R0 R7 LSL R8 
	15	E3E06000	MVN	R6 R0 0 
	16	E0070916	AND	R0 R7 R6 LSL R9	s0 := {m+n .. m-n}
	17	E3A09001	MOV	R9 R0 1
	18	E1100A19	TST	R0 R0 R9 LSL R10	IF n IN s0 THEN
	19	0A000000	BEQ	0
	20	E3A00001	MOV	R0 R0 1

	21	E1D1E002	BIC	LNK R1 R2	IF s1 <= s2 THEN
	22	1A000000	BNE	0
	23	E3A00E01	MOV	R0 R0 16

См. также

¹⁾ не включительно — прим. перев.

²⁾ Фактически речь идёт об известном математическом факте эквивалентности булевых алгебр алгебрам подмножеств. См. любой приличный учебник дискретной математики для программистов. — прим. корр.