Jak zweryfikować / udowodnić ortogonalność języka programowania?

10

Znam pojęcie ortogonalności, ale czy z punktu widzenia języka programowania istnieje sposób, aby to zweryfikować / udowodnić?

Na przykład w języku C # można użyć publiclub staticdo podpisu metody. Możesz użyć jednego lub obu z nich, a one nie przeszkadzałyby sobie nawzajem, więc są do siebie prostopadłe, prawda?

Moje pytanie brzmi: w jaki sposób mogę przejść do pozostałych funkcji, szczególnie tych, które nie są ze sobą powiązane?

Czy wszystkie funkcje muszą ze sobą współistnieć?

Czy istnieje język programowania, który jest w 100% ortogonalny?

Joan Venge
źródło
Zacznij od (blisko) początku: asemblera?
Matthew Flynn
1
Aby faktycznie coś udowodnić, potrzebujesz formalnej definicji tego. A jeśli twoja definicja będzie czymś tak dużym jak specyfikacja C #, udowodnienie, że wszystko zajmie dużo pracy.
svick

Odpowiedzi:

4

Nie jestem pewien, czy ortogonalność może służyć jako użyteczna lub ważna metryka w przypadku języków wyższego rzędu ogólnego przeznaczenia, takich jak C #, ponieważ wymaga ona rozróżnienia „operacji” i „operandów” - małych części języka, które nie są łatwe rozróżnialne w językach wysokiego rzędu, takich jak C #.

Moje rozumienie ortogonalności opiera się na języku asemblera, w którym ortogonalność zestawu instrukcji określonego procesora lub mikrokontrolera wskazywała, czy istnieją pewne ograniczenia operacji wykonywanych przez ten procesor lub kontroler w zależności od typów danych. Na początku było to ważne, ponieważ nie każdy procesor obsługiwał operacje na liczbach ułamkowych lub liczbach o różnej długości itp.

W związku z tym wolałbym sprawdzić ortogonalność wspólnego języka pośredniego za pomocą języka Stack Machine jako celu kompilatora C #, a nie samego C #.

Jeśli naprawdę interesujesz się ortogonalnością C # i nie mylę się tutaj (w jakimkolwiek celu) sugerowałbym spojrzenie na niektóre algorytmy programowania genetycznego . Możesz ich użyć do wygenerowania różnych programów z podanego zestawu słów kluczowych (nawet tych pozbawionych znaczenia) i możesz po prostu automatycznie sprawdzić, czy można je skompilować. Pomoże ci to automatycznie zobaczyć, które elementy języka mogą być łączone razem i uzyskać pewne aspekty twojej ortogonalności.

Alexander Galkin
źródło
6

Termin „ortogonalność” jest terminem laickim dla precyzyjnego pojęcia matematycznego: terminy językowe tworzą początkową algebrę (patrz na Wikipedii).

Oznacza to w zasadzie „istnieje zgodność 1-1 między składnią a znaczeniem”. Oznacza to: istnieje dokładnie jeden sposób wyrażania rzeczy, a jeśli umieścisz jakieś wyrażenie w określonym miejscu, możesz także umieścić w nim inne wyrażenie.

Innym sposobem myślenia o „ortogonalnym” jest to, że składnia jest zgodna z zasadą podstawiania. Na przykład, jeśli masz instrukcję ze szczeliną dla wyrażenia, możesz tam umieścić dowolne wyrażenie, a wynikiem jest nadal poprawny składniowo program. Ponadto, jeśli wymienisz

Chcę podkreślić, że „znaczenie” nie oznacza wyniku obliczeniowego. Oczywiste jest, że oba 1 + 2 i 2 + 1 są równe 3. Jednak warunki są różne i implikują inne obliczenia, nawet jeśli mają ten sam wynik. Znaczenie jest inne, podobnie jak dwa algorytmy sortowania są różne.

Być może słyszałeś o „abstrakcyjnym drzewie składni” (AST). Słowo „streszczenie” oznacza tutaj dokładnie „ortogonalny”. Technicznie większość AST nie jest w rzeczywistości abstrakcyjna!

Być może słyszałeś o języku programowania „C”? Notacja typu C nie jest abstrakcyjna. Rozważać:

int f(int);

Oto zwracany typ deklaracji funkcji int. Typ wskaźnika do tej funkcji określa:

int (*)(int)

Uwaga: nie można zapisać typu funkcji! Notacja typu C jest do bani! To nie jest abstrakcyjne. To nie jest ortogonalne. Załóżmy teraz, że chcemy stworzyć funkcję, która akceptuje powyższy typ zamiast int:

int (*) ( int (*)(int) )

Wszystko ok .. ale .. co jeśli chcemy zamiast tego zwrócić:

int (*)(int) (*) (int)

Woops! Nieważny. Pozwala dodać parens:

(int (*)(int)) (*) (int)

Woops! To też nie działa. Musimy to zrobić (to jedyny sposób!):

typedef int (intintfunc*) (int);
intintfunc (*)(int)

Teraz jest w porządku, ale użycie tu pisma maszynowego jest złe. C jest do bani. To nie jest abstrakcyjne. To nie jest ortogonalne. Oto jak to zrobić w ML, czyli:

 int -> (int -> int)

Potępiamy C na poziomie składni.

Ok, teraz pozwala flogować C ++. Możemy naprawić powyższą głupotę za pomocą szablonów i uzyskać zapis podobny do ML (mniej więcej):

fun<int, int>
fun< fun<int,int>, int>

ale rzeczywisty system typów jest zasadniczo wadliwy w odniesieniu do referencji: jeśli Tjest typem, to czy jest T&typem? Odpowiedź brzmi głupio: na poziomie składni, jeśli masz typ U = T &, wtedy U & jest dozwolone, ale oznacza to tylko, że T &: odwołanie do odwołania jest oryginalnym odwołaniem. To jest do bani! Semantycznie łamie wymóg wyjątkowości. Gorzej: T&& nie jest dozwolone składniowo: łamie to zasadę podstawiania. Tak więc odwołania do C ++ łamią ortogonalność na dwa różne sposoby, w zależności od czasu wiązania (parsowanie lub analiza typu). Jeśli chcesz zrozumieć, jak to zrobić dobrze ... nie ma problemu ze wskaźnikami!

Prawie żaden prawdziwy język nie jest ortogonalny. Nawet Schemat, który udaje wielką klarowność wypowiedzi, nie jest. Jednak wiele dobrych języków można uznać za mających „względnie bliskie podstawy cech ortogonalnych” i jest to dobra rekomendacja dla języka, zastosowanego zarówno do składni, jak i do podstawowej semantyki.

Yttrill
źródło
Więc uważasz, że ML jest bardziej ortogonalny niż inne? Co z Lispem i Haskellem?
Joan Venge
1
@joan: cóż, lisp nie ma żadnych funkcji, więc spełnia wymagania in vaccuuo :)
Yttrill 30.01.12
@joan: Nie jestem programistą Haskell, więc trudno powiedzieć, ale obecność w Haskell „wyjątkowo wysokiego poziomu funkcjonalności” wskazuje na silną ortogonalność: po prostu nie można mieć spójnej implementacji Monad lub Strzałek, chyba że reszta języka ma znaczną „ortogonalność”
Yttrill
Co myślisz o Pascalu. Wydaje się, że ładunki są lepsze niż C.
supercat
Wiem, że mój komentarz jest prawie 4 lata spóźniony, ale właśnie go spotkałem. Ta odpowiedź jest błędna w prawie wszystkim. Nawet całe „to jedyny sposób!” część jest po prostu zła. Można to łatwo wyrazić bez przykładu typedef int (*intintfunc())(int) { ... }- intintfunc to funkcja, która nie przyjmuje argumentów i zwraca wskaźnik do funkcji, która przyjmuje 1 argument int i zwraca wartość int.
Wiz
4

Udowodnienie ortogonalności jest negatywne. Oznacza to, że nie masz żadnych konstrukcji, które nie są ortogonalne, co oznacza, że ​​o wiele łatwiej jest udowodnić, że coś nie jest ortogonalne niż jest.

W praktyce większość ludzi mówi o ortogonalności języków programowania w kategoriach stopni, zamiast być całkowicie ortogonalnymi lub nie. Kiedy wiedza z robienia czegoś w jednym kontekście przekłada się na inny kontekst i „robi to, czego oczekujesz”, mówi się, że ten język jest bardziej ortogonalny. LISP jest uważany za wysoce ortogonalny, ponieważ wszystko jest listą, ale nie sądzę, że można powiedzieć, że jest w 100% ortogonalny z powodu pewnych redundancji, które ułatwiają jego użycie. C ++ jest uważany za niezbyt ortogonalny, ponieważ istnieje wiele małych „gotchas”, w których nie działa tak, jak myślisz.

Karl Bielefeldt
źródło
3

Ostrzeżenie, nic nie wiem na ten temat.

Szybkie spojrzenie na Wikipedię wydaje się wskazywać, że Ortogonalność jest głównie ukierunkowana na wzorce projektowe i projektowanie systemów. Jeśli chodzi o języki programowania, pozycja wskazuje, że zestawy instrukcji są ortogonalne, jeśli istnieje jedna i tylko jedna instrukcja dla każdej możliwej akcji, a raczej żadna instrukcja nie nakłada się na drugą.

W przypadku C # wyobrażam sobie, że jest on ortogonalny, ponieważ większość sztuczek składniowych ( foreachprzychodzi na myśl) to po prostu nakładki na specjalnie utworzone wersje podstawowej konstrukcji ( foreachstają się forpętlami). Ogólnie rzecz biorąc, język naprawdę obsługuje robienie rzeczy tylko w jeden sposób, mimo że cukier składniowy zapewnia dodatkowe sposoby ich wykonywania. I na koniec, wszystko się kompiluje do MSIL(lub jak to się obecnie nazywa) i MSILprawdopodobnie jest ortogonalne.

Jeśli zrobisz zastrzeżenie, że syntaktyczny materiał cukrowy jest zasadniczo „opakowaniem” wokół robienia tego w „trudny sposób”, możesz przeanalizować różne cechy języka, pomijając cukier, i sprawdzić, czy są jakieś konstrukcje, które naprawdę się pokrywają. Jeśli nie, wyobrażam sobie, że możesz zadeklarować język jako ortogonalny.

Moje dwa centy.

digitlworld
źródło
Myślę, że jeśli zarówno forach, jak i foreach są cechami języka, podczas gdy jeden jest składniowym cukrem drugiego (gdzie efekty foreach można osiągnąć za pomocą dla), język traci tam swoją ortogonalność.
vpit3833
Nie do...whilemożna użyć, aby zapewnić taki sam efekt jak for? Nigdy nie słyszałem o żadnym z nich jako o cukrze syntaktycznym.
Matthew Flynn
1
@MatthewFlynn: Bah! Są ZARÓWNO cukrem syntaktycznym, możesz po prostu zastąpić swoją iterację funkcją rekurencyjną! ;)
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner: Czy to nie tylko cukier syntaktyczny dla GOTO?
Ivan
2
@MatthewFlynn do whilegwarantuje wykonanie pojedynczej pętli i sprawdza stan po fakcie. fornajpierw sprawdza warunek i nie gwarantuje pojedynczego wykonania.
digitlworld
2

Moje pytanie brzmi: w jaki sposób mogę przejść do pozostałych funkcji, szczególnie tych, które nie są ze sobą powiązane?

Kontynuujesz robienie tego, co robisz, wyliczając wszystkie kombinacje, które działają lub są zabronione.

To wszystko. Jest to dość bolesne.

Czy wszystkie funkcje muszą ze sobą współistnieć?

Jeśli wszystkie funkcje można podzielić na rozłączne podzbiory, które nie kolidują ze sobą, to na pewno wszystko byłoby rozsądne.

Wszystkie struktury danych działają ze wszystkimi typami pierwotnymi. Wszystkie operatory wyrażeń działają ze wszystkimi typami. Są to powszechne definicje ortogonalności. Ale możesz chcieć więcej (lub mniej)

Czasami zdarzają się jednak przypadki szczególne z powodu systemów operacyjnych lub starszych bibliotek, które nie są ortogonalne.

Ponadto niektóre typy nie są w ogóle bardzo zgodne. Na przykład Python pozwala porównać dwa obiekty słownikowe do „porządkowania”. Ale nie ma prawie żadnej sensownej definicji „porządkowania” wśród słowników. Python definiuje jeden, ale jest dość dyskusyjny. Czy ten szczególny przypadek powoduje, że słowniki nie przejdą testu ortogonalności?

Jak ortogonalny jest „wystarczająco ortogonalny”? Co ty trzeba zobaczyć, aby być szczęśliwym ze stopniem ortogonalności w Twoim języku.

S.Lott
źródło
2

Lista nietypowych funkcji jest rzeczywiście długa w większości języków programowania, np

  • anonimowe klasy konfliktują z java refleksją
  • konflikt usuwania ogólnego i typu z odbiciem Java
  • tablice różnią się nieco od innych obiektów ze względu na swój specjalny typ, mimo że są obiektami.
  • metody statyczne vs. instancyjne nie są takie same, np. nie można przesłonić metody statycznej
  • klasa zagnieżdżona to następcza myśl
  • wpływ dynamicznego i statycznego pisania na strategię wysyłania wiadomości (patrz np. ten przypadek na krawędzi w C #)
  • itp.

To tylko kilka, które przychodzą mi na myśl, ale jest wiele innych, a także w innych językach.

Trudno zapewnić, aby nie występowały subtelne zakłócenia między funkcjami językowymi. Jak wskazuje CAR Hoare w swoim artykule „Wskazówki dotyczące projektowania języka programowania”:

Część projektowania języka składa się z innowacji. To działanie prowadzi do nowych funkcji językowych w oderwaniu. Najtrudniejsza część projektowania języka polega na integracji : wybranie ograniczonego zestawu funkcji językowych i dopracowanie ich do momentu uzyskania spójnego prostego frameworka, który nie ma żadnych ostrych krawędzi.

Prawdopodobnie dobrym sposobem na zwiększenie ortogonalności jest ujednolicenie pojęć (co idzie w kierunku odpowiedzi @ karl-bielfeld). Jeśli wszystko jest, powiedzmy lista lub obiekt, istnieje prawdopodobieństwo, że konfliktów będzie mniej. Lub zamiast zagnieżdżać klasę po przemyśleniu, uczyń ją podstawową cechą.

Większość dokumentów dotyczących języków programowania wykazuje pewne właściwości języka (np. Poprawność tekstu) w podzbiorze („rdzeniu”) sformalizowanego języka. Tutaj powinniśmy zrobić odwrotnie, udowodnić, że wszystkie funkcje komponują się bezpiecznie. Oznacza to również, że należy zdefiniować, co to znaczy „komponować”. Czy to znaczy „biegać”? (W tym przypadku powyższy link dotyczący wielkości krawędzi z dynamicznym i statycznym pisaniem jest bezpieczny). Czy to znaczy być „bezpiecznym”? Czy oznacza to przewidywalność z punktu widzenia dewelopera?

Wszystko to jest bardzo interesujące - ale także bardzo trudne.

ewernli
źródło