Мобильные персональные компьютеры: виды, варианты исполнения, их сравнение

Заметим, что по причине  наличия возможности получить значение указателя на любую статически объявленную  переменную, работа с указателями  на статические и динамические переменные производится полностью единообразно. Единообразная работа с массивами  и указателями естественным образом  позволяет создавать и использовать динамические массивы.

Как видно, с динамической памятью в языках Си/Си++ работать можно очень эффективно, но программирование является опасным.

Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные  динамические структуры памяти - списки, деревья, графы и т.д. (Особенности  указателей в языках Си/Си++ позволяют, вообще говоря, строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных.) Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип T, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная var типа T (или переменная типа указателя на T в случае полностью динамического создания структуры). Имя этой переменной при выполнении программы используется как имя "корня" динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной var (или первой динамической переменной, указатель на которую содержится в переменной var). Понятно, что этот подход позволяет создать динамическую структуру с любой топологией.

Наиболее простой динамической структурой является однонаправленный список. Для создания списка определяется структурный тип T, у которого имеется  одно поле next, объявленное как указатель на T. Другие поля структуры содержат информацию, характеризующую элемент списка. При образовании первого элемента ("корня") списка в поле next заносится пустой указатель (nil или NULL). При дальнейшем построении списка это значение будет присутствовать в последнем элементе списка

Над списком, построенном в такой манере, можно выполнять операции поиска элемента, удаления элемента и занесение нового элемента в начало, конец или середину списка. Понятно, что все эти операции будут выполняться путем манипуляций над содержимым поля next существующих элементов списка. Для оптимизации операций над списком иногда создают вспомогательную переменную-структуру (заголовок списка), состоящую из двух полей - указателей на первый и последний элементы списка. Для этих же целей создают двунаправленные списки, элементы которых, помимо поля next, включают поле previous, содержащее указатель на предыдущий элемент списка и, возможно, ссылки на заголовок списка.

Абстрактные (определяемые пользователями) типы данных

На самом деле, оба термина, употребленные в названии раздела, плохо отражают суть соответствующего понятия. Термин "абстрактные типы" плох тем, что реально ничего абстрактного в этой категории типов нет. Термин "определяемые пользователями типы" не точно отражает специфику, поскольку  все типы, обсуждавшиеся выше, кроме  встроенных в языки программирования, так или иначе определяются пользователями. Тем не менее, в силу привычки, мы будем использовать в этом разделе словосочетание "абстрактные типы данных" (АТД).

Не обращая больше внимания на ущербность терминологии, займемся содержанием понятия АТД. Как  мы видели, наличие перечисляемых, уточняемых и конструируемых типов данных в  сочетании со средствами выделения  динамической памяти позволяет конструировать и использовать структуры данных, достаточные для создания произвольно  сложных программ. Ограниченность этих средств состоит в том, что  при определении типов и создании структур невозможно зафиксировать  правила их использования. Например, если определен структурный тип  с полями salary, commissions и total в предположении, что для любой переменной этого типа поле total всегда будет содержать общую сумму выплат, то ничто не мешает по ошибке нарушить это условие (с точки зрения компилятора никакой ошибки нет) и получить неверные результаты работы программы.

Основной идеей АТД  является то, что при его определении  специфицируется не только структура  значений типа, но и набор допустимых операций над переменными и значениями этого типа. В наиболее сильном  случае доступ к внутренней структуре  типа доступен только через его операции. В число операций обязаны входить  один или несколько конструкторов  значений типа.

Имеется много разновидностей языков с АТД, языковые средства которых  весьма различаются. Кроме того, к  этому семейству языков примыкают  языки объектно-ориентированного программирования. По поводу них одни авторы (к числу  которых относится и автор  этой книги) полагают, что для них  термин "язык объектно-ориентированного программирования" является модной заменой старого термина "язык с АТД". Другие находят между  этими языковыми семействами  много тонких отличий, часть которых  считают серьезными. Мы не будем  глубоко анализировать эти дискуссии, а обсудим некоторые базовые  концепции, общие для обоих семейств.

Представление типа

При программировании с использованием АТД возможны три подхода (они  могут быть смешаны): (1) перед началом  написания основной программы полностью  определить все требуемые типы данных; (2) определить только те характеристики АТД, которые требуются для написания программы и проверки ее синтаксической корректности; (3) воспользоваться готовыми библиотечными определениями. В каждом из этих подходов имеются свои достоинства и недостатки, но их объединяет то, что при написании программы известны по меньшей мере внешние характеристики всех типов данных. В некотором смысле это означает, что расширен язык программирования.

Подобная внешняя характеристика АТД называется его представлением или спецификацией. Представление  включает имя АТД и набор спецификаций доступных пользователю операций со значениями этого типа. Со своей  стороны, спецификация операции состоит  из имени и типов параметров (в  последнее время такие спецификации принято называть сигнатурами операций). Для однозначного определения компилятором того, какая реально функция или  процедура должна быть вызвана при  обращении к операции, обычно требуют, чтобы сигнатуры всех операций всех АТД, используемых в программе, были различны (мы еще вернемся к этой теме ниже при обсуждении возможностей полиморфизма).

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

Иногда исходя из соображений эффективности допускается прямой доступ к некоторым переменным состояния значений типа (путем использования обычных предопределенных операций чтения и записи). В этом случае переменные состояния, доступные в таком режиме, также специфицируются во внешнем представлении типа.

Реализация типа

Реализация типа представляет собой многовходовой программный  модуль, точки входа которого соответствуют  набору операций реализуемого типа. Естественно, должно иметься полное соответствие реализации типа его спецификации. Набор статических переменных (в  смысле языков Си/Си++) этого модуля образует структуру данных, используемую для представления значений типа. Такой же структурой обладает любая переменная данного абстрактного типа.

Иногда для целей реализации типа бывает полезно иметь в составе  его операций такие, которые недоступны для внешнего использования и  носят служебный характер. Такие  функции и/или процедуры специальным  образом помечаются в реализации типа (например, как приватные), и  их сигнатуры не включаются во внешнюю  спецификацию типа. Переменные состояния, которые должны быть прямо доступны для внешнего использования, также  помечаются специальным образом. 

Инкапсуляция

Существуют разные точки  зрения относительно того, для чего наиболее полезно применять абстрактные  типы данных. Многие считают, например, что основной смысл этого подхода  состоит в развитии методов модульного структурного программирования. Это, конечно, верно, но с точки зрения автора наибольшее преимущество подхода абстрактных  типов данных состоит в принципиальном разделении спецификации и реализации типа. Для правильного написания (а иногда и отладки) программы  достаточно иметь набор спецификаций требуемых типов. Для каждой спецификации, вообще говоря, может существовать несколько реализаций, и при их корректном создании эти реализации могут быть взаимозаменяемыми.

В строго типизированных языках с абстрактными типами данных спецификация типа скрывает его реализацию. Внешнее  представление типа инкапсулирует  особенности его структурной  и операционной реализации. До сих  пор продолжаются споры о том, что является идеальной инкапсуляцией  типа. В частности, многие полагают, что разрешение прямого доступа  к переменным состояния нарушает принципы инкапсуляции. По всей видимости, это неверно. Если все возможные  операции со значениями типа строго специфицированы  в его внешнем представлении, то в любом случае могут допускаться  различные реализации типа. Но, естественно, чем более высоким уровнем  обладает спецификация, тем больше свобода при выборе реализации.

Наследование типов

Под наследованием типов  понимается возможность дисциплинированного  создания новых типов на основе уже  определенных. Мы подчеркиваем слово "дисциплинированного", потому что, конечно, можно определять новые типы и произвольным образом, используя в качестве заготовок  куски существующих программных  текстов.

В отличие от этого, при  использовании механизма наследования типов требуется, чтобы спецификация нового типа (подтипа) полностью включала спецификацию наследуемого типа (супертипа). Но эта спецификация может быть расширена сигнатурами дополнительных операций, вводимых для подтипа. Соответственно в реализации подтипа должны присутствовать коды функций и/или процедур дополнительных операций, а структуры данных, функции и процедуры супертипа могут быть переопределены.

В разных языках с абстрактными типами данных допускается либо только простое наследование типов (для  каждого подтипа существует только один супертип), либо множественное наследование (для подтипа может существовать несколько супертипов). Множественное наследование порождает проблему согласования сигнатур операций супертипов. Общего решения этой проблемы не существует, в каждом из языков с множественным наследованием используются свои приемы. Мы не будем более подробно останавливаться на этих деталях.

Имеются два основных соображения  по поводу пользы механизма наследования типов. Во-первых, этот механизм обеспечивает возможность контролируемого и  дисциплинированного повторного использования  программных кодов. Во-вторых (и может  быть, это даже более важно), во многих языках используется так называемая семантика включения: считается, что  значение любого подтипа одновременно является значением любого своего супертипа. Семантика включения хорошо соответствует смыслу механизма наследования как средства уточненной классификации объектов предметной области.

Естественно, что в подтипах типа "Человек" появляются дополнительные операции, например, "размер пособия" для безработных и "должностной  оклад" для служащих. Можно предположить, что операция "знание языков", вводимая для типа "Служащий", по-разному переопределяется для его подтипов "Программист" и "Преподаватель".

С другой стороны, очевидно, что из соображений здравого смысла и безработные, и служащие обладают общими свойствами, характерными для  типа "Человек", а программисты и преподаватели относятся к  категории "Служащие". Эти соображения  приводят нас к иерархии включения  значений этих типов данных. Это  означает, что, в частности, должна иметься  возможность единообразной работы со значениями типа "Человек" независимо от того, сформировано ли соответствующее значение конструктором этого типа или же конструктором любого из его подтипов. Конечно, при этом можно использовать только те операции, которые специфицированы во внешнем представлении типа "Человек".

Поскольку в подтипе может  быть переопределена реализация операций, специфицированных в супертипе, то во время компиляции программы иногда невозможно установить, какую функцию или процедуру требуется вызывать при выполнении операции над значением типа. По этой причине в системах программирования, поддерживающих развитый механизм наследования, для обеспечения корректного вызова функций и/или процедур, которые реализуют операции типа, приходится применять так называемый метод позднего связывания (late binding).

Суть этого метода состоит  в том, что во время выполнения программы при каждом значении (или  объекте в языках объектно-ориентированного программирования) содержится информация о типе, с помощью конструктора которого было создано это значение. На основе этой информации на стадии выполнения удается обнаружить требуемые реализации операций. Понятно, что применение метода позднего связывания вносит в процесс выполнения программы существенный элемент интерпретации, что приводит к снижению эффективности. Поэтому, по мере возможности, стремятся снизить накладные расходы даже за счет понижения универсальности механизма наследования. Примером может служить аппарат виртуальных функций в языке Си++.

Разновидности полиморфизма

Полиморфизм в языках программирования - это очень широкое и собирательное  понятие, включающее разные аспекты. Мы остановимся только на полиморфизме операций типов в контексте приведенного выше материала. Можно выделить две  разновидности полиморфных операций: (1) одноименные операции одного или  нескольких типов, различающиеся сигнатурами, и (2) операции с общей сигнатурой, определяемые и переопределяемые в  иерархии наследования типов.