Как выполняется дифференциальное выполнение?

Ответ 1

Джи, Брайан, мне жаль, что я не видел ваш вопрос раньше. Поскольку это в значительной степени мое "изобретение" (к лучшему или худшему), я мог бы помочь.

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

Объяснение @windfinder отличается от моего, и это нормально. Этот метод нелегко обернуть вокруг головы, и мне потребовалось около 20 лет (и так далее), чтобы найти объяснения, которые работают. Позвольте мне сделать еще один выстрел здесь:

• Что это такое?

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

Теперь представьте себе, что два компьютера выполняют один и тот же код в режиме блокировки друг с другом и могут сравнивать заметки. Компьютер 1 работает с входными данными A, а компьютер 2 работает со входными данными B. Они работают шаг за шагом рядом. Если они приходят к условному выражению, например, IF (test).... ENDIF, и если у них есть различие во мнениях относительно того, является ли тест истинным, то тот, кто говорит тест, если false, пропускает ENDIF и ждет вокруг его сестра догнать. (Вот почему код структурирован, поэтому мы знаем, что сестра в конечном итоге попадет в ENDIF.)

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

Конечно, в дифференциальном исполнении (DE) это делается с одним компьютером, имитирующим два.

СЕЙЧАС, предположим, что у вас есть только один набор входных данных, но вы хотите посмотреть, как он изменился со времени 1 на время. 2. Предположим, что программа, которую вы выполняете, является сериализатором/десериализатором. По мере выполнения вы оба сериализуете (выписываете) текущие данные и десериализуете (читаете) прошлые данные (которые были написаны в последний раз, когда вы это сделали). Теперь вы можете легко понять, какие различия существуют между данными, которые были в последний раз, и каково это на этот раз.

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

• Для чего это полезно?

Мне пришло в голову, когда я работал над графическим проектом, где пользователь мог создавать небольшие подпрограммы для отображения-обработки, называемые "символами", которые могли быть собраны в более крупные процедуры, чтобы рисовать такие вещи, как диаграммы труб, резервуаров, клапанов и т.д. как это. Мы хотели, чтобы диаграммы были "динамическими" в том смысле, что они могли инкрементно обновлять себя, не перерисовывая всю диаграмму. (Аппаратное обеспечение было медленным по сегодняшним меркам.) Я понял, что (например) подпрограмма, чтобы нарисовать панель бар-диаграммы, могла запомнить ее старую высоту и просто инкрементно обновить себя.

Это звучит как ООП, не так ли? Однако, вместо того, чтобы "делать" "объект", я мог бы воспользоваться предсказуемостью последовательности выполнения процедуры диаграммы. Я мог бы написать высоту бара в последовательном байт-потоке. Затем, чтобы обновить изображение, я мог бы просто запустить процедуру в режиме, когда он последовательно считывает свои старые параметры, когда он записывает новые параметры, чтобы быть готовым к следующему проходу обновления.

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

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

В те дни мне приходилось беспокоиться о вмешательстве между визуальными объектами, так что стирание одного не повредило бы других. Однако теперь я использую эту технику с элементами управления Windows, и я позволяю Windows заботиться о проблемах с рендерингом.

Итак, что он достиг? Это означает, что я могу создать диалог, написав процедуру рисования элементов управления, и мне не нужно беспокоиться о том, чтобы действительно запомнить объекты управления или иметь дело с постепенным их обновлением или заставить их появляться/исчезать/перемещаться по мере того, как условия гарантируются. В результате значительно меньше и проще исходный код диалога, примерно на порядок, и такие вещи, как динамическая компоновка или изменение количества элементов управления или наличие массивов или сеток элементов управления, тривиальны. Кроме того, элемент управления, такой как поле "Редактирование", может быть тривиально связан с данными приложения, которые он редактирует, и он всегда будет оправданным, и мне никогда не придется разбираться с его событиями. Вставка поля редактирования для строковой переменной приложения - это однострочное редактирование.

• Почему это трудно понять?

То, что мне показалось сложнее всего объяснить, заключается в том, что для этого требуется другое мышление о программном обеспечении. Программисты настолько прочно привязаны к объектно-ориентированному представлению программного обеспечения, что хотят знать, какие объекты, какие классы, как они "строят" дисплей, и как они обрабатывают события, что он принимает вишню чтобы выбить их из него. Я пытаюсь передать, что действительно важно, что вам нужно сказать? Представьте, что вы создаете доменный язык (DSL), где все, что вам нужно сделать, это сказать: "Я хочу редактировать переменную A здесь, переменную B там и переменную C вниз", и она волшебным образом позаботится об этом для вас, Например, в Win32 существует этот "язык ресурсов" для определения диалогов. Это совершенно хороший DSL, за исключением того, что он недостаточно далеко. Он не "живет" на основном процедурном языке или обрабатывает события для вас, или содержит циклы/условные обозначения/подпрограммы. Но это хорошо, и Dynamic Dialogs пытается завершить работу.

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

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

Извините, что так долго. Если бы у меня не было смысла, я был бы признателен, если бы вы указали это, и я могу попытаться исправить его.

Добавлено:

В Java Swing существует пример программы TextInputDemo. Это статический диалог, содержащий 270 строк (не считая списка из 50 состояний). В динамических диалогах (в MFC) это около 60 строк:

#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."));
}

Добавлено:

Здесь примерный код для редактирования массива больничных пациентов примерно в 40 строках кода. Строки 1-6 определяют "базу данных". Строки 10-23 определяют общее содержимое пользовательского интерфейса. Строки 30-48 определяют элементы управления для редактирования одной записи пациента. Обратите внимание, что форма программы почти не замечает событий во времени, как будто все, что нужно было сделать, это создать дисплей один раз. Затем, если предметы добавляются или удаляются или происходят другие структурные изменения, они просто повторно выполняются, как если бы они воссоздавались с нуля, за исключением того, что DE вызывает инкрементное обновление. Преимущество заключается в том, что вам, программисту, не нужно уделять никакого внимания или писать какой-либо код, чтобы сделать инкрементные обновления пользовательского интерфейса, и они гарантированы правильно. Может показаться, что это повторное выполнение будет проблемой производительности, но это не так, поскольку обновления элементов управления, которые не нуждаются в изменении, приобретают порядок в десятки наносекунд.

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 }

Добавлено: Брайан задал хороший вопрос, и я подумал, что ответ принадлежит главному тексту:

@Mike: Я не понимаю, что делает "if (deButton (50, 20," Добавить ")) {" инструкция на самом деле. Что делает функция deButton? Кроме того, ваши петли FOR/END используют какой-то макрос или что-то в этом роде? - Брайан.

@Brian: Да, операторы FOR/END и IF являются макросами. Проект SourceForge имеет полную реализацию. deButton поддерживает кнопочный контроль. Когда выполняется какое-либо действие пользователя, код запускается в режиме "управляющего события", в котором deButton обнаруживает, что он был нажат, и означает, что он был нажат, возвратив TRUE. Таким образом, "if (deButton (...)) {... action code...} - это способ привязки кода действия к кнопке, без необходимости создания замыкания или записи обработчика события. DD_THROW - это способ завершения передачи, когда действие принято, поскольку действие может иметь измененные данные приложения, поэтому недействительно продолжать" контрольное событие" проходить через подпрограмму.Если вы сравните это с записью обработчиков событий, это сэкономит вам написание тех, и он позволяет вам иметь любое количество элементов управления.

Добавлено: Извините, я должен объяснить, что я имею в виду под словом "поддерживает". Когда процедура сначала выполняется (в режиме SHOW), deButton создает кнопку управления и запоминает свой идентификатор в FIFO. При последующих проходах (в режиме UPDATE) дебат получает идентификатор из FIFO, при необходимости модифицирует его и помещает обратно в FIFO. В режиме ERASE он считывает его из FIFO, уничтожает его и не возвращает, тем самым "собирая мусор". Таким образом, вызов deButton управляет всем временем жизни элемента управления, сохраняя его в соответствии с данными приложения, поэтому я говорю, что он "поддерживает" его.

Четвертый режим - EVENT (или CONTROL). Когда пользователь набирает символ или нажимает кнопку, это событие захватывается и записывается, а затем процедура deContents выполняется в режиме EVENT. deButton получает идентификатор элемента управления кнопки из FIFO и спрашивает, является ли это элементом управления, который был нажат. Если это так, он возвращает TRUE, поэтому код действия может быть выполнен. Если нет, он просто возвращает FALSE. С другой стороны, deEdit(..., &myStringVar) определяет, предназначено ли событие для него, и если это так передается в элемент управления редактирования, а затем копирует содержимое элемента управления редактирования в myStringVar. Между этой и обычной обработкой UPDATE myStringVar всегда равно содержимому элемента управления редактирования. Так делается "привязка". Эта же идея применяется к полосам прокрутки, спискам, комбинированным ящикам, любому типу управления, позволяющему редактировать данные приложения.

Здесь ссылка на мою статью в Википедии: http://en.wikipedia.org/wiki/User:MikeDunlavey/Difex_Article

Ответ 2

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

Основной поток выглядит следующим образом:

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)

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

Ответ 3

Подумайте, как работает монитор:

Он обновляется на 60 Гц - 60 раз в секунду. Мерцание мерцания мерцает 60 раз, но ваши глаза медленные и не могут сказать. Монитор показывает, что находится в выходном буфере; он просто перетаскивает эти данные каждые 1/60 секунды, независимо от того, что вы делаете.

Теперь почему вы хотите, чтобы ваша программа обновляла весь буфер 60 раз в секунду, если изображение не должно часто меняться? Что делать, если вы меняете только один пиксель изображения, следует ли переписать весь буфер?

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

Монитор отделен от вашего компьютера и логики (программ). Он считывает из выходного буфера любой скоростью, когда он обновляет экран. Мы хотим, чтобы наш компьютер прекратил синхронизацию и перерисовку без необходимости. Мы можем решить это, изменив работу с буфером, что может быть сделано различными способами. Его техника реализует очередь FIFO, которая находится на задержке - она ​​содержит то, что мы только что отправили в буфер. Задержка в очереди FIFO не содержит данные пикселя, она содержит "примитивы формы" (которые могут быть пикселями в вашем приложении, но также могут быть линиями, прямоугольниками, удобными для рисования вещами, поскольку они представляют собой только фигуры, без лишних данных допускается).

Итак, вы хотите рисовать/стирать вещи с экрана? Нет проблем. Основываясь на содержимом очереди FIFO, я знаю, как выглядит монитор на данный момент. Я сравниваю свой желаемый результат (для стирания или рисования новых примитивов) с очередью FIFO и изменяю только значения, которые необходимо изменить/обновить. Это шаг, который дает ему название "Дифференциальная оценка".

Два разных способа, в которых я ценю это:

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

В каждый слот, который может содержать примитив в очереди FIFO, добавляется условный бит.

0 means erase
1 means draw

Однако мы имеем предыдущее состояние:

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);

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

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

Метод перерисовывания для рисования всего экрана невероятно дорог, и есть другие приложения, в которых это понимание невероятно ценно.

Мы никогда не "перемещаем" объекты по экрану. "Перемещение" - дорогостоящая операция, если мы собираемся подражать физическому действию "перемещения", когда мы разрабатываем код для чего-то вроде монитора компьютера. Вместо этого объекты в основном просто мерцают на мониторе. Каждый раз, когда объект перемещается, теперь появляется новый набор примитивов, и старый набор примитивов мерцает.

Каждый раз, когда монитор вытягивается из буфера, у нас есть записи, которые выглядят как

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

Никогда не взаимодействует объект с экраном (или чувствительным по времени устройством опроса). Мы можем справиться с этим более разумно, чем объект, когда он с жадностью просит обновить весь экран, чтобы показать изменение, относящееся только к самому себе.

Скажем, у нас есть список всех возможных графических примитивов, которые наша программа способна генерировать, и что мы связываем каждый примитив с набором условных операторов

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

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

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

Теперь, для любого состояния в программе, мы можем просто оценить все условные выражения и вывести на экран молниеносно! (Мы знаем наши примитивы формы и их зависимые if-утверждения.)

Это будет похоже на покупку графически насыщенной игры. Только вместо того, чтобы устанавливать его на свой жесткий диск и запускать его через ваш процессор, вы покупаете совершенно новую плату, которая содержит всю игру и принимает в качестве входных данных: мышь, клавиатуру и принимает на выходе: монитор. Невероятно сжатая условная оценка (поскольку наиболее фундаментальной формой условного является логические ворота на печатных платах). Разумеется, это будет очень отзывчиво, но почти не помогает в исправлении ошибок, так как вся конструкция платы меняется, когда вы делаете крошечное изменение дизайна (поскольку "дизайн" настолько далек от характера печатной платы). За счет гибкости и ясности в том, как мы представляем данные внутри, мы получили значительную "отзывчивость", потому что мы больше не делаем "мышления" в компьютере; это всего лишь рефлекс для печатной платы на основе входов.

Урок, как я понимаю, состоит в том, чтобы разделить труд таким образом, что вы отдаете каждую часть системы (не обязательно просто компьютер и монитор), что она может преуспеть. "Компьютерное мышление" можно сделать с точки зрения таких понятий, как объекты... Компьютерный мозг с радостью попытается все это продумать, но вы можете значительно упростить задачу, если сможете позволить компьютеру подумать условия data_update и условные_веды. Наши человеческие абстракции понятий в код являются идеалистическими, а в случае внутренней программы методы рисования немного чрезмерно идеалистичны. Когда все, что вы хотите, является результатом (массив пикселей с правильными значениями цвета), и у вас есть машина, которая может легко выплюнуть массив, который будет производиться каждые 1/60 секунды, попробуйте и устраните столько цветочного мышления от мозга компьютера, сколько возможно, чтобы вы могли сосредоточиться на том, что вы действительно хотите: синхронизировать свои графические обновления с вашими (быстрыми) входами и естественным поведением монитора.

Как это относится к другим приложениям? Я хотел бы услышать другие примеры, но я уверен, что их много. Я думаю, что все, что обеспечивает "окно" в реальном времени в состояние вашей информации (переменное состояние или что-то вроде базы данных... монитор - это просто окно в вашем буфере отображения) может извлечь выгоду из этих идей.

Ответ 4

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

Машина, следующий выход которой зависит от текущего входа и предыдущего выхода в соответствии с (ВАШ КОД ЗДЕСЬ). Этот текущий вход - ничто иное, как предыдущий вывод + (ПОЛЬЗОВАТЕЛЬ, ИНТЕРАКТ ЗДЕСЬ).

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

Затем, соединяйте машины на своей поверхности, пусть они делят заметки, согласно (ВАШ КОД ЗДЕСЬ), и теперь мы делаем его умным. Он станет интерактивной вычислительной системой.

Итак, вам просто нужно предоставить свою логику в двух местах в приведенной выше модели; остальные заботятся самим дизайном машины. Что хорошего в этом.