Метка: Наука
Большие программы
Большие программы обычно требуют объем памяти, близкий к общему объему памяти ЭВМ, на которой они должны выполняться, или даже превышающий его, поэтому программа, которая считается большой на одной ЭВМ, не считается таковой на другой ЭВМ с большим объемом памяти. Двумя основными факторами, определяющими размер программы, являются число операторов в программе и объем памяти, резервируемой программой для хранения данных (например, в массивах).
В этом разделе мы остановимся на проблемах, возникающих, если сам текст программы очень велик, т....
Взаимоотношения с другими людьми
До сих пор содержание этой книги было таково, чтобы помочь читателю усвоить практические рекомендации по программированию для написания собственных программ. Было рассмотрено, как подойти к решению задачи, как планировать и кодировать программу, как запускать ее в работу, как сделать ее эффективной и как преодолеть специфические трудности. Все эти рекомендации были даны Вам как отдельному программисту, работающему над отдельным проектом. Однако время от времени делались ссылки на необходимость на разных этапах консультироваться с...
Логика программы
Например, в случае обработки символов их различное представление может потребовать изменения логики программы для распознавания специальных символов и построения последовательности соответствия символов. Такого рода изменения должны производиться вручную и чрезвычайно внимательно. В случаях, когда нужно произвести систематические изменения, такие как для нестандартно представленных констант (например, восьмеричных и шестнадцатеричных), обычно практикуется применение микропроцессоров.
Наверное, наиболее сложные проблемы при переносе...
Математический фундамент
Автор стремился к объективному изложению современных тенденций в применении математического фундамента, полезного при использовании ЭВМ и служащего красной нитью при планировании создания будущих программных комплексов. От такого математического фундамента можно ожидать троякой пользы: во-первых, помощи исполнительного помощника, умеющего детализировать конкретные намерения; во-вторых, хитроумного помощника, предлагающего иногда весьма неожиданные решения неотложных проблем, и, наконец, в-третьих, умудренного опытом седого провидца,...
Алгоритмы в математике
Алгоритмы в математике использовались давно, но математически точное понятие алгоритма было предложено только в тридцатые годы нашего столетия. Тогда стало ясно, что некоторые дискретные задачи математики нельзя решать посредством алгоритмов. Последовавшее бурное развитие теории алгоритмов обеспечило появление большого числа разнообразных задач из различных областей математики, для каждой из этих задач была доказана невозможность их решения посредством алгоритма. Среди таких задач проблемы равенства в полугруппах и группах с конечным...
Доказательство алгоритмической неразрешимости
Параллельно с доказательствами алгоритмической неразрешимости многих естественно формулируемых математических массовых проблем возник вопрос об оптимизации алгоритмов, решающих математические массовые проблемы, естественно формулируемые в математической логике, алгебре, теории чисел, дискретной математике, математической кибернетике и метатеории программирования. Первоначально речь могла идти о примитивной рекурсивности алгоритма, затем об элементарности алгоритма по Кальмару.
Доказательство принадлежности некоторого алгоритма...
Иерархия класса
Наконец, имеется еще одно направление — изучение иерархии класса элементарных по Кальмару алгоритмов— класса, содержащего все практически вычислимые на ЭВМ алгоритмы. Это направление позволяет уточнить современный математический язык, обеспечивая его эффективность, например, при установлении разрешимости уравнений типов рассматриваемых во втором разделе книги. По сути дела речь идет о синтаксически ограниченных вычислениях.
Первый раздел книги носит в значительной степени вводный характер. Изложенный материал представлен в существенна...
Литеры и строки, форматный вывод чисел
В современном программировании важное место занимает обработка текстовых данных. С каждой литерой, которую можно ввести с внешнего устройства или вывести на него, связывается некоторое число — код этой литеры, так что в памяти ЭВМ литеры представлены своими кодами. Стандарт языка Форт предусматривает использование таблицы кодов ASCII, в которой задействованы все числа в диапазоне от 0 до 127. Каждый код занимает один 8-разрядный байт, в котором для представления литеры используются младшие 7 разрядов.
Такая привязка к одной конкретной кодировке...
Кодирование пробела
Ввиду его особой важности для кодирования пробела выделена специальная константа BL (от BLANK — пробел), которую для кода ASGII можно задать так: 32 CONSTANT BL. При исполнении слова BL на стеке остается код пробела. Чтобы вывести пробел на терминал, имеются следующие стандартные слова:
« SPACE ( — > ) BL EMIT | i SPACES < N--->) ?DUP IF 0 DO SPACE LOOP THEN f
Слово SPACE (пробел) выводит на терминал один пробел, а слово SPACES (пробелы) — несколько, снимая их количество со стека (это значение, как и длина строки в слове TYPE, должно быть неотрицательным).
Внутри определений через двоеточие...
Шитый код и его разновидности
Логически можно выделить два подхода к реализации языков программирования — трансляцию и интерпретацию. Транслятор преобразует входной текст программы в машинный код данной ЭВМ; впоследствии этот код, объединяясь с другими машинными модулями, образует рабочую программу, которую можно загрузить в оперативную память и исполнить. Интерпретатор непосредственно исполняет программу на языке высокого уровня, рассматривая входной текст как последовательность кодов операций, управляющих его работой. Между этими полюсами располагается целый...
Разновидности шитого кода
Во всех разновидностях шитого кода его интерпретатор должен обеспечивать выполнение трех действий, которые традиционно обозначаются так:
NEXT (следующий) — переход к интерпретации следующей ссылки в данной последовательности ссылок;
CALL (вызов) — переход в подпрограмму верхнего уровня, представленную в шитом коде;
RETURN (возврат) — возврат из подпрограммы верхнего уровня на продолжение интерпретации.
В силу его очевидной рекурсивности интерпретатор использует специальный стек в качестве собственной структуры данных. Этот стек называется...
Стек возвратов и реализация структур управления
Один из важных принципов языка Форт состоит в том, чтобы предоставить программисту максимальный доступ ко всем средствам его реализации. В соответствии с этим принципом собственные данные адресного интерпретатора — стек возвратов — были сделаны доступными, для чего введены специальные слова: > RA ->, R> ->А и R@->A. Буква R (от RETURN— возврат) в имени этих слов напоминает о том, что они работают со стеком возвратов. Все эти слова можно использовать только внутри компилируемых определений. Во время исполнения любого такого определения, представленного...
Определение слова PBRANCH
То обстоятельство, что в определении слова PBRANCH используется условный оператор, для реализации условного оператора несущественно, потому что на практике слова BRANCH и PBRANCH реализуются в форт-системах как подпрограммы нижнего уровня. Приведенные определения лишь иллюстрируют выразительные возможности языка, показывая, что даже такие, самые элементарные действия можно задать машиннонезависимым способом в виде высокоуровневых определений.
Слово LITERAL анализирует текущее состояние текстового интерпретатора: если это компиляция, то компилирует...
Реализация определяющих слов
Механизм определяющих слов составляет одно из основных достоинств языка Форт, главную «находку» его создателей. С его помощью программист может вводить свои типы данных и структуры управления, задавая их внешнее синтаксическое оформление и внутреннюю семантическую реализацию. Исходный строительный материал программист может брать из сравнительно небольшого исходного запаса слов-команд языка или создавать сам.
Широкие выразительные возможности и вместе с тем компактность реализации этого механизма вытекают из того, что в его основе...
DOES
Эта команда перехода с возвратом передает управление на точку DOES, сообщив ей в качестве своего адреса возврата адрес следующей последовательности ссылок — исполняющей части определения CONST . Точка DOES кладет на стек адрес поля параметров статьи ХОР (в этот момент в рабочей ячейке W еще находится адрес поля кода статьи ХОР , загруженный туда действием NEXT) и исполняет действие CALL для исполняющей части определения CONST . Следующее исполняемое слово @ заменит на стеке адрес поля параметров статьи ХОР числом 4, скомпилированным по этому адресу,...
Встроенный ассемблер
Встроенный ассемблер позволяет программисту задавать реализацию слов непосредственно в машинном коде данной ЭВМ. Это дает ему возможность, с одной стороны, повышать быстродействие программы до максимально возможного уровня за счет перевода интенсивно используемых слов непосредственно в машинный код, а с другой — использовать особенности архитектуры данной ЭВМ и «напрямик» связываться с операционной системой и внешним окружением.
Примеры обоих случаев дает сама форт-система. Очевидно, что слова, выполняющие арифметические операции...
Вид машинной программы
Конкретный вид машинной программы зависит от архитектуры данной ЭВМ. Общим правилом является то, что этот текст представляет собой последовательность слов, которые исполняются текстовым интерпретатором, в результате чего на вершине словаря формируется соответствующий двоичный машинный код. Машинные команды записываются в естественной для Форта обратной польской форме: сначала операнды, а затем слово, обозначающее мнемонику команды.
Операнды — это слова, вычисляющие на стеке размещения операндов: номера регистров, адреса в памяти...
Служебные слова
Пусть служебные слова RBLK A,N и WBLK A,N ->-выполняют чтение блока с указанным номером в заданную область оперативной памяти и запись из нее.
Для записи всех измененных буферов во внешнюю память служит слово SAVE-BUFFERS (сохранить буфера).
При исполнении слова SAVE-BUFFERS все буфера остаются приписанными прежним блокам. Слово FLUSH (очистить) переписывает все исправленные блоки во внешнюю память и освобождает буфера. Многие реализации имеют слово EMPTY-BUFFERS (опустошить буфера), которое освобождает буферный пул, не переписывая исправленные блоки.
Внешняя память...
Интерпретация входного потока
Собственно работа форт-системы заключается в распознавании и исполнении слов-команд, которые программист вводит с терминала. Ввод осуществляется построчно: набрав нужный текст, программист нажимает специальную управляющую клавишу, сообщая тем самым о завершении ввода. Форт-система размещает введенный текст в специальном буфере для ввода с терминала, который располагается в адресном пространстве оперативной памяти. Адрес начала этого буфера дает стандартное слово TIB (сокращение от TEXT INPUT BUFFER — буфер для ввода текста), его длина хранится...
Инфиксная запись формул
Для многих программистов трудным барьером на пути к овладению языком Форт оказывается используемая в нем обратная польская форма для записи выражений. Опишем простую надстройку над языком Форт, которая позволяет записывать формулы в обычной инфиксной форме с использованием скобок. Будем по-прежнему считать все элементы такого выражения (скобки, знаки операций и элементарные термы) отдельными форт-словами и разделять их при записи пробелами. Задача состоит в том, чтобы вычисления на стеке автоматически перегруппировывались исходя из...
Признак немедленного исполнения
Переопределенные слова получают признак немедленного исполнения, чтобы описанные действия по переупорядочиванию вычислений выполнялись и во время компиляции, компилируя нужную последовательность операций. В заключение осталось переопределить круглые скобки, явно задающие порядок вычислений.
Открывающая скобка кладет на стек значение 0 — ограничитель для выталкивания операций. Закрывающая скобка выталкивает все операции до ближайшего ограничителя и удаляет его из стека. Переопределение открывающей скобки делает невозможным ее...
Действие АДР
Нетрудно увидеть, что действие АДР совпадает со стандартным действием для переменной, состоящим в том, что адрес поля параметров кладется на стек. Определим теперь слово QUAN, используя слово ПРИСВ в качестве вспомогательного.
Создающая часть этого определения использует поле кода создаваемой статьи как рабочую ячейку, из которой сначала извлекается значение для 2CFA / засланное туда словом CREATE, и затем значение для 1CFA, которое засылается туда словом ПРИСВ . Окончательное значение в этой ячейке устанавливается словом DOES> . Описание переменной...
Примеры
Составить словесную запись алгоритма решения уравнения ах = Ъ (а — произвольное действительное число).
На первых порах перед составлением словесной записи алгоритма удобно предварительно вычерчивать его схему. В данном случае вся суть алгоритма сводится к проверке условия а = О (если оно не соблюдается, решение находится тривиально: х = 5/а; если же а = О, ни одно х не удовлетворяет решению). Схема искомого алгоритма изображена на рисунке.
Итак, вслед за чтением значения исходного данного а (в схеме-алгоритма нет такого блока) нужно сразу приступить...
Алгоритм вычисления суммы
Составить алгоритм вычисления суммы первых 20 членов последовательности с общим членом.
Для циклического накапливания сумм при составлении соответствующих алгоритмов используется предписание стандартного вида:
сумма: = сумма + слагаемое
Если повторять такое предписание требуемое количество раз, изменяя соответствующим образом слагаемое, то и будет получена искомая сумма. Понятно, что сумма перед началом работы цикла должна иметь нулевое значение. В схеме, изображенной на рисунке 34, роль суммы выполняет переменная S, а роль слагаемого...
Функции пользователя и подпрограммы
В программировании довольно часто возникают случаи, когда одинаковые вычисления приходится производить в разных местах программы. Чтобы каждый раз не выписывать одинаковые операторы, языки программирования включают специальные средства, позволяющие описывать повторяющиеся в программе вычисления только раз, а по мере необходимости использовать эти описания в тех местах, где это требуется. Для обозначения такого рода средств обычно используется общее наименование — процедуры. Имеются такие средства и в языке Бейсик, хотя в разных...
Устройство графического вывода
Пусть устройством графического вывода является экран дисплея, а курсор находится в исходном положении (в левом нижнем углу). Тогда оператор
PLOT < 280, U>
(здесь Ах = 280, Ду = $) вызывает холостое перемещение курсора по горизонтали вправо на 280 точек, т. е. до середины экрана. А оператор
PLOTC, 240, D> прочертит вертикальную линию в движении снизу вверх на 240 дискрет. Если эти два оператора выполнить один за другим, то на экране получится изображение в виде вертикальной линии, пересекающей экран точно посередине (рис. 60, а). Для последовательного выполнения...
Запись алгоритмов на языке Паскаль
Стремление усовершенствовать методику конструирования алгоритмов, приведшее к появлению структурного подхода, не могло не оказать влияния на разработку новых языков программирования. Потребность в разработке новых алгоритмических языков вытекает из многих факторов. Это и желание учесть недостатки и ошибки ранее разработанных языков, а также (и это наиболее существенно) учесть новые возможности вычислительных систем.
Так, появившиеся в сравнительно недавнее время версии алгоритмических языков Паскаль и Ада уже учитывали потребности...
Компилятор
Под ними подразумеваются эффективность и объем как компилятора, так и скомпилированного кода. И то и другое, очевидно, в большой степени аппаратурно-зависимо, но могут существовать ограничения, либо налагаемые самой машиной, либо финансовые, либо определяемые временем прохождения задания, которые будут в конкретных случаях устранены другими языками или, по крайней мере, ослаблены ими. Другой параметр — специальные машинные средства, которые могут Вам понадобиться, такие как графопостроитель или устройство микрофильмирования. Может...
Детальное рассмотрение Фортрана
Остальной материал данного раздела посвящен более детальному рассмотрению Фортрана, с которым возникает больше всего проблем. Фактически можно сказать, что огромное число программ на Фортране написано не в соответствии со стандартом и что значительная часть программистов, работающих на Фортране, не знает об ограничениях, налагаемых стандартов.
Ограниченность объема не позволяет рассмотреть стандартизацию языков с формальной и неформальной точек зрения, однако программисты должны всегда помнить о том, что любая реализация любого...