Czy struktury danych powinny być zintegrowane z językiem (jak w Pythonie) czy powinny być zapewnione w standardowej bibliotece (jak w Javie)?

21

W Pythonie i najprawdopodobniej w wielu innych językach programowania wspólne struktury danych można znaleźć jako zintegrowaną część języka podstawowego z ich własną dedykowaną składnią. Jeśli odłożymy na bok zintegrowaną składnię list LISP, nie mogę myśleć o żadnym innym znanym mi języku, który zapewnia jakąś strukturę danych nad tablicą jako zintegrowaną część ich składni, chociaż wszystkie (chyba C) wydają się zapewniać je w standardowej bibliotece.

Z perspektywy projektowania języka, jakie są Twoje opinie na temat posiadania konkretnej składni struktur danych w języku podstawowym? Czy to dobry pomysł i czy cel języka (itp.) Zmienia, jak dobry może być wybór?

Edycja: Przykro mi z powodu (najwyraźniej) nieporozumień dotyczących tego, które struktury danych mam na myśli. Mówię o podstawowych i często używanych, ale wciąż nie najbardziej podstawowych. Wyklucza to drzewa (zbyt skomplikowane, niezbyt częste), stosy (zbyt rzadko używane), tablice (zbyt proste), ale obejmuje np. Zestawy, listy i mapy skrótów.

Anto
źródło
1
Czy wykluczamy obiekt i skrót mapy?
Orbling
3
@Anto: Cóż, wiele języków ma tablice skrótów w postaci tablic asocjacyjnych, Perl, PHP, JS (technicznie tutaj obiekt) itp.
Orbling
1
Być może mógłbyś sprecyzować, o których strukturach danych myślisz, poza tablicami, listami, tablicami skrótów / tablicami asocjacyjnymi?
FrustratedWithFormsDesigner
1
Uwzględnij mapy skrótów, listy i wszystko bardziej zaawansowane jako „złożone struktury danych”, a tablice wyrzucaj jako zbyt proste.
Anto
1
Wydaje mi się, że bardziej sensownym tytułem byłoby: „Jakie struktury danych powinny być zawarte w języku, a co w bibliotece?” Znacząca odpowiedź zależy w dużej mierze od języka: im bardziej czysto biblioteka jest zintegrowana z tym językiem, tym bardziej rozsądne jest przenoszenie struktur do biblioteki.
Jerry Coffin

Odpowiedzi:

13

To zależy od języka.

Niektóre przykłady (nieco skradzione z innych odpowiedzi):

  • Perl ma specjalną składnię dla tablic skrótów, tablic, ciągów. Perl jest często używany do tworzenia skryptów, są one przydatne do tworzenia skryptów.
  • Matlab ma specjalną składnię list, macierzy i struktur. Matlab służy do wykonywania matematyki macierzowej i wektorowej w inżynierii.
  • Ciągi i tablice obsługi Java / .NET. Są to języki ogólnego przeznaczenia, w których często używane są tablice i ciągi (coraz mniej przy użyciu nowych klas kolekcji)
  • Tablice obsługi C / C ++. Są to języki, które nie ukrywają przed Tobą sprzętu. Ciągi są częściowo obsługiwane (bez konkatenacji, użyj strcpy itp.)

Myślę, że to zależy od celu / ducha / odbiorców twojego języka; jak abstrakcyjny i jak daleko od sprzętu ma być. Ogólnie języki, które obsługują listy jako prymitywy, umożliwiają tworzenie nieskończenie długich list. Podczas gdy niski poziom, taki jak C / C ++, nigdy by ich nie miał, ponieważ nie jest to celem, duch tych języków.

Według mnie zbieranie śmieci odbywa się według tej samej logiki: czy odbiorcy w Twoim języku dbają o dokładne określenie, kiedy i czy pamięć jest przydzielana czy zwalniana? Jeśli tak, malloc / free; jeśli nie, to odśmiecanie.

EarlNameless
źródło
6
Jest to złe miejsce na użycie terminu „C / C ++”, ponieważ obecność typów szablonów wysokiego poziomu w C ++ jest główną różnicą między tymi dwoma językami.
dan04,
Odśmiecanie można wykonać w sposób deterministyczny, potrzebujesz tylko rodzajów liniowych (lub zamiennika ich biednego człowieka: RAII).
pyon
@ EduardoLeón, chociaż można nazwać zbieranie śmieci na deterministycznego punktu, nie sądzę, jak długo to będzie działać, jest deterministyczny (z tego samego powodu, że malloci newsą niedeterministyczne w C / C ++).
EarNameless
@ PearlNameless: Jest deterministyczny w stosunku do wykorzystania zasobu: typy liniowe (lub typy unikatowości, które są podobne) powodują, że jest to błąd typu (a zatem błąd kompilacji), aby nie zwolnić zasobów (modulo możliwości, nie przechwycony przez typ system, o nienormalnym zakończeniu programu) lub użyć ich po ich usunięciu.
pyon
5

Perl ma mapy skrótów, a PL / SQL obsługuje rekordy, a ja mam bardzo mgliste wspomnienia o matlabie posiadającym składnię do obsługi wektorów i macierzy o różnych wymiarach (chociaż mogę się mylić w tej kwestii i można argumentować, że są to typy danych, a nie dane struktur ) ... Powiedziałbym, że dobrze jest mieć natywne wsparcie dla bardzo popularnych struktur. Zwykle wydaje się, że tablice i tablice skrótów / tablice asocjacyjne są najczęstszymi strukturami obsługiwanymi natywnie i prawdopodobnie są również najczęściej używane.

Nie zapominaj, że jeśli dodasz natywną obsługę składni dla innych struktur, takich jak drzewa binarne, struktury te zostaną również zaimplementowane przez narzędzia wspierające język (kompilator / środowisko wykonawcze / itp.). Dla ilu strucutres chcesz zbudować wsparcie?

Będziesz musiał wymyślić nową notację dla mniej powszechnie obsługiwanych struktur ... Keep It Simple !.

FrustratedWithFormsDesigner
źródło
Nie trzeba wymyślać dosłownej składni np. Drzew - są one rzadsze, nawet nie są dostępne w wielu językach! Tym samym argumentem można sprzeciwić się włączeniu operatorów, ponieważ „trzeba wymyślić nową notację dla rzadziej używanych operacji”.
@delnan: Zrozumiałem to z perspektywy projektowania nowego języka i zastanawiania się, czy struktury danych poza tablicami powinny być natywnie obsługiwane przez (prawdopodobnie) nową składnię, czy też powinny być obsługiwane przez włączenie biblioteki.
FrustratedWithFormsDesigner
Cóż, pierwsze zdanie wyraźnie mówi o „wspólnych strukturach danych”, więc zakładam, że OP nie jest wystarczająco szalone, aby spróbować dodać specjalną składnię dla każdej niejasnej struktury danych, jaką kiedykolwiek wymyślono.
@delnan: ... a następnie OP wyklucza listy i tablice LISP (ogólnie) „... odłóż na bok zintegrowaną składnię list LISP, nie mogę wymyślić żadnego innego języka, który znam, który zapewnia pewien rodzaj struktura danych powyżej tablicy jako integralna część ich składni”... więc pomyślałem były rozpatrzone struktur danych bardziej egzotyczne niż tablic / list ...
FrustratedWithFormsDesigner
Tak (zinterpretowałem „ponad tablicami” jako „inne wspólne struktury danych”), ale nic w pytaniu nie wskazuje na „stwórzmy literały dla każdej struktury danych, którą mamy”. Można stwierdzić, że powinno to ograniczać się do rozsądnych, ale nie sądzę, że możemy powiedzieć „zły pomysł” tylko z powodu tego założenia .
5

Moim ulubionym przykładem jest Lua . Lua ma tylko jeden wbudowany typ danych, „ tabelę ”, ale jego elastyczność i szybkość oznaczają, że faktycznie używasz ich zamiast zwykłych tablic, połączonych list, kolejek, map, a nawet są one podstawą obiektowych funkcji Lua (tj. zajęcia).

Lua jest tak niesamowicie prostym językiem, ale elastyczność struktury danych tabeli czyni go również dość potężnym.

Dean Harding
źródło
2
Obiekty JavaScript są w rzeczywistości takie same - tablice są po prostu obiektami o właściwościach numerycznych i długości.
Tikhon Jelvis,
1
Tabele Lua różnią się od obiektów JavaScript: W JavaScript {}nie ma [], w Lua masz {}jedno i drugie. Tabele Lua lepiej porównać z listami w Lisp.
Jakob,
W JavaScript myślę, że „wszystko jest obiektem” - w tym tablice - ale nie wszystko jest tablicą. W Lua wszystko jest stołem.
Dean Harding,
3

Nie musisz mieć dedykowanej składni dla każdego typu danych wysokiego poziomu. Na przykład tolerowanie jest set([1, 2, 3])(tak jak w Pythonie 2.x) zamiast {1, 2, 3}.

Ważną rzeczą jest, aby mieć jakiś wygodny sposób do budowy struktury danych na wysokim poziomie. To, czego chcesz uniknąć, to kod:

s = set()
s.add(1)
s.add(2)
s.add(3)

która denerwuje mnie bardzo, gdy używam std::vector, std::setoraz std::mapw języku C ++. Na szczęście nowy standard będzie miał std::initializer_list.

dan04
źródło
3

Moim zdaniem jest to niesamowicie prosty dodatek, który może przydać się zaskakująco często, przynajmniej jeśli jest wykonany ostrożnie - tj. Co najwyżej w przypadku krotek, list, map i zestawów, ponieważ mają one dobrze rozpoznane literały.

  • Dodawanie do języka jest tanie. Ten kosztowny budżet na złożoność nie kosztuje wiele:
    • gramatyka jest w zasadzie someBracket {expr ','} someBracketlubsomeBracket {expr ':' expr ','} someBracket , z pewnymi martwymi prostymi dodatkami, jeśli chcesz rzeczy takich jak opcjonalne przecinki końcowe. W literały pływak może łatwo być dłuższy w gramatyce.
    • W wielu językach żaden z popularnych literałów nie koliduje z istniejącą składnią (wyjątek, który mogę wymyślić, to język z blokami przypominającymi nawiasy klamrowe jako wyrażenia, operator przecinka i bez średnika, jak w {1, 2})
    • Semantykę można zdefiniować w mniej niż pięciu zdaniach, przy czym nieformalna wersja brzmi: „Utwórz nową kolekcję $, a następnie wywołaj .add/ .append/.setItem jeden raz dla podanych wyrażeń z tym (tymi) wyrażeniem (-ami) jako argumentami”.
  • Ze względu na poprzedni trzeci punkt jest również bardzo łatwy do wdrożenia.
  • Jest niezwykle przydatny, gdy go potrzebujesz, i nie ma (nie musi) wpływać na składnię innych elementów, tzn. Nie płacisz za to, gdy go nie używasz.
komar
źródło
3

Clojure jest seplenieniem, ale wspiera

Lists: (x1 x2)
Vectors: [x1 x2]
Maps: {k1 v1 k2 v2}
Sets: #{x1 x2}
WuHoUnited
źródło
2

Im więcej struktur danych masz w samym języku, tym trudniej będzie się go nauczyć. Może to być osobista preferencja, ale ja wolę prostszy język, a wtedy biblioteki mogą dostarczyć wszelkie dodatki.

Języki zaprojektowane dla określonych pól mogą czasami korzystać z wbudowanych w język określonych struktur danych, takich jak Matlab. Ale zbyt wielu może cię przytłoczyć.

ergodicsum
źródło
2

Aby język był naprawdę przydatny, musi wykonywać określone zadania od razu po wyjęciu z pudełka. Ponieważ praktyczne codzienne programowanie wymaga narzędzi, które rozwiązują ich problemy na pewnym ogólnym poziomie. Minimalizm wygląda kompaktowo i fajnie, ale jeśli chcesz zacząć rozwiązywać duże, ale powtarzające się problemy, potrzebujesz poziomu abstrakcji, na którym możesz budować.

Myślę więc, że języki programowania powinny zapewniać obsługę najczęściej używanych struktur danych w składni dla zadań, dla których język jest przeznaczony.

kamaal
źródło
2

Ogólnie uważam, że wygodne jest posiadanie literałów do list, zestawów i tak dalej. Ale czasem mnie to wkurza, że ​​nie wiem nic o faktycznej implementacji - powiedzmy - listy Python lub tablicy JavaScript. Jedyne, czego mogę być pewien, to to, że ujawniają dany interfejs.

Jako punkt odniesienia dla ekspresji językowej przyjmuję, jak dobrze potrafi pisać własne struktury danych jako biblioteki i jak wygodnie jest z nich korzystać.

Na przykład Scala zapewnia różne kolekcje z różnymi gwarancjami wdrożenia i wydajności. Wszystkie z nich są zaimplementowane w samej Scali, a składnia ich użycia jest tylko nieco bardziej złożona niż gdyby były wbudowane i miały wsparcie w czasie wykonywania.

Jedyną podstawową strukturą, która naprawdę potrzebuje wsparcia ze strony samego środowiska wykonawczego, przynajmniej w języku zarządzanym, jest tablica: jeśli nie zarządzasz pamięcią, ciężko będzie ci uzyskać kilka sąsiednich bajtów. Każda inna struktura może być zbudowana z tablic i wskaźników (lub odniesień).

Andrea
źródło
1

APL (i powiązane współczesne warianty, A +, J i K) mają skalar, wektor i macierz jako najwyższej klasy struktury danych.

Tak, mogą być przestarzałe jako zwykłe warianty tablicy. Ale są też wolne od złożonych deklaracji i nie pochodzą z oddzielnej biblioteki, czują się jak złożone struktury danych, które są pierwszorzędną częścią języka.

S.Lott
źródło
APL ma również zagnieżdżone tablice, a tablice nie muszą mieć jednorodnego typu danych, co sprawia, że ​​są to bardzo potężne struktury danych.
RFlack
1

Z perspektywy projektowania języka, jakie są Twoje opinie na temat posiadania konkretnej składni struktur danych w języku podstawowym? Czy to dobry pomysł i czy cel języka (itp.) Zmienia, jak dobry może być wybór?

Literały list i map oraz wygodna składnia zamknięcia są podstawowymi cechami języków wysokiego poziomu.

Różnica między tym kodem Java:

Thing t = new Thing();
t.setFoo(3);
t.setBar(6.3);
t.setBaz(true);

i ten kod Groovy:

t = new Thing(foo: 3, bar: 6.3, baz: true)

jest ogromny. Jest to różnica między 40 000 programem liniowym a 10 000 programem liniowym. Składnia ma znaczenie.

Kevin Cline
źródło
W języku C # można wykonać: var t = new Thing(foo: 3, bar: 6.3, baz: true);- tylko 4 dodatkowe znaki.
Job
to właściwie ta sama liczba; kod Groovy powinien brzmieć „def t = ...”
Kevin Cline,
1

Oczywiście zależy to od zastosowania języka programowania, ale w przypadku języków wyższego poziomu praca z dowolną wspólną strukturą danych powinna być jak najwygodniejsza. Przykłady można znaleźć na liście abstrakcyjnych typów danych w Wikipedii. Znalazłem następujące podstawowe zasady (ale chciałbym też usłyszeć inne opinie):

  • uporządkowane sekwencje (1-wymiarowe): tablica, kolejka, stos, listy ...
  • uporządkowane struktury wielowymiarowe : tabela, wektor, macierz ..
  • mapy : mapa , słownik, zestaw, multimapa ... (1-wymiarowy)
  • mapy wielowymiarowe : funkcje, mapy map ...
  • typy wykresów : drzewa, skierowane wykresy ...

Możesz emulować dowolną strukturę z dowolną inną strukturą - zależy to tylko od tego, jak łatwy i przejrzysty język programowania na to pozwala. Na przykład:

  • kolejki i stosy można łatwo emulować za pomocą tablic lub list, te ostatnie zapewniają operacje takie jak push, pop, shift itp.
  • uporządkowane sekwencje można emulować za pomocą map z klawiszami numerycznymi
  • zestawy mogą być emulowane przez mapy, które odwzorowują wartości na wartość logiczną
  • większość typów wykresów można emulować poprzez zagnieżdżanie sekwencji lub map
  • funkcji można użyć do emulacji map, jeśli można łatwo zmodyfikować ich definicję

Większość języków zapewnia co najmniej jeden typ dla uporządkowanych sekwencji, jeden dla map jednowymiarowych i jeden dla map wielowymiarowych, ograniczony do funkcji. Osobiście często brakuje mi zestawów i uporządkowanych struktur wielowymiarowych w językach takich jak Perl, PHP, JavaScript, Lua ... ponieważ ich emulowanie nie jest wystarczająco wygodne.

Jakob
źródło
1

Myślę, że złym pomysłem jest posiadanie zbyt wielu uprzywilejowanych typów danych, które mają specjalną składnię. To niepotrzebnie komplikuje składnię języka, utrudniając czytanie kodu, utrudniając początkującym naukę i utrudniając opracowanie narzędzi dla języka.

Można zrobić wyjątek dla niewielkiej liczby bardzo popularnych typów struktur danych. Prawdopodobnie pozwoliłbym maksymalnie:

  • Tablice o stałej długości
  • Zestawy
  • Hashmapy
  • Sekwencje / listy
  • Rekordy / struktury / klasy

Wszystko, co jest bardziej wyrafinowane niż to, powinno prawdopodobnie zostać pozostawione bibliotekom do obsługi, używając normalnej składni języka dla niestandardowych typów danych.

W szczególności rzeczy takie jak drzewa czerwone / czarne, kolejki priorytetowe itp. Mają całkiem sporo możliwych opcji implementacji, więc nie jest rozsądne upiec konkretną implementację w języku podstawowym. Lepiej pozwolić ludziom wybrać najbardziej odpowiednie wdrożenie dla ich sytuacji. Przykłady opcji implementacji, których projektant języka może nie chcieć ograniczać:

  • Zmienny czy niezmienny?
  • Pozwala na wartości zerowe czy nie?
  • Zsynchronizowany czy nie?
  • Wspierany przez trwałe przechowywanie, czy nie?
mikera
źródło