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

Я видел несколько упоминаний об этом в Stack Overflow, но просмотр Википедии (соответствующая страница с тех пор была удалена) и демонстрация динамического диалога MFC не помогли мне просветить. Может кто-нибудь объяснить это? Изучение принципиально иной концепции звучит неплохо.

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

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

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

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

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

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

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

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

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

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

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

• Для чего это?

Это пришло мне в голову, когда я работал над графическим проектом, где пользователь мог создавать небольшие процедуры процессора дисплея, называемые «символами», которые можно было объединить в более крупные процедуры, чтобы рисовать такие вещи, как схемы труб, резервуаров, клапанов и тому подобное. Мы хотели, чтобы диаграммы были «динамическими» в том смысле, что они могли бы постепенно обновляться без необходимости перерисовывать всю диаграмму. (Оборудование было медленным по сегодняшним стандартам.) Я понял, что (например) процедура рисования столбца гистограммы может запоминать свою старую высоту и просто постепенно обновлять себя.

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

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

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

В те дни мне приходилось беспокоиться о интерференции между визуальными объектами, чтобы стирание одного не повредило другим. Однако теперь я использую эту технику с элементами управления 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 определяют элементы управления для редактирования записи отдельного пациента. Обратите внимание, что форма программы почти не учитывает события во времени, как если бы все, что ей нужно было сделать, это создать отображение один раз. Затем, если субъекты добавляются или удаляются, или происходят другие структурные изменения, он просто повторно выполняется, как если бы он был воссоздан с нуля, за исключением того, что вместо этого выполняется инкрементное обновление. Преимущество состоит в том, что вам, как программисту, не нужно уделять никакого внимания или писать какой-либо код для выполнения инкрементных обновлений пользовательского интерфейса, и они гарантированно верны. Может показаться, что это повторное выполнение будет проблемой с производительностью, но это не так,

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, «Add»)) {». Что делает функция deButton? Кроме того, используются ли в ваших циклах FOR / END какой-то макрос или что-то в этом роде? - Брайан.

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

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

Четвертый режим - СОБЫТИЕ (или КОНТРОЛЬ). Когда пользователь вводит символ или нажимает кнопку, это событие фиксируется и записывается, а затем процедура deContents выполняется в режиме EVENT. deButton получает идентификатор своего элемента управления кнопкой из FIFO и спрашивает, был ли нажат этот элемент управления. Если это так, возвращается ИСТИНА, чтобы можно было выполнить код действия. Если нет, он просто возвращает FALSE. С другой стороны, deEdit(..., &myStringVar)определяет, было ли событие предназначено для него, и, если да, передает его элементу редактирования, а затем копирует содержимое элемента управления редактированием в myStringVar. Между этой и обычной обработкой UPDATE myStringVar всегда совпадает с содержимым поля редактирования. Так делается «привязка». Та же идея применима к полосам прокрутки, спискам, полям со списком и любым элементам управления, которые позволяют редактировать данные приложения.

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

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

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

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)

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

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

Он обновляется с частотой 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 и conditional_evals. Наши человеческие абстракции понятий в код идеалистичны, а в случае внутренних программных методов рисования несколько излишне идеалистичны. Когда все, что вам нужно, это результат (массив пикселей с правильными значениями цвета), и у вас есть машина, которая может легко выплевывать такой большой массив каждую 1/60 секунды, постарайтесь избавиться от как можно большего количества витиеватых мыслей из компьютерного мозга, чтобы вы могли сосредоточиться на том, что вы действительно хотите: синхронизировать графические обновления с вашими (быстрыми) входами и естественное поведение монитора.

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

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

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

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

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

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