Języki programowania dla wydajnych obliczeń

32

Niemożliwe jest napisanie języka programowania, który zezwala wszystkim maszynom, które zatrzymują się na wszystkich wejściach i żadnych innych. Wydaje się jednak, że łatwo jest zdefiniować taki język programowania dla dowolnej standardowej klasy złożoności. W szczególności możemy zdefiniować język, w którym możemy wyrazić wszystkie wydajne obliczenia i tylko wydajne obliczenia.

Na przykład, dla czegoś takiego jak : wybierz swój ulubiony język programowania, a po napisaniu programu (odpowiadającego Turing Machine ) dodaj trzy wartości do nagłówka: liczba całkowita i liczba całkowita oraz domyślne wyjście . Po skompilowaniu programu wypisz maszynę Turinga która otrzymała dane wejściowe rozmiaru uruchamia $P$ $M'$ $c$ $k$ $d$ $M$ $x$ $n$ $M'$ na dla kroków. Jeśli nie zatrzyma się przed wykonaniem kroków , wypisz domyślne wyjście $x$ $c n^k$ $M'$ $c n^k$ $d$ . O ile się nie mylę, te języki programowania pozwolą nam wyrazić wszystkie obliczenia w i nic więcej. Jednak ten proponowany język z natury nie jest interesujący. $P$

Moje pytanie: czy istnieją języki programowania, które przechwytują podzbiory funkcji obliczeniowych (takich jak wszystkie wydajnie obliczalne funkcje) w nie-trywialny sposób? Jeśli nie, czy istnieje ku temu powód?

cc.complexity-theory computability pl.programming-languages

— Artem Kaznatcheev
źródło

7

Kilka prostych przykładów języków programowania, które przechwytują podzbiory funkcji obliczalnych: wyrażenia regularne i gramatyki bezkontekstowe.

— Jukka Suomela

2

W rzeczywistości języki, które wychwytują klasę złożoności

taką jak

(która jest zdefiniowana w podobny sposób do prymitywnych funkcji rekurencyjnych z rekurencją zastąpioną rekursją ograniczoną) są dość interesujące (przynajmniej z teoretycznego punktu widzenia). :)

P

$\mathbf{P}$

P V

$\mathbf{PV}$

— Kaveh

Programowanie liniowe i całkowite rejestruje interesujące podzbiory funkcji obliczeniowych.

— Diego de Estrada

Datalog może wyrażać tylko algorytmy wielomianowe, ale nie wiem, czy może wyrażać wszystkie algorytmy wielomianowe.

— Jules

Dobrze znany artykuł „Total programowanie funkcjonalne” wysuwa argument, że języki programowania, które nie mają nierozstrzygniętego problemu zatrzymania, są w rzeczywistości praktyczne i przydatne. jucs.org/jucs_10_7/total_functional_programming

— brak

32

Jednym z języków próbujących wyrażać tylko wielomianowe obliczenia czasu jest rachunek różniczkowy lambda . Jego system typów jest zakorzeniony w logice liniowej. Ostatnia teza dotyczy wielomianowych obliczeń czasowych i stanowi dobre podsumowanie ostatnich zmian opartych na tym podejściu. Martin Hofmann pracuje nad tym tematem od dłuższego czasu. Starszą listę odpowiednich artykułów można znaleźć tutaj ; Wiele jego prac kontynuuje w tym kierunku.

Inne prace polegają na sprawdzeniu, czy program używa pewnej ilości zasobów, przy użyciu typów zależnych lub języka asemblowanego .

Jeszcze inne podejścia oparte są na formalnych rachunkach ograniczonych zasobami , takich jak warianty rachunku otoczenia.

Podejścia te mają właściwość polegającą na tym, że dobrze napisane programy spełniają określone ograniczenia zasobów. Zasób związany może być czasem lub przestrzenią i ogólnie może zależeć od wielkości danych wejściowych.

Wczesne prace w tym obszarze polegają na silnie normalizującym rachunku różniczkowym, co oznacza, że wszystkie dobrze napisane programy zostają zatrzymane. System F , czyli polimorficzny rachunek lambda, silnie się normalizuje. Nie ma operatora punktu stałego, ale mimo to jest dość wyrazisty, choć nie sądzę, że wiadomo, z jaką klasą złożoności odpowiada. Z definicji każdy rachunek normalizujący silnie wyraża pewną klasę obliczeń kończących.

Język programowania Charity jest dość ekspresyjnym językiem funkcjonalnym, który zatrzymuje się na wszystkich wejściach. Nie wiem, jaką klasę złożoności może wyrazić, ale funkcję Ackermanna można zapisać w Charity.

— Dave Clarke
źródło

Co rozumiesz przez „przynajmniej” tutaj?

— nponeccop

„Przynajmniej” oznacza tutaj „trochę”. Zmienię swoją odpowiedź, aby była nieco bardziej precyzyjna.

— Dave Clarke

Jestem całkiem pewien, że złożoność funkcji definiowanych w systemie F jest klasą funkcji, które kończą się w czasie „pewną możliwą do udowodnienia całkowitą funkcją arytmetyki drugiego rzędu” wejścia. Niezbyt konwencjonalna klasa złożoności, ale wciąż ...

— cody

cody: zgodnie z „Twierdzeniami za darmo” Wadlera, System F może wyrazić „każdą funkcję rekurencyjną, którą można udowodnić jako całkowitą w arytmetyki Peano drugiego rzędu”, i że „obejmuje ona [...] funkcję Ackermanna”. Nie jestem pewien, czy to to samo, co opisujesz. Główną cechą organizacji charytatywnej jest obsługa kodów, podczas gdy myślę, że sprawdzanie terminacji Agdy pozwala na większą ekspresję niż zarówno Coq, jak i System F, gwarantując jednocześnie zakończenie.

— Blaisorblade,

10

Spójrz na artykuł Guillaume Bonfante, który zaproponował dwie charakterystyki dla Logspace i czasu wielomianowego przy użyciu języków programowania.

Guillaume Bonfante, Niektóre języki programowania dla Logspace i Ptime, AMAST 2006, LNCS 4019, ss. 66-80, 2006

— Mohammad Al-Turkistany
źródło

8

Chciałbym również wspomnieć o teorii niejawnej złożoności jako podejściu do tego, ponieważ widziałem, że pojawia się ona w kilku dość powiązanych pytaniach. Cytując tę odpowiedź Neela Krishnaswamiego :

Podstawową techniką jest powiązanie klas złożoności z podsystemami logiki liniowej (tzw. „Lekka logika liniowa”), przy założeniu, że eliminacja cięć w systemie logicznym powinna być kompletna dla danej klasy złożoności (np. LOGSPACE, PTIME itp.). Następnie za pośrednictwem Curry-Howarda poznajesz język programowania, w którym dokładnie programy w danej klasie są wyraźne.

— Chris Pressey
źródło

5

Dziwi mnie, że nikt nie wspominał o prymitywnej rekurencji. Ograniczając się do ograniczonych pętli (tj. Liczba iteracji dla każdej pętli musi zostać obliczona przed rozpoczęciem pętli), wynikowy program jest pierwotnie rekurencyjny, a zatem całkowity. Douglas Hofstadter zaproponował język programowania BLOOP, który zezwala na wszystkie i tylko prymitywne funkcje rekurencyjne.

— David Harris
źródło

1

Jest to właściwa podklasa wszystkich funkcji, ale nazwanie jej klasą „wydajnych” funkcji może być nieco rozciągnięte.

— Raphael,

P

$\mathsf{P}$

P

$\mathsf{P}$

Inni wspominali o Systemie F i innych silnie normalizujących się językach, które w pewnym sensie obsługują tylko „prymitywną rekurencję”. Ponieważ jednak obsługują funkcje najwyższej klasy, umożliwiają pisanie większej liczby programów (takich jak funkcja Ackermann).

— Blaisorblade

3

Zobacz także Pola języka programowania PTIME i twórczości Japaridze na PTIME arytmetyka np http://arxiv.org/abs/0902.2969

— nponeccop
źródło