Chiusure e grammatiche libere dal contesto

Question

Sto esaminando il mio programma per la mia lezione teorica di informatica e all'interno della rubrica Grammatiche senza contesto che elenca "proprietà di chiusura". Ho consultato il mio libro di testo su questo argomento e ho trovato abbastanza poco. Il poco che ha è un po 'sopra la mia testa al momento (non ho ancora seguito il corso) ma capisco un po'.

Mi chiedevo se questa idea di chiusure all'interno di grammatiche libere dal contesto sia la stessa o correlata all'idea di chiusure all'interno della programmazione funzionale. Parla di combinare grammatiche e risolvere sovrapposizioni, per quanto posso dire. Ci sono molte parti della sezione all'interno del libro che non capisco ancora, quindi non sono sicuro che queste idee siano uguali.

(Un po 'più di contesto: sto scrivendo una e-mail al professore chiedendo se il corso può essere passato a Ruby o Python da Perl. Se questi concetti sono correlati, questo potrebbe essere un altro motivo per cui dovremmo usare Ruby su Perl. )

Answer 1

Il termine "chiusura" viene utilizzato in vari modi, per lo più riconducendo a un concetto matematico di completamento, in un certo senso.

• Un operatore è " chiuso " un insieme di valori se l'applicazione di quell'operatore ai valori dell'insieme produce sempre un valore dall'insieme dato. Ad esempio, l'addizione è chiusa sugli interi, ma la divisione non lo è (4/2 è integrale, ma 5/2 non lo è). Quindi l'aggiunta di numeri interi è in qualche modo "completa" in un certo senso tale divisione non è.

• Il " transitivo " chiusura di una relazione "completa" la relazione seguendo (tutte le possibili) più applicazioni. In termini quotidiani, il concetto di "è un discendente di" è la chiusura transitiva della relazione "è un figlio di".

• Una funzionale "chiusura" è "completato" ad es. specificando come devono essere risolte le variabili libere. Nell'espressione pseudo-codice:

  bump = function(x) (x + y)
  

  x è l'argomento per bump , ma la definizione sembra lasciare " aperto " la questione della risoluzione di y . D'altra parte, se definiamo:

  bumper = function(y) (function(x) (x + y))
  

  quindi invocando bumper restituisce una funzione che aggiunge l'argomento originale di bumper all'argomento della funzione creata, in modo che:

  add3 = bumper(3)
  

  equivale a definire:

  add3 = function(x) (x + 3)
  

  La definizione nidificata è " chiusa su " (o completato da) le variabili disponibili nel punto della sua definizione.

Quindi, in effetti, gli usi di " chiusura " soprattutto hanno significati specifici diversi, e a prima vista sembrano non correlati, ma c'è una sottile relazione di fondo.

Answer 2

Una proprietà di chiusura è così: se L e M sono linguaggi senza contesto, allora anche L | M. Le chiusure di funzioni sono un modo per implementare funzioni di prima classe. Quindi no, non hanno praticamente nulla a che fare l'uno con l'altro.

Perché lo stesso nome, quindi? Una chiusura di funzione è "chiusa" sulle sue variabili libere:

def adder(n): return lambda m: n + m

Qui n è una variabile libera della lambda. Il nome sottolinea questo perché in origine Lisp non si chiudeva su variabili libere - avrebbero preso il loro valore da qualunque associazione fosse nello stack quando veniva chiamata la funzione interna.

La chiusura di proprietà matematiche è un po 'più ovvia: se un set viene chiuso in un'operazione, l'applicazione di tale operazione all'interno di quel set non ti eliminerà. Se aggiungi numeri interi, quello che ottieni è ancora un numero intero.

Answer 3

Dario è corretto; "proprietà di chiusura" non hanno nulla a che fare con le "chiusure di funzioni". Ci sono solo così tante parole da aggirare :-(

L'idea delle proprietà di chiusura è applicata in tutto l'informatica, ma è molto applicata a diverse classi di lingue. Le diverse classi di lingue sono importanti perché sono necessarie tecnologie diverse per scansionare o riconoscere un enunciato. Ad esempio, le espressioni regolari possono dirti se hai una parola riservata, ma non possono dirti se hai un'espressione con parentesi bilanciate --- per questo hai bisogno di una grammatica senza contesto.

Le persone sono generalmente interessate a sapere se se prendi una lingua particolare e ti intersechi o ti unisci con un'altra lingua, o semplicemente completi la lingua, ottieni un'altra lingua nella stessa classe. Ad esempio, è possibile scrivere un'espressione regolare che corrisponda esattamente a quei token che sono non parole riservate? Possiamo rispondere a un clamoroso "sì" poiché le lingue normali sono chiuse sotto complemento, cioè il complemento di una lingua normale è essa stessa una lingua normale. Questo è un esempio di proprietà di chiusura. Di solito la dimostrazione è costruttiva, cioè non solo ti dice che esiste esiste un'espressione regolare che descrive tutti i token che non sono parole riservate, la dimostrazione della proprietà di chiusura ti dirà come trova un'espressione così regolare.