Программный код, состоящий из вызовов функций

Введение

Программа, исходный код которой состоит исключительно из вызовов функций.

В информатике, потоковый код — это техника программирования, в которой код по сути состоит исключительно из вызовов подпрограмм. Он часто используется в компиляторах, которые могут генерировать код в такой форме или быть реализованными в ней сами. Код может обрабатываться интерпретатором или представлять собой просто последовательность инструкций вызова машинного кода. Потоковый код обладает большей плотностью, чем код, генерируемый альтернативными методами генерации и альтернативными соглашениями о вызовах. В архитектурах с кэшем он может выполняться немного медленнее. Однако программа, достаточно маленькая, чтобы поместиться в кэш процессора, может работать быстрее, чем более крупная программа, страдающая от частых промахов кэша. Небольшие программы также могут быстрее переключаться между потоками, когда другие программы заполнили кэш. Потоковый код наиболее известен своим использованием во многих компиляторах языков программирования, таких как Forth, во многих реализациях BASIC, некоторых реализациях COBOL, ранних версиях B и других языках для небольших миникомпьютеров и для любительских радиоспутников.

История

Обычный способ создания компьютерных программ — использование компилятора для перевода исходного кода (написанного на каком-то символическом языке) в машинный код. Полученный исполняемый файл обычно быстрый, но поскольку он специфичен для аппаратной платформы, он не является переносимым. Другой подход заключается в генерации инструкций для виртуальной машины и использовании интерпретатора на каждой аппаратной платформе. Интерпретатор создает экземпляр среды виртуальной машины и выполняет инструкции. Таким образом, только интерпретатор должен быть скомпилирован. Ранние компьютеры имели относительно небольшой объем памяти. Например, большинство Data General Nova, IBM 1130 и многие из первых микрокомпьютеров имели всего 4 кБ оперативной памяти. Следовательно, много времени тратилось на поиск способов уменьшить размер программы, чтобы она поместилась в доступную память. Одно из решений — использовать интерпретатор, который читает символический язык по частям и вызывает функции для выполнения действий. Поскольку исходный код обычно намного компактнее, чем полученный машинный код, это может снизить общее потребление памяти. Именно поэтому Microsoft BASIC является интерпретатором: его собственный код должен был разделять 4 кБ памяти машин, таких как Altair 8800, с исходным кодом пользователя. Компилятор переводит с исходного языка в машинный код, поэтому компилятор, исходный код и результат должны находиться в памяти одновременно. В интерпретаторе выходных данных нет. *Код с прошивкой* — это стиль форматирования компилируемого кода, который минимизирует использование памяти. Вместо того чтобы записывать каждый шаг операции при каждом ее возникновении в программе, как это было принято, например, в макроассемблерах, компилятор записывает каждый общий фрагмент кода в подпрограмму. Таким образом, каждый фрагмент существует только в одном месте в памяти (см. «Не повторяйся»). Приложение верхнего уровня в этих программах может состоять только из вызовов подпрограмм. Многие из этих подпрограмм, в свою очередь, также состоят только из вызовов подпрограмм нижнего уровня. Основные вычислительные системы и некоторые ранние микропроцессоры, такие как RCA 1802, требовали несколько инструкций для вызова подпрограммы. В приложении верхнего уровня и во многих подпрограммах эта последовательность постоянно повторяется, при этом только адрес подпрограммы меняется от одного вызова к другому. Это означает, что программа, состоящая из множества вызовов функций, также может содержать значительное количество повторяющегося кода. Для решения этой проблемы системы с кодом с прошивкой использовали псевдокод для представления вызовов функций одним оператором. Во время выполнения крошечный «интерпретатор» сканировал бы код верхнего уровня, извлекал адрес подпрограммы в памяти и вызывал ее. В других системах эта же основная концепция реализуется в виде таблицы переходов, таблицы диспетчеризации или виртуальной таблицы методов, все из которых состоят из таблицы адресов подпрограмм. В 1970-х годах разработчики аппаратного обеспечения приложили значительные усилия, чтобы сделать вызовы подпрограмм более быстрыми и простыми. В улучшенных конструкциях для вызова подпрограммы требуется только одна инструкция, поэтому использование псевдоинструкции не экономит место. Кроме того, производительность этих вызовов практически не имеет дополнительных накладных расходов. Сегодня, хотя почти все языки программирования ориентированы на изоляцию кода в подпрограммы, они делают это для ясности и удобства сопровождения кода, а не для экономии места. Системы с кодом с прошивкой экономят место, заменяя список вызовов функций, где только адрес подпрограммы меняется от одного вызова к следующему, списком токенов выполнения, которые по сути являются вызовами функций без кода операции вызова, оставляя только список адресов. За прошедшие годы программисты создали множество вариаций этого «интерпретатора» или «маленького селектора». Конкретный адрес в списке адресов может быть извлечен с помощью индекса, регистра общего назначения или указателя. Адреса могут быть прямыми или косвенными, смежными или несмежными (связанными указателями), относительными или абсолютными, разрешаемыми во время компиляции или динамически создаваемыми. Ни одна из этих вариаций не является «лучшей» для всех ситуаций.

The common way to make computer programs is to use a compiler to translate source code (written in some symbolic language) to machine code. The resulting executable is typically fast but, because it is specific to a hardware platform, it isn't portable. A different approach is to generate instructions for a virtual machine and to use an interpreter on each hardware platform. The interpreter instantiates the virtual machine environment and executes the instructions. Thus, only the interpreter must be compiled. Early computers had relatively little memory. For example, most Data General Nova, IBM 1130, and many of the first microcomputers had only 4 kB of RAM installed. Consequently, a lot of time was spent trying to find ways to reduce a program's size, to fit in the available memory. One solution is to use an interpreter which reads the symbolic language a bit at a time, and calls functions to perform the actions. As the source code is typically much denser than the resulting machine code, this can reduce overall memory use. This was the reason Microsoft BASIC is an interpreter: its own code had to share the 4 kB memory of machines like the Altair 8800 with the user's source code. A compiler translates from a source language to machine code, so the compiler, source, and output must all be in memory at the same time. In an interpreter, there is no output. Threaded code is a formatting style for compiled code that minimizes memory use. Instead of writing out every step of an operation at its every occurrence in the program, as was common in macro assemblers for instance, the compiler writes each common bit of code into a subroutine. Thus, each bit exists in only one place in memory (see "Don't repeat yourself"). The top level application in these programs may consist of nothing but subroutine calls. Many of these subroutines, in turn, also consist of nothing but lower level subroutine calls. Mainframes and some early microprocessors such as the RCA 1802 required several instructions to call a subroutine. In the top level application and in many subroutines, that sequence is constantly repeated, with only the subroutine address changing from one call to the next. This means that a program consisting of many function calls may have considerable amounts of repeated code as well. To address this, threaded code systems used pseudo code to represent function calls in a single operator. At run time, a tiny "interpreter" would scan over the top level code, extract the subroutine's address in memory, and call it. In other systems, this same basic concept is implemented as a branch table, dispatch table, or virtual method table, all of which consist of a table of subroutine addresses. During the 1970s, hardware designers spent considerable effort to make subroutine calls faster and simpler. On the improved designs, only a single instruction is expended to call a subroutine, so the use of a pseudo instruction saves no room. Additionally, the performance of these calls is almost free of additional overhead. Today, though almost all programming languages focus on isolating code into subroutines, they do so for code clarity and maintainability, not to save space. Threaded code systems save room by replacing that list of function calls, where only the subroutine address changes from one call to the next, with a list of execution tokens, which are essentially function calls with the call opcode(s) stripped off, leaving behind only a list of addresses. Over the years, programmers have created many variations on that "interpreter" or "small selector". The particular address in the list of addresses may be extracted using an index, general purpose register or pointer. The addresses may be direct or indirect, contiguous or non contiguous (linked by pointers), relative or absolute, resolved at compile time or dynamically built. No single variation is "best" for all situations.

Модели резьбы

Практически весь исполняемый многопоточный код использует один из этих методов для вызова подпрограмм (каждый метод называется "моделью потоков").

Занавески подпрограмм

Так называемый "подпрограммный поточный код" (также "вызов-поточный код") состоит из серии машинных инструкций "вызова подпрограммы" (или адресов функций для "вызова", в отличие от использования "перехода" при прямой поточной адресации). Ранние компиляторы для ALGOL, Fortran, Cobol и некоторых систем Forth часто генерировали подпрограммный поточный код. Код во многих из этих систем работал со стеком операндов, организованным по принципу LIFO (последним пришел – первым ушел), для которого теория компиляции была хорошо разработана. Большинство современных процессоров имеют аппаратную поддержку инструкций "вызов" и "возврат из подпрограммы", поэтому накладные расходы, связанные с одной дополнительной машинной инструкцией при каждом вызове, несколько снижаются. Антон Эртл, соавтор компилятора Gforth, заявил, что "вопреки распространенному мнению, подпрограммная адресация обычно медленнее прямой адресации". Однако, последние тесты Эртла проводились на смарт-картах, игрушках, калькуляторах и часах. Битово-ориентированный токенизированный код, используемый в PBASIC, можно рассматривать как разновидность поточного кода Хаффмана.

Реже используемые нитки

Примером является строковое нить, в котором операции идентифицируются строками, обычно находящимися в хеш-таблице. Это использовалось в самых ранних реализациях Forth Чарльза Х. Мура и в экспериментальном аппаратном интерпретируемом компьютерном языке Университета Иллинойса. Оно также используется в Bashforth.