Miara mocy innej niż kompletność Turinga

Początkowo próbowałem zadać to pytanie na StackOverflow, ale było to zbyt subiektywne :-(. Interesują mnie metody definiowania mocy języków programowania. Turing jest kompletny, ale jest prawie uniwersalnie zadowolony. To, co byłoby miłe, to zdefiniować miara mocy, która rozróżnia faktycznie używane języki programowania. Czy na przykład ktoś może zaproponować nie subiektywną metodę, która rozróżniałaby między asemblerem a Javą?

Kompletność Turinga oznacza, że ​​język jest maksymalnie potężny w tym, co potrafi wydobyć (co właściwie oznacza, że ​​potrafi robić wszystko poza czasem w prawdziwym świecie). Więc jeśli chcemy zdefiniować silniejszą miarę siły, musimy przyjąć inne podejście. W pierwotnym pytaniu zasugerowano zwięzłość, ale wcale nie jest to łatwe do zdefiniowania. Czy ktoś ma jakieś inne propozycje?

Pojęcie, którego szukasz, nazywa się ekspresyjnością, a Matthias Felleisen ma matematycznie rygorystyczną definicję:

„ O ekspresyjnej sile języków programowania ”

www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz (wersja Postscript)

Intuicja leżąca u podstaw tego pomysłu jest taka, że ​​jeśli masz dwa równoważne programy w dwóch różnych językach - powiedzmy, program A w języku X i program B w języku Y - i jeśli wprowadzisz lokalną zmianę na A, która wymaga globalnej zmiany na B , to X jest bardziej wyrazisty niż Y.

Jednym z przykładów dostarczonych przez Felleisen jest przypisanie: W językach programowania schematu można usunąć operatora przypisania i nadal mieć kompletny język Turinga. Jednak w tak ograniczonym języku dodanie funkcji, która byłaby zlokalizowana, gdyby przypisanie było dozwolone, wymagałaby globalnej zmiany w programie bez przypisania.

Moja dyskusja uprościła niektóre szczegóły i powinieneś przeczytać sam artykuł na pełne konto.

Aby odpowiedzieć na inne pytanie: Możesz powiedzieć, że Java jest bardziej ekspresyjna niż asembler, ponieważ możesz dodać nową klasę do swojego programu Java, a następnie zyskać zalety polimorfizmu poprzez wywołanie innych części programu bez globalnej modyfikacji. Obsługa wyjątków jest kolejnym przykładem, w którym Java jest bardziej ekspresyjna niż asembler: wystarczy napisać pojedynczą throwinstrukcję, aby przenieść kontrolę na stos. Na bardziej elementarnym poziomie możesz również dodać nowe casezdanie na początku litery A switchi nie będziesz musiał martwić się o ręczne przeliczanie przeskoków skoku.

Jeśli dobrze rozumiem twoje pytanie, mimo to szukasz czegoś, co jest względnie mierzalne, a nie tylko subiektywnego osądu. Jeśli tak, osobiście wolałbym poświęcić czas na rozwiązanie konkretnego problemu (uśredniony dla wszystkich problemów i wszystkich programistów). W tym środku może być konieczne uwzględnienie nie tylko samego języka, ale także używanego z nim frameworka / interfejsu API. Zwięzła składnia jest bardzo małym czynnikiem: o wiele ważniejszym jest to, że najczęściej wymagana funkcjonalność jest łatwo dostępna.

Jeśli szukasz czegoś bardziej subiektywnego, powiedziałbym, że to zabawne . Programiści to zazwyczaj ludzie, którzy chcą rozwiązania problemów, więc język programowania, który jest przyjemny dla programistów, nieuchronnie będzie tym, który rozwiąże najwięcej problemów. Środek ten bierze pod uwagę, że różne osoby mają różne preferencje dotyczące sposobu korzystania z rzeczy, więc „najlepszy” język programowania będzie tym, który jest najbardziej atrakcyjny dla najszerszego grona programistów. Być może jednak będziesz musiał wziąć pod uwagę nie tylko język programowania i interfejs API, ale także środowisko (IDE), z czym oczywiście współpracuje programista.

Zdecydowałbym, jak potężny jest język, na podstawie tego, jak wydajna może być przy nim. Wiele osób mówi o produktywności w kontekście szybkiego pisania kodu, ale ponieważ większość cyklu życia programu to konserwacja, a nie programowanie, lepszym miernikiem jest to, jak łatwo można odczytać i debugować kod, zwłaszcza gdy jest on napisany przez kogoś jeszcze. Najpotężniejsze języki to te, które są najłatwiejsze do odczytania i utrzymania.

Musisz lepiej zdefiniować swoją terminologię.

Kompletność Turinga nie polega na „mocy” w takim znaczeniu, jakie prawdopodobnie masz na myśli. Raczej chodzi o obliczalność; tzn. czy dany język może wyrażać dowolny program, który można wdrożyć za pomocą maszyny Turinga. Okazuje się, że prawie każdy język programowania jest kompletny.

To, czego prawdopodobnie szukasz, jest miarą tak zwanej „ekspresyjności” języka programowania. Nie jestem pewien, czy takie środki istnieją, czy też istnieją, czy są przydatne. Zasadniczo różne języki programowania lepiej wyrażają rozwiązania różnych rodzajów problemów.

EDYTOWAĆ

Aby to przeliterować, języki programowania nie mają właściwości znanej jako „moc”. Istnieje koncepcja powszechnie znana jako „ekspresyjność” lub „ekspresyjna moc” języka programowania. Ekspresyjność polega częściowo na tym, jak łatwo jest napisać zwięzłe programy, aby rozwiązać określone problemy. Ale jest też znaczna miara tego, jak łatwo jest czytać i pisać programy. To jest trochę jak „piękno”. Będę wiedział, kiedy to zobaczę, ale nie proś mnie o zdefiniowanie tego.

Samo porównanie liczby znaków nie daje odpowiedniej miary ekspresji. W przeciwnym razie możesz uczynić język bardziej wyrazistym, kompresując kod źródłowy ... i to nonsens. W rzeczywistości nie znam żadnej obiektywnej miary ekspresji i mocno podejrzewam, że nie istnieje. Co skutecznie czyni tę cechę bezużyteczną i dość nieciekawą.