language agnostic - ¿Qué es la ejecución diferencial?

language-agnostic differential-execution (2)

Leí todas las cosas que puedo encontrar y miré el video y tomaré una foto de la descripción de los primeros principios.

Visión general

Este es un patrón de diseño basado en DSL para implementar interfaces de usuario y quizás otros subsistemas orientados al estado de una manera limpia y eficiente. Se centra en el problema de cambiar la configuración de la GUI para que coincida con el estado actual del programa, donde ese estado incluye la condición de los propios widgets de la GUI, por ejemplo, el usuario selecciona pestañas, botones de radio y elementos de menú, y los widgets aparecen / desaparecen en formas arbitrariamente complejas.

Descripción

El patrón asume:

Una colección global de objetos que necesita actualizaciones periódicas.
Una familia de tipos para esos objetos, donde las instancias tienen parámetros.
Un conjunto de operaciones en C:
- Agregar AP : coloque un nuevo objeto A en C con los parámetros P.
- Modificar AP - Cambie los parámetros del objeto A en C a P.
- Eliminar A - Eliminar objeto A de C.
Una actualización de C consiste en una secuencia de tales operaciones para transformar C en una colección de destino determinada, digamos C ''.
Dada la actual colección C y el objetivo C '', el objetivo es encontrar la actualización con el costo mínimo. Cada operación tiene costo unitario.
El conjunto de colecciones posibles se describe en un lenguaje específico del dominio (DSL) que tiene los siguientes comandos:
- Crear AH : crear una instancia de algún objeto A, usando las sugerencias opcionales H, y agregarlo al estado global. (Tenga en cuenta que no hay parámetros aquí.)
- Si B, luego T si no F : ejecute condicionalmente la secuencia de comandos T o F según la función booleana B, que puede depender de cualquier cosa en el programa en ejecución.

En todos los ejemplos,

El estado global es una pantalla o ventana GUI.
Los objetos son widgets de interfaz de usuario. Los tipos son botón, cuadro desplegable, campo de texto, ...
Los parámetros controlan la apariencia y el comportamiento del widget.
Cada actualización consiste en agregar, eliminar y modificar (por ejemplo, reubicar) cualquier número de widgets en la GUI.
Los comandos Crear están creando widgets: botones, cuadros desplegables, ...
Las funciones booleanas dependen del estado del programa subyacente, incluida la condición de los controles de la GUI. Así que cambiar un control puede afectar la pantalla.

Enlaces perdidos

El inventor nunca lo afirma explícitamente, pero una idea clave es que ejecutamos el intérprete DSL sobre el programa que representa todas las posibles colecciones (pantallas) de destino cada vez que esperamos que cualquier combinación de los valores de la función booleana B haya cambiado. El intérprete maneja el trabajo sucio de hacer que la colección (pantalla) sea consistente con los nuevos valores B emitiendo una secuencia de operaciones de Agregar, Eliminar y Modificar.

Hay una suposición final oculta: el intérprete DSL incluye un algoritmo que puede proporcionar los parámetros para las operaciones de Agregar y Modificar en función del historial de Creates ejecutados hasta el momento durante su ejecución actual. En el contexto de la GUI, este es el algoritmo de diseño, y los consejos Crear son consejos de diseño.

Línea de golpe

El poder de la técnica radica en la forma en que la complejidad se encapsula en el intérprete DSL. Un intérprete estúpido comenzaría por eliminar todos los objetos (widgets) en la colección (pantalla), luego agregar uno nuevo para cada comando Crear a medida que los ve mientras recorre el programa DSL. Modificar nunca se produciría.

La ejecución diferencial es solo una estrategia más inteligente para el intérprete. Se trata de mantener una grabación serializada de la última ejecución del intérprete. Esto tiene sentido porque la grabación captura lo que hay actualmente en la pantalla. Durante la ejecución actual, el intérprete consulta la grabación para tomar decisiones sobre cómo realizar la recopilación de destino (configuración del widget) con las operaciones que tienen el menor costo. Esto se reduce a nunca Eliminar un objeto (widget) solo para agregarlo nuevamente más tarde por un costo de 2. En su lugar, siempre se modificará, lo que tiene un costo de 1. Si sucede que ejecutamos el intérprete en algún caso donde los valores B no ha cambiado, el algoritmo DE no generará ninguna operación: el flujo grabado ya representa el objetivo.

A medida que el intérprete ejecuta comandos, también está configurando la grabación para su próxima ejecución.

Un algoritmo análogo

El algoritmo tiene el mismo sabor que la distancia de edición mínima (MED). Sin embargo, la DE es un problema más sencillo que la MED porque no hay "caracteres repetidos" en las cadenas de ejecución serializadas de la DE, como en la MED. Esto significa que podemos encontrar una solución óptima con un algoritmo codicioso en línea sencillo en lugar de programación dinámica. Eso es lo que hace el algoritmo del inventor.

Fortalezas

Mi opinión es que este es un buen patrón para implementar sistemas con muchas formas complejas en las que desea un control total sobre la colocación de los widgets con su propio algoritmo de diseño y / o la lógica de "si más" de lo que está visible está profundamente anidada. Si hay K nidos de "si hay otros" N en la lógica de la forma, entonces hay K * 2 ^ N diseños diferentes para corregirlos. Los sistemas de diseño de formas tradicionales (al menos los que he usado) no soportan valores K, N más grandes en absoluto. Tiende a terminar con una gran cantidad de diseños y lógica ad hoc para seleccionarlos que son feos y difíciles de mantener. Este patrón DSL parece una forma de evitar todo eso. En sistemas con formas suficientes para compensar el costo del intérprete DSL, incluso sería más barato durante la implementación inicial. La separación de las preocupaciones es también una fortaleza. Los programas DSL abstraen el contenido de los formularios, mientras que el intérprete es la estrategia de diseño, actuando sobre las sugerencias del DSL. El diseño correcto de la sugerencia de diseño y DSL parece ser un problema importante y genial en sí mismo.

Cuestionable...

No estoy seguro de que evitar Eliminar / Agregar pares en favor de Modificar valga la pena en los sistemas modernos. El inventor parece estar más orgulloso de esta optimización, pero la idea más importante es un DSL conciso con condicionales para representar formas, con una complejidad de diseño aislada en el intérprete DSL.

Resumen

Hasta el momento, el inventor se ha centrado en los detalles profundos de cómo el intérprete toma sus decisiones. Esto es confuso porque está dirigido a los árboles, mientras que el bosque es de mayor interés. Esta es una descripción del bosque.

Me encontré con una pregunta de desbordamiento de pila, ¿cómo funciona la ejecución diferencial? , que tiene una respuesta MUY larga y detallada. Todo tenía sentido ... pero cuando terminé todavía no tenía idea de qué diablos es la ejecución diferencial. ¿Qué es realmente?

REVISADO. Este es mi N º intento de explicarlo.

Supongamos que tiene un procedimiento determinista simple que se ejecuta repetidamente, siempre siguiendo la misma secuencia de ejecuciones de instrucciones o llamadas a procedimientos. El procedimiento se llama a sí mismo, escribe lo que quiera secuencialmente en un FIFO, y leen el mismo número de bytes desde el otro extremo del FIFO, como esto: **

Los procedimientos a los que se llama utilizan el FIFO como memoria, porque lo que leen es el mismo que escribieron en la ejecución anterior. Entonces, si sus argumentos son diferentes esta vez desde la última vez, pueden ver eso y hacer lo que quieran con esa información.

Para comenzar, tiene que haber una ejecución inicial en la que solo se produzca la escritura, no la lectura. Simétricamente, debería haber una ejecución final en la que solo ocurra la lectura, no la escritura. Así que hay un registro de modo "global" que contiene dos bits, uno que permite la lectura y otro que permite la escritura, como esto:

La ejecución inicial se realiza en el modo 01 , por lo que solo se realiza la escritura. Las llamadas al procedimiento pueden ver el modo, por lo que saben que no hay un historial anterior. Si quieren crear objetos, pueden, y colocar la información de identificación en el FIFO (no es necesario almacenar en variables).

Las ejecuciones intermedias se realizan en el modo 11 , por lo que se producen tanto la lectura como la escritura, y las llamadas al procedimiento pueden detectar cambios en los datos. Si hay objetos que se deben mantener actualizados, su información de identificación se lee y se escribe en el FIFO, de modo que se puede acceder a ellos y, si es necesario, modificarlos.

La ejecución final se realiza en el modo 10 , por lo que solo ocurre la lectura. En ese modo, el procedimiento llama a saber que solo están limpiando. Si se mantuvieron objetos, sus identificadores se leen desde el FIFO y se pueden eliminar.

Pero los procedimientos reales no siempre siguen la misma secuencia. Contienen declaraciones IF (y otras formas de variar lo que hacen). ¿Cómo se puede manejar eso?

La respuesta es un tipo especial de instrucción IF (y su instrucción ENDIF de terminación). Así es como funciona. Escribe el valor booleano de su expresión de prueba y lee el valor que tuvo la expresión de prueba la última vez. De esa manera, puede saber si la expresión de prueba ha cambiado y actuar. La acción que realiza es alterar temporalmente el registro de modo .

Específicamente, x es el valor anterior de la expresión de prueba, leída del FIFO (si la lectura está habilitada, de lo contrario 0), y y es el valor actual de la expresión de prueba, escrita en el FIFO (si la escritura está habilitada). (En realidad, si la escritura no está habilitada, la expresión de prueba ni siquiera se evalúa, y y es 0.) Entonces , x, y simplemente enmascara el registro de modo r, w . Entonces, si la expresión de prueba cambió de Verdadero a Falso, el cuerpo se ejecuta en modo de solo lectura. A la inversa, si ha cambiado de Falso a Verdadero, el cuerpo se ejecuta en modo de solo escritura. Si el resultado es 00 , se omite el código dentro de la declaración IF..ENDIF. (Es posible que desee pensar un poco acerca de si esto cubre todos los casos; lo hace).

Puede que no sea obvio, pero estas declaraciones IF..ENDIF pueden estar anidadas arbitrariamente, y pueden extenderse a todos los otros tipos de declaraciones condicionales como ELSE, SWITCH, WHILE, FOR e incluso llamadas a funciones basadas en punteros. También es cierto que el procedimiento se puede dividir en subprocedimientos en la medida que se desee, incluido el recursivo, siempre que se obedezca el modo.

(Hay una regla que debe seguirse, llamada regla de modo de borrado , que es que en el modo 10 no se debe realizar ningún cálculo de ninguna consecuencia, como seguir un puntero o indexar una matriz. Conceptualmente, la razón es que el modo 10 existe solo con el propósito de deshacerse de cosas.)

Por lo tanto, es una estructura de control interesante que se puede explotar para detectar cambios, generalmente cambios en los datos, y tomar medidas sobre esos cambios.

Su uso en interfaces gráficas de usuario es mantener algún conjunto de controles u otros objetos de acuerdo con la información del estado del programa. Para ese uso, los tres modos se llaman MOSTRAR (01), ACTUALIZAR (11) y BORRAR (10). El procedimiento se ejecuta inicialmente en el modo MOSTRAR, en el que se crean los controles, y la información relevante para ellos llena el FIFO. Luego, se realiza cualquier número de ejecuciones en el modo ACTUALIZACIÓN, donde los controles se modifican según sea necesario para mantenerse al día con el estado del programa. Finalmente, hay una ejecución en modo BORRAR, en la que los controles se eliminan de la interfaz de usuario y se vacía el FIFO.

El beneficio de hacer esto es que, una vez que haya escrito el procedimiento para crear todos los controles, como una función del estado del programa, no tiene que escribir nada más para mantenerlo actualizado o limpiarlo después. Cualquier cosa que no tenga que escribir significa menos oportunidades de cometer errores. (Hay una forma sencilla de manejar los eventos de entrada del usuario sin tener que escribir controladores de eventos y crear nombres para ellos. Esto se explica en uno de los videos vinculados a continuación).

En términos de administración de memoria, no tiene que inventar nombres de variables o estructura de datos para mantener los controles. Solo usa suficiente almacenamiento a la vez para los controles actualmente visibles, mientras que los controles potencialmente visibles pueden ser ilimitados. Además, nunca hay ninguna preocupación acerca de la recolección de basura de los controles utilizados anteriormente: el FIFO actúa como un recolector automático de basura.

En términos de rendimiento, cuando está creando, eliminando o modificando controles, es un gasto de tiempo que debe gastarse de todos modos. Cuando se trata simplemente de actualizar los controles y no hay ningún cambio, los ciclos necesarios para realizar la lectura, escritura y comparación son microscópicos en comparación con los controles de alteración.

Otra consideración de rendimiento y corrección, en relación con los sistemas que actualizan las pantallas en respuesta a los eventos, es que dicho sistema requiere que se responda a todos los eventos, y ninguno dos veces; de lo contrario, la pantalla será incorrecta, aunque algunas secuencias de eventos pueden ser auto-identificadas cancelado. Bajo la ejecución diferencial, los pases de actualización se pueden realizar tan a menudo o tan raramente como se desee, y la visualización siempre es correcta al final de un pase.

Aquí hay un ejemplo extremadamente abreviado donde hay 4 botones, de los cuales los botones 2 y 3 están condicionados a una variable booleana.

En la primera pasada, en el modo Mostrar, el valor booleano es falso, por lo que solo aparecen los botones 1 y 4.
Luego, el valor booleano se establece en verdadero y el paso 2 se realiza en el modo de actualización, en el que los botones 2 y 3 se crean instancias y el botón 4 se mueve, dando el mismo resultado que si el valor booleano hubiera sido verdadero en el primer paso.
Luego, el valor booleano se configura como falso y el paso 3 se realiza en el modo de actualización, lo que hace que los botones 2 y 3 se eliminen y el botón 4 retroceda hasta donde estaba antes.
Finalmente, el paso 4 se realiza en el modo Borrar, haciendo que todo desaparezca.

(En este ejemplo, los cambios se deshacen en el orden inverso a como se hicieron, pero eso no es necesario. Los cambios se pueden hacer y deshacer en cualquier orden).

Tenga en cuenta que, en todo momento, el FIFO, que consta de Antiguo y Nuevo concatenados, contiene exactamente los parámetros de los botones visibles más el valor booleano.

El objetivo de esto es mostrar cómo un solo procedimiento de "pintura" también se puede utilizar, sin cambios, para la actualización y el borrado incrementales automáticos arbitrarios. Espero que quede claro que funciona para la profundidad arbitraria de las llamadas de subprocedimiento y el anidamiento arbitrario de condicionales, incluido el switch , while y for bucles, llamadas a funciones basadas en punteros, etc. Si tengo que explicar eso, entonces Abierto a disparos para hacer la explicación demasiado complicada.

Finalmente, hay un par de videos crudos pero cortos publicados aquí .

** Técnicamente, tienen que leer el mismo número de bytes que escribieron la última vez. Entonces, por ejemplo, podrían haber escrito una cadena precedida por un conteo de caracteres, y eso está bien.

AGREGADO: Me tomó mucho tiempo estar seguro de que esto siempre funcionaría. Finalmente lo probé. Se basa en una propiedad de sincronización , lo que significa que, en cualquier punto del programa, el número de bytes escritos en el pase anterior es igual al número leído en el pase posterior. La idea detrás de la prueba es hacerlo por inducción en la longitud del programa. El caso más difícil de probar es el caso de una sección del programa que consta de s1 seguido de una IF (prueba) s2 ENDIF , donde s1 y s2 son subsecciones del programa, cada una de las cuales satisface la propiedad Sync . Hacerlo solo en texto es satinado, pero aquí he intentado diagramarlo:

Define la propiedad de sincronización y muestra el número de bytes escritos y leídos en cada punto del código, y muestra que son iguales. Los puntos clave son que 1) el valor de la expresión de prueba (0 o 1) leída en la pasada actual debe ser igual al valor escrito en la pasada anterior, y 2 ) se cumple la condición de Sincronización (s2) . Esto satisface la propiedad de sincronización para el programa combinado.