Czy rzeczywiście można mieć „użyteczny” język programowania, który nie jest kompletny w Turingu?

Jeżeli przyjmuje się, że język musi być kompletny Turinga, aby był dobry, to czy rzeczywiście można mieć „użyteczny” język programowania, który nie jest kompletny?

Powinienem wyjaśnić, że chodzi tu raczej o języki programowania w tradycyjnym znaczeniu, a nie o języki znaczników i zapytań.

Coq , Agda , HOL i ACL2 są bardzo przydatnymi i niezwykle potężnymi językami, chociaż nie są kompletne w Turingu .

Powszechną cechą, która czyni je niekompletnymi, jest fakt, że zawsze można udowodnić zakończenie. Wystarczy bardzo proste ograniczenie: połączenia rekurencyjne są dozwolone tylko na możliwych do udowodnienia strukturalnie mniejszych warunkach. Dlatego, gdy nie jest to możliwe do wykonania tłumacza języka Turinga uzupełniania lub nawet dla języka sama wiele innych przydatnych rzeczy są nadal możliwe, jak kwalifikowanego kompilatora C .

Sądzę, że termin „mini-język” Yegge odnosi się do faktu, że często użyteczne jest używanie języka do konkretnych problemów, w których język nie wymaga kompletności w celu wykonania zadania, a to dotyczy sedna tego, jak bardzo - użyteczne mogą być kompletne języki. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia odpowiada na to bardzo dobrze, zgodnie z tym, co powiedział mój brzuch. Najpierw myślałem o czystej matematyce, a potem przypomniałem sobie o wyrażeniach regularnych, a Wikipedia wymienia Epigram, który moim zdaniem byłby w stylu „czystej matematyki”.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Języki niekompletne

Istnieje wiele języków obliczeniowych, które nie są kompletne w Turingu. Jednym z takich przykładów jest zestaw języków regularnych, najczęściej wyrażeń regularnych, które są generowane przez automaty skończone. Potężniejszym, ale wciąż niepełnym rozszerzeniem automatów skończonych Turinga jest kategoria automatów wypychających i gramatyk bezkontekstowych, które są powszechnie używane do generowania parsowania drzew w początkowej fazie kompilacji programu. Dalsze przykłady obejmują niektóre wczesne wersje języków modułu cieniującego piksele osadzone w rozszerzeniach Direct3D i OpenGL, lub szereg formuł matematycznych w arkuszu kalkulacyjnym bez cykli. [Potrzebne źródło] We wszystkich funkcjonalnych językach programowania wszystkie funkcje są całkowite i muszą zakończyć, na przykład Charity i Epigram. Organizacja charytatywna wykorzystuje system typów i konstrukcje kontrolne oparte na teorii kategorii,

Języki danych

Pojęcie kompletności Turinga nie ma zastosowania do takich języków, jak XML, JSON, YAML i wyrażenia S, ponieważ są one zwykle używane do reprezentowania danych strukturalnych, a nie opisywania obliczeń. Są one czasami określane jako języki znaczników, a dokładniej jako „języki opisu danych”.

Wspomina również, że reprezentacje struktury danych nie są językami, ale sądzę, że XSLT powinien liczyć się jako reprezentacja obliczeń, XPath może nie opierać się na tym, co powiedział Yannis o SQL jako języku zapytań, a nie języku obliczeń. Być może T-SQL lub PL / SQL liczą się jako języki obliczeniowe, ponieważ można wykonać wiele obliczeń przy użyciu ich agregatów, gdzie uogólniona forma SQL może nie określać agregatów.

Rozumiem, że SQL jest dość popularny wśród typów biznesowych

Kompletność Turinga jest niezbędna, aby język mógł być używany jako język ogólnego przeznaczenia. Ale to nie wystarcza , tj. Tylko dlatego, że jest kompletne Turinga, nie nadaje się do każdej problematycznej dziedziny:

• Udowodniono, że biała spacja jest kompletna, ale w oczywisty sposób nie nadaje się do żadnej problematycznej dziedziny poza rozrywką dla programistów.
• Udowodniono, że szablony C ++ są kompletne, ale tak naprawdę nigdy nie napisałbyś z nimi całych programów.

I odwrotnie, DSL jest odpowiedni dla problematycznej dziedziny, dla której został zaprojektowany (zakładając, że został właściwie zaprojektowany), nawet bez kompletności Turinga:

• HTML ^* zapewnia zwięzły sposób opisu drzewa DOM. Chociaż JavaScript jest w pełni ukończony i można go używać do tego samego, jest o wiele głośniejszy i niejasny
• XPath i inne języki zapytań, PCRE bez osadzonego kodu i takie są potężnymi narzędziami do pojedynczego zadania, dla którego zostały zaprojektowane

^* IIRC udowodniono, że HTML z animacjami CSS jest w pełni Turinga, wykorzystując je do implementacji Gry życia Conwaya na szeregu pól wyboru. Ale przydatność HTML-u utrzymuje się nawet w przeglądarkach, które nie obsługują animacji CSS.

W rzeczywistości istnieją języki programowania, w których można pisać tylko „wydajne” programy. Wydajny w tym sensie oznacza, że ​​każdy program napisany w takim języku reprezentuje język P. Bellantoni, Niggl i Schwichtenberg opisują tutaj taki język .

Preprocesor C nie jest Turing-complete (z założenia), ale wciąż może implementować interpreter dla języka, który jest Turinga kompletny (Zamówienie języka, jak opisano w dokumentacji, jest w zasadzie tylko zbiorem frezować czysto funkcjonalny program typu ML / Scheme i byłby stosunkowo mało znaczący - prawdopodobnie całkiem przyjemny w użyciu - gdyby nie nietypowa implementacja).

Trik za tym jest podobny do argumentów powyżej dotyczących implementacji dowolnej maszyny Turinga w skończonym fizycznym wszechświecie: preprocesor C nie może zapewnić nieskończonej liczby kroków lub komórek danych dla języka, ale może:

1. zapewnienie bezzasadnie dużą liczbę dynamicznego (2 ^ 64 lub tak domyślnie), wystarczająco duży dla rozwiązywania problemów przy użyciu najbardziej realistyczny gwałtowny proces ekspansji ( bełkot bełkot dożywotnią wszechświata Mumble ).

2. użyj dowolnego statycznego ograniczenia dla powyższej liczby, tzn. chociaż liczba kroków musi być pewną liczbą skończoną, możesz zmienić to, co jest określone ograniczenie w czasie „kompilacji”, zmieniając ustawienia statyczne silnika interpretera. Ponieważ nie ma (teoretycznego) ograniczenia rzeczywistej wartości tego ograniczenia, można (teoretycznie) rozszerzyć, aby pasował do miejsca wymaganego przez dowolny program kończący.

Nie twierdząc, że Order jest koniecznie sam w sobie „użyteczny”, lub że jakikolwiek silnik implementowany przez CPP byłby, ale jest to ciekawy dowód koncepcji. Jest również podobno dynamicznie wpisywany , co jest niezwykłe w tym obszarze.

Tak, w rzeczywistości możliwe jest posiadanie przydatnego języka, który nie jest kompletny w Turingu. Zobacz tutaj: http://tkatchev.bitbucket.org/tab/examples.html

Innym przykładem przydatnego niekompletnego języka Turinga jest SQL. (A jeszcze innym są arkusze kalkulacyjne, takie jak Gnumeric lub Excel, chociaż tak naprawdę nie są to języki programowania).

Co do tego, dlaczego chcesz mieć język, który nie jest kompletny w Turingu: ponieważ pozwala to na pewne mocne gwarancje dotyczące zachowania w czasie wykonywania.

Mówiąc wprost, kompletność Turinga oznacza zdolność do rekurencji. Posiadanie rekurencji oznacza posiadanie potencjalnie niezwiązanych struktur w pamięci. Ponieważ w prawdziwym świecie pamięć nie jest nieskończona, kompletność Turinga wymaga zarządzania pamięcią i / lub wyrzucania elementów bezużytecznych.

Zakaz rekurencji to świetny sposób na uniknięcie naprawdę trudnego problemu zarządzania zasobami.

Nota bene! Niekompletność Turinga niekoniecznie oznacza, że ​​jakikolwiek program musi się zakończyć. Niekompletny język Turinga może umożliwić ocenę nieskończonej leniwej listy.

Do tej pory wspomniano o jednym interesującym „języku programowania sub-Turinga”, więc go dodam.

Nazywa się to „Crema” . Opisuje się jako:

Crema to front-end LLVM, którego celem jest specyficzne wykonanie w przestrzeni pod Turinga Complete. Zaprojektowany jako prosty do opanowania i praktyczny dla większości potrzebnych zadań programistycznych, Crema może ograniczyć złożoność obliczeniową programu do minimum niezbędnego do poprawy bezpieczeństwa.

To dość minimalistyczny i raczej niski poziom.

Powinien wyglądać znajomo dla programistów C.

Został początkowo sfinansowany przez Agencję Obrony Zaawansowanych Projektów Badawczych (DARPA), ale w chwili pisania tego tekstu wygląda na zupełnie nieokreślony. Ale może jednak ktoś jest zainteresowany.