Пирс Б. Типы в языках программирования

Подождите немного. Документ загружается.

Глава 18

Расширенный пример: императивные

объекты

В этой главе мы построим первый в этой книге пример нетривиальной системы. Мы используем

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

ссылки и наследование, — и с их помощью создадим набор программных идиом, поддерживающих

объекты и классы, вроде тех, что есть в объектно-ориентированных языках программирования, таких,

как Smalltalk или Java. В этой главе мы не введем никакого нового синтаксиса для объектов: нашей

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

сымитировать на основе более низкоуровневых элементов языка.

На протяжении большей части главы имитация будет довольно точной: мы сможем получить удовле-

творительную реализацию большинства свойств объектов и классов, рассматривая их как производные

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

Однако когда в §18.9 мы добиремся до виртуальных методов и self, мы столкнемся с некоторыми

сложностями, связанными с порядком вычислений, и из-за этого подход с удалением сахара окажется

нереалистичным. Более удовлетворительное описание этих конструкций можно получить путем пря-

мой аксиоматизации их синтаксиса, операционной семантики и правил типизации, как мы сделаем в

Главе 19.

18.1. Что такое объектно-ориентированное программирование?

Большинство споров на тему «В чем сущность такого-то явления?» скорее проявляют предрассуд-

ки их участников, чем проясняют какую-либо объективную истину относительно их темы. Попытки

точно определить термин «объектно-ориентированный» не являются здесь исключением. Тем не ме-

нее, можно отметить несколько основных конструкций, которые имеются в большинстве объектно-

ориентированных языков, и которые вместе служат основой характерного стиля программирования с

хорошо известными достоинствами и недостатками.

1. Множественные представления. Вероятно, самая фундаментальная характеристика

объектно-ориентированного стиля — то, что, когда по отношению к объекту применяется

некоторая операция, объект сам определяет, какой код ее осуществляет. Два объекта с одним и

тем же множеством операций (т. е., с одинаковым интерфейсом) могут иметь совершенно разные

внутренние представления, если каждый из них содержит реализацию операций, работающих с

его конкретным представлением. Эти реализации называются методами объекта. Применение

операции к объекту, называемое вызов метода или, более красочно, посылка объекту сообщения,

приводит к поиску во время исполнения имени метода в таблице методов, связанной с объектом.

Этот процесс называется диспетчеризация методов.

Примеры из этой главы являются термами простого типизированного лямбда-исчисления с наследованием (Рис. 15.1),

записями (15.3) и ссылками (13.1). Соответствующий интерпретатор на OCaml называется fullref.

181

182 18.1. Что такое объектно-ориентированное программирование?

В противоположность этому, обыкновенный абстрактный тип данных (АТД) состоит из набо-

ра значений, связанных с единственной реализацией операций над этими значениями. (Такое

статическое определение реализаций имеет как достоинства, так и недостатки по сравнению с

объектами; мы это подробно рассматриваем в §24.2.3.)

2. Инкапсуляция. Внутреннее представление объекта, как правило, недоступно за пределами его

определения: только собственные методы объекта имеют право прямо считывать или изменять его

поля.

Это означает, что изменения во внутреннем представлении объекта могут повлиять лишь

на небольшой, ясно определенный участок проограммы; такое ограничение значительно облегчает

чтение и поддержку больших систем.

Абстрактные типы данных предоставляют подобные же формы инкапсуляции, и делают конкрет-

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

модуля, или определения АТД), а код вне этого участка может работать со значениями типа

только с помощью операций, определенных внутри привилегированной области.

3. Наследование. Тип объекта — его интерфейс, — просто множество имен и типов его операций.

Внутреннее представление объекта не фигурирует в его типе, поскольку оно не влияет на набор

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

Интерфейсы объектов естественным образом определяют отношение наследования. Если объект

удовлетворяет интерфейсу I, то он, разумеется, удовлетворяет всякому интерфейсу J с более уз-

ким набором операций, чем I, поскольку всякий контекст, ожидающий J-объект, может вызывать

у него только J-операции, и использование I-объекта в таком контексте является безопасным.

(Таким образом, наследование объектов подобно наследованию записей. На самом деле, в модели

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

часть интерфейса объекта позволяет нам писать код, обрабатывающий многие различные виды

объектов единым способом, требуя при этом только опеределенного общего набора операций.

4. Наследование реализаций. Объекты, в интерфейсах которых есть общая часть, часто будут

иметь общность и в поведении, и нам хотелось бы эту общую часть поведения реализовать лишь

однажды. В большинстве объектно-ориентированных языков такое повторное использование по-

ведения достигается при помощи структур, называемых классы — образцы, служащие для созда-

ния экземпляров объектов, — и механизма производных классов, позволяющего порождать новые

классы из старых, добавляя реализации новых методов, и по необходимости переопределяя реали-

зации отдельных старых методов. (Некоторые объектно-ориентированные языки вместо классов

используют механизм делегатов, сочетающий свойства объектов и классов.)

5. Открытая рекурсия. Еще одна удобная конструкция, имеющаяся в большинстве языков с объ-

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

через особую переменную по имени self (в некоторых языках this). Особенность поведения self

состоит в том, что она имеет позднее связывание, что позволяет одному методу класса вызывать

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

В некоторых объектно-ориентированных языках программирования, таких как Smalltalk, инкапсуляция обязательна

— извне определения объекта невозможно даже назвать имя его полей. В других языках, скажем, C или Java, поля

могут быть помечены как общедоступные (public) или приватные (private). С другой стороны, в Smalltalk все методы

объекта публично доступны, в то время как C и Java позволяют отмечать методы модификатором private, и таким

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

подробно рассматривались в исследовательской литературе (Pierce and Turner 1993; Fisher and Mitchell 1998; Fisher 1996a;

Fisher and Mitchell 1996; Fisher 1996b; Fisher and Reppy 1999). В то время как в большинстве объектно-ориентированных

языков инкапсуляция считается существенным свойством, в нескольких языках это не так. Мультметоды, имеющиеся в

CLOS (Bobrow, DeMichiel, Gabriel, Keene, Kiczales and Moon 1988; Kiczales, des Rivi`eres and Bobrow 1991), Cecil (Chambers

1992, 1993), Dylan (Feinberg, Keene, Matthews and Withington 1997; Shalit 1997) и KEA (Mugridge. Hamer and Hosking

1991), а также в лямбда-& исчислении Кастаньи, Гелли и Лонго (Castagna, Ghelli and Longo 1995; Castagna 1997) хранят

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

особых меток типа. Внутренние механизмы создания объектов, вызова методов, определения классов и т. п. в этих

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

идиомам программирования.

rev. 104

18.2. Объекты 183

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

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

В последующих главах исследуются другие подходы к объектам и классам. Глава 19 представляет

прямое определение (в отличие от кодирования) объектов и классов в стиле Java. В Главе 27 мы воз-

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

классов при помощи ограниченной квантификации. В Главе 32 разрабатывается более амбициозная

версия кодирования, работающая в чисто функциональном контексте.

18.2. Объекты

В простейшем варианте объект — это просто структура данных, содержащая некоторое внутреннее

состояние и предоставляющая доступ к этому состоянию через набор методов. Внутреннее состояние

обычно состоит из нескольких изменяемых переменных экземпляра (или полей), разделяемых между

методами и недоступных остальным частям программы.

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

счетчики. Каждый объект-счетчик содержит одну числовую переменную и имеет два метода (т. е., ре-

агирует на два сообщения) — get, застаяляющий его вернуть текущее значение, и inc, увеличивающий

это значение.

Простейший способ обеспечить это поведение при помощи конструкций, описанных нами в преды-

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

циями для методов. Объект-счетчик, текущее состояние которого равняется 1, выглядит так:

c = let x = ref 1 in

{ get = λ_: Unit . !x ,

inc = λ_ : Unit . x := succ (! x )};

c : { get : Unit - >Nat , inc : Unit -> Unit }

Тела обоих методов записываются как функции с тривиальными параметрами (записываемыми _, по-

скольку нам не требуется обращаться к ним изнутри тел функций). Эти абстракции предотвращают

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

тела, снова и снова применяя их к аргументу unit. Заметим также, как состояние объекта разделя-

ется его методами и недоступно остальной программе: инкапсуляция состояния прямо возникает из

лексической области видимости переменной x.

Чтобы вызвать метод объекта c, мы просто извлекаем поле из записи и применяем его к соответ-

ствующему аргументу. Например:

c. inc unit ;

unit : Unit

c. get unit

2 : Nat

(c. inc unit ; c. inc unit ; c . get unit )

4 : Nat

То, что метод inc возвращает unit, позволяет нам для последовательности запросов на увеличение

счетчика воспользоваться записью через ; (§11.3). Можно было бы записать последнюю строку в эк-

вивалентной форме

let _ = c. inc unit in let _ = c . inc unit in c. get unit

Поскольку нам может понадобиться породить несколько счетчиков и работать с ними всеми, удобно

будет ввести сокращение для их типа:

Co unter = { get : Unit - >Nat , inc : Unit -> Unit }

rev. 104

184 18.3. Генераторы объектов

В этой главе мы основное внимание обращаем на то, как объекты устроены, а не на то, как они

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

ну функцию, использующую объекты, чтобы убедиться что она правильно работает с объектами, у

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

объект-счетчик и трижды вызывающая его метод inc:

inc3 = λc : C ounter . (c. inc unit ; c. inc unit ; c . inc unit );

inc3 : Cou nter -> Unit

( inc3 c; c. get unit );

7 : Nat

18.3. Генераторы объектов

Мы видели, как строить отдельные объекты-счетчики по одному. Столь же просто написать гене-

ратор счетчиков — функцию, создающую и возвращающую новый счетчик при каждом вызове.

newC o u n t e r =

λ_ : Unit . let x = ref 1 in

{ get = λ_: Unit . !x ,

inc = λ_ : Unit . x := succ (! x )};

newC o u n t e r : Unit -> Counte r

18.4. Наследование

Одна из причин популярности объектно-ориентированных стилей программирования в том, что

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

например, что, помимо определенных выше объектов типа Counter, мы создаем также некоторое коли-

чество объектов, имеющих дополнительный метод для сброса счетчика в начальное состояние (скажем,

1) в любое время.

ResetCounter = { get : Unit - >Nat , inc : Unit -> Nat , rese t : Unit -> Nat };

newResetCounte r =

λ_ : Unit : let x = ref 1 in

{ get = λ_ : Unit . !x ,

inc = λ_ : Unit . x := succ (! x) ,

reset = λ_ : Unit . x :=1};

newResetCounte r : Unit -> Re s e t C o u n t e r

Поскольку тип ResetCounter содержит все поля типа Counter (плюс еще одно), по правилу на-

следования для записей получаем ResetCounter <: Counter. Это означает, что клиентские функции

вроде inc3, принимающие в качестве аргументов счетчики, безопасно использовать и со сбрасываемыми

счетчиками.

rc = n e w R e s e t Co u n t e r unit ;

rc : ResetCounter

( inc3 rc ; rc . reset unit ; inc3 rcl rc . get unit );

4 : Nat

rev. 104

18.5. Группировка переменных экземпляра 185

18.5. Группировка переменных экземпляра

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

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

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

Чтобы дать себе такую возможность, давайте изменим внутреннее представление счетчиков, сделаем

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

методов через проекцию полей этой записи.

c = let r = { x = ref 1} in

{ get = λ_: Unit . !( r.x ) ,

inc = λ_ : Unit . r. x := succ (!( r.x ))};

c : Counte r

Тип этой записи, содержащей переменные экземпляра, называется типом представления объекта.

Coun t e r R e p = {x : Ref Nat };

18.6. Простые классы

Определения типов Counter и ResetCounter одинаковы, за исключением метода reset во втором

из них. Разумеется, оба эти определения настолько короткие, что повторение не создает особых труд-

ностей, но, если мы представим себе, что эти определения занимают многие страницы, как это часто

случается на практике, ясно, что было бы полезно уметь описывать общую функциональность в одном

месте. Механизм, позволяющий это делать в большинстве объектно-ориентированных языков, называ-

ется классы.

Механизмы определения классов в настоящих объектно-ориентированных языках, как правило,

очень сложны и перегружены деталями — self, super, аннотации видимости, статические поля и ме-

тоды, внутренние классы, аннотации вроде final и Serializable и т. д. и т. п.

На большую часть

этих деталей мы не будем обращать внимания, и сосредоточимся на самых базовых свойствах классов:

повторное использование кода через наследование реализаций, а также позднее связывание переменной

self. Рассмотрим сейчас только первый из этих вопросов.

В своей прстейшей форме класс — это просто структура данных, содержащая набор методов. У этой

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

и получить при этом новый класс.

Почему мы не можем использовать методы какого-либо объекта-счетчика, если хотим создать сбра-

сываемый счетчик? Просто потому, что в каждом конкретном объекте-счетчике тела методов содержат

ссылки на какую-то конкретную запись с переменными экземпляра. Ясно, что если мы хотим исполь-

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

методы по отношению к переменным экземпляра. Это приводит к разбиению функции newCounter на

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

экземпляра,

counterClass =

λr : Co u n t erRep .

{ get = λ_: Unit . !( r.x ) ,

inc = λ_ : Unit . r. x = succ (!( r.x ))};

counterClass : Co u n terRep -> Coun ter

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

объект:

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

структуризации программ в целом. Действительно, есть только один широко используемый язык — OCaml, — где имеются

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

языковых конструкций, имеющих какое-то отношение к структуре крупных программ.

rev. 104

186 18.7. Добавление новых переменных экземпляра

newC o u n t e r =

λ_ : Unit . let r = {x= ref 1} in

counterClass r;

newC o u n t e r : Unit -> Counte r

Тела методов из counterClass можно использовать для определения новых классов, называемых

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

resetCoun t e r C l as s =

λr : Co u n t erRep .

let super = co u n t e r C l a s s r in

{ get = super . get ,

inc = super .inc ,

reset = λ_ : Unit . r. x := 1};

resetCoun t e r C l as s : CounterRep -> ResetCounter

Подобно CounterClass, эта функция принимает запись переменных экземпляра и возвращает объект.

Внутри себя она сначала создает при помощи CounterClass объект-счетчик с той же самой записью

переменных экземпляра r. Затем она строит новый объект, копируя поля get и inc из переменной super,

а в качестве значения поля reset дает новую функцию. Поскольку super строится на представлении

r, все три метода разделяют одни и те же переменные экземпляра.

Чтобы построить новый объект-сбрасываемый счетчик, мы, опять же, просто выделяем память для

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

newResetCounte r =

λ_ : Unit . let r = {x= ref 1} in res e t C o u nt e r C la s s r ;

newResetCounte r : Unit -> Re s e t C o u n t e r

Упражнение 18.6.1 Рекомендуется, : Напишите подкласс resetCounterClass, который имеет

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

новый класс при помощи интерпретатора fullref.

Упражнение 18.6.2 : Явное копирование большинства полей надкласса в запись методов под-

класса достаточно неуклюже выглядит — при этом мы избегаем повторения текста методов над-

класса в подклассе, но все равно требуется набирать много текста. Если бы мы собирались разраба-

тывать в этом стиле большие объектно-ориентированные программы, нам бы очень скоро захоте-

лось иметь конструкцию вроде «super with {reset = λ_:Unit. r.x=1}», означающую «запись, та-

кая же, как super, только с дополнительным полем reset, содержащим функцию λ_:Unit. r.x=1».

Запишите синтаксис, операционную семантику и правила типизации для этой конструкции.

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

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

популярных объектно-ориентированных языках вроде C статус классов более сложен — они исполь-

зуются и как типы во время компиляции, и как структуры во время исполнения. Этот вопрос подробнее

рассматривается в §19.3.

18.7. Добавление новых переменных экземпляра

Так получилось, что у наших объектов, счетчика и сбрасываемого счетчика, представление одина-

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

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

мы хотим определить класс «счетчиков с восстановлением», у которых метод reset восстанавливает

состояние к тому значению, которое объект имел на момент последнего вызова метода backup, а не к

заранее заданной константе:

BackupCounter = { get : Unit -> Nat , inc : Unit -> Unit ,

reset : Unit - > Unit , backup : Unit -> Unit };

rev. 104

18.8. Вызов методов надкласса 187

Чтобы реализовать такие счетчики, нам нужна дополнительная переменная экземпляра, которая будет

хранить резервное значение состояния:

BackupCount e r R e p = { x: Ref Nat , b: Ref Nat };

Так же, как мы произвели resetCounterClass из CounterClass, скопировав методы get и inc и

добавив reset, теперь мы производим backupCounterClass из resetCounterClass, копируя get и inc,

и добавляя новое тело reset и backup.

backupCo u n t e rC l a s s =

λr : BackupCounte r R e p .

let super = resetCounter C l a s s r in

{ get = super . get ,

inc = super . inc ,

reset = λ_ : Unit . r.x :=!( r.b ) ,

ba ckup = λ_: Unit . r . b :=!( r . x )};

backupCo u n t e rC l a s s : b ac k u p C ou n t e r Re p -> BackupCounter

В этом определении интересны две подробности. Во-первых, несмотря на то, что в родительском объ-

екте super имеется метод reset, мы предпочитаем написать новую реализацию, поскольку нам нуж-

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

Во-вторых, при типизации выражения, которое строит super, существенным образом используется

наследование: resetCounterClass ожидает аргумента типа CounterRep, который является надтипом

BackupCounterRep, типа, который на самом деле имеет аргумент r. Другими словами, мы на самом

деле даем родительскому объекту запись переменных экземпляра большего размера, чем требуется его

методам.

Упражнение 18.7.1 Рекомендуется, : Определите подкласс backupCounterClass с двумя новы-

ми методами, reset2 и backup2, управляющими вторым «резервным регистром». Этот регистр

должен быть совершенно независим от регистра, добавленного в backupCounterClass: вызов reset

должен восстанавливать состояние счетчика к значению, имевшемуся при последнем вызове backup

(как это и сейчас происходит), а вызов reset2 должен восстанавливать состояние счетчика к зна-

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

татора fullref.

18.8. Вызов методов надкласса

С помощью переменной super мы копировали функциональность из надклассов в новые подклассы.

Кроме того, мы можем пользоваться super в телах определений методов, чтобы расширять поведение

надкласса чем-то новым. Предположим, например, что нам требуется вариант класса backupCounter,

где каждый вызов метода inc предваряется вызовом backup. (Совершенно непонятно, зачем бы такое

могло понадобиться — это всего лишь пример.)

funnyB a c ku p C ou nt e rC l as s =

λr : BackupCounte r R e p .

let super = backupCount e r C la s s r in

{ get = super . get ,

inc = λ_ : Unit . ( super . backup unit ; super . inc unit ) ,

reset = super . reset ,

ba ckup = super . back up };

funnyB a c ku p C ou nt e rC l as s : B ac k u p C o un t e r R ep -> Ba c ku p Co u n t e r

Обратите внимание, как с помощью вызовов super.inc и super.backup в новом определении inc мы

избегаем повторения кода надкласса для inc и backup. В примерах большего размера выигрыш в виде

повторного использования функциональности в таких ситуациях может быть очень существен.

rev. 104

188 18.9. Классы с переменной SELF

18.9. Классы с переменной self

Последнее наше расширение состоит в том, чтобы позволить методам класса ссылаться друг на дру-

га через переменную self. Чтобы оправдать это расширение, предположим, что мы хотим реализовать

класс счетчиков с методом set, с помощью которого можено извне устанавливать значение счетчика в

определенное число.

SetC o u n t e r = { get :Unit - > Nat , set : Natt -> Unit , inc : Unit - > Unit };

Более того, допустим, что мы хотим написать метод inc в терминах set и get, а не через прямое

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

размера, где определения set и get занимают по много страниц.) Поскольку get, set и inc определены

в рамках одного и того же класса, мы, в сущности, хотим позволить методам класса быть взаимно

рекурсивными.

Мы уже видели в §11.11, как взаимно рекурсивные записи или функции строятся с помощью опе-

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

функций (мы эту запись называем self), а затем с помощью оператора fix «затягиваем узел», чтобы

запись, создаваемая нами, сама передавалась как self.

setCounterClas s =

λr : Co u n t erRep .

fix

(λself : Se t C o u nter .

{ get = λ_: Unit . !( r.x ) ,

set = λi : Nat . r.x := i,

inc = λ_ : Unit . self . set ( succ ( self . get unit ))});

setCounterClas s : CounterRep -> SetCou n t e r

У этого класса нет родителя, так что переменная super не требуется. Вместо этого, тело метода inc

вызывает get, а затем set из записи с методами, переданной ему в качестве параметра self. Это

использование fix заметно только изнутри реализации setCounterClass. Счетчики с присваиванием

можно создавать так же, как обычно.

newSetCounter =

λ_ : Unit . let r = {x= ref 1} in

setCounterClas s r ;

newSetCounter : Unit -> SetCount e r

18.10. Открытая рекурсия через self

В большинстве объектно-ориентированных языков поддерживается более общая форма рекурсив-

ных вызовов между методами, известная под названием общая рекурсия, или позднее связывание пе-

ременной self. Можно добиться этой более общей формы поведения, избавившись от использования

fix в определении класса,

setCounterClas s =

λr : Co u n t erRep .

λself : SetCount e r .

{ get = λ_: Unit . !( r.x ) ,

set = λi : Nat . r.x := i.

inc = λ_ : Unit . self . set ( succ ( self . get unit ))};

setCounterClas s : CounterRep -> SetCou n t e r -> SetCounter

м поместив его взамен в функцию создания объекта.

rev. 104

18.11. Открытая рекурсия и порядок вычислений 189

newSetCounter =

λ_ : Unit . let r = {x= ref 1} in

fix ( s et C o u n t e rC l a s s r );

newSetCounter : Unit -> SetCount e r

Заметим, что перенос fix изменяет тип SetCounterClass: теперь он абстрагируется не только от записи

с переменными экземпляра, но и от «объекта self». И тот, и другой параметр поставляются ему в

момент создания экземпляра.

Открытая рекурсия через self интересна потому, что она позволяет методам надкласса вызывать

методы подкласса, несмотря даже на то, что подкласс не существует еще в тот момент, когда опреде-

ляется надкласс. В сущности, мы изменили интерпретацию переменной self так, что, вместо «методов

текущего класса», она дает доступ к «методам класса, экземпляром которого является текущий объект

а это может быть подкласс текущего класса ».

Например, предположим, что нам нужно построить подкласс наших счетчиков с присваиванием,

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

операцию для доступа к счетчику доступа,

InstrCounter = { get : Unit - >Nat , set : Nat -> Unit ,

inc :Unit - > Unit , access e s : Unit - > Nat };

а представление содержит переменную экземпляра, где хранится счетчик доступа:

InstrCounterRe p = { x : Ref Nat , a: Ref Nat };

В определении измененного класса счетчиков методы inc и get копируются из определенного выше

setCounterClass. Метод accesses пишется обычным способом. В методе set мы сначала увеличиваем

счетчик доступа, а затем через super вызываем метод set надкласса.

instrCoun t e r C l as s =

λr : InstrCounterRep .

λself : InstrCounter .

let super = se tC o u n t e r Cl a s s r self in

{ get = super . get ,

set = λi : Nat . (r. a := succ (!( r.a )); super . set i) ,

inc = super .inc ,

acc esses = λ_: Unit . !( r.a )};

instrCoun t e r C l as s : I n s t rC o u n t e r R ep ->

InstrCounter -> InstrCounter

Из-за открытой рекурсии через self, вызов set в теле inc приведет к увеличению переменной эк-

земпляра a, несмотря на то, что эта часть поведения set определена в подклассе, а определение inc

находится в надклассе.

18.11. Открытая рекурсия и порядок вычислений

С нашим определением InstrCounterClass есть только одна неприятность — его невозможно ис-

пользовать для создания экземпляров! Если мы напишем newInstrCounter обычным способом

newInstrCounte r =

λ_ : Unit . let r = {x= ref 1 , a = ref 0} in

fix ( instrCounte r C l a ss r );

newInstrCounte r : Unit -> In s t r C o u n t e r

и затем попытаемся создать счетчик с подсчетом доступа, применив эту функцию к Unit,

ic = n e w I n s t r Co u n t e r unit ;

вычисление этого выражения никогда не завершится. Чтобы понять, почему это так, рассмотрим по-

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

1. Сначала мы применяем newInstrCounter к unit, получая

rev. 104

190 18.11. Открытая рекурсия и порядок вычислений

let r = {x = ref 1, a= ref 0} in fix ( instrCoun t e r C l as s r )

2. Затем мы выделяем две ссылочных ячейки, упаковываем их в виде записи — назовем ее <ivars>,

— и подставляем <ivars> вместо переменной r в оставшейся части терма.

fix ( instrCounte r C l a ss < ivars >)

3. Передаем <ivars> в instrCounterClass. Поскольку instrCounterClass начинается с двух

лямбда-абстракций, мы немедленно получаем функцию, ожидающую значения self,

fix (λself : I n s t r C o u n t e r .

let super = se tC o u n t e r Cl a s s < ivars > self in in < imethods >)

где <imethods> — запись, содержащая методы класса счетчиков с подсчетом доступа. Давайте

назовем эту функцию <f>, и запишем текущее состояние в виде (fix <f>).

4. Применяем правило вычисления для fix (E-Fix c Рис. 11.12), стр. 116). Это правило «развора-

чивает» fix <f>, подставляя (fix <f>) вместо переменной self в теле <f>. Получаем

let super = se tC o u n t e r Cl a s s < ivars > ( fix <f >) in < imethods >

5. Теперь мы редуцируем применение setCounterClass к <ivars> и получаем

let super = (λself : SetC o u n t er . <smethods >) ( fix <f >)

in <imethods >

где <smethods> — запись, состоящая из методов счетчика с присваиванием.

6. По правилам вычисления для термов-применений, мы не можем редуцировать применение

(λself:SetCounter. <smethods>) к (fix <f>), пока (fix <f>) не сведен к значению. Поэтому

на следующем шаге вычисления мы снова разворачиваем fix <f>, получая

let super = (λself : SetC o u n t er . <smethods >)

( let super = s e tC o u n t e r Cl a s s < ivars > ( fix <f >)

in <imethods >)

in <imethods >

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

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

setCounterClass к <ivars> и получаем

let super = (λself : SetC o u n t er . <smethods >)

( let super = (λself : S e t C ounter . <smethods >)

( fix <f >)

in <imethods >)

in <imethods >

8. Теперь у нас получился внутренний терм-применение, подобный внешнему. Как и раньше, этот

внутренний терм не может быть редуцирован, пока полностью не вычислен его аргумент, fix

<f>. Таким образом, на следующем шаге мы снова развернем fix <f>, получая еще более глубоко

вложенное выражение той же формы, что и на шаге 6. Теперь должно быть понятно, что мы

никогда не доберемся до вычисления внешнего терма-применения.

С интуитивной точки зрения, проблема возникает оттого, что аргумент оператора fix слишком рано

использует свой собственный аргумент self. Операционная семантика fix определена в предположе-

нии, что, когда мы применяем fix к некоторой функции λx.t, переменная x должна встречаться в

теле t только в «защищенных» позициях, таких, как тела вложенных лямбда-абстракций. Например,

на стр. 116 мы определили iseven путем применения fix к функции вида λie.λx. ..., где рекур-

сивное упоминание ie было защищено абстракцией по x. Определение instrCounterClass, напротив,

пытается немедленно использовать self при вычислении значения super.

Мы можем пытаться преодолеть эту сложность несколькими способами:

rev. 104