Na početnu stranicu! Udruga Darovitih Informatičara Rijeke Na glavni izbornik!

logo / pascal?

Nema uopće diskusije o tome tko vlada u školstvu u Hrvatskoj (Pascal), a također i u većini ostalog dijela svijeta. No interesantno je pogledati što se događa (od 1984), nakon objavljivanja knjige SICP - Structure and Interpretation of Computer Programs, H. Abelson,... u USA. Od tog trenutka na M.I.T-u (Massachusetts Institute of Technology - mislim da ne moram objašnjavati što ovo ime znači medju univerzitetima u svijetu), Pascal se ne uči, a svi studenti (computer science i electrical engeneering) moraju proći SICP predavanja. SICP je baziran na Scheme. Od tada (1984) sve više Američkih univerziteta prelazi, ili paralelno drži predavanja na Scheme. I "ostatak" svijeta slijedi taj trend, a u tome prednjači Francuska. Srednje škole još uvijek kasne, ali se i tu stvar kreće. Oko 35 gimnazija u svijetu drži predavanja na Scheme (gotovo sve su u USA).
Sigurno se pitate - i kakove to sada veze ima sa Logom? Veza je vrlo jednostavna: Logo i Scheme su oboje verzije Lispa. U većini Scheme knjiga, autori u uvodu daju ovakovu primjedbu: Ne tražimo nikakovo predznanje, ali ako nešto i znate, neka to nikako ne bude Pascal nego Logo.

U čemu je onda bitna razlika? U teoretskim postavkama jezika. FORTRAN obitelj (u koju spadaju i Pascal i basic) nema čiste matematičke osnove - šokantno? Sigurno, jer FORTRAN je i danas primarni jezik za rješavanje matematičkih problema.

Evo u čemu je ta bitna razlika, koja iz korijena mijenja stil programiranja:

Uzmimo bilo koju matematičku funkciju; f(x) = 6x - 2
Pri rješavanju ove funkcije, (matematički) mi tražimo vrijednost varijable x. Znamo da x ima vrijednost i znamo da se ta vrijednost x-a tokom procesa izračunavanja neće promijeniti. Ako je to u matematici tako, zašto onda pascal krši to pravilo i postavlja osnove svog algoritmiranja na ovakovom principu: x := x + a . Mislim da nam to u matematici ne bi palo na pamet.

Zato Scheme inzistira na funkcijskom modelu programiranja: nema mijenjanja vrijednosti varijable unutar jedne funkcije (procedure), to jest unutar jedne invokacije funkcije. Scheme je u tom principu najstroži, Common Lisp malo blaži, a Logo (na žalost) najblaži i dozvoljava konstrukcije kao
make "x :x + :a . Ta popustljivost Loga dovela je do situacije da se kod nas (u školama i na takmičenjima) Logo tretira kao loša verzija Pascala.

Ako vam ova teoretska rasprava ništa ne znači, pogledajmo neke primjere:

1) Rjesenje Fibonacci algoritma:

	fib(0) = 0
	fib(1) = 1
	za sve (n > 1): fib(n) = fib(n - 1) + fib(n - 2)

1a) Iz knjige Programski jezik LOGO (Ines Kniewald)

 	TO FIB.NIZ :N
	MAKE "A 1
	MAKE "B 1
	PR :A
	PR :B
	REPEAT :N - 2 [MAKE "C :A + :B PR :C MAKE "A :B MAKE :B :C]
	END

Dakle očigledno kršenje matematičkog modela rješavanja funkcije (višestruko uzastopno mijenjanje vrijednosti varijabli A, B i C unutar jedne invokacije funkcije). Osim toga, još važnije od prijašnjeg razloga: pogledajmo matematičko rješenje (podcrtana linija gore) i usporedimo je sa REPEAT linijom u programu (koja zapravo računa niz). Da li nas logika REPEAT linije uopće podsjeća na gore postavljenu funkciju? Mene sigurno ne!

1b) Iz knjige Scheme & the Art of Programming (G. Springer & D.P. Friedman)
(primjer preveden na Logo sintaksu)

	to fib :n
	if :n < 2 [output :n]
	output (fib :n - 1) + (fib :n - 2)
	end

Nema uopće mijenjanja vrijednosti varijabli a usporedba matematičkog rješenja i programskog rješenja (output linije) govori sama za sebe. Da budem sasvim pošten 1a primjer ispisuje cijeli fibonacci niz, dok 1b vraća samo fib(n), ali to teoretski ništa ne mijenja na stvari. Oni oštrog oka ce primijetiti da je 1b primjer neefikasan jer se radi o višestrukoj rekurziji i za veće :n će se isti fib(n) računati mnogo puta. No i za to postoji rješenje:
Iteracija ili tail rekurzija.

1c) Moja obrada iterativnog algoritma iz SAP knjige
(da uskladim sa 1a primjerom - ispisuje cijeli niz)

	to fib.niz :n
	fib.it :n 0 1
	end

	to fib.it :n :acc1 :acc2
	pr :acc2
	if equalp :n 1 [stop]
	fib.it :n-1 :acc2 :acc1+:acc2
	end

Ovaj pristup je savršeno efikasan, a i dalje ne krši pravila funkcijskog programiranja - nema mijenjanja vrijednosti varijabli unutar procedure. Jedino nije matematički tako jasan kao 1b.

Drugi primjer: Veoma interesantan zadatak sa državnog takmičenja u Zadru 1997. godine.

Trebalo je napisati proceduru sort :ucenici, koja će sortirati podatke iz liste :ucenici. Sortirana lista je izlaz iz procedure sort.

Lista :ucenici ima slijedeći format:

    - sastoji se od riječi
    - sadrži podatke o učenicima: razred i ime učenika
    - na neparnim mjestima su oznake razreda koji učenici pohađaju (jedna riječ)
    - na parnim mjestima se nalaze imena učenika (jedna riječ)
    - na primjer: imamo 4 učenika:

      - Marek koji ide u 8a razred
      - Sandra koja ide u 6a razred
      - Diggy koji ide u 7a razred
      - Alan koji ide u 7a razred


  • Lista :ucenici izgleda ovako:

      [8a marek 6a sandra 7a diggy 7a alan]

    - riječi u listi nemaju nikakovo ograničenje (mogu biti ili samo slova ili samo brojke ili i jedno i drugo)
    - može postojati više učenika sa istim imenom, a da idu u različite razrede
    - u istom razredu može postojati više učenika sa istim imenom
    - maksimalan broj učenika je neograničen

Sortiranje se vrsi slijedećim redosljedom:

    1) prvo se članovi sortiraju po razredima od nižeg prema višem: 1a marek dolazi prije 2a marek
    2) zatim se sortiraju unutar razreda po učenicima. 2a marek dolazi prije 2a sandra.

Izlazni podatak je lista koja sadrzi sortirane podatke iz liste :učenici.

2a) Rješenje sastavljača zadatka (Mario Milešić), dato kao službeno rješenje na natjecanju:

TO SORT :UCENICI
	IF (LIST?:UCENICI)=:FALSE PRINT[ULAZNI PODATAK MORA BITI LISTA] STOP
	IF (EMPTY?:UCENICI)=:TRUE PRINT[PRAZNA LISTA] STOP
	IF NOT ((REMAINDER COUNT:UCENICI 2)=0) PRINT [NEPARAN BROJ PODATAKA] STOP
	MAKE"BRUC (COUNT:UCENICI)/2
	MAKE"A ARRAY FPUT:BRUC [2]
	FILLARRAY :A  :UCENICI
	SORTIRAJ
	MAKE"SUCENICI [ ]
	FOR "I 0 (:BRUC-1) [MAKE"SUCENICI SE:SUCENICI AGET:A FPUT:I[0]\
				 MAKE"SUCENICI SE:SUCENICI AGET:A FPUT:I[1]]
	OP:SUCENICI
END
TO SORTIRAJ
	MAKE"GRANICA :BRUC-2
	MAKE"GOTOVO:FALSE
	WHILE [:GOTOVO=:FALSE] [MAKE"GOTOVO:TRUE \
			FOR "I 0 :GRANICA [IF ZAMJENITI=:TRUE ZAMJENI]\
			MAKE"GRANICA:GRANICA-1]
END
TO ZAMJENITI
	IF (AGET:A FPUT:I[0]) = (AGET:A FPUT:I+1 [0] THEN \
		IF (AGET:A FPUT:I[1]) > (AGET:A FPUT:I+1 [1] THEN OP:TRUE
	IF (AGET:A FPUT:I[0]) > (AGET:A FPUT:I+1 [0] THEN OP:TRUE
	OP:FALSE
END
TO ZAMJENI
	MAKE"POM ARRAY 2
	ASET :POM 0			AGET:A FPUT:I [0]
	ASET :POM 1			AGET:A FPUT:I [1]
	ASET :A FPUT:I [0]		AGET:A FPUT:I+1 [0]
	ASET :A FPUT:I [1]		AGET:A FPUT:I+1 [1] 
	ASET :A FPUT:I+1 [0]		AGET:POM 0
	ASET :A FPUT:I+1 [1]		AGET:POM 1
	MAKE"GOTOVO:FALSE	

O ovom rješenju bi se moglo puno toga napisati i sa aspekta Loga i sa aspekta Pascala - jer ovo je očigledno Pascal rješenje.

Samo kratka Pascal primjedba: zar u ovako malom problemu čak 6 globalnih varijabli ... ccc

A sad malo sa Logo aspekta:

a) Rješavatelj očigledno vjeruje da je najbolji način sortiranja liste, tako da ju se pretvori u array (naravno - Pascal odgoj).
b) Iako Logo ne insistira tako strogo na sintaksi kao Pascal, sintaksu ipak ima - a ovaj program je krši nemilosrdno. Nazalost PC Logo to izgleda velikodušno dozvoljava - evo još jednog razloga za prebacivanje na ucblogo.
c) Upotreba veoma "interesantnih" konstrukcija, koje nameću pitanje da li rješavač razumije Logo semantiku?

	 IF (EMPTY?:UCENICI)=:TRUE PRINT.....

To bi valjda trebalo izgledati ovako

	 IF EMPTY? :UCENICI [PRINT .....

d) Elegancija i sigurnost nekog rješenja, otprilike su obrnuto proporcionalni broju upotrijebljenih varijabli, a koliko vidimo ovdje ih (uključujući indexe i switch-eve) zaista ima dosta.

2b) Logo rješenje (Hrvoje Blažević):

to half.list :l
if (count :l) < 2 [op :l]
op fput first :l half.list bf bf :l
end

to merge :l1 :l2
if emptyp :l1 [op :l2]
if emptyp :l2 [op :l1]
if beforep first :l1 first :l2 [op fput first :l1 merge bf :l1 :l2]
op fput first :l2 merge :l1 bf :l2
end

to merge.sort :l
if (count :l) < 2 [op :l]
op merge merge.sort half.list :l merge.sort half.list bf :l
end

to rastavi :l
op map.se [[x] [op list reverse bf member "_ reverse :x bf member "_ :x]] :l
end

to sastavi :l
op (map [[x y] [op (word :x "_ :y)]] half.list :l half.list bf :l)
end

to sort :ucenici
if or emptyp :ucenici not equalp remainder (count :ucenici) 2 0~
   [op [Error: neparni ili prazni input]]
op rastavi merge.sort sastavi :ucenici
end

Prve tri procedure half.list, merge i merge.sort, su primjer standardnog sortiranja u Lispu - može ih se doslovno dignuti iz ovog programa i ubaciti u bilo koji program gdje treba nesto sortirati. Dakle ako maknemo njih, ostajemo sa tri procedure sort, sastavi i rastavi - ukupno 4 programske linije za rješenje problema. Ovaj program ce raditi samo na ucblogu (i MSWLogu) - niti jedan drugi (uključujući i sve komercijalne verzije) nema šanse sa ovim kodom, radi upotrebe high-order funkcija map i map.se te lambde (bezimene funkcije).
U istom (funkcijskom) stilu bi se dalo riješiti i sa PC Logom, ali bi program porastao za jednu proceduru i jos nekoliko linija.

Globalnih varijabli uopće nema, nema niti jedan "make", a sve procedure imaju samo po jedan argument (varijablu) osim merge i jedne lambde (unutar sastavi) koje imaju dva argumenta.

Svrha ovih usporedbi raznih rješenja nije bila omalovažavanje rješavača "pascal" rjesenja nego dokazivanje slijedeće činjenice:

Kod nas je izgleda uvriježeno mišljenje da ako znaš basic ili Pascal onda "jasno" znaš i Logo, jer to je "dječja igra". Mislim da sam u ovih nekoliko primjera dokazao, da ništa ne može biti dalje od istine.

2c) Logo rješenje (Hrvoje Blažević):

Za one koji žele još kraće rješenje, evo ga (poziva se umjesto procedure sort, procedura skola):

to skola :l
localmake "n quotient count :l 2
if or emptyp :l not equalp int :n :n [op [Error: neparni ili prazni input]]
op reduce "se (sort [[x] [op word first :x last :x]] cascade :n [lput list first ? first bf ? bf bf ?] :l)
end


to sort :f :lst
if emptyp :lst [op :lst]
localmake "a reduce [[x y] [op ifelse beforep invoke :f :x invoke :f :y [:x] [:y]]] :lst
op fput :a sort :f filter [[x] [op not .eq :x :a]] :lst
end

Vaše mišljenje i primjedbe pošaljite na:
Hrvoje.Blazevic@ri.tel.hr