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

23

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ł”?

Xophmeister
źródło
1
Powiedziałbym, że maszyny Turinga lub uniwersalne maszyny rejestrujące są podstawą PL procesorów (PL PL). Nie mają funkcji. -funkcje rekurencyjne są podstawą imperatywnych PL. Nie mają funkcji wyższego rzędu. μ
beroal
1
Poleciłbym także przyjrzeć się logice pierwszego rzędu i Prologowi.
beroal
1
W wersjach wcześniejszych niż C ++ 11 constexprmożna było (trzeba było) używać „szablonów”, aby kompilator wykonywał obliczenia w czasie kompilacji. Ograniczenia dotyczące szablonów nie zezwalają na pętle, ale można użyć rekurencji do emulacji dowolnej pętli, dzięki czemu powstanie funkcja Turing-complete (metaprogramowanie) jako część standardu językowego C ++, patrz np. Stackoverflow.com/questions / 189172 / c-templates-turing-complete
JimmyB

Odpowiedzi:

45

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 μμμ 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 λμλ 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ć λμλFωfixλλ-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.μμμ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 λλλμλλ -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 λ-rachunek różniczkowy.

xuq01
źródło
7
„nikt nie konstruuje z Conwayem” ... niektórzy robią Zbuduj działającą grę Tetris w grze Conwaya Game of Life ... także jest tak praktyczna jak
biała
λλ
@AlexeiLevenkov To całkowicie nieprawda. Biała spacja jest zasadniczo (prostym) językiem imperatywnym, aczkolwiek z dziwną składnią. Posiada funkcje arytmetyczne, podstawowy przepływ sterowania, manipulowanie stosami i stertami oraz operacje we / wy . Z drugiej strony projekt QFT wymagał zaprojektowania kompilatora od bardzo prostego języka do zestawu RISC utworzonego dla procesora wbudowanego w podobny do Wireworld automat komórkowy emulowany za pomocą OTCA Metapixels .
Pisownia bezkontekstowa
@AlexeiLevenkov Ostateczny kompilator Cogol → CGoL wymagał pracy wielu osób w ciągu czterech lat, podczas gdy istnieje projekt o nazwie HaPyLi , kompilujący znacznie bardziej złożony język do Whitespace, napisany przez jedną osobę w wolnym czasie.
Pisownia bezkontekstowa
4

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.

Kapol
źródło
μ
2
Oczywiście. Po prostu założyłem, że OP chce znaleźć taki język, aby studiować teorię lub coś takiego, a nie podbić nią świat ;-)
Kapol