|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[12] sqrt sqrt-iter good-enough improve square abs average Рис. 1.2: Процедурная декомпозиция программы sqrt. 1.1.8 Процедуры как абстракции типа «черный ящик» Sqrt - наш первый пример процесса, определенного множеством зависимых друг от друга процедур. Заметим, что определение sqrt-iter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя. Идея, что можно определить процедуру саму через себя, возможно, кажется Вам подозрительной; неясно, как такое «циклическое» определение вообще может иметь смысл, не то что описывать хорошо определенный процесс для исполнения компьютером. Более осторожно мы подойдем к этому в разделе 1.2. Рассмотрим, однако, некоторые другие важные детали, которые иллюстрирует пример с sqrt. Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи: как понять, что очередное приближение нас устраивает, как улучшить очередное приближение, и так далее. Каждая из этих задач решается с помощью отдельной процедуры. Вся программа sqrt может рассматриваться как пучок процедур (показанный на рис.1.1.8), отражающий декомпозицию задачи на подзадачи. Важность декомпозиционной стратегии не просто в том, что задача разделяется на части. В конце концов, можно взять любую большую программу и поделить ее на части: первые десять строк, следующие десять строк и так далее. Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использована при определении других процедур. Например, когда мы определяем процедуру good-enough? с помощью square, мы можем рассматривать процедуру square как «черный ящик». В этот момент нас не интересует, как она вычисляет свой результат, - важно только то, что она способна вычислить квадрат. О деталях того, как вычисляют квадраты, можно сейчас забыть и рассмотреть их потом. Действительно, пока мы рассматриваем процедуру good-enough?, square - не совсем процедура, но скорее абстракция процедуры, так называемая процедурная абстракция (procedural abstraction). На этом уровне абстракции все процедуры, вычисляющие квадрат, одинаково хороши. Таким образом, если рассматривать только возвращаемые значения, то следующие две процедуры для возведения числа в квадрат будут неотличимы друг от друга. Каждая из них принимает числовой аргумент и возвращает в качестве значения квадрат этого числа.25 (define (square x) (* x x)) (define (square x) (exp (double (log x)))) (define (double x) (+ x x)) Таким образом, определение процедуры должно быть способно скрывать детали. Может оказаться, что пользователь процедуры не сам ее написал, а получил от другого программиста как черный ящик. От пользователя не должно требоваться знания, как работает процедура, чтобы ее использовать. Локальные имена Одна из деталей реализации, которая не должна заботить пользователя процедуры - это то, какие человек, писавший процедуру, выбрал имена для формальных параметров процедуры. Таким образом, следующие две процедуры должны быть неотличимы: (define (square x) (* x x)) (define (square y) (* y y)) Этот принцип - что значение процедуры не должно зависеть от имен параметров, которые выбрал ее автор, - может сначала показаться очевидным, однако он имеет глубокие следствия. Простейшее из этих следствий состоит в том, что имена параметров должны быть локальными в теле процедуры. Например, в программе вычисления квадратного корня при определении good-enough? мы использовали square: (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) Намерение автора good-enough? состоит в том, чтобы определить, достаточно ли близко квадрат первого аргумента лежит ко второму. Мы видим, что автор good-enough? обращается к первому аргументу с помощью имени guess, а ко второму с помощью имени x. Аргументом square является guess. Поскольку автор square использовал имя x (как мы видели выше), чтобы обратиться к этому аргументу, мы видим, что x в good-enough? должно отличаться от x в square. Запуск процедуры square не должен отразится на значении x, которое использует good-enough?, поскольку это значение x понадобится good-enough?, когда square будет вычислена. Если бы параметры не были локальны по отношению к телам своих процедур, то параметр x в square смешался бы с параметром x из good-enough?, и поведение good-enough? зависело бы от того, какую версию square мы использовали. Таким образом, процедура square не была бы черным ящиком, как мы того хотим. 25 Неясно даже, которая из этих процедур более эффективна. Это зависит от того, какая имеется аппаратура. Существуют машины, на которых «очевидная» реализация будет медленней. Представьте себе машину, в которой очень эффективным способом хранятся большие таблицы логарифмов и обратных логарифмов. У формального параметра особая роль в определении процедуры: не имеет значения, какое у этого параметра имя. Такое имя называется связанной переменной (bound variable), и мы будем говорить, что определение процедуры связывает (binds) свои формальные параметры. Значение процедуры не изменяется, если во всем ее определении параметры последовательным образом переименованы.26 Если переменная не связана, мы говорим, что она свободна (free). Множество выражений, для которых связывание определяет имя, называется областью действия (scope) этого имени. В определении процедуры связанные переменные, объявленные как формальные параметры процедуры, имеют своей областью действия тело процедуры. В приведенном выше определении good-enough?, guess и x - связанные переменные, а <, -, abs и square - свободные. Значение good-enough? должно быть независимо от того, какие имена мы выберем для guess и x, пока они остаются отличными друг от друга и от <, -, abs и square. (Если бы мы переименовали guess в abs, то породили бы ошибку, захватив (capture) переменную abs. Она превратилась бы из свободной в связанную.) Однако значение good-enough? не является независимым от ее свободных переменных. Разумеется, оно зависит от того факта (внешнего по отношению к этому определению), что символ abs называет процедуру вычисления модуля числа. Good-enough? будет вычислять совершенно другую функцию, если в ее определении мы вместо abs подставим cos. Внутренние определения и блочная структура До сих пор нам был доступен только один вид изоляции имен: формальные параметры процедуры локальны по отношению к телу этой процедуры. Программа вычисления квадратного корня иллюстрирует еще один вид управления использованием имен, которым мы хотели бы владеть. Существующая программа состоит из отдельных процедур: (define (sqrt x) (sqrt-iter 1.0 x)) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (improve guess x) (average guess (/ x guess))) Проблема здесь состоит в том, что единственная процедура, которая важна для пользователей sqrt - это сама sqrt. Остальные процедуры (sqrt-iter, good-enough? и improve) только забивают им головы. Теперь пользователи не могут определять других процедур с именем good-enough? ни в какой другой программе, которая должна работать совместно с программой вычисления квадратного корня, поскольку sqrt требуется это имя. Эта проблема 26Понятие последовательного переименования на самом деле достаточно тонкое и трудное для определения. Знаменитым логикам случалось делать здесь ужасные ошибки. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||