¿Cómo funciona la ejecución diferencial?

He visto algunas menciones de esto en Stack Overflow, pero mirar Wikipedia (la página relevante se ha eliminado desde entonces) y una demostración de diálogo dinámico de MFC no hizo nada para iluminarme. ¿Puede alguien por favor explicar esto? Aprender un concepto fundamentalmente diferente suena bien.

Basado en las respuestas: Creo que lo estoy sintiendo mejor. Supongo que no miré el código fuente con suficiente atención la primera vez. Tengo sentimientos encontrados sobre la ejecución diferencial en este momento. Por un lado, puede facilitar considerablemente determinadas tareas. Por otro lado, ponerlo en funcionamiento (es decir, configurarlo en el idioma que elijas) no es fácil (estoy seguro de que lo sería si lo entendiera mejor) ... aunque supongo que la caja de herramientas para ello solo necesita hacerse una vez y luego expandirse según sea necesario. Creo que para entenderlo realmente, probablemente tendré que intentar implementarlo en otro idioma.

Vaya, Brian, desearía haber visto tu pregunta antes. Dado que es prácticamente mi "invención" (para bien o para mal), es posible que pueda ayudar.

Insertado: La explicación más corta posible que puedo hacer es que si la ejecución normal es como lanzar una pelota al aire y atraparla, entonces la ejecución diferencial es como hacer malabares.

La explicación de @ windfinder es diferente a la mía, y está bien. Esta técnica no es fácil de entender, y me ha llevado unos 20 años (de vez en cuando) encontrar explicaciones que funcionen. Déjame darle otra oportunidad aquí:

• ¿Qué es?

Todos entendemos la simple idea de que una computadora avance a lo largo de un programa, tome ramas condicionales basadas en los datos de entrada y haga cosas. (Suponga que estamos tratando solo con código estructurado simple sin goto, sin retorno). Ese código contiene secuencias de declaraciones, condicionales estructurados básicos, bucles simples y llamadas a subrutinas. (Olvídese de las funciones que devuelven valores por ahora).

Ahora imagina dos computadoras ejecutando el mismo código en sincronía entre sí y capaces de comparar notas. La computadora 1 se ejecuta con los datos de entrada A y la computadora 2 se ejecuta con los datos de entrada B. Se ejecutan paso a paso lado a lado. Si llegan a una declaración condicional como IF (prueba) .... ENDIF, y si tienen una diferencia de opinión sobre si la prueba es verdadera, entonces el que dice la prueba si es falsa salta al ENDIF y espera su hermana para ponerse al día. (Esta es la razón por la que el código está estructurado, por lo que sabemos que la hermana eventualmente llegará al ENDIF).

Dado que las dos computadoras pueden comunicarse entre sí, pueden comparar notas y dar una explicación detallada de cómo los dos conjuntos de datos de entrada y los historiales de ejecución son diferentes.

Por supuesto, en ejecución diferencial (DE) se realiza con un ordenador, simulando dos.

AHORA, suponga que solo tiene un conjunto de datos de entrada, pero quiere ver cómo ha cambiado desde el tiempo 1 al tiempo 2. Suponga que el programa que está ejecutando es un serializador / deserializador. A medida que ejecuta, serializa (escribe) los datos actuales y deserializa (lee) los datos anteriores (que se escribieron la última vez que hizo esto). Ahora puede ver fácilmente cuáles son las diferencias entre lo que eran los datos la última vez y lo que son esta vez.

El archivo en el que está escribiendo y el archivo antiguo desde el que está leyendo, en conjunto, constituyen una cola o FIFO (primero en entrar, primero en salir), pero ese no es un concepto muy profundo.

• ¿Para que sirve?

Se me ocurrió mientras trabajaba en un proyecto de gráficos, donde el usuario podía construir pequeñas rutinas de procesador de pantalla llamadas "símbolos" que podrían ensamblarse en rutinas más grandes para pintar cosas como diagramas de tuberías, tanques, válvulas, cosas así. Queríamos que los diagramas fueran "dinámicos" en el sentido de que pudieran actualizarse de forma incremental sin tener que volver a dibujar todo el diagrama. (El hardware era lento para los estándares actuales). Me di cuenta de que (por ejemplo) una rutina para dibujar una barra de un gráfico de barras podía recordar su antigua altura y simplemente actualizarse gradualmente.

Esto suena a OOP, ¿no? Sin embargo, en lugar de "hacer" un "objeto", podría aprovechar la previsibilidad de la secuencia de ejecución del procedimiento del diagrama. Podría escribir la altura de la barra en un flujo de bytes secuencial. Luego, para actualizar la imagen, podría simplemente ejecutar el procedimiento en un modo en el que lea secuencialmente sus parámetros antiguos mientras escribe los nuevos parámetros para estar listo para la siguiente pasada de actualización.

Esto parece estúpidamente obvio y parecería romperse tan pronto como el procedimiento contenga un condicional, porque entonces la nueva transmisión y la transmisión anterior se desincronizarían. Pero luego me di cuenta de que si también serializaban el valor booleano de la prueba condicional, podrían volver a sincronizarse . Me tomó un tiempo convencerme y luego demostrar que esto siempre funcionaría, siempre que se siguiera una regla simple (la "regla del modo de borrado").

El resultado neto es que el usuario puede diseñar estos "símbolos dinámicos" y ensamblarlos en diagramas más grandes, sin tener que preocuparse por cómo se actualizarán dinámicamente, sin importar cuán compleja o estructuralmente variable sea la pantalla.

En aquellos días, tenía que preocuparme por la interferencia entre objetos visuales, para que borrar uno no dañara a otros. Sin embargo, ahora uso la técnica con los controles de Windows y dejo que Windows se encargue de los problemas de renderizado.

Entonces, ¿qué logra? Significa que puedo crear un diálogo escribiendo un procedimiento para pintar los controles, y no tengo que preocuparme por recordar realmente los objetos de control o tratar de actualizarlos de forma incremental, o hacer que aparezcan / desaparezcan / se muevan según lo requieran las condiciones. El resultado es un código fuente de diálogo mucho más pequeño y simple, aproximadamente en un orden de magnitud, y cosas como el diseño dinámico o alterar el número de controles o tener matrices o cuadrículas de controles son triviales. Además, un control como un campo de edición se puede vincular trivialmente a los datos de la aplicación que está editando, y siempre será demostrablemente correcto y nunca tendré que lidiar con sus eventos. Poner un campo de edición para una variable de cadena de aplicación es una edición de una línea.

• ¿Por qué es tan difícil de entender?

Lo que me ha resultado más difícil de explicar es que requiere pensar de manera diferente sobre el software. Los programadores están tan firmemente aferrados a la visión objeto-acción del software que quieren saber qué son los objetos, qué son las clases, cómo "construyen" la pantalla y cómo manejan los eventos, que se necesita una cereza bomba para hacerlos explotar. Lo que trato de transmitir es que lo que realmente importa es lo que necesitas decir.Imagina que estás construyendo un lenguaje específico de dominio (DSL) en el que todo lo que necesitas hacer es decirle "Quiero editar la variable A aquí, la variable B allá y la variable C allá abajo" y mágicamente se encargaría de ello por ti. . Por ejemplo, en Win32 existe este "lenguaje de recursos" para definir diálogos. Es un DSL perfectamente bueno, excepto que no llega lo suficientemente lejos. No "vive en" el lenguaje procedimental principal, ni maneja eventos por usted, ni contiene bucles / condicionales / subrutinas. Pero tiene buenas intenciones y Dynamic Dialogs intenta terminar el trabajo.

Entonces, el modo diferente de pensar es: para escribir un programa, primero encuentra (o inventa) un DSL apropiado, y codifica tanto de su programa como sea posible. Deje que se ocupe de todos los objetos y acciones que solo existen para la implementación.

Si realmente desea comprender la ejecución diferencial y usarla, hay un par de problemas delicados que pueden hacerle tropezar. Una vez lo codifiqué en macros Lisp , donde estos complicados bits podrían ser manejados por usted, pero en lenguajes "normales" se requiere cierta disciplina del programador para evitar las trampas.

Lamento ser tan prolijo. Si no he tenido sentido, le agradecería que me lo señalara y puedo intentar solucionarlo.

Adicional:

En Java Swing , hay un programa de ejemplo llamado TextInputDemo. Es un diálogo estático, que ocupa 270 líneas (sin contar la lista de 50 estados). En Dynamic Dialogs (en MFC) son aproximadamente 60 líneas:

#define NSTATE (sizeof(states)/sizeof(states[0]))
CString sStreet;
CString sCity;
int iState;
CString sZip;
CString sWholeAddress;

void SetAddress(){
    CString sTemp = states[iState];
    int len = sTemp.GetLength();
    sWholeAddress.Format("%s\r\n%s %s %s", sStreet, sCity, sTemp.Mid(len-3, 2), sZip);
}

void ClearAddress(){
    sWholeAddress = sStreet = sCity = sZip = "";
}

void CDDDemoDlg::deContentsTextInputDemo(){
    int gy0 = P(gy);
    P(www = Width()*2/3);
    deStartHorizontal();
    deStatic(100, 20, "Street Address:");
    deEdit(www - 100, 20, &sStreet);
    deEndHorizontal(20);
    deStartHorizontal();
    deStatic(100, 20, "City:");
    deEdit(www - 100, 20, &sCity);
    deEndHorizontal(20);
    deStartHorizontal();
    deStatic(100, 20, "State:");
    deStatic(www - 100 - 20 - 20, 20, states[iState]);
    if (deButton(20, 20, "<")){
        iState = (iState+NSTATE - 1) % NSTATE;
        DD_THROW;
    }
    if (deButton(20, 20, ">")){
        iState = (iState+NSTATE + 1) % NSTATE;
        DD_THROW;
    }
    deEndHorizontal(20);
    deStartHorizontal();
    deStatic(100, 20, "Zip:");
    deEdit(www - 100, 20, &sZip);
    deEndHorizontal(20);
    deStartHorizontal();
    P(gx += 100);
    if (deButton((www-100)/2, 20, "Set Address")){
        SetAddress();
        DD_THROW;
    }
    if (deButton((www-100)/2, 20, "Clear Address")){
        ClearAddress();
        DD_THROW;
    }
    deEndHorizontal(20);
    P((gx = www, gy = gy0));
    deStatic(P(Width() - gx), 20*5, (sWholeAddress != "" ? sWholeAddress : "No address set."));
}

Adicional:

A continuación, se muestra un código de ejemplo para editar una serie de pacientes del hospital en aproximadamente 40 líneas de código. Las líneas 1-6 definen la "base de datos". Las líneas 10 a 23 definen el contenido general de la interfaz de usuario. Las líneas 30 a 48 definen los controles para editar el registro de un solo paciente. Tenga en cuenta que la forma del programa casi no se da cuenta de los eventos en el tiempo, como si todo lo que tuviera que hacer fuera crear la pantalla una vez. Luego, si se agregan o quitan sujetos o se llevan a cabo otros cambios estructurales, simplemente se vuelve a ejecutar, como si se estuviera recreando desde cero, excepto que DE hace que se lleve a cabo una actualización incremental. La ventaja es que usted, el programador, no tiene que prestar atención ni escribir ningún código para que se produzcan las actualizaciones incrementales de la interfaz de usuario, y se garantiza que son correctas. Podría parecer que esta nueva ejecución sería un problema de rendimiento, pero no lo es,

1  class Patient {public:
2    String name;
3    double age;
4    bool smoker; // smoker only relevant if age >= 50
5  };
6  vector< Patient* > patients;

10 void deContents(){ int i;
11   // First, have a label
12   deLabel(200, 20, “Patient name, age, smoker:”);
13   // For each patient, have a row of controls
14   FOR(i=0, i<patients.Count(), i++)
15     deEditOnePatient( P( patients[i] ) );
16   END
17   // Have a button to add a patient
18   if (deButton(50, 20, “Add”)){
19     // When the button is clicked add the patient
20     patients.Add(new Patient);
21     DD_THROW;
22   }
23 }

30 void deEditOnePatient(Patient* p){
31   // Determine field widths
32   int w = (Width()-50)/3;
33   // Controls are laid out horizontally
34   deStartHorizontal();
35     // Have a button to remove this patient
36     if (deButton(50, 20, “Remove”)){
37       patients.Remove(p);
37       DD_THROW;
39     }
40     // Edit fields for name and age
41     deEdit(w, 20, P(&p->name));
42     deEdit(w, 20, P(&p->age));
43     // If age >= 50 have a checkbox for smoker boolean
44     IF(p->age >= 50)
45       deCheckBox(w, 20, “Smoker?”, P(&p->smoker));
46     END
47   deEndHorizontal(20);
48 }

Agregado: Brian hizo una buena pregunta y pensé que la respuesta pertenecía al texto principal aquí:

@Mike: No tengo claro qué está haciendo realmente la declaración "if (deButton (50, 20,“ Add ”)) {". ¿Qué hace la función deButton? Además, ¿sus bucles FOR / END están usando algún tipo de macro o algo así? - Brian.

@Brian: Sí, las declaraciones FOR / END e IF son macros. El proyecto SourceForge tiene una implementación completa. deButton mantiene un control de botón. Cuando se lleva a cabo cualquier acción de entrada del usuario, el código se ejecuta en modo "evento de control", en el que deButton detecta que se presionó y significa que se presionó al devolver TRUE. Por tanto, el "if (deButton (...)) {... action code ...} es una forma de adjuntar código de acción al botón, sin tener que crear un cierre o escribir un controlador de eventos. El DD_THROW es un forma de terminar el pase cuando se toma la acción porque la acción puede haber modificado los datos de la aplicación, por lo que no es válido continuar con el "evento de control" pase a través de la rutina. Si lo compara con la escritura de controladores de eventos, le ahorra escribir esos, y te permite tener cualquier número de controles.

Agregado: Lo siento, debería explicar lo que quiero decir con la palabra "mantiene". Cuando el procedimiento se ejecuta por primera vez (en modo SHOW), deButton crea un control de botón y recuerda su id en el FIFO. En pasadas subsiguientes (en modo ACTUALIZAR), deButton obtiene el id del FIFO, lo modifica si es necesario y lo vuelve a poner en el FIFO. En el modo BORRAR, lo lee del FIFO, lo destruye y no lo devuelve, por lo que lo "recolecta como basura". Entonces, la llamada deButton gestiona toda la vida útil del control, manteniéndolo de acuerdo con los datos de la aplicación, por lo que digo que lo "mantiene".

El cuarto modo es EVENTO (o CONTROL). Cuando el usuario escribe un carácter o hace clic en un botón, ese evento se captura y registra, y luego el procedimiento deContents se ejecuta en el modo EVENT. deButton obtiene la identificación de su control de botón del FIFO y pregunta si este es el control en el que se hizo clic. Si lo fue, devuelve VERDADERO para que se pueda ejecutar el código de acción. Si no, simplemente devuelve FALSE. Por otro lado, deEdit(..., &myStringVar)detecta si el evento estaba destinado a él y, si es así, lo pasa al control de edición y luego copia el contenido del control de edición en myStringVar. Entre esto y el procesamiento de ACTUALIZACIÓN normal, myStringVar siempre es igual al contenido del control de edición. Así es como se hace la "unión". La misma idea se aplica a las barras de desplazamiento, cuadros de lista, cuadros combinados, cualquier tipo de control que le permita editar datos de la aplicación.

Aquí hay un enlace a mi edición de Wikipedia: http://en.wikipedia.org/wiki/User:MikeDunlavey/Difex_Article

La ejecución diferencial es una estrategia para cambiar el flujo de su código en función de eventos externos. Esto generalmente se hace manipulando una estructura de datos de algún tipo para registrar los cambios. Esto se usa principalmente en interfaces gráficas de usuario, pero también se usa para cosas como la serialización, donde se fusionan los cambios en un "estado" existente.

El flujo básico es el siguiente:

Start loop:
for each element in the datastructure: 
    if element has changed from oldDatastructure:
        copy element from datastructure to oldDatastructure
        execute corresponding subroutine (display the new button in your GUI, for example)
End loop:
Allow the states of the datastructure to change (such as having the user do some input in the GUI)

Las ventajas de esto son algunas. Uno, es la separación de la ejecución de sus cambios y la manipulación real de los datos de respaldo. Lo cual es bueno para múltiples procesadores. Dos, proporciona un método de ancho de banda bajo para comunicar cambios en su programa.

Piense en cómo funciona un monitor:

Se actualiza a 60 Hz, 60 veces por segundo. Parpadeo Parpadeo Parpadeo 60 veces, pero sus ojos son lentos y realmente no pueden decirlo. El monitor muestra lo que hay en el búfer de salida; simplemente arrastra estos datos cada 1/60 de segundo, sin importar lo que haga.

Ahora, ¿por qué querría que su programa actualice todo el búfer 60 veces por segundo si la imagen no debería cambiar con tanta frecuencia? ¿Qué pasa si solo cambia un píxel de la imagen, debería reescribir todo el búfer?

Esta es una abstracción de la idea básica: desea cambiar el búfer de salida en función de la información que desea que se muestre en la pantalla. Desea ahorrar tanto tiempo de CPU y tiempo de escritura en búfer como sea posible, de modo que no edite partes del búfer que no necesitan cambiarse para la siguiente extracción de pantalla.

El monitor está separado de su computadora y lógica (programas). Lee del búfer de salida a la velocidad con la que actualiza la pantalla. Queremos que nuestra computadora deje de sincronizarse y redibujarse innecesariamente. Podemos resolver esto cambiando la forma en que trabajamos con el búfer, lo que se puede hacer de varias maneras. Su técnica implementa una cola FIFO que está en retraso: contiene lo que acabamos de enviar al búfer. La cola FIFO retrasada no contiene datos de píxeles, contiene "formas primitivas" (que pueden ser píxeles en su aplicación, pero también pueden ser líneas, rectángulos, cosas fáciles de dibujar porque son solo formas, no hay datos innecesarios permitido).

Entonces, ¿quieres dibujar / borrar cosas de la pantalla? No hay problema. Según el contenido de la cola FIFO, sé cómo se ve el monitor en este momento. Comparo mi salida deseada (para borrar o dibujar nuevas primitivas) con la cola FIFO y solo cambio los valores que necesitan ser cambiados / actualizados. Este es el paso que le da el nombre de Evaluación Diferencial.

Dos formas distintas en las que aprecio esto:

El primero: Mike Dunlavey usa una extensión de declaración condicional. La cola FIFO contiene mucha información (el "estado anterior" o el material actual en el monitor o dispositivo de sondeo basado en el tiempo). Todo lo que tiene que agregar a esto es el estado que desea que aparezca en la pantalla a continuación.

Se agrega un bit condicional a cada ranura que puede contener una primitiva en la cola FIFO.

0 means erase
1 means draw

Sin embargo, tenemos estado anterior:

Was 0, now 0: don't do anything;
Was 0, now 1: add it to the buffer (draw it);
Was 1, now 1: don't do anything;
Was 1, now 0: erase it from the buffer (erase it from the screen);

Esto es elegante, porque cuando actualiza algo, solo necesita saber qué primitivas desea dibujar en la pantalla; esta comparación descubrirá si debe borrar una primitiva o agregarla / mantenerla en el búfer.

El segundo: Este es solo un ejemplo, y creo que a lo que Mike realmente está llegando es a algo que debería ser fundamental en el diseño de todos los proyectos: Reduzca la complejidad (computacional) del diseño escribiendo sus operaciones más intensas desde el punto de vista computacional como computerbrain-food o tan cerca como puedas. Respete la sincronización natural de los dispositivos.

Un método de redibujo para dibujar toda la pantalla es increíblemente costoso y hay otras aplicaciones en las que esta información es increíblemente valiosa.

Nunca estamos "moviendo" objetos por la pantalla. "Mover" es una operación costosa si vamos a imitar la acción física de "mover" cuando diseñamos código para algo como un monitor de computadora. En cambio, los objetos básicamente parpadean con el monitor. Cada vez que un objeto se mueve, ahora es un nuevo conjunto de primitivos y el antiguo conjunto de primitivos parpadea.

Cada vez que el monitor extrae del búfer, tenemos entradas que parecen

Draw bit    primitive_description
0           Rect(0,0,5,5);
1           Circ(0,0,2);
1           Line(0,1,2,5);

Nunca un objeto interactúa con la pantalla (o dispositivo de sondeo sensible al tiempo). Podemos manejarlo de manera más inteligente que un objeto cuando solicita con avidez actualizar toda la pantalla solo para mostrar un cambio específico solo para sí mismo.

Digamos que tenemos una lista de todas las primitivas gráficas posibles que nuestro programa es capaz de generar, y que vinculamos cada primitiva a un conjunto de declaraciones condicionales.

if (iWantGreenCircle && iWantBigCircle && iWantOutlineOnMyCircle) ...

Por supuesto, esto es una abstracción y, en realidad, el conjunto de condicionales que representa un ser primitivo particular encendido / apagado podría ser grande (quizás cientos de banderas que deben evaluarse como verdaderas).

Si ejecutamos el programa, podemos dibujar en la pantalla esencialmente al mismo ritmo al que podemos evaluar todos estos condicionales. (En el peor de los casos: cuánto tiempo lleva evaluar el mayor conjunto de declaraciones condicionales).

Ahora, para cualquier estado en el programa, ¡podemos simplemente evaluar todos los condicionales y la salida a la pantalla rápidamente! (Conocemos nuestras primitivas de forma y sus declaraciones if dependientes).

Esto sería como comprar un juego con gráficos intensos. Solo que en lugar de instalarlo en tu disco duro y ejecutarlo a través de tu procesador, compras una placa nueva que contiene la totalidad del juego y toma como entrada: mouse, teclado y toma como salida: monitor. Evaluación condicional increíblemente condensada (ya que la forma más fundamental de un condicional son las puertas lógicas en las placas de circuito). Esto, naturalmente, sería muy receptivo, pero casi no ofrece soporte para corregir errores, ya que todo el diseño de la placa cambia cuando realiza un pequeño cambio de diseño (porque el "diseño" está muy alejado de la naturaleza de la placa de circuito ). A expensas de la flexibilidad y claridad en cómo representamos los datos internamente, hemos ganado una "capacidad de respuesta" significativa porque ya no estamos "pensando" en la computadora; para la placa de circuito basada en las entradas.

La lección, según tengo entendido, es dividir el trabajo de manera que le dé a cada parte del sistema (no necesariamente solo la computadora y el monitor) algo que pueda hacer bien. El "pensamiento de la computadora" se puede hacer en términos de conceptos como objetos ... El cerebro de la computadora con gusto intentará pensar en todo esto por usted, pero puede simplificar mucho la tarea si puede dejar que la computadora piense en términos de data_update y conditional_evals. Nuestras abstracciones humanas de conceptos en código son idealistas y, en el caso de los métodos de dibujo de programas internos, un poco demasiado idealistas. Cuando todo lo que desea es un resultado (matriz de píxeles con valores de color correctos) y tiene una máquina que puede fácilmente escupe una matriz tan grande cada 1/60 de segundo, intente eliminar la mayor cantidad posible de pensamientos floridos del cerebro de la computadora para que pueda concentrarse en lo que realmente desea: sincronizar sus actualizaciones gráficas con sus entradas (rápidas) y el comportamiento natural del monitor.

¿Cómo se relaciona esto con otras aplicaciones? Me gustaría conocer otros ejemplos, pero estoy seguro de que hay muchos. Creo que cualquier cosa que proporcione una "ventana" en tiempo real sobre el estado de su información (estado variable o algo así como una base de datos ... un monitor es solo una ventana en su búfer de visualización) puede beneficiarse de estos conocimientos.

Encuentro este concepto muy similar a las máquinas de estado de la electrónica digital clásica. Especialmente los que recuerdan su salida anterior.

Una máquina cuya próxima salida depende de la entrada actual y la salida anterior según (SU CÓDIGO AQUÍ). Esta entrada actual no es más que la salida anterior + (USUARIO, INTERACTÚE AQUÍ).

Llene una superficie con tales máquinas, será interactivo para el usuario y al mismo tiempo representará una capa de datos cambiantes. Pero en esta etapa seguirá siendo tonto, solo reflejará la interacción del usuario con los datos subyacentes.

Luego, interconecta las máquinas en tu superficie, deja que compartan notas, según (TU CÓDIGO AQUÍ), y ahora lo hacemos inteligente. Se convertirá en un sistema informático interactivo.

Así que solo tienes que proporcionar tu lógica en dos lugares del modelo anterior; del resto se encarga el propio diseño de la máquina. Eso es lo bueno que tiene.