Czy koncepcję Entropy można wykorzystać do analizy kodu źródłowego w użyteczny sposób?

19

Wydaje mi się logiczne, że można zdefiniować kontekst dla statycznej analizy kodu źródłowego, który obejmował reguły generujące względną wartość złożoności. Wiem, że to nie jest w sensie fizycznym, ponieważ kod sosu nie ma „Energii”, ale założę się, że przynajmniej starałem się wykreślić analogię. Czy ktoś wie o tym, a jeśli tak, to w jakim stopniu przyniósł on użyteczne wyniki?

Aaron Anodide
źródło
Nie mam żadnej wiedzy konkretnego na ten temat. Ale jako inżynier wierzę, że możesz zastosować tę koncepcję do wszystkiego, co chcesz we wszechświecie. „Wszystko” jest energią. Twój kod może być modelowany jako byt, który ma energię.
wleao
3
Istnieją już miary złożoności kodu - złożoność cykliczna, długość klasy (LOC), długość metody (LOC), liczba pól, liczba parametrów metody, złożoność ścieżki n, wyjście wentylatora / wyjście wentylatora i analiza przepływu danych (DU / łańcuchy DD). Wykonano prace, aby skorelować je z gęstością defektów, wysiłkiem na rzecz utrzymania i łatwością zrozumienia. Jak wypada to, czego szukasz?
Thomas Owens
@Thomas Owens: Myślę, że właśnie o to prosił PO, proszę opublikować to jako odpowiedź!
blubb
@ Simon, ok, jeśli tak uważasz. Nie jestem w 100% pewien.
Thomas Owens
1
W przypadku niekonwencjonalnego podejścia można albo bezpośrednio obliczyć współczynnik kompresji danych dla kodu źródłowego, albo obliczyć współczynnik kompresji danych po pewnego rodzaju normalizacji. (np. c2.com/doc/SignatureSurvey ) - Nie wiem, jak by to było znaczące lub przydatne, ale może dać pewien wgląd w połączeniu z bardziej tradycyjnymi pomiarami.
William Payne,

Odpowiedzi:

22

Istnieje już szereg miar złożoności kodu:

  • Złożoność cykliczna
  • Długość klasy
  • Długość metody
  • Liczba pól
  • Liczba parametrów metody
  • Złożoność ścieżki N.
  • Fan-in i fan-out
  • Analiza przepływu danych (łańcuchy DU / DD)

Wykonano prace, aby skorelować je z gęstością defektów, wysiłkiem na rzecz utrzymania i łatwością zrozumienia. Niektóre są bardziej znaczące niż inne, w zależności od tego, czego próbujesz się nauczyć z analizy. Nie jestem zbyt obeznany z pojęciem entropii z nauk fizycznych, ale zastanawiam się, czy śledzenie pomiarów i metryk takich jak te, które wymieniłem w czasie i powiązanie ich z defektami w czasie, byłoby podobne do tego, czego szukasz.

Możesz być także zainteresowany definicją entropii oprogramowania i zgnilizny oprogramowania przez Ivara Jacobsona . Ogólna idea tych tematów jest taka, że ​​wraz z upływem czasu, wraz ze zmianami kodu i środowiska wykonawczego, system oprogramowania zaczyna się degradować. Refaktoryzacja jest postrzegana jako metoda minimalizacji entropii lub zgnilizny, a przynajmniej z moich doświadczeń, wskaźniki i pomiary, o których wspomniałem powyżej, byłyby wskaźnikami, że refaktoryzacja może być konieczna w systemie lub podsystemie.

Thomas Owens
źródło
13

Myślę, że próbujesz narysować analogię między entropią termodynamiczną a „złożonością”. Rzecz w tym, że entropia jest miarą nieporządku, a nie złożoności . Nie wierzę, że te dwa są równoważne i wymienne.

Najbliższym analogiem do entropii termodynamicznej jest entropia Shannona, która mierzy wielkość zaburzenia w zmiennej losowej. Pojęcie to dotyczy przede wszystkim ilości „informacji” w wiadomości.

Pod tym względem fragment kodu może zawierać wiele informacji (wysoka entropia), ale bardzo małą złożoność. Pomyśl o programie, który po prostu drukuje bardzo długi ciąg dowolnych znaków. Ma wiele informacji, ale niską złożoność.

tskuzzy
źródło
1
Entropia dla kodu źródłowego nie byłaby obliczana z tego samego modelu, co dla tekstu nieustrukturyzowanego. Z modelu dostosowanego do kodu źródłowego , powinno być sensowne obliczyć entropię, która nie zmieniałaby szeroko dla dowolnych sytuacjach, takich jak długi ciąg znaków, które opisują.
Matthew Rodatus
Jak oceniłbyś entropię i złożoność w danym programie? Twierdziłbym, że zawiera wiele informacji bez względu na używany model. Chociaż definicja złożoności jest znacznie mniej jasna.
tskuzzy
1
Podobnie jak nie ma sensu obliczanie entropii termodynamicznej dla tekstu w języku naturalnym, nie ma sensu używać entropii Shannon do komputerowego kodu źródłowego, ponieważ znaczenie programu jest skonstruowane w oparciu o inny zestaw reguł i wzorców (tj. składnia). Język naturalny ma własną składnię. Model musi odpowiadać składni domeny. Entropia termodynamiczna jest mierzona w dżulach na kelwin. Entropia Shannona jest mierzona w bitach. Entropia kodu źródłowego byłaby mierzona w ... różnych wymiarach całkowicie. W odpowiedzi odpowiedziałem nożem na wygląd modelu.
Matthew Rodatus
Podoba mi się twoja odpowiedź - myślałem na przykład, kiedy wprowadzono „zły” kod, zwiększa się entropia całego środowiska, w którym ono istnieje, tj. Włączając programistów, którzy muszą ciężej pracować - w ten sposób może być praktyczne, jeśli nie związek naukowe termodynamiki?
Aaron Anodide
2

Entropia jest „środkiem nieporządku [i] nieprzewidywalności”. Szerszy zakres unikalnych wzorców w informacji (tj. Z grubsza „więcej znaczenia”) wskazuje na wyższy stopień entropii.

Zastosowane do kodu źródłowego komputera, myślę, że zasada ta może być przydatna. Jednakże, konieczne byłoby zaprojektować model probabilistyczny dla kodu źródłowego z którego można obliczyć entropię. (Struktura danych, która przychodzi mi do głowy, to wykres z różnymi typami krawędzi: wywołanie, dziedziczenie klas itp.)

Po zaprojektowaniu modelu, a następnie wypełnieniu go kodem źródłowym aplikacji (tj. Częstotliwościami dla węzłów / krawędzi), można obliczyć entropię.

Nie znam żadnych badań na ten temat, ale moja intuicja jest taka, że ​​niski stopień entropii oznaczałby, że kod źródłowy ponownie wykorzystuje wspólne wzorce w całej aplikacji (tj. DRY ). I odwrotnie, wysoki stopień entropii oznaczałby, że kod źródłowy ma wysoką złożoność i nie został dobrze uwzględniony.

Matthew Rodatus
źródło
2

Jednym ze sposobów myślenia o entropii jest „średnia informacja do zdobycia”, więc myślę, że lepiej jest wrócić do informacji o modelowaniu. Znam dwa podstawowe podejścia do modelowania matematycznego informacji. (Wybacz mi, że podawałem odniesienia do Wikipedii, ale IMHO nie są złe.)

  • Informacje Shannona , które analizują zestawy symboli, rozkłady prawdopodobieństwa na nich, kody, które mogą przenosić informacje między zestawami symboli, i długości tych kodów. Ogólne pojęcia dotyczące wydajności kodu, szumu, wykrywania błędów i korekcji przez redundancję itp. Są ujęte w teorii informacji Shannona. Jednym ze sposobów wyrażania informacji jest stwierdzenie, że jest to długość najkrótszego kodu binarnego, który może reprezentować symbol. Jest to oparte na prawdopodobieństwie, które jest wartością liczbową przypisaną do symbolu lub zdarzenia przez jakiegoś obserwatora.

  • Solomonoff (lub Kołmogorowa ) informacje. Oto inne wyjaśnienie. W tym preparacie, zawartość informacyjna symbol lub imprezy jest reprezentowana przez długość najkrótszego programu, który może ją obliczyć. Tutaj znowu, to jest względne, nie przypisując prawdopodobieństwem obserwatora, ale do uniwersalnego urządzenia, które można uruchomić program. Ponieważ każda uniwersalna maszyna może być symulowane przez uniwersalną maszynę Turinga, to znaczy, w pewnym sensie, że treść informacji symbolu lub zdarzenia nie jest względne, ale absolutne.

Jeśli mogę sobie pozwolić na mówienie tego, co myślę, że to oznacza w warunkach codziennych, o których pisałem książkę , to po prostu oznacza, że złożoność programu jest jego długość, kiedy takie rzeczy specyfikacji funkcjonalnej i języka są utrzymywane na stałym poziomie, z odpowiednimi dodatki na komentarze i długości nazwisk. Ale jest problem z tym - w „APL Tarpit”, gdzie zwięzłość równa niezrozumiałość.

O wiele lepiej jest wziąć pod uwagę (tak jak to uczyłem podczas nauki AI), że funkcjonalna specyfikacja programu składa się z modelu mentalnego, który jest nie tylko rzeczywisty, ale także efektywnie zakodowany, to znaczy z dostatecznie małą redundancją, która zmienia zdanie na temat wymagań można to zrobić bez zbytniego zagrożenia, zarówno wewnętrznie sprzeczny - czyli o „błąd”. Następnie proces programowania jest kanał informacyjny, do którego wprowadzany model mentalny, a jego wyjście jest kod źródłowy działa. Wówczas, gdy zmiana jest wykonana w modelu mentalnego, że delta musi być karmione przez proces programowania i przekształcony w odpowiadającą delta w kodzie źródłowym. To delta jest łatwo zmierzyć. Różnica pomiędzy źródłem przed nałożeniem tej delta, a po zastosowaniu go (całkowicie, wszystkie błędy opracowano) i policz liczbę wstawionych, usuniętych i zamienionych bloków kodu. Im mniejsza to jest lepiej język kod źródłowy oznacza język model mentalny jest reprezentowany w (pod względem rzeczowników, czasowników i struktury). Jeśli środek jest w jakiś sposób uśrednione przestrzeni prawdopodobnych zmian funkcjonalnych, które jest pojęciem entropii w języku źródłowym, a mniej znaczy lepiej. Jest to termin ten -Język specyficzny dla domeny (DSL)

Przepraszam, jeśli odniesienia są słabe / osobisty, ale myślę, że ta ogólna kwestia jest bardzo ważna.

Mike Dunlavey
źródło
+1 do Shannon i Kołmogorowa, z których oba są istotne ...
Alex Feinman
@Alex: Myślę Shannon jako mające zastosowanie w czasie wykonywania. Tak na przykład, można zrozumieć działanie algorytmów pod względem entropii punktów decyzyjnych, a można zrozumieć normalizację struktury danych w zakresie minimalnym kodu. Algorytmiczne informacji wydaje się o wiele bardziej językowym, stosując do odpowiedniego języka za to wyrazisty cel, a algorytm starasz się zrobić skuteczny jest tajemnicza, że korby w głowie podczas programowania.
Mike Dunlavey,
2

Jon Jagger i Ølve Maudal mają nieco inny pogląd kodu Entropia, co widać w ich 2011 konferencyjnej Accu sesji Kod Entropy i Fizyki Oprogramowania .

Rozmawiają o stabilność kodu jest podobne do tego, czy deweloperzy przyszłe / opiekunowie mogą zmienić ten kod.

Aby to zademonstrować, przeprowadzili ankietę z wieloma fragmentami kodu, a wyniki były dość interesujące.

  • Wydawało się, że silne uprzedzenia wobec stylu jedna prawda-nawiasów .
  • Ale silne nastawienie do przyjęcia pojedynczego stwierdzenia, jeśli jest.
  • Istniało silne uprzedzenie wobec stosowania zmiennych tymczasowych.
  • Dodanie nawiasów było mocno obciążone, aby oczywiste było, że operator ma pierwszeństwo.

plus 16 innych.

Wydawało się, że ogólną tendencją jest ułatwianie zrozumienia kodu i trudniejsze do błędnego zrozumienia.

Analizują także niektóre zmiany wprowadzone w dużej bazie kodu na przestrzeni lat.

Chociaż slajdy same w sobie nie są transkrypcją sesji, wciąż jest kilka interesujących punktów.

Mark Booth
źródło
1

Uczyłem się pod profesora , którzy używali entropia jako miara złożoności programów (nasz podręcznik był starszy edycja tego jednego , kilku jego pubów są tutaj ). W FAU odbyło się wiele rozpraw, w których była to jedna z głównych miar, ale strona internetowa szkoły zmieniła się od czasu ostatniego spojrzenia i nie jestem w stanie zlokalizować, gdzie obecnie znajduje się praca / praca doktorska.

Jedną z takich rozpraw jest teoria informacji i pomiar oprogramowania .

Tangurena
źródło
0

Jeśli chcesz definicję, która jest „Mathy” w sposób entropia jest, warto spojrzeć na Złożoność Kołmogorowa, które środki złożoność przez minimalną ilość kodu coś ewentualnie mogłyby być wykonane w. Jednak nie jest to złożoność kodu, ale z tego, co staramy się robić z kodem. Ale myślisz, że to istotne, ponieważ teoretycznie można porównać konkretny kawałek kodu z minimalnym jeden. Jednak nie jest to obecnie użyteczną techniką pomiaru złożoności rzeczywistym kodzie światowej.

psr
źródło
0

Myślę, że to nie jest opłacalne, można argumentować, że dobrze napisany kod bazowy powinien mieć większą entropię (zaburzenia). Pomyśl na bazie kodu gdzie fragment kodu jest powtarzany w kółko, może być skompresowany z wysokim współczynnikiem kompresji z powodu powtarzających się część (niższa entropia / rozmiar pliku), jednak jeśli przenieść kod do osobnej funkcji współczynnik kompresji będą niższe (większy rozmiar entropii / pliku).

Tak może się wydawać, a następnie można obliczyć coś takiego entropia / codelines stosując współczynnik kompresji jako współczynnik, aby mierzyć jakość kodu, jednak ten problem, że ma całkowite wejście losowe będzie wyglądać najlepiej kodu świata wich nie jest oczywisty.

Rzeczywiście stopień sprężania jest to dobry miernik do pomiaru entropii kodu, jednak oba nie są dobre mierniki jakości kodu.

Twórca gier
źródło
0

Cóż, entropia termin nie pojawia się tylko w termodynamiki i teorii informacji, pojawia się również w świecie rzeczywistym kompresji danych. W tym kontekście, entropia, że sprężarka widzi jest równa liczbie bitów produkuje. (Zauważ, że powiedziałem „entropię że sprężarka widzi ”, ponieważ to, co jest uważane za entropia zależy od modelu zastosowań sprężarek opisać dane wejściowe To jest powód, dlaczego różne kompresory produkować plików o różnej wielkości. Co to jest entropia do jeden sposób wykorzystać struktury do drugiego).

Może to być w zasadzie pięknie zastosowane do kodu źródłowego złożoności: „Po prostu” napisać kompresor, który działa tylko na standardowym kodzie źródłowym w pełni zgodny, który kompresuje faktycznie parsowania go jak kompilator, wytwarzając odpowiednie drzewo składni. Wtedy może dojść do tego drzewa składni, i zdecydować, w każdym węźle, które węzły byłby możliwy w każdym punkcie, kodujący ten węzeł z tej wiedzy.

Tak więc, na przykład, jeśli język pozwala albo istniejący identyfikator, albo coś w nawiasach lub produktu w punkcie konkretnego, sprężarka liczyłbym ewentualne istniejące identyfikatory, biorąc informacje typu uwzględnieniu (powiedzmy masz 3 takie identyfikatory ) i dodać 2 dla dwóch możliwych podwyrażeń, dając 5 mozliwosci. Więc węzeł zostanie zakodowany z lb 5 = 2.32bitów. W przypadku dwóch możliwych podwyrażeń, konieczne byłoby więcej bitów do zakodowania ich zawartość.

To rzeczywiście dałoby bardzo dokładną miarę złożoności kodu. Jednak ten środek jest nadal bezużyteczny! To bezużyteczne z tego samego powodu, że wszystkie pomiary kod złożoności są bezużyteczne: Oni nie robić narysować połączenia między zmierzoną złożoności kodu (cokolwiek to może być) i złożoność problemu, że rozwiązuje kod. Można zawsze znaleźć absurdalnie skomplikowane rozwiązania problemów programistycznych zaimponować pracodawcy ze swoimi liczy LOC, ale kod nie miara złożoności powie, że zadanie mogło być rozwiązane z ułamek wysiłku.

cmaster - przywróć monikę
źródło
-2

Kod ma dokładnie tyle samo entropii, co liczba π.

Utrzymanie i zmiana kodu może wprowadzić entropię (ponieważ wiąże się to z możliwą zmianą stanu).

Ale kod jest tylko duża liczba. Z reprezentacji binarnej.

S.Lott
źródło
myśląc w ten sposób, czy nie można powiedzieć, że cały kod ma taką samą entropię, gdy jest gzip?
Aaron Anodide
@Gabriel: To inna sprawa. To entropia ilość zakłóceń w bitach podczas oglądania ten numer jako sekwencję bitów. Brak wyświetlania jako pojedynczej liczby statycznej. Kod źródłowy to pojedynczy numer statyczny, na przykład 42. Tylko z dużo większą ilością bitów.
S.Lott,
ciekawe, czy w tym widoku dziesiętne 42 i dwójkowe 42 mają równą entropię, czy też ten komentarz mówi, że liczby nie mają entropii, i o to właśnie chodzi?
Aaron Anodide
„liczby nie mają entropii”. Po prostu są. Przedstawienie, widziane jako strumień symboli może mieć entropii, ale liczba jako całość jest tylko kilka.
S.Lott,