Napotkałem dziwny problem podczas pisania interpretera, który (powinien) zaczepia się o zewnętrzne programy / funkcje: Funkcje w „C” i „C ++” nie mogą przechwytywać funkcji variadic , np. Nie mogę utworzyć funkcji, która wywoła „printf” z dokładnie tymi samymi argumentami, które otrzymał, i zamiast tego musi wywołać alternatywną wersję, która przyjmuje obiekt variadic. Jest to bardzo problematyczne, ponieważ chcę być w stanie wykonać obiekt z anonimowym hakiem.

Pomyślałem więc, że to dziwne, ponieważ Forth , JavaScript i być może mnóstwo innych języków może to zrobić bardzo łatwo, bez konieczności uciekania się do języka asemblera / kodu maszynowego. Skoro inne języki potrafią to zrobić tak łatwo, czy to oznacza, że ​​klasa problemów, które każdy język programowania może rozwiązać, różni się w zależności od języka, nawet jeśli wszystkie te języki są w Turingu kompletne ?

Turing pełne języki mogą obliczyć ten sam zestaw funkcji , który jest zbiorem ogólnych rekurencyjnych funkcji cząstkowych. Otóż ​​to.$\mathbb{N}^k \rightarrow \mathbb{N}$

To nic nie mówi o funkcjach językowych. Maszyna Turinga ma bardzo ograniczone właściwości kompozycyjne. Bez typu -calculus jest znacznie bardziej kompozycyjny, ale brakuje mu wiele cech powszechnie spotykane w nowoczesnych językach.$\lambda$

Kompletność Turinga nie mówi nic o posiadaniu typów, wbudowanych tablicach / liczbach całkowitych / słownikach, możliwościach wejścia / wyjścia, dostępu do sieci, wielowątkowości, alokacji dynamicznej, ...

Tylko dlatego, że Java nie ma funkcji X (powiedzmy makr, typów wyższej rangi lub typów zależnych), nie przestaje nagle być ukończonym Turingiem.

Kompletność Turinga i ekspresja językowa to dwa różne pojęcia.

Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga.

Nie oznacza to jednak, jak wygodne jest to zrobić. Niektóre funkcje, które są łatwe w niektórych językach, mogą być bardzo trudne w innych, ze względu na wybór projektu. Kompletność Turinga po prostu mówi, że można wykonać obliczenia. Jako skrajny przykład może być trudne zaczepienie funkcji varadycznych w C ++, ale możliwe jest napisanie interpretera JavaScript w C ++, który może zaczepić funkcje variadic.

Projektowanie języka jest dość interesującą sztuką. Jednym z głównych kroków, które należy podjąć, jest określenie, jakie zachowania mają stanowić kręgosłup twojego języka. Te zachowania są łatwe do zrobienia w twoim języku, ponieważ są wbudowane w parter. Podejmujemy decyzje projektowe dotyczące tego, które funkcje należy uwzględnić w każdym języku.

Jeśli chodzi o twój konkretny przykład, kiedy C został opracowany, został zaprojektowany tak, aby działał bardzo blisko sposobu, w jaki działały języki asemblera dnia. Funkcje variadic po prostu wypychały argumenty na stos, z bardzo małym bezpieczeństwem typów. Wdrożenie tych różnych funkcji pozostawiono kompilatorowi, aby zapewnić maksymalną przenośność. W związku z tym poczyniono bardzo niewiele założeń dotyczących możliwości sprzętu. Zanim pojawił się JavaScript, scena się zmieniła. Działa już na maszynie wirtualnej jako język interpretowany, więc równowaga przesuwa się w kierunku wygody. Umożliwienie łączenia funkcji różnorodnych staje się rozsądne. Nawet w przypadku JavaScript, który jest kompilowany Just In Time, nasze kompilatory są skłonne przechowywać znacznie więcej dodatkowych informacji na temat argumentów niż kompilatory C z przeszłości.

Pomyśl o językach programowania jako o różnych pojazdach lądowych: rowerach, samochodach, poduszkowcach, pociągach.

Turing Completeness mówi: „ten pojazd może jechać wszędzie, gdzie może się udać dowolny pojazd”. Oznacza to, że możesz obliczyć wszystkie te same funkcje. Wejście do wyjścia, od początku do końca.

Ale to stwierdzenie nic nie mówi o tym, jak się tam dostałeś. Może być na szynach, może być na drogach, może być w powietrzu. W ten sam sposób Turing Completeness nic nie mówi o tym , jak obliczasz funkcję. Możesz użyć rekurencji, iteracji lub dziwnych automatów komórkowych. Możesz używać typów lub nie, możesz używać technik dynamicznych lub statycznych. Ale jeśli wszystko, co rozważasz, to funkcje (lub zestawy / języki formalne), które możesz obliczyć, o ile masz Turing Complete, te funkcje dają ci tę samą moc.

W istocie pytasz o różnicę między mocą obliczeniową a tak zwaną potęgą ekspresyjną (lub po prostu ekspresyjnością ) języka (lub systemu obliczeniowego).

Moc obliczeniowa

Moc obliczeniowa odnosi się do jakiego rodzaju problemów język może obliczyć. Najbardziej znaną klasą mocy obliczeniowej jest ta, która jest równoważna z uniwersalną maszyną Turinga . Istnieje wiele innych systemów obliczeniowych, takich jak Random Access Maszyn , X-rachunku , SK combinator rachunku , funkcji ľ-rekurencyjne , WHILEprogramy i wiele innych. Jak się okazuje, wszystkie one mogą się symulować, co oznacza, że ​​wszystkie mają taką samą moc obliczeniową.

Daje to podstawę do Hipoteza Churcha-Turinga (nazwany Alonzo Church , który stworzył X nazębnego i Alana Turinga , który stworzył Universal Turing Machine). Teza Churcha-Turinga jest hipotezą o obliczalności z dwoma aspektami:

1. wszystkie systemy obliczeniowe zdolne do obliczeń ogólnych są równie wydajne, i
2. człowiek postępujący zgodnie z algorytmem może dokładnie obliczyć funkcje, które może obliczyć Maszyna Turinga (a więc każdy inny system).

Drugi jest jednak ważniejszy w dziedzinie filozofii umysłu niż informatyki.

Są jednak dwie rzeczy, których nie mówi teza Kościoła-Turinga , które są bardzo istotne dla twojego pytania:

1. jak skuteczne są różne symulacje i
2. jak wygodne jest kodowanie problemu.

Prosty przykład dla (1): na maszynie o swobodnym dostępie kopiowanie tablicy zajmuje czas proporcjonalny do długości tablicy. Na maszynie Turinga zajmuje to jednak czas proporcjonalny do kwadratu długości macierzy, ponieważ maszyna Turinga nie ma losowego dostępu do pamięci, może przemieszczać się po taśmie tylko jedna komórka na raz. Dlatego musi przesuwać się przez n elementów tablicy n razy, aby je skopiować. Różne modele obliczeń mogą mieć różne charakterystyki wydajności, nawet w przypadku asymptotycznym, w którym staramy się oderwać od szczegółów implementacji.

Mnóstwo przykładów (2): zarówno rachunek λ, jak i Python są kompletne według Turinga. Ale czy wolisz napisać program w języku Python lub w rachunku λ?

Jest też trzecia zmarszczka, którą omijałem do tej pory: wszystkie te oryginalne systemy zostały zaprojektowane przez logików, filozofów lub matematyków, a nie przez informatyków… po prostu dlatego, że komputery, a więc informatyka, nie istniały. Te wszystkie wrócić do początku 1930 roku, jeszcze przed Konrad Zuse „s bardzo pierwsze eksperymenty (które nie były programowalne i / lub Turing-complete tak). Mówią tylko o „funkcjach obliczalnych na liczbach naturalnych”.

Teraz, jak się okazuje, wiele funkcji można wyrazić jako funkcje liczb naturalnych - w końcu nasze nowoczesne komputery radzą sobie nawet z dużo mniejszą liczbą (w zasadzie 3-4 funkcje na liczbach 0 i 1 i to wszystko ), ale na przykład jaką funkcję oblicza system operacyjny?

To pojęcie I / O, efektów ubocznych, interakcji z otoczeniem, nie jest ujęte w idei „funkcji ponad liczbami naturalnymi”. A jednak jest to trochę ważne, ponieważ, jak to kiedyś ujął Simon Peyton Jones , „czystą funkcją bez efektów ubocznych jest rozgrzanie procesora” , na co członek publiczności odpowiedział „właściwie, to jest strona -efekt też! ”

Edwin Brady , projektant Idris , (tylko połowa) żartobliwie używa (nie wiem, czy to wynalazł) terminu „Tetris-complete”, aby wyrazić tę różnicę między „potrafi obliczyć dowolną funkcję obliczalną na liczbach naturalnych” i „potrafi być używane do pisania niebanalnych programów, które współdziałają ze środowiskiem ". Jeszcze bardziej ironicznie, demonstruje to, wdrażając klon Space Invaders w Idris , ale mówi, że jest pewien, że Tetris sprowadza się do Space Invaders.

Inną rzeczą, na którą należy zwrócić uwagę, jest to, że nie tylko ekwiwalent Turinga niekoniecznie wystarcza, aby mówić o pisaniu „przydatnych” programów, ale OTOH może nawet nie być konieczny . Np. SQL stał się odpowiednikiem Turinga tylko z ANSI SQL: 1999 , ale przedtem był użyteczny. W rzeczywistości niektórzy mogą twierdzić, że uczynienie go ekwiwalentem Turinga wcale nie zwiększyło jego przydatności. Istnieje wiele języków specyficznych dla domeny, które nie są odpowiednikami Turinga. Dane Opis Język zwykle nie jest (i nie powinien być). Total Languages ​​oczywiście nie może być odpowiednikiem Turinga, ale nadal można w nich pisać pętle zdarzeń, serwery sieciowe lub systemy operacyjne. Istnieją również języki, które są odpowiednikami Turinga, ale w rzeczywistości uważa się to za błąd.

Podsumowując, równoważność Turinga nie jest szczególnie interesująca, chyba że chcesz statystycznie analizować programy.

Wyrazistość

Zakładając, że nasz system obliczeniowy ma wystarczającą moc obliczeniową, aby w ogóle rozwiązać nasz problem, musimy następnie wyrazić nasz algorytm rozwiązania tego problemu w formie formalnej notacji dla tego systemu. Innymi słowy: musimy napisać program w jakimś języku komputerowym. Właśnie tutaj pojawia się pojęcie ekspresji .

Odnosi się zasadniczo do tego, jak „łatwe” lub „przyjemne” jest pisanie naszego programu w naszym konkretnym języku programowania. Jak widać, pojęcie jest dość niejasne, subiektywne i bardziej psychologiczne niż techniczne.

Istnieją jednak próby dokładniejszych definicji. Najsłynniejszy (i najbardziej rygorystyczny, jaki znam) to Matthias Felleisen w swoim artykule O ekspresyjnej mocy języków programowania (pierwsze dwie strony zawierają łagodne wprowadzenie, reszta artykułu jest bardziej mięsista).

Główna intuicja jest taka: podczas tłumaczenia programu z języka na inny język niektóre zmiany, które należy wprowadzić, są lokalnie zawarte (takie jak np. Przekształcanie FORpętli w WHILEpętle lub pętle w warunkowe GOTO), a niektóre wymagają zmiany w globalnym struktura programu.

Jeśli możesz zastąpić jedną cechę jednego języka inną cechą innego języka tylko lokalnymi transformacjami, wówczas mówi się, że te funkcje nie mają wpływu na siłę ekspresji. Nazywa się to cukrem syntaktycznym .

Z drugiej strony, jeśli wymaga to zmiany globalnej struktury programu, mówi się, że język, na który tłumaczysz, nie jest w stanie wyrazić tej funkcji. Mówi się, że język, z którego się tłumaczy, jest bardziej wyrazisty (w odniesieniu do tej funkcji).

Zauważ, że daje to obiektywnie mierzalną definicję ekspresji. Zauważ też, że pojęcie zależy od kontekstu i jest porównawcze. Tak więc, jeśli każdy program w języku A można przetłumaczyć na język B tylko z lokalnymi zmianami, a istnieje co najmniej jeden program w języku B, którego nie można przetłumaczyć na język A tylko z lokalnymi zmianami, to język B jest bardziej wyrazisty niż język ZA. Jednak bardziej prawdopodobnym scenariuszem jest to, że wiele programów w obu językach może być tłumaczonych tam iz powrotem, ale istnieją pewne programy w obu językach, których nie można przetłumaczyć na inny. Oznacza to, że żaden język nie jest bardziej wyrazisty niż inny, mają tylko różne funkcje, które pozwalają na różne wyrażenia różnych programów.

Daje to formalną definicję tego, co znaczy być „bardziej ekspresyjnym”, ale wciąż nie uchwyca psychologicznych pojęć tego zjawiska. Na przykład cukier składniowy, zgodnie z tym modelem, nie zwiększa mocy ekspresyjnej języka, ponieważ można go przetłumaczyć przy użyciu tylko lokalnych zmian. Jednak z doświadczenia wiemy, że posiadanie FOR, WHILEi IFdostępne, nawet jeśli są one po prostu cukier syntaktyczny dla warunkowych GOTOmarek wyrażając naszą intencją łatwiejsze .

Faktem jest, że różne języki mają różne funkcje, dzięki którym wyrażanie różnych sposobów myślenia o problemie jest łatwiejsze lub trudniejsze. I niektórzy ludzie mogą znaleźć jeden sposób wyrażenia swoich zamiarów łatwiej, a inni inny sposób.

Przykład, który znalazłem w tagu Ruby na StackOverflow: wielu użytkowników, którzy śledzą tag Ruby, twierdzą, że pętle są łatwiejsze do zrozumienia niż rekurencja, a rekurencja dotyczy tylko zaawansowanych funkcjonalnych programistów, a pętle są bardziej intuicyjne dla początkujących, ale widziałem wiele przypadków kompletni nowicjusze, którzy intuicyjnie piszą taki kod:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Co zwykle prowadzi do tego, że kilka osób komentuje, że „to nie działa” i „robią to źle”, a „poprawny sposób” jest następujący:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Oczywiście są ludzie, dla których rekurencja ogona jest bardziej naturalnym sposobem wyrażenia koncepcji „zapętlenia” niż konstrukcji pętli.

Podsumowanie

Fakt, że dwa języki są odpowiednikami Turinga, mówi jedną i dokładnie jedną rzecz: że mogą one obliczyć ten sam zestaw funkcji na liczbach naturalnych, co maszyna Turinga. Otóż ​​to.

Nie mówi nic o tym, jak szybko obliczają te funkcje. Nie mówi nic o łatwości wyrażania tych funkcji. I nie mówi nic o tym, co mogą zrobić poza funkcjami obliczania liczb naturalnych (np. Łączenie z bibliotekami C, odczytywanie danych wejściowych od użytkownika, zapisywanie danych wyjściowych na ekranie).

czy to oznacza, że ​​klasa problemów, które każdy język programowania może faktycznie rozwiązać, różni się w zależności od języka, mimo że wszystkie te języki są w pełni gotowe?

Tak.

1. Istnieją problemy, których nie obejmuje termin „Turing-complete” (który dotyczy wyłącznie funkcji obliczeniowych na liczbach naturalnych), np. Drukowanie na ekranie. Dwa języki mogą być kompletne Turinga, ale jeden umożliwia drukowanie na ekranie, a drugi nie.
2. Nawet jeśli oba języki mogą rozwiązać te same problemy, nie mówi to nic o tym, jak skomplikowane jest kodowanie i jak łatwo jest je wyrazić. Np. C może rozwiązać każdy problem, który potrafi Haskell, po prostu pisząc interpreter Haskell w C… ale najpierw musisz napisać interpreter Haskell, aby rozwiązać problem w ten sposób!

Wszystkie kompletne języki programowania Turinga mogą implementować ten sam zestaw algorytmów. Jeśli więc zauważysz, że niektóre algorytmy są bardzo trudne do zaimplementowania w określonym języku, nie oznacza to, że jest to niemożliwe.

Pamiętaj, że język składa się ze składni i semantyki. Czasami zestaw słów należących do jakiegoś języka nie jest minimalny, aby uznać go za kompletny, istnieją funkcje, które ułatwiają (dlatego nazywane są funkcjami ). Jeśli wyłączysz te funkcje, język nadal będzie kompletny.

Niektóre z nich mogą być interesujące:

• Kompilator typu źródło-źródło na Wikipedii

• O znaczeniu kompletności Turinga w Lambda the Ultimate

Wszystkie języki kompletne Turinga mogą obliczać te same rzeczy.

Jeśli spróbujesz wdrożyć nowoczesny język, zauważysz, że większość jego funkcji nie dodaje żadnych możliwości obliczeniowych. Wiele z tych funkcji można sprowadzić do prostszych, które już istnieją w tym samym języku.

Oto kilka przykładów:

• Jeśli nie masz wyliczeń, możesz użyć liczb całkowitych.
• Jeśli nie masz buforów znających ich rozmiar, możesz utworzyć typ zawierający rozmiar i bufor, który nie zna jego rozmiaru.
• Jeśli nie masz sprawdzania granic buforów, możesz po prostu sprawdzić indeks za każdym razem, gdy ich używasz.
• Jeśli nie masz funkcji variadic, możesz utworzyć funkcję, która pobiera bufor znający jego rozmiar i odczytuje z tego bufora te same informacje, które można uzyskać z formalnych argumentów.
• Jeśli nie masz operatorów, możesz użyć funkcji.
• Jeśli nie masz typów, które mogą się dziedziczyć, możesz tworzyć typy, które się zawierają, i uzyskać do nich dostęp poprzez dodatkowy poziom pośredni, przy czym podtyp jest po prostu transformacją typu uchwyt do całego typu na uchwyt do typu zamkniętego.
• Jeśli nie masz delegatów, ale masz wskaźniki funkcji, możesz utworzyć typ zawierający obiekt referencyjny i wskaźnik funkcji.
• Jeśli nie masz delegatów, ale masz interfejsy, możesz zadeklarować interfejs zawierający jedną metodę z żądanym podpisem.
• Jeśli nie masz typów ogólnych, możesz użyć typów ogólnych, które zakładają jedynie górne lub dolne granice, którymi jesteś zainteresowany (i być może wykonuj odpowiednie rzuty w miejscach użycia, aby utrzymać kompilator w dobrej formie).
• Jeśli nie masz systemu liniowego / afinicznego, możesz po prostu uniknąć używania dowolnej zmiennej więcej niż raz.
• ...i tak dalej.

Projektowanie język nurt koncentruje się na funkcji, które sprawiają, że łatwiej i bardziej wygodne dla nas, aby obliczyć rzeczy szybciej rozpoznawać nasze błędy wcześniej programu przed nieznanymi komponentów sprawiają, że równoległości bezpieczniejsze, i tak dalej.

Rzeczy czysto obliczeniowe zostały przybite dawno temu.

Istniejące odpowiedzi słusznie wskazują, że kompletność Turinga nie jest dobrym sposobem na porównanie języków. Rzeczywiście, prawie wszystkie języki są kompletne. („Jeśli każdy jest wyjątkowy, to nikt nie jest wyjątkowy”, jak mawiał Iniemamocni).

Jednak to jest możliwe porównanie wyrazistość języków z matematyczną precyzją. Spójrz na ekspresyjną moc języków programowania Felleisen . Z grubsza chodzi o to, aby zadać następujące pytanie: Czy mogę przekonwertować dowolny program w języku A na program w języku B, wprowadzając tylko lokalne zmiany? Innymi słowy, Felleisen nadaje twojej intuicji matematycznie precyzyjną formę.

Oprócz odpowiedzi innych osób, oto kolejna analogia.

Do prania ubrań potrzebne są trzy rzeczy: zbiornik, w którym znajduje się woda, pewnego rodzaju detergent i mechanizm mieszania. Można to zrealizować na wiele sposobów. Zbiornik wodny to wszystko, co utrzymuje wystarczającą ilość wody (np. Wanna, jezioro, rzeka). Mechanizmem mieszającym może być urządzenie mechaniczne, zmywarka, a nawet kamień, o który ubijane są ubrania. I detergenty są również w różnych postaciach.

Jaka jest różnica między nowoczesną skomputeryzowaną pralką a kamieniem nad rzeką?

Sprowadza się do trzech rzeczy: wydajności, bezpieczeństwa i wygody. Niektóre metody prania zużywają mniej energii, mniej zanieczyszczają środowisko, zużywają mniej wody i tak dalej. Niektóre metody prania wymagają mniej powtarzalnych czynności manualnych (które powodują obrażenia) lub przebywania na zewnątrz w niesprzyjających warunkach pogodowych. Niektóre metody prania nie wymagają od człowieka opieki nad tym procesem.

Języki programowania Turing-complete są uniwersalne, więc są stawiane przed więcej niż jednym zadaniem. Niemniej jednak, dla danego zadania, niektóre języki programowania są bardziej wydajne, wygodniejsze i bezpieczniejsze (w tym sensie, że mniej może się nie udać, gdy program jest faktycznie używany) niż inne.

Inni udzielili wielu dobrych odpowiedzi, ale nie wspominają jednoznacznie o jednym zastrzeżeniu, które kiedyś bardzo mnie pomieszało: kompletność Turinga nie oznacza, że ​​język może wyrażać dowolne funkcje obliczeniowe od danych wejściowych do wyjściowych. Jest słabszy: musi istnieć jakiś sposób reprezentowania dziedziny i zakresu zestawu funkcji obliczalnych jako danych wejściowych i wyjściowych, tak aby każda z tych funkcji odwzorowała się na program, który przyjmuje reprezentację swoich danych wejściowych do odpowiednich wyników.

Weźmy na przykład język, który wyraża maszyny Turinga. Każdy program w języku jest maszyną Turinga.

Teraz rozważ podjęzyk wszystkich maszyn Turinga, które odczytują i zapisują tylko znaki a, b i puste. Jest zakończony Turinga, ale nie może wyrazić żadnych programów, które na przykład produkują c na wszystkich wejściach, ponieważ nie może napisać żadnego cs. Może wyrażać tylko wszystkie funkcje obliczalne na wejściach i wyjściach zakodowanych jako ciągi znaków as i bs.

Nie jest więc prawdą, że wszystkie języki kompletne Turinga mogą obliczać te same rzeczy, nawet jeśli ograniczymy te rzeczy do funkcji obliczeniowych od ich potencjalnych danych wejściowych do ich potencjalnych wyników. Język może wymagać kodowania danych wejściowych i wyjściowych w określony sposób.