In Scheme, qual è lo stato formalmente di un programma?

4

Penso di aver capito più o meno come appare un programma Scheme analizzato (un albero binario con valori atomici sulle foglie, se ho capito bene). Qualcuno può definirmi o dare un riferimento, che cos'è uno stato (o un calcolo ) di un programma Scheme? È solo l'associazione corrente più una posizione, o una pila di posizioni, nell'albero della sintassi? (In tal caso, apprezzerei anche un riferimento per una definizione formale di associazione al regime:)).

C'è qualche descrizione semplice, come quella per la Turing Machine (il programma + il contenuto corrente del nastro + la posizione corrente sul nastro)?

    
posta Alexey 28.03.2013 - 16:26
fonte

4 risposte

3

Entrambe le altre risposte mi sembrano eccellenti.

Vorrei aggiungere quanto segue: lo stato di un programma di schemi è ... un programma di schemi! Cioè, puoi definire una funzione di "significato" per i programmi di schema mostrando come i programmi si riducono ad altri programmi. Questa è chiamata semantica "small-step". Per mostrarti cosa intendo: quali sono i "passi" - in un senso di settimo grado - nella valutazione di

3 * (4 + 5)

? Secondo le regole in piccolo passo fornite dalla maggior parte degli insegnanti, il primo passo nella valutazione di questo programma è di ridurlo a

3 * 20

Nello stesso identico modo, puoi definire una semantica in piccolo passo per Scheme che riduce un programma a una risposta effettuando una serie di passaggi di riduzione.

    
risposta data 29.03.2013 - 04:22
fonte
2

Non sono a conoscenza di alcuna definizione formale, ma posso speculare un po '.

Fondamentalmente puoi rappresentare qualsiasi programma con un'espressione lambda nel calcolo lambda. Un albero binario è una visione più semplice introdotta dai creatori di Scheme, per dare una bella idea ai neofiti in informatica.

Il calcolo Lambda definisce esplicitamente la semantica operazionale per la valutazione dell'espressione lambda. Fondamentalmente questo significa, nel calcolo lambda, che definiscono come si calcola il valore effettivo di qualsiasi espressione lambda, o se mappiamo le espressioni lambda ai programmi, come funzionerà un programma.

Esistono diverse alternative per definire la semantica operativa di un linguaggio di programmazione. Nel mondo di lambda calcolo queste alternative implicano regole di riduzione e strategia di riduzione. Sembrano sempre identiche, ma piccole variazioni cambiano il modo in cui viene ridotta l'espressione lambda. Nel mondo della programmazione questo corrisponde al modo in cui il programma viene eseguito. Ad esempio, diversi meccanismi di riduzione potrebbero valutare i parametri effettivi di una funzione prima o dopo la valutazione della funzione. Ciò corrisponde a meccanismi di valutazione dei parametri desiderosi e pigri di diversi linguaggi di programmazione.

In Scheme è possibile rappresentare ciascuna espressione in una più semplice vista ad albero binario. Simile alle espressioni lambda, gli alberi binari vengono ridotti da foglie a radice. Quindi ogni configurazione di un programma Scheme in esecuzione è ancora un albero binario.

Tuttavia, le chiamate di funzione complicano questo. Quando chiami una nuova funzione, hai una nuova espressione Schema da valutare. È semanticamente possibile collegare la nuova espressione all'albero binario sostituendo la chiamata di funzione. Ma praticamente non è un buon metodo. So che List non usa questo approccio, ma usa una serie di configurazioni, ognuna corrispondente a una funzione. Non sarei sorpreso se Scheme seguisse questa fazione.

Inoltre, i collegamenti complicano ulteriormente tale problema. Lo schema non è puramente funzionale, è possibile definire i binding e la loro semantica dovrebbe essere inclusa nel programma obbedendo alle regole dello scope. Anche quando esistono regole di ambito semplici, è difficile combinare associazioni con alberi di espressioni binarie. Il modo più semplice è utilizzare i collegamenti virtuali ai collegamenti (come i puntatori).

Questi sono basati solo sulle mie osservazioni dei tempi in cui ho usato Scheme, e alcuni di essi potrebbero essere falsi. Ma immagino sia chiaro che un modello molto semplice come Turing Machine non è puramente applicabile quando fattori come la chiamata di funzione e l'associazione entrano in scena. Il linguaggio di programmazione e il design del compilatore sono un puzzle complesso con molti sotto-problemi all'interno.

C'è un libro disponibile sul web, chiamato Un'introduzione allo schema e alle sue implementazioni . Potrebbe fornire ulteriori informazioni e fatti reali sull'implementazione del Programma. Se vuoi saperne di più su questo argomento ti consiglio di leggere un libro di linguaggi di programmazione su lambda calcolo e un libro di progettazione del compilatore (probabilmente il famoso dragon book ).

    
risposta data 28.03.2013 - 16:59
fonte
2

Stato e significato sono due cose molto diverse e la tua domanda li confonde.

Alla domanda "Che cosa significa questo programma ?" di Scheme, si può guardare a una semantica, o informale (una specifica scritta in inglese, per esempio) o formale (di solito una semantica operativa, ma a volte una semantica denotazionale, ecc.). Tuttavia, la semantica di un linguaggio di programmazione reale come Scheme sarà estremamente complicata.

Ora, se hai scelto una semantica operazionale (al contrario di una semantica denotazionale), avrà qualcosa che assomiglia ad uno stato (hai descritto lo stato della semantica operativa di un Turing Macchina nella tua domanda). Questo può essere un oggetto ragionevolmente semplice ... tuttavia, ci sono molte semantiche operative che puoi escogitare per Scheme (o qualsiasi linguaggio del mondo reale), e ognuna di esse avrà il suo stato come qualcosa di diverso!

Quindi, essenzialmente, ci sono infinite risposte alla tua domanda, nessuna di queste sarà illuminante senza la sua semantica corrispondente.

The Turing Machine, perché il modo in cui viene solitamente presentato è così vicino a una semantica operativa (perché è così di basso livello e "state-y"), in realtà non ha questo problema, perché c'è solo una buona scelta , che hai descritto bene nella tua domanda.

    
risposta data 28.03.2013 - 22:35
fonte
0

Dopo aver esaminato i calcoli di lambda-conversione di Alonzo Church, e pensando un po 'ai sistemi di riscrittura, alle diverse definizioni di algoritmi e al Lisp, sono giunto per lo più d'accordo con risposta di John Clements" : che lo stato di un programma Scheme è un programma Schema "ridotto".

Vorrei tuttavia formulare la mia versione di esso (che posso modificare o migliorare se imparo di più).

Secondo me, uno stato di un programma Scheme può essere visto come una sorta di programma Scheme, dove invece di costanti letterali , i dati costanti arbitrari valori sono consentiti (devono essere consentiti perché non sono sicuro che, ad esempio, un valore float arbitrario possa essere scritto come valore letterale float).

Ad esempio, un programma può essere eseguito come segue (la sequenza di stati):

Il programma:

(define x 0)
(set! x (lambda (x) (+ x 1)))
(define y 2)
(x y)

Stato del programma dopo il punto 1:

(define x (lambda (x) (+ x 1)))
(define y 2)
(x y)

Stato del programma dopo il passaggio 2:

(define y 2)
((lambda (x) (+ x 1)) y)

Stato del programma dopo il passaggio 3:

((lambda (x) (+ x 1)) 2)

Stato del programma dopo il punto 4:

(+ 2 1)

Stato del programma dopo il passaggio 5:

3

Aggiorna . Per confermare questo punto di vista, ecco le citazioni dal riferimento :

1.1 Evaluation Model

Racket evaluation can be viewed as the simplification of expressions to obtain values. For example, just as an elementary-school student simplifies

  1 + 1 = 2

Racket evaluation simplifies

  (+ 1 1) → 2

The arrow above replaces the more traditional = to emphasize that evaluation proceeds in a particular direction towards simpler expressions. In particular, a value is an expression that evaluation simplifies no further, such as the number 2.

[...]

1.1.4 Top-Level Variables

Given

x = 10

then an algebra student simplifies x + 1 as follows:

x + 1 = 10 + 1 = 11

Racket works much the same way, in that a set of top-level variables are available for substitutions on demand during evaluation. [...]

Each evaluation step, then, takes the current set of definitions and program to a new set of definitions and program. Before a define can be moved into the set of definitions, its right-hand expression must be reduced to a value.

  defined:
  evaluate: (begin (define x (+ 9 1)) (+ x 1))
→ defined:
  evaluate: (begin (define x 10) (+ x 1))
→ defined:  (define x 10)
  evaluate: (begin (void) (+ x 1))
→ defined:  (define x 10)
  evaluate: (+ x 1)
→ defined:  (define x 10)
  evaluate: (+ 10 1)
→ defined:  (define x 10)
  evaluate: 11

Using set!, a program can change the value associated with an existing top-level variable:

  defined:  (define x 10)
  evaluate: (begin (set! x 8) x)
→ defined:  (define x 8)
  evaluate: (begin (void) x)
→ defined:  (define x 8)
  evaluate: x
→ defined:  (define x 8)
  evaluate: 8

Ho letto anche la macchina SECD , le chiusure e gli ambienti, ma mi sembrano solo un metodo di implementazione particolare.

    
risposta data 12.08.2013 - 17:09
fonte

Leggi altre domande sui tag