Legarea variabilelor. Recursivitate
În LISP argumentele unei proceduri sunt transmise prin valoare
(ca în limbajul C). La intrarea în procedură
parametrii sunt legaţi la argumente devenind variabile
legate, iar la ieşirea din procedură variabilele
legate de procedură primesc vechile valori. Variabilele folosite
într-o procedură dar care nu sunt parametrii se numesc variabile
libere în raport cu acea procedura şi valoarea lor
este determinată lexical.
Primitiva LET
LET leagă variabile şi le dă valori. (SETQ doar dă valori!)
Sintaxa:
(let ((<parametru
1> <valoare initiala 1>)
(<parametru
2> <valoare initiala 2>)
(<parametru
n> <valoare initiala n>))
...
<corpul
lui let>)
Legarea este valabilă doar în interiorul corpului lui let.
LET calculează toate valorile initiale înainte de legare (atribuirea
se face "în paralel", spre deosebire de SETQ care atribuie
pe masură ce evaluează).
Există varianta LET* care leagă variabilele dar atribuie valorile secvenţial
(ca procedura SET).
Şi SETQ are varianta PSETQ
care atribuie valorile în "paralel".
| SETQ şi LET - secvenţial şi paralel |
| (SETQ a 'a b 'b c 'c d 'd)
D
(LET ((a 'alfa) (b 'beta) (ab (LIST a b))) ab)
;LET paralel
(A B)
(LET* ((c 'gamma) (d 'delta) (cd (LIST c d))) cd) ;LET secvenţial
(GAMMA DELTA)
(SETQ a 'alfa b 'beta ab (LIST a b)) ;SETQ secvenţial
(ALFA BETA)
ab
(ALFA BETA)
(PSETQ c 'gamma d 'delta cd (LIST c d)) ;SETQ paralel
nil ; PSETQ treturnează totdeauna nil
cd
(C D)
|
Primitiva FUNCALL
FUNCALL permite apelul indirect al funcţiilor.
| FUNCALL |
|
(setq operatie '+)
+
(funcall operatie 2 3 4)
9
(setq operatie '*)
*
(funcall operatie 2 3 4)
24 |
Recursivitate
Atunci cănd o procedură se apelează pe sine, direct
sau indirect, pentru a rezolva o parte din problemă, avem de a
face cu recursivitate.
Calculul lui m^n (n
întreg) se poate face recursiv cu formula:
/ m * m^(n-1),
pentru n > 0
m^n = {
\ 1, pentru n = 0
Programul implementat în LISP este:
| Exponenţial |
|
(defun our-expt (m n)
(cond ((zerop n) 1) ;
n=0?
(t
(* m (our-expt m (- n 1)))))) ; apel recursiv
|
| Problema 1 |
| Implementaţi recursiv funcţia factorial.
|
| Problema 2 |
| Implementaţi recursiv şirul lui Fibonacci.
|
| Problema 3 |
| Implementaţi recursiv funcţia member, care
testează dacă un element este membru al unei liste.
|
| Problema 4 |
| Implementaţi funcţia (trim-head
l n) care elimină din lista l
primele n elemente.
|
| Problema 5 |
| Implementaţi funcţia (trim-tail
l n) care elimină din lista l
ultimele n elemente.
|
| Problema 6 |
| Implementaţi (count-atoms
l) care numară toţi atomii listei l, inclusiv cei din
eventualele liste imbricate.
|
| Problema 7 |
| Presupuneţi că
+ si - pot fi folosite doar pentru
a incrementa sau decrementa un număr cu unu (eventual scrieti
procedurile inc si dec).
Scrieţi o procedură recursivă pentru adunarea a
două numere întregi pozitive.
|
| Problema 8 |
| Implementaţi procedura reverse.
|
| Problema 9 |
| Implementaţi predicatul presentp
care determină dacă un atom apare oriunde în interiorul
unei liste.
|
| Problema 10 |
| Implementaţi procedura squash care primeşte
o listă generalizată şi returnează lista tuturor atomilor gasiţi.
|
Probleme
Problema 1. Factorial
Problema 2. Fibonacci
Problema 3. Member
Problema 4. Trim-head
Problema 5. Trim-tail
Problema 6. Count-atoms
Problema 7. Însumare, scădere
Problema 8. Reverse
Problema 9. Presentp
Problema 10. Squash
|