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

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


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

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

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

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

  • Что это?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

То, что мне показалось сложнее всего объяснить, заключается в том, что для этого требуется другое мышление о программном обеспечении. Программисты настолько прочно привязаны к объектно-ориентированному представлению программного обеспечения, что хотят знать, какие объекты, какие classы, как они «строят» дисплей, и как они обрабатывают события, что он принимает вишню чтобы выбить их из него. Я пытаюсь передать, что действительно важно, что вам нужно сказать? Представьте, что вы создаете доменный язык (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, iname)); 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

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

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

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

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

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

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

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

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

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

Давайте будем гением компьютера.