Лекции по информатике (984119), страница 29
Текст из файла (страница 29)
О„днако этот способ не позволяет полностью реализовать тот уровень обобщения, который можно достичь при работе с процедурами. 7.2.1.2 Спецификационньсй метод Абстракция через спецификацию позволяет нам абстрагироваться от процесса вычислений, описанных в теле процедуры, до уровня знания лишь того, что данная процедура должна в итоге реализовать ~40~. Это достигается путем задания лля каждой процедуры спецификации, описывающей эффект ее работы, после чего смысл обращения к данной процедуре становитс:я ясным чсрез анализ этой спецификации, а, не самого тела, процедуры.
Мы пользуемся абстракцией через спецификацию всякий раз, когда связываем с процедурой некий комментарий, достаточно информативный для того, чтобы иметь возможность работы с ней без анализа тела процедуры. Одним из удобных способов составления подобных комментариев является использование пар угпв~рждеиий. Утверждение тес>ц>геа (или начальное условие) задает на входе процедуры истинность или ложность некоторого условия.
Обычно на практике правильное выполнение процедуры задается некоторым набором таких условий. (Это часто просто означает, что некоторое логическое утверждение истинно.) Утверждение еНессэ (или конечное условие) задает некоторое условие, которое предполагается истинным по завершению данной процедуры в предположении, что для этой процедуры было удовлетворено началыюе условие.
Рассмотрим, например, процедуру загс(), ас1г$ — ргос (соебгеа1) ге$пгпв геа! % геЧп1геа сое1 ) 0 % ейес$в возвращает приближенное значение корня из с>оса апв: геа1 - соеГ,~'2.0 йш1:=1 жЫ1е > < Т с1о апсс апз-Яа»з«апв-соеГ)Д2.0"а»в) Н1 епс1 ге1пгп (апа) епс1 ас1гС Поскольку в процедуре имеется спецификация, мы можем игнорировать тело процедуры.
Обращение вида са11 у: - = зогг(х) будет иметь следующий смысл: «Если при вызове процедуры х больше О, то после выполнения процедуры у есть приближение квадратного корня из т». Отметим, что начальные и конечные условия позволяют нам не упоминать о значении у для случая, когда х не больше О. При анализе спецификации для уяснения смысла обращения к процедуре мы придерживаемся двух четких правил: 1.
После выполнения гсроцедуры можно считать, что конечное условие выполнено. 2. Можно ограничиться только теми свойствак>и, которые подразумевает конечное условие. Эти два пра,вила демонс>трирусот два преимущества, предоставляемых абстракцией через спецификацию. Первое из них состоит в том, что использующие данную процедуру программисты не обязаны знакомиться с ее телом. Следовательно, они освобождены от необходимости уяснения подробностей выполнения описанных в теле вычислений, устанавливая, что процедура действительно извлекает квадратный корень из аргумента.
Это является большим преимуществом при работе со сложными процедурами и даже с простыми, но использующими нс,знакомые алгоритмы. Второе правило уточняет, что мы па самом деле абстрагировались от тела процедуры, позволив себе не обращать внимания на несущественную информацию.
Именно это «забывание информации» и отличает абстракцию от декомпозиции. Анализируя тело процедуры здг1О, пользователи данной процедуры могут извлечь для себя большое количество информации, не следующее из конечного условия, например, что вдгг(4) возвратит результат 02. Однако в спецификации мы говорим, что подобная информация о возвращаемом результате игнорируется. Этим мы утверждаем, что процедура адг1О есть абстракция, представляющая собой набор всех вычислений, при котором определяется «приближение квадратного корня из х». 7.2.2 Виды абстракции в языках программирования Абстракции через параметризацин> и через спецификацию являются мощными средствами создания программ.
Они позволяют нам определить три различных вида абстракций: процедурнук> абстракцию, абстракцию данных и абстракпин> через итерацию. В общем случае каждая процедурная абстракция, абстракция через данные и абстракция через итерацию используют оба способа. Например, абстракпию вг>г~0 можно сравнить о операцией: она абстрагирует отдельное собьп ие или задачу. Мы будем ссылаться к абстракциям такого рода как к нроцсдурн»>м вбс>нракцилм. Отметим, что абстракция вдгГО включает в себя как абстракцию через параметризациго, так и абстракцию через спецификацшо.
Процедурная абстракция является мощным средством. Она позволяет нам расгпирить заданную некоторым языком программирования виртуальнук> машину новой операцией. Такой вид расширения наиболес полезен в тоъл случае, когда мы работаем с задачами, которые легко п1>едстг>вить в виде набора независимых функционал>.ных единиц. Однако часто оказывается более удобным добавить к виртуальной машине несколько объектов данных с новыми типами. Поведение объектов данных наиболее естественно представлять в терминах набора операций, применимых к данным объектам.
Такой набор включает в себя операции по созданию объектов, получению информации от них и, возможно, их модификации. Например, операции рив60 и рор() принадлежат к классу операций, имеющих смысл при работе со стеками, в то время как для работы с целыми числами используются обычные арифметические операции. Таким образоъг, абсгиракиия данны (или >нии данны и) состоит из набора обьектов и набора операций, характеризующих поведение этих объектов. В качестве примера рассмотрим мультимножества (>пп16эегэ). Мультимножества сходны с обычными множествами, за исключением того.
что элемент может входить в мульти- множества несколько раз. Операции для работы с подобными мультимножествами включают в себя ои> рации егпргу(), гпвегЯ, гйЫе0, г>итЬег о г () и и с(). Эти операции создают пустое мультиъиножество, удаляют и добавляют в него элементы, вычисляют, сколько раз данный элемент входит в мультимножество и сколько всего элементов содержится в мультимножестве. Данные операции могут быть реализованы в языке программирования через соответствующие процедуры.
Программисты, работающие с мультимпожествами, нс должны оеспокоитг.ся о том, каким об1>азом эти проггедурьг 1эеа.>гизоваьгы. Для них операции сггЧ>Гу0, ггпвег1(), гЬ',Ые0, нигпЬег ог'() и вгике~) являк>тся абстракциями> определяеъгьгъли функциональными спецификаторами вида: Т1к> а1ие оГ г1>е >тп>111эеГ, 1г>аегГ(э, е) 1в ег1па1 ъо а1яе(э) 1 (Размер мультимножества >пэегг,(в, е) равен а1хе(а) -~ 1) Рог а11 е С1>е пшпбег оГ гипсе е осспгв 1п 11>е пш!6всг сто 1в О. (Для всех е число вхождений е в пустое мультимножество стра равно 0.) Важно отметить, что каждый из этих операторов работает сразу с несколысими операциями. Мы не приводим независимые определения каждой операции, но скорее определяем их через взаимосвязи.
Этот акцент на взаимосвязях ълсжду операциями и делает абстракцию данных существенно отличной от набора процедур. Важность этого отличия еще будет обсуждаться. В дополнение к процедурным абстракциям и абстракцияъл данных мы рассмотрим также абстракиию через итерацию. Абстракция через итерацию дает возможность не рассматривать информацию, не имеющую прямого отношения к управляя>щему потоку или циклу. Типичная абстракция итерации позволяет пам обрабатывать все элементы мультипабора без накладывания каких-либо ограничений на последовательность обработки.
Далее мы покажем, как осуществлять декомпозицию программы на базе абстракции через итерацию. Акцент будет делаться на абстракции данных. Мы считаем, .что, хотя процедурные абстракции и абстракции через итерацию и играют существенную роль, организация процесса программирования начинается, как правило, с абстракции данных. При программировании на С получаются более соверпсенныс реализации абстрактных типов данных. Более того, прин.;секаи инструментальные средства системы программировании ОС 111с1Х мы можем автоматизировать сборку программ модульной структуры с помощью утилиты п1а1се. Заголовочный файл яСас1с.11 определяет интерфейс стека, файл яСас)с.с — реализацию. ф1Спс1еС' БТАСК Н фс1ейпе БТАСК Н фшс1пс1е <яссЬоо1 1т> увшс1пс1е <яСс11о.1т> Сурес1еГ 1пС ча1пе Суре: яСгпсС ягас1с я; Сурес1еС'яСгпсС яСас1с я яС,ас1с; вСас1с~ яСас1с сгеаСеД; Ьоо1 яСас1с 1я егпрСу(сопяС яСас1с.
яС); чоЫ ягас1с рпя11(яСас1с:~ вС, ча1пе Суре ча1); ча1пе Суре яСас1с рор(яСас1с* яС,); я1ге С вСас1с я1ге(сопяС яСас1св яС); чоЫ яСас1с с1еяСгоу(ягас1св я); чоЫ яСас1с рггпС(сопяС вСас1* яС, Г1БЕ~ жСсеге); уС=епс111' фшс1пс1е <яСс1111ь Ь > фшс1пс1е "яСас1с.11в епшп ( игах яСас1с я1ге — 100 ); яСгпсС яСас1с в ( ча1пе Суре сСаСа1птах ягас1с яСге); я1ге С Сор; С; яСас1с* яСас1с сгеаСе() ( яСас1с* я -- (всас1сс)пта11ос(в1геоГ(ясас1с)); в — >Сор — 0; геСпгп в; Ьоо1 вСас1с 1я еп11эСу(сопяС вСас1св я) геСпгп я->Гор -- П; ъоЫ я1ас1г рпяЬ1ягас1сэ в, та!пе Гуре ча1) ( я — >с1ага1я — >Го1ь-'+~ та1; ма!пе Гуре агам рор1я1асЫ я) гегпгп я — >г1ага~ — — я — >гор~; я1хе г ягас1г я1хе(сопМ я$ас)гв я) геСпгп я — >1ор; моЫ ягас1г г1еяггоу1я1ас1гэ я) 1гее (я); ~оЫ я1ас1г рпп11сопя$ я1ас1* я, ИЬЕ* 6!е) ( рагс('1', Й1е ): 1Г ~я — >гор!=- 0) 11зг1пгг ( й!е, ЯЯг1", я — >с1а1а~01)1 Гог 1Я1хе Г 1 - 1; 1 < Я вЂ” >гоР; ++1) 1рг1пг1( й1е, ", .%сГ, я — >с1вга~11); рпгс( ) Алгоритм сортировки стека определен в отдельных файлах яогГ.1г и яогг.с.
4~Нпг1еГ БОКТ Н ферейне ЯОКТ Н фшс1пс1е "яГас1гЬ Я чоЫ ягвс1г яогг(ягас1г* я); фепг11Г В реализации сортировки используются несколько вспомогательных функций, невидимых извне. ~шс1пг1е "яог1.1г" Как уже отмечалось, Ма1еНс позволяет существенно сократить затраты на сборку проекта (сели то.))ько это не тотальная пересборка). СС асс СГ1.ЛСЯ вЂ” — с — рес1ап11с — %а11 — э1г) с99 ЬР =-= асс ЬЛГЬАСЯ == ОВ,) == э1ас)чо эог$.о п)а1п.о РКОСХАМЕ -- 1аЬ26 .ЯЕГГ1ХЕЯ: .с .о а11: $(РКОСХЛМЕ) с1еап: пп — 1 *.о 8(РКОСХЛМЕ) 8 ( РКО СХЛМЕ): 8 (ОВ1) $(Щ 8(ЬЛГ1.ЛС8) 8(ОВЗ) — о 8(РКОСХЛМГ) с.о 8(СС) 8(СГЬАСЯ) 8< ша1п.с: вс)г1.Ь эдас~.Ь зов .
с: аог$ . Ь э1ас1~ . Ь э1ас1с.с, эдас)г.Ь 7.3 Типовые абстракции 7.3.1 Типизация языка Типизация языка программирования -- это наделение языка той или иной системой типов ~46~. Существуют бестиповые языки, наиболее известным из которых среди специалистов является Ь)эр в связи с тем, что он основан на бестиповом Л-исчислении, получившем блестящую математическук) интерпретацин) Д. Скотта.
Бсстиповыми являются и предшественники Си языки системного программирования В и ВСР1. язык ВЬ1ВЯ, а также весьма интересный язык Сетл. В бестиповых ~зыках все обьекты одного и того же типа, например машинные слова, адреса или строки ~21~. В обычных многотиповых фон-Неймановских языках программирования вопрос типизации тесно связан с контролем типов. Ведущие специалисты по языкам программирования Ч, Хоор, Б. Лисков и друтие высказываются в пользу строгой типизации языка, под которой понимается статическая фиксация во время компиляции типа каждой переменной, массива, компоненты записи, выражения, функции и параметра, причем тип каждой переменной должен быть явно описан в программе и не должен меняться во время вы- !!(>Лнения программь!. 7.3.2 Контроль типов Деятельность по опречелению тинов переменных, выражений и т, д, в программе часто называют конгаролем типов, Контроль, проводимый во время компиляции, называют статическим, а в период выполнения динамическим [46].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
