Cos’è l’esecuzione differenziale?

Mi sono imbattuto in una domanda Stack Overflow, come funziona l’esecuzione differenziale? , che ha una risposta MOLTO lunga e dettagliata. Tutto ciò aveva senso … ma quando ho finito non avevo ancora idea di cosa fosse effettivamente l’esecuzione differenziale del diavolo. Cos’è veramente?

REVISIONE. Questo è il mio ennesimo tentativo di spiegarlo.

Supponiamo di avere una semplice procedura deterministica che viene eseguita ripetutamente, sempre seguendo la stessa sequenza di esecuzioni di istruzioni o chiamate di procedura. La procedura chiama se stessi scrivendo tutto ciò che vogliono in sequenza su una FIFO, e leggono lo stesso numero di byte dall’altra parte della FIFO, in questo modo: **

inserisci la descrizione dell'immagine qui

Le procedure che vengono chiamate utilizzano la memoria FIFO come memoria, perché ciò che leggono è lo stesso di quello che hanno scritto nell’esecuzione precedente. Quindi se i loro argomenti sono diversi questa volta dall’ultima volta, possono vederlo e fare tutto ciò che vogliono con quelle informazioni.

Per iniziare, ci deve essere un’esecuzione iniziale in cui solo la scrittura avviene, nessuna lettura. Simmetricamente, dovrebbe esserci un’esecuzione finale in cui avviene solo la lettura, nessuna scrittura. Quindi c’è un registro di modalità “globale” contenente due bit, uno che consente la lettura e uno che consente la scrittura, come questo:

inserisci la descrizione dell'immagine qui

L’esecuzione iniziale viene eseguita in modalità 01 , quindi viene eseguita solo la scrittura. Le chiamate di procedura possono vedere la modalità, quindi sanno che non esiste una cronologia precedente. Se vogliono creare oggetti che possono, e inserire le informazioni di identificazione nella FIFO (non è necessario archiviare in variabili).

Le esecuzioni intermedie vengono eseguite in modalità 11 , pertanto avvengono sia la lettura che la scrittura e le chiamate alla procedura possono rilevare le modifiche dei dati. Se ci sono oggetti da tenere aggiornati, le loro informazioni identificative vengono lette e scritte sul FIFO, in modo che possano essere consultate e, se necessario, modificate.

L’esecuzione finale viene eseguita in modalità 10 , quindi avviene solo la lettura. In questa modalità, le chiamate alla procedura sanno che stanno solo pulendo. Se sono stati mantenuti oggetti, i loro identificatori vengono letti dal FIFO e possono essere cancellati.


Ma le procedure reali non seguono sempre la stessa sequenza. Contengono dichiarazioni IF (e altri modi per variare ciò che fanno). Come può essere gestito?

La risposta è un tipo speciale di istruzione IF (e la sua istruzione ENDIF di chiusura). Ecco come funziona. Scrive il valore booleano della sua espressione di test e legge il valore che l’espressione di test ha avuto l’ultima volta. In questo modo, può determinare se l’espressione di test è cambiata e agire. L’azione che si richiede è di modificare temporaneamente il registro delle modalità .

inserisci la descrizione dell'immagine qui

Specificamente, x è il valore precedente dell’espressione test, letto dal FIFO (se la lettura è abilitata, altrimenti 0), e y è il valore corrente dell’espressione test, scritto sul FIFO (se la scrittura è abilitata). (In realtà, se la scrittura non è abilitata, l’espressione di test non viene nemmeno valutata, e y è 0.) Quindi x, y semplicemente MASKs il registro di modalità r, w . Quindi se l’espressione di test è cambiata da True a False, il corpo viene eseguito in modalità di sola lettura. Al contrario, se è stato modificato da False a True, il corpo viene eseguito in modalità solo scrittura. Se il risultato è 00 , il codice all’interno dell’istruzione IF..ENDIF viene saltato. (Puoi pensare un po ‘se questo riguarda tutti i casi – lo fa.)

Potrebbe non essere ovvio, ma queste istruzioni IF..ENDIF possono essere nidificate arbitrariamente e possono essere estese a tutti gli altri tipi di istruzioni condizionali come ELSE, SWITCH, WHILE, FOR e persino a chiamare le funzioni basate su puntatore. È anche il caso che la procedura può essere suddivisa in sottoprocedure in qualsiasi misura desiderata, incluso ricorsivo, purché la modalità sia rispettata.

(Esiste una regola da seguire, detta regola della modalità di cancellazione , che in modalità 10 non deve essere calcasting alcuna conseguenza, come il seguire un puntatore o l’indicizzazione di un array. Concettualmente, la ragione è quella modalità 10 esiste solo allo scopo di sbarazzarsi di cose.)

Quindi è un’interessante struttura di controllo che può essere sfruttata per rilevare le modifiche, in genere i cambiamenti dei dati, e agire su tali cambiamenti.


Il suo uso nelle interfacce utente grafiche è di mantenere un certo insieme di controlli o altri oggetti in accordo con le informazioni sullo stato del programma. A tale scopo, le tre modalità sono denominate SHOW (01), UPDATE (11) e ERASE (10). La procedura viene inizialmente eseguita in modalità SHOW, in cui vengono creati i controlli e le informazioni ad essi relative popolano FIFO. Quindi qualsiasi numero di esecuzioni viene eseguito in modalità AGGIORNAMENTO, dove i controlli vengono modificati secondo necessità per rimanere aggiornati con lo stato del programma. Infine, c’è un’esecuzione in modalità ERASE, in cui i controlli vengono rimossi dall’interfaccia utente e il FIFO viene svuotato.

inserisci la descrizione dell'immagine qui

Il vantaggio di fare questo è che, una volta che hai scritto la procedura per creare tutti i controlli, in funzione dello stato del programma, non devi scrivere altro per tenerlo aggiornato o ripulire in seguito. Qualsiasi cosa tu non debba scrivere significa meno possibilità di commettere errori. (C’è un modo semplice per gestire gli eventi di input dell’utente senza dover scrivere gestori di eventi e creare nomi per essi. Questo è spiegato in uno dei video collegati sotto.)

In termini di gestione della memoria, non è necessario creare nomi di variabili o strutture dati per contenere i controlli. Utilizza solo memoria sufficiente in qualsiasi momento per i controlli attualmente visibili, mentre i controlli potenzialmente visibili possono essere illimitati. Inoltre, non vi è mai alcuna preoccupazione per la raccolta dei dati obsoleti dei controlli utilizzati in precedenza: la FIFO funge da garbage collector automatico.

In termini di prestazioni, quando si creano, eliminano o modificano i controlli, è tempo di spesa che deve essere speso comunque. Quando si aggiornano semplicemente i controlli e non vi sono cambiamenti, i cicli necessari per eseguire la lettura, la scrittura e il confronto sono microscopici rispetto ai controlli di modifica.

Un’altra considerazione relativa alla performance e alla correttezza, relativa ai sistemi che si aggiorna in risposta agli eventi, è che un sistema di questo tipo richiede che ogni evento venga risposto e nessuno due volte, altrimenti il ​​display non sarà corretto, anche se alcune sequenze di eventi potrebbero essere auto- annullamento. Sotto l’esecuzione differenziale, i passaggi di aggiornamento possono essere eseguiti con la frequenza desiderata o raramente, e il display è sempre corretto alla fine di un passaggio.


Ecco un esempio estremamente abbreviato in cui ci sono 4 pulsanti, di cui i pulsanti 2 e 3 sono condizionati da una variabile booleana.

  1. Nel primo passaggio, in modalità Mostra, il valore booleano è falso, pertanto compaiono solo i pulsanti 1 e 4.
  2. Quindi il valore booleano è impostato su true e il passaggio 2 viene eseguito in modalità di aggiornamento, in cui i pulsanti 2 e 3 vengono istanziati e il pulsante 4 viene spostato, dando lo stesso risultato come se il valore booleano fosse stato true al primo passaggio.
  3. Quindi il valore booleano è impostato su false e il passaggio 3 viene eseguito in modalità di aggiornamento, causando la rimozione dei pulsanti 2 e 3 e il pulsante 4 per tornare indietro al punto precedente.
  4. Infine, il passaggio 4 viene eseguito in modalità Cancella, facendo scomparire tutto.

(In questo esempio, le modifiche vengono annullate nell’ordine inverso così come è stato fatto, ma ciò non è necessario. Le modifiche possono essere apportate e disfatte in qualsiasi ordine.)

Nota che, in ogni momento, il FIFO, composto da vecchio e nuovo concatenati insieme, contiene esattamente i parametri dei pulsanti visibili più il valore booleano.

Lo scopo è mostrare come una singola procedura “paint” può essere utilizzata, senza modifiche, per l’aggiornamento e la cancellazione incrementali automatici arbitrari. Spero sia chiaro che funzioni per profondità arbitrarie delle chiamate sub-procedure e nidificazione arbitraria di condizionali, inclusi switch , while e for loops, chiamate funzioni basate su puntatori, ecc. Se devo spiegarlo, allora sono aperto a potshots per rendere la spiegazione troppo complicata.

inserisci la descrizione dell'immagine qui

Infine, ci sono un paio di video grezzi ma brevi pubblicati qui .

** Tecnicamente, devono leggere lo stesso numero di byte che hanno scritto l’ultima volta. Quindi, per esempio, potrebbero aver scritto una stringa preceduta da un numero di caratteri, e questo è OK.


AGGIUNTO: Mi ci è voluto molto tempo per essere sicuro che funzionasse sempre. Alla fine l’ho dimostrato. È basato su una proprietà Sync , il che significa che in qualsiasi punto del programma il numero di byte scritti sul pass prioritario è uguale al numero letto sul pass successivo. L’idea alla base della dimostrazione è di farlo per induzione sulla lunghezza del programma. Il caso più difficile da dimostrare è il caso di una sezione di programma composta da s1 seguita da un IF (test) s2 ENDIF , in cui s1 e s2 sono sottosezioni del programma, ognuna delle quali soddisfa la proprietà Sync . Per farlo in solo testo è l’occhiale, ma qui ho provato a disegnarlo: inserisci la descrizione dell'immagine qui

Definisce la proprietà Sync e mostra il numero di byte scritti e letti in ogni punto del codice e mostra che sono uguali. I punti chiave sono che 1) il valore dell’espressione test (0 o 1) letta sulla pass corrente deve essere uguale al valore scritto sul pass precedente, e 2) la condizione di Sync (s2) è soddisfatta. Questo soddisfa la proprietà Sync per il programma combinato.

Ho letto tutto il materiale che riesco a trovare e ho guardato il video e prenderò una foto di primo livello.

Panoramica

Questo è un modello di progettazione basato su DSL per l’implementazione di interfacce utente e forse di altri sottosistemi orientati allo stato in modo pulito ed efficiente. Si concentra sul problema della modifica della configurazione della GUI per far corrispondere lo stato corrente del programma, dove lo stato include la condizione dei widget GUI stessi, ad esempio l’utente seleziona tabs, pulsanti di opzione e voci di menu ei widget appaiono / scompaiono in modi arbitrariamente complessi.

Descrizione

Il modello assume:

  1. Una raccolta globale C di oggetti che richiede aggiornamenti periodici.
  2. Una famiglia di tipi per quegli oggetti, in cui le istanze hanno parametri.
  3. Una serie di operazioni su C:
    • Aggiungi AP – Metti un nuovo object A in C con i parametri P.
    • Modifica AP : modifica i parametri dell’object A in C in P.
    • Elimina A – Rimuovi l’object A da C.
  4. Un aggiornamento di C consiste in una sequenza di tali operazioni per trasformare C in una determinata raccolta di target, ad esempio C ‘.
  5. Data la raccolta corrente C e la destinazione C ‘, l’objective è trovare l’aggiornamento con un costo minimo. Ogni operazione ha un costo unitario.
  6. L’insieme delle possibili raccolte è descritto in un linguaggio specifico del dominio (DSL) che ha i seguenti comandi:
    • Crea AHCrea un’istanza dell’object A, utilizzando i suggerimenti facoltativi H, e aggiungilo allo stato globale. (Nota nessun parametro qui.)
    • Se B Then T Else F – Esegue in modo condizionale la sequenza di comando T o F in base alla funzione Booleana B, che può dipendere da qualsiasi cosa nel programma in esecuzione.

In tutti gli esempi,

  • Lo stato globale è uno schermo o una finestra della GUI.
  • Gli oggetti sono widget dell’interfaccia utente. I tipi sono pulsante, casella a discesa, campo di testo, …
  • Parametri controllano l’aspetto e il comportamento del widget.
  • Ogni aggiornamento consiste nell’aggiungere, eliminare e modificare (ad es. Ricollocare) qualsiasi numero di widget nella GUI.
  • I comandi Crea stanno creando widget: pulsanti, caselle a discesa, …
  • Le funzioni booleane dipendono dallo stato del programma sottostante inclusa la condizione dei controlli della GUI stessi. Quindi cambiare un controllo può influenzare lo schermo.

Collegamenti mancanti

L’inventore non lo afferma esplicitamente, ma un’idea chiave è che eseguiamo l’interprete DSL sul programma che rappresenta tutte le possibili raccolte di destinazione (schermate) ogni volta che prevediamo che una qualsiasi combinazione dei valori della funzione booleana B sia cambiata. L’interprete gestisce il lavoro sporco di rendere la raccolta (schermo) coerente con i nuovi valori B emettendo una sequenza di operazioni Aggiungi, Elimina e Modifica.

Esiste un’ipotesi finale nascosta: l’interprete DSL include un algoritmo in grado di fornire i parametri per le operazioni Aggiungi e Modifica in base alla cronologia di Creates eseguita finora durante la sua esecuzione corrente. Nel contesto della GUI, questo è l’algoritmo di layout e i suggerimenti per la creazione sono suggerimenti di layout.

Punch line

Il potere della tecnica sta nel modo in cui la complessità è incapsulata nell’interprete DSL. Uno stupido interprete comincerebbe eliminando tutti gli oggetti (widget) nella raccolta (schermo), quindi aggiungine uno nuovo per ogni comando Crea mentre li vede mentre passa attraverso il programma DSL. La modifica non si verificherebbe mai.

L’esecuzione differenziale è solo una strategia più intelligente per l’interprete. Si tratta di tenere una registrazione serializzata dell’ultima esecuzione dell’interprete. Questo ha senso perché la registrazione cattura ciò che è attualmente sullo schermo. Durante l’esecuzione corrente, l’interprete consulta la registrazione per prendere decisioni su come realizzare la raccolta di destinazione (configurazione del widget) con operazioni che hanno il minor costo. Questo si risolve in mai Eliminazione di un object (widget) solo per aggiungerlo di nuovo in un secondo momento per un costo di 2. DE cambierà sempre invece, che ha un costo di 1. Se ci capita di eseguire l’interprete in alcuni casi dove i valori B non sono stati modificati, l’algoritmo DE non genererà alcuna operazione: il stream registrato rappresenta già il target.

Mentre l’interprete esegue i comandi, sta anche impostando la registrazione per la sua prossima esecuzione.

Un algoritmo analogo

L’algoritmo ha lo stesso sapore della distanza minima di modifica (MED). Tuttavia, DE è un problema più semplice di MED perché non ci sono “caratteri ripetuti” nelle stringhe di esecuzione serializzate DE come in MED. Ciò significa che possiamo trovare una soluzione ottimale con un algoritmo onirico on-line semplice piuttosto che una programmazione dynamic. Questo è ciò che fa l’algoritmo dell’inventore.

Punti di forza

La mia opinione è che questo è un buon modello per l’implementazione di sistemi con molte forms complesse in cui si desidera il controllo totale sul posizionamento dei widget con il proprio algoritmo di layout e / o la logica “if else” di ciò che è visibile è profondamente annidata. Se ci sono nidi K di “if els” N nella logica del modulo, allora ci sono K * 2 ^ N layout diversi per avere ragione. I tradizionali sistemi di design delle forms (almeno quelli che ho usato) non supportano molto bene i valori K, N più grandi. Si tende a finire con un gran numero di layout simili e una logica ad hoc per selezionarli che è brutto e difficile da mantenere. Questo modello DSL sembra un modo per evitare tutto ciò. Nei sistemi con un numero sufficiente di moduli per compensare il costo dell’interprete DSL, sarebbe addirittura più economico durante l’implementazione iniziale. La separazione delle preoccupazioni è anche una forza. I programmi DSL astraggono il contenuto dei moduli mentre l’interprete è la strategia di layout, agendo su suggerimenti del DSL. Ottenere il DSL e il design del suggerimento del layout a destra sembra un problema significativo e interessante di per sé.

Discutibile…

Non sono sicuro che evitare le coppie Delete / Add a favore di Modify valga la pena di tutti i problemi nei sistemi moderni. L’inventore sembra più orgoglioso di questa ottimizzazione, ma l’idea più importante è un DSL conciso con condizionali per rappresentare le forms, con la complessità del layout isolata nell’interprete DSL.

Ricapitolare

Finora l’inventore si è concentrato su dettagli profondi su come l’interprete prende le sue decisioni. Ciò è fonte di confusione perché è diretto agli alberi mentre la foresta è di maggiore interesse. Questa è una descrizione della foresta.