Do czego konkretnie odnosi się moc ekspresji?

Moc ekspresyjna jest definiowana przez Wikipedię jako:

.. szerokość pomysłów, które można przedstawić i przekazać w tym języku.

Czy „pomysły” odnoszą się do rzeczy (operacji, struktur, algorytmów itp.), Które możemy komunikować z maszyną ? Czy też odnosi się do „ludzkich” pojęć, które można uchwycić i komunikować z językiem innym ludziom?

Jak ocenia się i mierzy siłę ekspresji?

Na przykład, jeśli weźmiemy język taki jak JavaScript i narzucimy dziwne ograniczenie nazw zmiennych, takie jak zmienna musi być 8-cyfrową liczbą poprzedzoną podkreśleniem, dopasowaniem/^_[0-9]{8}$/ , czy stracilibyśmy moc ekspresji?

A może byłoby to tylko absurdalne i denerwujące?

Wyjaśnić:

Czy moc ekspresji mierzona jest przez ogólne idee właściwe dla języka:

• liczby całkowite i ciągi
• pętle
• warunkowe

Lub liczba konkretnych , unikalnych pomysłów, które język może reprezentować:

• liczby całkowite 1, 2 ... 2 ^ 32
• ciągi zawierające „co mówi lis?” i „wha pah pah pah pah pah pow”
• dla każdej żaby w mojej kolekcji żab
• jeśli żaba jest zielona lub coś wtedy zrobić coś

Przełomowym artykułem na temat ekspresji jest O ekspresyjnej sile programowania języków autorstwa Matthiasa Felleisena (1991) . Zawiera matematycznie rygorystyczną definicję ekspresji języka.

Intuicyjnie, jeśli każdy program, który można napisać w języku A, można również napisać w języku B z lokalnymi przekształceniami, ale istnieją pewne programy napisane w języku B, których nie można napisać w języku A bez zmiany ich globalnej struktury (tj. Nie tylko czysto lokalne transformacje), a następnie język B jest bardziej wyraziste niż językowej A .

Jedną z przyjemnych właściwości tej definicji jest to, że dopuszcza możliwość istnienia par języków, w których istnieją programy w X, których nie można wyrazić w Y, oraz programy w Y, których nie można wyrazić w X , a zatem języki są różne, ale żadne język jest bardziej wyrazisty niż drugi. To dobrze współgra z naszym doświadczeniem w świecie, że istnieje kilka języków, które są dobre w niektórych rzeczach, a niektóre są dobre w innych rzeczach i żadne z nich nie jest ogólnie „lepsze” niż inne.

Moc ekspresyjna jest definiowana przez Wikipedię jako:

Dajmy tej stronie ponownie. Jedną z pierwszych rzeczy, na które należy zwrócić uwagę, jest to, że mówi „język”, a nie „język programowania”, a większość jego przykładów nie jest językami programowania, np. Pierwszy podany przykład to porównanie OWL2 EL i OWL2 RL, które są zarówno ontologią Języki.

Można zastosować tę koncepcję do języków programowania, ale także do języków, w których używane są wzorce, języki znaczników, języki zapytań, języki do wizualnego arkusza stylów, wyrażenia regularne (i wszystkie języki, do których się odnoszą) i tak dalej. Można nawet odnieść się do ekspresyjnej mocy języków naturalnych, takich jak angielski, co często odbywa się bardzo nieformalnie, ale z większą powagą przy rozważaniu problemów związanych z przetwarzaniem języka naturalnego.

Czy „pomysły” odnoszą się do rzeczy (operacji, struktur, algorytmów itp.), Które możemy komunikować z maszyną? Czy też odnosi się do „ludzkich” pojęć, które można uchwycić i komunikować z językiem innym ludziom?

Odnosi się do tego, co można wyrazić w tym języku, uważanym wyłącznie za rzecz samą w sobie.

Na przykład (użyję javascript w moich przykładach, ponieważ twoje pytanie wskazuje, że jest to jeden z języków, które znasz) rozważ instrukcję javascript:

var x = 3 + 4;

Oznacza to, że obliczana jest suma wartości 3 i 4, a wartość powiązana z etykietą xw danym zakresie przestrzeni nazw.

Gdybyśmy zniszczyli wszystkie komputery na świecie i napisali ten kod na kartce papieru, pozostałoby, że w javascript nadal miałby to samo znaczenie; nie bylibyśmy w stanie uruchomić takiego kodu na niczym, ale abstrakcyjna definicja języka jest nadal czymś, o czym moglibyśmy porozmawiać.

Może się to wydawać pedantyczne, ale w rzeczywistości bardzo ważne jest, aby języki były rozumowane w sposób abstrakcyjny bez uwzględnienia prawdziwych komputerów. Po pierwsze, ludzie myślący o teoretycznych aspektach języków komputerowych, które nie były jeszcze wykonalne w praktyce, są jedną z rzeczy, które doprowadziły nas do tego, gdzie jesteśmy dzisiaj; komputery potrzebują informatyki, ale informatyka nie potrzebuje komputerów, wystarczy idea obliczeń.

Oczywiście korzystamy z komputerów w prawdziwym świecie, a obecnie wiele osób korzysta z nich w praktyce, a nie kilku specjalistów dyskutujących o nich teoretycznie. Strona, do której prowadzisz link, mówi:

Termin moc ekspresyjna może być używany z szeregiem znaczeń. Może to oznaczać miarę pomysłów wyrażanych w tym języku:

• niezależnie od łatwości (teoretyczna ekspresja)

• zwięźle i łatwo (praktyczna ekspresja)

Pierwszy zmysł dominuje w obszarach matematyki i logiki, które dotyczą formalnego opisu języków i ich znaczenia, takich jak formalna teoria języka, logika matematyczna i algebra procesów.

W nieformalnych dyskusjach termin często odnosi się do drugiego zmysłu lub obu. Często dzieje się tak przy omawianiu języków programowania. Podjęto wysiłki w celu sformalizowania tych nieformalnych zastosowań tego terminu

Z tych dwóch zastosowań tego terminu praktyczny wpływ pierwszego dotyczy wyłącznie tego, co można przekazać do komputera.

Drugi odnosi się bardziej do ludzkiego zrozumienia zarówno w czytaniu, jak i pisaniu, chociaż stopień, w jakim to robi, różni się znacznie między zastosowaniami, ponieważ są nieformalne i jako takie nie są ściśle określone.

Na przykład, jeśli weźmiemy język taki jak JavaScript i narzucimy dziwne ograniczenie nazw zmiennych, takie jak zmienna musi być 8-cyfrową liczbą poprzedzoną podkreśleniem, dopasowaniem /^_[0-9]{8}$/, czy stracilibyśmy moc ekspresji?

Zgodnie z formalną definicją nie straciliśmy żadnej mocy ekspresji: jesteśmy ograniczeni do 100 000 000 zmiennych, ale gdybyśmy naprawdę tego potrzebowali, moglibyśmy obejść ten problem, tworząc obiekty przechowujące więcej zmiennych w nowo utworzonej przestrzeni nazw. W związku z tym każdy program napisany dzisiaj w javascript może zostać przepisany w tej nowej formie, więc są równie ekspresyjne.

Zgodnie z nieformalną definicją straciliśmy trochę, ale to, jak bardzo zależy od tego, jak bardzo jesteśmy nieformalni, będzie się różnić, ponieważ ponownie nie możesz powiedzieć, jaka jest „reguła” dotycząca używania nieformalnego. Można powiedzieć, że straciliśmy niewielką ilość, ponieważ programy zawierające ponad 100 000 000 zmiennych w tej samej przestrzeni nazw muszą zostać przepisane poza prostą zamianą. Jeszcze bardziej nieformalne użycie ponownie odnosiłoby się do mentalnego wpływu takich niezgrabnie zmiennych nazw na ludzkie kompleksowe.

Warto również zauważyć, że ludzie nieformalnie rozważą rzeczy, które nie są ściśle częścią języka. Zastanów się nad zmianami w Javascripcie od jego stworzenia do dzisiaj.

Zgodnie z najbardziej formalną definicją ekspresja pozostała niezmieniona; W końcu Turing był kompletny.

Dzięki bardziej nieformalnej definicji stała się znacznie bardziej ekspresyjna w niektórych kwestiach, takich jak manipulacje tablicami, obsługa wyjątków i (być może przede wszystkim) włączenie wyrażeń regularnych. Nie robią nic, czego wcześniej nie można było zrobić w javascript, chociaż często potrafią zrobić coś w kilku wierszach i w ciągu drugiego sekundy wykonania, co zajęłoby kilobajty kodu do napisania w javascript1.0 i długo trwało.

Według znacznie bardziej nieformalnej definicji zmiana od pierwszego użycia javascript w przeglądarkach (możliwość zmiany wartości danych wejściowych formularza, document.writepodczas gdy strona jest najpierw analizowana i przenoszona do nowej lokalizacji lub cofania się w przód lub w historii, ale ładna nic więcej) do tego dzisiaj (możliwość zmiany prawie wszystkiego na stronie, w tym na podstawie danych z wywołań serwera) jest absolutnie ogromna, chociaż większość nie dotyczy javascript, ale modeli obiektowych i stworzonych interfejsów API dostępne, a nie język (np. vbscript w IE korzystał z tych zmian w równym stopniu).

Moim zdaniem, to ostatnie użycie jest tak nieformalne, że tak naprawdę nie jest poprawne, ale taki jest problem z nieformalnymi definicjami.

Według formalnej definicji tak naprawdę wcale nie stała się bardziej ekspresyjna.

Nie sądzę, że zmienne reguły nazewnictwa naprawdę wychwytują to, co rozumie się przez „ekspresywność”. Myślę, że „ekspresja” odnosi się do bardziej fundamentalnych rzeczy. Rozważmy na przykład C # z Linq kontra C # przed Linq. Po dodaniu Linq stało się możliwe pisanie zapytań podobnych do SQL bezpośrednio w języku C #. Jest to o wiele bardziej eleganckie niż poprzednie alternatywy, np. Wstawianie SQL do literałów łańcuchowych, a następnie przekazywanie go do serwera lub iterowanie kolekcji za pomocą „for”.

Innym dobrym przykładem mogą być języki z dziedziczeniem opartym na prototypach. W tych językach można po prostu dodać nowe metody do instancji, a nawet klasy (pod dowolną nazwą, jaką „klasa” może przejść w danym języku ...) w czasie wykonywania. Naprawdę nie możesz tego zrobić w C ++ lub C #. Brakuje im takiego stopnia ekspresji w porównaniu do języków opartych na prototypach. (C # ma koncepcję metod rozszerzenia i można z pewnością powiedzieć, że dodają one ekspresji.)

Jak wspomniano w artykule w Wikipedii, moc ekspresyjna odnosi się do zestawu programów, które można wyrazić w języku. Wszystko, co myślisz o „języku programowania” (JavaScript, LISP, C #, Perl itp.), Jest zasadniczo Turing zakończone, co oznacza, że ​​mogą wyrażać wszystko, co można nazwać „obliczalnym”.

Jednak powinno być całkiem jasne, że wyrażenia regularne nie są tak wyraziste jak zwykły język programowania. Ponadto symbole wieloznaczne powłoki są nieco mniej wyraziste niż wyrażenia regularne.

Wersja SQL z typowymi wyrażeniami tabel jest bardziej ekspresyjna niż wersja bez, ponieważ CTE pozwalają na reprezentowanie zapytań rekurencyjnych, które w innym przypadku byłyby niemożliwe do wyrażenia w SQL.

Istnieje prostszy i bardziej bezpośredni sposób na zrozumienie siły wyrazu, ale najpierw musimy ustalić, co rozumiemy przez języki. Istnieją dwie dziedziny nauki języków: językoznawstwo i automaty. Oba zgodziłyby się co do tego, że język jest zestawem słów (ciągów skończonych) zbudowanych z jakiegoś skończonego alfabetu przy użyciu konkatenacji. Zazwyczaj interesujące języki (przez interesujące, mam na myśli takie języki, które możemy interpretować w użyteczny sposób) mają również zestaw reguł, które określają, które słowa są w danym języku, a które nie. Pamiętaj, że ekspresja może istnieć tylko wtedy, gdy istnieje interpretacja.

Przez interpretację rozumiem istnienie funkcji, która podając słowo w języku wybiera obiekt z pewnego zestawu obiektów (jest to oczywiście dyskusyjne w przypadku języków naturalnych).

Nie daj się jednak zwieść słowu. Program Java to słowo w języku Java (chociaż może obejmować wiele plików zawierających wiele ciągów znaków oddzielonych spacjami).

Używanie tak skomplikowanych języków jak współczesne języki programowania przyniosłoby efekt przeciwny do zamierzonego, aby poradzić sobie z tą stosunkowo prostą koncepcją, dlatego wolałbym zamiast tego używać wzorów matematycznych.

• Zdefiniujmy język A jako wszystkie formuły obejmujące dodawanie liczb całkowitych.

• Zdefiniujmy język B jako język wszystkich formuł obejmujących mnożenie liczb całkowitych.

W obu przypadkach nie zezwalamy na użycie elementu tożsamości. Zatem język A zawiera słowa „1 + 1”, „1 + 2”, „1 + 3”, „2 + 3” i tak dalej. Język B zawiera słowa „2 * 2”, „2 * 3”, „2 * 4”, „3 * 4” i tak dalej. Przypisujemy również zwykłe interpretacje do „*” i „+” (dodawanie liczb całkowitych i mnożenie liczb całkowitych) do odpowiednich symboli. Tak więc interpretacja „1 + 1” to 2, a interpretacja „2 * 2” to 4.

Zauważ teraz, że język A jest ściśle bardziej wyrazisty niż język B, ponieważ w liczbach całkowitych prawdą jest, że mnożenie może być rzutowane jako wielokrotne dodawanie, ale nie ma sposobu, aby reprezentować dodawanie jako mnożenie w ogóle.

Podsumowując: można powiedzieć, że język A jest bardziej wyrazisty niż język B, gdy ich funkcje interpretacyjne dzielą wspólną domenę, ale obraz funkcji interpretacyjnej B jest odpowiednim podzbiorem obrazu funkcji interpretacyjnej A.

TLDR: Jeśli brakuje funkcji, ale można ją wyrazić w inny sposób, nie oznacza to braku ekspresji. Jeśli potrafisz wyobrazić sobie algorytm w głowie, a nawet zaimplementować go w jednym języku, ale inny język jest w jakiś sposób skonstruowany w sposób uniemożliwiający wdrożenie algorytmu, jest to problem z ekspresją *.

Zmienne ograniczenia nazewnictwa nie zmniejszają ekspresji (chyba że jest tak mało nazw, że nie można już wyrazić wszystkich algorytmów i nie można sfałszować zmiennych za pomocą czegoś takiego jak tablice + indeksy).

Prostym przykładem braku mocy ekspresyjnej jest to: Musisz do_homeworki bring_down_trash. Można to łatwo napisać w kodzie:

do_homework();
bring_down_trash();

To rozwiązanie wygląda dość proste, ale w rzeczywistości do_homeworki bring_down_trashsą nieuporządkowane, można również napisać:

bring_down_trash();
do_homework();

Co jest równie nieprecyzyjne, ponieważ nie oznacza, że ​​nie zamierzaliśmy egzekwować zamówienia. Nie chcemy również używać wątków. Chcemy powiedzieć coś takiego:

compiler_or_interpreter_pick_one(
    {
        do_homework();
        bring_down_trash();
    },
    {
        bring_down_trash();
        do_homework();
    }
);

O ile wiem, jest to bardzo trudne do niemożliwego do wyrażenia w dowolnym języku programowania.

Przykładem, który bez końca mnie wkurza, jest to, że w Javie nie ma tablicy obiektów. Możesz utworzyć tablicę wskaźników do obiektów, ale która nie ma tego samego układu pamięci (wydajność mówienia).

Biorąc przykład z innej odpowiedzi : C ++ nie obsługuje dodawania metod do klasy lub instancji . To prawda, jednak nie ogranicza to ekspresyjności C ++.

struct Extensible{
    std::vector<std::function<void(Extensible *)>> instanceExtensions;
    static std::vector<std::function<void(Extensible *)>> classExtensions;
};

Jest to klasa, do której można dodawać, usuwać i wywoływać dowolną liczbę funkcji składowych dla instancji i klasy. Technicznie C ++ jest pod tym względem prawdopodobnie bardziej wyrazisty niż języki programowania, które faktycznie obsługują tę funkcję, ponieważ w C ++ możesz wybrać sposób przechowywania funkcji (wektor vs tablica vs lista_w przód).

* Niektóre języki mają brak wyrazistości jako cechy. Zazwyczaj uniemożliwiają pisanie nieskończonych pętli. Może to rozwiązać problem zatrzymania i pozwolić na automatyczne udowodnienie poprawności.