Управляющие таблицы — это таблицы , которые управляют потоком управления или играют важную роль в управлении программой. Не существует жестких правил относительно структуры или содержания управляющей таблицы — ее квалифицирующим атрибутом является ее способность каким-либо образом направлять поток управления посредством «выполнения» процессором или интерпретатором . Проектирование таких таблиц иногда называют проектированием на основе таблиц [1] [2] (хотя обычно это относится к автоматической генерации кода из внешних таблиц, а не к прямым таблицам времени выполнения). В некоторых случаях управляющие таблицы могут быть конкретными реализациями автоматного программирования на основе конечных автоматов . Если существует несколько иерархических уровней управляющей таблицы, они могут вести себя аналогично конечным автоматам UML [3].
В управляющие таблицы часто встроены эквиваленты условных выражений или ссылок на функции , что обычно подразумевается по относительному положению их столбца в списке ассоциаций . Управляющие таблицы уменьшают необходимость многократного программирования аналогичных структур или программных операторов. Двумерная природа большинства таблиц облегчает их просмотр и обновление, чем одномерный характер программного кода.
В некоторых случаях обслуживание содержимого управляющих таблиц может быть поручено непрограммистам. Например, если введенная пользователем поисковая фраза содержит определенную фразу, URL-адрес (веб-адрес) может быть назначен в таблице, которая контролирует, куда попадает пользователь, осуществляющий поиск. Если фраза содержит слово «юбка», то таблица может направить пользователя на страницу «www.shopping.example/catalogs/skirts», которая является страницей каталога товаров с юбками. (Пример URL-адреса на практике не работает). Вместо программистов такой таблицей могут управлять сотрудники отдела маркетинга.
Таблицы могут иметь несколько измерений фиксированной или переменной длины и обычно переносятся между компьютерными платформами , требуя только изменения интерпретатора, а не самого алгоритма , логика которого по существу воплощена в структуре и содержимом таблицы. Структура таблицы может быть аналогична ассоциативному массиву с несколькими отображениями , где значение данных (или комбинация значений данных) может быть сопоставлено с одной или несколькими функциями, которые необходимо выполнить.
Возможно, в своей простейшей реализации управляющая таблица иногда может быть одномерной таблицей для непосредственной трансляции значения необработанных данных в соответствующее смещение , индекс или указатель подпрограммы с использованием значения необработанных данных либо непосредственно в качестве индекса массива, либо путем выполнения заранее выполнить некоторые базовые арифметические действия с данными. Этого можно добиться за постоянное время (без линейного поиска или двоичного поиска с использованием типичной справочной таблицы в ассоциативном массиве ). В большинстве архитектур это можно выполнить с помощью двух или трех машинных инструкций — без каких-либо сравнений или циклов. Этот метод известен как « тривиальная хэш-функция » или, при использовании специально для таблиц ветвей, « двойная диспетчеризация ». Чтобы это было осуществимо, диапазон всех возможных значений данных должен быть небольшим (например, значение символа ASCII или EBCDIC , которое имеет диапазон шестнадцатеричных значений от «00» до «FF». Если фактический диапазон гарантированно будет меньше чем это, массив может быть усечен до размера менее 256 байт).
Таблица для перевода необработанных значений ASCII (A,D,M,S) в новый индекс подпрограммы (1,4,3,2) за постоянное время с использованием одномерного массива
(пробелы в диапазоне в этом примере показаны как «..», что означает «все шестнадцатеричные значения до следующей строки». Первые два столбца не являются частью массива)
В автоматном программировании и обработке псевдодиалоговых транзакций , если количество различных состояний программы невелико, можно использовать управляющую переменную «плотной последовательности», чтобы эффективно диктовать весь поток основного программного цикла.
Для двухбайтового значения необработанных данных потребуется минимальный размер таблицы 65 536 байт – для обработки всех возможностей ввода – при этом допускается всего 256 различных выходных значений. Однако этот метод прямого перевода обеспечивает чрезвычайно быструю проверку и преобразование в (относительный) указатель на подпрограмму, если эвристика вместе с достаточным объемом памяти быстрого доступа разрешает его использование.
Таблица ветвей — это одномерный «массив» непрерывных инструкций ветвления/перехода машинного кода , обеспечивающий многоходовой переход к метке программы при разветвлении непосредственно предшествующей и индексированной ветки. Иногда он генерируется оптимизирующим компилятором для выполнения оператора переключения – при условии, что входной диапазон небольшой и плотный, с небольшим количеством пробелов (как это было в предыдущем примере массива) [1].
IfХотя инструкции ветвления довольно компактны по сравнению с несколькими эквивалентными операторами, они все же несут некоторую избыточность, поскольку код операции ветвления и маска кода условия повторяются вместе со смещениями ветвления. Управляющие таблицы, содержащие только смещения меток программы, могут быть созданы для преодоления этой избыточности (по крайней мере, в языках ассемблера), но при этом требуют лишь незначительных затрат времени на выполнение по сравнению с обычной таблицей ветвей.
Чаще всего управляющую таблицу можно рассматривать как таблицу истинности или как исполняемую («двоичную») реализацию печатной таблицы решений (или дерева таблиц решений на нескольких уровнях). Они содержат (часто подразумеваемые) предложения вместе с одним или несколькими связанными с ними «действиями». Эти действия обычно выполняются общими или специально созданными подпрограммами , вызываемыми программой- интерпретатором . Интерпретатор в этом случае эффективно функционирует как виртуальная машина , которая «выполняет» записи таблицы управления и, таким образом, обеспечивает более высокий уровень абстракции , чем базовый код интерпретатора.
Управляющая таблица может быть построена аналогично оператору переключения , зависящему от языка , но с добавленной возможностью проверки комбинаций входных значений (с использованием логических условий И / ИЛИ ) и потенциального вызова нескольких подпрограмм (вместо одного набора значений). и метки программ «перейти к программе»). (Конструкция оператора переключения в любом случае может быть недоступна или иметь разные реализации на языках высокого уровня ( HLL ). Концепция управляющей таблицы, напротив, не имеет внутренних языковых зависимостей, но, тем не менее, может быть реализована по-разному в зависимости от доступных особенности определения данных выбранного языка программирования.)
Управляющая таблица, по сути, воплощает « суть » обычной программы, лишенную синтаксиса языка программирования и компонентов, зависящих от платформы (например, IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL) и ' сжато» до переменных (например, input1), значений (например, «A», «S», «M» и «D») и идентификаторов подпрограмм (например, «Сложить», «вычесть,..» или #1, # 2,..). Структура самой таблицы обычно подразумевает задействованные логические операции (по умолчанию), такие как «проверка на равенство», выполнение подпрограммы и «следующая операция» или следование последовательности по умолчанию (вместо того, чтобы они были явно указаны в операторах программы — по мере необходимости). в других парадигмах программирования ).
Многомерная управляющая таблица обычно, как минимум, содержит пары значение/действие и может дополнительно содержать операторы и информацию о типе , такую как расположение, размер и формат входных или выходных данных, преобразование данных (или другие действия во время выполнения). нюансы обработки) требуется до или после обработки (если это еще не предусмотрено в самой функции). Таблица может содержать или не содержать индексы , относительные или абсолютные указатели на общие или индивидуальные примитивы или подпрограммы , которые должны выполняться в зависимости от других значений в «строке».
Таблица, показанная ниже, применима только к «входу 1», поскольку в таблице не указан конкретный вход.
условия и действия, подразумеваемые структурой
(Это параллельное сочетание значения и действия имеет сходство с конструкциями в событийно-ориентированном программировании , а именно с «обнаружением событий» и «обработкой событий», но без (обязательно) асинхронной природы самого события)
Разнообразие значений, которые могут быть закодированы в управляющей таблице, во многом зависит от используемого компьютерного языка . Язык ассемблера предоставляет самый широкий диапазон типов данных , включая (для действий) возможность непосредственно исполняемого машинного кода . Обычно управляющая таблица содержит значения для каждого возможного соответствующего класса входных данных вместе с соответствующим указателем на подпрограмму действия. Некоторые языки утверждают, что не поддерживают указатели (напрямую), но, тем не менее, вместо этого могут поддерживать индекс , который можно использовать для представления «относительного номера подпрограммы» для выполнения условного выполнения, контролируемого значением в записи таблицы (например, для использования в оптимизированном SWITCH заявление – спроектировано с нулевыми пробелами (т.е. многоходовая ветвь )).
Комментарии, расположенные над каждым столбцом (или даже встроенная текстовая документация), могут сделать таблицу решений «читабельной» даже после «сжатия» (кодирования) до ее основных элементов (и при этом в целом соответствовать исходной спецификации программы, особенно если она распечатана). таблица решений, перечисляющая каждое уникальное действие, создается до начала кодирования). Записи таблицы также могут дополнительно содержать счетчики для сбора статистики времени выполнения для оптимизации в реальном времени или для последующей оптимизации.
Управляющие таблицы могут находиться в статическом хранилище, во вспомогательном хранилище , таком как плоский файл или в базе данных , или, альтернативно, могут быть частично или полностью построены динамически во время инициализации программы из параметров (которые сами могут находиться в таблице). Для оптимальной эффективности таблица должна находиться в памяти, когда интерпретатор начинает ее использовать.
Интерпретатор может быть написан на любом подходящем языке программирования, включая язык высокого уровня . Подходяще спроектированный универсальный интерпретатор вместе с хорошо выбранным набором общих подпрограмм (способных обрабатывать наиболее часто встречающиеся примитивы ) потребует дополнительного традиционного кодирования только для новых пользовательских подпрограмм (помимо указания самой управляющей таблицы). Интерпретатор, опционально, может применяться только к некоторым четко определенным разделам полной прикладной программы (например, к основному контуру управления ), а не к другим, «менее условным» разделам (таким как инициализация программы, завершение и т. д.).
Интерпретатор не обязательно должен быть чрезмерно сложным или создан программистом с глубокими знаниями автора компилятора, и его можно написать так же, как и любую другую прикладную программу, за исключением того, что он обычно разрабатывается с учетом эффективности. Его основная функция — «выполнять» записи таблицы как набор «инструкций». Нет необходимости в синтаксическом анализе записей управляющей таблицы, и поэтому они должны быть спроектированы, насколько это возможно, «готовыми к выполнению», требующими только «подключения» переменных из соответствующих столбцов в уже скомпилированный общий код таблицы. переводчик. Программные инструкции теоретически бесконечно расширяемы и представляют собой (возможно, произвольные) значения внутри таблицы, которые имеют смысл только для интерпретатора. Поток управления интерпретатора обычно представляет собой последовательную обработку каждой строки таблицы, но может быть изменен с помощью определенных действий в записях таблицы.
Таким образом, эти произвольные значения могут быть разработаны с учетом эффективности — путем выбора значений, которые можно использовать в качестве прямых индексов данных или указателей на функции . Для определенных платформ/ языков они могут быть специально разработаны для минимизации длины пути инструкций с использованием значений таблицы ветвей или даже, в некоторых случаях, например, в JIT- компиляторах, состоять из « фрагментов » непосредственно исполняемого машинного кода (или указателей на них).
Подпрограммы могут быть закодированы либо на том же языке, что и сам интерпретатор, либо на любом другом поддерживаемом программном языке (при условии, что существуют подходящие механизмы межъязыковой связи «Вызов»). Выбор языка интерпретатора и/или подпрограмм обычно зависит от того, насколько он должен быть переносимым на различные платформы . Может быть несколько версий интерпретатора для повышения переносимости управляющей таблицы. Указатель подчиненной управляющей таблицы может опционально заменять указатель подпрограммы в столбцах «действие», если интерпретатор поддерживает эту конструкцию, представляющую условный «переход» на более низкий логический уровень, имитируя традиционную структурированную структуру программы.
На первый взгляд может показаться, что использование управляющих таблиц существенно увеличивает накладные расходы программы , поскольку требует процесса интерпретатора перед выполнением операторов «родного» языка программирования. Однако это не всегда так. Отделяя (или «инкапсулируя») исполняемый код от логики, как показано в таблице, его можно легче настроить для наиболее эффективного выполнения своей функции. Наиболее очевидно это можно наблюдать в приложении для работы с электронными таблицами , где базовое программное обеспечение для работы с электронными таблицами прозрачно преобразует сложные логические «формулы» наиболее эффективным способом, каким только возможно, для отображения результатов.
Приведенные ниже примеры были выбраны частично для иллюстрации потенциального повышения производительности, которое может не только существенно компенсировать дополнительный уровень абстракции, но и улучшить – то, что в противном случае могло бы быть – менее эффективным, менее поддерживаемым и более длинным кодом. Хотя приведенные примеры относятся к ассемблеру «низкого уровня» и к языку C , можно видеть, что в обоих случаях требуется очень мало строк кода для реализации подхода с использованием таблицы управления, но при этом можно достичь очень значительного постоянного времени . повышение производительности, уменьшение повторяющегося исходного кода и повышение ясности по сравнению с многословными традиционными языковыми конструкциями программ. См. также цитаты Дональда Кнута , касающиеся таблиц и эффективности многопутевого ветвления в этой статье.
Следующие примеры являются произвольными (и для простоты основаны только на одном вводе), однако цель состоит в том, чтобы просто продемонстрировать, как можно реализовать поток управления с помощью таблиц вместо обычных программных операторов. Должно быть ясно, что этот метод можно легко расширить для работы с несколькими входными данными либо за счет увеличения количества столбцов, либо за счет использования нескольких записей таблицы (с необязательным оператором и/или). Аналогичным образом, используя (иерархические) «связанные» управляющие таблицы, можно осуществить структурное программирование (необязательно с использованием отступов, чтобы выделить подчиненные управляющие таблицы).
«CT1» — это пример управляющей таблицы, которая представляет собой простую таблицу поиска . Первый столбец представляет входное значение, подлежащее проверке (подразумеваемым «IF input1 = x»), и, если TRUE, соответствующий второй столбец («действие») содержит адрес подпрограммы, которую нужно выполнить путем вызова ( или перехода к – аналогично оператору 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) ПОПРОБУЙТЕ CLC INPUT1,0(R15) ********* Найдено значение в записи таблицы? BE ACTION * цикл * ДА, загрузить указатель регистра на подпрограмму из таблицы AR R15,R14 * * НЕТ, укажите следующую запись в CT1, добавив R14 (=4) BCT R0,TRY ********* Назад, пока счет не иссякнет, затем пройдите дальше. . действие по умолчанию... ни одно из значений в таблице не соответствует, сделайте что-нибудь еще LA R15,4(R15) указывает на запись по умолчанию (за концом таблицы) ДЕЙСТВИЕ L R15,0(R15) получить указатель на R15, откуда указывает R15. BALR R14,R15 Выполнение подпрограммы («ВЫЗОВ» и возврат) 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, но может . альтернативно быть встроенным кодом) . инструкции по добавлению БР Р14 возврат ВЫЧИТАНИЕ CSECT, подпрограмма № 2 . инструкция(и) по вычитанию БР Р14 возврат . и т. д..
улучшение производительности интерпретатора в приведенном выше примере
Улучшенный интерпретатор (в среднем до 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) ..x'E0' – X'EF' DC AL1(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 (ПО УМОЛЧАНИЮ) = 00 НАЧАЛО таблицы управления (4-байтовые адресные константы) PADD DC A(ADD) =04 PSUB DC A(ВЫЧИТАНИЕ) =08 PMUL DC A(MULTIPLY) =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) ..x'E0' – X'EF' DC AL1(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 (ПО УМОЛЧАНИЮ) = 00 НАЧАЛО таблицы управления (4-байтовые адресные константы) PADD DC A(ADD) =01 PSUB DC A(ВЫЧИТАНИЕ) =02 PMUL DC A(MULTIPLY) =03 PDIV DC A(ДЕЛИТЬ) =04 * остальной код остается таким же, как во втором примере
Пример языка C. В этом примере на C используются две таблицы: первая (CT1) представляет собой простую одномерную справочную таблицу с линейным поиском – для получения индекса путем сопоставления входных данных (x), а вторая, связанная таблица (CT1p), таблица адресов меток для перехода.
static const char CT1 [] = { "A" , "S" , "M" , "D" }; /* разрешенные входные значения */ static const void * CT1p [] = { && Add , && Subtract , && Multiply , && Divide , && Default }; /* метки для перехода & default*/ for ( int i = 0 ; i < sizeof ( CT1 ); i ++ ) /* цикл по значениям ASCII */ { if ( x == CT1 [ i ]) goto * CT1p [ я ]; } /* найдено --> соответствующая метка */ goto * CT1p [ i + 1 ]; /* не найден --> метка по умолчанию */ Это можно сделать более эффективным, если использовать таблицу размером 256 байт для преобразования необработанного значения ASCII (x) непосредственно в значение плотного последовательного индекса для использования при непосредственном обнаружении адреса ветки из CT1p (т. е. « отображение индекса » с помощью байтового значения индекса). множество). Затем он будет выполняться за постоянное время для всех возможных значений x (если бы CT1p содержал имена функций вместо меток, переход можно было бы заменить динамическим вызовом функции, устраняя переход, подобный переключению, но снижая производительность из-за дополнительных затрат). функции ведения домашнего хозяйства ).
static const void * CT1p [] = { && Default , && Add , && Subtract , && Multiply , && Divide }; /* таблица размером 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' , '\x03' , '\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' , '\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' }; /* следующий код будет выполняться за постоянное время, независимо от значения входного символа (x) */ i = CT1x ( x ); /* извлекаем правильный индекс подпрограммы из таблицы CT1x, используя ее значение ASCII в качестве индекса изначально */ goto * CT1p [ i ]; /* перейти (переключиться) на метку, соответствующую индексу (0=по умолчанию, 1=сложить, 2=вычесть,.) - см. CT1p */ Следующий пример ниже иллюстрирует, как аналогичный эффект может быть достигнут в языках, которые не поддерживают определения указателей в структурах данных, но поддерживают индексированное ветвление к подпрограмме, содержащейся в массиве указателей подпрограмм ( начиная с 0 ). Таблица (CT2) используется для извлечения индекса (из 2-го столбца) в массив указателей (CT2P). Если массивы указателей не поддерживаются, можно использовать оператор SWITCH или его эквивалент для изменения потока управления на одну из последовательностей программных меток (например: Case0, Case1, Case2, Case3, Case4), которые затем либо обрабатывают ввод напрямую, либо иначе выполните вызов (с возвратом) соответствующей подпрограммы (по умолчанию, Add, Subtract, Multiply или Divide,...), чтобы справиться с ней.
КТ2
Как и в приведенных выше примерах, можно очень эффективно преобразовать потенциальные входные значения ASCII (A,S,M,D или неизвестные) в индекс массива указателей без фактического использования поиска в таблице, но здесь это показано в виде таблицы для обеспечения согласованности с первый пример.
Могут быть созданы (т.е. настроены) многомерные управляющие таблицы, которые могут быть «более сложными», чем приведенные выше примеры, которые могут проверять наличие нескольких условий на нескольких входных данных или выполнять более одного «действия» на основе некоторых критериев соответствия. «Действие» может включать указатель на другую подчиненную управляющую таблицу. В приведенном ниже простом примере неявное условие «ИЛИ» включено в качестве дополнительного столбца (для обработки ввода в нижнем регистре, однако в данном случае это можно было бы также обработать, просто добавив дополнительную запись для каждого символа нижнего регистра, определяющего тот же идентификатор подпрограммы, что и символы верхнего регистра). Также включен дополнительный столбец для подсчета фактических событий времени выполнения для каждого входа по мере их возникновения.
КТ3
Записи управляющей таблицы в этом случае гораздо больше похожи на условные операторы в процедурных языках , но, что особенно важно, без присутствия реальных (зависящих от языка) условных операторов (то есть инструкций) (обобщенный код физически находится в интерпретаторе, который обрабатывает записи таблицы, а не в интерпретаторе). в самой таблице, которая просто воплощает логику программы через свою структуру и значения).
В таких таблицах, где ряд одинаковых записей таблицы определяет всю логику, номер записи таблицы или указатель могут эффективно заменять программный счетчик в более традиционных программах и могут быть сброшены с помощью «действия», также указанного в запись таблицы. В приведенном ниже примере (CT4) показано, как расширение предыдущей таблицы за счет включения «следующей» записи (и/или включения подпрограммы «изменения потока» ( прыжка )) может создать цикл (на самом деле этот пример не является самым эффективным способом построить такую таблицу управления, но, демонстрируя постепенную «эволюцию» из первых приведенных выше примеров, показывает, как можно использовать дополнительные столбцы для изменения поведения.) Пятый столбец демонстрирует, что с помощью одной записи таблицы можно инициировать более одного действия – в этом случае действие, которое должно быть выполнено после нормальной обработки каждой записи (значения «-» означают «нет условий» или «нет действия»).
Структурированное программирование или код «без перехода» (включающий эквивалент конструкций « DO WHILE » или « цикл for ») также может быть реализовано с помощью соответствующим образом спроектированных и «отступных» структур управляющих таблиц.
CT4 (полная «программа» для чтения ввода 1 и обработки, повторяющаяся до тех пор, пока не встретится буква «E»)
В специальной области оценки телекоммуникаций (связанной с определением стоимости конкретного звонка) методы оценки на основе таблиц иллюстрируют использование контрольных таблиц в приложениях, где правила могут часто меняться из-за рыночных сил. Во многих случаях таблицы, определяющие расходы, могут быть изменены в кратчайшие сроки непрограммистами. [4] [5]
Если алгоритмы не встроены заранее в интерпретатор (и, следовательно, требуют дополнительной интерпретации выражения, содержащегося в таблице, во время выполнения), это называется «рейтингом на основе правил», а не рейтингом на основе таблицы (и, следовательно, требует значительно больше накладных расходов). ).
Таблицу данных электронной таблицы можно рассматривать как двумерную управляющую таблицу, в которой непустые ячейки представляют данные для базовой программы работы с электронными таблицами (интерпретатора). Ячейки, содержащие формулу, обычно имеют префикс знака равенства и просто обозначают особый тип ввода данных, который определяет обработку других ячеек, на которые имеются ссылки, — путем изменения потока управления в интерпретаторе. Именно экстернализация формул из базового интерпретатора четко идентифицирует как электронные таблицы, так и приведенный выше пример «рейтинга на основе правил» как легко идентифицируемые случаи использования управляющих таблиц непрограммистами.
Если можно сказать, что техника управляющих таблиц принадлежит какой-либо конкретной парадигме программирования , то ближайшей аналогией может быть программирование на основе автоматов или «рефлексивное» программирование (форма метапрограммирования – поскольку можно сказать, что записи таблицы «модифицируют» поведение устный переводчик). Однако сам интерпретатор и подпрограммы могут быть запрограммированы с использованием любой из доступных парадигм или даже их смеси. Сама таблица по существу может представлять собой набор значений « необработанных данных », которые даже не нужно компилировать и которые можно считывать из внешнего источника (за исключением конкретных, зависящих от платформы реализаций, использующих указатели памяти напрямую для большей эффективности).
Многомерная управляющая таблица имеет некоторое концептуальное сходство с байт-кодом , работающим на виртуальной машине , в том смысле, что для фактического выполнения обычно требуется зависящая от платформы программа -интерпретатор (которая в значительной степени условно определяется содержимым таблицы). Есть также некоторые концептуальные сходства с недавним Common Intermediate Language (CIL) с целью создания общего промежуточного «набора инструкций», независимого от платформы (но, в отличие от CIL, нет претензий на использование в качестве общего ресурса для других языков). . P-код также можно считать похожей, но более ранней реализацией, возникшей еще в 1966 году.
Когда для определения хода выполнения программы используется многомерная управляющая таблица, обычная «аппаратная» функция счетчика программ эффективно моделируется либо с помощью указателя на первую (или следующую) запись таблицы, либо с помощью индекса к ней. «Извлечение» инструкции включает декодирование данных в этой записи таблицы – без обязательного предварительного копирования всех или некоторых данных внутри записи. Языки программирования, которые могут использовать указатели, имеют двойное преимущество: требуется меньше накладных расходов как при доступе к содержимому, так и при перемещении счетчика так, чтобы он указывал на следующую запись таблицы после выполнения. Вычисление адреса следующей «инструкции» (т.е. записи таблицы) может даже выполняться как необязательное дополнительное действие для каждой отдельной записи таблицы, позволяющее выполнять циклы и/или инструкции перехода на любом этапе.
Программа-интерпретатор может дополнительно сохранять счетчик программ (и другие важные сведения в зависимости от типа инструкции) на каждом этапе, чтобы записывать полную или частичную трассировку фактического потока программы в целях отладки , обнаружения горячих точек , анализа покрытия кода и анализа производительности (см. примеры CT3 и CT4 выше).
Необязательно:-
Следующее в основном относится к их использованию в многомерных таблицах, а не к одномерным таблицам, обсуждавшимся ранее.
Многоходовое ветвление — важный метод программирования, который слишком часто заменяется неэффективной последовательностью проверок if. Питер Наур недавно написал мне, что считает использование таблиц для управления ходом выполнения программы основной идеей информатики, которая почти забыта; но он ожидает, что со дня на день оно созреет для повторного открытия. Это ключ к эффективности всех лучших компиляторов, которые я изучал.
— Дональд Кнут , Структурное программирование с переходом к операторам.
Есть еще один способ взглянуть на программу, написанную на интерпретативном языке. Его можно рассматривать как серию вызовов подпрограмм, идущих один за другим. Такая программа фактически может быть расширена до длинной последовательности вызовов подпрограмм, и, наоборот, такая последовательность обычно может быть упакована в закодированную форму, которая легко интерпретируется. Преимуществом методов интерпретации являются компактность представления, машинная независимость и расширенные диагностические возможности. Интерпретатор часто может быть написан так, что время, затрачиваемое на интерпретацию самого кода и переход к соответствующей процедуре, будет незначительным.
- Дональд Кнут , Искусство компьютерного программирования , том 1, 1997, стр. 202.
Пространство, необходимое для представления программы, часто можно уменьшить за счет использования интерпретаторов, в которых общие последовательности операций представляются компактно. Типичным примером является использование конечного автомата для кодирования сложного протокола или лексического формата в небольшую таблицу.
— Джон Бентли , «Написание эффективных программ»
Таблицы переходов могут быть особенно эффективны, если можно опустить проверку диапазона. Например, если управляющее значение представляет собой перечислимый тип (или символ), то оно может содержать только небольшой фиксированный диапазон значений, и проверка диапазона является избыточной, если таблица переходов достаточно велика, чтобы обрабатывать все возможные значения.
— Дэвид А. SPULER, Генерация кода компилятора для операторов многопутевого ветвления как задача статического поиска
Программы должны быть написаны для того, чтобы их могли читать люди, и лишь вскользь для того, чтобы их могли выполнять машины.
- «Структура и интерпретация компьютерных программ», предисловие к первому изданию, Abelson & Sussman.
Покажите мне свою блок-схему и спрячьте свои таблицы, и я буду продолжать оставаться в недоумении. Покажите мне свои таблицы, и ваша блок-схема обычно мне не понадобится; это будет очевидно.
- «Мифический человеко-месяц: очерки по разработке программного обеспечения», Фред Брукс
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )