Таблицы управления — это таблицы , которые управляют потоком управления или играют важную роль в управлении программой. Не существует жестких правил относительно структуры или содержания таблицы управления — ее квалификационным атрибутом является ее способность направлять поток управления каким-либо образом посредством «выполнения» процессором или интерпретатором . Проектирование таких таблиц иногда называют таблично-управляемым проектированием [1] [2] (хотя это обычно относится к автоматической генерации кода из внешних таблиц, а не к прямым таблицам времени выполнения). В некоторых случаях таблицы управления могут быть конкретными реализациями программирования на основе конечных автоматов . Если есть несколько иерархических уровней таблицы управления, они могут вести себя аналогично конечным автоматам UML [3]
Управляющие таблицы часто имеют эквивалент условных выражений или ссылок на функции, встроенных в них, обычно подразумеваемых их относительным положением столбца в списке ассоциаций . Управляющие таблицы уменьшают необходимость программирования похожих структур или операторов программы снова и снова. Двумерная природа большинства таблиц делает их более простыми для просмотра и обновления, чем одномерная природа программного кода.
В некоторых случаях непрограммисты могут быть назначены для поддержки содержимого контрольных таблиц. Например, если введенная пользователем поисковая фраза содержит определенную фразу, URL (веб-адрес) может быть назначен в таблице, которая контролирует, куда направляется пользователь поиска. Если фраза содержит «юбка», то таблица может направить пользователя на «www.shopping.example/catalogs/skirts», которая является страницей каталога продукции «юбки». (Пример URL не работает на практике). Персонал по маркетингу может управлять такой таблицей вместо программистов.
Таблицы могут иметь несколько измерений, фиксированной или переменной длины и обычно переносимы между компьютерными платформами , требуя только изменения интерпретатора, а не самого алгоритма – логика которого по сути воплощена в структуре и содержимом таблицы. Структура таблицы может быть похожа на ассоциативный массив multimap , где значение данных (или комбинация значений данных) может быть сопоставлено с одной или несколькими функциями, которые должны быть выполнены.
Возможно, в своей простейшей реализации таблица управления иногда может быть одномерной таблицей для прямого перевода необработанного значения данных в соответствующее смещение подпрограммы , индекс или указатель, используя необработанное значение данных либо напрямую в качестве индекса массива, либо выполняя некоторую базовую арифметику над данными заранее. Этого можно достичь за постоянное время (без линейного поиска или двоичного поиска с использованием типичной таблицы поиска в ассоциативном массиве ). В большинстве архитектур это можно сделать за две или три машинные инструкции — без каких-либо сравнений или циклов. Этот метод известен как « тривиальная хэш-функция » или, при использовании специально для таблиц ветвлений, « двойная диспетчеризация ». Чтобы это было осуществимо, диапазон всех возможных значений данных должен быть небольшим (например, значение символа ASCII или EBCDIC , которое имеет диапазон шестнадцатеричного «00» — «FF». Если фактический диапазон гарантированно меньше этого, массив можно усечь до менее чем 256 байт).
Таблица для перевода необработанных значений ASCII (A,D,M,S) в новый индекс подпрограммы (1,4,3,2) за постоянное время с использованием одномерного массива
(пробелы в диапазоне показаны как «..» для этого примера, что означает «все шестнадцатеричные значения до следующей строки». Первые два столбца не являются частью массива)
В программировании на основе автоматов и псевдоразговорной обработке транзакций , если число отдельных состояний программы невелико, можно использовать управляющую переменную «плотной последовательности» для эффективного управления всем потоком основного цикла программы.
Двухбайтовое значение необработанных данных потребует минимальный размер таблицы в 65 536 байт — для обработки всех входных возможностей — при этом позволяя всего 256 различных выходных значений. Однако эта техника прямого перевода обеспечивает чрезвычайно быструю проверку и преобразование в (относительный) указатель подпрограммы, если эвристика , вместе с достаточно быстрой памятью доступа, позволяет ее использовать.
Таблица ветвлений — это одномерный «массив» смежных инструкций ветвления/перехода машинного кода для осуществления многопутевого ветвления к метке программы при ветвлении непосредственно предшествующей и индексированной ветвью. Иногда она генерируется оптимизирующим компилятором для выполнения оператора switch — при условии, что входной диапазон небольшой и плотный, с небольшим количеством пробелов (как создано в предыдущем примере массива) [1].
Хотя они довольно компактны — по сравнению с несколькими эквивалентными Ifоператорами — инструкции ветвления все еще несут в себе некоторую избыточность, поскольку код операции ветвления и маска кода условия повторяются вместе со смещениями ветвления. Таблицы управления, содержащие только смещения к меткам программ, могут быть построены для преодоления этой избыточности (по крайней мере, в языках ассемблера) и при этом требуют лишь незначительных накладных расходов по времени выполнения по сравнению с обычной таблицей ветвления.
Чаще всего управляющую таблицу можно рассматривать как таблицу истинности или как исполняемую («двоичную») реализацию печатной таблицы решений (или дерева таблиц решений на нескольких уровнях). Они содержат (часто подразумеваемые) предложения вместе с одним или несколькими связанными «действиями». Эти действия обычно выполняются общими или специально созданными подпрограммами , которые вызываются программой « интерпретатора ». Интерпретатор в этом случае эффективно функционирует как виртуальная машина , которая «выполняет» записи управляющей таблицы и, таким образом, обеспечивает более высокий уровень абстракции , чем базовый код интерпретатора.
Таблица управления может быть построена аналогично оператору switch, зависящему от языка , но с дополнительной возможностью проверки комбинаций входных значений (используя условия AND / OR в булевом стиле ) и потенциального вызова нескольких подпрограмм (вместо простого набора значений и меток программы «перейти к»). (Конструкция оператора switch в любом случае может быть недоступна или иметь путано различающиеся реализации в языках высокого уровня ( HLL ). Концепция таблицы управления, для сравнения, не имеет внутренних языковых зависимостей, но тем не менее может быть реализована по-разному в соответствии с доступными функциями определения данных выбранного языка программирования.)
Таблица управления по сути воплощает « сущность » обычной программы, лишенную синтаксиса языка программирования и зависящих от платформы компонентов (например, IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL) и «сжатую» до ее переменных (например, input1), значений (например, 'A','S','M' и 'D') и идентификаторов подпрограмм (например, 'Add','subtract,..' или #1, #2,..). Структура самой таблицы обычно подразумевает (по умолчанию) задействованные логические операции — такие как 'проверка на равенство', выполнение подпрограммы и 'следующая операция' или следование последовательности по умолчанию (вместо того, чтобы они были явно указаны в операторах программы — как требуется в других парадигмах программирования ).
Многомерная таблица управления обычно, как минимум, содержит пары значение/действие и может дополнительно содержать операторы и информацию о типе , например, местоположение, размер и формат входных или выходных данных, требуется ли преобразование данных (или другие нюансы обработки во время выполнения ) до или после обработки (если это уже не подразумевается в самой функции). Таблица может содержать или не содержать индексы или относительные или абсолютные указатели на общие или настраиваемые примитивы или подпрограммы, которые должны быть выполнены в зависимости от других значений в «строке».
Приведенная ниже таблица применима только к «input1», поскольку в таблице не указан конкретный вход.
условия и действия, подразумеваемые структурой
(Это параллельное сочетание значения и действия имеет сходство с конструкциями в событийно-управляемом программировании , а именно «обнаружение событий» и «обработка событий», но без (обязательно) асинхронной природы самого события)
Разнообразие значений, которые могут быть закодированы в управляющей таблице, во многом зависит от используемого компьютерного языка . Язык ассемблера предоставляет самый широкий спектр типов данных , включая (для действий) возможность непосредственно исполняемого машинного кода . Обычно управляющая таблица будет содержать значения для каждого возможного класса соответствия входных данных вместе с соответствующим указателем на подпрограмму действия. Некоторые языки заявляют, что не поддерживают указатели (напрямую), но тем не менее могут вместо этого поддерживать индекс , который может использоваться для представления «относительного номера подпрограммы» для выполнения условного выполнения, контролируемого значением в записи таблицы (например, для использования в оптимизированном операторе SWITCH – разработанном с нулевыми зазорами (т. е. многоканальный переход )).
Комментарии, размещенные над каждым столбцом (или даже встроенная текстовая документация), могут сделать таблицу решений «удобочитаемой» даже после «сжатия» (кодирования) до ее основных частей (и все еще в целом соответствующей исходной спецификации программы – особенно если печатная таблица решений, перечисляющая каждое уникальное действие, создается до начала кодирования). Записи таблицы также могут опционально содержать счетчики для сбора статистики времени выполнения для «поточной» или более поздней оптимизации
Таблицы управления могут находиться в статическом хранилище, во вспомогательном хранилище , таком как плоский файл или в базе данных , или могут быть частично или полностью созданы динамически во время инициализации программы из параметров (которые сами могут находиться в таблице). Для оптимальной эффективности таблица должна быть резидентной в памяти, когда интерпретатор начинает ее использовать.
Интерпретатор может быть написан на любом подходящем языке программирования, включая язык высокого уровня . Правильно спроектированный универсальный интерпретатор вместе с хорошо выбранным набором универсальных подпрограмм (способных обрабатывать наиболее часто встречающиеся примитивы ) потребует дополнительного обычного кодирования только для новых пользовательских подпрограмм (в дополнение к указанию самой таблицы управления). Интерпретатор, по желанию, может применяться только к некоторым четко определенным разделам полной прикладной программы (например, к основному циклу управления ), а не к другим, «менее условным», разделам (например, к инициализации программы, завершению и т. д.).
Интерпретатор не должен быть чрезмерно сложным или созданным программистом с передовыми знаниями автора компилятора, и может быть написан так же, как и любая другая прикладная программа, за исключением того, что он обычно разрабатывается с учетом эффективности. Его основная функция — «выполнять» записи таблицы как набор «инструкций». Не требуется разбора записей таблицы управления, и поэтому они должны быть разработаны, насколько это возможно, «готовыми к выполнению», требуя только «подключения» переменных из соответствующих столбцов к уже скомпилированному универсальному коду интерпретатора. Инструкции программы , в теории, бесконечно расширяемы и представляют собой (возможно, произвольные) значения в таблице, которые имеют смысл только для интерпретатора. Поток управления интерпретатора обычно осуществляется путем последовательной обработки каждой строки таблицы, но может быть изменен определенными действиями в записях таблицы.
Эти произвольные значения могут быть разработаны с учетом эффективности — путем выбора значений, которые могут использоваться как прямые индексы для данных или указателей на функции . Для определенных платформ/ языков они могут быть специально разработаны для минимизации длины пути инструкций с использованием значений таблицы ветвлений или даже, в некоторых случаях, например, в JIT- компиляторах, состоять из непосредственно исполняемых « фрагментов » машинного кода (или указателей на них).
Подпрограммы могут быть закодированы либо на том же языке, что и сам интерпретатор, либо на любом другом поддерживаемом языке программирования (при условии, что существуют подходящие межъязыковые механизмы связи «Вызов»). Выбор языка для интерпретатора и/или подпрограмм обычно зависит от того, насколько переносимым он должен быть на различных платформах . Может быть несколько версий интерпретатора для повышения переносимости управляющей таблицы. Указатель подчиненной управляющей таблицы может опционально заменять указатель подпрограммы в столбцах «действие», если интерпретатор поддерживает эту конструкцию, представляя условный «переход» на более низкий логический уровень, имитируя традиционную структурированную структуру программы .
На первый взгляд, использование управляющих таблиц, по-видимому, добавляет довольно много к накладным расходам программы , требуя, как это и происходит, процесса интерпретатора перед выполнением операторов «родного» языка программирования. Однако это не всегда так. Разделяя (или «инкапсулируя») исполняемый код от логики, как выражено в таблице, его можно легче нацелить на выполнение его функции наиболее эффективно. Это можно наиболее наглядно испытать в приложении электронных таблиц – где базовое программное обеспечение электронных таблиц прозрачно преобразует сложные логические «формулы» наиболее эффективным способом, чтобы отобразить свои результаты.
Примеры ниже были выбраны частично для иллюстрации потенциального прироста производительности, который может не только значительно компенсировать дополнительный уровень абстракции, но и улучшить – то, что в противном случае могло бы быть – менее эффективным, менее поддерживаемым и более длинным кодом. Хотя приведенные примеры относятся к языку ассемблера «низкого уровня» и к языку C , можно увидеть, что в обоих случаях для реализации подхода с использованием управляющей таблицы требуется очень мало строк кода, и при этом можно достичь очень значительных постоянных улучшений производительности, сократить повторяющееся кодирование исходного кода и повысить ясность по сравнению с многословными конструкциями обычного языка программ. См. также цитаты Дональда Кнута относительно таблиц и эффективности многоканального ветвления в этой статье.
Следующие примеры произвольны (и основаны только на одном входе для простоты), однако их цель — просто продемонстрировать, как поток управления может быть реализован с помощью таблиц вместо обычных операторов программы. Должно быть ясно, что этот метод можно легко расширить для работы с несколькими входами, либо увеличив количество столбцов, либо используя несколько записей таблицы (с необязательным оператором and/or). Аналогично, используя (иерархические) «связанные» таблицы управления, можно реализовать структурное программирование (опционально используя отступы для выделения подчиненных таблиц управления).
"CT1" — пример таблицы управления, которая является простой таблицей поиска . Первый столбец представляет входное значение для проверки (подразумеваемым 'IF input1 = x') и, если TRUE, соответствующий 2-й столбец ('action') содержит адрес подпрограммы для выполнения вызова ( или перехода к — аналогично оператору SWITCH ). Это, по сути, многоканальная ветвь с возвратом (форма " динамической диспетчеризации "). Последняя запись — это случай по умолчанию, когда совпадение не найдено.
СТ1
Для языков программирования, которые поддерживают указатели внутри структур данных наряду с другими значениями данных, приведенную выше таблицу (CT1) можно использовать для направления потока управления в соответствующие подпрограммы в соответствии с совпадающим значением из таблицы (без столбца, указывающего на иное, в этом простом случае предполагается равенство).
Пример языка ассемблера для IBM/360 (максимальный диапазон адресов 16 Мб) или Z/Architecture
Никаких попыток оптимизировать поиск в кодировании для этого первого примера не предпринималось, и вместо этого он использовал простую технику линейного поиска — исключительно для иллюстрации концепции и демонстрации меньшего количества исходных строк. Для обработки всех 256 различных входных значений потребовалось бы около 265 строк исходного кода (в основном однострочные записи таблицы), тогда как для множественных «сравнений и ветвлений» обычно потребовалось бы около 512 исходных строк (размер двоичного файла также примерно вдвое меньше, каждая запись таблицы требует всего 4 байта вместо примерно 8 байтов для серии инструкций «сравнить немедленно»/ветвления (для больших входных переменных экономия еще больше).
* ------------------ устный переводчик --------------------------------------------* LM R14,R0,=A(4,CT1,N) Установите R14=4, R15 --> таблица, а R0 =количество записей в таблице (N) TRY CLC INPUT1,0(R15) ********* Найденное значение в записи таблицы? BE ACTION * loop * YES, загрузить указатель регистра на подпрограмму из таблицы AR R15,R14 * * НЕТ, Укажите на следующую запись в CT1, добавив R14 (=4) BCT R0,TRY ********* Назад, пока не закончится счет, затем пропустить . действие по умолчанию ... ни одно из значений в таблице не совпадает, сделайте что-нибудь другое LA R15,4(R15) указывают на запись по умолчанию (за концом таблицы) ДЕЙСТВИЕ L R15,0(R15) получить указатель на R15,откуда указывает R15 BALR R14,R15 Выполнить подпрограмму ("CALL" и вернуться) B END завершить эту программу * ------------------ таблица управления -----------------------------------------* * | этот столбец допустимых значений EBCDIC или ASCII проверяется '=' относительно переменной 'input1' * | | этот столбец представляет собой 3-байтовый адрес соответствующей подпрограммы * вв CT1 DC C'A',AL3(ADD) НАЧАЛО таблицы управления (длина записи 4 байта) DC C'S',AL3(ВЫЧИТАНИЕ) DC C'M',AL3(УМНОЖИТЬ) DC C'D',AL3(ДЕЛИТЬ) N EQU (*-CT1)/4 количество допустимых записей в таблице (общая длина/длина записи) DC C'?',AL3(DEFAULT) запись по умолчанию – используется при сквозном просмотре для перехвата всех Входная переменная INPUT1 DS C находится в этой переменной * ------------------ подпрограммы -------------------------------------------* ДОБАВИТЬ подпрограмму CSECT № 1 (здесь она показана как отдельная CSECT, но может . в качестве альтернативы может быть встроенным кодом) . инструкция(и) по добавлению BR R14 возврат Подпрограмма SUBTRACT CSECT №2 . инструкция(ы) для вычитания BR R14 возврат . и т. д..улучшение производительности интерпретатора в примере выше
Улучшенный интерпретатор (в среднем до 26 раз меньше выполняемых инструкций , чем в примере выше, где n= от 1 до 64 и до 13 раз меньше, чем потребовалось бы при использовании множественных сравнений).
Для обработки 64 различных входных значений требуется около 85 строк исходного кода (или меньше) (в основном однострочные записи таблицы), тогда как для множественного «сравнения и ветвления» потребуется около 128 строк (размер двоичного файла также уменьшается почти вдвое — несмотря на дополнительную таблицу размером 256 байт, необходимую для извлечения второго индекса).
* ------------------ устный переводчик --------------------------------------------* SR R14,R14 ********* Установите R14=0 CALC IC R14,INPUT1 * calc * поместить байт EBCDIC в биты младшего порядка (24–31) R14 IC R14,CT1X(R14) * * используйте значение EBCDIC как индекс в таблице 'CT1X' для получения нового индекса НАЙДЕНО L R15,CT1(R14) ********* получить указатель на подпрограмму, используя индекс (0,4, 8 и т.д.) BALR R14,R15 Выполнить подпрограмму ("CALL" и вернуться или по умолчанию) B END завершить эту программу * --------------- дополнительная таблица трансляции (EBCDIC --> указатель таблицы INDEX) 256 байт----* CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 одинаковых наборов по 16 байт x'00 * представляет X'00 – x'BF' DC AL1(00, 04 ,00,00, 16 ,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF' DC AL1(00,00,00,00, 12 ,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF' DC AL1(00,00, 08 ,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF' DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF' * ассемблер можно использовать для автоматического расчета значений индекса и сделать значения более удобными для пользователя * (например, «04» можно заменить символическим выражением «PADD-CT1» в таблице CT1X выше) * изменен CT1 (добавлено действие по умолчанию, когда индекс = 00, одно измерение, полный 31-битный адрес) CT1 DC A(DEFAULT) индекс =00 НАЧАЛО таблицы управления (4-байтовые константы адреса) PADD DC A(ADD) =04 PSUB DC A(ВЫЧИТАНИЕ) =08 PMUL DC A(УМНОЖИТЬ) =12 PDIV DC A(ДЕЛИТЬ) =16 * остальная часть кода остается такой же, как в первом примереДальнейшее улучшение интерпретатора (в среднем до 21 раза меньше выполняемых инструкций (где n>=64) , чем в первом примере, и до 42 раз меньше, чем потребовалось бы при использовании множественных сравнений).
Для обработки 256 различных входных значений потребуется около 280 строк исходного кода или меньше (в основном однострочные записи таблиц), тогда как для множественных «сравнений и ветвлений» потребуется около 512 строк (размер двоичного файла также уменьшается почти вдвое).
* ------------------ устный переводчик --------------------------------------------* SR R14,R14 ********* Установите R14=0 CALC IC R14,INPUT1 * calc * поместить байт EBCDIC в биты младшего порядка (24–31) R14 IC R14,CT1X(R14) * * используйте значение EBCDIC как индекс в таблице 'CT1X' для получения нового индекса SLL R14,2 * * умножить индекс на 4 (дополнительная инструкция) НАЙДЕНО L R15,CT1(R14) ********* получить указатель на подпрограмму, используя индекс (0,4, 8 и т.д.) BALR R14,R15 Выполнить подпрограмму ("CALL" и вернуться или по умолчанию) B END завершить эту программу * --------------- дополнительная таблица трансляции (EBCDIC --> указатель таблицы INDEX) 256 байт----* CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 одинаковых наборов по 16 байт x'00' * представляет X'00 – x'BF' DC AL1(00, 01 ,00,00, 04 ,00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF' DC AL1(00,00,00,00, 03 ,00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF' DC AL1(00,00, 02 ,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF' DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF' * ассемблер можно использовать для автоматического расчета значений индекса и сделать значения более удобными для пользователя * (например, «01» можно заменить символическим выражением «PADD-CT1/4» в таблице CT1X выше) * измененный CT1 (теперь индекс основан на 0,1,2,3,4, а не на 0,4,8,12,16, чтобы разрешить все 256 вариаций) CT1 DC A(DEFAULT) индекс =00 НАЧАЛО таблицы управления (4-байтовые константы адреса) PADD DC A(ADD) =01 PSUB DC A(ВЫЧИТАНИЕ) =02 PMUL DC A(УМНОЖИТЬ) =03 PDIV DC A(ДЕЛИТЬ) =04 * остальная часть кода остается такой же, как во 2-м примереПример на языке C В этом примере на языке C используются две таблицы: первая (CT1) — это простая одномерная таблица линейного поиска , позволяющая получить индекс путем сопоставления входных данных (x), а вторая, связанная таблица (CT1p), представляет собой таблицу адресов меток для перехода.
static const char CT1 [] = { "A" , "S" , "M" , "D" }; /* разрешенные входные значения */ static const void * CT1p [] = { && Add , && Subtract , && Multiply , && Divide , && Default }; /* метки для перехода и по умолчанию*/ for ( int i = 0 ; i < sizeof ( CT1 ); i ++ ) /* цикл по значениям ASCII */ { if ( x == CT1 [ i ]) goto * CT1p [ i ]; } /* найдено --> подходящая метка */ goto * CT1p [ i + 1 ]; /* не найдено --> метка по умолчанию */ Это можно сделать более эффективным, если использовать таблицу размером 256 байт для прямого перевода необработанного значения ASCII (x) в плотное последовательное индексное значение для использования в прямом поиске адреса перехода из CT1p (т. е. « индексное отображение » с массивом шириной в байт). Затем он будет выполняться за постоянное время для всех возможных значений x (если бы CT1p содержал имена функций вместо меток, переход можно было бы заменить динамическим вызовом функции, исключив goto, подобный switch, но снизив производительность за счет дополнительных затрат на поддержание функций ).
static const void * CT1p [] = { && По умолчанию , && Сложить , && Вычесть , && Умножить , && Делить }; /* 256-байтовая таблица ниже содержит значения (1,2,3,4) в соответствующих позициях ASCII (A,S,M,D), все остальные установлены в 0x00 */ static const char CT1x [] = { '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\ x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' ,'\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x01' , '\x00' , '\x00' , '\x04' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\ x00 ' , '\x00' , '\x00' , '\x00' , '\x03' , '\x00' , '\x00' , '\x00' , '\x00' , '\ x00' , '\x00' , '\x02' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00', ' \ x00 ' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , ' \x00' , '\x00 ' , '\x00', '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00', '\x00', '\x00' , '\x00 ' , '\x00', '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' ,'\x00' , '\x00' , ' \x00' , '\x00' , '\x00', '\x00', '\x00' , ' \ x00 ' , '\x00 ' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , ' \x00' , '\x03' , '\x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00', '\x00' , '\x00' ,'\x00' , '\x00' , ' \x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00 ' , '\x00' , ' \x00 ' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' , '\x00' }; /* следующий код будет выполнен за постоянное время, независимо от значения входного символа (x) */ i = CT1x ( x ); /* извлечь правильный индекс подпрограммы из таблицы CT1x, используя его значение ASCII в качестве индекса изначально */ goto * CT1p [ i ]; /* перейти (перейти) к метке, соответствующей индексу (0=по умолчанию, 1=Добавить, 2=Вычесть,.) - см. CT1p */ Следующий пример ниже иллюстрирует, как можно достичь подобного эффекта в языках, которые не поддерживают определения указателей в структурах данных, но поддерживают индексированное ветвление к подпрограмме, содержащейся в массиве указателей подпрограмм ( начинающемся с 0 ). Таблица (CT2) используется для извлечения индекса (из 2-го столбца) в массив указателей (CT2P). Если массивы указателей не поддерживаются, можно использовать оператор SWITCH или эквивалент для изменения потока управления на одну из последовательности меток программы (например, case0, case1, case2, case3, case4), которые затем либо обрабатывают входные данные напрямую, либо выполняют вызов (с возвратом) соответствующей подпрограммы (default, Add, Subtract, Multiply или Divide,..) для работы с ними.
КТ2
Как и в примерах выше, можно очень эффективно преобразовать потенциальные входные значения ASCII (A, S, M, D или неизвестно) в индекс массива указателей без фактического использования поиска по таблице, но здесь это показано в виде таблицы для согласованности с первым примером.
Можно построить (т. е. настроить) многомерные таблицы управления, которые могут быть «более сложными», чем приведенные выше примеры, которые могут проверять несколько условий на нескольких входах или выполнять более одного «действия» на основе некоторых критериев соответствия. «Действие» может включать указатель на другую подчиненную таблицу управления. В простом примере ниже в качестве дополнительного столбца было включено неявное условие «ИЛИ» (для обработки ввода в нижнем регистре, однако в этом случае это можно было бы сделать просто с помощью дополнительной записи для каждого из символов нижнего регистра, указав тот же идентификатор подпрограммы, что и для символов верхнего регистра). Также включен дополнительный столбец для подсчета фактических событий времени выполнения для каждого ввода по мере их возникновения.
КТ3
Записи таблицы управления в этом случае гораздо больше похожи на условные операторы в процедурных языках , но, что особенно важно, в них отсутствуют фактические (зависимые от языка) условные операторы (т. е. инструкции) (общий код физически находится в интерпретаторе, который обрабатывает записи таблицы, а не в самой таблице, которая просто воплощает логику программы через свою структуру и значения).
В таблицах, подобных этим, где ряд похожих записей таблицы определяет всю логику, номер записи таблицы или указатель могут эффективно занять место счетчика программы в более обычных программах и могут быть сброшены в «действии», также указанном в записи таблицы. Пример ниже (CT4) показывает, как расширение предыдущей таблицы для включения «следующей» записи (и/или включения подпрограммы «изменить поток» ( jump )) может создать цикл (этот пример на самом деле не является самым эффективным способом построения такой таблицы управления, но, демонстрируя постепенную «эволюцию» из первых примеров выше, показывает, как дополнительные столбцы могут использоваться для изменения поведения.) Пятый столбец показывает, что с помощью одной записи таблицы можно инициировать более одного действия — в этом случае действие, которое должно быть выполнено после нормальной обработки каждой записи (значения «-» означают «отсутствие условий» или «отсутствие действия»).
Структурное программирование или код «Goto-less» (включающий эквивалент конструкций « DO WHILE » или « for loop ») также может быть реализовано с помощью соответствующим образом спроектированных и «отступных» структур управляющих таблиц.
CT4 (полная «программа» для чтения и обработки input1, повторяющаяся до тех пор, пока не встретится «E»)
В специализированной области телекоммуникационной тарификации (связанной с определением стоимости конкретного звонка) таблично-ориентированные методы тарификации иллюстрируют использование контрольных таблиц в приложениях, где правила могут часто меняться из-за рыночных сил. Таблицы, определяющие тарифы, могут быть изменены в короткие сроки непрограммистами во многих случаях. [4] [5]
Если алгоритмы не встроены в интерпретатор заранее (и, следовательно, требуют дополнительной интерпретации выражения, хранящегося в таблице, во время выполнения), это называется «рейтингом на основе правил», а не рейтингом, управляемым таблицей (и, следовательно, потребляет значительно больше накладных расходов).
Лист данных электронной таблицы можно рассматривать как двумерную контрольную таблицу, в которой непустые ячейки представляют данные для базовой программы электронной таблицы (интерпретатора). Ячейки, содержащие формулу, обычно имеют префикс в виде знака равенства и просто обозначают особый тип входных данных, который диктует обработку других ссылаемых ячеек – путем изменения потока управления в интерпретаторе. Именно экстернализация формул из базового интерпретатора четко идентифицирует как электронные таблицы, так и приведенный выше пример «рейтинга на основе правил» как легко идентифицируемые случаи использования контрольных таблиц непрограммистами.
Если бы можно было сказать, что метод управляющих таблиц принадлежит к какой-либо конкретной парадигме программирования , то ближайшей аналогией могло бы быть программирование на основе автоматов или «рефлексивное» (форма метапрограммирования – поскольку записи таблицы, можно сказать, «изменяют» поведение интерпретатора). Однако сам интерпретатор и подпрограммы могут быть запрограммированы с использованием любой из доступных парадигм или даже их смеси. Сама таблица может быть по сути набором значений « сырых данных », которые даже не нужно компилировать и которые можно считывать из внешнего источника (за исключением определенных, зависящих от платформы реализаций, использующих указатели памяти напрямую для большей эффективности).
Многомерная таблица управления имеет некоторые концептуальные сходства с байт-кодом, работающим на виртуальной машине , в том, что для выполнения фактического выполнения обычно требуется зависящая от платформы программа- "интерпретатор" (что в значительной степени условно определяется содержимым таблиц). Также есть некоторые концептуальные сходства с недавним Common Intermediate Language (CIL) в целях создания общего промежуточного "набора инструкций", который не зависит от платформы (но в отличие от CIL, не претендует на использование в качестве общего ресурса для других языков). P-код также можно считать похожей, но более ранней реализацией, берущей начало еще в 1966 году.
Когда многомерная таблица управления используется для определения потока программы, обычная «аппаратная» функция счетчика программ эффективно моделируется либо указателем на первую (или следующую) запись таблицы, либо индексом к ней. «Извлечение» инструкции включает декодирование данных в этой записи таблицы — без обязательного копирования всех или некоторых данных в записи в первую очередь. Языки программирования, которые могут использовать указатели , имеют двойное преимущество, заключающееся в меньших накладных расходах , как при доступе к содержимому, так и при перемещении счетчика для указания на следующую запись таблицы после выполнения. Вычисление следующего адреса «инструкции» (т. е. записи таблицы) может даже выполняться как необязательное дополнительное действие каждой отдельной записи таблицы, позволяя циклы и/или инструкции перехода на любом этапе.
Программа-интерпретатор может опционально сохранять счетчик программ (и другие соответствующие данные в зависимости от типа инструкции) на каждом этапе, чтобы записывать полную или частичную трассировку фактического потока программы для целей отладки , обнаружения горячих точек , анализа покрытия кода и анализа производительности (см. примеры CT3 и CT4 выше).
По желанию:-
Следующее относится в основном к их использованию в многомерных таблицах, а не к одномерным таблицам, обсуждавшимся ранее.
Многоканальное ветвление — важный метод программирования, который слишком часто заменяется неэффективной последовательностью проверок if. Недавно Питер Наур написал мне, что считает использование таблиц для управления потоком программы базовой идеей компьютерной науки, которая почти забыта; но он ожидает, что она созреет для повторного открытия в любой день. Это ключ к эффективности во всех лучших компиляторах, которые я изучал.
— Дональд Кнут , Структурное программирование с go to Statements
Есть другой способ взглянуть на программу, написанную на интерпретативном языке. Ее можно рассматривать как ряд вызовов подпрограмм, следующих один за другим. Такая программа фактически может быть расширена в длинную последовательность вызовов подпрограмм, и, наоборот, такая последовательность обычно может быть упакована в кодированную форму, которая легко интерпретируется. Преимуществом интерпретативных методов является компактность представления, независимость от машины и повышенная диагностическая способность. Интерпретатор часто может быть написан таким образом, что количество времени, потраченного на интерпретацию самого кода и переход к соответствующей подпрограмме, будет незначительным
— Дональд Кнут , Искусство программирования, том 1, 1997, стр. 202
Пространство, необходимое для представления программы, часто можно уменьшить за счет использования интерпретаторов, в которых общие последовательности операций представлены компактно. Типичным примером является использование конечного автомата для кодирования сложного протокола или лексического формата в небольшую таблицу
— Джон Бентли , Написание эффективных программ
Таблицы переходов могут быть особенно эффективны, если тесты диапазона можно опустить. Например, если контрольное значение является перечислимым типом (или символом), то оно может содержать только небольшой фиксированный диапазон значений, и тест диапазона избыточен, если таблица переходов достаточно велика, чтобы обработать все возможные значения.
— Дэвид А. СПУЛЕР, Генерация кода компилятора для операторов многоходового ветвления как задача статического поиска
Программы должны быть написаны для того, чтобы их могли читать люди, и только потом — чтобы их могли выполнять машины.
— «Структура и интерпретация компьютерных программ», предисловие к первому изданию, Abelson & Sussman
Покажите мне вашу схему и спрячьте ваши таблицы, и я буду продолжать оставаться в недоумении. Покажите мне ваши таблицы, и мне обычно не понадобится ваша схема; это будет очевидно.
— «Мифический человеко-месяц: очерки по программной инженерии», Фред Брукс
{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )