Czy są dziś dostępne główne, uniwersalne języki inne niż Turinga?


12

Języki niekompletne Turinga oferują dużą przewagę nad językami kompletnymi bez Turinga, ponieważ są one znacznie bardziej analizowalne, a tym samym oferują znacznie szersze możliwości optymalizacji. Jednak są one rzadko używane, a kompletność Turinga jest sprzedawana jako dobra cecha.

Czy są dostępne obecnie główne języki niekompletne, które są przeznaczone do programowania ogólnego?


8
Myślę, że dwie rzeczy, których szukasz, są wzajemnie niezgodne. Jeśli nie jest ukończony, nie można go zmienić na dowolny sposób.
Bobson

@Dokkat Ponownie otworzyłem pytanie i usunąłem dyskusję Meta z komentarzy. Pamiętaj, że jeśli nie zgadzasz się z jedną z wytycznych witryny, właściwym sposobem jej zakwestionowania jest opublikowanie dyskusji Meta; nie tylko to ignoruj. Ponadto w przypadku subiektywnych pytań kluczem do sukcesu są wcześniejsze badania i rygorystyczna definicja. Im więcej badań, tym bardziej konkretne (i możliwe do udzielenia odpowiedzi) staje się twoje pytanie, a im dalej znajdujesz się od znanej „niekonstruktywnej” przestrzeni.
yannis

Ponadto, dlaczego uważa Pan „szersze możliwości optymalizacji” za „wielką zaletę”? Nie oznacza to, że optymalizacja nie jest opłacalna, ale z pewnością nie nazwałbym wrodzonej możliwości optymalizacji języka „wielką zaletą”, biorąc pod uwagę moc nowoczesnych komputerów.
Bobson

2
Coq można uznać za „główny nurt” w swojej dziedzinie, a konkurenci (HOL, Agda, ACL i inni) są znacznie mniej widoczni.
SK-logic

Być może tak naprawdę nie rozumiem, czym jest kompletność Turinga , ale jak język może być uniwersalny, a nie Turing pełen? Myślałem, że sens bycia nie-Turingiem jest kompletny, nie jest w stanie wykonać żadnego zadania obliczeniowego, a więc być ukierunkowanym na konkretny cel ..?
Aviv Cohn

Odpowiedzi:


24

Obecnie nie ma uniwersalnych, uniwersalnych, niekompletnych języków Turinga. Istnieje jednak kilka kompletnych języków specyficznych dla domeny. ANSI SQL, wyrażenia regularne, języki danych (HTML, CSS, JSON itp.) Oraz wyrażenia s to niektóre godne uwagi przykłady.

Tak naprawdę nie ma korzyści dla wielofunkcyjnych pełnych języków Turinga. Stosuje się aspekt „znacznie bardziej analizowalny”, który, jak zakładam, stanowi ukłon w stronę twierdzenia Rice'a, ale nie ma większego sensu w przypadku języków, które są ukierunkowane na kilka różnych domen aplikacji, inne wymagania mają pierwszeństwo. Elastyczność kompletności Turinga jest o wiele ważniejsza niż jej złożoność. Języki programowania, jak każde inne oprogramowanie, dotyczą kompromisów.

Z drugiej strony w przypadku języków specyficznych dla domeny może być odwrotnie. Jeśli nie budujesz „jednego języka, aby rządzić nimi wszystkimi”, możesz zaimplementować tylko te funkcje, które mają sens dla bardzo konkretnego celu twojego języka. I najczęściej kompletność Turinga nie jest jedną z nich.


CSS3 jest kompletny w Turingu.
SK-logic

5
@ SK-logic CSS ma sens bez HTML, może być stosowany do dowolnego rodzaju XML i nic nie stoi na przeszkodzie, aby wdrożyć go dla dowolnego innego formatu o z grubsza kompatybilnym kształcie (drzewa o nazwanych węzłach, kolejności rodzeństwa itp.). Osobiście napisałem reguły CSS dla pliku SVG. Jest o wiele bardziej powszechny w HTML, ponieważ HTML jest znacznie bardziej powszechny niż inne formaty.

2
@ Mike, to zepsuta analogia. Semantyka CSS3 jest ściśle związana z semantyką języka prezentacji.
SK-logic

2
Zauważ, że SQL z Windowing i CTE (tj. SQL: 2003) jest również Turing-complete.
Jörg W Mittag,

1
„Obecnie nie ma uniwersalnych, uniwersalnych, niekompletnych języków Turinga”. - C bez pamięci zewnętrznej nie jest kompletny z Turinga, ale jest bardzo ogólny i główny nurt. (Cóż, osobiście twierdziłbym, że jest to język specyficzny dla domeny do pisania jądra uniksowego i nawet nie jest w tym szczególnie dobry, ale świat się nie zgadza.)
Jörg W Mittag

-3

Powodem, dla którego niekompletne języki Turinga nie są głównym nurtem, jest to, że łatwo jest zaimplementować własny, kiedy tylko jest to potrzebne i jakkolwiek jest to potrzebne. Ciekawym przykładem jest skrypt bitcoin: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp


5
Naprawdę? Zastanów się nad wdrożeniem Coq od zera, jeśli to takie proste?
SK-logic

czy to tylko Twoja opinia, czy możesz jakoś to zrobić?
komara

Przykładami są wszystkie języki specyficzne dla domeny, które nie wymagają rekurencji, nieograniczonej iteracji ani innych plandek Turinga. Jestem też pewien, że większość z nas wdrożyła jakiś prosty kalkulator przetwarzający podstawową arytmetykę.
MauganRa,

1
Zgadzam się jednak, że utrzymanie języka Turinga jako niekompletnego nie jest trywialne. Nawet bez oczywistych plandek Turinga zawsze może zawierać błąd kompilatora, który umożliwia korzystanie z jednej z podstawowych platform.
MauganRa,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.