Miara mocy innej niż kompletność Turinga

18

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?

Casebash
źródło

Odpowiedzi:

24

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.

Macneil
źródło
Dziękuję Ci bardzo! Właśnie tego szukałem!
Casebash
6

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.

Timwi
źródło
Powiedziałbym, że pomiar czasu jest również subiektywny. Który programista poświęcił czas? Jeśli testujesz czasy obu języków za pomocą tego samego programisty, to który język znał lepiej? Istnieją statystyczne sposoby poradzenia sobie z tym, ale osoba nie mogłaby tego zrobić sama.
John Fisher
1
@John: To, że coś można analizować tylko statystycznie, nie oznacza, że ​​jest to subiektywne.
David Thornley,
@David: Nie o to mi chodziło. Chodziło o to, że bez wcześniejszych badań pytający nie byłby w stanie porównać „potęgi” języków, na których mu zależało - pozostawiając je subiektywne, gdy nie były analizowane statystycznie w dużej grupie.
John Fisher
1

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.

Mason Wheeler
źródło
2
Trudność polega na tym, że znajomość języka ułatwia ten, kto go zna. Tak więc ta miara staje się subiektywna.
John Fisher
1

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ą.

Stephen C.
źródło
1
Wiem, że kompletność Turinga polega na obliczalności. Wiemy, że istnieją mniejsze miary skali obliczalności, takie jak maszyny stanów skończonych. Ale nie możemy użyć obliczalności do zdefiniowania poziomu mocy powyżej tego, ponieważ kompletność Turinga jest maksymalnie potężna pod względem obliczalności
Casebash
@Casebash - wciąż nie powiedziałeś, czym jest „moc”.
Stephen C
2
To dlatego, że nie wiem i to jest sedno tego pytania!
Casebash,
Jaki jest sens twojej odpowiedzi? To powinien być komentarz.
reinierpost
@reinerpost - Celem mojej odpowiedzi jest szczegółowe wyjaśnienie, że pytanie jest bez znaczenia i dlaczego. Zasadniczo pytanie brzmi: „Istnieje coś, co nazywa się„ mocą ekspresyjną ”- nie wiem, co to jest, ale czy możesz mi powiedzieć, jak to zmierzyć”. A sednem mojej odpowiedzi jest to, że „moc ekspresyjna” jest źle zdefiniowanym pojęciem / właściwością, a na pewno NIE jest wymierna / kwantyfikowalna. (I to jest wyraźnie odpowiedź, a nie komentarz. Być może po prostu nie zrozumiałeś, co próbuję powiedzieć?)
Stephen C