Наследование: откат в интерактивных системах

Многоуровневый откат и повтор: undo и redo

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

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

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

Практические проблемы

Хотя при разумных усилиях механизм undo-redo может быть встроен в любую хорошо написанную ОО-систему, лучше всего с самого начала планировать его использование. На архитектуре ПО это скажется введением класса command, что может и не придти в голову, если не думать об откате при проектировании системы.

Практичный механизм undo-redo требует учета нескольких требований. Это свойство следует включить в интерфейс пользователя. Для начала можно полагать, что множество доступных операций обогащено двумя новыми командами: Undo и Redo. (Для них может быть введена соответствующая комбинация горячих клавиш, например control-U и control-R.) Команда Undo отменяет эффект последней еще не отмененной команды; Redo повторно выполняет команду, отмененную при откате. Следует определить соглашения для попыток отката на большее число шагов, чем их было сделано первоначально, при попытках повтора, когда не было отката, - такие запросы можно игнорировать или выдавать предупреждающее сообщение. (Таков возможный взгляд на интерфейс пользователя, поддерживающий undo-redo. В конце лекции мы увидим, что возможен лучший вариант интерфейса.)

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

Наконец, можно попытаться предложить общую схему "Undo, Skip, Redo", позволяющую после нескольких операций Undo пропустить некоторые команды перед включением Redo. Интерфейс пользователя, показанный в конце этой лекции, поддерживает такое расширение, но возникают концептуальные проблемы: после пропуска некоторых команд может оказаться невозможным выполнить следующую команду. Рассмотрим тривиальный пример текстового редактора и сессию некоторого пользователя с набранной одной строкой текста. Предположим, пользователь выполнил две команды:

(1) Добавить строку в конец текста.
(2) Удалить вторую строку.

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

Требования к решению

Механизм undo-redo, который мы намереваемся обеспечить, должен удовлетворять следующим свойствам:

Первое требование следует из того, что ничего проблемно-специфического в откатах и повторах нет. Только для облегчения обсуждения мы будем использовать в качестве примера знакомый каждому инструмент - текстовый редактор, (подобный Notepad или Vi), позволяющий пользователям вводить тексты и выполнять такие команды, как: INSERT_LINE, DELETE_LINE, GLOBAL_REPLACEMENT (одного слова в тексте другим) и другие. Но это только пример, и ни одна из концепций, обсуждаемых ниже, не является характерной только для текстовых редакторов.

Второе требование означает, что Undo и Redo имеют особый статус и не могут рассматриваться подобно любым другим командам интерактивной системы. Будь Undo обычной командой, ее структура требовала бы разбора случаев в форме:

If "Последняя команда была INSERT_LINE" then
    "Undo эффект INSERT_LINE"
elseif "Последняя команда была DELETE_LINE" then
    "Undo эффект DELETE_LINE"
и т.д.

Мы знаем (см. лекцию 3 курса "Основы объектно-ориентированного программирования"), как плохи такие структуры, противоречащие принципу Единственного Выбора и затрудняющие расширяемость системы. Пришлось бы изменять программный текст при всяком добавлении новой команды. Хуже того, код каждой ветви отражал бы код соответствующей команды, например, первая ветвь должна бы знать достаточно много о том, что делает команда INSERT_LINE. Это было бы свидетельством изъянов проекта.

Третье требование заставляет нас бережно относиться к памяти. Понятно, что механизм undo-redo требует хранения некоторой информации для каждой команды Undo: например, при выполнении DELETE_LINE, нет возможности выполнить откат, если перед выполнением команды не запомнить где-нибудь удаляемую строку и ее позицию в тексте. Но следует хранить только то, что логически необходимо.

Вследствие третьего требования исключается такое очевидное решение, как сохранение полного состояния системы перед выполнением каждой команды. Такое решение можно было бы тривиально написать, используя свойства STORABLE (см.лекцию 8 курса "Основы объектно-ориентированного программирования"), но оно было бы нереалистичным, так как просто пожирало бы память. Нужно придумать что-то более разумное.

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

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

Поиск абстракций

Ключом ОО-решения является поиск правильных абстракций. Здесь фундаментальное понятие буквально напрашивается.

Класс Command

Для нашей проблемы характерна фундаментальная абстракция данных COMMAND, представляющая любую операцию, отличающуюся от Undo и Redo. Выполнение операции это лишь один из многих компонентов, применимых к команде, - команду можно сохранить, тестировать или отменить. Так что нам понадобится класс и вот его первоначальная форма:

deferred class COMMAND feature
    execute is deferred end
    undo is deferred end
end

Класс COMMAND описывает абстрактное понятие команды и потому должен оставаться отложенным. Фактические типы команды будут представлены эффективными потомками этого класса, такими как:

class LINE_DELETION inherit
    COMMAND
feature
    deleted_line_index: INTEGER
    deleted_line: STRING
    set_deleted_line_index (n: INTEGER) is
            -- Устанавливает n номер следующей удаляемой строки
        do
            deleted_line_index := n
       end
    execute is
        -- Удаляет строку
        do
            "Удалить строку с номером deleted_line_index"
            "Записать текст удаляемой строки в deleted_line"
        end
    undo is
            -- Восстанавливает последнюю удаляемую строку
        do
            "Поместить deleted_line в позицию deleted_line_index"
        end
end

Аналогичный класс строится для каждой команды класса.

Что же представляют собой такие классы? Экземпляр LINE_DELETION, как будет показано ниже, является небольшим объектом, несущим всю необходимую информацию, связанную с выполнением команды: строку, подлежащую удалению, ( deleted_line ) и ее индекс в тексте ( deleted_line_index ). Эта информация необходима для выполнения команды undo, если она потребуется, или для повтора redo.

Атрибуты, такие как deleted_line и deleted_line_index, у каждой команды будут свои, но всегда они должны быть достаточными для поддержки локальных операций execute и undo. Объекты, концептуально описывающие разницу между двумя состояниями приложения: предшествующим и последующим за выполнением команды, дают возможность удовлетворить требование U3 из нашего списка - хранить только то, что строго необходимо.

Структура наследования классов выглядит следующим образом:

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

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

Основной интерактивный шаг

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

В любой интерактивной системе в модуле, ответственном за коммуникацию с пользователем, должен быть некоторый фрагмент следующего вида:

basic_interactive_step is
        -- Декодирование и выполнение одного запроса пользователя
    do
        "Определить, что пользователь хочет выполнить"
        "Выполнить это (если возможно)"
    end

В традиционных структурированных системах, подобных редактору, эти операции будут частью цикла - базисного цикла программы:

from start until quit_has_been_requested_and_confirmed loop
    basic_interactive_step
end

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

С учетом наших абстракций тело процедуры можно уточнить следующим образом:

"Получить последний запрос пользователя"
"Декодировать запрос"
if "Запрос является нормальной командой (не Undo)" then
    "Определить соответствующую команду в системе"
    "Выполнить команду"
elseif "Запрос это Undo" then
    if "Есть обратимая команда" then
        "Undo последней команды"
    elseif "Есть команда для повтора" then
        "Redo последней команды"
    end
else
    "Отчет об ошибочном запросе"
end

Здесь реализуется соглашение, что Undo примененное сразу после Undo, означает Redo. Запрос Undo или Redo игнорируется, если нет возможности отката или повтора. В простом текстовом редакторе с клавиатурным интерфейсом, процедура "Декодировать запрос" будет анализировать ввод пользователя, отыскивая такие коды, как control-I (для вставки строки, control-D для удаления) и другие. В графическом интерфейсе будет проверяться выбор команды меню, нажатие кнопки или соответствующих клавиш.

Сохранение последней команды

Располагая понятием объекта command, можно добавить специфику в выполняемые операции, введя атрибуты:

requested: COMMAND
--Команда, запрашиваемая пользователем

Атрибут задает последнюю команду, подлежащую выполнению, отмене или повтору. Это позволяет уточнить нашу схему следующим образом:

"Получить и декодировать последний запрос пользователя"
if "Запрос является нормальной командой (не Undo)" then
    "Создать подходящий объект command и присоединить его к requested"
        -- requested создан как экземпляр некоторого потомка
        -- класса COMMAND, такого как LINE_DELETION.
        -- (Эта инструкция детализируется ниже.)
    requested.execute; undoing_mode := False
elseif "Запрос является Undo" and requested /= Void then
    if undoing_mode then
        "Это Redo; детали оставляем читателям"
    else
        requested.undo; undoing_mode := True
    end
else
    "Ошибочный запрос: вывод предупреждения или игнорирование"
end

Информация, сохраняемая перед каждым выполнением команды, задается в экземпляре некоторого потомка COMMAND, такого как LINE_DELETION. Это означает, что, как и анонсировалось, решение удовлетворяет свойству U3 в списке требований: хранится не все состояние, а только разница между новым состоянием и предыдущим.

Ключом решения - и его уточнением в оставшейся части лекции - является полиморфизм и динамическое связывание. Атрибут requested полиморфен: объявленный как COMMAND он присоединяется к объектам одного из эффективных потомков, таким как LINE_INSERTION. Вызовы requested.execute и requested.undo осмыслены из-за динамического связывания: подключаемый компонент должен быть версией, определенной в соответствующем классе, выполняя, например, откат LINE_INSERTION, LINE_DELETION или команду любого другого типа, определенного тем объектом, к которому присоединен requested во время вызова.

Действия системы

Ни одна из рассмотренных частей структуры не зависела до сих пор от специфики приложения. Фактические операции приложения, основанные на структурах специфических объектов, например, структурах, представляющих текст в текстовом редакторе, - находятся где-то в другом месте. Как же осуществляется соединение?

Ответ основан на процедурах execute и undo классов command, которые должны вызывать компоненты, специфические для приложения. Например, процедура execute класса LINE_DELETION должна иметь доступ к классам, специфическим для текстового редактора, чтобы вызывать компоненты, вырабатывающие текст конкретной строки, задающие ее позицию в тексте.

Результатом является четкое разделение части системы, обеспечивающей взаимодействие с пользователем, и той ее части, которая зависит от специфики приложения. Вторая часть близка к концептуальной модели приложения - обработке текстов, CAD-CAM или чему-нибудь еще. Первая часть, особенно с учетом механизма истории действий пользователя, будет, как поясняется, широко использоваться в самых разных областях приложения.

Как создается объект command

После декодирования запроса система должна создать соответствующий объект command. Инструкцию, абстрактно появившуюся как "Создать подходящий объект command и присоединить его к requested ", можно теперь выразить более точно, используя инструкцию создания:

if "Запрос является LINE INSERTION" then
    create {LINE_INSERTION} requested.make (input_text, cursor_index)
elseif "Запрос является LINE DELETION" then
    create {LINE_DELETION} requested.make (current_line, line_index)
elseif
    ...

Используемая здесь форма инструкции создания create {SOME_TYPE} x создает объект типа SOME_TYPE и присоединяет его к x. Тип SOME_TYPE должен соответствовать типу объявления x. Это имеет место в данном случае, так как requested имеет тип COMMAND и все классы команд являются потомками COMMAND.

Если каждый тип команды использует уникальный числовой ( integer ) или символьный ( character ) код, то слегка упрощенная форма предыдущей записи может использовать inspect:

inspect
    request_code
when Line_insertion then
    create {LINE_INSERTION} requested.make (input_text, cursor_position)
и т.д.

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

Фактически можно получить более элегантное решение и полностью избавиться от разбора случаев. Мы увидим его в конце презентации.

Многоуровневый откат и повтор: UNDO-REDO

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

Список истории

Что не позволяло нам производить откат на большую глубину? Ответ очевиден - у нас был только один объект - последний созданный экземпляр COMMAND, доступный через requested.

Для обеспечения глубины отката достаточно заменить единственный объект requested списком, содержащим выполненные команды, - списком истории:

history: SOME_LIST [COMMAND]

Имя SOME_LIST не является именем настоящего класса, - в подлинном ОО стиле АТД мы исследуем, какие операции и свойства необходимы классу SOME_LIST, и позже вынесем заключение, какой же списочный класс из базовой библиотеки (Base library) следует использовать. Принципиальные операции, нужные нам непосредственно, хорошо известны из предыдущего обсуждения:

В отсутствие откатов курсор всегда (за исключением пустого списка) будет указывать на последний элемент и is_last будет истинным. Если же пользователь начнет выполнять откат, курсор начнет передвигаться назад по списку вплоть до before, если отменяются все выполненные команды. Когда же начинается повтор, то курсор перемещается вперед.

На рис. 3.3 курсор указывает на элемент, отличный от последнего. Это означает, что пользователь выполнял откат, возможно, перемежаемый повторами. Заметьте, число команд Undo всегда не меньше числа Redo (в состоянии на рисунке оно на два больше). Если в этом состоянии пользователь выберет обычную команду (ни Undo, ни Redo) соответствующий элемент будет вставлен непосредственно справа от курсора. Это означает, что остававшиеся справа в списке элементы будут потеряны, так для них не имеет смысла выполнение Redo. Здесь возникает та же ситуация, которая привела нас в начале лекции к введению понятия операции Skip (см. У3.4). Как следствие, в классе SOME_LIST понадобится еще один компонент - процедура remove_all_right, удаляющий все элементы справа от курсора.

Выполнение Undo возможно, если и только если курсор стоит на элементе с истинным значением on_item. Выполнение Redo возможно, если и только если был сделан откат, для которого еще не выполнена операция Redo, - это означает истинность выражения: (not empty) and (not is_last), которое будем называть запросом not_last.

Реализация Undo

Имея список истории, достаточно просто реализовать Undo:

if on_item then
    history.item.undo
    history.back
else
    message ("Нет команды для отката - undo")
end

И снова динамическое связывание играет основную роль. Список истории history является полиморфной структурой данных:

При передвижении курсора влево каждое успешное значение history.item может быть присоединено к объекту любого доступного типа command. Динамическое связывание гарантирует, что в каждом случае history.item.undo автоматически выберет нужную версию undo.

Реализация Redo

Реализация Redo аналогична:

if not_last then
        history.forth
        history.item.redo
    else
        message ("Нет команды для отката - undo")
    end

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

redo is
            -- Повтор команды, которую можно отменить,
            -- по умолчанию эквивалентно ее выполнению.
    do
        execute
    end

Наличие реализации превращает класс COMMAND в класс, определяющий поведение (см. лекцию 4 курса "Основы объектно-ориентированного программирования"). Он имеет отложенные процедуры execute и undo и эффективную процедуру redo. Большинство из потомков сохранят поведение по умолчанию redo, но некоторые зададут поведение, соответствующее специфике команды.

Выполнение обычных команд

Обычная команда по-прежнему идентифицируется ссылкой requested. Такую команду следует не только выполнить, но и добавить ее в список истории, предварительно удалив все элементы справа от курсора. В результате получим:

if not is_last then remove_all_right end
history.put (requested)
    -- Напомним, put вставляет элемент в конец списка,
    -- курсор указывает на новый элемент
requested.execute

Мы рассмотрели все основные элементы решения. В оставшейся части лекции обсудим некоторые аспекты реализации и извлечем из нашего примера методологические уроки.

Аспекты реализации

Давайте займемся деталями, что позволит получить лучшую из возможных реализаций.

Аргументы команды

Некоторым командам нужны аргументы. Например, команде LINE_INSERTION нужен текст вставляемой строки.

Простым решением является добавление атрибута и процедуры в класс COMMAND:

argument: ANY
set_argument (a: like argument) is
    do argument := a end

Тогда любой потомок - командный класс - сможет переопределить argument, задав для него подходящий тип. Чтобы справиться с множественными аргументами, достаточно выбрать массив или списочный тип. Такова была техника, принятая выше, при передаче аргументов процедуре создания объектов командных классов.

Эта техника подходит для всех простых приложений. Заметьте, библиотечный класс COMMAND в среде ISE использует другую технику, немного более сложную, но более гибкую: здесь нет атрибута argument, но процедура execute имеет аргумент в обычном для процедур смысле:

execute (command_argument: ANY) is ...

Причина в том, что в графических системах удобнее позволять различным экземплярам одного и того же командного типа разделять один и тот же аргумент. Удаляя атрибут, мы получаем возможность повторно использовать тот же командный объект во многих различных контекстах, избегая создания нового командного объекта всякий раз, когда пользователь запрашивает команду.

Небольшое усложнение связано с тем, что теперь элементы списка истории уже не являются экземплярами COMMAND - они теперь должны быть экземплярами класса COMMAND_INSTANCE с атрибутами:

command_type: COMMAND
argument: ANY

Для серьезных систем стоит пойти на усложнение ради выигрыша в памяти и времени. В этом варианте создается один объект на каждый тип команды, а не на каждую выполняемую команду. Эта техника рекомендуется для производственных систем. Необходимо лишь изменить некоторые детали в рассмотренном ранее классе (см. У3.4).

Предвычисленные командные объекты

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

inspect
    request_code
when Line_insertion then
    create {LINE_INSERTION} requested.make (...)
и т.д. (одна ветвь для каждого типа команды)

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

Мы создадим широко применимый образец проектирования, который может быть назван множество предвычисленных полиморфных экземпляров (precomputing a polymorphic instance set).

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

Хотя для этого возможны различные структуры, например списки, мы будем использовать массив ARRAY [COMMAND], позволяющий идентифицировать каждый тип команды целым в интервале 1 и до command_count - числом типов команд. Объявим:

commands: ARRAY [COMMAND]

и инициализируем его элементы так, чтобы i -й элемент ( 1 <= i <= n ) ссылался на экземпляр класса потомка COMMAND, соответствующего коду i ; например, создадим экземпляр LINE_DELETION, свяжем его с первым элементом массива, так что удаление строки будет иметь код 1.

Массив commands дает еще один пример мощи полиморфных структур данных. Его инициализация тривиальна:

create commands.make (1, command_count)
create {LINE_INSERTION} requested.make; commands.put (requested, 1)
create {STRING_REPLACE} requested.make; commands.put (requested, 2)
... И так для каждого типа команд ...

Заметьте, при этом подходе процедуры создания не должны иметь аргументов; если командный класс имеет атрибуты, то следует устанавливать их значения позднее в специально написанных процедурах, например li.make (input_text, cursor_position), где li типа LINE_INSERTION.

Теперь исчезла необходимость применения разбора случаев и ветвящихся инструкций if или inspect. Приведенная выше инициализация служит теперь точкой Единственного Выбора. Теперь реализацию абстрактной операции "Создать подходящий командный объект и присоединить его к requested " можно записать так:

requested := clone (commands @ code)

где code является кодом последней команды. Так как каждый тип команды имеет теперь код, соответствующий его индексу в массиве, то базисная операция интерфейса, ранее написанная в виде "Декодировать запрос", анализирует запрос пользователя и определяет соответствующий код.

В присваивании requested используется клон ( clone ) шаблона команды из массива, так что можно получать более одного экземпляра одной и той же команды в списке истории (как это показано в предыдущем примере, где в списке истории присутствовали два экземпляра LINE_DELETION ).

Если, однако, использовать предложенную технику, полностью отделяющую аргументы команды от командных объектов (так что список истории содержит экземпляры COMMAND_INSTANCE, а не COMMAND ), то тогда в получении клонов нет необходимости, и можно перейти к использованию ссылок на оригинальные объекты из массива:

requested:= commands @ code

В длительных сессиях такая техника может давать существенный выигрыш.

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

Для списка истории был задан абстрактный тип SOME_LIST, обладающий компонентами: put, empty, before, is_first, is_last, back, forth, item и remove_all_right. (Есть также on_item, выраженный в терминах empty и before, и not_last, выраженный в терминах empty и is_last.)

Большинство из списочных классов базовой библиотеки можно использовать для реализации SOME_LIST ; например, класс TWO_WAY_LIST или одного из потомков класса CIRCULAR_LIST. Для получения независимой версии рассмотрим специально подобранный класс BOUNDED_LIST. В отличие от ссылочной реализации списков, подобных TWO_WAY_LIST, этот класс основан на массиве, так что он хранит лишь ограниченное число команд в истории. Пусть remembered будет максимальным числом хранимых команд. Если используется в системе подобное свойство, то запомните (если не хотите получить гневное письмо от меня как от пользователя вашей системы): этот максимум должен задаваться пользователем либо во время сессии, либо в профиле пользователя. По умолчанию он должен выбираться никак не менее 20.

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

Размером capacity массива является remembered + 1 ; это соглашение означает фиксирование одной из позиций (последней с индексом capacity ), оно необходимо для различения пустого и полностью заполненного списка. Занятые позиции помечены двумя целочисленными атрибутами: oldest - является позицией самой старой запомненной команды, и next - первая свободная позиция (для следующей команды). Атрибут index указывает текущую позицию курсора.

Вот как выглядит реализация компонентов. Для put(c), вставляющей команду c в конец списка, имеем:

representation.put (x, next);
--где representation это имя массива
next:= (next\\ remembered) + 1
index:= next

где операция \\ представляет остаток от деления нацело. Значение empty истинно, если и только если next = oldest ; значение is_first истинно, если и только если index = oldest; и before истинно, если и только если (index\\ remembered) + 1 = oldest. Телом forth является:

index:= (index\\ remembered) + 1
а телом back:
index:= ((index + remembered - 2) \\ remembered) + 1

Запрос item возвращает элемент в позиции курсора - representation @ index, - элемент массива с индексом index. Наконец, процедура remove_all_right, удаляющая все элементы справа от курсора, реализована так:

next:= (index remembered) + 1

Интерфейс пользователя для откатов и повторов

Покажем, как выглядит возможный интерфейс пользователя, поддерживающий механизм undo-redo. Пример взят из ISE, но и некоторые другие наши продукты используют ту же схему.

Хотя горячие клавиши доступны для Undo и Redo, полный механизм включает показ окна истории (history window). В нем отображается список history. Однажды открытое, оно регулярно обновляется при выполнении команд. В отсутствие откатов оно выглядит так:

Оно отображает список выполненных команд. При выполнении новой команды, она появится в конце списка. Текущая активная команда (отмеченная курсором) подсвечена, как показано на рисунке для " change relation label ".

Для отката достаточно щелкнуть по кнопке со стрелкой $$\uparrow$$ или использовать горячие клавиши (Alt-U). Если передвинуть курсор вверх (для списка это переход назад - back) то после нескольких операций Undo, окно примет вид, показанный на рис. 3.8.

В этом состоянии есть выбор:

Можно выполнить нормальную команду. Как мы знаем, из истории удалятся все команды, для которых был откат, но не было повтора; для списка это означает удаление элементов справа от курсора и вызов remove_all_right; все команды ниже подсвеченной исчезнут.

Обсуждение

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

Роль реализации

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

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

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

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

Небольшие классы

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

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

Иногда для операций приходится писать обертывающий класс, что кажется искусственным, особенно для людей, привыкших передавать процедуры в качестве аргументов. Но мне неоднократно приходилось видеть, что класс, введенный с единственной целью инкапсуляции операции, превращался позже в полноценную абстракцию данных с добавлением операций, о которых не шла речь в первоначальном замысле. Класс COMMAND не попадает в эту категорию, он с самого начала рассматривался как абстракция данных и имел два компонента ( execute and undo ). Но, что типично, серьезная работа с командами приводит к осознанию необходимости других компонентов, таких как:

Еще один пример взят из области численных вычислений. Рассмотрим классическую задачу вычисления интеграла. Как правило, подынтегральная функция f передается как аргумент в программу, вычисляющую интеграл. Традиционная техника представляет f как функцию, при ОО-проектировании мы обнаруживаем, что "Интегрируемая функция" является важной абстракцией со многими возможными свойствами. Для пришедших из мира C, Fortran и нисходящего проектирования необходимость написания класса в такой ситуации кажется простым программистским трюком. Возможно, первое время он неохотно будет принимать эту технику, смиряясь с ней. Продолжая проект, он скоро осознает, что интегрируемая функция - INTEGRABLE_FUNCTION - на самом деле является одной из главных абстракций проблемной области. В этом классе появятся новые полезные компоненты помимо компонента item (a: REAL): REAL, возвращающего значение функции в точке a.

То, что казалось лишь трюком, превращается в главную составляющую проекта.

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

Механизм undo-redo, описанный в этой лекции, был реализован в конструкторе структурированных документов Cepage, разработанном Жан-Марк Нерсоном и автором в 1982 [M 1982] и позже был интегрирован во многие интерактивные средства ISE (включая ArchiText [ISE 1996], преемника Cepage).

На первой конференции OOPSLA в 1986 Larry Tesler говорил о механизме, основанном на той же идее, встроенном в интерактивный каркас Apple's MacApp.

В работе [Dubois 1997] объясняется в деталях, как применять ОО концепции в численных вычислениях, с приведением такой абстракции как "Integrable function".

Упражнения

У3.1 Небольшая интерактивная система (программистский проект)

Этот небольшой программистский проект является лучшим способом проверки понимания тем этой лекции и ОО-техники в целом.

Напишите текстовый редактор, ориентированный на работу со строками, поддерживающий следующие операции:

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

У3.2 Многоуровневый Redo

Дополните одноуровневую схему предыдущего упражнения переопределением смысла операции отката u:

У3.3 Undo-redo в Pascal

Объясните, как применить рассмотренную технику в не ОО-языках, подобных Pascal, Ada (используя записи с вариантами) или C (используя структуры и union типы). Сравните с ОО-решениями.

У3.4 Undo, Skip и Redo

С учетом проблем, поднятых в обсуждении, рассмотрите, как можно расширить механизм, разработанный в этой лекции так, чтобы он допускал поддержку Undo, Skip и Redo, а также делал возможным повтор и откат, перемежаемый обычными командами. Обсудите эффект обоих новинок как на уровне интерфейса, так и реализации.

У3.5 Сохранение командных объектов

Рассмотрите аргументы команды независимо от команд и создайте только один командный объект на каждый тип команды.

Если вы выполнили предыдущее упражнение, примените эту технику к решению.

У3.6 Составные команды

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

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

У3.7 Необратимые команды

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

Указание: введите наследников UNDOABLE и NON_UNDOABLE класса COMMAND.

У3.8 Библиотека команд (проектирование и реализация)

Напишите общецелевую библиотеку команд, предполагающую использование в произвольной интерактивной системе и поддерживающую неограниченный механизм undo-redo. Библиотека должна интегрировать свойства, обсуждаемые в последних трех упражнениях: отделение команд от их аргументов, составные команды, необратимые команды. Возможно также встраивание свойства "Undo, Skip и Redo". Проиллюстрируйте применимость библиотеки, построив на ее основе три демонстрационные системы различной природы, такие как текстовый редактор, графическая система, инструмент тестирования.

У3.9 Механизм истории

Полезным компонентом, встраиваемым в командно-ориентированный инструментарий, является механизм истории, запоминающий выполненную команду и позволяющий пользователю повторно ее выполнить, возможно, модифицировав. Под Unix, например, доступен командный язык C-shell, запоминающий несколько последних выполненных команд. Вы можете напечатать !-2, означающее, что нужно выполнить команду, предшествующую последней. Запись ^yes^no^ означает "выполнение последней команды с заменой yes на no". Другие окружения предлагают схожие свойства.

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

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

Обсудите расширение этого механизма на общий класс USER_INTERFACE.

У3.10 Тестирование окружения

Тестирование компонентов ПО, например, класса требует определенных свойств при подготовке теста: ввода тестовых данных, выполнения теста, записи результатов, сравнения с ожидаемыми результатами и так далее. Определите общий, допускающий наследование класс TEST, задающий тестирующее окружение. (Обратите внимание, что и здесь важно множественное наследование.)

У3.11 Интегрируемые функции

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