Le strutture di dati dovrebbero essere integrate nella lingua (come in Python) o essere fornite nella libreria standard (come in Java)?

21

In Python, e molto probabilmente in molti altri linguaggi di programmazione, le strutture dati comuni possono essere trovate come parte integrante del core language con la loro sintassi dedicata. Se mettiamo da parte la sintassi della lista integrata di LISP, non riesco a pensare ad altri linguaggi che conosco che forniscono una sorta di struttura dati sopra l'array come parte integrante della loro sintassi, sebbene tutti loro (ma C, immagino) sembra fornirli nella libreria standard.

Da una prospettiva di progettazione linguistica, quali sono le tue opinioni sull'avere una sintassi specifica per le strutture di dati nel linguaggio principale? È una buona idea, e lo scopo della lingua (ecc.) Cambia quanto potrebbe essere buona questa scelta?

Modifica: mi dispiace (apparentemente) causando una certa confusione su quali strutture di dati intendo. Parlo di quelli di base e comunemente usati, ma non ancora quelli di base. Ciò esclude gli alberi (troppo complessi, non comuni), le pile (utilizzate troppo raramente), le matrici (troppo semplici) ma che includono per es. insiemi, elenchi e hashmap.

    
posta Anto 04.04.2011 - 22:11
fonte

13 risposte

13

Dipende dal significato della lingua.

Alcuni esempi (in qualche modo rubati da altre risposte):

  • Perl ha una sintassi speciale per hashtables, array, stringhe. Perl è spesso usato per lo scripting, questi sono utili per lo scripting.
  • Matlab ha una sintassi speciale per liste, matrici, strutture. Matlab è per fare matrix e matematica vettoriale per l'ingegneria.
  • Stringa e array di supporto Java / .NET. Questi sono linguaggi di uso generale in cui vengono spesso utilizzati array e stringhe (sempre meno con l'uso di nuove classi di raccolta)
  • matrici di supporto C / C ++. Queste sono lingue che non nascondono l'hardware da te. Le stringhe sono parzialmente supportate (nessuna concatenazione, uso strcpy, ecc.)

Penso che dipenda da quale sia lo scopo / lo spirito / il pubblico della tua lingua; quanto è astratto e quanto lontano dall'hardware vuoi che sia. Generalmente le lingue che supportano gli elenchi come primitive ti permettono di creare liste infinitamente lunghe. Mentre il livello basso come C / C ++ non avrebbe mai questi, perché quello non è l'obiettivo, lo spirito di quelle lingue.

Per me, la garbage collection segue la stessa logica: il pubblico della tua lingua si preoccupa di sapere esattamente quando e se la memoria viene allocata o liberata? Se si, malloc / free; se no, quindi garbage collection.

    
risposta data 05.04.2011 - 06:22
fonte
5

Perl ha hashmaps e PL / SQL supporta i record, e ho memorie molto nebbiose di matlab che hanno sintassi per supportare vettori e matrici di tutte le diverse dimensioni (anche se potrei sbagliarmi su questo e si potrebbe sostenere che questi sono dati tipi non dati strutture ) ... Direi che avere un supporto nativo per strutture molto comuni è bello avere. Di solito sembra che gli array e le hashmap / array associativi siano le strutture supportate in modo nativo più comuni e probabilmente sono anche quelle più comunemente usate.

Non dimenticare che se si aggiunge il supporto della sintassi nativa per altre strutture come gli alberi binari, anche queste strutture sono implementate dagli strumenti di supporto del linguaggio (compiler / runtime / etc). Per quante strutture vuoi creare supporto?

Dovrai inventare una nuova notazione per le strutture meno comunemente supportate nativamente ... Keep It Simple!.

    
risposta data 04.04.2011 - 22:27
fonte
5

Il mio esempio preferito qui è Lua . Lua ha solo un tipo di dati incorporato, la " tabella ", ma la sua flessibilità e velocità significano che tu effettivamente usi al posto di array regolari, liste collegate, code, mappe e sono anche la base per le funzionalità orientate agli oggetti di Lua (ad es. le classi).

Lua è un linguaggio straordinariamente semplice, ma la flessibilità della struttura dei dati della tabella lo rende piuttosto potente.

    
risposta data 04.04.2011 - 23:38
fonte
3

Non è necessario avere una sintassi dedicata per ogni tipo di dati di alto livello. Ad esempio, è tollerabile avere set([1, 2, 3]) (come ha fatto Python 2.x) invece di {1, 2, 3} .

L'importante è avere qualche modo conveniente per costruire una struttura di dati di alto livello. Quello che vuoi evitare è un codice come:

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

che mi infastidisce enormemente quando uso std::vector , std::set e std::map in C ++. Per fortuna, il nuovo standard avrà std::initializer_list .

    
risposta data 05.04.2011 - 15:25
fonte
3

Secondo me, è un'aggiunta straordinariamente semplice che può tornare utile a sorpresa, spesso, almeno se fatta con cautela, vale a dire al massimo per le tuple, gli elenchi, le mappe e gli insiemi come quelli con valori letterali ben noti.

  • È economico aggiungere a una lingua. Non ti costa molto di quel prezioso budget di complessità:
    • la grammatica è fondamentalmente someBracket {expr ','} someBracket o someBracket {expr ':' expr ','} someBracket , con alcuni extra semplici morti se vuoi cose come le virgole trailing opzionali. i letterali float possono facilmente essere più lunghi nella grammatica.
    • In molte lingue, nessuno dei letterali popolari si scontrano con la sintassi esistente (un'eccezione che posso pensare è una lingua con blocchi simili a parentesi come espressioni, un operatore virgola e nessun punto e virgola, come in {1, 2} )
    • La semantica può essere definita in meno di cinque frasi, la versione informale è "Istanziare una nuova raccolta $, quindi chiamare .add / .append / .setItem una volta per determinate espressioni con quella (quelle) espressione (s) ) come argomenti ".
  • A causa del precedente terzo punto, è anche molto facile da implementare.
  • È incredibilmente utile quando ne hai bisogno, e non (ha bisogno di) di influire sulla sintassi di altri elementi, cioè non lo "paghi" per quando non lo usi.
risposta data 04.04.2011 - 22:34
fonte
3

Clojure è un lisp ma supporta

Lists: (x1 x2)
Vectors: [x1 x2]
Maps: {k1 v1 k2 v2}
Sets: #{x1 x2}
    
risposta data 05.04.2011 - 00:29
fonte
2

Più strutture di dati hai nella lingua stessa più difficile sarà la lingua da apprendere. Potrebbe essere una preferenza personale, ma io preferisco un linguaggio più semplice e quindi eventuali extra possono essere forniti dalle librerie.

Le lingue progettate per campi specifici a volte possono trarre vantaggio dall'avere alcune strutture dati integrate nel linguaggio come Matlab. Ma troppi possono sopraffarti.

    
risposta data 05.04.2011 - 04:59
fonte
2

Perché un linguaggio sia veramente utile, deve svolgere un certo grado di compiti fuori dagli schemi. Perché la pratica programmazione quotidiana richiede strumenti che risolvano i loro problemi ad un livello generico. Il minimalismo sembra compatto e interessante, ma quando vuoi iniziare a utilizzare per risolvere problemi grandi ma ripetuti, hai bisogno di un livello di astrazione su cui puoi costruire.

Quindi penso che i linguaggi di programmazione dovrebbero fornire supporto per le strutture di dati più comunemente usate nella sintassi per le attività per cui è stato progettato il linguaggio.

    
risposta data 05.04.2011 - 07:04
fonte
2

In generale trovo conveniente avere letterali per elenchi, set e così via. Ma a volte mi infastidisce il fatto che io non sappia nulla dell'attuale implementazione di - diciamo - l'elenco Python o l'array Javascript. L'unica cosa di cui posso essere certo è che espongono un'interfaccia specifica.

Prendo come punto di riferimento di un linguaggio espressivo quanto possa scrivere le proprie strutture dati come librerie e quanto sia conveniente usarle.

Ad esempio, Scala offre varie raccolte con diverse garanzie di implementazione e prestazioni. Tutti sono implementati in Scala stessa, e la sintassi per usarli è solo leggermente più complessa rispetto a se fossero incorporati e avessero il supporto di runtime.

L'unica struttura di base che ha realmente bisogno del supporto del runtime stesso, almeno in un linguaggio gestito, è l'array: se non gestisci la memoria, avrai difficoltà a ottenere un mucchio di byte adiacenti. Ogni altra struttura può essere costruita da matrici e puntatori (o riferimenti).

    
risposta data 28.05.2014 - 18:07
fonte
1

L'APL (e le relative varianti moderne, A +, J e K) hanno scalare, vettore e matrice come strutture di dati di prima classe.

Sì, possono essere deprecati come mere varianti su array. Ma sono anche liberi da dichiarazioni complesse e non provengono da una libreria separata, si sentono come strutture dati complesse che sono una parte di prima classe della lingua.

    
risposta data 04.04.2011 - 23:22
fonte
1

From a language design perspective, what are your opinions on having a specific syntax for data structures in the core language? Is it a good idea, and does the purpose of the language (etc.) change how good this could be of a choice?

Elenchi e mappa letterali e una comoda sintassi di chiusura sono caratteristiche essenziali dei linguaggi di alto livello.

La differenza tra questo codice Java:

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

e questo codice Groovy:

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

è enorme. È la differenza tra un programma di 40.000 linee e un programma di 10.000 linee. La sintassi è importante.

    
risposta data 05.04.2011 - 06:55
fonte
1

Sicuramente dipende dall'applicazione del linguaggio di programmazione, ma per i linguaggi di livello superiore dovrebbe essere il più comodo possibile per lavorare con qualsiasi struttura dati comune. Dai un'occhiata alla lista dei tipi di dati astratti in Wikipedia per gli esempi. Ho trovato i seguenti principi di base più comuni (ma mi piacerebbe sentire anche altre opinioni):

  • sequenze ordinate (1-dimensionale): array, coda, stack, elenchi ...
  • strutture multidimensionali ordinate : tabella, vettore, matrice ..
  • mappe : hashmap, dizionario, set, multimap ... (1-dimensionale)
  • mappe multidimensionali : funzioni, mappe di mappe ...
  • tipi di grafici : alberi, grafici diretti ...

È possibile emulare qualsiasi struttura con qualsiasi altra struttura - dipende solo da quanto semplice e chiaro il linguaggio di programmazione lo consente. Ad esempio:

  • la coda e lo stack sono facili da emulare con matrici o elenchi, di questi ultimi offrono operazioni come push, pop, shift ecc.
  • le sequenze ordinate possono essere emulate con mappe che hanno i tasti numerici
  • gli insiemi possono essere emulati dalle mappe che mappano i valori su un valore booleano
  • la maggior parte dei tipi di grafici può essere emulata nidificando sequenze o mappe
  • Le funzioni
  • possono essere utilizzate per emulare le mappe se è possibile modificare facilmente la loro definizione

La maggior parte delle lingue fornisce almeno un tipo per sequenze ordinate, una per le mappe monodimensionali e una per le mappe multidimensionali, limitate alle funzioni. Personalmente, mi mancano spesso set e strutture multidimensionali ordinate in linguaggi come Perl, PHP, JavaScript, Lua ... perché emularli non è abbastanza conveniente.

    
risposta data 06.04.2011 - 22:25
fonte
1

Penso che sia una cattiva idea avere troppi tipi di dati privilegiati che ottengono una sintassi speciale. Ciò complica inutilmente la sintassi del linguaggio, rendendo il codice più difficile da leggere, rendendo più difficile l'apprendimento da parte dei principianti e rendendo più difficile lo sviluppo di strumenti per la lingua.

È corretto fare un'eccezione per un piccolo numero di tipi di strutture dati molto comuni. Probabilmente lo permetterò al massimo:

  • Matrici di lunghezza fissa
  • Imposta
  • HashMaps
  • Sequenze / elenchi
  • Records / structs / classes

Qualunque cosa più sofisticata di quella dovrebbe essere lasciata alle librerie da gestire, usando la normale sintassi del linguaggio per i tipi di dati personalizzati.

In particolare, cose come gli alberi rosso / nero, le code prioritarie ecc. hanno molte opzioni di implementazione possibili, quindi non è saggio utilizzare una particolare implementazione nel linguaggio di base. È meglio consentire alle persone di scegliere l'implementazione più appropriata per la loro situazione. Esempi di scelte di implementazione che potrei non volere che un designer di linguaggio limiti la mia scelta su:

  • Mutevole o immutabile?
  • Permette null o no?
  • Sincronizzato o no?
  • Supportato da archiviazione persistente o no?
risposta data 24.04.2012 - 11:50
fonte

Leggi altre domande sui tag