¿Cómo funciona la ejecución diferencial?

He visto algunas menciones de esto en Stack Overflow, pero mirando a Wikipedia (la página relevante ya ha sido eliminada) y en un demo de diálogo dynamic de MFC no hice nada para aclararme. ¿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 simplemente no miré el código fuente con cuidado la primera vez. Tengo sentimientos encontrados sobre la ejecución diferencial en este punto. Por un lado, puede hacer que ciertas tareas sean considerablemente más fáciles. Por otro lado, ponerlo en funcionamiento (es decir, configurarlo en el idioma de su elección) no es fácil (estoy seguro de que sería si lo entendiera mejor) … aunque supongo que la caja de herramientas para ello solo se debe hacer una vez, luego se debe expandir según sea necesario. Creo que para entenderlo realmente, probablemente deba intentar implementarlo en otro idioma.

Vaya, Brian, desearía haber visto tu pregunta antes. Como es más o menos mi “invención” (para bien o para mal), podría ayudar.

Insertado: La explicación más breve posible que puedo hacer es que si la ejecución normal es como tirar una pelota en el air y atraparla, entonces la ejecución diferencial es como malabares.

La explicación de @ windfinder es diferente de la mía, y eso 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 comprendemos la idea simple de una computadora que avanza a través de un progtwig, tomando twigs condicionales basadas en los datos de entrada y haciendo cosas. (Supongamos que estamos tratando solo con código simple, sin retorno, sin retorno.) Ese código contiene secuencias de enunciados, 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 el paso de locking entre ellas, 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 uno al lado del otro. Si llegan a un enunciado condicional como IF (prueba) …. ENDIF, y si tienen una diferencia de opinión sobre si la prueba es verdadera, entonces quien diga la prueba en caso de falsa se salta al ENDIF y espera para su hermana para ponerse al día. (Esta es la razón por la cual el código está estructurado, por lo que sabemos que la hermana finalmente 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 e historias de ejecución son diferentes.

Por supuesto, en la ejecución diferencial (DE) se hace con una computadora, simulando dos.

AHORA, supongamos que solo tiene un conjunto de datos de entrada, pero desea ver cómo ha cambiado desde el momento 1 hasta el tiempo 2. Supongamos que el progtwig que está ejecutando es un serializador / deserializador. Al ejecutar, ambos serializan (escriben) los datos actuales y deserializan (leen) los datos pasados ​​(que fueron escritos la última vez que lo hicieron). Ahora puede ver fácilmente cuáles son las diferencias entre lo que fue la información la última vez y lo que es esta vez.

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

  • ¿Para que sirve?

Se me ocurrió mientras estaba trabajando en un proyecto de gráficos, donde el usuario podía construir pequeñas rutinas de procesador de pantalla llamadas “símbolos” que podían ensamblarse en rutinas más grandes para pintar cosas como diagtwigs de tuberías, tanques, válvulas, cosas así. Queríamos que los diagtwigs fueran “dynamics” en el sentido de que podían actualizarse de forma incremental sin tener que volver a dibujar todo el diagtwig. (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 altura anterior y simplemente actualizarse incrementalmente.

Esto suena como OOP, ¿no? Sin embargo, en lugar de “hacer” un “objeto”, podría aprovechar la predictibilidad de la secuencia de ejecución del procedimiento del diagtwig. Podría escribir la altura de la barra en una secuencia de bytes secuencial. Luego, para actualizar la imagen, podría simplemente ejecutar el procedimiento en un modo donde lea secuencialmente sus parámetros anteriores mientras escribe los nuevos parámetros para estar listo para la siguiente actualización.

Esto parece estúpidamente obvio y parecería romperse tan pronto como el procedimiento contenga un condicional, porque entonces la nueva secuencia y la 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 a mí mismo, y luego probar, que esto siempre funcionaría, siempre que se siguiera una regla simple (la “regla del modo borrar”).

El resultado neto es que el usuario podría diseñar estos “símbolos dynamics” y ensamblarlos en diagtwigs más grandes, sin tener que preocuparse por cómo se actualizarían dinámicamente, sin importar cuán compleja o estructuralmente sea la pantalla.

En aquellos días, tenía que preocuparme por la interferencia entre los objetos visuales, de modo que borrar uno no dañaría a los demás. Sin embargo, ahora uso la técnica con los controles de Windows y dejo que Windows se encargue de los problemas de representación.

Entonces, ¿qué logra? Significa que puedo construir un diálogo escribiendo un procedimiento para pintar los controles, y no tengo que preocuparme por recordar los objetos de control ni por actualizarlos incrementalmente, o hacer que aparezcan / desaparezcan / muevan según lo exijan las condiciones. El resultado es un código fuente de diálogo mucho más pequeño y simple, en un orden de magnitud, y cosas como el diseño dynamic o la alteración del número de controles o tener matrices o cuadrículas de controles son triviales. Además, un control como un campo de edición puede vincularse trivialmente a los datos de la aplicación que está editando, y siempre será probablemente correcto, y nunca tendré que ocuparme de sus eventos. Poner en un campo de edición para una variable de cadena de aplicación es una edición de una línea.

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

Lo que he encontrado más difícil de explicar es que requiere pensar diferente sobre el software. Los progtwigdores están tan firmemente vinculados a la vista de acción del objeto del software que quieren saber cuáles son los objetos, cuáles son las clases, cómo “crean” la pantalla y cómo manejan los eventos, que se necesita una cereza. bomba para expulsarlos de allí. Lo que trato de transmitir es que lo que realmente importa es ¿qué necesitas decir? Imagine que está creando un lenguaje específico de dominio (DSL) donde todo lo que necesita 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 usted . Por ejemplo, en Win32 existe este “lenguaje de recursos” para definir diálogos. Es un DSL perfectamente bueno, excepto que no va lo suficientemente lejos. No “vive” en el idioma de procedimiento principal, ni maneja los eventos por usted, ni contiene bucles / condicionales / subrutinas. Pero significa bien, y Dynamic Dialogs intenta terminar el trabajo.

Entonces, el diferente modo de pensar es: para escribir un progtwig, primero encuentras (o inventas) un DSL apropiado, y codificas la mayor cantidad posible de tu progtwig. Deje que se ocupe de todos los objetos y acciones que solo existen para la implementación.

Si realmente quiere entender la ejecución diferencial y usarla, hay un par de cuestiones delicadas que pueden hacer que se tropiece. Una vez lo codifiqué en macros Lisp , donde estos bits difíciles podrían manejarse para ti, pero en lenguajes “normales” se requiere cierta disciplina del progtwigdor para evitar las trampas.

Perdón por ser tan prolijo. Si no tengo sentido, te agradecería que lo señalaras y pudiera intentar solucionarlo.

Adicional:

En Java Swing , hay un progtwig de ejemplo llamado TextInputDemo. Es un diálogo estático, tomando 270 líneas (sin contar la lista de 50 estados). En Diálogos dynamics (en MFC), se trata de 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:

Aquí hay un código de ejemplo para editar una matriz de pacientes de hospital en aproximadamente 40 líneas de código. Las líneas 1-6 definen la “base de datos”. Las líneas 10-23 definen el contenido general de la IU. Las líneas 30-48 definen los controles para editar el registro de un solo paciente. Tenga en cuenta que la forma del progtwig casi no toma nota de los eventos a tiempo, como si todo lo que tenía que hacer fuera crear la pantalla una vez. Luego, si los sujetos son agregados o eliminados u ocurren otros cambios estructurales, simplemente se vuelve a ejecutar, como si se estuviera recreando desde cero, excepto que DE ocasiona que la actualización incremental se realice en su lugar. La ventaja es que usted, el progtwigdor, no tiene que prestar atención ni escribir ningún código para que las actualizaciones incrementales de la IU sucedan, y se garantiza que son correctas. Podría parecer que esta nueva ejecución sería un problema de rendimiento, pero no lo es, ya que la actualización de los controles que no es necesario cambiar toma el orden de decenas de nanosegundos.

 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, iname)); 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é hace realmente la statement “if (deButton (50, 20,” Add “)) {“. ¿Qué hace la función deButton? Además, ¿tus bucles FOR / END usan 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 produce una acción de entrada del usuario, el código se ejecuta en el modo “evento de control”, en el que deButton detecta que se presionó y significa que se presionó al devolver VERDADERO. Por lo tanto, el “if (deButton (…)) {… código de acción …} es una forma de asociar 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 realiza la acción porque la acción puede haber modificado los datos de la aplicación, por lo que no es válido continuar el paso de “evento de control” a través de la rutina. Si lo compara con escribir controladores de eventos, le ahorra escribirlos, y te permite tener varios controles.

Agregado: Lo siento, debería explicar lo que quiero decir con la palabra “mantiene”. Cuando el procedimiento se ejecuta por primera vez (en el modo MOSTRAR), deButton crea un control de botón y recuerda su identificación en el FIFO. En pases posteriores (en modo ACTUALIZACIÓN), deButton obtiene la identificación de la FIFO, la modifica si es necesario y la vuelve a colocar en la FIFO. En el modo ERASE, lo lee del FIFO, lo destruye y no lo vuelve a poner, por lo tanto lo “recoge basura”. Entonces, la llamada a deButton administra toda la vida 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 se graba, y luego el procedimiento deContents se ejecuta en modo EVENTO. deButton obtiene la identificación de su control de botón de la FIFO y pregunta si este es el control en el que se hizo clic. Si lo fue, devuelve TRUE para que se pueda ejecutar el código de acción. Si no, solo devuelve FALSO. Por otro lado, deEdit(..., &myStringVar) detecta si el evento fue diseñado para é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 este y el proceso normal de ACTUALIZACIÓN, myStringVar siempre es igual al contenido del control de edición. Así es como se hace “vinculante”. La misma idea se aplica a barras de desplazamiento, cuadros de lista, cuadros combinados, cualquier tipo de control que le permite editar datos de aplicaciones.

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 tu código en función de eventos externos. Esto generalmente se hace manipulando una estructura de datos de algún tipo para hacer una crónica de 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 los cambios y la manipulación real de los datos de soporte. Lo cual es bueno para múltiples procesadores. Dos, proporciona un método de ancho de banda bajo para comunicar los cambios en su progtwig.

Piensa 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 decir. El monitor muestra lo que está en el búfer de salida; simplemente arrastra esta información cada 1/60 de segundo sin importar lo que haga.

Ahora, ¿por qué quieres que tu progtwig actualice todo el buffer 60 veces por segundo si la imagen no cambia tan seguido? ¿Qué pasa si solo cambia un píxel de la imagen, debería reescribir todo el buffer?


Esta es una abstracción de la idea básica: desea cambiar el búfer de salida según la información que desea mostrar en la pantalla. Desea ahorrar tanto tiempo de CPU y tiempo de escritura de búfer como sea posible, por lo que no edita 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 (progtwigs). Se lee desde el búfer de salida a la velocidad que actualiza la pantalla. Queremos que nuestra computadora deje de sincronizar y redibujar 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 “primitivas de forma” (que pueden ser píxeles en su aplicación, pero también podrían ser líneas, rectangularjs, elementos fáciles de dibujar porque son solo formas, no se necesitan datos innecesarios). permitido).

Entonces, ¿quieres dibujar / borrar cosas de la pantalla? No hay problema. En función del contenido de la cola FIFO, conozco el aspecto del monitor en este momento. Comparo mi salida deseada (para borrar o dibujar nuevas primitivas) con la cola FIFO y solo cambio valores que necesitan ser cambiados / actualizados. Este es el paso que le da el nombre Evaluación Diferencial.

Dos formas distintas en que aprecio esto:

Primero: Mike Dunlavey usa una extensión de enunciado condicional. La cola FIFO contiene mucha información (el “estado anterior” o las cosas actuales en el monitor o el 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 / en el búfer.

El segundo: Este es solo un ejemplo, y creo que lo que Mike realmente está entendiendo es algo que debería ser fundamental en el diseño de todos los proyectos: reduzca la complejidad (computacional) del diseño escribiendo sus operaciones computacionalmente intensas como cerebros computarizados o tan cerca como puedas. Respete el calendario natural de los dispositivos.

Un método de redibujar para dibujar toda la pantalla es increíblemente costoso, y hay otras aplicaciones donde 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 así como un monitor de computadora. En cambio, los objetos simplemente parpadean con el monitor. Cada vez que un objeto se mueve, ahora es un nuevo conjunto de primitivas y el antiguo conjunto de primitivas se apaga.

Cada vez que el monitor extrae del buffer, tenemos entradas que se parecen a

 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 votación sensible al tiempo). Podemos manejarlo de manera más inteligente de lo que lo hará un objeto cuando solicita ansiosamente 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 progtwig es capaz de generar, y que unimos 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 indicadores que todos deben evaluar como verdaderos).

Si ejecutamos el progtwig, podemos dibujar en la pantalla esencialmente a la misma velocidad con la que podemos evaluar todos estos condicionales. (Peor caso: cuánto tiempo lleva evaluar el mayor conjunto de declaraciones condicionales).

Ahora, para cualquier estado en el progtwig, podemos simplemente evaluar todos los condicionales y enviar a la pantalla de forma rápida como un rayo. (Conocemos nuestras primitivas formas y sus declaraciones if dependientes).

Esto sería como comprar un juego gráficamente intenso. Solo que en lugar de instalarlo en su HDD y ejecutarlo a través de su procesador, compra una placa totalmente 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 circuitos). Esto, naturalmente, sería muy receptivo, pero casi no ofrece soporte para corregir errores, ya que el diseño de la placa entera cambia cuando se 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 la claridad en la forma en que representamos los datos internamente, hemos obtenido una “capacidad de respuesta” significativa porque ya no estamos haciendo “pensar” en la computadora; todo es reflection de 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 computadora y monitor) algo que pueda hacer bien. El “pensamiento informático” se puede hacer en términos de conceptos como objetos … El cerebro de la computadora gustosamente intentará pensarlo todo por usted, pero puede simplificar mucho la tarea si puede dejar que la computadora piense términos de data_update y conditional_evals. Nuestras abstracciones humanas de conceptos en código son idealistas, y en el caso de los progtwigs internos de dibujar un progtwig demasiado idealista. Cuando lo único que desea es un resultado (una matriz de píxeles con valores de color correctos) y tiene una máquina que puede escupir fácilmente una matriz de un tamaño de 1/60 de segundo, intente eliminar tanto pensamiento floral del cerebro de la computadora como posible para que pueda enfocarse 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 saber de otros ejemplos, pero estoy seguro de que hay muchos. Creo que cualquier cosa que proporcione una “ventana” en tiempo real al 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 de acuerdo con (SU CÓDIGO AQUÍ). Esta entrada de stream no es más que la salida anterior + (USUARIO, INTERACT AQUÍ).

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

A continuación, interconecte las máquinas en su superficie, permítales compartir notas, de acuerdo con (SU CÓDIGO AQUÍ), y ahora lo hacemos inteligente. Se convertirá en un sistema de computación interactivo.

Entonces solo tiene que proporcionar su lógica en dos lugares en el modelo anterior; el rest está a cargo del diseño de la máquina. Eso es lo bueno de eso.