Czy jakieś języki programowania wykorzystują ogólne funkcje rekurencyjne jako podstawę?

To naiwne i dlatego prawdopodobnie źle sformułowane pytanie, więc z góry przepraszamy!

Moim zdaniem maszynę Turinga można postrzegać jako podstawę obliczeniową dla proceduralnych / imperatywnych języków programowania. Podobnie, rachunek lambda jest podstawą funkcjonalnych języków programowania.

Niedawno dowiedziałem się, że teza Churcha-Turinga wykazuje również wzajemną równoważność z trzecim modelem obliczeń: ogólnymi funkcjami rekurencyjnymi . Czy istnieją języki programowania, które wykorzystują to jako model obliczeń? Jeśli nie, czy istnieje techniczny powód; tj. oprócz „Nikt jeszcze nie próbował”?

Bezpośrednia odpowiedź na pytanie: tak, istnieją ezoteryczne i wysoce niepraktyczne PL oparte na funkcjach rekurencyjnych (pomyśl Whitespace), ale żaden praktyczny język programowania nie jest oparty na $\mu$$\mu$ funkcjach rekurencyjnych z ważnych powodów.

Ogólne funkcje rekurencyjne (tj. rekurencyjne) są znacznie mniej ekspresyjne niż rachunek lambda. Stanowią zatem słabą podstawę dla języków programowania. Nie masz również racji, że TM jest podstawą imperatywnych PL: w rzeczywistości dobre imperatywne języki programowania są znacznie bliższe $\mu$$\lambda$ kalkulatorowi niż maszynom Turinga.

Pod względem obliczalności, -funkcje rekurencyjne, maszyna Turinga i niepoprawny λ- rachunek są równoważne. Jednak nietypowy LC ma dobre właściwości, których nie ma żadne z pozostałych dwóch. Jest bardzo prosty (tylko 3 formy składniowe i 2 reguły obliczeniowe), jest bardzo kompozycyjny i stosunkowo łatwo potrafi wyrażać konstrukcje programistyczne. Ponadto, wyposażony w prosty system typów (np. System F ω rozszerzony o f i x ), λ- rachunek może być niezwykle ekspresyjny, ponieważ może wyrażać wiele złożonych konstrukcji programistycznych łatwo, poprawnie i kompozycyjnie. Możesz także rozszerzyć $\mu$$\lambda$$F\omega$$\mathsf{fix}$$\lambda$$\lambda$-kalkulus z łatwością zawiera konstrukty, które nie są lambdami. Żaden z pozostałych modeli obliczeniowych wymienionych powyżej nie daje tych dobrych właściwości.

Maszyna Turinga nie jest ani kompozycyjna, ani uniwersalna (musisz mieć TM dla każdego problemu). Brak jest pojęć „funkcji”, „zmiennych” lub „kompozycji”. Nie jest również do końca prawdą, że bazy TM są podstawą imperatywnych PL - FWIW, imperatywne PL są znacznie, znacznie bliższe obliczeniom lambda u operatorów sterujących niż maszynom Turinga. Zobacz wyjaśnienie Petera J. Landina „Korespondencja między ALGOL 60 a notacją lambda Kościoła”, aby uzyskać szczegółowe wyjaśnienie. Jeśli zaprogramowałeś w Brainf ** k (który faktycznie implementuje dość prostą maszynę Turinga), będziesz wiedział, że maszyny Turinga nie są dobrym pomysłem na programowanie.

Funkcje rekursywne μ są pod tym względem podobne do TM. Są kompozycyjne, ale nie tak kompozycyjne jak LC. Nie można również zakodować użytecznych konstrukcji programistycznych wfunkcjach μ- rekurencyjnych. Co więcej, funkcje μ- rekurencyjne obliczają tylko N , a do obliczania czegokolwiek innego trzeba będzie zakodować dane w liczbach naturalnych za pomocą pewnego rodzaju numeracji Gödla, co jest bolesne.$\mu$$\mu$$\mu$$\mathbb{N}$

To nie przypadek, że większość języków programowania jest w jakiś sposób oparta na rachunku! Λ -calculus ma dobre właściwości: ekspresja, kompozycjonalność i rozciągliwość, że inne systemy brakuje. Jednak maszyny Turinga są dobre do badania złożoności obliczeniowej, a funkcje μ- rekurencyjne są dobre do badania logicznego pojęcia obliczalności. Oba mają wybitne właściwości, których brakuje λ- rachunku, ale w dziedzinie programowania $\lambda$$\lambda$$\mu$$\lambda$$\lambda$ -calculus wyraźnie wygrywa.

W rzeczywistości istnieje wiele, wiele innych kompletnych systemów Turinga, ale brakuje im jakichkolwiek wyjątkowych właściwości. Conway's Game of Life, makra LaTeX, a nawet (niektórzy twierdzą) DNA są kompletne Turinga, ale żaden program (tj. Nie robi poważnego programowania) z Conwayem ani nie bada złożoności obliczeniowej przy użyciu makr LaTeX. Po prostu brakuje im dobrych właściwości. Turing kompletny per se jest prawie bez znaczenia, jeśli chodzi o programowanie.

Ponadto wiele kompletnych systemów obliczeniowych innych niż Turing jest bardzo użytecznych, jeśli chodzi o programowanie. Wyrażenia regularne i yacc nie są kompletne w Turingu, ale są niezwykle potężne w rozwiązywaniu pewnej klasy problemów. Coq również nie jest kompletny w Turingu, ale jest niesamowicie potężny (w rzeczywistości jest uważany za znacznie bardziej wyrazisty niż jego kompletny kuzyn Turinga, OCaml). Jeśli chodzi o programowanie, kompletność Turinga nie jest kluczem, ponieważ wiele (blisko) bezużytecznych systemów jest nieinteresująco kompletnych Turinga. Nie będziesz twierdził, że Brainf ** k lub Whitespace są potężniejszymi językami programowania niż Coq, prawda? Wyraziste fundamentem jest kluczem do potężnych języków programowania, dlatego nowoczesne języki programowania są prawie zawsze oparte na $\lambda$-rachunek różniczkowy.

Wpisanie µ-recursive function programming languagew Google zaprowadziło mnie do tego repozytorium GitHub , więc odpowiedź na twoje pytanie brzmi:

Tak i nazywa się to krótkowzrocznością

Nawiasem mówiąc, jest napisane w Haskell.