Как работает дифференциальное исполнение?
Я видел несколько упоминаний об этом в переполнении стека, но, глядя на Википедию (соответствующая страница была с тех пор удалена), и на демонстрацию динамического диалога MFC ничего не просветило меня. Может кто-нибудь, пожалуйста, объясните это? Изучение принципиально другой концепции звучит хорошо.
Основываясь на ответах: я думаю, что я чувствую это лучше. Наверное, я просто не достаточно внимательно посмотрел на исходный код в первый раз. На данный момент у меня смешанные чувства по поводу дифференциального исполнения. С одной стороны, это может значительно облегчить выполнение определенных задач. С другой стороны, запустить и запустить его (то есть настроить его на выбранном вами языке) непросто (я уверен, что было бы, если бы я понял его лучше)... хотя я думаю, что набор инструментов для этого нужно сделать только один раз, а затем расширить при необходимости. Я думаю, что для того, чтобы по-настоящему понять это, мне, вероятно, нужно попробовать реализовать его на другом языке.
4 ответа
Ну и дела, Брайан, я хотел бы видеть ваш вопрос раньше. Поскольку это в значительной степени мое "изобретение" (к лучшему или к худшему), я мог бы помочь.
Вставлено: Самое короткое возможное объяснение, которое я могу сделать, состоит в том, что если нормальное выполнение - это как бросать мяч в воздух и ловить его, то дифференциальное выполнение - как жонглирование.
Объяснение @windfinder отличается от моего, и это нормально. Этот метод нелегко обернуть голову, и мне потребовалось около 20 лет (время от времени), чтобы найти объяснения, которые работают. Позвольте мне дать ему еще один шанс здесь:
- Что это?
Мы все понимаем простую идею о том, что компьютер шагает по программе, берет условные ветви на основе входных данных и что-то делает. (Предположим, что мы имеем дело только с простым структурированным кодом goto-less, return-less.) Этот код содержит последовательности операторов, базовые структурированные условия, простые циклы и вызовы подпрограмм. (Забудьте о функциях, возвращающих значения на данный момент.)
Теперь представьте, что два компьютера выполняют один и тот же код в режиме блокировки друг с другом и могут сравнивать записи. Компьютер 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, Add))){. Что делает функция deButton? Кроме того, ваши циклы FOR/END используют какой-то макрос или что-то еще? Брайан.
@Brian: Да, операторы FOR/END и IF являются макросами. Проект SourceForge полностью реализован. Дебаттон поддерживает кнопку управления. Когда происходит любое действие пользовательского ввода, код запускается в режиме "события управления", в котором deButton обнаруживает, что он был нажат, и означает, что он был нажат, возвращая TRUE. Таким образом, "if(deButton(...)){... код действия...} является способом присоединения кода действия к кнопке без необходимости создавать замыкание или писать обработчик события. DD_THROW является способ завершения прохода, когда действие предпринято, потому что действие, возможно, изменило данные приложения, поэтому недопустимо продолжать проход "управляющего события" через подпрограмму. Если вы сравните это с записью обработчиков событий, это спасет вас от написания тех, и это позволяет вам иметь любое количество элементов управления.
Добавлено: Извините, я должен объяснить, что я имею в виду под словом "поддерживает". Когда процедура выполняется впервые (в режиме SHOW), deButton создает элемент управления кнопки и запоминает его идентификатор в FIFO. При последующих проходах (в режиме UPDATE) deButton получает идентификатор из FIFO, изменяет его, если необходимо, и помещает обратно в FIFO. В режиме ERASE он читает его из FIFO, уничтожает и не возвращает обратно, тем самым "собирая мусор". Таким образом, вызов deButton управляет всем временем жизни элемента управления, поддерживая его в соответствии с данными приложения, поэтому я говорю, что он "поддерживает" его.
Четвертый режим - СОБЫТИЕ (или КОНТРОЛЬ). Когда пользователь вводит символ или нажимает кнопку, это событие перехватывается и записывается, а затем процедура deContents выполняется в режиме EVENT. deButton получает идентификатор элемента управления своей кнопки из FIFO и спрашивает, был ли этот элемент управления нажатым. Если это так, он возвращает TRUE, чтобы можно было выполнить код действия. Если нет, он просто возвращает 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) ...
Конечно, это абстракция, и, действительно, набор условий, представляющих включение / выключение определенного примитива, может быть большим (возможно, сотни флагов, которые все должны принимать значение true).
Если мы запустим программу, мы сможем рисовать на экране с той же скоростью, с которой мы можем оценить все эти условия. (Худший случай: сколько времени занимает оценка наибольшего набора условных операторов.)
Теперь для любого состояния в программе мы можем просто оценить все условия и выводить их на экран молниеносно! (Мы знаем наши примитивы формы и их зависимые операторы if.)
Это все равно что покупать графически насыщенную игру. Только вместо того, чтобы устанавливать его на жесткий диск и запускать его через процессор, вы покупаете совершенно новую плату, которая содержит всю игру и принимает в качестве входных данных: мышь, клавиатуру и принимает в качестве выходных данных: монитор. Невероятно сжатая условная оценка (поскольку самая фундаментальная форма условной логики - логические элементы на платах). Это, естественно, будет очень отзывчивым, но практически не будет поддерживать исправление ошибок, так как дизайн всей платы меняется, когда вы вносите незначительное изменение в конструкцию (потому что "дизайн" настолько далек от природы печатной платы). За счет гибкости и ясности в том, как мы представляем данные внутри, мы получили значительную "отзывчивость", потому что мы больше не "думаем" на компьютере; это всего лишь рефлекс для печатной платы на основе входов.
Урок, насколько я понимаю, состоит в том, чтобы разделить труд таким образом, чтобы вы дали каждой части системы (не обязательно только компьютеру и монитору) что-то, что она может хорошо выполнить. "Компьютерное мышление" может быть реализовано в терминах таких понятий, как объекты... Компьютерный мозг с радостью постарается все обдумать, но вы можете значительно упростить задачу, если сможете позволить компьютеру мыслить условия data_update и conditional_evals. Наши человеческие абстракции концепций в коде идеалистичны, а в случае внутренней программы методы рисования немного чрезмерно идеалистичны. Когда все, что вам нужно, это результат (массив пикселей с правильными значениями цвета), и у вас есть машина, которая может легко выплевывать массив, который увеличивается каждую 1/60 секунды, постарайтесь избавиться от такого большого количества цветочного мышления от компьютерного мозга, как возможно, так что вы можете сосредоточиться на том, что вы действительно хотите: синхронизировать графические обновления с вашими (быстрыми) входами и естественным поведением монитора.
Как это сопоставить с другими приложениями? Я хотел бы услышать о других примерах, но я уверен, что есть много. Я думаю, что все, что обеспечивает в реальном времени "окно" в состояние вашей информации (переменное состояние или что-то вроде базы данных... монитор - это просто окно в ваш буфер отображения), может извлечь пользу из этих выводов.
Я нахожу эту концепцию очень похожей на конечные автоматы классической цифровой электроники. Особенно те, которые помнят свой предыдущий вывод.
Машина, следующий выход которой зависит от текущего и предыдущего выхода в соответствии с (ВАШ КОД ЗДЕСЬ). Этот текущий вход является ничем иным, как предыдущим выходом + (ПОЛЬЗОВАТЕЛЬ, ВЗАИМОСВЯЗЬ ЗДЕСЬ).
Заполните поверхность такими машинами, и она будет интерактивной для пользователя и в то же время будет представлять собой слой изменяемых данных. Но на этом этапе все равно будет глупо, просто отражая взаимодействие пользователя с основными данными.
Затем, соедините машины на своей поверхности, пусть они делятся заметками, согласно (ВАШ КОД ЗДЕСЬ), и теперь мы делаем это разумно. Он станет интерактивной вычислительной системой.
Так что вам просто нужно представить свою логику в двух местах в приведенной выше модели; об остальном заботится сама конструкция машины. Вот что хорошего в этом.