?

Log in

о типах (программистское) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о типах (программистское) [ноя. 27, 2009|02:49 am]
Anatoly Vorobey
Я искренне пытался понять эту статью, сравнивающую объекты и абстрактные типы данных, но в итоге всего лишь сломал мозг. Основной аргумент мне кажется то ли невнятным, то ли очевидно неверным. В результате ее прочтения я решил, что объекты и ADTs более похожи друг на друга, чем до того считал (т.е. пришел к выводу, противоположному утверждениям статьи).

Скорее всего, виноват я, а не автор, и у меня просто не получается понять, что он говорит (главным образом, когда он говорит об OOP). Кстати, если вы понимаете эту статью и согласны с ней, я был бы рад задать вам пару вопросов. Короче, основным результатом моей фрустрации стало то, что я начал читать Types and Programming Languages Пирса. Вот прочитаю и буду все знать про типы. Пока что очень нравится, отлично объясняет и заинтересовывает. Кстати, обнаружился черновик русского перевода. Мне он ни к чему, но может кому-то пригодится.
СсылкаОтветить

Comments:
[User Picture]From: ygam
2009-11-27 12:56 am

Книжка Пирса - очень хорошая!
(Ответить) (Thread)
[User Picture]From: alexeybobkov
2009-11-27 12:59 am
Прекрасная книга.
Пирс вообще крут. При описании даже самого тривиального, казалось бы, понятия находит нетривиальные примеры и неочевидные тонкости.
(Ответить) (Thread)
[User Picture]From: kouzdra
2009-11-27 01:01 am
АТД легко выражаются через экзистенциальные типы. Но это сугубо двухуровневая иерархия - "интерфейс - множество реализаций" (присутствующая в куче языков - начниная с Clean и кончая почти стандартными уже расширениями Haskell), для представления же обектоности - с неограниченной иерахией наследования нужна система типов дикой мощности (это все 80-е было чуть ли не самой challenging задачей в области теории типов, пока ее в 1994 Пирс формально не решил - решение скучное и техническое, но требует очень мощной системы типов)
(Ответить) (Thread)
[User Picture]From: avva
2009-11-27 01:03 am
Кук вообще игнорирует наследование в своей статье; с его точки зрения разница между ADTs и объектами вовсе не в этом.
(Ответить) (Parent) (Thread)
[User Picture]From: kouzdra
2009-11-27 01:13 am
Я при пролистывании не понял, попробую потом еще посмотреть. Но вообще - тема изрядно изъезженная и уже почти в mainstream перешедшая - в виде тех же Haskell и ML (АКА F#). Что там нового можно сейчас сказать, как-то уже не очень ясно.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-11-27 01:28 am
Спасибо.
(Ответить) (Parent) (Thread)
[User Picture]From: psr1913plus16
2009-11-27 02:11 am
Если абстрагироваться от деталей (которые в каких-то случаях важны, в каких-то - нет), то OOP - это результат применения к ADT процедуры _популяризации_, в результате которой оно становится доступным для понимания простым (commodity) программистам. После чего им можно дать задание запрограммировать результат анализа предметной области и не беспокоиться, что они сломают на этом мозг. Для собственно Computer же Science, ее существенных и интересных задач, OOP не имеет никакого значения.
(Ответить) (Parent) (Thread)
[User Picture]From: abreslav
2009-11-27 09:41 am
Мне кажется, в статье разница прописана довольно четко: в случае объектов есть позднее связывание, которое автор описывает как применение функций высших порядков, в случае АТД, как верно отметил kouzdra, все можно описать через экзистенциальные типы.

Если есть еще конкретные вопросы, я готов вчитаться глубже и попробовать пообсуждать.
(Ответить) (Parent) (Thread)
[User Picture]From: tt_net
2009-11-27 02:02 am
Ну да, мозг ломается с разгону.
Странно, что на Peter Wegner ссылаются поищу эту статью, всегда считал его адоптом ООП.
Если совсем интересно внятное мнение могу рекомендовать обратится к Jim Wooley (http://geekswithblogs.net/cwilliams/archive/2008/07/25/124017.aspx), обращаться можно здесь http://www.thinqlinq.com/ он обычно отвечает почти сразу.
Для меня он стал ментором, подняв мой рейтинг очень сильно, думаю и ему будет интересно обсудить Types and Objects.
Кстати после "Тhe OO composite pattern is a poor tool for GUIs" мне стало скучно, похоже парень ушел глубоко в теорию и давно не занимался практикой...
Ему бы с Rockford Lhotka поговорить (http://www.lhotka.net/) - как десять лет назад он сломал мое понимание ООП, так и работаю с CSLA не останавливаясь

(Ответить) (Thread)
[User Picture]From: kmmbvnr
2009-11-27 06:26 am
>>как десять лет назад он сломал мое понимание ООП,
А у него есть что почитать такого, ломающего понимание ООП?
(Ответить) (Parent) (Thread)
[User Picture]From: tt_net
2009-11-27 10:50 am
CSLA, раннее всё о Visul Basic к сожалению, потом без привязки к языку.
У Jim пока только о LINQ, итстатьи в MSDN.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-11-30 07:13 am
Ничего особенного он там не сломал, за исключением здравого утверждения, что объекты должны проектироваться отталкиваясь не от сущностей, которые они представляют, а от функций, которые они выполняют.

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

Впрочем, после убожества ADO.NET это можно считать прорывом.

ЗЫ К самому Лотке я отношусь с гигантским уважением. Работу он проделал великую, а учитывая, что писал он это еще для VB6, то только можно шляпу снять. Что не отменяет того факта, что сейчас такой фреймворк больше мешает чем помогает (imho, конечно).
(Ответить) (Parent) (Thread)
[User Picture]From: kmmbvnr
2009-11-27 06:22 am
Интересно, а прочитав Concepts, techniques, and models of computer programming у меня сложилось мнение что ADT это всего лишь более общее понятие чем объекты.

В терминологии из этой книги объекты это Statefull, Closed and Secured ADT.
(Ответить) (Thread)
[User Picture]From: alexott
2009-11-27 08:14 am
а сделайте ссылку пожалуйста на главную страницу перевода - там есть координаты куда слать замечания и комментарии
(Ответить) (Thread)
[User Picture]From: avva
2009-11-27 11:41 am
Сейчас сменю ссылку.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2009-11-27 10:04 am
мне кажется, я понял, о чем статья, и готов отвечать на вопросы.
(Ответить) (Thread)
[User Picture]From: cousin_it
2009-11-27 11:41 am
The article is pretty poor. In truth Cook isn't comparing objects to ADTs; he's comparing his idea of a pure object system (no type checking, all objects are opaque so no binary operations, all classes freely subclassable) to his idea of a pure ADT-based system (statically typed, binary operations implementable, all types sealed). So in section 4 he points out some important-sounding theoretical differences, but in most industry languages those differences just evaporate completely (because objects are allowed access to other objects of the same class, etc.)
(Ответить) (Thread)
[User Picture]From: gdy
2009-11-27 02:37 pm
Мне кажется, это отличие между Smalltalk и CLU. Или между программированием на С++ с помощью value types и programming to interface.

Я могу попробовать коротко написать, что мне кажется сутью статьи, но я не уверен, что вы хотели спросить именно про это.
Общее то, что ADT и объекты скрывают реализацию от пользователей, то есть от функций, которые работают только с интерфейсами экземпляров ADT и класса. Различие в том, что некоторые "сложные" операции в случае ADT могут быть частью определения типа и поэтому знать, что оба аргумента реализованы одинаково, а в случае "объектов" (как их определяет автор, Smalltalk или COM) сложные операции могут работать только с интерфейсами, возможно, по-разному реализованными.
В первом случае мы в программе не можем смешивать различные реализации множества, во втором - можем, но ценой неэффективной реализации сложных операций, либо жирного интерфейса, ограничивающего разнообразие реализаций (вплоть до единственной и тогда всё вырождается в ADT).
(Ответить) (Thread)
From: (Anonymous)
2009-11-29 05:35 am
совершенно целиком и полностью согласен
(Ответить) (Parent) (Thread)
[User Picture]From: gdy
2009-12-02 03:05 pm
Или так:
Пользователи обращаются к методам объекта косвенно (через virtual method table, dynamic dispatch или ещё что-то), это позволяет писать код, который может работать с разными реализациями абстрактного интерфейса, но из-за этого же такой код не может знать ничего про реализацию объектов. Если функция использует два объекта, то даже если она является член-функцией класса одного из объектов, она не имеет понятия о реализации второго объекта.
В случае ADT косвенного обращения нет, и это позволяет писать функции, имеющие доступ к реализации обоих аргументов.

Edited at 2009-12-02 15:19 (UTC)
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-02 06:22 pm
Кстати, здесь не учитывается такая дивная вещь как мультиметоды. Только что вот сообразил.
(Ответить) (Parent) (Thread)
[User Picture]From: laformica
2009-11-29 07:44 pm
Лень читать статью, и не очень понимаю, почему сравниваются АТД и объекты, а не классы, но Bertrand Meyer дает следующее, довольно ясное определение:

A class is an abstract data type equipped with a possibly partial implementation.

т.е. как только появляется хоть какая-то имплементация, это уже класс, если только спецификация, это еще АТД. Объект, в свою очередь, это:

An object is a run-time instance of some class.

Сама книга называется Object Oriented Software Construction, и там хоть и есть спорные вещи, но я бы рекомендовал.
(Ответить) (Thread)
From: (Anonymous)
2009-11-30 06:01 am
эта книга чуть менее, чем полностью, состоит из спорных вещей, очень спорных вещей и откровенно неверных вещей. я ее в свое время купил за свои кровные $70 (кажется) плюс пересылка. мне случалось разбазаривать более крупные суммы на куда как менее полезные вещи, но такого расстройства от потраченных зря денег не испытывал никогда. если бы взял в библиотеке, наверное, не был бы так разочарован.

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

наконец (идем от конца к началу) статья рассматривает типы и значения, не слишком стараясь разграничить их на уровне слов (из контекста понятно, о чем речь). под объектом часто понимается объектный тип, а под ADT — значение абстрактного типа (пафос статьи заключается в том, что объектный тип и ADT — содержательно разные вещи). а классы могут отождествляться с типами, а могут и не, а могут и вообще отсутствовать как класс, поэтому лучше о них молчать.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-11-30 07:36 am
сейчас сообразил, что как раз таки по Майеру объекты/классы и ADT формально унифицированы, из-за наличия в его языке волшебных слов like Current и no polymorphic catcalls. но содержательно они остаются разными вещами. то есть ковариантность и сопутствующий ей запрет на полиморфизм как раз и превращает класс в ADT, или разграничивает класс и ADT, whatever. я это так всегда и воспринимал для себя, с самого начала, как прочитал OOSC. только не называл ADT ADT, а называл value type.
(Ответить) (Parent) (Thread)
[User Picture]From: laformica
2009-11-30 02:12 pm
Какая-то каша, если честно. "Классы могут отсутствовать как класс" - не понимаю.

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

DT is a set of data values and associated operations that are precisely specified independent of any particular implementation.

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

Еще раз, это те определения, которыми пользуюсь я. Если вы можете поделиться определениями того, что вы понимаете под словами ADT, object и class, то я готов продолжить беседу. Если нет - то я не вижу и смысла.

Вообще у меня сложилось впечатление, что вы под object понимаете reference type, а под adt - value type.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-11-30 06:03 pm
Я могу, конечно, поделиться определениями, но не проще ли почитать статью? Речь-то не обо мне и не о моих личных определениях, а о статье, с которой я всего лишь более или менее согласен, потому что в ней говорятся довольно очевидные вещи. Я совершенно не готов ее неустанно пропагандировать и защищать перед людьми, которые не хотят ее читать.

Насколько я могу судить, понимание adt как value type довольно близко к позиции автора статьи, но не идентично.
(Ответить) (Parent) (Thread)
[User Picture]From: laformica
2009-11-30 07:59 pm
Почитал. Мое мнение: наукообразная ересь.

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

Не согласен, потому что несмотря на ссылки на 62 источника, совершенно непонятно, на что он ссылается, заявляя, что

built-in types in most languages... are abstract data types

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

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

Суть вашего ответа я понял так, что данная статья намного менее спорная, чем труд Мейера, на которого ссылается ни много ни мало Гради Буч, и что вы ее прекрасно поняли (и даже нашли некий пафос) и способны объяснить, почему же она стоит того, чтобы ее вообще читать. И это меня заинтересовало.
Но так как вы излагаете свои мысли еще немного менее понятно, чем автор статьи, для начала я решил узнать, что вы понимаете под теми терминами, которые используете.

В итоге я остаюсь с мнением, что некоторым просто гораздо приятнее рассуждать о том, насколько очевидным для них кажется то, что другим ломает мозг, чем в двух словах донести до этих последних очевидное.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-01 06:44 am
Ну вот, хотел в двух словах, а написал столько, что даже заглавные буквы пришлось расставить, чтобы уж совсем было все как положено.

built-in types in most languages... are abstract data types

Это не определение, а наблюдение. Определение было предложением раньше. Вот оно еще раз: An abstract data type (ADT) has a public name, a hidden representation, and operations to create, combine, and observe values of the abstraction.

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

Наблюдение утверждает, что, например, тип Integer в языке Паскаль имеет публичное имя (ставим галочку), скрытое представление (галочку) и набор операций для манипуляции значениями (галочку). Если принять предложенное определение, то я не очень понимаю, с чем здесь спорить. Разве что с тем, что пользователь не знает, единственное ли там представление — для этого нужно в компилятор лезть и смотреть, как Integer реализован. Но логика и опыт написания компиляторов подсказывают, что скорее всего все-таки единственное.

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

Это как раз то, что автор называет object interface.

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

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

И все. Ну что здесь такого спорного или непонятного, а?

Здесь несколько больше, чем два слова, но я надеюсь, что очевидное-тривиальное худо-бедно донесено и не расплескано по дороге.
(Ответить) (Parent) (Thread)
[User Picture]From: laformica
2009-12-01 10:53 pm
О, вот теперь я вас понимаю. И, о чудо, я понимаю и автора статьи. Хотя понимать ее уже даже не надо, потому что, по моему, суть вы прекрасно изложили здесь. За что спасибо.

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

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

Интересно, что если посмотреть, какие определения неправильны с точки зрения автора, а именно “A class is itself an abstract data type” и “the abstract data types in object-oriented languages... are called classes.”, то они более или менее совпадают с моими.

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

В итоге, апдейт вывода о статье: ну раз автор называет словами ADT и object именно то, что он называет, спорить, действительно, не о чем. Различие, действительно, есть, различие существенное, чтобы о нем помнить, хотя бы изучая новый язык программирования. В общем, тогда не ересь. Но и не более того.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-02 07:58 am
1. Я, например, познакомился с абстракцией данных через язык CLU (да, я такой старый), в котором АТД определяются как в статье (на самом деле наоборот, в статье как в CLU). Так что терминология мне вполне близка. Тому, кто начал изучение с ООП, она может показаться странной.

2. Наличие или отсутствие mutable state вполне ортогонально предмету разговора. Для простоты можно считать, что методы принимают состояние объекта и возвращают новое состояние. Так обычно принято.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-04 04:22 am
Кстати, на статью Кука ссылается Гай Стил, человек тоже не последний в дизайне языков программирования.
http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion

(Ответить) (Parent) (Thread)
From: textrider
2009-12-05 04:21 am
Хмм. Объект - это ПЕРЕМЕННАЯ, сложного типа. Абстактный тип данных - это именно ТИП ДАННЫХ.
(Ответить) (Thread)
From: tr1gger
2009-12-05 09:59 am
Как вредный математик не могу не прокомментировать что статья содержит ошибки, а автор не разобрался о чем пишет:
1. Уже на второй странице insert неправильно реализован.

2. "Two standard approaches to describe sets abstractly are as an algebra or as a characteristic function." Множества стандартно определяются аксиомами Цермело-Френкеля.
"The sort, or carrier set, of an algebra is often described as a set, making this definition circular" в математике нет циклических определений, автор откровенно лжёт.

Дальше статью не читал.
(Ответить) (Thread)