Jaka jest różnica między abstrakcyjnymi typami danych a obiektami?

Odpowiedź na Programmers.SE charakteryzuje esej Cook ( Przedmioty nie są ADTS ) wypowiedź

• Obiekty zachowują się jak funkcja charakterystyczna względem wartości typu, a nie jak algebra. Obiekty używają abstrakcji proceduralnej zamiast abstrakcji typu

• ADT zwykle mają unikalną implementację w programie. Gdy w danym języku są moduły, możliwe jest posiadanie wielu implementacji narzędzia ADT, ale zwykle nie mogą one współpracować.

Wydaje mi się, że w eseju Cooka zdarza się tak, że w konkretnym przykładzie zestawu użytego w pracy Cooka obiekt można postrzegać jako funkcję charakterystyczną . Nie sądzę, że obiekty można ogólnie postrzegać jako charakterystyczne funkcje.

Również artykuł Aldritcha Siła interoperacyjności: dlaczego obiekty są nieuniknione ¹, sugeruje

Definicja Cooka zasadniczo identyfikuje dynamiczną wysyłkę jako najważniejszą cechę obiektu

zgadzając się z tym i Alanem Kayem, kiedy to powiedział

OOP oznacza dla mnie tylko wysyłanie wiadomości, lokalne przechowywanie, ochronę i ukrywanie procesów państwowych oraz ekstremalne późne wiązanie wszystkich rzeczy.

Jednak te slajdy wykładowe do artykułu Aldritcha sugerują, że klasy Java są ADT, podczas gdy interfejsy Java są obiektami - i rzeczywiście za pomocą interfejsów „obiekty” mogą współdziałać (jedna z kluczowych cech OOP podana przez jeden z powyższych punktów ).

Moje pytania są

1. Czy mam rację twierdząc, że charakterystyczne funkcje nie są kluczową cechą obiektów i że Frank Shearar się myli?

2. Czy dane, które komunikują się ze sobą za pośrednictwem interfejsów Java, są przykładami obiektów, nawet jeśli nie używają dynamicznej wysyłki? Czemu? (Rozumiem, że dynamiczna wysyłka jest bardziej elastyczna i że interfejsy są krokiem w kierunku przesyłania komunikatów w stylu C-smalltalk / erlang).

3. Czy idea zasady inwersji zależności jest związana z rozróżnieniem między ADT a obiektami? (Zobacz stronę Wikipedii lub The Talking Objects: A Tale about Programme-Oriented Programming ) Chociaż jestem nowy w tej koncepcji, rozumiem, że obejmuje to dodawanie interfejsów między „warstwami” programu (patrz schemat strony Wikipedii).

4. Jeśli chcesz, podaj inne przykłady / wyjaśnienia dotyczące rozróżnienia między obiektami a ADT.

¹ _{Ten artykuł (opublikowany w 2013 r.) Jest łatwy do przeczytania i podsumowuje artykuł Cooka z 2009 r. Z przykładami w Javie. Gorąco zalecam przynajmniej przejrzenie go, aby nie odpowiedzieć na to pytanie, ale tylko dlatego, że jest to dobry papier.}

Google wywołało podobne pytanie z odpowiedzią, która moim zdaniem jest bardzo dobra. Cytowałem to poniżej.

Czai się tutaj inna różnica, która została wyjaśniona w eseju Cooka, który podłączyłem.

Obiekty nie są jedynym sposobem implementacji abstrakcji. Nie wszystko jest przedmiotem. Obiekty implementują coś, co niektórzy nazywają abstrakcją danych proceduralnych. Abstrakcyjne typy danych implementują inną formę abstrakcji.

Kluczowa różnica pojawia się, gdy weźmie się pod uwagę metody / funkcje binarne. W przypadku abstrakcji danych proceduralnych (obiektów) możesz napisać coś takiego dla interfejsu zestawu Int:

interface IntSet {
  void unionWith(IntSet s);
  ...
}

Rozważmy teraz dwie implementacje IntSet, na przykład jedną wspieraną przez listy, a drugą opartą na bardziej wydajnej strukturze drzewa binarnego:

class ListIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
} 
class BSTIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}

Zauważ, że unionWith musi przyjąć argument IntSet. Nie bardziej szczegółowy typ, jak ListIntSet lub BSTIntSet. Oznacza to, że implementacja BSTIntSet nie może zakładać, że jej dane wejściowe to BSTIntSet i wykorzystać ten fakt, aby zapewnić wydajną implementację. (Może użyć pewnych informacji o typie wykonawczym, aby to sprawdzić i użyć bardziej wydajnego algorytmu, jeśli tak jest, ale nadal może zostać przekazany ListIntSet i musi wrócić do mniej wydajnego algorytmu).

Porównaj to z ADT, w których możesz napisać coś podobnego do poniższego w pliku podpisu lub nagłówka:

typedef struct IntSetStruct *IntSetType;
void union(IntSetType s1, IntSetType s2);

Programujemy w oparciu o ten interfejs. Warto zauważyć, że typ pozostaje abstrakcyjny. Nie wiesz, co to jest. Następnie mamy implementację BST, która zapewnia konkretny typ i operacje:

struct IntSetStruct {
 int value;
 struct IntSetStruct* left;
 struct IntSetStruct* right;
}

void union(IntSetType s1, IntSetType s2){ ... }

Teraz związek faktycznie zna konkretne reprezentacje zarówno s1, jak i s2, więc może to wykorzystać do wydajnej implementacji. Możemy również napisać implementację opartą na liście i zamiast tego wybrać link.

Napisałem składnię C (ish), ale powinieneś spojrzeć np. Na Standardowy ML dla abstrakcyjnych typów danych wykonanych poprawnie (gdzie możesz np. Faktycznie użyć więcej niż jednej implementacji ADT w tym samym programie z grubsza, kwalifikując typy: BSTImpl. Powiedzmy, że IntSetStruct i ListImpl.IntSetStruct)

Wręcz przeciwnie, abstrakcja danych proceduralnych (obiekty) pozwala łatwo wprowadzić nowe implementacje, które działają ze starymi. np. możesz napisać własną niestandardową implementację LoggingIntSet i połączyć ją z BSTIntSet. Ale to jest kompromis: tracisz pouczające typy metod binarnych! Często zdarza się, że musisz ujawnić w interfejsie więcej szczegółów dotyczących funkcjonalności i implementacji niż w przypadku implementacji ADT. Teraz czuję, że po prostu przepisuję esej Cooka, więc naprawdę, przeczytaj!

Chciałbym dodać do tego przykład.

Cook sugeruje, że przykładem abstrakcyjnego typu danych jest moduł w C. Rzeczywiście, moduły w C obejmują ukrywanie informacji, ponieważ istnieją funkcje publiczne, które są eksportowane przez plik nagłówka, i funkcje statyczne (prywatne), które nie. Ponadto często istnieją konstruktory (np. List_new ()) i obserwatorzy (np. List_getListHead ()).

Kluczowym punktem, który sprawia, że, powiedzmy, moduł listy o nazwie LIST_MODULE_SINGLY_LINKED ADT jest to, że funkcje modułu (np. List_getListHead ()) zakładają, że wprowadzane dane zostały utworzone przez konstruktora LIST_MODULE_SINGLY_LINKED, w przeciwieństwie do jakiegokolwiek „równoważnego” ”wdrożenie listy (np. LIST_MODULE_DYNAMIC_ARRAY). Oznacza to, że funkcje LIST_MODULE_SINGLY_LINKED mogą przy swojej realizacji przyjąć szczególną reprezentację (np. Pojedynczo połączoną listę).

LIST_MODULE_SINGLY_LINKED nie może współpracować z LIST_MODULE_DYNAMIC_ARRAY, ponieważ nie możemy karmić danych utworzonych, powiedzmy za pomocą konstruktora LIST_MODULE_DYNAMIC_ARRAY, obserwatorowi LIST_MODULE_SINGLY_LINKED, ponieważ zakłada, że ​​zachowanie reprezentuje tylko listę, która zakłada, że ​​zachowanie tylko dla LIST_MODULE_LINKED zakłada, że ​​zachowanie tylko dla obiektu LIST_MODULE_LINKED zakłada, że ​​zachowanie tylko dla obiektu LIST_MODULE_LINKED zakłada, że ​​zachowanie tylko dla obiektu LIST_MODULE_LINS

Jest to analogiczne do sposobu, w jaki dwie różne grupy z algebry abstrakcyjnej nie mogą ze sobą współpracować (to znaczy nie można wziąć iloczynu elementu jednej grupy z elementem innej grupy). Jest tak, ponieważ grupy przyjmują właściwość zamknięcia grupy (iloczyn elementów w grupie musi znajdować się w grupie). Jeśli jednak udowodnimy, że dwie różne grupy są w rzeczywistości podgrupami innej grupy G, możemy użyć iloczynu G, aby dodać dwa elementy, po jednym z każdej z dwóch grup.

Porównanie ADT i obiektów

• Cook wiąże różnicę między ADT i obiektami częściowo z problemem wyrażania. Z grubsza mówiąc, ADT są połączone z funkcjami ogólnymi, które często są implementowane w funkcjonalnych językach programowania, podczas gdy obiekty są sprzężone z „obiektami” Java dostępnymi poprzez interfejsy. Do celów tego tekstu funkcja ogólna to funkcja, która przyjmuje niektóre argumenty ARGS i typ TYPE (warunek wstępny); na podstawie TYPU wybiera odpowiednią funkcję i ocenia ją za pomocą ARGS (warunek końcowy). Zarówno funkcje ogólne, jak i obiekty implementują polimorfizm, ale dzięki funkcjom ogólnym programista WIE, która funkcja zostanie wykonana przez funkcję ogólną bez patrzenia na kod funkcji ogólnej. Z drugiej strony programista nie wie, jak obiekt będzie obsługiwał argumenty, chyba że programiści spojrzą na kod obiektu.

• Zazwyczaj problem z wyrażeniem jest rozważany w kategoriach „czy mam wiele reprezentacji?” vs. „czy mam wiele funkcji z niewielką reprezentacją”. W pierwszym przypadku kod należy uporządkować według reprezentacji (jak to jest najczęściej, szczególnie w Javie). W drugim przypadku kod należy uporządkować według funkcji (tj. Mając jedną funkcję ogólną obsługującą wiele reprezentacji).

• Jeśli zorganizować swój kod przez reprezentację, a następnie, jeśli chcesz dodać dodatkowe funkcje, jesteś zmuszony do dodania funkcjonalności do każdej reprezentacji obiektu; w tym sensie funkcja dodawania nie jest „addytywna”. Jeśli porządkujesz kod według funkcjonalności, to jeśli chcesz dodać dodatkową reprezentację - jesteś zmuszony dodać reprezentację do każdego obiektu; w tym sensie dodawanie reprezentacji nie jest „addytywne”.

Przewaga ADT nad obiektami

• Dodanie funkcjonalności jest addytywne

• Możliwe wykorzystanie wiedzy na temat reprezentacji ADT dla wydajności lub udowodnienie, że ADT zagwarantuje pewne warunki dodatkowe, pod warunkiem spełnienia warunku wstępnego. Oznacza to, że programowanie przy użyciu narzędzi ADT polega na robieniu właściwych czynności we właściwej kolejności (łączenie warunków wstępnych i warunków wstępnych w celu spełnienia warunku „celowego”).

Zalety obiektów w porównaniu z ADT

• Dodawanie reprezentacji w dodatku

• Obiekty mogą współpracować

• Możliwe jest określenie warunków przed / po dla obiektu i połączenie ich razem, tak jak w przypadku ADT. W tym przypadku zaletami obiektów jest to, że (1) zmiana reprezentacji jest łatwa bez zmiany interfejsu, a (2) obiekty mogą współpracować. Jednak to pokonuje cel OOP w sensie smalltalk. (patrz sekcja „Wersja OOP Alana Kay)

Dynamiczna wysyłka jest kluczem do OOP

Teraz powinno być oczywiste, że dynamiczne wysyłanie (tj. Późne wiązanie) jest niezbędne dla programowania obiektowego. Jest tak, aby możliwe było zdefiniowanie procedur w sposób ogólny, który nie zakłada określonej reprezentacji. Mówiąc konkretnie - programowanie obiektowe jest łatwe w Pythonie, ponieważ możliwe jest programowanie metod obiektu w sposób, który nie zakłada określonej reprezentacji. Dlatego python nie potrzebuje interfejsów takich jak Java.

W Javie klasy są ADT. jednak klasa dostępna za pośrednictwem interfejsu, który implementuje, jest obiektem.

Dodatek: wersja OOP autorstwa Alana Kay

Alan Kay wyraźnie nazwał obiekty „rodzinami algeb”, a Cook sugeruje, że ADT jest algebrą. Dlatego Kay prawdopodobnie oznaczała, że ​​obiekt jest rodziną ADT. Oznacza to, że obiekt jest zbiorem wszystkich klas, które spełniają interfejs Java.

Jednak obraz przedmiotów namalowanych przez Cooka jest znacznie bardziej restrykcyjny niż wizja Alana Kay. Chciał, aby obiekty zachowywały się jak komputery w sieci lub komórki biologiczne. Chodziło o to, aby zastosować zasadę najmniejszego zaangażowania w programowanie - aby łatwo było zmieniać warstwy ADT po ich zbudowaniu. Mając to na uwadze, interfejsy Java są zbyt restrykcyjne, ponieważ nie pozwalają obiektowi interpretować znaczenia wiadomości , a nawet całkowicie ją ignorować.

Podsumowując, kluczową ideą obiektów, dla Kay, nie jest to , że są rodziną algebr (jak podkreśla Cook). Kluczową ideą Kay było raczej zastosowanie modelu, który działał w dużych (komputery w sieci) do małych (obiekty w programie).

edytuj: Kolejne wyjaśnienie wersji OOP Kaya: Celem obiektów jest zbliżenie się do deklaratywnego ideału. Powinniśmy powiedzieć obiektowi, co ma robić - a nie mówić, jak przez mikrozarządzanie jest stanem, jak to jest zwykle w przypadku programowania procedur i ADT. Więcej informacji można znaleźć tutaj , tutaj , tutaj i tutaj .

edit: znalazłem bardzo dobrą ekspozycję definicji Alan Kay OOP tutaj .

Jeśli spojrzysz na zwolenników ADT, uważają ADT za coś, co OOP nazwałby klasą (stan wewnętrzny, prywatny; dozwolony jest ograniczony zestaw operacji), ale nie bierze się pod uwagę relacji między klasami (w zasadzie bez dziedziczenia). Chodzi o to, że to samo zachowanie można uzyskać przy różnych implementacjach. Np. Zestaw może być zaimplementowany jako lista, elementy w tablicy lub tablicy mieszającej lub jako jakiś rodzaj drzewa.

Zawsze rozumiałem to w ten sposób:

1. ADT to interfejs: jest to tylko zbiór metod, ich podpisów typu, prawdopodobnie z warunkami przed i po.

2. Klasa może implementować jeden lub więcej ADT, podając rzeczywiste implementacje dla metod określonych w ADT.

3. Obiekt jest instancją klasy z własną kopią dowolnych zmiennych niestatycznych.

Możliwe, że w literaturze różnice są różne, ale jest to „standardowa” terminologia, którą usłyszysz w informatyce.

Na przykład w Javie Collectionjest ADT, ArrayListjest klasą i można utworzyć ArrayListobiekt za pomocą newoperatora.

Jeśli chodzi o stwierdzenie, że ADT zwykle mają tylko jedną implementację, często tak nie jest. Na przykład możliwe jest, że chcesz używać zarówno słowników opartych na drzewie, jak i hashtable w swoim programie, w zależności od tego, co przechowujesz. Dzieliliby ADT, ale używali różnych implementacji.