Jakie imperatywne języki programowania nie obsługują rekurencji?

21

O ile mi wiadomo, wszystkie współczesne imperatywne języki programowania obsługują rekurencję w tym sensie, że procedura może się nazywać sama. Nie zawsze tak było, ale nie mogę znaleźć żadnych twardych faktów dzięki szybkiemu wyszukiwaniu w Google. Więc moje pytanie brzmi:

Które języki od samego początku nie obsługiwały rekurencji i kiedy dodano tę obsługę?

fredoverflow
źródło

Odpowiedzi:

21

Nie jestem pewien, czy COBOL tak robi (z pewnością tak nie było kiedyś), ale nie mogę sobie wyobrazić nikogo, kto by się tak bardzo przejmował.

Fortran ma od Fortran 90, ale wymaga użycia recursivesłowa kluczowego, aby powiedzieć, że podprogram jest rekurencyjny.

PL / I byłem prawie taki sam - rekurencja była obsługiwana, ale trzeba było wyraźnie powiedzieć, jakie procedury były rekurencyjne.

Wątpię jednak, aby było ich o wiele więcej. Kiedy do tego doszło, zakaz rekurencji był głównie czymś, co IBM zrobił w swoich projektach językowych, z tego prostego powodu, że komputery mainframe IBM (360/370/3090 / ...) nie obsługują stosu sprzętu. Kiedy większość języków pochodziła od IBM, najczęściej zabraniały rekursji. Teraz, gdy wszystkie pochodzą z innych miejsc, rekursja jest zawsze dozwolona (chociaż powinienem dodać, że kilka innych maszyn, zwłaszcza oryginalny Cray 1, również nie miało obsługi sprzętowej dla stosu).

Jerry Coffin
źródło
Komputery sterujące danymi okresu również nie obsługiwały rekurencji (wywołania podprogramów wykonano za pomocą instrukcji, która zmodyfikowała kod, aby wstawić skok do instrukcji wywołującej + 1). Kiedy Wirth opracował Pascala na 6600, prawdopodobnie musiał wymyślić nowy sposób wywoływania podprogramów.
David Thornley
@David: tak - i nie zbieg okoliczności, zostały również zaprojektowane przez Seymour Cray. Kiedyś musiałem spojrzeć na kompilator Pascal 6000, ale nie przypominam sobie, że sprawdziłem, co zrobił, aby wygenerować (symulować?) Ramki stosu.
Jerry Coffin
notably the original cray 1Więc nie potrzebujesz rekurencji, aby sklonować dinozaury? Wydaje mi się, że to naprawdę do nas, małp, należy huśtać się między drzewami.
normanthesquid
2
nawet CAML (i OCAML, F #) wymagają wyraźnie zaznaczonych funkcji rekurencyjnych.
jk.
1
@Panzercrisis: Nie jestem pewien, czy IBM był zaangażowany w x86, ale ich obecne komputery mainframe śledzą bezpośrednio do IBM 360, który pojawił się na rynku w 1964 roku, więc podstawowa konstrukcja wyprzedza x86 o kilka dekad.
Jerry Coffin
16

Wikipedia mówi:

Wczesne języki, takie jak Fortran, początkowo nie obsługiwały rekurencji, ponieważ zmienne były przydzielane statycznie, a także lokalizacja adresu zwrotnego.

http://en.wikipedia.org/wiki/Subroutine#Local_variables.2C_recursion_and_re-entrancy

FORTRAN 77 nie pozwala na rekurencję, Fortran 90 tak, (procedury rekurencyjne muszą być wyraźnie zadeklarowane).

Większość kompilatorów FORTRAN 77 umożliwia rekurencję, niektóre (np. DEC) wymagają użycia opcji kompilatora (patrz rozdział opcji kompilatora). GNU g77, który jest ściśle zgodny ze standardem Fortran 77, w ogóle nie pozwala na rekurencję.

http://www.ibiblio.org/pub/languages/fortran/ch1-12.html

Robert Harvey
źródło
iirc istniał co najmniej jeden kompilator FORTRAN 77, który chociaż technicznie obsługiwał rekurencję, całkowita liczba ramek stosu, które mogłeś mieć tak niewielką rekurencję, nie była efektywnie użyteczna dla wielu problemów
jk.
6

Język programowania OpenCL nie obsługuje rekurencji. (patrz sekcja 6.8 specyfikacji OpenCL )

Obecną motywacją tego jest a) brak miejsca na głębokie stosy b) chęć poznania, statycznie, całkowitych wymaganych przydziałów w celu zoptymalizowania wydajności w obecności dużych zestawów rejestrów i obszernego wbudowania.

Może to również dotyczyć innych języków programowania GPU, np. Języków shaderów.

Grrussel
źródło
2

Niektóre kompilatory c dla małych mikrokontrolerów nie obsługują rekurencji, prawdopodobnie dlatego, że mają bardzo ograniczony rozmiar stosu.

Jeanne Pindar
źródło
Niektóre z tych mikrokontrolerów (np. Rodzina PIC16) mają tylko sprzętowy stos wywołań (niedostępny dla instrukcji) i nie mają żadnej innej postaci stosu, więc funkcje nie mogą mieć zmiennych lokalnych podczas korzystania z rekurencji (ponieważ stos danych jest wyraźnie potrzebny za to ...) Referencje: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

BASIC, w czasach numerów linii, zwykle słabo obsługiwał rekurencję. Wiele (wszystkich?) BASIC ówczesnych obsługiwało zagnieżdżone wywołania gosub, ale nie obsługiwało łatwego sposobu przekazywania parametrów lub zwracania wartości w sposób, który czyniłby użyteczne samodzielne wywołanie.

Wiele wczesnych komputerów miało problemy z rekurencją, ponieważ korzystały z instrukcji wywołania, które zapisały adres zwrotny na początku procedury o nazwie (PDP8, rodzina maszyn IAS, prawdopodobnie więcej architektur, których nie znam), zwykle w taki sposób, że był kod maszynowy dla „Przejdź do instrukcji po tej, która wywołała procedurę”.

Vatine
źródło
1

To zależy od tego, co rozumiesz przez „ wsparcie ”. Do obsługi rekurencji potrzebny jest stos, w którym przy każdym ponownym wejściu należy ponownie tworzyć zmienne lokalne.

Nawet jeśli język nie ma pojęcia zmiennych lokalnych, jeśli ma pojęcie „podprogramu” i ma sposób zarządzania indeksowaniem między identycznymi zmiennymi (inaczej tablicą), możesz zwiększać / zmniejszać indeks globalny przy każdym wejściu / wyjściu funkcji i dostęp do niej przez członka jednej lub więcej tablic.

Nie wiem, czy można to nazwać „wsparciem”. Fakty są takie, że napisałem funkcję rekurencyjną w ZX-Spectrum BASIC, tak jak to zrobiłem w Fortran77 jak w COBOL ... zawsze z tą sztuczką.

Emilio Garavaglia
źródło
1

Język asemblera nie obsługuje bezpośrednio rekurencji - musisz „zrób to sam”, zwykle poprzez wypchnięcie parametrów na stos maszyny.

mikera
źródło
2
Obsługuje rekurencję, o ile obsługuje wywołania metod. Zwykle jest CALLinstrukcja, która automatycznie wypycha adres IP na stos przed przejściem do podprogramu, oraz instrukcja, która wstawia RETadres zwrotny do adresu IP. Nie ma powodu, dla którego nie możesz mieć CALLwłasnego punktu wejścia.
Blorgbeard
@Blorgbeard - absolutnie prawda, chociaż twierdzę, że nie jest to wystarczające, aby liczyć się jako „obsługuje rekurencję” w powszechnie rozumianym znaczeniu, ponieważ nie obsługuje parametrów wymaganych dla wywołania rekurencyjnego.
mikera
1
Połączenia rekurencyjne nie wymagają parametrów, prawda? void f() { f(); }jest rekurencyjny.
Blorgbeard
Technicznie nie. Ale możliwość kodowania jednej trywialnej sprawy nie oznacza, że ​​powinieneś opisać asembler jako „wspieranie rekurencji”. Najbardziej praktyczne zastosowania rekurencji wymagają parametrów.
mikera
Przypuszczam, że możesz tak powiedzieć. Ale w takim przypadku asembler również nie obsługuje pętli (musisz ręcznie CMP i JNZ). Myślę, że to kwestia tego, co nazywacie „wspieraniem”.
Blorgbeard