Эмуляция объектной технологии в не ОО-средах

Уровни языковой поддержки

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

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

Общее замечание по ОО-эмуляции. В своей основе объектная технология - это "программирование с абстрактными типами данных". Даже на функциональном уровне можно применять рудиментарную форму этой идеи, определив набор строгих методологических правил, требующих вызова подпрограмм для доступа к данным. Предполагается, что начинать надо с ОО-построения, определяющего АТД и его компоненты. Затем пишется набор подпрограмм, представляющих эти компоненты - put, remove, item, empty, как в нашем стандартном примере стека. Далее требуется, чтобы все клиентские модули использовали только эти подпрограммы. При отсутствии языковой поддержки, но при условии, что все в команде подчиняются навязанным правилам, это можно рассматривать как начало объектного подхода. Назовем эту технику дисциплинарным подходом.

ОО-программирование на языке Pascal?

Язык Pascal, введенный в 1970г. Никласом Виртом, много лет являлся доминирующим языком начального обучения программированию на факультетах информатики и оказал большое влияние на построение последующих языков. Pascal - это функциональный язык в только что определенном смысле.

Собственно Pascal

Многое ли из ОО-подхода можно реализовать в Pascal?

К сожалению, немногое. Структура программы в Pascal основана на совершенно другой парадигме. Программа на языке Pascal состоит из последовательности описательных разделов, следующих в неизменном порядке: метки, константы, типы, переменные, подпрограммы (процедуры и функции) и раздела выполняемых инструкции. Сами подпрограммы рекурсивно имеют ту же структуру.

Это простое правило облегчает однопроходную компиляцию. Но любая попытка использования ОО-техники обречена. Рассмотрим, что нужно для реализации ADT, например, стека, представленного массивом: несколько констант, задающих размер массива, тип, описывающий элементы стека, несколько переменных, таких как указатель на вершину стека и несколько подпрограмм, задающих операции АТД. В Pascal эти элементы будут разбросаны по разделам: все константы вместе, все типы вместе и т. д.

Результирующая программная структура противоположна ОО-проектированию. Использование Pascal противоречит принципу Лингвистических Модульных Единиц: любая политика модульности должна поддерживаться доступными конструкциями языка.

Итак, если рассматривать официальный стандарт Pascal, то сделать можно немногое, не считая использования дисциплинарного подхода.

Модульные расширения языка Pascal

За пределами стандарта Pascal многие коммерчески доступные версии снимают ограничения на порядок объявлений и включают поддержку модульности, включая независимую компиляцию. Такие модули могут содержать константы, типы и подпрограммы. Эти языки более гибкие и сильные, чем стандартный Pascal, сохраняют имя Pascal. Они не стандартизированы, и в действительности больше напоминают инкапсулирующие языки, такие как Modula-2 или Ada, обсуждаемые в предыдущей лекции.

ОО-расширения языка Pascal

Некоторые компании предложили ОО-расширения языка Pascal, широко известные как "Object Pascal". Две версии особенно значимы:

Наше обсуждение не затрагивает эти языки, так как реально их связь с Pascal проявляется только в имени, стиле синтаксиса и статически типизированном подходе. В частности, Borland Pascal - это ОО-язык с обработкой исключений. Он не поддерживает механизмов универсальности, утверждений, сборки мусора и множественного наследования.

Fortran

FORTRAN: Предварительный отчет, IBM, Ноябрь, 1954

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

Немного контекста

Язык Fortran был первоначально создан как инструмент для программирования на IBM 704 командой IBM во главе с Джоном Бэкусом (позже он принимал активное участие в описании языка Algol). Первая версия языка появилась в 1957 году. Затем последовал Fortran II, введший подпрограммы. Fortran IV появился в 1966 году и был стандартизирован ANSI (Fortran III не получил широкого распространения). Дальнейший процесс развития привел к Fortran 77, одобренному в 1978 году, имевшему лучшие управляющие структуры и приятные упрощения. После длительного процесса пересмотра появился Fortran 90 и Fortran 95, они были по-разному приняты и до сих пор не заменили своих предшественников.

Для большинства специалистов в компьютерных науках Fortran устарел. Однако можно найти немало программистов Fortran еще с тех времен и тех, в чьих дипломах стоит "физик-теоретик", "прикладной математик", "инженер-механик", или даже "специалист по ценным бумагам", использующих Fortran повседневно и не только в старых проектах, но и в новых разработках.

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

Техника COMMON

Fortran система состоит из главной программы и ряда подпрограмм. Как обеспечить схожесть с абстракцией данных?

Возможная техника состоит в том, чтобы представить данные в так называемом общем блоке COMMON, а экспортируемые компоненты (например, put и т. д. для стеков) реализовать в виде независимых подпрограмм. Блок COMMON - это механизм Fortran, предоставляющий доступ к данным любой подпрограмме, желающей их получить. Вот набросок подпрограммы put для стека действительных чисел:

SUBROUTINE RPUT (X)
    REAL X
C
C    ВТАЛКИВАНИЕ X НА ВЕРШИНУ СТЕКА
C
    COMMON /STREP/ TOP, STACK (2000)
    INTEGER TOP
    REAL STACK
C    
    TOP = TOP + 1
    STACK (TOP) = X
    RETURN
    END

Эта версия не управляет переполнением (будет исправлено в следующей версии). Функция, возвращающая элемент вершины:

INTEGER FUNCTION RITEM
C
C     ВОЗВРАЩЕНИЕ ВЕРШИНЫ СТЕКА
C
    COMMON /STREP/ TOP, STACK (2000)
    INTEGER TOP
    REAL STACK
    RITEM = STACK (TOP)
    RETURN
    END

Здесь также необходимо было бы проверять стек на пустоту. Подпрограммы REMOVE и другие строятся по тому же образцу. Имя общего блока - STREP - объединяет различные подпрограммы, дающие доступ к одним и тем же данным.

Ограничения очевидны: данная реализация описывает один абстрактный объект (один отдельный стек), а не абстрактный тип данных, из которого во время выполнения можно создать множество экземпляров. Мир Fortran статичен: необходимо указывать размеры всех массивов (в примере 2000 - произвольно выбранное число). Поскольку отсутствует универсальность, то в принципе, придется объявлять новый набор подпрограмм для каждого типа элементов стека. Отсюда имена RPUT и RITEM, где R означает Real. Можно справиться с этими проблемами, но не без значительных усилий.

Техника подпрограммы с множественным входом

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

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

Это расширение, введенное, возможно, для других целей, можно использовать во благо ОО-подхода. Клиентские подпрограммы могут вызывать точки входа, как если бы они были автономными подпрограммами, и разные входы могут иметь разные аргументы. Вызов входа начинает выполнение подпрограммы с этой точки. Все входы разделяют хранимые данные подпрограммы, появляющиеся с директивой SAVE и сохраняемые от одной активизации подпрограммы к другой. Понятно, куда мы клоним: эту технику можно использовать для определения модуля, инкапсулирующего абстрактный объект, почти как в инкапсулирующем языке. Здесь модуль моделируется подпрограммой, структура данных - набором объявлений с директивой SAVE, и каждый компонент соответствующего класса в ОО-языке - входом, заканчивающимся инструкцией RETURN:

ENTRY (arguments)
... Инструкции ...
RETURN

В отличие от предыдущего решения, основанного на COMMON, теперь все необходимое сосредоточено в единой синтаксической единице. В таблице 34.1 дан пример реализации стека действительных величин. Вызовы клиента выглядят следующим образом:

LOGICAL OK
    REAL X
C
    OK = MAKE ()
    OK = PUT (4.5)
    OK = PUT (-7.88)
    X = ITEM ()
    OK = REMOVE ()
    IF (EMPTY ()) A = B

Взглянув на этот текст, можно почти поверить, что это использование класса, или, по крайней мере, объекта, через его абстрактный, официально определенный интерфейс!

C    --РЕАЛИЗАЦИЯ
C    --АБСТРАКТНЫЙ СТЕК ЧИСЕЛ
C
    INTEGER FUNCTION RSTACK ()
    PARAMETER (SIZE=1000)
C
C        --ПРЕДСТАВЛЕНИЕ
C
    REAL IMPL (SIZE)
    INTEGER LAST
    SAVE IMPL, LAST
C
C        --ВХОД С ОБЪЯВЛЕНИЯМИ
C
    LOGICAL MAKE
    LOGICAL PUT
    LOGICAL REMOVE
    REAL ITEM
    LOGICAL EMPTY
C
    REAL X
C
C        -- СОЗДАНИЕ СТЕКА
C
        ENTRY MAKE ()
            MAKE = .TRUE.
            LAST = 0
        RETURN
C
C    -- ДОБАВЛЕНИЕ ЭЛЕМЕНТА
C
        ENTRY PUT (X)
        IF (LAST .LT. SIZE) THEN
                PUT = .TRUE.
                LAST = LAST + 1
                IMPL (LAST) = X
        ELSE
            PUT = .FALSE.
        END IF
        RETURN

C            --УДАЛЕНИЕ ВЕРШИНЫ
C
        ENTRY REMOVE (X)
            IF (LAST .NE. 0) THEN
                REMOVE = .TRUE.
                LAST = LAST - 1
            ELSE
                REMOVE = .FALSE.
            END IF
        RETURN
C
C            --ЭЛЕМЕНТ ВЕРШИНЫ
C
        ENTRY ITEM ()
            IF (LAST .NE. 0) THEN
                ITEM = IMPL (LAST)
            ELSE
                CALL ERROR
    *        ('ITEM: EMPTY STACK')
            END IF
        RETURN
C
C            -- ПУСТ ЛИ СТЕК?
C
        ENTRY EMPTY ()
            EMPTY = (LAST .EQ. 0)
        RETURN
C
END

Этот стиль программирования может успешно применяться для эмуляции инкапсуляции Ada или Modula-2 в контекстах, где нет другого выбора, кроме использования Fortran. Конечно, он страдает от жестких ограничений:

ОО-программирование и язык C

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

Немного контекста

Язык C создавался в ATT's Bell Laboratories как машинонезависимый язык для написания операционных систем. Первая версия ОС Unix была написана на языке ассемблера, но вскоре потребовалась ее переносимая версия. Для решения этой задачи в 1970 г. и был создан язык С. Он вырос из идей языка BCPL. Как и С, это язык высокого уровня (благодаря управляющим структурам, похожим на структуры в Algol или Pascal), машинно-ориентированный (из-за возможности манипулировать данными на самом низком уровне через адреса, указатели и байты) и переносимый (поскольку машинно-ориентированные концепции охватывают широкий круг типов компьютеров). Язык С появился вовремя. В конце 70-х операционная система Unix использовалась во многих университетах, и вместе с ней распространялся С. В 80-х гг. началась революция микрокомпьютеров, и С был готов служить ей как lingua franca (язык франков), поскольку был более масштабируемым, чем Basic, и более гибким, чем Pascal. Система Unix тоже была коммерчески успешна, и с ней р ядом шел С. Через несколько лет он стал доминирующим языком в больших и самых активных сегментах компьютерной индустрии.

Все, кто интересуется развитием языков программирования, и даже те, кто не очень обращает внимание на сам язык, должны быть признательны языку С по крайней мере по двум причинам.

Стандарт ANSI для С впервые был опубликован в 1990 году. Более ранняя версия языка известна как KR (по инициалам авторов первой книги по С - Кернигана и Ритчи). Со временем противоречие между двумя взглядами на С - как на язык программирования высокого уровня и переносимый язык ассемблера - стало более явным. Эволюция стандарта сделала язык более типизированным и, следовательно, менее удобным для использования в качестве целевого кода компилятора. Было даже объявлено, что следующие версии будут иметь понятие класса, сглаживая отличие от C++ и Java.

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

Основные положения

Дисциплинарный подход применим к языку С, как и к любому другому языку. За его пределами для реализации модульности можно использовать понятие файла. Файл - это понятие языка С, балансирующее на границе между языком и операционной системой. Файл - единица компиляции, он может содержать функции и данные. Некоторые функции могут быть скрытыми от других файлов, другие - общедоступны. Это прямой путь к инкапсуляции: файл может содержать все элементы, относящиеся к реализации одного или более абстрактных объектов, или абстрактного типа данных. Благодаря понятию файла, С достигает уровня инкапсулирующего языка, как Ada или Modula-2. В сравнении с Ada здесь нет универсальности и отличия между интерфейсом и и реализацией.

Обычная техника программирования на С не расположена к ОО-принципам. Большинство программ С используют "файлы заголовков", описывающих разделяемые данные. Любой файл, нуждающийся в данных, получает доступ к ним через директиву " include " (управляемую встроенным препроцессором С):

#include <header.h>

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

Эмуляция объектов

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

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

Например, структурный тип REAL_STACK можно объявить так:

typedef struct
{
/* Экспортируемые компоненты */
void (*remove) ();
void (*put) ();
float (*item) ();
BOOL (*empty) ();
/* Закрытые компоненты (реализация) */
int count;
float representation [MAXSIZE];
}
REAL_STACK;

В структурном типе REAL_STACK два последних компонента - переменная и массив, остальные - ссылки на функции. В данном тексте комментарии предупреждают об экспортируемых и закрытых компонентах эмулируемого класса, но на уровне языка клиентам доступно все.

Каждый экземпляр типа должен инициализироваться так, чтобы поля ссылок указывали на соответствующие функции. Например, если my_stack является переменной этого типа, а C_remove - функция, реализующая выталкивание из стека, то можно присвоить полю remove объекта my_stack ссылку на эту функцию таким образом:

my_stack.remove = C_remove

В эмулируемом классе remove не имеет необходимого для нее аргумента. Для доступа к соответствующему стеку следует объявить функцию C_remove так:

C_remove (s)
REAL_STACK s;
    {
... Реализация операции remove ...
    }

Тогда клиент сможет применить remove к стеку my_stack:

my_stack.remove (my_stack)

В общем случае, подпрограмма rout, имеющая n аргументов в эмулируемом классе, порождает функцию C_rout с n+1 аргументами. Вызов ОО-подпрограммы:

x.rout (arg1, arg2, ..., argn)

эмулируется как:

x.C_rout (x, arg1, arg2, ..., argn)

Эмулирующие классы

Описанная техника будет работать в определенных пределах. Ее даже можно расширить для эмуляции наследования.

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

Для снижения потерь заметим, что подпрограммы одинаковы для всех экземпляров класса. Поэтому для каждого класса можно ввести структуру данных периода выполнения, дескриптор класса, содержащий ссылки на подпрограммы. Его можно реализовать как связный список или массив. Требования к пространству значительно уменьшаются: вместо n*m указателей можно иметь их n+m, где n - число подпрограмм, а m - число объектов, как показано на рис. 16.2.

Это приводит к незначительным временным потерям, но экономия пространства и простота стоят этого.

В этой технике нет секрета. Именно она сделала С полезным в качестве средства реализации для компиляторов ОО-языков, начиная с Objective-C и C++ в начале 80-х. Способность использовать указатели функций, в сочетании с идеей группирования этих указателей в дескриптор класса, разделяемый произвольным числом экземпляров, служит первым шагом к реализации ОО-техники.

Конечно, это только первый шаг, и нужно еще найти способы реализации наследования (особенно непросто множественное наследование), универсальности, исключений, утверждений и динамического связывания. Объяснения потребовали бы отдельной книги. Отметим лишь одно важное свойство, выводимое из всего, что мы видели до сих пор. Реализация динамического связывания требует доступа к типу каждого объекта во время выполнения для нахождения нужного варианта компонента f в динамически связываемом вызове x.f (...) (написанном здесь в ОО-нотации). Другими словами: в дополнение к официальным полям объекту необходимо дополнительное внутреннее поле, порождаемое компилятором и указывающее на тип объекта. Описанный подход показывает возможную реализацию такого поля - как указателя на дескриптор класса. По этой причине на рис. 16.2 для такого поля используется ярлык type.

OO C: оценка

Обсуждение показало, что в С есть технические способы введения ОО-идей. Но это еще не значит, что программисты должны их использовать. Как и в случае с языком Fortran, эмуляция - это некоторое насилие над языком. Сила языка С - в его доступности как "структурного языка ассемблера" (последователя BCPL и PL/360, созданного Виртом), переносимого, разумно простого и эффективно интерпретируемого. Его базисные понятия далеки от ОО-проектирования.

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

Библиографические замечания

Способы написания пакетов в Fortran, основанные на принципах абстракции данных, описаны в [M1982a]. Они используют подпрограммы, разделяющие блоки COMMON, а не подпрограммы с множественным входом, и идут дальше в реализации ОО-концепций, чем способы, описываемые в данной лекции. Это становится возможным благодаря использованию специфических библиотечных механизмов, эквивалентных динамически размещаемым экземплярам классов. Однако такие механизмы требуют значительных вложений и должны переноситься на каждый тип платформы.

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

[Cox 1990] содержит обсуждение технических приемов C для реализации ОО-концепций.

Ссылки на историю классических языков программирования даны в трудах конференции [Wexelblat 1981], см. также [Knuth 1980].

Упражнения

У16.1 Графические объекты (для программистов на Fortran)

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

У16.2 Универсальность (для программистов на C)

Как бы Вы преобразовали на С эмуляцию класса "real stack" в эмуляцию с родовыми параметрами, адаптируемую к стекам любого типа G, а не просто float?

У16.3 ОО-программирование на C (семестровый проект)

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

Подойдите к задаче через три последовательные уточнения: