Czy możesz podać język programowania bez implementacji?

11

Czy teoretycznie jest możliwe określenie języka programowania, dla którego nie byłoby możliwe wdrożenie? Język programowania to sposób definiowania funkcji. Implementacja oznacza metodę wykonania danego programu w tym języku na danym wejściu na wyjściu funkcji odpowiadającej programowi na tym wejściu.

Jakie są minimalne wymagania takiego języka?

formal-languages computability programming-languages

— Kaveh
źródło

3

Co to jest „implementacja” języka?

— Raphael

@Raphael: To ty zmieniłeś „język programowania” na „język”. Przed edycją było jasne, co oznacza implementacja języka.

— Tsuyoshi Ito

@TsuyoshiIto: Niezupełnie; Dostosowałem tylko tytuł, aby pasował do pytania, które zostało zmienione na cstheory.SE. Zmieniłem to z powrotem, ale nadal nie jest jasne, co to znaczy. Kompilator? Tłumacz? W każdym razie, migrując tutaj pytanie, które ma prawie rok, i przez użytkownika, który najwyraźniej nigdy nie wrócił do pytania, w najlepszym razie było to niewskazane.

— Raphael

@Raphael: Pytanie „co to jest implementacja języka?” po usunięciu wszystkich wskazówek było po prostu poza moim zrozumieniem. Ale zgadzam się, że pytanie od początku było niejasne.

— Tsuyoshi Ito,

Myślę, że twoja domniemana definicja „języka programowania” jest źle rozumiana. Należy to przynajmniej zmienić, zastępując „funkcje” przez „funkcje obliczalne”. W przeciwnym razie nie jest jasne, dlaczego miałbyś nazywać ten język „językiem programowania”. Po jego zmianie pytanie staje się pozbawione sensu, ponieważ nie ma takich „języków programowania, dla których nie byłoby możliwe wdrożenie”.

— Uday Reddy

7

Zazwyczaj implementacja języka programowania daje przynajmniej tłumacza w języku (lub kompilatorze języka), który nie jest niczym więcej niż ukończeniem Turinga.

Korzystając z tej „definicji” możemy określić język programowania taki jak ten:

istnieje tylko jeden możliwy program HALT;
specyfikacja HALT: jest to funkcja, która rozwiązuje problem zatrzymania .

Implementacja tego języka programowania wymaga rozwiązania problemu zatrzymania przy implementacji. (Co jest niemożliwe, ponieważ nasza implementacja nie powinna być mocniejsza niż maszyna Turinga).

Specyfikacja obsługuje logikę i dlatego może prosić o wiele więcej. Inną specyfikacją, której wdrożenie będzie niemożliwe, jest „fałsz”. (Lub dowolne sprzeczne zdanie w specyfikacji) Ale to nie wydaje się być specyfikacją, dlatego użyłem przykładu problemu zatrzymania.

— jmad
źródło

1

Uogólniony: Dowolny język, który określa funkcję rozwiązującą nierozstrzygnięty problem, nie może zostać zaimplementowany.

— edA-qa mort-ora-y

@ edA-qamort-ora-y Technicznie można to zaimplementować. Nie możesz zdecydować o problemie z zatrzymaniem, ale TM może symulować inną maszynę i zaakceptować, jeśli maszyna się zatrzyma; język akceptowany przez taką bazę TM jest dokładnie językiem (kodowania) maszyn, które się zatrzymują. Ale ze względów praktycznych zwykle lubimy prymitywne operacje języków programowania, aby zagwarantować ich zakończenie! (przynajmniej na „rozsądnym” wejściu)

— Ben

1

Tak, funkcje języka powinny mieć złożoność czasową mniejszą niż

:)

O (\infty)

$O(∞)$

— edA-qa mort-ora-y

@ edA-qamort-ora-y nie zawsze jest to prawdą. Na przykład w semantyce denotacyjnej Haskella 1/0

a zatem jest

w modelu kosztu oczywistego. W praktyce wszystkie implementacje Haskell rozróżniają wyjątek i rozbieżność, a GHC ma określoną semantykę operacji, która wyjaśnia, jak powinny działać wyjątki. Ale możliwe byłoby posiadanie zgodnej implementacji, która zapętlałaby się na zawsze przy dzieleniu przez zero!

\equiv

$\equiv$ let loop = loop in loop

Ω (\infty)

$\Omega(\infty)$

— Philip JF

3

Ciekawa uwaga: silnik szablonów C ++ jest kompletny w Turingu

Twierdzenie 1: W przypadku braku granic tworzenia szablonów szablony C ++ są kompletne według Turinga.

Konsekwencją 1: W przypadku braku limitów tworzenia instancji, czy kompilator C ++ zatrzyma się podczas kompilacji danego programu, jest nierozstrzygalny.

... więc sam C ++ można uznać za język programowania, dla którego nie może istnieć „implementacja” ... :-D

— Vor
źródło

Czy więc „kompilator” C może być używany jako interpreter, jeśli nie obchodzi go wygenerowany kod, a jedynie wygenerowana diagnostyka?

— supercat

Tak, jak pokazano w artykule, kompilator zatrzymuje się z listą błędów, które pasują do historii obliczeń maszyny Turinga (i jej końcowej konfiguracji taśmy). Oczywiście dane wejściowe nie mogą być interaktywne (muszą zostać zakodowane w kodzie źródłowym przed uruchomieniem kompilatora).

— Vor

2

Nie jest jasne, co rozumiesz przez „język programowania” i „implementację języka”. Musisz podać rygorystyczne definicje tych dwóch, aby uzyskać odpowiedź.

$\Sigma^*$ $2^{\Sigma^*}$

$M$ $M$ $0$

Ale nie jest to język specyfikacji, który ludzie mają na myśli, gdy używają wyrażenia „język programowania”. Język programowania jest zazwyczaj rozumie się język do wyrażania funkcje obliczalne (procesy, ...) i do komunikowania się z instrukcjami do maszyny, a zatem nie jest TM, które może symulować te swoje programy i wyjście ich wyników. W pewnym sensie posiadanie języka programowania, którego nie można wdrożyć, nie ma znaczenia.

(Domyślam się, że prawdopodobnie mylisz języki programowania z językami specyfikacji lub językami formalnymi . W każdym razie możemy zdefiniować języki, które nie są obliczalne.)

— Kaveh
źródło

Jestem prawie pewien, że „język programowania” oznacza język programowania w taki sposób, w jaki normalnie o nim mówimy, a „implementacja języka” oznacza środowisko do wykonywania programów w tym języku na prawdziwych komputerach. Pytanie nie jest sformalizowane , ale na pewno nie jest niejasne? Mogę łatwo napisać specyfikację dla nowego języka programowania, nie zawracając sobie głowy jego implementacją; pytaniem jest po prostu pytanie, czy można to zrobić w taki sposób, aby język nie mógł zostać zaimplementowany.

— Ben

@ Ben, jeśli spojrzysz na oryginalne pytanie w cstheory, zobaczysz, że nie ma programowania słownego w pytaniu tylko w tytule. Pytanie zadane przez OP jest zdecydowanie jasne. ps: Byłbym zainteresowany rygorystyczną (nie musi być formalną) definicją języka programowania. Nie możemy udowodnić negatywnych wyników dotyczących języków programowania wyłącznie na podstawie intuicji i przykładów. Jeśli masz odniesienie do definicji, opublikuj ją jako edycję lub komentarz do pytania.

— Kaveh

W porządku, chociaż SE twierdzi, że odpowiedziałeś na nie 9 godzin temu, długo po migracji i edycji. Zresztą i tak dokonałbym tej samej interpretacji na podstawie pierwotnego pytania. Jeśli chodzi o definicję języka programowania, powiedziałbym, że oczywistym jest gramatyka formalna plus albo redukcja do innego dobrze rozumianego modelu obliczeniowego (rachunek lambda, maszyna Turinga itp.), Albo rygorystyczna semantyka operacyjna. Model redukcji uczyniłby odpowiedź na to pytanie banalnym „nie”, oczywiście.

— Ben

1

Podano wiele języków bez implementacji, np. Algol 60 miał być językiem do pisania algorytmów, a nie do implementacji. Niektóre z wielu języków „tylko dla zabawy” zostały określone na długo przed nadejściem implementacji, przychodzi mi na myśl Intercal.

— vonbrand
źródło