- •Глава 1
- •1.2. Процедурные языки
- •1.3. Языки, ориентированные на данные
- •1.4. Объектно-ориентированные языки
- •1.5. Непроцедурные языки
- •1.6. Стандартизация
- •1.7. Архитектура компьютера
- •1.8. Вычислимость
- •1.9. Упражнения
- •Глава 2
- •2.2. Семантика
- •2.3. Данные
- •2.4. Оператор присваивания
- •2.5. Контроль соответствия типов
- •2.7. Подпрограммы
- •2.8. Модули
- •2.9. Упражнения
- •Глава 3
- •3.1. Редактор
- •3.2. Компилятор
- •3.3. Библиотекарь
- •3.4. Компоновщик
- •3.5. Загрузчик
- •3.6. Отладчик
- •3.7. Профилировщик
- •3.8. Средства тестирования
- •3.9. Средства конфигурирования
- •3.10. Интерпретаторы
- •3.11. Упражнения
- •Глава 4
- •4.1. Целочисленные типы
- •I: Integer; -- Целое со знаком в языке Ada
- •4.2. Типы перечисления
- •4.3. Символьный тип
- •4.4. Булев тип
- •4.5. Подтипы
- •4.6. Производные типы
- •4.7. Выражения
- •4.8. Операторы присваивания
- •4.9. Упражнения
- •Глава 5
- •5.1. Записи
- •5.2. Массивы
- •5.3. Массивы и контроль соответствия типов
- •Подтипы массивов в языке Ada
- •5.5. Строковый тип
- •5.6. Многомерные массивы
- •5.7. Реализация массивов
- •5.8. Спецификация представления
- •5.9. Упражнения
- •Глава 6
- •6.1. Операторы switch и case
- •6.2. Условные операторы
- •6.3. Операторы цикла
- •6.4. Цикл for
- •6.5. «Часовые»
- •6.6. Инварианты
- •6.7. Операторы goto
- •6.8. Упражнения
- •Глава 7
- •7.1. Подпрограммы: процедуры и функции
- •7.2. Параметры
- •7.3. Передача параметров подпрограмме
- •7.4. Блочная структура
- •7.5. Рекурсия
- •7.6. Стековая архитектура
- •7.7. Еще о стековой архитектуре
- •7.8. Реализация на процессоре Intel 8086
- •7.9. Упражнения
- •Глава 8
- •8.1 . Указательные типы
- •8.2. Структуры данных
- •8.3. Распределение памяти
- •8.4. Алгоритмы распределения динамической памяти
- •8.5. Упражнения
- •Глава 9
- •9.1. Представление вещественных чисел
- •9.2. Языковая поддержка вещественных чисел
- •9.3. Три смертных греха
- •Вещественные типы в языке Ada
- •9.5. Упражнения
- •Глава 10
- •10.1. Преобразование типов
- •10.2. Перегрузка
- •10.3. Родовые (настраиваемые) сегменты
- •10.4. Вариантные записи
- •10.5. Динамическая диспетчеризация
- •10.6. Упражнения
- •Глава 11
- •11.1. Требования обработки исключительных ситуаций
- •11.2. Исключения в pl/I
- •11.3. Исключения в Ada
- •11.5. Обработка ошибок в языке Eiffei
- •11.6. Упражнения
- •Глава 12
- •12.1. Что такое параллелизм?
- •12.2. Общая память
- •12.3. Проблема взаимных исключений
- •12.4. Мониторы и защищенные переменные
- •12.5. Передача сообщений
- •12.6. Язык параллельного программирования оссаm
- •12.7. Рандеву в языке Ada
- •12.9. Упражнения
- •Глава 13
- •13.1. Раздельная компиляция
- •13.2. Почему необходимы модули?
- •13.3. Пакеты в языке Ada
- •13.4. Абстрактные типы данных в языке Ada
- •13.6. Упражнения
- •Глава 14
- •14.1. Объектно-ориентированное проектирование
- •В каждом объекте должно скрываться одно важное проектное решение.
- •14.3. Наследование
- •14.5. Объектно-ориентированное программирование на языке Ada 95
- •Динамический полиморфизм в языке Ada 95 имеет место, когда фактический параметр относится к cw-типу, а формальный параметр относится к конкретному типу.
- •14.6. Упражнения
- •Глава 15
- •1. Структурированные классы.
- •15.1. Структурированные классы
- •5.2. Доступ к приватным компонентам
- •15.3. Данные класса
- •15.4. Язык программирования Eiffel
- •Если свойство унаследовано от класса предка более чем одним путем, оно используется совместно; в противном случае свойства реплицируются.
- •15.5. Проектные соображения
- •15.6. Методы динамического полиморфизма
- •15.7. Упражнения
- •5Непроцедурные
- •Глава 16
- •16.1. Почему именно функциональное программирование?
- •16.2. Функции
- •16.3. Составные типы
- •16.4. Функции более высокого порядка
- •16.5. Ленивые и жадные вычисления
- •16.6. Исключения
- •16.7. Среда
- •16.8. Упражнения
- •Глава 17
- •17.2. Унификация
- •17.4. Более сложные понятия логического программирования
- •17.5. Упражнения
- •Глава 18
- •18.1. Модель Java
- •18.2. Язык Java
- •18.3. Семантика ссылки
- •18.4. Полиморфные структуры данных
- •18.5. Инкапсуляция
- •18.6. Параллелизм
- •18.7. Библиотеки Java
- •8.8. Упражнения
6.8. Упражнения
1. Реализует ваш компилятор все case-/switch-операторы одинаково, или он пытается выбирать оптимальную реализацию для каждого оператора?
2. Смоделируйте оператор repeat языка Pascal в Ada и С.
3. Первоначально в языке Fortran было определено, что цикл выполняется, по крайней мере, один раз, даже если значение low больше, чем значение high! Чем могло быть мотивировано такое решение?
4. Последовательный поиск в языке С:
C |
i++;
можно записать как
C |
; /* Пустой оператор */
В чем различие между двумя вариантами вычислений?
5. Предположим, что в языке Ada переменная индекса может существовать за рамками цикла. Покажите, как бы это воздействовало на оптимизацию цикла.
6. Сравните сгенерированный для поиска код, реализованный с помощью операторов break или exit, с кодом, сгенерированным для поиска с «часовым».
7. Напишите программу поиска с «часовым», используя do-while вместо while. Будет ли это эффективнее?
8. Почему мы помещали «часового» в начало массива, а не в конец?
9. (Шолтен) В игре Го используют камни двух цветов, черные и белые. Предположим, что у вас в коробке неизвестная смесь камней, и вы выполняете следующий алгоритм:
while Stones_Left_in_Can loop -- пока есть камни в коробке
Ada |
if Color(S1 )=Color(S2) then
Add_Black_Stone; --добавить черный камень
else
Add_White_Stone; -- добавить белый камень
end if;
end loop;
Найдите переменную, значение которой уменьшается, оставаясь неотрицательным, и тем самым покажите, что цикл заканчивается. Можете ли вы что-нибудь сказать относительно цвета последнего камня? (Подсказка: напишите инвариант цикла для числа белых камней).
Глава 7
Подпрограммы
7.1. Подпрограммы: процедуры и функции
Подпрограмма — это сегмент программы, к которому можно обратиться из любого места внутри программы. Подпрограммы используются по разным причинам:
• Сегмент программы, который должен выполняться на разных стадиях вычисления, может быть написан один раз в виде подпрограммы, а затем многократно выполняться. Это экономит память и позволяет избежать ошибок, возможных при копировании кода с одного места на другое.
• Подпрограмма — это логическая единица декомпозиции программы. Даже если сегмент выполняется только один раз, полезно оформить его в виде подпрограммы с целью тестирования, документирования и улучшения читаемости программы.
• Подпрограмму также можно использовать как физическую единицу декомпозиции программы, т. е. как единицу компиляции. В языке Fortran подпрограмма (subroutine) — это единственная единица и декомпозиции, и компиляции. В современных языках физической единицей декомпозиции является модуль, представляющий собой группу объявлений и подпрограмм (см. гл. 13).
Подпрограмма состоит из:
• объявления, которое задает интерфейс с подпрограммой; это объявление включает имя подпрограммы, список параметров (если есть) и тип возвращаемого значения (если есть);
• локальных объявлений, которые действуют только внутри тела подпрограммы;
• последовательности выполняемых операторов.
Локальные объявления и выполняемые операторы образуют тело подпрограммы.
Подпрограммы, которые возвращают значение, называются функциями (functions), а те, что не возвращают, — процедурами (procedures). Язык С не имеет отдельного синтаксиса для процедур; вместо этого следует написать функцию, которая возвращает тип void, т.е. тип без значения:
C |
void proc(int a, float b);
Такая функция имеет те же свойства, что и процедура в других языках, поэтому мы используем термин «процедура» и при обсуждении языка С.
Обращение к процедуре задается оператором вызова процедуры call. В языке Fortran он имеет специальный синтаксис:
C |
call proc(x,y)
тогда как в других языках просто пишется имя процедуры с фактическими параметрами:
-
C
ргос(х.у);
Семантика вызова процедуры следующая: приостанавливается текущая последовательность команд; выполняется последовательность команд внутри тела процедуры; после завершения тела процедуры выполнение продолжается с первой команды, следующей за вызовом процедуры. Это описание игнорирует передачу параметров и их области действия, что будет объектом детального рассмотрения в следующих разделах.
Так как функция возвращает значение, объявление функции должно определять тип возвращаемого значения. В языке С тип функции задается в объявлении функции перед ее именем:
C |
int func(int a, float b);
тогда как в языке Ada используется другой синтаксис:
Ada |
function Func(A: Integer; В: Float) return Integer;
Вызов функции является не оператором, а элементом выражения:
-
C
a = x + func(r,s) + y;
Тип результата функции не должен противоречить типу, ожидаемому в выражении. Обратите внимание, что в языке С во многих случаях делаются неявные преобразования типов, тогда как в Ada тип результата должен точно соответствовать контексту. По смыслу вызов функции аналогичен вызову процедуры: приостанавливается вычисление выражения; выполняются команды тела функции; затем возвращенное значение используется для продолжения вычисления выражения.
Термин «функция» фактически совершенно не соответствует тому контексту, в котором он употребляется в обычных языках программирования. В математике функция — всего лишь отображение одного набора значений на другой. Если использовать техническую терминологию, то математическая функция не имеет побочного эффекта, потому что ее «вычисление» прозрачно в точке, в которой делается «вызов». Если есть значение 3.6, и вы запрашиваете значение sin(3.6), то вы будете получать один и тот же результат всякий раз, когда в уравнении встретится эта функция. В программировании функция может выполнять произвольное вычисление, включая ввод-вывод или изменение глобальных структур данных:
int x,y,z;
C |
{
у = get(); /* Изменяет глобальную переменную */
return x*y; /* Значение зависит от глобальной переменной */
z = х + func(void) + у;
Если оптимизатор изменил порядок вычисления так, что х + у вычисляется перед вызовом функции, то получится другой результат, потому что функция изменяет значение у.
Поскольку все подпрограммы в С — функции, в программировании на языке С широко используются возвращаемые значения и в «невычислительных» случаях, например в подпрограммах ввода-вывода. Это допустимо при условии, что понятны возможные трудности, связанные с зависимостью от порядка и оптимизацией. Исследование языков программирования привело к разработке интереснейших языков, которые основаны на математически правильном понятии функции (см. гл. 16).