Alex = Alex + 1
November 20th, 2007 Alex
It always takes longer than you expect, even when you take into account Hofstadter’s Law.
Hofstadter’s Law
Mă simt limitat de paradigmele cu care am fost obișnuit lucrând cu Java sau C++ și-mi simt limitările când programez în limbaje mai funcționale gen Javascript, Ruby sau Python. Desigur, toate 3 acceptă aceleași idiome, dar degeaba folosești limbaje de scripting dacă nu-ți schimbi mentalitatea.
Cu părere de rău mă surprind mereu traversând vectori în javascript folosind
for (var i=0; i<arr.length; ++i) …
Sau în Python mă trezesc căutând maximul unui șir folosind:
for i in range(0,len(arr)): if max < v[i]: max = v[i]
Lame.
Limbajele cu metafore funcționale sunt special proiectate pentru definiții recursive iar eu nu sunt antrenat să gândesc recursiv.
Sunt un “blob programmer” și este timpul pentru o operație pe creier 
Am început să studiez Structure and Interpretation of Computer Programs (Abelson & Sussman). Este cursul de computer science introductiv de la MIT, și deși este considerat a fi de nivel introductiv, este extrem de bun la introducerea de tehnici recursive de programare.
Limbajul folosit în curs este Scheme, un dialect de LISP extrem de ușor de folosit și de învățat. Și deși aveam o idee extrem de bună despre capabilitățile de meta-programare din LISP, singurul limbaj de programare high-level unde diferența dintre structuri de date și proceduri nu există - dar nu aveam idee până unde se ajunge.
Un concept care mi-a spart toate perspectivele este că Scheme poate fi definit complet în termeni Scheme … fiind astfel recursivă chiar și definiția limbajului. Pentru a exemplifica voi defini principalele proceduri pe care se bazează programarea în Scheme folosind tot Scheme …
Să definim o procedură ce ia ca parametru o listă și un scalar și înmulțește fiecare element cu acel scalar, rezultatul fiind tot o listă.
Pseudocodul ar fi:
1. daca lista este nula atunci returneaza o lista goala, altfel …
2. extrage primul element din lista si inmulțește-l cu scalarul
3. executa recursiv metoda pentru restul listei (in afara de elementul extras)
4. concateneaza rezultatul de la pasul 2 cu lista rezultata la pasul 3 si intoarce
rezultatul
Codul în Scheme este …
(define (scale-list s l)
(if (null? l)
nil
(cons (* (car l) s)
(scale-list s (cdr l)))))
Codul este destul de citibil dacă clarificăm funcțiile folosite …
- funcția (cons a b) returnează o pereche (aka listă) formată elementele a și b
- funcția (car L) returnează primul element din listă astfel încât (car (cons a b)) => a
- funcția (cdr L) returnează al 2-lea element din pereche (restul listei în afară de primul element), astfel încât (cdr (cons a b)) => b
- funcția (null? L) returnează adevărat dacă lista dată ca parametru este goală
În mod normal cons, car și cdr folosesc primitive predefinite din LISP (aka liste), dar le putem redefini în termeni de proceduri (fara să avem nevoie de primitive magiceale limbajului) astfel -
(define (cons a b)
(lambda (nr)
(if (= nr 1) a b)))
(define (car list)
(list 1))
(define (cdr list)
(list 2))
Mai sus am definit cons ca fiind o procedură ce întoarce o altă procedură, procedură ce acceptă un parametru ce indică indexul elementului (din cele 2 elemente) ce trebuie returnat. Procedurile car și cdr iau ca parametru această procedură creată de cons și o apelează pentru a returna cele 2 elemente.
Pentru a înțelege conceptul mai bine, hai să scriem același cod în Python -
def cons(a,b): return lambda(nr): a if nr==1 else b
def car(list): return list(1)
def cdr(list): return list(2)
OK, parcă aud … și ce dacă?
Eh, păi hai să dăm definiția unei liste ce conține toate numerele de la 1 la 4 (o terminăm cu un null) …
(define 1-to-4
(cons 1 (cons 2 (cons 3 (cons 4 nil)))))
sau în Python …
one_to_four = cons(1, cons(2, cons(3, cons(4, False))))
Și revenind la funcția scale-list, am putea generaliza procesul …
(define (map p l)
(if (null? l)
nil
(cons (p (car l))
(map p (cdr l)))))
iar functia originala o putem defini astfel:
(define (scale-list s l)
(map
(lambda (x) (* x s))
l))
Plecând de la cons, car și cdr, funcții ce îndeplinesc următorul contract -
- (car (cons a b)) => a
- (cdr (cons a b)) => b
putem defini orice structuri de date high-level, indiferent de complexitate, deoarece funcțiile returnează tot obiecte ce pot fi combinate cu alte obiecte (adică în termeni matematici obiectele din LISP sunt închise sub operațiile cons, car și cdr), adică funcțiile pot combina orice structuri de date ar fi conținute de variabilele a sau b. În curs se dă un exemplu de operație din alt limbaj de programare ce nu este închidere pentru obiectele limbajului - în Fortran poți avea vectori de primitive, dar nu poți avea vectori de vectori.
Este într-un fel trist deoarece astfel de tehnici sunt cunoscute din anii 70-80, iar abstractuzările posibile sunt nelimitate. Dar nu spuneți managerilor voștrii asta 
Toate aceste definiții vin din SICP. Cursurile video și cartea sunt disponibile gratuit online.
Posted in edu, learning | 5 Comments »