Natknąłem się na pytanie przepełnienie stosu, How does differential execution work?, które ma bardzo długą i szczegółową odpowiedź. Wszystko to miało sens ... ale kiedy skończyłem, wciąż nie miałem pojęcia, co tak naprawdę jest w rzeczywistości. Co to naprawdę jest?Co to jest wykonanie różnicowe?
ZMIENIONA. To moja n-ta próba wyjaśnienia tego.
Załóżmy, że masz prostą deterministyczną procedurę, która jest wykonywana wielokrotnie, zawsze zgodnie z tą samą sekwencją instrukcji wyciągów lub wywołań procedur. Procedura zwraca się pisać co chcą kolejno do FIFO, a oni czytają tę samą liczbę bajtów z drugiego końca FIFO, tak: **
Procedury są nazywane korzystania FIFO jako pamięć, ponieważ to, co czytają, jest takie samo, jak to, co napisali podczas wcześniejszej realizacji. Więc jeśli ich argumenty zdają się być inne niż poprzednio, mogą to zobaczyć i robić, co tylko zechcą.
Aby rozpocząć, należy wykonać początkową operację, w której wykonywane jest tylko pisanie, bez czytania. Symetrycznie, powinno być ostateczne wykonanie, w którym odbywa się tylko czytanie, brak pisania. Tak jest „globalny” rejestr tryb zawierający dwa bity, jeden, który umożliwia odczyt i jeden, który umożliwia pisanie, tak:
Początkowa realizacja odbywa się w trybie , więc tylko pisanie skończone. Wywołania procedur mogą zobaczyć tryb, więc wiedzą, że nie ma wcześniejszej historii. Jeśli chcą tworzyć obiekty, mogą i umieszczają informacje identyfikujące w FIFO (nie ma potrzeby przechowywania w zmiennych).
Pośrednie wykonywanie jest wykonywane w trybie , więc zarówno odczyt, jak i zapis mają miejsce, a wywołania procedur mogą wykrywać zmiany danych. Jeśli istnieją obiekty, które mają być aktualizowane, ich dane identyfikacyjne są odczytywane i zapisywane w FIFO, , aby można było uzyskać do nich dostęp i, jeśli to konieczne, zmodyfikować.
Końcowe wykonanie jest wykonywane w trybie , więc dzieje się tylko czytanie. W tym trybie wywołania proceduralne wiedzą, że po prostu się czyszczą. Jeśli istniały jakiekolwiek obiekty, ich identyfikatory są odczytywane z FIFO i można je usunąć.
Ale rzeczywiste procedury nie zawsze mają tę samą sekwencję. Zawierają instrukcje IF (i inne sposoby różnicowania ich działania). Jak można to załatwić?
Odpowiedzią jest specjalny rodzaj instrukcji JEŻELI (i kończąca się instrukcja ENDIF). Oto jak to działa. Zapisuje wartość boolowską wyrażenia testowego i odczytuje wartość, którą wyrażenie testowe ostatni raz. W ten sposób można sprawdzić, czy wyrażenie testowe uległo zmianie i podjąć działanie. Czynność, którą trzeba wykonać, to tymczasowo zmienić rejestr trybu.
szczególności x jest przed wartość wyrażenia testu odczytywane z FIFO (jeśli odczytu jest włączona, inny 0) i Y jest bieżąca wartość wyrażenia testu zapisywane do FIFO (jeśli zapis jest włączony). (Faktycznie, jeśli pisanie nie jest włączona, ekspresja Test nie jest jeszcze oceniany, a y 0.) Następnie x, y prostu maskuje tryb zarejestrować R, W. Więc jeśli wyrażenie testowe ma zmienione z True na False, ciało jest wykonywane w trybie tylko do odczytu. Odwrotnie, jeśli zmieniła się z Fałszywy na Prawdziwy, ciało jest wykonywane w trybie tylko do zapisu. Jeśli wynik to , kod wewnątrz instrukcji IF..ENDIF zostanie pominięty. (Możesz zastanowić się trochę nad tym, czy obejmuje to wszystkie przypadki - tak się dzieje.)
To może nie być oczywiste, ale te instrukcje IF..ENDIF mogą być arbitralnie zagnieżdżone i mogą być rozszerzone na wszystkie inne rodzaje instrukcji warunkowych, takich jak ELSE, SWITCH, WHILE, FOR, a nawet wywoływanie funkcji opartych na wskaźnikach. Jest również tak, że procedurę można podzielić na pod-procedury w dowolnym zakresie, w tym rekurencyjnym, o ile tryb jest przestrzegany.
(Nie jest to regułą, które muszą być przestrzegane, zwana reguła erase trybu, czyli że w trybie bez obliczania jakiekolwiek konsekwencje, takie jak następujące wskaźnik lub indeksowania tablicy, należy zrobić Konceptualnie powodem jest to, że tryb istnieje tylko w celu pozbycia się rzeczy.)
Jest to interesująca struktura kontrolna, która może być wykorzystywana do wykrywania zmian, zwykle zmian danych i podejmowania działań na te zmiany.
Jego zastosowanie w graficznych interfejsów użytkownika jest, aby utrzymać pewien zestaw elementów sterujących lub innych obiektów w porozumieniu z informacji o stanie programu. W tym celu trzy tryby nazywają się SHOW (01), UPDATE (11) i ERASE (10). Procedura jest początkowo wykonywana w trybie POKAŻ, w którym tworzone są formanty, a informacje dla nich istotne wypełniają FIFO. Następnie wykonuje się dowolną liczbę wykonań w trybie UPDATE, gdzie elementy sterujące są modyfikowane w razie potrzeby, aby być na bieżąco ze stanem programu. W końcu następuje wykonanie w trybie ERASE, w którym elementy sterujące są usuwane z interfejsu użytkownika, a FIFO jest opróżniany.
korzyści w ten sposób jest to, że kiedy już napisane procedurę, aby utworzyć wszystkie elementy sterujące, w zależności od stanu programu, nie trzeba pisać nic innego do aktualizuj je później lub usuwaj. Wszystko, czego nie musisz pisać, oznacza mniej okazji do popełniania błędów. (Istnieje prosty sposób obsługi zdarzeń wprowadzanych przez użytkownika bez konieczności pisania programów obsługi zdarzenia i tworzenia nazw dla nich.Jest to wyjaśnione w jednym z filmów wideo poniżej.)
Pod względem zarządzania pamięcią, nie muszą nadrobić nazwy zmiennych lub strukturę danych, aby przechowywać formanty.Używa tylko tyle pamięci w tym samym czasie dla aktualnie widocznych formantów, podczas gdy widoczne elementy sterujące mogą być nieograniczone. Ponadto, nigdy nie ma obaw związanych z wyrzucaniem śmieci z wcześniej używanych kontrolek - FIFO działa jak automatyczny garbage collector.
Pod względem wydajności, podczas tworzenia, usuwania lub modyfikowania elementów sterujących, wydaje się, że i tak trzeba poświęcić czas. Gdy po prostu aktualizuje się kontrolki i nie ma żadnych zmian, cykle potrzebne do odczytu, zapisu i porównania są mikroskopijne w porównaniu ze zmieniającymi się kontrolkami.
Kolejnym czynnikiem wpływającym na wydajność i poprawność w stosunku do systemów, które aktualizuje się w odpowiedzi na zdarzenia, jest to, że taki system wymaga odpowiedzi na każde zdarzenie, a nie dwa razy, w przeciwnym razie wyświetlanie będzie nieprawidłowe, nawet jeśli niektóre sekwencje zdarzeń może samo się anulować. Podczas wykonywania różnicowego aktualizacje mogą być wykonywane tak często lub rzadko, jak to jest wymagane, a wyświetlacz jest zawsze poprawny na końcu przebiegu.
Oto bardzo skrócony przykład, w którym znajdują się 4 przyciski, z których przyciski 2 i 3 są zależne od zmiennej binarnej.
(W tym przykładzie, zmiany zostaną cofnięte w odwrotnej kolejności jak zostały zrobione, ale to nie jest konieczne. Zmiany mogą być wykonane i nieutwardzona w dowolnej kolejności).
zauważyć, że w ogóle razy, FIFO, składające się ze starych i nowych połączonych ze sobą, zawiera dokładnie parametry widocznych przycisków plus wartość boolowską.
Celem jest pokazanie, w jaki sposób można zastosować pojedynczą procedurę "malowania", bez zmian, dla arbitralnej automatycznej aktualizacji przyrostowej i kasowania. Mam nadzieję, że jest oczywiste, że działa on na dowolną głębokość wywołań w podprocesie i arbitralne zagnieżdżanie warunków, w tym pętle switch, while i for, wywoływanie funkcji opartych na wskaźnikach itp. Jeśli muszę to wyjaśnić, to ja Jestem otwarty na strzały, ponieważ wyjaśnienie jest zbyt skomplikowane.
Wreszcie, istnieje kilka surowy ale krótki videos posted here.
** Z technicznego punktu widzenia muszą odczytać tę samą liczbę bajtów, które napisali ostatnio. Tak więc, na przykład, mogli napisać ciąg poprzedzony liczbą znaków, i to jest w porządku.
DODANO: Zajęło mi dużo czasu, aby mieć pewność, że zawsze będzie działać. W końcu to udowodniłem. Jest on oparty na właściwości Sync, co oznacza, że w jakimkolwiek punkcie programu liczba bajtów zapisanych w poprzednim przebiegu jest równa liczbie odczytanej w kolejnym przebiegu. Ideą dowodu jest zrobienie tego poprzez indukcję długości programu. Najtwardszy przypadkiem udowodnienia w przypadku z sekcji programu obejmującej s1 następnie przez IF (Test) S2 ENDIF gdzie S1 i S2 są podsekcje programu, każdy spełniający synchronizacji Właściwość. Aby zrobić to w tekście jest tylko oko-szyby, ale tutaj Próbowałem go schematem: 
Definiuje Sync własności i pokazuje liczbę bajtów pisanych i czytanych w każdym punkcie kod i pokazuje, że są równe. Najważniejsze punkty to: 1) wartość wyrażenia testowego (0 lub 1) odczytana na bieżącym przebiegu musi być równa wartości zapisanej w poprzednim przebiegu, oraz 2) spełniony jest warunek Sync (s2). Spełnia to właściwość Sync dla połączonego programu.
Myślę, że problem z twoimi wyjaśnieniami jest taki, że zbyt głęboko zagłębiasz się w szczegóły implementacji. 01, 10 i 11 nie są naprawdę ważne, nawet FIFO nie ma związku z główną ideą, jest to po prostu przydatny sposób na przechowywanie stanu dla żywiołów. Funkcjonalność byłaby taka sama, gdyby każdy element interfejsu był przechowywany osobno, a następnie po prostu wydawał instrukcje do jego renderowania. Wyjaśnienie "tłumacza" Gene'a faktycznie przekazuje ten pomysł nieco jaśniej, IMHO; dane zapisane w FIFO są zasadniczo renderującymi instrukcjami, które będą interpretowane. – Groo
@Groo: Dzięki za twoje wejście. To zawsze zagadka, jak ją przedstawić. Rzeczywistym punktem jest to, że jest to język specyficzny dla danej domeny, ale aby to zadziałało, potrzebna jest struktura kontrolna, a niektórzy mają twarde (co jest dobre) czytelników, którzy pomyślą, że to jest hooey, chyba że potrafię to wyjaśnić. –
Przeczytałem wszystkie rzeczy, które mogę znaleźć i obejrzałem film, i zrobię zdjęcie na opis pierwszej zasady.
Przegląd
Jest to wzornictwo oparte na DSL wdrażanie interfejsów użytkownika i być może inne podsystemy państwowych zorientowanych w czystym i efektywny sposób. Koncentruje się na problemie zmiany konfiguracji GUI tak, aby pasował do bieżącego stanu programu, gdzie ten stan obejmuje stan samych widgetów GUI, np. użytkownik wybiera karty, przyciski opcji i elementy menu, a widżety pojawiają się/znikają w dowolnie złożony sposób.
Opis
Wzór zakłada:
We wszystkich przykładach,
Brakujące linki
Wynalazca nigdy wyraźnie stwierdza, ale kluczowym pomysłem jest to, że możemy uruchomić interpreter DSL nad programem, który reprezentuje wszystkie możliwe zbiory docelowych (ekranów) za każdym razem, gdy będziemy oczekiwać dowolną kombinację wartości funkcji Boolean B uległy zmianie. Interpreter obsługuje brudną pracę polegającą na tym, że kolekcja (ekran) jest zgodna z nowymi wartościami B, emitując sekwencję operacji dodawania, usuwania i modyfikacji.
Istnieje ostateczne ukryte założenie: Interpreter DSL zawiera pewien algorytm, który może dostarczyć parametry operacji dodawania i modyfikacji na podstawie historii kreacji wykonanych do tej pory podczas bieżącego uruchomienia. W kontekście interfejsu GUI jest to algorytm układu, a podpowiedzi Utwórz to wskazówki dotyczące układu.
puenta
Moc techniki leży w sposobie złożoności jest zawarta w tłumacza DSL. Głupi tłumacz zaczynał od usunięcia wszystkich obiektów (widżetów) z kolekcji (ekranu), a następnie Dodaj nowy dla każdego polecenia Utwórz, gdy widzi je podczas przechodzenia przez program DSL. Modyfikacja nigdy nie nastąpi.
Wykonanie różnicowe to tylko mądrzejsza strategia dla tłumacza. Jest to równoznaczne z zachowaniem zserializowanego zapisu ostatniej realizacji tłumacza. Ma to sens, ponieważ nagranie rejestruje to, co jest aktualnie na ekranie. Podczas bieżącej sesji tłumacz konsultuje się z nagraniem, aby podjąć decyzję o tym, jak doprowadzić do docelowego gromadzenia danych (konfiguracja widżetów), przy czym operacje mają najmniejszy koszt. To sprowadza się do tego, że nigdy nie usuwa obiektu (widżetu), aby dodać go ponownie później, kosztem 2. DE zawsze będzie modyfikować, co ma koszt 1. Jeśli zdarzy nam się uruchomić interpreter w niektórych przypadkach, gdy wartości B Zmieniono nie, algorytm DE nie wygeneruje żadnych operacji: zarejestrowany strumień już reprezentuje cel.
Gdy interpreter wykonuje polecenia, konfiguruje także nagranie do następnego uruchomienia.
Analogiczny algorytm
Algorytm ten sam smak jak minimum edit distance (MED). Jednak DE jest prostszym problemem niż MED, ponieważ nie ma "powtarzających się znaków" w serializowanych ciągach wykonawczych DE, jak to jest w MED. Oznacza to, że możemy znaleźć optymalne rozwiązanie dzięki prostemu algorytmowi chciwemu on-line, a nie programowaniu dynamicznemu. Tak właśnie działa algorytm wynalazcy.
Mocne
My się, że jest to dobry wzór do układów wykonawczych z wielu złożonych form, gdzie chcesz całkowitą kontrolę nad umieszczania widgetów z własnego algorytmu układu i/lub logiki „czy innego” co jest widoczne jest głęboko zagnieżdżone. Jeśli w logice formalnej znajduje się K "jeśli elses" N, to istnieje K * 2^N różnych układów, aby uzyskać prawo. Tradycyjne systemy projektowania formularzy (przynajmniej te, z których korzystałem) nie obsługują w ogóle większych wartości K, N. Na ogół masz do czynienia z dużą liczbą podobnych układów i logiką ad hoc, aby wybrać te, które są brzydkie i trudne do utrzymania. Ten wzór DSL wydaje się sposobem na uniknięcie tego wszystkiego. W systemach z wystarczającą liczbą formularzy, aby zrekompensować koszty tłumacza DSL, byłoby nawet taniej podczas początkowej implementacji. Separacja obaw jest także siłą. Programy DSL pobierają treść formularzy, podczas gdy interpreter jest strategią układu, działającą na podstawie podpowiedzi z DSL. Uzyskanie prawidłowego wyglądu i wyglądu podpowiedzi DSL wydaje się samo w sobie znaczącym i fajnym problemem.
wątpliwa ...
nie jestem pewien, że unikanie Usuń/Dodaj par na rzecz Modyfikuj jest wart cały kłopot w nowoczesnych systemach. Wynalazca wydaje się najbardziej dumny z tej optymalizacji, ale ważniejszym pomysłem jest zwięzły DSL z warunkami do reprezentowania formularzy ze złożonością układu izolowaną w interpretorze DSL.
Podsumowanie
wynalazcy tej pory koncentrowała się na głębokich szczegółach jak interpreter podejmuje decyzje. Jest to mylące, ponieważ jest skierowane na drzewa, podczas gdy las jest bardziej interesujący. To jest opis lasu.
Dziękuję za uwagę i dobry opis. Rzeczywiście, myślę, że jego użyteczność wynika z tego, że jest DSL i jest to część inżynierii oprogramowania, która wymaga dużo większego nacisku.Dodałbym tylko 1), że słowo "tłumacz" jest dobrym słowem, ale może wprowadzać w błąd, ponieważ kod jest kompilowany - tłumacze zwykle mają karę za wykonanie rzędu wielkości, a 2) nie twierdzą, że znajdują minimalną odległość edycyjną , tylko rozsądne. –
... także, nie jestem pewien co mówisz o podpowiedziach układu. Każda kontrolka ma pozycję i rozmiar, a ja po prostu obliczam te w locie, albo jako argumenty dla prymitywnych procedur, albo jako "globalne" zmienne z efektami ubocznymi. (Przy obliczaniu tych w locie należy przestrzegać reguły trybu kasowania.) BTW, innym problemem jest wiązanie danych, które można również wykonać w locie i nie wymaga żadnej dodatkowej struktury danych. –
@MikeDunlavey Dzięki Mike. Wskazówki wydawały się mieć sens w przypadku złożonych form. Zamiast po prostu powiedzieć "Przycisk A" w DSL, powiedz "Przycisk w kolumnie poniżej przycisku B" lub coś podobnego. W przeciwnym razie tracisz miły rozdział obaw. Wskazówki są podobne do obecnych tradycyjnych menedżerów układów, takich jak Java Swing. Na tłumaczu opisujesz formularze w DSL, a niektóre fragmenty kodu przetwarzają DSL w celu dodania, usunięcia, modyfikacji. Ten fragment kodu jest z definicji tłumaczem. To nie jest nowy: Windows formy sinve v1.0 mają takie same dla zasobów okna dialogowego, ale ich DSL nie ma warunków warunkowych! – Gene
Możesz poprosić o dodatkowe wyjaśnienia dotyczące tych odpowiedzi ... –
Nadal chcesz, żebym spróbował to przerzucić? Co miałeś na myśli jako możliwe wytłumaczenie? –