Jeśli zbudujesz od podstaw minimalną liczbę operacji na komputerze ogólnym, „Iteracja” jest najważniejsza jako element konstrukcyjny i wymaga mniej zasobów niż „rekurencja”, więc ergo jest szybsze.
Ustanowimy hierarchię pojęć, zaczynając od zera i definiując przede wszystkim podstawowe, podstawowe pojęcia, a następnie budujemy z nimi pojęcia drugiego poziomu i tak dalej.
Pierwsza koncepcja: komórki pamięci, pamięć, stan . Aby coś zrobić, potrzebujesz miejsca do przechowywania końcowych i pośrednich wartości wyników. Załóżmy, że mamy nieskończoną tablicę komórek „całkowitych”, zwanych Memory , M [0..Infinite].
Instrukcje: zrób coś - przekształć komórkę, zmień jej wartość. zmienić stan . Każda ciekawa instrukcja wykonuje transformację. Podstawowe instrukcje to:
a) Ustaw i przenieś komórki pamięci
- zapisz wartość w pamięci, np .: zapisz 5 m [4]
- skopiuj wartość do innej pozycji: np .: zapisz m [4] m [8]
b) Logika i arytmetyka
- i, lub xor, nie
- dodaj, sub, mul, div. np. dodaj m [7] m [8]
Agent wykonujący : rdzeń nowoczesnego procesora. „Agent” to coś, co może wykonywać instrukcje. Agenta może być także osoba następujący algorytm na papierze.
Kolejność kroków: sekwencja instrukcji : tj. Zrób to najpierw, zrób to później itp. Konieczna sekwencja instrukcji. Nawet wyrażenia jednej linii są „bezwzględną sekwencją instrukcji”. Jeśli masz wyrażenie z określoną „kolejnością oceny”, masz kroki . Oznacza to, że nawet jedno złożone wyrażenie ma niejawne „kroki”, a także niejawną zmienną lokalną (nazwijmy to „wynikiem”). na przykład:
4 + 3 * 2 - 5
(- (+ (* 3 2) 4 ) 5)
(sub (add (mul 3 2) 4 ) 5)
Powyższe wyrażenie oznacza 3 kroki z niejawną zmienną „wynik”.
// pseudocode
1. result = (mul 3 2)
2. result = (add 4 result)
3. result = (sub result 5)
Tak więc nawet wyrażenia niepoprawne, ponieważ masz określoną kolejność oceny, są konieczną sekwencją instrukcji . Wyrażenie implikuje sekwencję operacji, które należy wykonać w określonej kolejności, a ponieważ istnieją kroki , istnieje również domniemana zmienna pośrednia „wynik”.
Wskaźnik instrukcji : Jeśli masz sekwencję kroków, masz również domyślny „wskaźnik instrukcji”. Wskaźnik instrukcji oznacza następną instrukcję i przesuwa się po jej odczytaniu, ale przed wykonaniem instrukcji.
W tej pseudo-maszynie obliczeniowej wskaźnik instrukcji jest częścią pamięci . (Uwaga: normalnie wskaźnik instrukcji będzie „specjalnym rejestrem” w rdzeniu procesora, ale tutaj uprościmy koncepcje i założymy, że wszystkie dane (łącznie z rejestrami) są częścią „pamięci”)
Skok - po uzyskaniu uporządkowanej liczby kroków i wskaźnika instrukcji można zastosować instrukcję „ zapisz ”, aby zmienić wartość samego wskaźnika instrukcji. Będziemy nazywać to konkretne użycie instrukcji sklepu nową nazwą: Jump . Używamy nowej nazwy, ponieważ łatwiej jest myśleć o niej jako o nowej koncepcji. Zmieniając wskaźnik instrukcji, instruujemy agenta, aby „poszedł do kroku x”.
Nieskończona iteracja : Odskakując , możesz teraz sprawić, że agent „powtórzy” określoną liczbę kroków. W tym momencie mamy nieskończoną iterację.
1. mov 1000 m[30]
2. sub m[30] 1
3. jmp-to 2 // infinite loop
Warunkowe - warunkowe wykonanie instrukcji. Dzięki klauzuli „warunkowej” możesz warunkowo wykonać jedną z kilku instrukcji na podstawie bieżącego stanu (który można ustawić za pomocą poprzedniej instrukcji).
Właściwa iteracja : Teraz dzięki klauzuli warunkowej możemy uciec od nieskończonej pętli instrukcji cofania . Mamy teraz pętlę warunkową, a następnie właściwą iterację
1. mov 1000 m[30]
2. sub m[30] 1
3. (if not-zero) jump 2 // jump only if the previous
// sub instruction did not result in 0
// this loop will be repeated 1000 times
// here we have proper ***iteration***, a conditional loop.
Nazewnictwo : nadawanie nazw konkretnej lokalizacji pamięci przechowującej dane lub trzymającej stopień . To tylko „wygoda”. Nie dodajemy żadnych nowych instrukcji, ponieważ możemy zdefiniować „nazwy” dla lokalizacji pamięci. „Nazewnictwo” nie jest instrukcją dla agenta, jest dla nas jedynie wygodą. Nazewnictwo sprawia, że kod (w tym momencie) jest łatwiejszy do odczytania i łatwiejszy do zmiany.
#define counter m[30] // name a memory location
mov 1000 counter
loop: // name a instruction pointer location
sub counter 1
(if not-zero) jmp-to loop
Podprogram jednopoziomowy : Załóżmy, że musisz wykonać szereg czynności często. Możesz zapisać kroki w nazwanej pozycji w pamięci, a następnie przeskoczyć do tej pozycji, kiedy trzeba je wykonać (połączenie). Na końcu sekwencji musisz wrócić do punktu wywołania, aby kontynuować wykonywanie. Dzięki temu mechanizmowi tworzysz nowe instrukcje (podprogramy), tworząc podstawowe instrukcje.
Wdrożenie: (nie są wymagane nowe koncepcje)
- Przechowuj bieżący wskaźnik instrukcji we wstępnie zdefiniowanej pozycji w pamięci
- przejść do podprogramu
- na końcu podprogramu pobiera się wskaźnik instrukcji ze wstępnie zdefiniowanego miejsca w pamięci, skutecznie skacząc z powrotem do następującej instrukcji pierwotnego wywołania
Problem z implementacją jednopoziomową : Nie można wywołać innego podprogramu z podprogramu. Jeśli to zrobisz, nadpiszesz adres zwrotny (zmienna globalna), więc nie możesz zagnieżdżać połączeń.
Aby mieć lepszą implementację podprogramów: Potrzebujesz stosu
Stos : definiujesz przestrzeń pamięci jako „stos”, możesz „wypychać” wartości na stosie, a także „pop” ostatnią „wypchniętą” wartość. Aby wdrożyć stos, potrzebujesz wskaźnika stosu (podobnego do wskaźnika instrukcji), który wskazuje na rzeczywistą „głowę” stosu. Kiedy „wypychasz” wartość, wskaźnik stosu zmniejsza się i zapisujesz wartość. Kiedy „wyskakujesz”, otrzymujesz wartość przy rzeczywistym wskaźniku stosu, a następnie wskaźnik stosu jest zwiększany.
Podprogramy Teraz, gdy mamy stos , możemy zaimplementować odpowiednie podprogramy umożliwiające zagnieżdżanie wywołań . Implementacja jest podobna, ale zamiast przechowywać wskaźnik instrukcji we wstępnie zdefiniowanej pozycji pamięci, „wypychamy” wartość adresu IP na stos . Na końcu podprogramu po prostu „wyskakujemy” wartość ze stosu, skutecznie skacząc z powrotem do instrukcji po pierwotnym wywołaniu . Ta implementacja, posiadająca „stos”, umożliwia wywołanie podprogramu z innego podprogramu. Dzięki tej implementacji możemy stworzyć kilka poziomów abstrakcji podczas definiowania nowych instrukcji jako podprogramów, wykorzystując podstawowe instrukcje lub inne podprogramy jako bloki konstrukcyjne.
Rekurencja : Co się dzieje, gdy podprogram wywołuje się ?. Nazywa się to „rekurencją”.
Problem: Nadpisanie lokalnych wyników pośrednich, które podprogram może przechowywać w pamięci. Ponieważ wywołujesz / ponownie używasz tych samych kroków, jeśli wynik pośredni jest przechowywany w predefiniowanych lokalizacjach pamięci (zmienne globalne), zostaną one zastąpione w zagnieżdżonych wywołaniach.
Rozwiązanie: Aby umożliwić rekurencję, podprogramy powinny przechowywać lokalne wyniki pośrednie na stosie , dlatego przy każdym wywołaniu rekurencyjnym (bezpośrednim lub pośrednim) wyniki pośrednie są przechowywane w różnych lokalizacjach pamięci.
...
Na koniec zauważ, że masz wiele możliwości korzystania z rekurencji. Wszędzie masz Rekurencyjne Struktury Danych , na które teraz patrzysz: części DOM obsługujące to, co czytasz, to RDS, wyrażenie JSON to RDS, hierarchiczny system plików na twoim komputerze to RDS, tzn .: masz katalog główny zawierający pliki i katalogi, każdy katalog zawierający pliki i katalogi, każdy katalog zawierający pliki i katalogi ...