Qual è il fondamento matematico per i valori di prima / seconda / terza classe nei linguaggi di programmazione?

19

Aggiunto

Ho appena trovato due domande correlate

link

link

Nei linguaggi di programmazione, da Pragmatica del linguaggio di programmazione di Michael Scott

In general, a value in a programming language is said to have first-class status if it can be passed as a parameter, returned from a subroutine, or assigned into a variable. Simple types such as integers and characters are first-class values in most programming languages. By contrast, a “second-class” value can be passed as a parameter, but not returned from a subroutine or assigned into a variable, and a “third-class” value cannot even be passed as a parameter.

Labels are third-class values in most programming languages, but second-class values in Algol. Subroutines display the most variation. They are first-class values in all functional programming languages and most scripting languages. They are also first-class values in C# and, with some restrictions, in several other imperative languages, including Fortran, Modula-2 and -3, Ada 95, C, and C++. 11 They are second-class values in most other imperative languages, and third-class values in Ada 83.

  1. Qual è il fondamento matematico per la prima / seconda / terza classe valori nei linguaggi di programmazione?

    La terminologia mi ricorda la logica del primo / secondo ordine, ma sono loro correlato?

  2. Mi sembra che la differenza tra loro sia specifica caso può essere usato un valore

    • passato come parametro,
    • restituito da una subroutine o
    • assegnato a una variabile.

    Perché i casi specifici sono importanti, mentre non altri casi no menzionato?

Grazie.

    
posta Tim 26.09.2016 - 23:16
fonte

6 risposte

45

Non ce n'è, ed è piuttosto arbitrario.

L'unica distinzione utile è tra prima classe e tutti gli altri. Ogni caso che si trova nella parentesi "altro" ha un proprio insieme di regole distinte in ciascun caso e il fatto di raggrupparle tutte insieme non è molto utile. "Prima classe" significa "Non devi cercare le regole", in sostanza, e "altro" è "Devi imparare le regole".

Ad esempio in C ++ le singole funzioni sono valori di prima classe, purché siano stateless. I set di sovraccarico non sono altro che lambda. In C # le funzioni sono generalmente valori di prima classe, ma ci sono alcuni casi imbarazzanti che si presentano quando si ha a che fare con l'inferenza di tipo che impedisce loro di essere in tutti i casi.

    
risposta data 26.09.2016 - 23:28
fonte
11

Sono d'accordo con DeadMG, l'importante distinzione è tra prima classe e "tutto il resto". Tuttavia, c'è un modo più familiare per classificare la differenza.

I valori di prima classe sono dati, gli altri sono codici. (in parole povere: sono sicuro che ci sono delle eccezioni, ma questa è una buona approssimazione che vale per le lingue del mondo reale.)

In alcune lingue puoi trattare il codice come dati. I linguaggi funzionali sono famosi per questo: alcuni di questi ti permettono di cambiare il codice del programma mentre è in esecuzione (le fondamenta della programmazione genetica ).

Lingue come C e C ++ consentono di prendere l'indirizzo delle funzioni: mentre non è possibile modificarle, è possibile passare funzioni come parametri ad altre funzioni. Il C ++ ha anche lo zucchero sintattico di functors . L'idea è di creare un oggetto intero che, in superficie, sembra comportarsi come una funzione e può essere passato in giro come se fosse un dato. Ciò che altrimenti è un valore di classe inferiore può essere considerato un valore di prima classe.

Matematicamente, penso che il modo migliore sia di pensare a AST di un programma. In genere, ciascun token ha un tipo specifico che può essere o non essere compatibile con altri tipi. Pensa valore-l, valore-r e l'altro intero pasticcio di tipi di valore in C ++ . Quindi aggiungi le parole chiave, i simboli che sono funzioni, ecc. Alcuni di questi possono essere valori di prima, seconda o terza classe a seconda della lingua.

Non sono sicuro che conoscere la "classe" di valore sia tanto importante, tranne forse in un ambiente accademico. Nel mondo reale, la cosa importante da sapere è come passare il codice, trattandolo come dati: funtori, lambda / chiusure, puntatori di funzioni, ecc.

    
risposta data 26.09.2016 - 23:46
fonte
8

Denotational Semantics fornisce una base matematica per descrivere come valori e variabili funzionano in un linguaggio di programmazione. E 'stato spiegato così bene nella mia Laurea in Computer Science che ho ottenuto un ottimo punteggio nell'Esame Semantica Denotazionale, poi ho dimenticato la maggior parte di esso e non ho mai avuto bisogno di usarlo in una vita di 20 anni come programmatore.

È possibile scegliere di utilizzare una fondazione matematica ben definita oppure utilizzare una terminologia informale come "stato di prima classe". Avrei imparato molto di più se il corso fosse basato sul programma di programmazione Pragmatica di Scott, tuttavia la matematica formale è necessaria per qualcuno che sta per fare un dottorato in programmazione del linguaggio di programmazione.

Se leggi le specifiche per la maggior parte del linguaggio di programmazione, noterai una mancanza dissidente di Denotational Semantics, tuttavia le lingue più ben progettate hanno qualcuno nel team che è un esperto nella programmazione del linguaggio di programmazione, quindi capisce bene la semantica denotazionale.

Quindi Michearl Scott usa una terminologia informale che ha qualche relazione con la matematica formale, mentre presenta l'argomento in un modo che la maggior parte dei programmatori può trarre beneficio. La sua terminologia non è usata da altre persone, quindi non utile per comunicare, ma ti dà una buona base sulle domande che dovresti fare quando vedi un nuovo linguaggio di programmazione per la prima volta.

Si noti che Michael L. Scott è un ricercatore leader in Computer Science, quindi comprenderà e sarà molto felice utilizzando la matematica formale, ma come i migliori ricercatori è l'abilità nello spiegare l'applicazione della ricerca al resto di noi.

    
risposta data 27.09.2016 - 12:09
fonte
3

No, la parola "first" in "first-class" e in "first-order" significa cose diverse.

Ma sì, i concetti di "prima classe" e "primo ordine" sono correlati. Stanno entrambi classificando i concetti in cui una lingua può descrivere la lingua possono anche astrarsi.

Un concetto è di prima classe se i soliti meccanismi di astrazione di una lingua possono astrarre su quel concetto.

Ad esempio, il linguaggio di programmazione Java può descrivere interi e tutti i soliti meccanismi per astrarre gli interi (accettarli come parametri del metodo, restituirli come risultati di funzione, archiviarli in strutture di dati, ...) funzionano per interi.

Un concetto è di primo ordine se non può essere utilizzato per astrarsi su se stesso.

Ad esempio, sempre in Java, possiamo usare metodi per astrarre determinate cose. Ma non possiamo usare i metodi per astrarre i metodi, perché un nome di metodo non può essere passato come parametro di metodo. Questo è diverso in JavaScript, dove puoi usare la notazione della parentesi per accedere a una proprietà di un oggetto con il suo nome come una stringa e puoi astrarre le stringhe.

Un concetto è di secondo ordine se può essere utilizzato per astrarre gli usi del primo ordine di se stesso, ma non per gli usi del secondo ordine.

Ad esempio, in Java, puoi utilizzare Generics per astrarre i tipi (come in class Foo<T> { public List<T> content; } ). Tuttavia, non è possibile utilizzare i generici per astrarre su Generics (come in class Bar<T> { public T<Int> content; } ). Questo è diverso in Scala.

Un concetto è di terzo ordine se può essere utilizzato per astrarre gli usi del primo ordine e del secondo ordine di se stesso, ma non per gli usi del secondo ordine.

E così via.

Infine, un concetto è di ordine superiore se può essere utilizzato per astrarre usi arbitrari di se stesso.

Riepilogo: se una funzione di astrazione è di prima classe, è anche un ordine superiore. E se una caratteristica di astrazione è di primo ordine, non può essere di prima classe.

    
risposta data 27.09.2016 - 16:17
fonte
2

What is the mathematics foundation for first/second/third class values in programming languages?

Nessuna delle quali sono a conoscenza.

The terminology reminds me of first/second order logic, but are they related?

Non proprio.

La "classe" di un elemento del linguaggio di programmazione è solo un modo stenografico di pensare alla domanda quali cose l'utente della mia lingua desidera manipolare a livello di programmazione ? Ad esempio, C # ti offre un ricco insieme di operazioni per manipolare valori , un insieme meno ricco di modi per manipolare tipi e nessuna operazione che manipola le etichette .

Tuttavia la tua intuizione che qui c'è una connessione non è completamente fuori luogo. Esiste un'analogia che va dalla logica del primo ordine alla programmazione procedurale e dalla logica di ordine superiore alla programmazione funzionale. La logica del primo ordine riguarda la manipolazione logica dei valori; la programmazione procedurale riguarda la manipolazione programmatica dei valori. La logica di ordine superiore riguarda la manipolazione logica delle dichiarazioni di logica , la programmazione funzionale riguarda la manipolazione programmatica di funzioni .

Why are the specific cases important, while not other cases not mentioned?

Dovresti chiedere all'autore una risposta definitiva.

Non mi perderei troppo attaccare a questa nozione di "classe". Non è una cosa formalmente definita. È una stenografia che i designer di linguaggio usano per parlare di quali tipi di cose possono essere manipolati a livello di programmazione.

    
risposta data 27.09.2016 - 19:40
fonte
2

"Valore di prima classe", in questo contesto, è la terminologia standard nella teoria del linguaggio di programmazione. Un valore di prima classe è qualcosa che può essere manipolato come valori normali nella lingua, qualcosa che può essere calcolato in fase di runtime. Naturalmente, questa è una definizione tautologica finché non hai definito una semantica per il linguaggio, e quindi un valore è qualunque cosa la semantica definisce come un valore. Il punto del concetto è identificare ciò che può essere manipolato direttamente, invece di accedere solo indirettamente.

Ad esempio, in quasi tutti i linguaggi di programmazione, gli interi macchina di una dimensione limitata (ad esempio interi a 8 bit o interi a 32 bit o interi a 64 bit, ecc.) sono valori di prima classe. Puoi archiviarli in variabili, passarli e restituirli alle funzioni, ecc. Nella maggior parte delle lingue, ma non in linguaggi di basso livello come assembly e C, le stringhe sono valori di prima classe, ma in C non lo sono, sei solo ottenere puntatori alle stringhe. In C, le stringhe e gli array non sono valori di prima classe: ad esempio non è possibile passare una matrice a una funzione, non è possibile assegnare una matrice a una variabile di matrice, ecc. In C, le funzioni non sono valori di prima classe entrambi: non è possibile memorizzare una funzione in una variabile, solo un puntatore a una funzione. Al contrario, le stringhe e le funzioni sono valori di prima classe nella maggior parte dei linguaggi di programmazione di alto livello: è possibile memorizzarli in una stringa, ecc.

Un esempio di un concetto che non è di prima classe in molti linguaggi di programmazione progettati per essere compilati è di tipo. In un linguaggio come C o Java, i tipi vivono al momento della compilazione, non è possibile manipolarli utilizzando i costrutti del linguaggio. (Java ha anche un sistema di tipo dinamico basato su classi; le classi sono valori di prima classe attraverso la riflessione.) Al contrario, un linguaggio come Python ha una funzione type che restituisce un valore che rappresenta il tipo del suo argomento.

La negazione del "valore di prima classe" nella terminologia standard è "non un valore di prima classe". Il termine "valore di seconda classe" non è comunemente usato e "valore di terza classe" ancora meno. Non aspettarti di vederli al di fuori di questo libro. Non c'è assolutamente alcuna base per definire "secondo" come "può essere passato come parametro" e "terzo" come "non può essere passato come parametro", non esiste una scala di cose che possa essere numerata in modo significativo. Pochissime lingue fanno la differenza tra i valori che possono essere passati come parametro alle funzioni e ai valori che possono essere assegnati alle variabili, quindi non è utile definire un nome per questo concetto.

    
risposta data 27.09.2016 - 21:01
fonte

Leggi altre domande sui tag