Войти
Эта простая управляющая таблица выполняет выполнение программы в соответствии со значением единственной входной переменной. Каждая запись содержит возможное входное значение, которое необходимо проверить на равенство (подразумевается), и соответствующая подпрограмма для выполнения в столбце действия. Имя подпрограммы может быть заменено относительным номером подпрограммы, если указатели не поддерживаются Управляющие таблицы - это управления таблицы, которые управляют потоком или играют основную роль в программном управлении. Способность его каким-либо образом направлять поток управления посредством «выполнения» или интерпретатором. Дизайн таких таблиц иногда структурой, управляемой таблицами . В некоторых случаях управляющие таблицы могут быть конкретными реализациями конечного автомата на основе программирования на основе автоматов. Если существует несколько иерархических уровней управляющей таблицы, они могут вести себя аналогично конечным автоматом UML
Управляющие таблицы часто имеют эквивалент условных выражений или функций ссылок, встроенных в них обычно подразумевается их относительным положительным столбцом в списке ассоциаций. Таблицы управления сокращают потребность в многократном программировании подобных структур структур или программных операторов. Двумерный характерных таблиц облегчает их просмотр и обновление, чем одномерный характер программного кода. В некоторых случаях для ведения управляющих таблиц могут быть назначены непрограммисты.
Таблицы могут иметь несколько размеров, фиксированной или Параметры прочности и обычно переносимые между компьютерными платформами, требуя только изменения в интерпретаторе, а не в алгоритме Сама по себе - логика, по суть, воплощена в структуре и содержании таблицы. Структура таблицы может быть подобна ассоциативному массиву multimap , где значение данных (или комбинация значений данных) может быть отображено на одну или несколько выполняемых функций.
Возможно, в простейшей реализации управляющая таблица иногда может быть одной таблицей для прямого преобразования значений необработанных данных в соответствующей подпрограмму смещение, index или указатель с использованием значений необработанных данных либо непосредственно в качестве индекса для массива, либо путем выполнения некоторых основных арифметических действий с данными заранее. Это может быть достигнуто за постоянное время (без линейного поиска или двойного поиска с использованием типичной таблицы поиска на ассоциативной массив ). В большинстве архитектур это может быть выполнено двумя или тремя машинными инструкциями - без каких-либо сравнений или циклов. Этот метод как известен «тривиальная хеш-функция » или, когда используется специально для таблиц переходов, «двойная отправка ». Чтобы это было осуществимо, диапазон всех значений данных должен быть небольшим (например, символьное значение ASCII или EBCDIC, которое имеет диапазон шестнадцатеричное '00 '-' FF '. Если фактический диапазон гарантированно меньше, может быть усечен до размера менее 256 байт).
Таблица для преобразования необработанных значений ASCII (A, D, M, S) в новый индекс подпрограммы (1,4,3,2) в постоянное время с использованием одномерного массива
(пробелы в в этом примере показаны как "..", что означает "все шестнадцатеричные значения до следующей строки". Первые два столбца не являются массивом)
| ASCII | Hex | Массив |
|---|---|---|
| null | 00 | 00 |
| .. | .. | 00 |
| @ | 40 | 00 |
| A | 41 | 01 |
| .. | .. | 00 |
| D | 44 | 04 |
| .. | .. | 00 |
| M | 4D | 03 |
| .. | .. | 00 |
| S | 53 | 02 |
В автоматном программировании и обработка псевдоконверсионных транзакций, если количество различных программных состояний невелико, можно использовать управляющую переменную «плотной руководящей», чтобы эффективно диктовать весь поток основного цикла.
Для двухбайтовых значений необработанных данных требуется всех размеров таблицы 65 536 байт - для обработки возможностей ввода - при этом разрешается только 256 различных выходных значений. Однако этот метод прямого преобразования обеспечивает максимально быструю Проверка и преобразование в (относительный) указатель подпрограммы, если эвристика вместе с достаточным быстрым доступом к памяти разрешает его использование.
A Таблица переходов - это одномерный «массив» непрерывных машинных кодов инструкций перехода / перехода для выполнения многоходовой ветки Программа при переходе на предшествующую и проиндексированную ветвь. Иногда он генерируется оптимизирующим компилятором для выполнения оператора переключения - при условии, что входной диапазон небольшой и плотный, с небольшими промежутками (как создано в предыдущем пространстве) [2].
Несмотря на то, что они довольно компактны - по своим мобильным операторам Если- инструкции ветления по-прежнему имеют некоторую избыточность, поскольку код операции ветвления и маска условия кода повторяются вместе с ущерба ветвей. Таблицы управления, требующие лишь незначительного времени выполнения накладных расходов по сравнению с обычными таблицами, должны быть построены для преодоления этой избыточности (по крайней мере, в языках ассемблера). переходов.
Обычно контрольную таблицу можно рассматривать как таблицу истинности или как исполняемую («двоичную») воспроизведенного таблицу решений (или дерево таблиц решений на нескольких уровнях). Они включают (подразумеваются) предложения вместе с одним или двумя связанными «действиями». Эти действия обычно выполняются универсальными или специально созданными подпрограммами , которые запускаются программой «интерпретатор ». Интерпретатор в этом случае функционирует как виртуальная машина, которая «выполняет» записи таблицы управления и таким образом, обеспечивает более высокий уровень абстракции , чем базовый код интерпретатора.
Управляющая таблица может быть построена по аналогии с зависимым от языка оператором переключения, но с добавлением тестирования комбинаций входных значений (с использованием логического стиля И /OR условия) и новое вызывая несколько подпрограмм (вместо одного набора значений и меток программы «переход к»). (Конструкция оператора переключателя в любом случае может быть недоступна или может иметь разные реализации на языках высокого уровня (HLL ). Для сравнения, концепция управляющей таблицы не имеет внутренних языковых зависимостей, но, тем не менее, может быть реализованы по-разному в зависимости от доступных функций определения выбранного языка программирования.)
Управляющая таблица по существу воплощает «сущность » обычной программы, лишенный синтаксиса языка программирования и компонентов, зависящих от платформы (например, IF / THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL) и 'сжатые' к его переменным (например, input1), значениям (например, 'A ',' S ',' M 'и' D ') и указанные подпрограммы (например,' Добавить ',' вычесть,.. 'или # 1, # 2,..). Структура самой подразумевает задействованные (по умолчанию) логические операции, такие как «проверка на равенство», выполнение подпрограммы и «следующая операция» или следование следования по умолчанию (вместо того, чтобы они явно указывались в операх программы - по мере необходимости в других парадигмах программирования ).
Многоканальная управляющая таблица обычно, как минимум, содержит значение пары / действие и может содержать операторы и тип информацию, как такую местоположение, размер и формат ввода или выходных данных, требуется ли преобразование данных (или другие нюансы обработки времени выполнения ) до или после обработки (если это еще не предусмотрено в самой функции). Таблица может или содержать не содержать индексы или относительные или абсолютные указатели на общие или настроенные примитивы или подпрограммы, которые должны быть в зависимости от других значений в «строке».
Приведенная ниже таблица применима только к 'input1', в этой таблице не указан конкретный вход.
условия и действия, подразумеваемые структурой
| (подразумеваемая) IF = | (подразумеваемая) выполнение |
| значение | действие |
| value | действие |
( Это параллельное соединение значений и действий имеет сходство с конструкциями в Программирование, управляемое событие, а именно «обнаружение событий» и «обработка событий», но без (обязательно) асинхронного характер события)
Разнообразие значений, которые можно закодировать в таблице управления, в степени зависит от используемого компьютерного языка. Язык ассемблера предоставляет самые широкие возможности для типов данных, включая (для действий) возможность прямого исполняемого машинного кода. Обычно управляющая таблица будет содержать значения для каждого сообщения назначенного списка сообщений вместе с указателем на подпрограмму действия. Некоторые языки заявляют, что не могут быть вместо указатели (напрямую), но, тем не менее, поддерживать этот индекс , который может выступать за представление «относительного номера подпрограммы» для выполнения условного выполнения, положения в записи таблицы (например, для использования в оптимизированном операторе SWITCH - разработанном с нулевыми пробелами (т. е. многосторонняя ветвь )).
Комментарии, расположенные над каждым столбцом (или даже встроенная текстовая документация), могут сделать таблицу решений `` удобочитаемой '' (кодирования) до ее основных элементов (и по-прежнему в целом) соответствует исходной программе спецификация - особенно если печатная таблица решений, перечисляющая каждое уникальное действие, создается до начала кодирования). Записи в таблице также могут содержать счетчики для сбора времени выполнения для «оперативной» или более поздней оптимизации
Управляющие таблицы могут находиться в статическом хранилище, на вспомогательной памяти, такой как плоский файл или в базе данных, или альтернативно, может быть частично или полностью построено динамически при инициализации программы время из параметров (сами могут находиться в таблице). Для оптимальной эффективности таблица должна быть резидентной в памяти, когда интерпретатор начинает ее использовать.
Интерпретатор может быть написан на любом подходящем языке программирования, включая язык высокого уровня. Подходящим образом универсальный интерпретатор вместе с хорошо подобранным набором универсальных подпрограмм (способ обрабатывать наиболее часто встречающиеся примитивы ) потребует дополнительного обычного кодирования только для новых пользовательских подпрограмм.. Интерпретатор, необязательно, может использовать только к определенным разделам полной прикладной программы (например, основной цикл управления ), а не к другим, менее условным, разделам (таким как инициализация программы, завершение и так далее).
Интерпретатор не должен быть чрезмерно сложным или создаваться программистами с продвинутыми знаниями в области записи компилятора, и его можно написать так же, как любую другую прикладную программу, за исключением того, что он обычно разрабатывается с эффективностью в разум. Его основная функция - «выполнять» записи таблицы как набор «инструкций». Нет необходимости в необходимости синтаксического анализа таблиц управления, и поэтому они должны быть спроектированы, насколько это возможно, «готовыми к выполнению», требуя только «вставки» из соответствующих столбцов в уже скомпилированный общий код переводчик. Программные инструкции теоретически являются расширяемыми бесконечно и составляют (возможно, произвольные) значения в таблице, которые имеют смысл только для интерпретатора. Поток управления интерпретатора обычно осуществляется последовательной обработки каждой строки таблицы, но может быть изменен посредством определенных действий в основных таблицах.
Эти произвольные значения, таким образом, могут быть разработаны с учетом эффективности - выбора значений, которые могут быть указаны в качестве прямых индексов данных или указателей на функции. Для платформ / языка они могут быть специально разработаны для минимизации длины пути инструкций с использованием значений таблицы переходов или даже в некоторых случаях, например, в Компиляторы JIT состоят из собственного исполняемого машинного кода «сниппетов » (или указателей на них).
Подпрограммы могут быть закодированы либо на том же языке, что и сам интерпретатор, на любом другом языке, поддерживаемом программном языке (при условии, что существуют подходящие механизмы межъязыковой связи «Вызов»). Выбор языка для интерпретатора и / или подпрограмм обычно зависит от того, насколько он должен быть переносимым на различные платформы. Может быть несколько версий интерпретатора для улучшения переносимости управляющей таблицы. Указатель подчиненной управляющей таблицы может необязательно заменить указатель подпрограммы в столбцах «действие», если интерпретатор поддерживает эту конструкцию, представляя условное «падение» на более низкий уровень, имитируя стандартную структурированной программы .
На первый взгляд, использование управляющих таблиц может значительно увеличить накладные расходы программы, требуя, как это происходит, процесса интерпретатора перед выполнением операторов «родного» языка программирования. Однако это не всегда так. Отделяя (или «инкапсулируя») выполняет кодирование от логики, как это выражено в таблице, можно более легко нацелить его на выполнение своей функции наиболее эффективно. Это может быть наиболее в приложении электронных таблиц - где лежащее в программном обеспечении электронные таблицы прозрачно преобразует логические схемы «формулы» эффективным способом.
Приведенные ниже примеры были отчасти выбраны для потенциального увеличения производительности, которое может не только усилить дополнительный уровень абстракции, но также улучшить - что в случае угрозы бы быть менее эффективным, менее обслуживаемым и более длинным кодом. Хотя приведенные примеры относятся к «низкоуровневому» ассемблеру и для языка C, в обоих случаях можно увидеть, что для реализации требуется очень мало строк кода. подход с использованием таблицы управления и, тем не менее, может достигать очень значительных улучшений производительности с постоянным временем, сокращать повторяющееся исходное кодирование и способствовать ясности по сравнению с подробными традиционными конструкциями языка программ. См. Также цитаты Дональда Кнута, касающиеся таблиц и эффективности многостороннего ветвления в этой статье.
Следующие ниже примеры являются произвольными (и для простоты основаны только на одном вводе), однако цель состоит в том, чтобы просто продемонстрировать, как поток управления может может осуществляться за счет использования таблиц вместо обычных программных операторов. Должно быть ясно, что этот метод можно легко расширить для работы с несколькими входами, либо увеличив количество столбцов, либо используя несколько записей таблицы (с дополнительным оператором и / или). Точно так же, используя (иерархические) «связанные» управляющие таблицы, можно выполнить структурированное программирование (возможно, используя отступы, чтобы помочь выделить подчиненные управляющие таблицы).
«CT1» - это пример управляющей таблицы, которая является простой таблицей поиска. Первый столбец представляет входное значение для тестирования (подразумевается 'IF input1 = x') и, если TRUE, соответствующий 2-й столбец ('action') содержит адрес подпрограммы для выполнения с помощью вызова (или перейти от к - аналогично оператору SWITCH ). По сути, это многосторонняя ветвь с возвратом (форма «динамической отправки »). Последняя запись - это случай по умолчанию, когда совпадений не найдено.
CT1
| вход 1 | указатель |
|---|---|
| A | ->сложить |
| S | ->вычесть |
| M | ->умножить |
| D | ->разделить |
| ? | ->по умолчанию |
Для языков программирования, которые поддерживают указатели в структурах данных наряду с другими значениями данных, указанная выше таблица (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 * * NO, указать на следующий запись в CT1 путем добавления R14 (= 4) BCT R0, TRY ********* Назад, пока счетчик не будет исчерпан, затем пропустить. действие по умолчан ию... ни одно из значений в таблице не соответствует, сделайте что-нибудь еще LA R15, 4 (R15) п oint к записи по умолчанию (за пределами конца таблицы) ACTION L R15,0 (R15) получить указатель на R15, откуда R15 указывает BALR R14, R15 Выполнить подпрограмму («CALL» и возврат) B END go завершить эту программу * - ----------------- таблица управления ------------------------------- ---------- * * | этот столбец допустимых значений EBCDIC или ASCII проверяется '=' на переменную 'input1' * | | этот столбец представляет собой 3-байтовый адрес соответствующей подпрограммы * vv CT1 DC C'A ', AL3 (ADD) START of Control Table (длина записи 4 байта) DC C'S', AL3 (SUBTRACT) DC C'M ', AL3 (MULTIPLY) DC C'D', AL3 (DIVIDE) N EQU (* -CT1) / 4 количество допустимых записей в таблице (общая длина / длина записи) DC C '?', AL3 (DEFAULT) запись по умолчанию - используется при перетаскивании для перехвата всех входных переменных INPUT1 DS C в этой переменной * ------------------ подпрограммы -------- ---------------------------------- * Подпрограмма ADD CSECT №1 (здесь показана как отдельный CSECT, но может. альтернативно быть встроенным кодом). инструкция (и) для добавления BR R14 возвращает подпрограмму SUBTRACT CSECT # 2. инструкция (и) на вычитание возврата BR R14. и т. д.
повышение производительности интерпретатора в приведенном выше примере
с помощью длина пути '5' с нулевыми сравнениями, если сначала используется 256-байтовая таблица преобразования для создания прямого индекса CT1 из необработанных данных EBCDIC. Если n = 6, это было бы эквивалентно всего 3 последовательным инструкциям сравнения и перехода. Однако где n <=64, on average it would need approximately 13 times less instructions than using multiple compares. Where n=1 to 256, on average it would use approximately 42 times less instructions - since, in this case, one additional instruction would be required (to multiply the index by 4).Улучшенный интерпретатор (до в 26 раз меньше выполняемых инструкций, чем в среднем в приведенном выше примере, где n = от 1 до 64 и до 13 раз меньше, чем было бы необходимо при использовании множественные сравнения).
Для обработки 64 различных входных значений требуется примерно 85 строк исходного кода (или меньше) (в основном записи однострочной таблицы), тогда как для нескольких операций сравнения и перехода потребуется около 128 строк (размер двоичный также почти вдвое - несмотря на дополнительную 256-байтовую таблицу, необходимую для извлечения 2-го индекса).
* ------------------ переводчик ------------------------ -------------------- * SR R14, R14 ********* Установить R14 = 0 CALC IC R14, INPUT1 * calc * поместить байт EBCDIC в Порядковые биты (24–31) R14 IC R14, CT1X (R14) * * используйте значение EBCDIC в качестве индекса в таблице CT1X, чтобы получить новый индекс FOUND 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' * t ассемблер можно использовать для автоматического вычисления значений индекса и сделать значения более удобными для пользователя * (например, '04' можно заменить символьным выражением 'PADD-CT1' в таблице CT1X выше) * измененный CT1 (добавлено действие по умолчанию, когда индекс = 00, одномерный, полный 31-битный адрес) CT1 DC A (ПО УМОЛЧАНИЮ) index = 00 ПУСК таблицы управления (4-байтовые адресные константы) PADD DC A (ADD) = 04 PSUB DC A (SUBTRACT) = 08 PMUL DC A (MULTIPLY) = 12 PDIV DC A (DIVIDE) = 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 Выполнить подпрограмму («ВЫЗОВ» и возврат или по умолчанию) 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 (DEFAULT) index = 00 START of Control Table (4-байтовые адресные константы) PADD DC A (ADD) = 01 PSUB DC A (SUBTRACT) = 02 PMUL DC A ( MULTIPLY) = 03 PDIV DC A (DIVIDE) = 04 * остальная часть кода остается такой же, как во втором примере
язык C пример В этом примере на C используются две таблицы, первая (CT1) - это простой линейный поиск одномерная таблица поиска - для получения индекса путем сопоставления ввода (x), а вторая, связанная таблица (CT1p), представляет собой таблицу адресов ярлыков, к которым нужно перейти.
static const char CT1 = {"A", "S", "M", "D"}; / * допустимые входные значения * / static const void * CT1p = {Сложение, Вычитание, Умножение, Деление, По умолчанию}; / * метки для перехода и по умолчанию * / for (int i = 0; i < sizeof(CT1); i++) /* loop thru ASCII values */ {if (x==CT1[i]) goto *CT1p[i]; } /* found -->соответствующая метка * / goto * CT1p [i + 1]; / * не найдены ->метка по умолчанию * /Это может быть становится более эффективным, если 256-байтовая таблица используется для преобразования необработанного значения ASCII (x) непосредственно в плотное последовательное значение индекса для использования при непосредственном обнаружении адреса ветвления от CT1p (например, «отображение индекса » с байтовый массив). Затем он будет выполняться в с постоянным временем для всех возможных значений x (если CT1p содержал имена функций вместо меток, переход можно было бы заменить вызовом динамической функции, исключив аналогично переключателю goto, но снижает производительность за счет дополнительных затрат на функцию housekeeping ).
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 ',' \ x 00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ 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 ',' \ 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 ',' \ x 00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ x00 ',' \ 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]; / * goto (переключиться на) метку, соответствующую индексу (0 = по умолчанию, 1 = сложение, 2 = вычитание,.) - см. CT1p * /Следующий пример ниже показывает, как подобный эффект может быть достигнут на языках. которые не поддерживают определения указателей в структурах данных, но действительно поддерживают индексированное ветвление к подпрограмме - содержащееся в (основанном на 0 ) массиве указателей подпрограмм. Таблица (CT2) используется для извлечения индекса (из 2-го столбца) в массив указателей (CT2P). Если массивы указателей не поддерживаются, можно использовать оператор SWITCH или его эквивалент для изменения потока управления на одну из последовательностей программных меток (например: case0, case1, case2, case3, case4), которые затем либо обрабатывают ввод напрямую, либо иначе выполните вызов (с возвратом) соответствующей подпрограммы (по умолчанию, сложение, вычитание, умножение или деление,..), чтобы справиться с этим.
CT2
| input 1 | subr # |
|---|---|
| A | 1 |
| S | 2 |
| M | 3 |
| D | 4 |
| ? | 0 |
Как и в примерах выше, можно очень эффективно преобразовать потенциальные входные значения ASCII (A, S, M, D или неизвестные) в индекс массива указателей без фактического использования поиска по таблице, но показан здесь в виде таблицы для согласованности с первым примером.
Могут быть построены (т. Е. Настроены) многомерные управляющие таблицы, которые могут быть «более сложными», чем приведенные выше примеры, которые могут проверять несколько условий на нескольких входах или выполнять более одного «действия» на основе некоторых критериев соответствия. «Действие» может включать указатель на другую подчиненную управляющую таблицу. В приведенном ниже простом примере есть неявное условие «ИЛИ», включенное в качестве дополнительного столбца (для обработки ввода в нижнем регистре, однако в этом случае это также можно было бы обработать, просто добавив дополнительную запись для каждого из символов нижнего регистра, определяющих same subroutine identifier as the upper case characters). An extra column to count the actual run-time events for each input as they occur is also included.
CT3
| input 1 | alternate | subr # | count |
|---|---|---|---|
| A | a | 1 | 0 |
| S | s | 2 | 0 |
| M | m | 3 | 0 |
| D | d | 4 | 0 |
| ? | ? | 0 | 0 |
The control table entries are then much more similar to conditional statements in procedural languages but, crucially, without the actual (language dependent) conditional statements (i.e. instructions) being present (the generic code is physically in the interpreter that processes the table entries, not в самой таблице, которая просто воплощает логику программы через ее структуру и значения).
В таких таблицах, где последовательность одинаковых записей таблицы определяет всю логику, номер записи таблицы или указатель может эффективно заменять программный счетчик в более традиционных программах и может быть сброшен с помощью «действия», также указанного в записи таблицы. В приведенном ниже примере (CT4) показано, как расширение предыдущей таблицы для включения «следующей» записи (и / или включения подпрограммы «изменить поток» (jump )) может создать цикл (Этот пример на самом деле не самый эффективный способ создания такой контрольной таблицы, но, демонстрируя постепенную «эволюцию» из первых примеров выше, показывает, как можно использовать дополнительные столбцы для изменения поведения.) Пятый столбец демонстрирует, что больше чем одно действие может быть инициировано с помощью одной записи таблицы - в этом случае действие, которое должно быть выполнено после нормальной обработки каждой записи (значения «-» означают «нет условий» или «нет действий»).
Структурированное программирование или код без перехода (включая эквивалент конструкций 'DO WHILE ' или 'for loop '), также могут быть приспособлены к соответствующим образом спроектированным структурам управляющих таблиц с «отступами».
CT4 (полная 'программа' для чтения input1 и обработки, повторяется до тех пор, пока не встретится 'E')
| input 1 | alternate | subr # | count | jump |
|---|---|---|---|---|
| - | - | 5 | 0 | - |
| E | e | 7 | 0 | - |
| A | a | 1 | 0 | - |
| S | s | 2 | 0 | - |
| M | m | 3 | 0 | - |
| D | d | 4 | 0 | - |
| ? | ? | 0 | 0 | - |
| - | - | 6 | 0 | 1 |
В специальной области рейтинг телекоммуникаций (связанный с определением стоимости конкретного вызова), методы рейтинга на основе таблиц иллюстрируют использование контрольных таблиц в приложениях, где правила могут часто меняться из-за рыночных сил. Таблицы, определяющие стоимость, во многих случаях могут быть изменены в короткие сроки непрограммистами.
Если алгоритмы не встроены в интерпретатор заранее (и, следовательно, требуют дополнительной интерпретации во время выполнения выражения, содержащегося в таблица), он известен как «рейтинг на основе правил», а не рейтинг на основе таблицы (и, следовательно, требует значительно больше накладных расходов).
A Электронная таблица лист данных можно рассматривать как двумерную контрольную таблицу, в которой непустые ячейки представляют данные для базовой программы электронных таблиц (интерпретатора). Ячейки, содержащие формулу, обычно имеют префикс со знаком равенства и просто обозначают особый тип ввода данных, который определяет обработку других ячеек, на которые имеются ссылки, - путем изменения потока управления в интерпретаторе. Именно экстернализация формул из базового интерпретатора четко определяет как электронные таблицы, так и приведенный выше пример «рейтинга на основе правил» как легко идентифицируемые примеры использования управляющих таблиц непрограммистами.
Если бы можно было сказать, что техника управляющих таблиц принадлежит какой-либо конкретной парадигме программирования, ближайшей аналогией могло бы быть программирование на основе автоматов или «отражающий» (форма метапрограммирования - поскольку можно сказать, что записи таблицы «изменяют» поведение интерпретатора). Однако сам интерпретатор и подпрограммы могут быть запрограммированы с использованием любой из доступных парадигм или даже их комбинации. Сама таблица может представлять собой набор значений «необработанных данных », которые даже не нужно компилировать и которые могут быть прочитаны из внешнего источника (за исключением конкретных, зависящих от платформы, реализаций, использующих указатели памяти непосредственно для большей эффективности).
Многомерная управляющая таблица имеет концептуальное сходство с байт-кодом, работающим на представленной машине, в том, что зависимая от платформы программа «интерпретатор» обычно требуется для выполнения фактического выполнения (которое в степени условно определяется содержимым таблиц). Есть также некоторые концептуальные сходства с недавним Общий промежуточный язык (CIL) с целью создания общего промежуточного «набора инструкций», который не зависит от платформы (но, в качестве отличия от CIL, никаких претензий на использование в общем ресурсе) для других языков). P-код также можно рассматривать как аналогичную, но более раннюю работу с истоками еще в 1966 году.
Чтобы определить ход выполнения программы, обычная "аппаратная" функция Счетчик программ эффективно моделируется либо с помощью указателя на первую (или следующую) запись таблицы, либо с помощью индекс к нему. «Извлечение» инструкции включает декодирование данных в этой записи таблицы - без необходимости сначала копировать все или некоторые данные в этой записи. Языки программирования, которые могут использовать указатели, имеют двойное преимущество: меньше накладных расходов, как при доступе к содержимому, так и при перемещении счетчика, чтобы он указывал на следующую таблицу после выполнения. Вычисление адресной следующей «инструкции» (т. Е. Записи в таблице) может быть выполнено даже как необязательное дополнительное действие для каждой отдельной записи таблицы, позволяющее циклически выполнять и / / переходить инструкции на на любом этапе.
Программа-интерпретатор может использовать другие параметры выполнения программы управления (и соответствующие детали в зависимости от типа инструкции) на каждом этапе записи полной записи или частичной трассировки фактического выполнения программы для отладки, обнаружения горячих точек, анализа покрытия кода и анализа производительности (см. примеры CT3 и CT4 выше).
Необязательно: -
Следующее в основном относится к их использованию в многомерных таблицах, а не в одномерных таблицах, обсужденных ранее.
Многостороннее ветвление - важный метод программирования, который слишком часто заменяется эффективная последовательность тестов if. Питер Наур недавно написал мне, что он использует таблицы для управления потоком программ основной идеей информатики, которая была почти забыта; но он ожидает, что в любой день он будет готов для повторного открытия. Это ключ к эффективности всех лучших компиляторов, которые я изучал.
— Дональд Кнут, Структурированное программирование с переходом к работеЕсть другой способ взглянуть на программу, написанную на языке интерпретации. Это можно рассматривать как серию различных подпрограмм, один за другим. Такая программа может быть расширена до закодированную форму, которая легко интерпретируется. Преимущество методов интерпретации - компактность представления, машинная независимость и повышенные диагностические возможности. Интерпретатор часто можно написать так, чтобы время, затрачиваемое на интерпретацию самого кода и переходного процесса, было незначительным
— Дональд Кнут, Искусство компьютерного программирования, том 1, 1997, стр. 202Пространство, используемое для представления программы, часто можно уменьшить за счет использования интерпретаторов. Типичным примером является использование сложного протокола или лексического формата в небольшой таблице
— Джон Бентли, Написание эффективных программТаблицы переходы могут быть особенно эффективными, если тесты могут опускаться. Например, если какое-либо значение является перечислимым типом (или символом), то оно может содержать только небольшой фиксированный диапазон значений, а проверка диапазона избыточной при условии, что таблица переходов достаточно велика для обработки всех возможных значений
— Дэвид. А. SPULER, Генерация компилятора для многосторонних ветвей как проблема статического поискаПрограммы должны быть написаны для чтения и людьми только случайно для выполнения машинами.
— «Структура и интерпретация компьютерных программ», предисловие к первому изданию, Абельсон и СассманПокажи мне свою блок-схему и скрой свои таблицы, и я буду продолжать озадачиваться. Покажите мне свои таблицы, и обычно ваша блок-схема мне не понадобится; это будет очевидно.
— «Мифический человеко-месяц: Очерки программной инженерии», Фред Брукс