차등 실행은 어떻게 작동합니까?

차등 실행은 어떻게 작동합니까?

---

Stack Overflow에서 이에 대한 몇 가지 언급을 보았지만 Wikipedia (관련 페이지가 삭제 된 이후로 삭제됨)와 MFC 동적 대화 데모에서 나를 깨우쳐주지 못했습니다. 누군가 이것을 설명해 주시겠습니까? 근본적으로 다른 개념을 배우는 것은 좋은 것 같습니다.

---

답변을 바탕으로 : 나는 그것에 대해 더 나은 느낌을 받고 있다고 생각합니다. 처음에는 소스 코드를 충분히주의 깊게 보지 않은 것 같습니다. 나는이 시점에서 차등 실행에 대해 엇갈린 감정을 가지고있다. 한편으로는 특정 작업을 상당히 쉽게 만들 수 있습니다. 반면에, 그것을 시작하고 실행 (즉, 선택한 언어로 설정)하는 것은 쉽지 않습니다. (내가 더 잘 이해한다면 그럴 것이라고 확신합니다) ... 한 번만 만든 다음 필요에 따라 확장하면됩니다. 정말 이해하기 위해서는 다른 언어로 구현해야 할 것 같습니다.

---

이봐, 브라이언, 당신의 질문을 더 빨리 보았 으면 좋았을 텐데요 (좋든 나쁘 든) 거의 나의 "발명품"이기 때문에 도움을 드릴 수있을 것입니다.

삽입 됨 : 내가 할 수있는 가장 짧은 설명은 정상적인 실행이 공을 공중에 던지고 잡는 것과 같으면 차등 실행은 저글링과 같다는 것입니다.

@windfinder의 설명이 나와 다르며 괜찮습니다. 이 기술은 머리를 감싸는 것이 쉽지 않으며, 작동하는 설명을 찾는 데 약 20 년이 걸렸습니다. 여기에 또 다른 기회를 드리겠습니다.

• 뭔데?

우리 모두는 컴퓨터가 프로그램을 따라 가며 입력 데이터를 기반으로 조건부 분기를 수행하고 작업을 수행하는 간단한 아이디어를 이해합니다. (단순한 구조화 된 goto-less, return-less 코드 만 처리한다고 가정합니다.)이 코드에는 일련의 명령문, 기본 구조화 된 조건, 단순 루프 및 서브 루틴 호출이 포함됩니다. (지금은 값을 반환하는 함수는 잊어 버리세요.)

이제 동일한 코드를 서로 잠금 단계에서 실행하고 메모를 비교할 수있는 두 대의 컴퓨터를 상상해보십시오. 컴퓨터 1은 입력 데이터 A로 실행되고 컴퓨터 2는 입력 데이터 B로 실행됩니다. 이들은 단계별로 나란히 실행됩니다. 만약 그들이 IF (test) .... ENDIF와 같은 조건문을 접하고 그들이 테스트가 참인지에 대한 의견 차이가 있다면, 거짓이면 테스트를 말하는 사람은 ENDIF로 건너 뛰고 기다립니다. 따라 잡을 여동생. (이것이 코드가 구조화 된 이유이므로 자매가 결국 ENDIF에 도달 할 것이라는 것을 알고 있습니다.)

두 컴퓨터가 서로 대화 할 수 있기 때문에 메모를 비교하고 두 입력 데이터 세트와 실행 기록이 어떻게 다른지에 대한 자세한 설명을 제공 할 수 있습니다.

물론 차등 실행 (DE)에서는 한 대의 컴퓨터로 두 대를 시뮬레이션합니다.

이제 한 세트의 입력 데이터 만 가지고 있지만 그것이 시간 1에서 시간 2로 어떻게 변경되었는지 확인하고 싶다고 가정합니다. 실행중인 프로그램이 직렬 변환기 / 역 직렬 변환기라고 가정합니다. 실행할 때 현재 데이터를 직렬화 (쓰기)하고 과거 데이터 (마지막으로 기록한 데이터)를 역 직렬화 (읽기)합니다. 이제 지난번 데이터와 이번 데이터의 차이점을 쉽게 확인할 수 있습니다.

쓰고있는 파일과 읽고있는 이전 파일이 함께 큐 또는 FIFO (선입 선출)를 구성하지만 이는 매우 깊은 개념이 아닙니다.

• 무엇에 좋은가요?

그래픽 프로젝트에서 작업하는 동안 사용자가 "기호"라고하는 작은 디스플레이 프로세서 루틴을 구성 할 수있었습니다.이 루틴은 파이프, 탱크, 밸브 등의 다이어그램과 같은 것을 그리기 위해 더 큰 루틴으로 조립 될 수 있습니다. 전체 다이어그램을 다시 그릴 필요없이 자체적으로 점진적으로 업데이트 할 수 있다는 점에서 다이어그램을 "동적"으로 만들고 싶었습니다. (하드웨어는 오늘날의 표준에 비해 느 렸습니다.) 저는 (예를 들어) 막대 차트 막대를 그리는 루틴이 이전 높이를 기억하고 점차적으로 자체적으로 업데이트 할 수 있다는 것을 깨달았습니다.

이것은 OOP처럼 들리지 않습니까? 그러나 "개체"를 "만들기"보다는 다이어그램 프로 시저의 실행 순서에 대한 예측 가능성을 활용할 수 있습니다. 막대의 높이를 순차적 인 바이트 스트림으로 쓸 수 있습니다. 그런 다음 이미지를 업데이트하기 위해 다음 업데이트 단계를 준비하기 위해 새 매개 변수를 쓰는 동안 이전 매개 변수를 순차적으로 읽는 모드에서 프로 시저를 실행할 수 있습니다.

이것은 어리석은 것처럼 보이며 프로 시저에 조건부가 포함되는 즉시 중단되는 것처럼 보입니다. 왜냐하면 새 스트림과 이전 스트림이 동기화되지 않기 때문입니다. 그러나 조건부 테스트의 부울 값도 직렬화하면 동기화 상태로 돌아갈 수 있다는 사실이 나에게 떠 올랐습니다 . 간단한 규칙 ( "지우기 모드 규칙")을 따른 다면 이것이 항상 작동 한다는 것을 스스로 확신하고 증명하는 데 시간이 걸렸 습니다.

결과적으로 사용자는 디스플레이가 아무리 복잡하거나 구조적으로 변하더라도 동적으로 업데이트되는 방식에 대해 걱정할 필요없이 이러한 "동적 심볼"을 디자인하고 더 큰 다이어그램으로 조합 할 수 있습니다.

그 당시에는 시각적 개체 간의 간섭에 대해 걱정해야했기 때문에 하나를 지워도 다른 개체가 손상되지 않도록했습니다. 그러나 이제는 Windows 컨트롤에서이 기술을 사용하고 Windows에서 렌더링 문제를 처리하도록합니다.

그래서 그것은 무엇을 성취합니까? 즉, 컨트롤을 그리는 절차를 작성하여 대화 상자를 만들 수 있으며 컨트롤 개체를 실제로 기억하거나 점진적으로 업데이트하거나 조건이 보장하는대로 나타나거나 사라지거나 이동하는 것에 대해 걱정할 필요가 없습니다. 그 결과 대화 소스 코드가 훨씬 더 작고 단순 해졌으며, 동적 레이아웃, 컨트롤 수 변경, 컨트롤 배열 또는 그리드 포함 등은 사소한 일입니다. 또한 편집 필드와 같은 컨트롤은 편집중인 응용 프로그램 데이터에 간단하게 바인딩 될 수 있으며 항상 정확할 것이므로 이벤트를 처리 할 필요가 없습니다. 응용 프로그램 문자열 변수에 대한 편집 필드를 입력하는 것은 한 줄 편집입니다.

• 이해하기 어려운 이유는 무엇입니까?

제가 가장 설명하기 어려운 점은 소프트웨어에 대해 다르게 생각해야한다는 것입니다. 프로그래머는 소프트웨어의 객체-액션 뷰에 너무 굳게 결합하여 객체가 무엇인지, 클래스가 무엇인지, 디스플레이를 "구축"하는 방법, 이벤트를 처리하는 방법을 알고 싶어합니다. 폭탄을 터뜨리는 것입니다. 제가 전하려고하는 것은 정말로 중요한 것은 당신이 말해야 하는 것이 무엇이라는 것입니다 ."여기에서 변수 A, 거기에서 변수 B, 아래에서 변수 C를 편집하고 싶다"라고 말하면 DSL (domain-specific language)을 만들고 있다고 상상해보십시오. 그러면 마법처럼 처리해줍니다. . 예를 들어, Win32에는 대화 상자를 정의하기위한이 "자원 언어"가 있습니다. 그것은 충분히 멀리 가지 않는 것을 제외하고는 완벽하게 좋은 DSL입니다. 기본 절차 언어에 "살아 있지"않거나 이벤트를 처리하거나 루프 / 조건부 / 서브 루틴을 포함하지 않습니다. 그러나 그것은 의미가 있으며 Dynamic Dialogs는 작업을 완료하려고합니다.

따라서 다른 사고 방식은 프로그램을 작성하려면 먼저 적절한 DSL을 찾고 (또는 발명) 가능한 한 많은 프로그램을 코딩하는 것입니다. 하자 가 단지 구현을 위하여 존재하는 모든 객체와 작업을 처리합니다.

차등 실행을 실제로 이해하고 사용하려면 몇 가지 까다로운 문제가 있습니다. 한때 Lisp 매크로로 코딩 했는데,이 까다로운 부분을 처리 할 수 ​​있었지만 "일반"언어에서는 함정을 피하기 위해 프로그래머 규율이 필요합니다.

너무 길어서 죄송합니다. 내가 말이 안 됐다면 지적 해 주시면 고맙게 생각하고 고칠 수 있습니다.

추가 :

에서 자바 스윙 , TextInputDemo라는 예제 프로그램이있다. 270 줄 (50 개 상태 목록 제외)을 사용하는 정적 대화 상자입니다. Dynamic Dialogs (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 행은 UI의 전체 내용을 정의합니다. 30-48 행은 단일 환자의 기록을 편집하기위한 컨트롤을 정의합니다. 프로그램의 형식은 마치 디스플레이를 한 번만 만드는 것처럼 제 시간에 이벤트를 거의 알리지 않습니다. 그런 다음 주제가 추가 또는 제거되거나 다른 구조적 변경이 발생하면 DE가 대신 증분 업데이트를 수행한다는 점을 제외하고는 처음부터 다시 생성되는 것처럼 간단히 다시 실행됩니다. 장점은 프로그래머가 UI의 점진적 업데이트를 수행하기 위해주의를 기울이거나 코드를 작성할 필요가 없으며 정확하다는 것입니다. 이 재실행이 성능 문제로 보일 수 있지만 그렇지 않습니다.

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 }

Added: Brian asked a good question, and I thought the answer belonged in the main text here:

@Mike: I'm not clear on what the "if (deButton(50, 20, “Add”)){" statement is actually doing. What does the deButton function do? Also, are your FOR/END loops using some sort of macro or something? – Brian.

@Brian: Yes, the FOR/END and IF statements are macros. The SourceForge project has a complete implementation. deButton maintains a button control. When any user input action takes place, the code is run in "control event" mode, in which deButton detects that it was pressed and signifies that it was pressed by returning TRUE. Thus, the "if(deButton(...)){... action code ...} is a way of attaching action code to the button, without having to create a closure or write an event handler. The DD_THROW is a way of terminating the pass when the action is taken because the action may have modified application data, so it is invalid to continue the "control event" pass through the routine. If you compare this to writing event handlers, it saves you writing those, and it lets you have any number of controls.

Added: Sorry, I should explain what I mean by the word "maintains". When the procedure is first executed (in SHOW mode), deButton creates a button control and remembers its id in the FIFO. On subsequent passes (in UPDATE mode), deButton gets the id from the FIFO, modifies it if necessary, and puts it back in the FIFO. In ERASE mode, it reads it from the FIFO, destroys it, and does not put it back, thereby "garbage collecting" it. So the deButton call manages the entire lifetime of the control, keeping it in agreement with application data, which is why I say it "maintains" it.

The fourth mode is EVENT (or CONTROL). When the user types a character or clicks a button, that event is caught and recorded, and then the deContents procedure is executed in EVENT mode. deButton gets the id of its button control from the FIFO and askes if this is the control that was clicked. If it was, it returns TRUE so the action code can be executed. If not, it just returns FALSE. On the other hand, deEdit(..., &myStringVar) detects if the event was meant for it, and if so passes it to the edit control, and then copies the contents of the edit control to myStringVar. Between this and normal UPDATE processing, myStringVar always equals the contents of the edit control. That is how "binding" is done. The same idea applies to scroll bars, list boxes, combo boxes, any kind of control that lets you edit application data.

Here's a link to my Wikipedia edit: http://en.wikipedia.org/wiki/User:MikeDunlavey/Difex_Article

---

Differential execution is a strategy for changing the flow of your code based on external events. This is usually done by manipulating a data structure of some kind to chronicle the changes. This is mostly used in graphical user interfaces, but is also used for things like serialization, where you are merging changes into an existing "state."

The basic flow is as follows:

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)

The advantages of this are a few. One, it is separation of the execution of your changes, and the actual manipulation of the supporting data. Which is nice for multiple processors. Two, it provides a low bandwidth method of communicating changes in your program.

---

Think of how a monitor works:

It is updated at 60 Hz -- 60 times a second. Flicker flicker flicker 60 times, but your eyes are slow and can't really tell. The monitor shows whatever is in the output buffer; it just drags this data out every 1/60th of a second no matter what you do.

Now why would you want your program to update the whole buffer 60 times a second if the image shouldn't change that often? What if you only change one pixel of the image, should you rewrite the entire buffer?

---

This is an abstraction of the basic idea: you want to change the output buffer based on what information you want displayed on the screen. You want to save as much CPU time and buffer write time as possible, so you don't edit parts of the buffer that need not be changed for the next screen pull.

The monitor is separate from your computer and logic (programs). It reads from the output buffer at whatever rate it updates the screen. We want our computer to stop synchronizing and redrawing unnecessarily. We can solve this by changing how we work with the buffer, which can be done in a variety of ways. His technique implements a FIFO queue that is on delay -- it holds what we just sent to the buffer. The delayed FIFO queue does not hold pixel data, it holds "shape primitives" (which might be pixels in your application, but it could also be lines, rectangles, easy-to-draw things because they are just shapes, no unnecessary data is allowed).

So you want to draw/erase things from the screen? No problem. Based on the contents of the FIFO queue I know what the monitor looks like at the moment. I compare my desired output (to erase or draw new primitives) with the FIFO queue and only change values that need to be changed/updated. This is the step which gives it the name Differential Evaluation.

Two distinct ways in which I appreciate this:

The First: Mike Dunlavey uses a conditional-statement extension. The FIFO queue contains a lot of information (the "previous state" or the current stuff on monitor or time-based polling device). All you have to add to this is the state you want to appear on screen next.

A conditional bit is added to every slot that can hold a primitive in the FIFO queue.

0 means erase
1 means draw

However, we have previous state:

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

This is elegant, because when you update something you really only need to know what primitives you want to draw to the screen -- this comparison will find out if it should erase a primitive or add/keep it to/in the buffer.

The Second: This is just one example, and I think that what Mike is really getting at is something that should be fundamental in design for all projects: Reduce the (computational) complexity of design by writing your most computationally intense operations as computerbrain-food or as close as you can get. Respect the natural timing of devices.

A redraw method to draw the entire screen is incredibly costly, and there are other applications where this insight is incredibly valuable.

We are never "moving" objects around the screen. "Moving" is a costly operation if we are going to mimic the physical action of "moving" when we design code for something like a computer monitor. Instead, objects basically just flicker on and off with the monitor. Every time an object moves, it's now a new set of primitives and the old set of primitives flickers off.

Every time the monitor pulls from the buffer we have entries that look like

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

Never does an object interact with the screen (or time-sensitive polling device). We can handle it more intelligently than an object will when it greedily asks to update the whole screen just to show a change specific to only itself.

Say we have a list of all possible graphical primitives our program is capable of generating, and that we tie each primitive to a set of conditional statements

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

Of course, this is an abstraction and, really, the set of conditionals that represents a particular primitive being on/off could be large (perhaps hundreds of flags that must all evaluate to true).

If we run the program, we can draw to the screen at essentially the same rate at which we can evaluate all these conditionals. (Worst case: how long it takes to evaluate the largest set of conditional statements.)

Now, for any state in the program, we can simply evaluate all the conditionals and output to the screen lightning-quick! (We know our shape primitives and their dependent if-statements.)

This would be like buying a graphically-intense game. Only instead of installing it to your HDD and running it through your processor, you buy a brand-new board that holds the entirety of the game and takes as input: mouse, keyboard, and takes as output: monitor. Incredibly condensed conditional evaluation (as the most fundamental form of a conditional is logic gates on circuit boards). This would, naturally, be very responsive, but it offers almost no support in fixing bugs, as the whole board design changes when you make a tiny design change (because the "design" is so far-removed from the nature of the circuit board). At the expense of flexibility and clarity in how we represent data internally we have gained significant "responsiveness" because we are no longer doing "thinking" in the computer; it is all just reflex for the circuit board based on the inputs.

The lesson, as I understand it, is to divide labor such that you give each part of the system (not necessarily just computer and monitor) something it can do well. The "computer thinking" can be done in terms of concepts like objects... The computer brain will gladly try and think this all through for you, but you can simplify the task a great deal if you are able to let the computer think in terms of data_update and conditional_evals. Our human abstractions of concepts into code are idealistic, and in the case of internal program draw methods a little overly idealistic. When all you want is a result (array of pixels with correct color values) and you have a machine that can easily spit out an array that big every 1/60th of a second, try and eliminate as much flowery thinking from the computer brain as possible so that you can focus on what you really want: to synchronize your graphical updates with your (fast) inputs and the natural behavior of the monitor.

How does this map to other applications? I'd like to hear of other examples, but I'm sure there are many. I think anything that provides a real-time "window" into the state of your information (variable state or something like a database... a monitor is just a window into your display buffer) can benefit from these insights.

---

I find this concept very similar to the state machines of classic digital electronics. Specially the ones which remember their previous output.

A machine whose next output depends on current input and previous output according to (YOUR CODE HERE). This current input is nothing but previous output + (USER, INTERACT HERE).

Fill up a surface with such machines, and it will be user interactive and at the same time represent a layer of changeable data. But at this stage it will still be dumb, just reflecting user interaction to underlying data.

Next, interconnect the machines on your surface, let them share notes, according to (YOUR CODE HERE), and now we make it intelligent. It will become an interactive computing system.

So you just have to provide your logic at two places in the above model; the rest is taken care of by the machine design itself. That's what good about it.

참고URL : https://stackoverflow.com/questions/371898/how-does-differential-execution-work