Che cosa fanno i progettisti di linguaggi per decidere o dimostrare che una particolare funzionalità funziona correttamente?

11

Mi interessa la progettazione della lingua e in generale posso ragionare facilmente su caratteristiche ampiamente conosciute (ad es. ereditarietà, polimorfismo, delegati, lambda, catture, garbage collection, eccezioni, generici, varianze, riflessioni e così via), le loro interazioni in una particolare lingua, i modi in cui possono essere implementate, i loro limiti, ecc.

Negli ultimi mesi ho iniziato a leggere su Rust, che ha un sistema di proprietà che garantisce la sicurezza della memoria e una gestione delle risorse deterministica costringendo la vita degli oggetti a essere staticamente verificabile. Dal punto di vista di un utente semplice della lingua, potrei prendere il sistema quasi immediatamente.

Dal punto di vista di un progettista di linguaggi, tuttavia, mi ci è voluto un po 'per capire perché le cose in Rust sono esattamente come sono. Non sono riuscito a capire immediatamente il ragionamento dietro alcune restrizioni del sistema di proprietà, fino a quando non mi sono costretto a escogitare casi che violassero l'integrità di un sistema se non avesse quegli aspetti.

La mia domanda principale non ha nulla a che fare con Rust e la sua proprietà in particolare - ma sentiti libero di usarla come esempio nei tuoi commenti / risposte, se necessario.

Quando i progettisti di linguaggi progettano una nuova funzione, quale metodologia o processo usano per decidere che la funzionalità funzioni correttamente?

Con "nuovo" intendo che non è qualcosa che è già stato testato nelle lingue esistenti (e quindi la maggior parte del lavoro è stata eseguita da altri designer). Con "funziona correttamente" intendo che la funzione risolve correttamente il problema previsto ed è ragionevolmente a prova di proiettile. Con "ragionevolmente a prova di proiettile" intendo che nessun codice può essere scritto nella lingua o in un particolare sottoinsieme della lingua (ad esempio un sottoinsieme senza codice "non sicuro") che possa violare l'integrità della funzione.

  • È un processo di prova ed errore, nel senso che ti viene in mente una forma semplice della funzione, quindi prova a trovare modi per violarlo, quindi correggilo se lo violano con successo, quindi ripeti? E poi, quando non riesci a pensare ad altre possibili violazioni, speri che non rimanga niente e lo chiami un giorno?

  • O c'è un modo formale per provare (nel senso matematico della parola) che il tuo elemento funziona e quindi usare quella prova per ottenere con sicurezza la funzionalità (o per lo più correttamente ) dall'inizio?

(Devo dire che ho un background ingegneristico, non informatica, quindi se mi manca qualcosa che sarebbe ovvio per le persone CS, non esitare a segnalarlo.)

    
posta Theodoros Chatzigiannakis 18.03.2016 - 16:37
fonte

4 risposte

6

Ho difficoltà a trovare il riferimento esatto al momento, ma qualche tempo fa ho guardato diversi video di Simon Peyton Jones , che ha contribuito in maniera determinante al design di Haskell. È un ottimo oratore sulla teoria dei tipi, sul design del linguaggio e simili, a proposito, e ha molti video disponibili gratuitamente su youtube.

Haskell ha una rappresentazione intermedia che è essenzialmente un calcolo lambda accresciuto con poche semplici cose per renderlo più facile da lavorare. Il calcolo Lambda è stato usato e provato poiché un computer era solo una persona che calcolava le cose. Un punto interessante che Simon Peyton Jones fa spesso è che ogni volta che fanno qualcosa di selvaggio e pazzo con la lingua, sa che è fondamentalmente sano quando alla fine si riduce a quel linguaggio intermedio.

Altre lingue non sono così rigorose, piuttosto che favoriscono facilità d'uso o implementazione. Fanno le stesse cose che fanno gli altri programmatori per ottenere un codice di alta qualità: segui le buone pratiche di codifica e testalo fino alla morte. Una caratteristica come la semantica della proprietà di Rust sono sicura che ottiene sia un sacco di analisi e test formali per trovare casi d'angolo dimenticati. Spesso caratteristiche come quella iniziano come tesi di laurea di qualcuno.

    
risposta data 18.03.2016 - 17:21
fonte
8

Quindi per la lingua design , ci sono prove (o bug). Ad esempio, digita i sistemi. Tipi e linguaggi di programmazione è il libro canonico che descrive i sistemi di tipi e si concentra sulla dimostrazione della correttezza e della completezza del sistema di tipo. Le grammatiche hanno analisi simili e gli algoritmi (come il sistema di proprietà che descrivi) hanno il loro.

Per l'implementazione della lingua , è un codice come qualsiasi altro. Scrivi test unitari. Scrivi test di integrazione. Esegui revisioni del codice.

L'unica cosa che rende speciali le lingue è che sono (quasi sempre) infinite. Non puoi letteralmente testare per tutti gli input. E (idealmente) sono usati da molte persone, facendo cose strane e interessanti, quindi qualsiasi bug nella lingua sarà alla fine.

In pratica , relativamente poche lingue usano le dimostrazioni per verificare la loro funzionalità e finiscono con un misto di opzioni che menzioni.

    
risposta data 18.03.2016 - 17:02
fonte
4

La prima e più difficile cosa di cui un progettista linguistico deve occuparsi quando introduce nuove funzionalità, è mantenere la sua lingua coerente:

  • come può essere integrato nella grammatica della lingua senza rompere il codice esistente (questo può essere provato matematicamente)
  • come si relaziona con le funzionalità esistenti (ad esempio se hai fissato gli array indicizzati 0..n-1, non introduci una nuova caratteristica di matrice variabile indicizzata 1..n) (questa è la parte artistica del progetto)
  • in che modo è possibile implementare la funzionalità attraverso l'intera toolchain in modo che la nuova funzionalità possa essere assorbita dall'ecosistema, dai produttori di strumenti e dai programmatori (la fattibilità può essere dimostrata con una dimostrazione del concetto, ma la piena implementazione è un approccio simile a programmazione)

Per guidare in questa materia, un designer si basa su un insieme di regole e principi di progettazione. Questo approccio è molto ben descritto in " La progettazione e l'evoluzione di C ++ " di Bjarne Stroustrup , uno dei libri rari dedicati al design della lingua. Ciò che è molto interessante è vedere che le lingue sono raramente progettate nel vuoto e il designer guarda anche come le loro lingue hanno implementato funzionalità simili. Un'altra fonte (online e gratuita) è i principi di progettazione per la lingua java .

Se osservi i procedimenti pubblici dei comitati di standardizzazione, vedrai che si tratta più di un processo di errore di prova. Ecco un esempio sul modulo C ++ un concetto completamente nuovo da introdotto nella prossima versione della lingua. E qui un'analisi redatta dopo alcune modifiche linguistiche , per valutarne il successo. E qui il Processo della comunità Java per definire nuove specifiche Java, come una nuova API . Vedrai che questo lavoro viene eseguito da diversi esperti che redigono creativamente un concept paper e una prima proposta. Quindi queste proposte vengono esaminate da una più ampia comunità / comitato che può modificare la proposta per garantire un maggiore livello di coerenza.

    
risposta data 18.03.2016 - 22:05
fonte
4

Come testare le caratteristiche del linguaggio di programmazione? È un'ottima domanda e non sono sicuro che lo stato dell'arte sia all'altezza del lavoro.

Ogni nuova funzione può interagire con tutte le altre funzionalità. (Questo riguarda la lingua, i documenti, i compilatori, i messaggi di errore, gli IDE, le librerie, ecc.) Le funzionalità si combinano per aprire una scappatoia? Per creare brutti casi limite?

Anche i progettisti di linguaggi molto intelligenti che lavorano duramente per mantenere la solidità del tipo scoprono violazioni come questo bug di ruggine . Il sistema di tipo di Rust non è così ovvio per me, ma penso che in questo caso avere la vita del valore del sistema del tipo significa che la vita "sottotipizzazione" si scontra con aspettative di sottotipizzazione, coercizione, riferimenti e mutabilità ordinarie, creando una scappatoia in cui una percentualestatic lifetime ref può puntare a un valore allocato allo stack e successivamente diventare un riferimento ciondolante.

By "works properly" I mean that the feature solves the intended problem correctly, and it's reasonably bulletproof.

Per le lingue destinate a essere linguaggi di produzione , cioè utilizzati da molti programmatori per creare software di produzione affidabile, "funziona correttamente" deve inoltre significare risolvere correttamente il problema previsto per il pubblico previsto .

In altre parole, usabilità è importante tanto per la progettazione della lingua quanto per altri tipi di design. Ciò comporta (1) design per l'usabilità (ad es. Conoscendo il tuo pubblico) e (2) test di usabilità.

Un esempio di questo argomento è " I programmatori sono persone, anche , Il linguaggio di programmazione e i progettisti di API possono imparare molto dal campo della progettazione di fattori umani. "

Un esempio di domanda SE su questo argomento è È stata verificata la sintassi di qualsiasi linguaggio di programmazione?

Un test di usabilità di esempio ha preso in considerazione l'estensione di una funzione di iterazione di elenchi (non ricordo in quale lingua) prendere più elenchi. Le persone si aspettavano che iterassero attraverso gli elenchi in parallelo o attraverso il prodotto incrociato? I progettisti di linguaggi sono stati sorpresi dai risultati del test di usabilità.

Lingue come Smalltalk, Python e Dart sono state progettate con un'enfasi sull'usabilità. Chiaramente Haskell non lo era.

    
risposta data 23.03.2016 - 01:43
fonte

Leggi altre domande sui tag