Formalne przedstawienie hierarchii abstrakcji

Wprowadzenie

Piszę pracę doktorską na temat abstrakcyjnego modelowania delty (ADM), abstrakcyjnego algebraicznego opisu modyfikacji (znanych jako delty ) zdolnych do działania na produkty (jak w „produktach programowych”). Można to wykorzystać do zorganizowania zestawu powiązanych produktów („linii produktów”) jako prostego produktu podstawowego i zestawu warunkowo zastosowanych delt, a tym samym umożliwienia większego ponownego wykorzystania podstawowych artefaktów.

Szczegóły modelowania delta nie są tak naprawdę ważne w moim pytaniu, ale ADM stanowi dobry przykład do wyjaśnienia problemu, dlatego przedstawię najważniejsze pojęcia.

tło

Główną interesującą strukturą jest deltoid . Produkty pochodzą z Uniwersalny zestaw . Delta pochodzą z monoid z operatorem kompozycji i neutralne elementu . Operator oceny semantycznej przekształca deltę syntaktyczną w relację$(\mathcal P, \mathcal D, \cdot, \epsilon, \mathbf{[\kern-1pt[-]\kern-1pt]})$$\mathcal P$$(\mathcal D, \cdot, \epsilon)$$\cdot : \mathcal D \times \mathcal D \to \mathcal D$$\epsilon \in \mathcal D$$\mathbf{[\kern-1pt[-]\kern-1pt]} : \mathcal D \to 2^{\mathcal P \times \mathcal P}$$d \in \mathcal D$$\mathbf{[\kern-1pt[}\,d\,\mathbf{]\kern-1.5pt]} \subseteq \mathcal P \times \mathcal P$co decyduje o tym, jak może zmodyfikować produkt.$d$

Pytanie

Ponieważ ADM jest algebrą abstrakcyjną, większość moich prac abstrahuje od konkretnej natury produktów i delt, a wiele wyników zostało udowodnionych bez schodzenia na bardziej konkretny poziom. Oczekuje się, że wyniki te zostaną przeniesione do bardziej konkretnej dziedziny, ale jeszcze tego nie sformalizowałem.

Istnieją przykłady i studia przypadków, które działają w konkretnej dziedzinie: obiektowy kod źródłowy, , liczby naturalne, profile telefonów komórkowych itp. Istnieją również pośrednie etapy abstrakcji, takie jak zagnieżdżanie pary klucz-wartość. Dla każdego ponownie zdefiniuję (lub „poprawię”) .$\small\mathrm{\LaTeX}$$(\mathcal P, \mathcal D, \cdot, \epsilon, \mathbf{[\kern-1pt[-]\kern-1pt]})$

Chciałbym wyrazić tę hierarchię w sposób wyraźny: (1) w celu zapewnienia czytelnikowi większej przejrzystości i (2) w celu formalnego uzasadnienia wykorzystania wyników z bardziej abstrakcyjnych poziomów.

Moje pytanie: Jak formalnie zorganizować te poziomy abstrakcji?

Mam nadzieję, że będę w stanie uzasadnić za pomocą prostej relacji udoskonalenia na deltoidach. I czuję, jak to może być po prostu zdefiniowane przez odwoływanie się do relacji na podzbioru i . Ale nie jestem jeszcze pewien. Czy istnieją jakieś podejścia do tego rodzaju problemu, który opisuję? Publikacje, które powinienem przeczytać?$\sqsubseteq$$\mathcal P$$\mathcal D$

Hierarchia deltoidalna

Aby lepiej zrozumieć, co mam na myśli, oto hierarchia abstrakcji naramiennej, o której myślę:

• Streszczenie Deltoid : To podstawowy deltoid, w którym produkty i delty mogą być nadal czymkolwiek. Większość teorii opiera się na tej, a większość wyników została udowodniona na tym poziomie.
  • Relacyjna deltoid : Tutaj delty są relacjami na a jest funkcją tożsamości. $\mathcal P$$\mathbf{[\kern-1pt[-]\kern-1pt]}$
    • Funkcjonalna deltoid : tutaj delty są funkcjonalne (lub „deterministyczne”).
  • Naturalna deltoid : Jest to najprostsza konkretna deltoid, stworzona tylko w celu zilustrowania udoskonalenia deltoidów. Tutaj produkty są liczbami naturalnymi, a delty to proste sekwencje liczb reprezentujące operacje wielomianowe.$\mathcal P = \mathbb N$$\mathcal D = \mathbb N^+$
  • Zagnieżdżona para klucz-wartość deltoid : pośredni poziom abstrakcji dla dowolnej hierarchii, w której klucze są mapowane na wartości lub podhierarchie. Delty mogą dokonywać modyfikacji w tym „drzewie” na dowolnej głębokości.
    • OOP Deltoid : Do abstrakcyjnych reprezentacji programów obiektowych. Są to zasadniczo zagnieżdżone pary klucz-wartość, ponieważ programy mapują nazwy modułów na zestawy klas, które mapują nazwy klas na zestawy metod, które mapują nazwy metod na implementacje metod.
      • ABS Deltoid : ABS to prawdziwy język programowania obiektowego.
    • Profil telefonu Deltoid : W tym przypadku produkt jest płaskim mapowaniem ustawień (takich jak głośność, jasność ekranu itp.) Na wartości z odpowiedniej domeny.
  • $\small\mathrm{\LaTeX}$ Deltoid : Produkty to dokumenty i delty modyfikują je poprzez przedefiniowanie makr.$\small\mathrm{\LaTeX}$

To powinno dać ci dobry obraz tego, co mam na myśli. mówiąc, dla każdego deltoida jest homomorfizmem od do należącym do odpowiedniego relacyjnego deltoida.$\mathbf{[\kern-1pt[-]\kern-1pt]}$$\mathcal D$$\mathcal D'$

Rzeczywista hierarchia może być większa. Może być również inaczej zorganizowany, w zależności od tego, jakiej teorii doskonalenia użyję. Na przykład, jeśli wybiorę prostą relację podzbioru na i Deltoid ABS nie mieści się w zagnieżdżonej deltoidzie pary klucz-wartość, ponieważ jego produkty i delty są w rzeczywistości zwykłym tekstem (kod źródłowy). Jednak podana hierarchia może nadal działać, jeśli użyję homomorfizmów.$\mathcal P$$\mathcal D$

Uważam, że byłoby dobrze, gdybyś zapoznał się z teorią abstrakcyjnej interpretacji, która zapewnia bardzo dokładne odpowiedzi na podobne pytania w nieco innym obszarze analizy programu opartej na sieci.

Wydaje mi się, że używasz frameworka opartego na algebrach. Używam tutaj słowa algebra w znaczeniu algebry uniwersalnej, w której zakładam, że ograniczenia w strukturze algebry wynikają z równości między terminami. Istnieją dwa różne zmysły, w których abstrakcje (lub hierarchie) wchodzą w obraz.

1. Abstrakcja jako relacja między dwoma konkretnymi algebrami. Możesz powiedzieć, że jedna algebra ma bogatszą strukturę niż inna algebra lub że każdy problem, który możesz rozwiązać za pomocą jednej algebry, możesz rozwiązać za pomocą drugiego. Ten rodzaj relacji sformalizowałby homomorfizmy kupna lub inne mapowanie między algebrami.
2. Hierarchie abstrakcji jako rodziny algebry. W twoim przypadku byłyby to rodziny deltoidów o określonych właściwościach. Jako bardziej ogólny przykład rozważ wszystkie częściowo uporządkowane zestawy. Możemy myśleć o sieciach kratowych, sieciach dystrybucyjnych i sieciach boolowskich jako o sekwencji podrodzin o bogatszych właściwościach.

Te dwa pojęcia są ze sobą ściśle powiązane, ale różne.

Abstrakcja między dwiema strukturami

Wgląd w abstrakcyjną interpretację jest taki, że przydatne jest nadanie badanym strukturom pojęcia porządku. Rozważ dwie struktury

$(M, f_M)$ i $(N, f_N)$, z $f_M: M \to M$ i $f_N:N \to N$ jako operacje będące przedmiotem zainteresowania.

Homomorfizm w sensie algebry uniwersalnej wyglądałby mniej więcej tak:

$h:M \to N$ jest funkcją spełniającą równość $h(f_M(a)) = f_N(h(a))$.

Dwie powyższe struktury możemy zobaczyć jako struktury zamówione w przedsprzedaży

$(M, =, f_M)$ i $(N, =, f_N)$

i homomorfizm, który możemy przepisać, aby był funkcją spełniającą

1. że jeśli $a = b$ następnie $h(a) = h(b)$, i
2. dla wszystkich $a$ w $M$, $h(f_M(a)) = f_N(h(a))$.

Załóżmy teraz, że masz inne pojęcie przybliżenia, które ma sens. Na przykład, gdy mamy do czynienia z zestawami stanów podczas weryfikacji programu, włączenie podzbioru ma sens w przypadku niektórych aplikacji lub gdy mamy do czynienia z formułami zautomatyzowanej dedukcji, implikacja ma sens. Ogólniej możemy rozważyć

$(M, \preceq, f_M)$ i $(N,\sqsubseteq, f_N)$, gdzie $\preceq$ i $\sqsubseteq$ są zamówieniami wstępnymi.

Teraz zamiast homomorfizmu możemy mieć funkcję abstrakcji

$\alpha: M \to N$ który jest

1. monotonowy, co oznacza, że ​​kiedykolwiek $a \preceq b$ mamy $\alpha(a) \sqsubseteq \alpha(b)$, i
2. częściowo dojeżdża do pracy z operacjami: $\alpha(f_M(a)) \sqsubseteq f_N(\alpha(a))$ dla wszystkich $a$ w $M$.

Funkcja abstrakcji wyraża ideę, że jeśli struktura się skończy $N$ jest abstrakcją struktury $M$, a następnie oceniając termin w $N$ nie może dać dokładniejszych wyników (w odniesieniu do pojęcia przybliżenia w $N$) niż ocena tego samego terminu w $M$ a następnie mapowanie na $N$.

Teraz możemy zapytać, czy konieczne jest podejście do problemu w kategoriach abstrakcji, a nie wyrafinowania. Czyli nie możemy tego powiedzieć$M$ jest udoskonaleniem $N$i formułować warunki w kategoriach. To właśnie robi funkcja konkretyzacji .

Funkcja konkretyzacji $\gamma: N \to M$jest monotonny i spełnia nierówność$f_M(\gamma(b)) \preceq \gamma(f_N(b))$.

Warunki abstrakcji i konkretyzacji nazywane są warunkami solidności w interpretacji abstrakcyjnej. W specjalnym przypadku to$\alpha$ i $\gamma$tworzą połączenie Galois, warunki abstrakcji i konkretyzacji są równoważne. Zasadniczo nie są one równoważne.

Wszystko, co do tej pory zrobiliśmy, jedynie formalizuje pojęcie abstrakcji między parą struktur. To, co powiedziałem, można streścić znacznie bardziej zwięźle w języku teorii kategorii. Unikałem kategorii z powodu twojego komentarza powyżej.

Hierarchie abstrakcji

Załóżmy, że mamy strukturę $\mathcal{M}$obdarzony przedsprzedażą i niektórymi operacjami. Możemy rozważyć wszystkie struktury$\mathcal{N}$ takie, że $\mathcal{N}$ jest abstrakcją $\mathcal{M}$w sensie powyżej. Jeśli mamy to$\mathcal{N}_1$ jest abstrakcją $\mathcal{N}_2$ i oba są abstrakcjami $\mathcal{M}$, mamy trzy elementy hierarchii. Relacja „jest abstrakcją” pozwala nam zdefiniować zamówienie wstępne między strukturami. Nazwijmy rodzinę struktur uporządkowanych według abstrakcji hierarchią .

Jeśli wezmę twój przykład, wydaje się, że twoja abstrakcyjna deltoid może być kandydatem na maksymalny element w jakiejś hierarchii. Nie jestem do końca pewien, ponieważ abstrakcyjny deltoid wydaje się być rodziną deltoidów, a nie konkretnym deltoidem.

Teraz możesz rozważyć różne hierarchie. Hierarchia wszystkich deltoidów. Podhierarchia oparta na różnych powyższych rozważaniach. Konkretnym przykładem w kontekście abstrakcyjnej interpretacji jest hierarchia kompletnych sieci, które są w połączeniu Galois z daną siecią zestawów mocy, oraz podhierarchie składające się wyłącznie z sieci dystrybucyjnych lub tylko boolowskich.

Jak zauważa Martin Berger w komentarzach, pojęcie abstrakcji między hierarchiami jest uchwycone przez powiązanie między kategoriami.

Kategoryczna perspektywa

Pojawił się komentarz z prośbą o więcej komentarzy na temat kategorii. Tego komentarza już nie ma, ale i tak odpowiem.

Cofnijmy się i spójrzmy na to, co robisz przy projektowaniu deltoidów, i co opisałem powyżej z bardziej ogólnej perspektywy. Interesuje nas zrozumienie podstawowej struktury podmiotów, którymi manipulujemy w kontekście oprogramowania oraz relacji między tymi podmiotami.

Pierwszą ważną realizacją jest to, że interesuje nas nie tylko zestaw elementów, ale także operacje, które możemy wykonać na tych elementach i właściwości tych operacji. Ta intuicja napędza projektowanie klas w programowaniu obiektowym i definiowanie struktur algebraicznych. Wyraziłeś już tę intuicję w definicji deltoida, która zidentyfikowała kilka interesujących operacji. Mówiąc bardziej ogólnie, jest to proces myślowy leżący u podstaw opisów algebraicznych. Musimy określić, jakie są nasze operacje i jakie mają one właściwości. Ten krok pokazuje nam strukturę typów, z którą pracujemy.

Drugą realizacją jest to, że interesuje nas nie tylko zestaw elementów, ale relacje abstrakcyjne. Najprostszą formalizacją, jaką mogę sobie wyobrazić z abstrakcji, jest rozważenie wcześniej ustalonego zestawu. Możemy pomyśleć o zamówionym zestawie jako ścisłym uogólnieniu zestawu na coś, co przychodzi wraz z koncepcją przybliżenia.

Idealnie chcemy pracować w środowisku, w którym oba powyższe spostrzeżenia są pierwszorzędnymi obywatelami. Oznacza to, że chcemy ustawienia typu takiego jak algebra, ale także ustawienia presetu uwzględniającego przybliżenie. Pierwszym krokiem w tym kierunku jest rozważenie sieci. Krata jest interesującą koncepcyjnie strukturą, ponieważ możemy ją zdefiniować na dwa równoważne sposoby.

1. Możemy zdefiniować sieć równorzędnie jako zbiór $(L, \sqcap, \sqcup)$wyposażony w operację Meet i Join. Możemy czerpać częściowy porządek poprzez zdefiniowanie$a \sqsubseteq b$ trzymać za każdym razem $a \sqcap b = a$.
2. Alternatywą jest zdefiniowanie sieci jako zestawu częściowo uporządkowanego $(L, \sqsubseteq)$ spełnianie, że każda para elementów w $L$ma unikalną największą dolną granicę i najmniejszą górną granicę. Następnie możemy wyliczyć spotkanie i połączyć operacje z częściowego zamówienia.

Krata jest zatem strukturą matematyczną, do której można podejść z perspektywy algebraicznej lub aproksymacyjnej. Wadą tego jest to, że same elementy sieci nie mają struktury typu, która jest uwzględniona w relacji aproksymacji. Oznacza to, że nie możemy porównywać elementów w oparciu o pojęcie większej lub mniejszej struktury.

W kontekście twojego problemu możesz myśleć o kategoriach jako o naturalnym uogólnieniu zamówień przedpremierowych, które wychwytują zarówno pojęcie aproksymacji (w morfizmach), jak i strukturę typów w układzie algebraicznym. Ustawienie teorii kategorii pozwala nam zrezygnować z różnych niepotrzebnych rozróżnień i skupić się na strukturze istot, na których ci zależy, i przybliżeniu tej struktury. Uniwersalne właściwości i powiązania dają bardzo potężne słownictwo i narzędzia do zrozumienia krajobrazu interesujących cię struktur i umożliwiają rygorystyczne matematyczne traktowanie nawet intuicyjnych pojęć, takich jak różne poziomy abstrakcji.

Jeśli chodzi o mój komentarz na temat abstrakcyjnych deltoidów, wydaje się, że to, czego chcesz, to kategoria. Abstrakcyjna deltoid jest specyficzną kategorią analogiczną do kategorii zbiorów. Istnieją inne kategorie, które rozważasz. Początkowo myślałem, że definiujesz deltoidę, która w sensie teorii kategorii będzie obiektem końcowym (lub końcowym).

Studiujesz pytania, na które teoria kategorii daje bardzo satysfakcjonujące odpowiedzi. Mam nadzieję, że sam dojdziesz do tego wniosku.

Bibliografia

1. Abstrakcyjna interpretacja i zastosowanie do programów logicznych , Patrick Cousot i Radhia Cousot. Pierwsza połowa tego artykułu to ogólne wprowadzenie do samouczka na temat interpretacji abstrakcyjnej.
2. Abstrakcyjne ramy interpretacyjne , Patrick Cousot i Radhia Cousot. W tym artykule szczegółowo omówiono wszystkie zarysowane powyżej możliwości dotyczące funkcji abstrakcji i konkretyzacji.
3. Systematyczne projektowanie ram analizy programów , Patrick Cousot i Radhia Cousot. Był to artykuł, który wprowadził pojęcie hierarchii abstrakcji w kontekście analizy programu.
4. Uogólnione silne zachowanie według abstrakcyjnej interpretacji , Francesco Ranzato i Francesco Tapparo. W tym artykule zastosowano te idee w innym kontekście abstrakcji, który zachowuje formuły logiki czasowej. Znajdziesz tutaj działające przykłady abstrakcji logicznych i dystrybucyjnych.
5. Abstrakcyjna interpretacja, relacje logiczne i rozszerzenia Kan , Samson Abramsky. Przedstawia perspektywę teorii kategorii na powyższym materiale teoretycznym rzędu.

Pracujesz nad swoim doktoratem. Mówiąc: „Nie jestem dobrze zorientowany$X$„nie jest usprawiedliwieniem. A jeśli jesteś dobry, to powiedz„ mój doradca nie wie $X$„nie jest również wymówką.

Używasz monoidów tam, gdzie powinieneś używać kategorii. Twoje operacje monoidalne zakładają, że możesz łączyć dowolne$\delta$jest razem. Ale czy to naprawdę ma sens, na przykład, jak skomponowałbyś „dodaj plastikową obudowę” i „dodaj metalową obudowę”? Myślę, że niektóre z was$\delta$powodują puste relacje, ponieważ nie mają sensu. Powinieneś być podejrzliwy wobec tego rodzaju rzeczy.

Jako zainteresowany obserwator wydaje się, że monoid powinien być kategorią, więc możemy skomponować dwie $\delta$tylko wtedy, gdy ma sens ich skomponowanie. Zatem twoja ocena semantyczna jest po prostu funktorem do kategorii zbiorów i relacji. A potem widzisz, że istnieje wiele innych kategorii, których możesz użyć. Delty funkcjonalne będą odpowiadały funktorowi, który odwzorowuje się na kategorię zbiorów i funkcji, deltoid liczb naturalnych jest funktorem na monoidę wielomianów na liczbach naturalnych (postrzeganych jako kategoria) itp.

Nie jestem pewien, czy chcesz zbyt poważnie sformalizować telefony komórkowe LaTeX i Nokia w ogólnej teorii. Ale oczywiście twoja teoria powinna mieć zastosowanie do takich przykładów (po prostu nie odkładaj słuchawki, gdy odkryjesz, że telefony komórkowe nie mają właściwie zdefiniowanej semantyki).

Jesteś naprawdę shortchanging siebie poprzez naleganie na określonej technologii (przez doradcę?), Przez wygląda to.