1. Home
  2. Różne
  3. Scheme w 5 minut (dla programistów C++)

Scheme w 5 minut

Przy założeniu znajomości C/C++

Typ int użyty w deklaracjach C/C++ jest dla prostoty przykładu. Proszę pamiętać że scheme można traktowac jak język słabo typowany, bez jawnej deklaracji typu zmiennej.

Rekurencja (wikipedia)

Definicja rekurencja to definiowanie rzeczy, zazwyczaj zależącej od pewnego parametru n (wielkość, złozoność) wykorzystując tą samą rzecz, z tym, że dla wartosi parametrów mniejszych. Najłatwiej zobrazować to definicją ciągu np. arytmetycznego - n-ty wyraz ciągu = n-1 wyraz ciągu + różnica. W definicji, aby była poprawna musi istnieć jeszcze przypadek bazowy, na którym rekurencja zostaje przerwana! W przykładzie z ciągiem jest to wyraz dla n = 0

Z definicji rekurencyjnej dostajemy często procedurę rekurencyjną. Jest to funkcja (matematyczna, programistyczna), która odwołuje się podczas obliczeń do wywołań samej siebie. Przykład: 

unsigned int fib(unsigned int n){
	if (n <= 1) return n;
	return fib(n-2) + fib(n-1);
}

Mamy dwa przypadki brzegowe: dla n=0 i n=1 (pierwszy return). Rekurencja jest wywoływana przed zwróceniem wartości w drugim returnie (nalezy zauważyć, że funkcja dwa razy wywołuje samą siebie!).

Konstrukcje Scheme dla programistów C/C++

Z przymrużeniem oka ;)

C/C++ Scheme
Przypisanie wartości 
c = 123;
 
(define c 123)
W Scheme jako takim nie ma zmiennych! Wszystkie obiekty są traktowane jako stałe i nie mogą się zmieniać. Można co najwyżej w głównym programie przedefiniować co kryje się pod napisem np. c.
Operacje arytmetyczne 
c = a + b;
c = a - b;
c = a / b;
c = a * b;
 
(define c (+ a b))
(define c (- a b))
(define c (/ a b))
(define c (* a b))
Scheme wykorzystuje "funkcyjną" - prefiksową notację, nawet dla standardowych operatorów dwuargumentowych!
definicja funkcji 
int foo(int a, int b, int c){
	return a + b - c;
}

int boo(int a, int b){
	b = a * a - b;
	a = a - b * b;
	return a + b;
}
 
(define foo (lambda (a b c) (
	(- (+ a b) c)
)

(define boo (lambda (a b) (
	(+ (- (* a a) b) (- a (* b b) ))
)
Jak widać w scheme nie mozna wyliczać wartości krok po kroku w zmiennych tymczasowych - trzeba wszystkie obliczenia funkcji zawrzeć w jednej instrukcji ewaluacji. Stąd zaleca się pisanie prostych, krótkich funkcji (i dobrze komentować! Dla własnego dobra!).
Wywołanie funkcji 
foo(1, 2, 3)
 
(foo 1 2 3)
W Scheme zawsze należy pamiętać o spacji po nazwie funkcji, jest to szczególnie ważne przy operatorach typu +, -, /, *, itp.
Lista 
struct ListElem{
	int data;
	ListElem* next;
}

//pomocnicza
void add(ListElem* head, int x){
	ListElem* e = new ListElem();
	e->data = x;
	e->next = head;
	head = e;
}

int head(ListElement* h){
	return h->data;
}

ListElement* tail(listElement* head){
	return head->next;
}

//stworzenie listy pustej
ListElement* lista;
//dodajemy elementy do listy pustej
add(lista, 4);
add(lista, 3);
add(lista, 2);
add(lista, 1);
 
;stworzenie listy pustej
(define pusta '())
;stworzenie listy 4 elementów
(define lista '(1 2 3 4))
;dodanie elementu na początek listy (*)
(define lista (cons 0 lista))
UWAGA! Powyższego przykładu proszę nie rozumieć dosłownie, ponieważ oba języki programowania mają troche inne zadania. W C/C++ tworzymy programy operujące na bardzo podstawowych, "informatycznych" typach danych - tablice, struktury, itp. Aby otrzymać bardziej złozone, "teoretyczne" struktury musimy je sami napisać (tak jak w przykładzie), albo skorzystać z gotowych bibliotek (np. STL). Scheme działa na poziomie "teoretycznym" - nie ma w nim wskaźników, iteratorów, "programistycznych "struktur danych, itp. Za to od razu, z definicji języka otrzymujemy struktury danych "teoretyczne" - przedewszystkim listy.

(*) Proszę pamiętać, że w Scheme lista jest zdefiniowana rekurencyjnie, jako lista pusta '() lub para składająca się z głowy (head) bedącej czymkolwiek, oraz ogona (tail) będącego listą (tu jest rekurencja!). Stąd możemy użyć funkcji stworzenia pary (cons) aby dodać element na początek listy. 
							
							
								
						
							


							
								
					

				

				

					
Jak pisać i czytać napisy w scheme

					
Należy pamiętać o paru zasadach:

					
    
						
  1. Wszystko w scheme jest wyrażeniem symbolicznym. Literały (liczby, napisy, znaki) same w sobie są wyrażeniem symbolicznym. Ewaluacja funkcji (fun ...) jest wyrażeniem symbolicznym. Definicja funkcji (lambda (params...) ... ) jest wyrażeniem symbolicznym. Stąd mozna je wykorzystywać wszędzie gdzie można wstawiać wyrażenie symboliczne!
    2. 
						
  2. Nalezy uważać na liczbę nawiasów ( i ), a najlepiej wypracować sobie sposób robienia wcięć w kodzie. Dla ułatwienia poniżej podam swoj system.
    3. 
						
  3. Nie należy przesadzać z ilością nawiasów ( i ) aby uzyskać "bardziej czytelny" kod. Napisy (fun 1 2) i ((fun 1 2)) wcale nie są równoważne. Pierwszy jest ewaluacją funkcji fun na argumentach 1 i 2, drugi jest ewaluacją tego co zwróci ewaluacja funkcji fun na argumentach 1 i 2. Jesli funkcja fun zwraca dla 1 i 2 wartość 5 to pierwszy napis spowoduje wyświetlenie na ekranie liczby 5 a drugi spowoduje błąd wykonania!
    4. 						
						
  4. Należy pamietać, żeby zwracając z funkcji wartość będącą literałem nie brać jej w nawiasy ( i ), gdyż Scheme zinterpretuje to jako ewaluacje funkcji (ponieważ literał sam z siebie jest wyrażeniem symbolicznym)
    5. 
						
  5. Zwracanie wartości będącej listą realizujemy poprzez '(1 2 3 4) (UWAGA: nie przez ('(1 2 3 4)) - gdyż '(1 2 3 4) jest wyrażeniem symbolicznym, tak samo jak literał! Stąd ('(1 2 3 4)) będzie próbą ewaluacji funkcji!)
    6. 
					

					
Jak czytać zapisy w scheme?

					

						

							

								
									

(define x 11)
							
									
										
								
									(matematycznie) Niech x bedzie równe 11 

									(programistycznie) Zdefiniuj wartość x jako 11
										
							

							

								
									

(lambda (a b) (+ a b))
							
									
										
								
									funkcja przyjmująca dwa parametry i zwaracająca ich sumę
								
							

							

								
									

(define f (lambda (a b) (+ a b)))
							
									
										
								
									(matematycznie) Niech f bedzie funkcją N x N -> N taką, że f(a,b) = a + b

									(programistycznie) Zdefiniuj funkcję o nazwie f przyjmującą dwa argumenty i zwracającą ich sumę
										
							

							

								
									

(define f 
	(lambda (x) 
		(if (> x 0)
			(- x 1)
			(+ x 1)
		)
	)
)
							
									
										
								
									(matematycznie) Niech f bedzie funkcją taką że
     

									(programistycznie) Zdefiniuj funkcję o nazwie f która dodaje do x 1 jesli jest mniejszy bądz równy od 0 a odejmuje 1 w przeciwnym przypadku.
										
							
							
						
						
					

					
Proponowany sposób na robienie wcięć

					

;definicja funkcji
(define f
	(lambda (params)
		wyrsymb
	)
)
;przykład
(define f 
	(lambda (a b c)
		(+ (+ a b) c)
	)
)

;if
(if war
	wyrsymb_1
	wyrsymb_2
)

;przykład
(if (> a 0)
	(- a 1)
	(+ a 1)
)

;if połączony z definicją funkcji
(define f 
	(lambda (a)
		(if (> a 0)
			(- a 1)
			(+ a 1)
		)
	)
)

;wywolanie rekurencyjne funkcji
(define f 
	(lambda (params)
		(if warunek_stopu
			wyrsymb_1 	;jeśli baza indukcji
			(...) 		;w przeciwnym razie coś co zawiera odwołanie do f
		)
	)
)
;przykład
(define f 
	(lambda (l)
		(if (eqv? l '())
			0 	
			(+ (car l) (f (cdr l)) )
		)
	)
)


					
					

						W ostatnim przykładzie proszę zwrócić uwagę na brak nawiasów wokół 0 (0 jest literałem, a więc wyrażeniem symbolicznym samym w sobie), oraz na użycie listy wpisanej jako literał poprzez '().
					

					

						Warto jeszcze przeczytać całą definicję f z podziałem na linijki kodu:

						
    
							
  1. Niech f będzie... 
    2. 
							
  2. ... funkcją przyjmującą jeden parametr l ...
    3. 
							
  3. ... która jesli l jest listą pustą zwraca ... 
    4. 
							
  4. ... 0 ...
    5. 
							
  5. ... w przeciwnym razie zwraca sumę głowy listy //(car l)// i wywołania rekurencyjnego f na ogonie listy //(cdr l)//
    6. 
						
											
						Pytanie kontrolne: jaką wartość zwraca f dla listy (1 2 3 4)? Co zwraca f?