Что такое дифференциальное исполнение?

Ответ 1

перераб. Это моя N-я попытка объяснить это.

Предположим, что у вас есть простая детерминированная процедура, которая выполняется повторно, всегда следуя той же последовательности выполнения операторов или вызовов процедур. Процедура вызывает себя, пишут все, что они хотят последовательно, в FIFO, и они читают одинаковое количество байтов с другого конца FIFO, например: **

Вызываемые процедуры используют FIFO в качестве памяти, поскольку то, что они читают, совпадает с тем, что они пишут при предыдущем выполнении. Так что, если их аргументы будут отличаться на этот раз с последнего времени, они могут это увидеть и делать все, что захотят, с этой информацией.

Чтобы начать работу, должно быть начальное выполнение, в котором происходит только запись, без чтения. Симметрично должно быть окончательное исполнение, в котором происходит только чтение, без записи. Таким образом, существует "глобальный" регистр режима, содержащий два бита, один из которых позволяет читать и один, который позволяет записывать, например:

Первоначальное выполнение выполняется в режиме 01, поэтому выполняется только запись. Вызовы процедуры могут видеть режим, поэтому они знают, что нет предшествующей истории. Если они хотят создавать объекты, которые они могут, и помещают идентифицирующую информацию в FIFO (нет необходимости хранить в переменных).

Промежуточные исполнения выполняются в режиме 11, поэтому происходит как чтение, так и запись, а вызовы процедур могут обнаруживать изменения данных. Если есть объекты, которые нужно обновлять, их идентификационная информация считывается и записывается в FIFO, поэтому они могут быть доступны и, при необходимости, изменены.

Окончательное исполнение выполняется в режиме 10, поэтому происходит только чтение. В этом режиме вызовы процедур знают, что они просто убираются. Если были сохранены какие-либо объекты, их идентификаторы считываются из FIFO, и их можно удалить.

Но реальные процедуры не всегда соответствуют одной и той же последовательности. Они содержат утверждения IF (и другие способы изменения того, что они делают). Как это можно обработать?

Ответ - это особый тип оператора IF (и его завершающая инструкция ENDIF). Вот как это работает. Он записывает логическое значение своего тестового выражения и считывает значение, которое испытательное выражение имело в прошлый раз. Таким образом, он может определить, изменилось ли тестовое выражение и принять меры. Требуемое действие - временно изменить регистр режима.

В частности, x является предшествующим значением тестового выражения, считанным из FIFO (если чтение включено, else 0), а y - текущее значение тестового выражения, записанное в FIFO (если запись включена), (На самом деле, если запись не включена, тестовое выражение даже не оценивается, а y равно 0.) Тогда x, y просто MASKs регистр режима r, w. Поэтому, если тестовое выражение изменилось с True на False, тело выполняется в режиме только для чтения. И наоборот, если он изменился с False на True, тело выполняется в режиме только для записи. Если результат равен 00, код внутри инструкции IF..ENDIF пропускается. (Возможно, вы захотите немного подумать о том, охватывает ли это все случаи - он это делает.)

Это может быть не очевидно, но эти утверждения IF..ENDIF могут быть произвольно вложенными и могут быть расширены для всех других условных операторов, таких как ELSE, SWITCH, WHILE, FOR и даже для вызова функций на основе указателей. Кроме того, процедура может быть разделена на подпроцедуры в любой желаемой степени, включая рекурсивную, до тех пор, пока выполняется режим.

(Существует правило, которое необходимо соблюдать, называемое правилом режима стирания, которое заключается в том, что в режиме 10 никакое вычисление каких-либо последствий, таких как слежение за указателем или индексирование массива, должно быть выполнено. что режим 10 существует только для того, чтобы избавиться от всего.)

Таким образом, это интересная структура управления, которая может быть использована для обнаружения изменений, как правило, изменений данных и принятия мер по этим изменениям.

Его использование в графических пользовательских интерфейсах заключается в том, чтобы сохранить некоторый набор элементов управления или других объектов в соответствии с информацией о состоянии программы. Для этого использования три режима называются SHOW (01), UPDATE (11) и ERASE (10). Процедура изначально выполняется в режиме SHOW, в которой создаются элементы управления, а информация, относящаяся к ним, заполняет FIFO. Затем любое количество исполнений выполняется в режиме UPDATE, где элементы управления изменяются по мере необходимости, чтобы оставаться в курсе состояния программы. Наконец, выполняется выполнение в режиме ERASE, в котором элементы управления удаляются из пользовательского интерфейса, а FIFO освобождается.

Преимущество этого заключается в том, что после того, как вы написали процедуру для создания всех элементов управления, как функцию состояния программы, вам не нужно писать что-либо еще, чтобы впоследствии обновлять или очищать. Все, что вам не нужно писать, означает меньше возможностей совершать ошибки. (Существует простой способ обработки пользовательских событий ввода без необходимости писать обработчики событий и создавать имена для них. Это объясняется в одном из видео, приведенных ниже.)

Что касается управления памятью, вам не нужно составлять имена переменных или структуру данных для хранения элементов управления. Он использует только достаточное количество хранилища в любой момент для видимых в данный момент элементов управления, а потенциально видимые элементы управления могут быть неограниченными. Кроме того, никогда не возникает никаких проблем с сборкой мусора ранее используемых элементов управления - FIFO действует как автоматический сборщик мусора.

С точки зрения производительности, когда он создает, удаляет или изменяет элементы управления, он тратит время, которое нужно потратить в любом случае. Когда он просто обновляет элементы управления, и нет изменений, циклы, необходимые для чтения, записи и сравнения, являются микроскопическими по сравнению с изменениями элементов управления.

Еще одно соображение о производительности и правильности относительно систем, которые обновляют дисплеи в ответ на события, заключается в том, что такая система требует, чтобы на каждое событие отвечали, и ни один из них дважды, иначе отображение будет неправильным, хотя некоторые последовательности событий могут быть самоотверждающимся. При дифференциальном исполнении обновления могут выполняться так часто или как редко, и дисплей всегда корректен в конце прохода.

Вот очень сокращенный пример, где есть 4 кнопки, из которых кнопки 2 и 3 являются условными для булевой переменной.

• В первом проходе в режиме просмотра логическое значение false, поэтому появляются только кнопки 1 и 4.
• Затем логическое значение имеет значение true, а pass 2 выполняется в режиме обновления, в котором кнопки 2 и 3 создаются, а кнопка 4 перемещается, давая тот же результат, что и логическое значение true на первом проходе.
• Затем логическое значение устанавливается в false, а проход 3 выполняется в режиме обновления, заставляя кнопки 2 и 3 удаляться, а кнопка 4 - назад, где она была раньше.
• Наконец, проход 4 выполняется в режиме Erase, в результате чего все исчезает.

(В этом примере изменения отменены в обратном порядке по мере их выполнения, но это необязательно. Изменения могут быть сделаны и отменены в любом порядке.)

Обратите внимание, что во все времена FIFO, состоящий из старого и нового, объединенного вместе, содержит точно параметры видимых кнопок плюс логическое значение.

Точка зрения заключается в том, чтобы показать, как единая "краска" процедура также может быть использована без изменений для произвольного автоматического инкрементного обновления и стирания. Надеюсь, что ясно, что он работает для произвольной глубины вызовов подпроцедур и произвольного вложения условных выражений, включая циклы switch, while и for, вызывая функции на основе указателей и т.д. Если я должен это объяснить, тогда я открыт для потшотов, чтобы сделать объяснение слишком сложным.

Наконец, есть несколько сырых, но коротких видео, размещенных здесь.

** Технически, они должны прочитать такое же количество байтов, которые они написали в прошлый раз. Так, например, они могли бы написать строку, которой предшествует счетчик символов, и это ОК.

ADDED: Мне потребовалось много времени, чтобы быть уверенным, что это всегда будет работать. Я наконец доказал это. Он основан на свойстве Sync, что примерно означает, что в любой точке программы количество байтов, записанных на предыдущем проходе, равно числу, читаемому на последующем проходе. Идея доказательства состоит в том, чтобы сделать это путем индукции по длине программы. Самый сложный пример для доказательства - это раздел программы, состоящий из s1, за которым следует IF (тест) s2 ENDIF, где s1 и s2 являются подразделами программы, каждая из которых удовлетворяет свойству Sync. Сделать это в текстовом режиме - это остекление, но здесь я попытался его нарисовать:

Он определяет свойство Sync и показывает количество байтов, записанных и прочитанных в каждой точке кода, и показывает, что они равны. Ключевыми моментом является то, что 1) значение тестового выражения (0 или 1), прочитанного на текущем проходе, должно равняться значению, записанному на предыдущем проходе, и 2) выполняется условие Sync (s2). Это удовлетворяет свойству Sync для комбинированной программы.

Ответ 2

Я прочитал все материалы, которые я могу найти, и посмотрел видео, и сделаю снимок первого описания принципов.

Обзор

Это шаблон проектирования на основе DSL для реализации пользовательских интерфейсов и, возможно, других ориентированных на состояние подсистем в чистом и эффективном режиме. Он фокусируется на проблеме изменения конфигурации графического интерфейса для соответствия текущему состоянию программы, где это состояние включает в себя состояние самих виджетов графического интерфейса пользователя, например. пользователь выбирает вкладки, переключатели и пункты меню, а виджеты появляются/исчезают сколь угодно сложными способами.

Описание

Шаблон предполагает:

• Глобальная коллекция C объектов, которые нуждаются в периодических обновлениях.
• Семейство типов для этих объектов, где экземпляры имеют параметры.
• Набор операций на C:
  • Добавить A P - Поместить новый объект A в C с параметрами P.
  • Изменить A P - изменить параметры объекта A в C на P.
  • Удалить A - удалить объект A с C.
• Обновление C состоит из последовательности таких операций для преобразования C в данный целевой набор, например C '.
• Учитывая текущий сбор C и цель C ', цель состоит в том, чтобы найти обновление с минимальными затратами. Каждая операция имеет удельную стоимость.
• Набор возможных коллекций описан на языке, специфичном для домена (DSL), который имеет следующие команды:
  • Создать A H - инициировать некоторый объект A, используя необязательные подсказки H, и добавить его в глобальное состояние. (Здесь нет параметров).
  • Если B Then T Else F - условно выполнить последовательность команд T или F на основе булевой функции B, которая может зависеть от чего-либо в текущей программе.

Во всех примерах

• Глобальное состояние - это экран или окно GUI.
• Объекты - это виджеты пользовательского интерфейса. Типы - это кнопка, раскрывающийся список, текстовое поле,...
• Параметры управления виджетами и их поведение.
• Каждое обновление состоит из добавления, удаления и изменения (например, перемещения) любого количества виджетов в графическом интерфейсе.
• Команды Create создают виджеты: кнопки, выпадающие окна,...
• Булевы функции зависят от основного состояния программы, включая состояние самих элементов управления графическим интерфейсом. Таким образом, изменение элемента управления может повлиять на экран.

Отсутствующие ссылки

Изобретатель никогда явно не заявляет об этом, но ключевая идея заключается в том, что мы запускаем интерпретатор DSL по программе, который представляет все возможные целевые коллекции (экраны) каждый раз, когда мы ожидаем, что какая-либо комбинация значений логической функции B изменилась. Интерпретатор обрабатывает грязную работу по созданию коллекции (экрана) в соответствии с новыми значениями B, испуская последовательность операций добавления, удаления и изменения.

Существует окончательное скрытое предположение: интерпретатор DSL включает в себя некоторый алгоритм, который может предоставить параметры для операций Add и Modify, основанных на истории создания, выполненных до сих пор во время его текущего прогона. В контексте GUI это алгоритм компоновки, а подсказки Create - подсказки макета.

Линия перфорации

Сила техники заключается в том, как сложность инкапсулируется в интерпретаторе DSL. Глупый интерпретатор начнется с удаления всех объектов (виджетов) в коллекции (экране), а затем добавьте новый для каждой команды Create, когда он увидит их, пройдя через программу DSL. Изменение никогда не произойдет.

Дифференциальное исполнение - это более разумная стратегия для переводчика. Это означает сохранение сериализованной записи последнего исполнения интерпретатора. Это имеет смысл, потому что запись фиксирует то, что в настоящее время отображается на экране. Во время текущего прогона интерпретатор консультируется с записью, чтобы принимать решения о том, как создать целевую коллекцию (конфигурацию виджетов) с наименьшими затратами. Это сводится к тому, чтобы никогда не удалять объект (виджет) только для добавления его позже позже для стоимости 2. DE всегда будет изменять вместо этого, которая имеет стоимость 1. Если нам случится запустить интерпретатор в том случае, когда значения B не изменились, алгоритм DE не будет генерировать никаких операций вообще: записанный поток уже представляет цель.

Когда интерпретатор выполняет команды, он также настраивает запись для следующего прогона.

Аналогичный алгоритм

Алгоритм имеет тот же вкус, что и минимальное расстояние редактирования(MED). Однако DE - более простая проблема, чем MED, потому что в сериализованных строках DE нет "повторяющихся символов", как в MED. Это означает, что мы можем найти оптимальное решение с простым алгоритмом жадных алгоритмов, а не динамическим программированием. Это то, что делает алгоритм изобретателя.

Сильные стороны

Я считаю, что это хорошая модель для внедрения систем со многими сложными формами, где вам нужен полный контроль над размещением виджетов с вашим собственным алгоритмом компоновки и/или логикой "если еще", что видимо глубоко вложен. Если есть K гнезд "if elses" N глубоко в форме логики, то есть K * 2 ^ N разных макетов, чтобы получить право. Традиционные системы проектирования форм (по крайней мере те, которые я использовал) не поддерживают большие значения K, N очень хорошо. Вы, как правило, получаете большое количество аналогичных макетов и специальной логики, чтобы выбрать их, которые уродливы и трудно поддерживать. Этот шаблон DSL кажется способом избежать всего этого. В системах с достаточными формами для компенсации стоимости переводчика DSL это будет даже дешевле при первоначальной реализации. Разделение проблем также является сильным. Программы DSL абстрагируют содержание форм, в то время как интерпретатор представляет собой стратегию компоновки, действуя по подсказкам из DSL. Получение правильного дизайна подсказки DSL и макета похоже на значительную и крутую проблему сама по себе.

Сомнительный...

Я не уверен, что избегать удаления/добавления пар в пользу модификации стоит всех проблем в современных системах. Изобретатель, похоже, больше всего гордится этой оптимизацией, но более важной идеей является сжатая DSL с условными выражениями для представления форм с сложностью компоновки, изолированной в интерпретаторе DSL.

Резюме

Изобретатель до сих пор сосредоточился на глубоких подробностях того, как интерпретатор принимает свои решения. Это путано, потому что оно направлено на деревья, в то время как лес представляет большой интерес. Это описание леса.