Structuri Si Interpretari DE Programe
CAPITOLUL I
INTRODUCERE
În procesele de calcul un rol important îl au procedurile în proiectarea programului . }tim cum să folosim datele primitive (numerele) și operatorii primitivi (operatori aritmetici) , cum să combinăm procedurile compuse prin compunere și prin folosirea parametrilor și cum să abstractizăm procedurile folosind definiția. O procedură poate fi privită ca o formă locală de realizare a procesului și am realizat , judec[\i de analize algoritmice simple a unor modele comune pentru procese cum ar fi reprezentarea prin proceduri . Programele sunt în mod obișnuit proiectate pentru a modela fenomene complexe , dîndu-ne posibilitatea de a manipula și de a raționa în termenii unor metode generale de calcul .Aceasta este astfel esența programării.
În acestă lucrare ne vom ocupa de date mai complexe .Toate procedurile operează pe date numerice simple și datele simple nu sunt suficiente pentru o mulțime de probleme pe care vrem să le apelăm care trebuie să construiască obiecte computaționale compuse din mai multe părți într-o anumită ordine pentru a modela fenomene din viața reală și care au mai multe aspecte . Abstactizările se construiesc mai int`i prin combinarea procedurilor pentru a forma proceduri compuse . Acum ne îndreptam atenția spre alt aspect cheie al oricărui limbaj de programare : mijloacele care să asigure construcția abstractizărilor prin combinarea obiectelor de date pentru a forma date compuse .
De ce vrem date compuse într-un limbaj de programare? Din același motiv din care vrem și proceduri compuse: să ridicăm nivelul conceptual la care vrem să proiectăm programele, să creștem modularitatea proiectelor , să mărim puterea expresivă a limbajului nostru . Cum abilitatea de a defini procedurile ne dă posibilitatea să lucrăm cu procese la cel mai înalt nivel conceptual mai înalt decît cel al obiectelor de date primitive limbajului.
Considerăm c[ avem ca sarcină să proiectam un sistem ce rezolvă operații aritmetice cu numere raționale . Ne putem imagina un operator “ + rat “ care are două numere raționale drept argumente și produce suma lor. Folosind termeni de date simple , un număr rațional poate fi gîndit ca doi întregi un numărator și un numitor.
Astfel putem proiecta un program în care fiecare număr rațional ar fi reflectat de doi întregi (un numărător și un numitor) și unde “ +rat “ ar fi implementat ca doua proceduri (una producînd numărătorul sumei și cealaltă numitorul).Dar aceasta ar fi dificil deoarece ar fi necesar să urmărim explicit ce numărători corespund la ce numitori. Într-un sistem ce intenționează să facă multe operații cu multe numere raționale astfel de detalii sporesc dezordinea programării în mod substanțial, produse în mintea noastră pentru realizarea programelor .
Ar fi mai bine dacă am putea “ asocia împreună “ un numărător și un numitor pentru a forma o pereche – un obiect de date compuse pe care programele noastre ar putea să-l manipuleze în așa fel încît să fie consistent în ceea ce privește ca numărul rațional să fie privit ca o singură unitate conceptuală.
Folosirea datelor compuse , de asemenea ne dă posibilitatea să sporim modularitatea programelor noastre . Dacă putem manipula numere raționale direct ca obiecte în sensul propriu , atunci putem separa partea din program care lucreză cu numere raționale pentru a vedea detalii de a reprezenta întregi. Tehnica generală de izolare a părților de program care se ocupă cu modul în care obiectele de date sunt reprezentate de părți din program în care obiectele de date sunt folosite este o metodologie de proiectare foarte puternică numită abstractizarea datelor.Vom vedea cum abstractizarea datelor face programele mai ușor de proiectat , întreținut și modificat .
Folosirea datelor compuse conduce la o reală creștere a puterii expresive a limbajului de programare . Să considerăm ideea formarii unei combinații liniare “ ax+by “.
Am putea scrie o procedură care ar accepta a,b,x și y ca argumentye și care ne-ar returna valoarea lui ax+by.Aceasta nu prezintă dificultate dacă argumentele sunt numere , deoarece putem defini procedura :
(define(linear-combination a b x y )
(+(* a x ) (* b y ) ) )
Dar să presupunem că nu lucrăm doar cu numere . Să presupunem că am vrea să exprimăm în termeni procedurali , ideea că cineva poate forma combinații liniare oricînd sunt definite adunări și inmulțiri pentru numere raționale , complexe , polinomiale etc.
Putem exprima aceasta ca o procedură de forma :
(define(linear-combination a b x y )
(add(mul a x ) (mul b y) ) )
unde add și mul nu sunt procedurile primitive + și * , ci mai degrabă operații mai complexe care ar rezolva operațiile pentru orice fel de date care sunt argumente pentru a , b , x și y . Punctul cheie este faptul că o singură combinație liniară este necesară pentru a ști despre a , b , x și y și operatorii add și mul vor rezolva manipulările în discuție . Din perspectiva procedurii combinației liniare este irelevant ce sunt a , b , x și y și chiar mai irelevant cum ar putea fi reprezentate în termeni de date primitive . Acest exemplu arată de ce este important ca limbajul de programare are abilitatea de a manipula obiectele compuse în mod direct : fără această abilitate , nu este posibil ca o procedură , ca și combinația liniară să-și treacă argumentele împreună cu add și mul fără să trebuiască să știm structura detaliată .
Începem acest capitol implementînd sistemul numerelor raționale aritmetice menționat mai sus . Acesta va forma fundalul pentru discuția asupra datelor compuse și a abstractizării datelor . Ca și la procedurile compuse principala problemă de adresare este aceea a abstractizării ca o tehnică de a păstra complexitatea , vom vedea cum abstractizarea datelor , ne dă posibilitatea înființării unor bariere de abstractizare printre diferite părți ale programului . Vom vedea că o cheie a formării datelor compuse este faptul că un limbaj de programare ar furniza un tip de liant încît datele simple să poată fi combinate pentru a forma date mai complexe. Sunt multe feluri de liante.Într-adevăr , vom descoperi cum să formăm date compuse fără să folosim deloc nici un fel de operație specială cu date ci numai proceduri.Aceasta va întuneca distincția dintre "proceduri" și "date". Vom explora de asemenea cîteva tehnici convenționale de reprezentare a secvențelor, arborilor și a expresiilor simbolice și vom aplica aceste tehnici la diferențierea simbolică , reprezentarea mulțimilor și codificarea informațiilor. Ne vom ocupa în continuare de problema de lucru cu date care pot fi reprezentate diferit prin diferite părți de program. Numerele complexe de exemplu, pot fi reprezentate fie în formă carteziană, fie în formă polară și pentru aplicații ar fi de dorit să putem folosi amîndouă reprezentări fară să sacrificăm abilitatea de a lucra în termeni de "numere complexe" abstracte.Aceasta duce la problema implementării unor operatori generici (cum sunt add și mul folosiți mai sus) care să trebuiască să opereze cu mai multe tipuri diferite de date. Menținînd modularitatea in prezența operatorilor generici se cer limitee de abstractizare mai puternice decît cele din cazul abstractizărilor de date simple și introducem programul de date directă ca o tehnică de proiectare puternică pentru a putea lucra cu aceasta complexitate.
Pentru a ilustra puterea acestui demers de a proiecta sistemul încheiem capitolul aplicînd ceea ce am învățat la implementarea unui pachet (de informații) pentru realizarea unor simboluri aritmetice la polinoame,în care coeficientul polinomului poate fi :întreg, numere raționale, complexe și chiar alte polinoame.
CAPITOLULII
Introducere în abstractizarea datelor
O procedură folosită ca un element în crearea unei proceduri mai complexe ar putea fi privită nu numai ca o colecție de operații particulare dar și ca o abstractizare procedurală. Aceasta înseamnă detaliile despre cum procedura a fost implementată ar putea fi ascunse și procedura în sine ar putea fi înlocuită de oricare altă procedură cu același comportament. Cu alte cuvinte am putea face o abstractizare care ar separa modul în care procedura ar fi folosită de detaliile despre modul în care procedura ar fi implementată în termenii unei proceduri primitive. Noțiunea analoagă pentru datele compuse se numește abstractizarea datelor. Abstractizarea datelor este o metodologie care ne dă posibilitatea să izolăm moodul în care un obiect de date compuse este folosit de detaliile modului de construcție din mai multe obiecte de date primitive.Ideea de bază a abstractizării datelor este de a structura programele care folosesc obiecte de date compuse în așa fel încît ele să poată opera pe date abstracte. Adică , programele noastre ar trebui să folosească datele în așa fel încît să nu facă nici o ipoteză asupra datelor care nu sunt în mod strict necesare pentru a rezolva sarcina imediată . În același timp o reprezentare concretă a datelor este definită în mod independent de programele care folosesc datele. Interfața dintre aceste două părți a sistemului nostru va fi o mulțime de proceduri numite selectori și constructori care implementează datele abstracte în termenii unei reprezentări concrete . Pentru a ilustra această tehnică vom lua în considerare modul de proiectare a unui set de proceduri pentru a manipula numere raționale .
2.1 Exemplu : Operatori aritmetici pentru numere raționale
Să presupunem că vrem să facem operații aritmetice cu numere raționale. Vrem să fie capabile să adune , să scadă , să înmulțească și să împartă și să testeze dacă două numere raționale sunt egale . Să presupunem că deja avem un mod de construcție a unui număr rațional dintr-un numărător și numitor . Presupunem , de asemenea , că dînd un număr rațional avem un mod de extragere sau selectare a numărătorului sau numitorului său. Să presupunem mai departe că și constructorul și selectorul sunt disponibile ca proceduri:
(make-rat <n> <d> ) returnează numărul rațional al cărui numărător este întregul <n> și al cărui numitor este întregul <d>.
(numer<x>) returneză numărul rațional <x>.
(denom<x>) returneză numitorul numărului rațional <x>.
Folosim aici o stategie puternică de sinteză : modul de gîndire dorit.
Nu am spus încă cum este reprezentat un număr rațional sau cum procedurile numer , denom și make-rat trebuie implementate . Chiar și așa dacă avem într-adevăr aceste trei proceduri am putea apoi să adunăm , scădem , să multiplicăm ,să împărțim și să testăm egalitatea folosind următoarele relații :
dacă și numai dacă
(define (+ rat x y )
(make-rat ( + ( * numer x)(denom y) )
(* denom x)(numer y) ) )
(* (denom x)(denom y) ) ) )
(define (- rat x y )
( make-rat (- ( * numer x )(denom y) )
( * denom x )(numer y) ) )
( *( denom x )(denom y) ) ) )
(define ( * rat x y)
( make-rat ( * ( numer x )(numer y) )
( * (denom x )(denom y) ) ) )
(define ( / rat x y )
(make-rat ( * numer x )(denom y) )
( * (denom x)(numer y) ) ) )
(define ( = rat x y )
( = ( * (numer x)(denom y ) )
( * (numer y )(denom x) ) ) )
Acum avem operatorii asupra numerelor raționale definiți în termeni de proceduri , selectori și constructori : numer, denom și make-rat. Dar nu le-am definit încă pe acestea . Ceea ce avem nevoie este un anumit mod de a asocia numărătorul și numitorul pentru a forma numărul rațional .
Perechi
Pentru a fi capabili să implementăm un nivel mai concret a abstractizării datelor noastre limbajul nostru furnizează o structură compusă numită pereche, care poate fi construită cu procedura primitivă cons. Această procedură depinde de două argumente și returnează un obiect de date compuse care conține cele două argumente ca părți. Dând o pereche putem extrage părțile folosrat ( * numer x )(denom y) )
( * (denom x)(numer y) ) ) )
(define ( = rat x y )
( = ( * (numer x)(denom y ) )
( * (numer y )(denom x) ) ) )
Acum avem operatorii asupra numerelor raționale definiți în termeni de proceduri , selectori și constructori : numer, denom și make-rat. Dar nu le-am definit încă pe acestea . Ceea ce avem nevoie este un anumit mod de a asocia numărătorul și numitorul pentru a forma numărul rațional .
Perechi
Pentru a fi capabili să implementăm un nivel mai concret a abstractizării datelor noastre limbajul nostru furnizează o structură compusă numită pereche, care poate fi construită cu procedura primitivă cons. Această procedură depinde de două argumente și returnează un obiect de date compuse care conține cele două argumente ca părți. Dând o pereche putem extrage părțile folosind procedurile primitive car și cdr. Astfel putem folosi
cons, car și cdr după cum urmează:
==>(define x (cons 1 2) )
x
==>(car x)
1
==>(cdr x)
2
Să notăm că o pereche este un obiect de date reale căruia și putem da un nume
și manipula exact ca orice alt obiect de date. Mai mult cons poate fi folosită
pentru a forma perechi ale căror elemente sunt perechi :
==>( define x ( cons 1 2 ) ) x
==>( define y(cons 3 4 ) ) y
==>(define z(cons x y ) ) z
==>(car (car z) ) 1
==>(car (cdr z) ) 3
În secțiunea 2.2 vom vedea cum această abilitate de combina perechi înseamnă că perechile pot fi folosite ca scop general de construcție în bloc de a crea tot felul de structuri complexe de date. Singura pereche de compuse primitive implementate de procedurile cons, car și cdr este singurul liant de care avem nevoie. Obiectele de date construite din perechi se numesc liste structurate de date.
Reprezentarea numerelor raționale
Perechile ne oferă un mod natural de a completa un sistem de numere raționale. În mod simplu reprezentăm un număr rațional ca o pereche de doi întregi un numărător și un numitor. Apoi make-rat, numer și denom sunt implementate după cum urmează:
(define (make-rat n d)(cons n d) )
(define (numer x)(car x) )
(define (denom x )(cdr x) )
De asemenea, pentru a afișa rezultatele calculului nostru putem alege să scriem un număr rațional, prin scrierea numărătorului, slash, și numitorului:
(define (print-rat x)
(newline)
(princ(numer x))
(princ “/”)
(princ(denom x))
Acum putem încerca funcțiile numărului rațional:
==>(define one-half(make-rat 1 2)) 1/2
=>(print-rat one-half) 1/2
==>(define one-third(make-rat 1 3 ) ) 1/3
==>(print-rat(+rat one-half one-third) ) 5/6
==>(print-rat(*rat one-half one-third) ) 1/6
==>(print-rat(+rat one-third one-third) ) 6/9
După cum arată exemplul final implementarea numărului rațional nu reduce numărul rațional la termeni mai mici. Putem remedia aceasta schimbând make-rat. Dacă avem o procedură gcd, ca cea din secțiunea 1.2.5, care produce cel mai mare divizor comun, a două numere întregi, putem folosi gcd pentru a reduce numărătorul și numitorul la cei mai mici termeni înainte de construirea perechii.
(define(make-rat n d)
(let ( (g(gcd n d) ) )
(cons(/n g )(/d g ) ) ) )
Acum avem :
==>(print-rat(+rat one-third one-third) ) 2/3
dorită. Modificarea a fost îndeplinită schimbând constructorul procedurii make-rat fără să schimbăm procedurile care implementează operatorii actuali cum ar fi +rat și *rat.
2.2 Bariere de abstractizare
Înainte de a continua cu mai multe exemple de date compuse și abstractizări de date să luăm în considerare câteva din problemele ridicate de exemplu numărului rațional. Am definit că operatorii numărului rațional în termen de constructori make-rat și selectori numer și denom. În general ideea care stă la baza abstractizării datelor este de a identifica pentru fiecare tip de obiect de date o mulțime de bază de operatori în termenii cărora toate manipulările obiectelor de date de acel tip vor fi exprimate și după aceea să folosim numai acei operatori în manipularea datelor.
Putem viziona structura sistemului nostru arătată ca în figura 2.1. Liniile orizontale subțiri reprezintă barierele de abstractizare care izolează diferite nivele ale sistemului. Programele care folosesc numere raționale manipulează singure în termenii unui operator furnizat pentru folosirea publică prin pachetul numărului rațional +rat, -rat, *rat, /rat, =rat. Acestea, în schimb, sunt implementate singure în termenii constructorului și selectorilor make+rat, numer și denom care la rândul lor sunt implementați în termeni de perechi. Detaliile despre cum perechile sunt implementate sunt irelevante pentru restul pachetului de numere raționale astfel încât perechile pot fi manipulate prin folosirea procedurii cons, car și cdr.
În consecință, procedurile la fiecare nivel sunt interfețele care definesc barierele de abstractizare și leagă diferite nivele.
Numere rationale in domeniul problemei
Reguli pentru numerele rationale aritmetice
Numere rationale ca perechi
Fig 2.1
Bariere de date abstracate in pachete de numere rationale
Aceasta idee simpla are mai multe avantaje.Unul dintre avantaje este acela ca face programele mai usor de intretinut si modificat. Orice structura de date comlexe poate fi reprezentata intr-o varietate de moduri cu structuri de date primitive furnizate de un limbaj de programare. Desigur alegerea reprezentarii influenteaza programul care opereaza asupra numerelor rationale; astfel daca reprezentarea trebuie schimbata la cîtva timp mai tîrziu toate programele de acest fel trebuie modificate corespunzător . Acestă sarcină poate fi una care ia mult timp și scumpă în cazul unor programe mai mari dacă nu dependența de reprezentare este limitată prin proiectarea cîtorva module de program. De exemplu, un mod alternativ de a adresa problema reducerii numărului rațional în termenii cei mai mici este de a rezolva reducerea de cîte ori avem acces la părțile unui număr rațional mai de grabă cînd îl vom construi. Aceasta conduce la proceduri constructori și selectori diferiți:
(define(make-rat n d)
(cons n d)
(define(numer x)
(let( (g(gcd(car x)(cdr x) ) ) )
(/(car x)g) ) )
(define(denom x)
(let( (g(gcd(car x)(cdr x) ) ) )
(/(cdr x)g) ) )
Diferenta între această implementare și cea anterioară este atunci cînd calculăm cel mai mare divizor comun. Dacă examinăm numerele raționale adesea ar fi bine să calculăm imediat cel mai mare divizor comun în construcția lor. Dacă nu ar putea fi mai bine să așteptăm pînă la timpul de acces sau vchiar la timpul de scriere pentru a calcula cel mai mare divizor comun. În orice caz cînd schimbăm de la o reprezentare la alta operatorii +rat,-rat și ceilalți nu trbuie modificați deloc.
Restringerea dependenței de reprezentare la cîteva proceduri de interfață ne ajută să proiectăm programe și la fel de bine să le modificăm deoarece ne permite să menținem flexibilitatea de a considera implementările alternative. Pentru a putea constinua cu exemplul nostru să presupunem că proiectăm un pachet de numere raționale și nu putem inițial decide dacă să rezolvăm cel mai mare divizor comun în timpul construcției sau în timpul selectării.
Metodologia de abstractizare a datelor ne dă un mod de a amîna această decizie fără să stabilim abilitatea de a face progrese în restul sistemului.
2.3 Ce se înțelege prin date?
Am început implementarea numerelor raționale în secțiunea 1.1 prin implementarea unor operatori de numere raționale +rat,-rat și ceilalți în temenii unor trei proceduri nespecificate make-rat, numer, denom. La acel punct ne-am putea gîndi la operatori ca fiind definiți în termeni ca obiecte de date(numărător,numitor și numere raționale) al căror comportament a fost specificat de ultimele trei proceduri, dar în mod exact, ce se înțelege prin date? Nu este de ajuns să spunem “ orice este implementat de selectorii și constructorii dați ” ,pentru clarificarea faptului că oricare di cele trei proceduri nu ar putea servi ca bază potrivită pentru implementarea numărului rațional. Avem nevoie să garantăm că dacă vom construi un număr rațional x dintr-o pereche de întregi n și d extrăgând numitorul și număratorul lui x și formând câtul ar trebui să producă numărul rațional =n/d . Cu alte cuvinte make-rat, numer și denom trebuie să satisfacă condiția ca pentru orice întreg n și d, dacă x este (make-rat n d), atunci :
De fapt, aceasta este singura condiție pentru care make-rat, numer și denom trebuie să îndeplinească pentru a forma o bază potrivită pentru reprezentarea unui număr rațional.În general ne putem gândi la date ca fiind definite de o anumită colecție de selectori și constructori laolaltă cu condițiile specificate ca aceste proceduri trebuie îndeplinite pentru o reprezentare validă. Acest punt de vedere poate servi să definim nu numai ”nivelul-înalt” de obiecte de date cum ar fi numerele raționale, dar și la nivele joase ale obiectelor . Să considerăm noțiunea de pereche pe care am folosit-o pentru a defini numărul rațional. Nu am spus de fapt niciodată că o pereche este numai ceea ce limbajul furnizează operatorii cons, car și cdr pentru operarea asupra perechilor. Dar singurul lucru pe care avem nevoie sa-l știm despre acești trei operatori este acela dacă liantul a două obiecte folosind cons putem recupera obiectele folosind car și cdr. Adică operatorii satisfac condiția ca pentru orice obiect x și y dacă z este (cons x y ) atunci (car z ) este x și ( cdr z )este y.Într-adevăr, am menționat că acești trei opertatori sunt incluși ca primitive în limbajul nostru . Totuși, orice triplă dintre procedurile care satisfac condiția de mai sus poate fi folosită ca bază pentru implementarea perechilor. Acest punct este ilustrat strict de faptul că am puitea implementa cons, car și cdr fără să folosim nici ostuctură de date ci folosind doar proceduri.Iată definițiile:
(define (cons x y )
(define(dispatch m)
(cond( (=m 0)x)
( (=m 1) y)
else(error “Argument not 0 or 1 –cons” m) ) ) ) dispatch)
(define(car z)(z 0) )
(define(cdr z)(z 1) )
Aceasta este o folosire extremă a procedurii și nu corespunde cu nimic ca noțiunea noastră intuitivă despre ce date ar trebui să fie. Cu toate acestea, tot ceea ce avem nevoie de făcut pentru a arăta că aceasta esteun mod valid de a reprezenta perechile este acela de a verifica faptul că aceste proceduri satisfac condiția dată mai sus.
Punctul subtil de notat este acela că valoarea returnată de (cons x y) este o procedură, adică procedura de expediere definită intern, care ia un singur argument și returnează fie x,fie y depinzând dacă argumentul este 0 sau 1. În mod corespunzător, (car z) este definit pentru a aplica pe z lui 0. Prin urmare, dacă z este procedura formată de (cons x y) atunci z corespunde lui 0, va produce pe x. Totuși, am arătat că (car(cons x y)) produce pe x așa cum am dorit. În mod similar, (cdr(cons x y)), aplică procedurii returnate de (cons x y) pe 1, care returnează pe y. De aceea această implementare procedurală a perechilor este o implementare validă și dacă vom accesa perechile folosind numai cons, car și cdr nu vom putea distinge această implementare de cea care folosește structuri de date “reale”.
Ideea acesteia nu este faptul că limbajul nostru lucrează în acest mod(sistemele Lisp implementează perechile în mod direct, di motive de eficiență), ci acela, că ar putea lucra în acest mod. Reprezentarea de mai sus, cu toate că este obscură este un mod perfect adecvat de a reprezenta perechile, deoarece îndeplinește singurele condiții pe care perechile trebuie să le îndeplinească. Ca o parte interesantă, vedem că abilitatea de a manipula procedurile ca obiecte furnizează în mod automat abilitatea de a reprezenta date compuse. Aceasta poate părea o curiozitate acum,dar reprezentarile procedurale de date vor juca un rol central în repertoriul nostru de peogramare. Acest stil de programare este adesea numit “ trecerea mesajelor” și îl vom folosi ca unealtă de bază în capitolul 3, cînd ne vom adresa cercetărilor de modelare și simulare.
2.4 Exemplu:Aritmetica de interval
Alyssa P.Hacker proiectează un sistem pentru a ajuta oamenii să rezolve problemele inginerești. O caracteristică pe care ea vrea s-o furnizeze în sistemul ei este abilitatea de a manipula cantități inexacte(cum ar fi parametrii măsurați ai invențiilor fizice) cu precizie știută în așa fel încît calculele sunt făcute cu cantități aproximative, rezultatele vor fi numere de precizie știută. Construcțiile electrice vor folosi sistemul Alyssey pentru a calcula cantitățile electrice. Este adesea necesar pentru constructorii de mașini electrice să calculeze valoarea rezistenței paralele Rp echivalentă a doi rezistori R1 și R2 ,folosind formula:
Valorile rezistenței sunt în mod normal cunoscute numai pînă la o anumită toleranță garantată de constructorul rezistorului. De exemplu, dacă veți cumpăra un rezistor cu eticheta “6,8 ohmi cu 10% toleranță” veți putea fi siguri numai de faptul că rezistorul are o rezistență între 6,8-0,68=6,12 și 6,8+0,68=7,48 ohmi. Astfel, dacă aveți un rezistor de 6,8 ohmi cu toleranță 10% în paralel cu un rezistor de 4,7 ohmi cu 5% toleranța, rezistența combinației poate fi limitată la aproximativ 2,5 ohmi(dacă cei doi rezistori sunt la limitele cele mai joase) și la aproximativ 2,97 ohmi(dacă cei doi rezistori sunt la limitele cele mai înalte).
Ideea Alyssey este de a implementa “aritmetica de interval” ca un set de operatori aritmetici simpli pentru a combina intervalele(obiecte care reprezintă măsura posibilelor valori a unei cantități inexacte). Rezultatul adunării, scăderii, înmulțirii sau împărțirii a două intervale este un nou interval reprezentînd limitele rezultatului.
Alyssa postulează existența unui obiect abstract numit “interval”,care are două puncte de sfîrșit: o limită inferioară și una superioară. Presupunem de asemenea, fiind date punctele de sfîrșit ale unui interval putem construi intervalul folosind constructorul de date make-interval. Alyssa scrie la început intadd pentru adunarea a două intervale. Ea crede că valoarea minimă pe care suma poate s-o ia este suma celor două limite inferioare și valoarea maximă pe care suma poate să o ia este suma celor două limite superioare :
(define (intadd x y)
(make-interval( + (lim_inf x)(lim_inf y) )
(+(lim_sup x)(lim_sup y) ) ) )
Alyssa de asemenea află produsul celor două intervale găsind minimul și maximul produsului limitelor și folosindu-le ca limite ale intervalului rezultat (min și max sunt primitive care găsesc minimul și maximul oricărui număr de argumente )
(define(intmul x y)
(let((p1(*(lim_inf x)(lim_inf y ) ) )
(p2(*(lim_inf x)(lim_sup y) ) )
(p3(*(lim_sup x)(lim_inf y) ) )
(p4(*(lim_sup x)(lim_sup y) ) ) )
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4) ) ) )
Pentru a împărți două intervale, Alyssa îl înmulțește pe primul cu inversul celui de-al doilea. Observăm că limitele intervalului invers sunt inversul limitei superioare și inversul limitei inferioare, în această ordine :
(define (intdiv x y)
(intmul x
(make-interval (/1 (lim_sup y) )
(/1(lim_inf y) ) ) ) )
Programul Alyssei este incomplet, deoarece ea nu a specificat implementarea abstractizării intervalului. Iată o definiție a constructorului make-interval:
(define (make-interval a b)(cons a b) )
Mărimea unui intervcal este diferența dintre limita superioară și limita inferioară.Mărimea este o măsură a incertitudinii unui număr specificat de interval. Pentru câțiva operatori aritmetici mărimea rezultată combinării a două intervale este în funcție numai de mărimea argumentelor intervalelor. Mărimea sumei(sau diferenței) a două intervale este în funcție numai de mărimea intervalelor adăugate (sau scăzute). Aceasta nu este adevărată pentru înmulțire și împărțire.
Ben Bitdiddle, un expert în programarea sistemelor comentează că nu este clar ce înseamnă să împarți un interval la un altul care tinde spre 0.
În trecere, Ben comentează că: ”Testând semnele punctelor finale ale intervalelor trecute la intmul este posibil să întrerupă intmul în nouă cazuri dintre care numai unu are mai mult de două înmulțiri”.
După verificarea programului ei, Alyssa îl arată unui potențial utilizator, care spune că programul ei rezolvă problema greăit. El vrea un program care se ocupă cu numere reprezentate ca valori centrale și o adăugare a unei toleranțe; de exemplu, vrea să lucreze cu un interval cum ar fi 3,5 0,15, mai degrabă ă3.35, 3.65î. Alyssa se întoace la birou și fixează această problemă furnizând constructori și selectori alternativi:
(define (center-width c w)
(make-interval (-c w)(+c w) ) )
(define (center I)
(/ (+(lim_inf i)(lim_sup I) )2) )
( define(width I)
(/ (-(lim_sup i)(lim_inf I) )2) )
Din păcate majoritatea utilizatorilor lui Alyssa sunt ingineri. Situațiile reale de construire de obicei implică măsurători cu o mică incertitudine măsurată ca raportul mărimii intervalului. Inginerii, de obicei, specifică procentajul de toleranță în parametrii dispozitivului ca și specificațiile date mai devreme asupra rezistorului.
După o muncă considerabilă, Alyssa P. Hacker dă sistemul terminat. Câțiva ani mai târziu, după ce uitase de el, primeîte un telefon de la un beneficiar. Părea că acesta a observat că formula pentru rezistori paraleli poate fi scrisă în două moduri algebrice echivalente:
și
Beneficiarul a scris următoarele două programe, fiecare din ele calculează formula rezistorilor paraleli în mod diferit:
(define (par1 r1 r2 )
(intdiv (intmul r1 r2)
(intadd r1 r2) ) )
(define (par 2 r1 r2)
(let ((one (make-interval 1 1) )
(intdiv one
(intadd (intdiv one r1)
(intdiv one r2) ) ) ) )
Beneficiarul sesizează că programul Alyssei dă răspunsuri diferite pentru cele două moduri de calculare. Aceasta este o sesizare serioasă.
Eva Lu Ator un alt utilizator a observat intervale diferite calculate de expresii echivalente în mod algebric, dar diferite. Ea spune că o formulă de a face calcul cu intervale folosind sistemul Alyssei va produce erori mai mici de limită, dacă poate fi scris în aîa formă încât nici o variabilă care reprezintă un număr nesigur să fie repetată. Astfel, spune ea, că par 2 este un program mai bun pentru rezistențe paralele, decât par 1.
COPITOLUL III
Date ierarhice
După cum am văzut, perechile furnizaează o primitivă pe care o folosim în construirea de obiecte de date compuse.
Figura 2.2 arată un mod standard de a vizualiza o pereche -în acest caz, perechea formată de (cons 1 2). În această reprezentare, care este numită notația box-and-pointer, fiecare obiect este arătat ca on poiter la o celulă. Celula pentru un obiect primitiv conține o reprezentare a obiectului. De exemplu, celula pentru un număr conține un numeral. Celula pentru o pereche este de fapt o dublă celulă, partea stăngă conținând un poiter la car-ul perechii și partea dreaptă conținând cdr-ul :
Fig2.2
Reprezentarea celulă și pointer lui (cons 1 2)
A fost deja menționat că cons poate fi folosit nu numai pentru a combina numere, dar și alte perechi. Ca o consecință, perechile furnizează un bloc universal de la care vom putea construi tot felul de structuri de date.
Figura 2.3 arată două moduri de a folosi perechile pentru a combina numerele 1, 2, 3, 4.
(cons (cons 1 2) (cons (cons 1
(cons 3 4) (cons 2 3) )
4)
fig.2.3
În general, perechile ne dau posibilitatea de a reprezenta date ierarhice date, făcute din părți care sunt la rândul lor construite din părți ].a.m.d.
După cum indică figura 2.3 putem folosi perechile pentru a combina datele în mai multe moduri diferite și am început această secțiune, explorînd cîteva tehnici convenționale, pentru folosirea perechilor, pentru a reprezenta secvențe și arbori.
În continuare, vom mări puterea reprezentațională a limbajului nosteru, introducând expresii simbolice-date ale căror părți elementare pot fi mai degrabă simboluri arbitrare decât numere. Vom explora apoi, alternative variate pentru a reprezenta seturi de obiecte. Vom afla că, la fel cum o funcție numerică poate fi calculată prin mai multe procese de calcul diferite, există căi în care o structură dată de date poate fi reprezentată în termenii unor obiecte mai simple și alegerea reprezentării poate avea un impact semnificativ asupra necesităților timpului și spațiului procesului, care manipulează datele. Vom investiga , de asemenea, codificarea lui Huffman ca o folosire inteligentă a arborilor pentru a implementa coduri eficiente.
fig 2.4
Reprezentarea secventelor 1, 2, 3, 4 ca o secven\[ de perechi
3.1 Reprezentarea secvențelor
Una din structurile folositoare pe care le putem construi cu perechi este secvența-o colecție ordonată de obiecte de date. Sunt desigur multe moduri de a reprezenta secvențele în termenii unor perechi. O reprezentare particulară strictă este arătată în figura 2.4, unde secvența 1, 2, 3, 4 este reprezentată ca o secvență de perechi. Cdr-ul fiecărei perechi este corespondentul numărului în secvență în cdr-ul perechii este perechea următoare în secvență.Cdr-ul perechii finale semnalizează sfîrșitul secvenței arătând spre un element distinct reprezentat în diagramele box-and-pointer ca o linie diagonală în programele Lisp ca valoarea simbolului nil. Această secvență este construită prin operațiile cons-nested:
(cons 1
(cons 2
(cons 3
(cons 4 nil) ) ) )
O asemenea secvență de perechi formată din cons-urile sub formă de cons-nested se numește listă în Lisp furnizează o primitivă numită list pentru a ajuta în construirea listelor. Secvența de mai sus poate fi produsă de (list 1, 2, 3, 4).
În general,
(list <a1> <a2> …<an>)
este echivalent cu:
(cons <a1> (cons <a2> (cons…(cons <an> nil)…) ) )
În mod convențional, Lisp printează listele tipărind secvența elementelor introduse între paranteze. Astfel, obiectul de date din figura 2.4 este tipărită ca (1 2 3 4).
==>(define 1-through-4 (list 1 2 3 4 ) )
1-through-4
==>1-through-4
(1 2 3 4)
Trebuie să nu confundăm expresiile (list 1 2 3 4 ) cu list(1 2 3 4), care este rezultatul obținut când expresia este evaluată. Încercând să-l evaluăm pe list(1 2 3 4) ca o expresie, ar semnala o eroare când interpretorul ar încerca să aplice procedura 1 argumentelor 2, 3 și 4. Ne gândim la car, ca selectând primul articol din listă și la cdr, ca selectând sublista ce este constitită din nimic altceva, decât primul articol. Aplicațiile sub formă de celulă ale lui car și cdr, pot fi folosite pentru a extrage al doilea, al treilea și subsecventul articolului în listă. Constructorul cons adaugă un nou articol la începutul listei:
==>(car 1-through-4)
1
==>(cdr 1- through-4)
(2 3 4)
==>(car (cdr 1- through-4) )
2
==>(cons 10 1-through-4)
(10 1 2 3 4)
Valoarea lui nil folosită pentru terminarea lanțului de perechi poate fi gândită ca o secvență fără nici un element, o listă goală. Într-adevăr, nil este o contracție a cuvântului latin nimic.
Operații cu liste
Folosirea perechilor pentru a reprezenta secvențe de elemente ca liste este însoțită de tehnici de programare convenționale pentru manipularea listelor prin succesiune de cdr-uri. De exemplu, procedura nth, are ca argument un număr n și o listă și returnează cel de-al n articol în listă. Este obișnuit la numărul de elemente al listei începând cu 0. Metoda pentru calcularea nth este următoarea:
Pentru n=0, nth ar trebui să returneze car-ul listei.
Altfel, nth returnează n-1 articol al cdr-ului din listă.
(define (nth n x)
(if (=n 0)
(car x)
(nth (-n 1)(cdr x) ) ) )
==>(define squares (list 1 4 9 16 25) )
squares
==>(nth 3 squares)
16
Adesea facem cdr-ul întregii liste. Pentru a ajuta în acest lucru Lisp include un predicat primitiv null? care testează dacă argumentul său este o listă goală. Iată o procedură tipică de lungime, care returnează numărul articolelor din listă:
(define (length x)
(if (null? x)
0
(+1 (length (cdr x) ) ) ) )
==>(define odds (list 1 3 5 7 ) )
odds
==>(length odds)
4
Procedura de lungime implementează un plan recursiv simplu. Pasul de reducere este:
Lungimea oricărei liste este unu plus lungimea cdr-ului listei. Aceasta se aplică succesiv până ajungem la cazul de bază.
Lungimea unei liste goale este 0. Am putea de asemenea, calcula lungimea într-un stil iterativ:
(define (length x)
(define (length-iter a count)
(if (null? a)
count
(length-iter (cdr a)(+1 count) ) ) )
(length-iter x 0) )
Altă tehnică de programare convențională este de a cons-up o listă de răspuns în timp ce facem cdr-ul listei.
Procedura append ia două liste ca argumente și le combină elementele pentru a face o nouă listă:
==>(append squares odds)
(1 4 9 16 25 1 3 5 7 )
==>(append odds squares)
(1 3 5 7 1 4 9 16 25)
Append este de asemenea, implementat folosind un plan recursiv. Pentru a folosi instrucțiunea append asupra listelor x și y procedăm în modul următor:
Dacă x este listă goală, rezultatul este doar y.
Altfel, adunăm cdr-ului x și y și construim car-ul lui x în rezultat:
(define (append x y)
(if (null? x)
y
(cons (car x)(append (cdr x) y) ) ) )
3.2 Reprezentarea arborilor
Reprezentarea secvențelor în termeni de liste, generalizează în mod natural o posibilitate pentru noi de a reprezenta secvențele ale căror elemente pot fi ele însele secvențe.
De exemplu, putem privi obiectul:
==>(cons (list 1 2)(list 3 4) )
((1 2)3 4)
ca o listă de trei articole, primul dintre ele fiind lista (1 2). Într-adevăr, aceasta este sugestionată de forma în care rezultatul este tipărit de interpretor:
(3 4)
( (1 2) 3 4)
(1 2)
fig 2.5
Structura formată de (cons (list 1 2) (list 3 4) )
Figura 2.6 arată structura figurii 2.5 văzută ca arbore.
(( 1 2 ) 3 4 )
3 4
1 2
fig 2.6
Structura perechii văzută ca arbore
Repetarea este un instrument natural pentru a lucra cu structurile sub formă de ramurilor arborilor, care reduc la urma lor operațiile asupra ramurilor, și arbori, din moment ce putem adesea să reducem operațiile pe arbori la operații asupra. ș. a. m. d. pînă ce ajungem la sfârșitul arborelui. Pentru a ajuta la scrierea procedurilor recursive asupra arborelui Lisp furnizează predicatul simplu atom?, care testează dacă argumentul său este atomic(adică nu este pereche).
Pentru a implementa countatoms reapelăm planul recursiv pentru calcularea lungimii:
Lungimea unei liste x este egală cu unu plus lungimea lui (cdr x).
Lungimea unei liste goale este 0.
Procedura countatoms este similară. Valoarea pentru lista goală este la fel.
Countatoms pentru lista goală este 0. Dar în pasul de reducere, unde renunțăm la car-ul listei trebuie să luăm în considerare faptul că (car x) în sine poate fi o listă ale cărei elemente trebuie să le numărăm. Astfel, pasul potrivit de reducere este:
(countatoms x)=(countatoms (car x) )+(countatoms (cdr x) )
În sfârșit, dacă calculăm în mod succesiv cdr-ul lui car, ajungem la atomi astfel încât avem nevoie de un alt caz de bază.
countatoms unui atom este 1.
Iată procedura completă:
(define (countatoms x)
(cond ( (null? x) 0)
( (atom? x) 1)
(else (+ (countatoms (car x) )
(countatoms (cdr x) ) ) ) )
3.3 Simboluri ncesare pentru citări
Toate obiectele de date compuse pe care noi le-am folosit până acum au fost construite din numere. Acum vom extinde capacitatea de reprezentare a limbajului introducând abilitati de a lucra cu simboluri arbitrare ca date. Dacă putem forma date compuse folosind ca atomi nu numai numere ci și simboluri arbitrare putem avea liste ca:
(a b c d)
(23 45 17)
( (Charles 33) (Leonard 31) (Carolyn 27) )
Listele care conțin simboluri pot arăta ca expresiile limbajului nostru:
(* (+ 23 45) (+ x 9) )
(define (factorial n) (if (=n 1) 1 (* n (factorial (-n 1) ) ) ) )
Pentru a manipula simbolurile avem nevoie de un nou element în limbajul nostru: abilitatea de a cita(quote) un obiect de date. Să presupunem că vrem să construim o listă (a b). Nu vom putea realiza aceasta (list a b), deoarece interpretorul va crede că dorim să combinăm într-o listă mai degrabă valori lui a și b, decât simbolurile în sine. Această problemă este bine cunoscută în contextul limbajelor naturale, unde cuvintele și propozițiile pot fi privite fie ca entități semantice, fie ca șiruri de caractere(entități sintactice). O practică comună în limbajele naturle este de a folosi semnele citării (“ “), pentru a indica că un cuvânt sau o propoziție trebuie tratată literal ca un șir de caractere. De exemplu, prima literă din cuvântul “John” este în mod clar ”J”.Dacă spunem ciuva “spuneți numele tare”, ne vom aîtepta să auzim numele acelei persoane. Totuși, dacă spunem cuiva “spune’numele tău’tare”, ne vom aștepta să auzim cuvintele “numele tău”. De observat, că suntem forțați să formăm semnele citării sub formă de celulă pentru a descrie ce ar putea spune altcineva. Putem urma aceeași practică pentru a identifica liste și atomi, care trebuiesc tratate mai degrabă ca obiecte de date și nu ca expresii ce trebuiesc evaluate. Totuși formatul pentru citare diferă de acel al limbilor naturale, în faptul că vom poziționa semnele citării(în mod tradițional singurul simbol de citat este ‘), numai la începutul obiectului care vrem să-l cităm. Putem reuși asta numai în sintaxa Lisp, deoarece ne bazăm pe spații goale și paranteze pentru a delimita obiectele. Astfel, sensul unui singur caracter de citat este de cita următorul obiect.
Acum putem distinge între simboluri și valorile lor:
==> (define a 1)
a
==> (define b 2)
b
==> (list a b)
(1 2)
==> (list ‘a ‘b)
(a b)
==> (list ‘a b)
(a 2)
Citarea ne permite să catalogăm obiectele compuse, folosind reprezentația tipărită convențional pentru liste:
==> (car ‘(a b c) )
a
==> (cdr ‘(a b c) )
(b c)
O primitivă suplimentară folosită în manipularea simbolurilor este eq?, care ia două simboluri ca argumente și testează dacă ele sunt la fel. Folosind eq?, putem imlementa o procedură folositoare numită memq. Aceasta ia două argumente, un simbol și o listă. Dacă simbolul nu este conținut în listă(adică nu este eq? la unul dintre articolele di listă), atunci memq returnează lista goală. Altfel returnează sublista listei care începe cu prima literă a simbolului:
(define (memq item x)
(cond ( (null? x) ‘( ) )
( (eq? item (car x) ) x)
(else (memq item (cdr x) ) ) ) )
De exemplu,
(memq ‘apple ’(pear banana prune) ) returnează lista goală, în timp ce:
(memq ‘apple ’(x (apple sauce) y apple pear) ) returnează (apple pear).
Se spune că două liste sunt egale, dacă ele conțin elemente egale, aranjate în aceeași ordine. De exemplu,
(equal? ‘(this is a list) ’(this is a list) )
este adevărat , dar: (equal? ‘(this is a list) ‘(this (is a) list) )
este fals. Pentru a fi mai preciși, putem defini equal? în mod recursiv în termeni de egalitate de bază eq? a simmbolurilor, spunând că a și bsunt egale, dacă sunt amândouă simboluri și dacă simbolurile sunt eq?, sau dacă sunt amândouă liste precum (car a) este egal cu (cdr b).
3.4 Exemplu:diferențiere simbolică
Ca o ilustrație la manipularea simbolurilor și ca o ilustrație mai îndepărtată a abstractizării datelor luăm în considerare proiectarea unei proceduri, care rezolvă diferențierea simbolică a expresiilor algebrice. Ne-ar plăcea ca procedura să ia ca argumente p expresie algebrică și o variabilă și să returneze o derivată a expresiei cu privire la variabilă. De exemplu, dacă argumentele procedurii sunt ax2+bx+c și x, procedura ar trebui să returneze 2ax+b. Diferențierea simbolică este de o semnificație istorică specială în Lisp. A fost una dintre exemplele motivaționale cu privire la dezvoltarea limbajului calculatorului pentru manipularea simbolică. Mai mult, am marcat începutul liniei de cercetare care au condus la dezvoltarea unor sisteme puternice pentru lucrul matematic simbolic, care este folosit în mod curent de un număr tot mai mare de matematicieni și fizicieni.
În dezvoltarea unui program de diferențiere simbolică, vom urmări aceeași strategie a abstractizării datelor pe care am urmărit-o în dezvoltarea sistemului de numere raționale. Aceasta înseamnă că, vom defini prima dată un algoritm de diferențiere, care operează asupra unor obiecte abstracte, cum ar fi “sume”,”proceduri” și ”variabile” fără să ne facem griji cum vor fi acestea reprezentate. Numai după aceea vom adresa problema de reprezentare.
Programul de diferențiere cu date abstracte
Pentru a menține lucrurile simple, vom lua în considerare un foarte simplu program de diferențiere simbolică, care se ocupă cu expresiile care trebuie construite folosind numai operațiile de adunare și înmulțire cu două argumente. Diferențierea unei astfel de expresii poate fi îndeplinită de aplicarea următorelor reguli de reducere:
Observăm că, ultimele două reguli sunt repetabile. Adică să obținem derivata unei sume găsim întâi derivatele termenilor care trebie adunați și apoi adunăm derivatele lor. Fiecare din factori poate fi la rândul său o expresie, care trebuie descompusă. Descompunând în părți din ce în ce mai mici vom produce părți care vor fi ori constante, ori variabile a căror derivată va fie 0 sau 1.
Pentru a introduce aceste reguli într-o procedură, vom permite într-o mai mică măsură de gândire, decât am făcut în proiectarea implementării numerelor raționale. Dacă avem un mijloc de a reprezenta expresiile algebrice, vom fi capabili să spunem dacă o expresie este sumă, produs, constantă sau variabilă. Vom fi capabili să extragem părțile unei expresii (de axemplu, pentru o sumă vom fi capabili să extragem termenii de adunat) și vom fi capabili să construin expresii din părți. Să presupunem că avem deja proceduri de implementare a următorilor selectori, constructori și predicate:
(constant? <e>) Este <e> constant?
(variable? <e>) Este <e> variabil?
(same-variable? <v1> <v2>) Sunt <v1> și <v2> aceleași variabile?
(sum? <e>) Este <e> o sumă?
(product? <e>) Este <e> produs?
(addend <e>)
(augend <e>)
(multiplier <e>) Înmulțitorul produsului <e>
(multiplicant <e>) Înmulțitul produsului <e>
(make-sum <a1> <a2>) Construim suma dintre <a1> și <a2>
(make-product <m1> <m2>) Construim produsul dintre <m1> și <m2>
Folosind aceîti operatori, putem exprima regulile de diferențiere ca în procedura următoare:
(define (deriv exp var)
(cond ( (constant? exp) 0)
( (variable? exp)
(if (same-variable? exp var ) 1 0) )
( (sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var) ) )
( (product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var) )
(make-product (deriv (multiplier exp) var)
(multiplicand exp) ) ) ) ) )
Această procedură încorporează algoritmul complet de diferențiere. Din moment ce este exprimat în termeni de date abstracte, va lucra indiferent de modul în care noi alegem să rerezentăm expresiile algebrice, atâta timp cât vom proiecta un set potrivit de selectori și constructori. Aceasta este problema pe care o vom lua în considerare în ceea ce urmează.
Reprezentarea expresiilor algebrice
Ne putem imagina multe moduri de a folosi structurile listă, pentru a reprezenta expresii algebrice. De exemplu, putem folosi liste de simboluri care arată notația algebrică, reprezentând ax+b ca list(a*x+b). Totuși, o alegere directă este de a folosi aceeași notație ca prefix parantezî pe care Lisp o foloseîre pentru combinații; adică, de areprezenta ax+b ca
(+ (*a x) b). Atunci, reprezentarea noastră de date pentru problema
diferențierii este după cum urmează:
Constantele sunt numere identificate de predicatul simplu number?
(define (constant? x)(number? x) )
Variabilele sunt simboluri identificate de predicatul simplu symbol?
(define (variable? x) (symbol? x) )
Două variabile sunt la fel dacă simbolurile care le reprezintă sunt eq?
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2) ) )
Sumele și produsul sunt construite ca liste:
(define (make-sum a1 a2) (list ‘+a1 a2) )
(define (make-product m1 m2) (list ‘*m1 m2) )
O sumă este o listă al cărei prim element este simbolul +:
(define (sum? x)
(if (not (atom? x) ) (eq? (car x) ‘+)nil) )
Addend este al doilea articol din lista sumă:
(define (addend s) (cadr s) )
Augend este al treilea articol di lista sumă:
(define (augend s) (caddr s) )
Produsul este o listă al cărui prim element este simbolul *:
(define (product? x)
(if (not (atom? x) ) (eq? (car x) ‘*) nil) )
Înmulțitul este al doilea articol din lista produs:
(define (multiplier p) (cadr p) )
Înmulțitorul este al treilea articol din lista produs:
(define (multiplicand p) (caddr p) )
Astfel, avem nevoie numai de a combina acestea cu algoritmi aîa cum este îmbrățiîat de derivare, pentru a avea un program de diferențiere simbolică ce funcționează. Să privim câteva exemple cu comportamentul acestuia:
==>(deriv ‘(+ x 3) ‘ x)
(+ 1 0)
==>(deriv ‘(* x y) ‘ x)
(+ (* x 0) (* 1 y) )
==>(deriv ‘(* (* x y) (+ x 3) ) ‘ x)
(+ (* (* x y) (+ 1 0) )
(* (+ (* x 0) (* 1 y) )
(+ x 3) ) )
Programul produce răspunsurile care sunt corecte;totuși ele sunt nesimplificate. Este adevărat că:
,
dar ne-ar plăcea ca programul să îtie că x0=0, 1y=y și 0+y=y. Răspunsul pentru al doilea exemplu, ar trebui să fie în mod similar y. După cum arată al treile exemplu, aceasta devine o problemă serioasă când expresiile sunt complexe.
Dificultatea noastră este asemănătore cu cea pe care am întâlnit-o la implementarea numerelor raționale:nu am redus răspunsurile la cea mai mică formă. Pentru a realiza reducerea numerelor raționale, am avut nevoie numai să schimbăm selectorii și constructorii implementării. Putem adopta aceeași strategie similară și aici. Nu vom schomba deloc deriv. În schimb, vom schimba procedura make-sum astfel încât dacă cei doi factori ai sumei sunt numere, make-suma și va aduna și va returna suma lor. De asemenea, dacă unul din factori este 0, atunci make-sum va returna celălalt factor:
(define (make-sum a1 a2)
(cond ( (and (number? a1) (number? a2) ) (+a1 a2) )
( (number? a1) (if (=a1 0) a2 (list ‘+ a1 a2) ) )
(number? a2) (if (=a2 0) a1 (list ‘+ a1 a2) ) )
(else (list ‘+ a1 a2) ) ) )
În mod similar, vom schimba procedura make-product, pentru a construi regula că 0 înmulțit cu ceva este 0 și 1 înmulțit cu ceva este acel ceva:
(define (make-product m1 m2)
(cond ( (and (number? m1) (number? m2) ) (*m1 m2) )
( (number? m1)
(cond ( (=m1 0) 0)
( (=m1 1) m2)
(else (list ‘* m1 m2) ) ) )
( (number? m2)
(cond ( (=m2 0) 0)
( (=m2 1) m1)
(else (list ‘* m1 m2) ) ) )
(else (list ‘* m1 m2) ) ) )
Iată cum această versiune lucrează pe cele trei exemple:
==>(deriv ‘(+ x 3) ‘x)
1
==>(deriv ‘(* x y) ‘x)
y
==>(deriv ‘(* x y) (+ x 3) ) ‘x)
(+ (* x y) (* y (+ x 3) ) )
Cu tote că aceasta este o îmbunătățire, al treilea exemplu ne arată că mai este mult de mers până obținem un program ce pune expresii într-o formă cu care am putea fi de acord că este cea mai simplă. Problema simplificării algebrice este destul de complexă, deoarece printre alte motive, o formă ce poate fi cea mai simplă pentru un scop nu poate fi cea mai simplă pentru altul.
3.5 Exemplu: Reprezentarea mulțimilor
În exemplul anterior, am construit reprezentării pentru două feluri de obiecte de date compuse:numere raționale și expresii algebrice. Într-unul dintre aceste exemple, am avut posibilitatea de simplificare(reducere) a expresiilor ori în timpul construcției, ori în timpul selectării, dar altceva decât posibilitatea dea reprezenta aceste structuri în termen de liste a fost mai directă.
Când ne-am întors la seturile de reprezentare, posibilitatea de reprezentare nu mai este aîa de evidentă. Într-adevăr, este un număr de reprezentări posibile și diferite în mod semnificativ de la unul la altul în mai multe moduri. În mod neoficial, o multime este în modsimplu o colecție de obiecte distincte. Pentru a da o mai precisă definiție ne putem folosi de metoda abstractizării datelor. Aceasta înseamnă că, definim o multime specificând operatorii folosiți în seturi. Aceîti operatori sunt:union-set, intersection-set, element-of-set? și adjoin-set. Element-of-set? este un predicat ce determină dacă un element dat este element al unei multimi. Adjoin-set ia un obiect și un set ca argumente și returnează un set ce conține elementele multimii initiale și de asemenea elementul adăugat. Union-set calculează reuniunea a două multimi, care este o multime ce conține fiecare element care apare în cele două argumente. Intersection-set calculează intrțersecția a două multimi este multimea ce conține numai elementele comune din cele două argumente. Vom folosi lista vidă pentru a reprezenta o multime vida. Din punct de vedere al abstractizării datelor, suntem liberi să proiectăm orice reprezentare care implementează aceîti operatori într-un mod corespunzător interpretărilor date mai sus.
Multimi ca liste neordonate
Un mod de a reprezenta o multime este ca o listă cu elementele sale unde nici un element nu apare mai mult de o dată. Multimea vidă este reprezentat de lista vidă. În această reprezentare, element-of-set? este similar procedurii memq. Foloseste equal? în loc de eq? astfel încât elementele multimi nu au nevoie să fie simboluri:
(define (element-of-set? x set)
(cond ( (null? set) nil)
( (equal? x (car set) ) t)
(else (element-of-set? x (cdr set) ) ) ) )
Folosind aceasta, putem scrie adjoin-set. Dacă obiectul care trebuie adunat este deja în o multime vom returna numai multimea Altfel, vom folosi cons pentru a adăuga obiectul la lista care reprezintă multimea:
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set) ) )
Pentru intersection-set vom folosi o strategie recursivă. Dacă îtim cum sî formăm intersecția dintre set2 și cdr-ul lui set1, avem nevoie să decidem dacă să includem sau nu car-ul lui set1 în aceasta. Dar aceasta depinde de faptul că, dacă car set1 este în set2. Iată procedura ce rezultă:
(define (intersection-set set1 set2)
(cond ( (or (null? set1) (null? set2) ) ‘( ) )
( (element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2) ) )
(else (intersection-set (cdr set1) set2) ) ) )
În proiectarea unei reprezentări, una dintre problemele ce trebuie luate în considerare este eficiența. Să luăm în considerare timpul cerut de operațiile noastre asupra operațiilor cu multimi. Din moment ce majoritatea folosesc element-of-set?, viteza acestor operații are un impact major asupra eficienței implementării multimi ca întreg. Acum pentru a vaerifica dacă un obiect este membru al unei multimi, element-of-set ? poate să scaneze întregul set. De aceea, dacă multimi are n elemente, element-of-set? poate primi până la n pași. Astfel timpul cerut de adjoin-set, care foloseîte această operație, de asemenea creîte la O(n).Pentru intersection-set, care face o verificare element-of set? pentru fiecare element din set1, timpul cerut creîte ca și produsul mărimilor seturilor implicate sau O(n2), pentru două multimi de mărime n. Aceasta este adevărată și pentru union-set.
Multimi ca liste ordonate
Un mod de a mări viteza operațiilor cu multimi este de a schimba reprezentarea astfel încât elementele setului să fie listate în ordine crescătoare. Pentru a face aceasta avem nevoie de un anumit mod de a compara două obiecte astfel încât să putem spune care este mai mare. De exemplu, am putea compara simbolurile în mod lexicografic, sau am putea fi de acord asupra unei metode pentru a stabili un număr unic la un obiect și apoi să comparăm elementelecomparând numerele corespunzătoare. Pentru a menține discuția noastră simplă, vom lua în considerare numai cazul în care elementele multimii sunt numere astfel încât să putem compara elementele folosind > și <. Vom reprezenta un set de numere listând elementele sale în ordine crescătoare, întrucât prima noastă reprezentație de mai sus ne-a permis să reprezentăm o multime {1, 3, 6, 10Ș listând elementele în orice ordine, noua reprezentație ne permite numai lista (1, 3, 6, 10).
Un avantaj al ordonării apare în element-of-set?: în verificarea prezenței unui articol nu mai este nevoie să scanăm întrega multime. Dacă ajungem la un element de multime care este mai mare decât articolul pe care îl căutăm, atunci îtim că articolul nu se află în multime (define (element-of-set? x set)
(cond ( (null? set) nil)
( (=x (car set) ) t)
( (< x (car set) ) nil)
(else (element-of-set? x (cdr set) ) ) ) )
Cât de mult timp salvează aceasta? În cel mai rău caz, articolul pe care îl căutăm pote fi cel mai mare din set astfel încât numărul pașilor este la fel ca pentru reprezentarea neordonată. Pe de altă parte, dacă vom căuta articole de mărimi diferite ne aîteptăm ca uneori să fim capabili să ne oprim căutarea la un punct apropiat de începutul listei și altădată să fie nevoie să examinăm majoritatea listei. Pe medie ne-am putea aîtepta să fie nevoie să examinăm din numărul de articole din set. Astfel timpul mediu necesar va fi de aproximativ n/2. Aceasta este totuși creîterea O(n), dar ne salvează pe medie un factor din doi în timpul implementării anterioare.
Vom obține o impresionantă vitezăcând vom lua în considerare intersection-set. În reprezentarea neordonată această operație necesită timpul O(n2), deoarece vom face o scanare completă a lui set2 pentru fiecare element din set1. Dar cu reprezentarea ordonată putem folosi o metodă mai inteligentă. Să începem comparând elementele inițiale x1 și x2 a două multimi. Dacă x1=x2 , atunci aceasta ne dă un element de intersecție și restul intersecției este intersecția cdr-urilor din cele două multimi. Să presupunem totuși că, x1<x2. Din moment ce x1 este cel mai mic element din set2, putem imediat concluziona că x1 nu poate apărea oriunde în multime și prin urmare nu este în intesecție. Deci intersecția este egală cu intersecția lui set2 cu cdr-ul din set1. În mod similar, dacă x2<x1, atunci intersecția este dată de intersecția lui set1 cu intersecția cdr-ului lui set2. Iată procedura:
(define (intersection-set set1 set2)
(if (or (null? set1) (null? set2) )
‘( )
(let ( (x1 (car set1) ) (x2 (car set2) ) )
(cond ( (=x1 x2)
(cons x1
(intersection-set (cdr set1)
(cdr set2) ) ) )
((< x1 x2)
(intersection-set (cdr set1) set2) )
( (< x2 x1)
(intersection-set set1
(cdr set2) ) ) ) ) ) )
Pentru a estima timpul cerut de acest proces, observăm că la fiecare pas reducem problema intersecției de a calcula intersecțiile celor mai mici multimi. îndepărtând primul element din set1 sau set2 sau amândouă. Astfel, numărul pașilor necesari este în majoritatea cazurilor suma mărimilor lui set1 și set2, mai degrabădecât produsul mărimilor ca și cu reprezentarea neordonată. Aceasta este creîterea O(n) mai degrabă decât O(n2)- o viteză considerabilă chiar și pentru multimi. de mărimi moderate.
Multimi ca arbori binari
Putem face mai bine decât reprezentarea listelor ordonate aranjând elementele setului sub formă de arbore. Fiecare nod al arborelui ține un element al setului numită intrarea la acel nod și o legătură la fiecare dintre cele două alte(posibile goale) noduri. Legătura stângă duce la elemente mai mici decât cele din nod și legătura dreaptă la elemente mai mari decât cele din nod. 7 3 5
3 9 1 7 3 9
1 5 11 5 9 1 7 11
11
Fig.2.7
Valorile arborelui binar care reprezintă multimea. {1,3,5,7,9,11}
Figura 2.7 arată câțiva arbori ce reprezintă setul {1,3,5,7,9,11}. Același multimi. poate fi reprezentat de un arbore într-un număr de moduri diferite. Singurul lucru necesar pentru o reprezentare validă este faptul că toate elementele din subarborul stâng să fie mai mici decât intrarea nodului și toate elementele din subarborele din dreapta să fie mai mari. Avantajul reprezentării sub formă de arbore este următorul: să presupunem că vrem să verificăm dacă un număr x este conținut într-un set. Începem comparând x cu intrarea în modul cel mai mare. Dacă x este mai mic decât acesta, îtim că trebuie să căutăm numai în subarborele stâng; dacă x este mai mare trebuie să căutăm numai în subarborele drept. Dacă arborele este balansat(egal), fiecare din aceîti subarbori vor fi de aproximativ jumătate din mărimea originalului. Astfel într-un singur pas am redus problema căutării într-un arbore de mărime n, la căutarea într-un arbore de mărime n/2.
Din moment ce mărimea arborelui este înjumătățită la fiecare pas, ne-am putea aîtepta ca numărul de pași necesari pentru căutarea unui arbore de mărime n să fie O(log n). Pentru seturi mari aceasta va fi o viteză semnificantă asupra reprezentațiilor anterioare. Putem reprezenta arborii folosind liste. Fiecare nod va fi o listă din trei artcole: intrarea la acel nod, subarborele stâng și subarborele drept. Un subarbore drept sau stâng al unei liste goale va indica faptul că nu este nici un subarbore conectat acolo.Putem descrie această reprezentație prin procedurile următoare:
(define (entry tree) (car tree) )
(define (left-branch tree) (cadr tree) )
(define (right-branch tree) (caddr tree) )
(define (make-tree entry left right)
(list entry left right) )
Acum putem scrie procedura element-of-set? folosind strategia descrisă mai sus:
(define (element-of-set? x set)
(cond ( (null? set) nil)
( (= x (entry set) ) t)
( (< x (entry set) )
(element-of-set? x (left-branch set) ) )
( (element-of-set? x (right-branch set) ) ) ) )
Adăugând un articol la un set este implementat în mod similar și necesită de asemenea O(log n) pași. Pentru a adăuga un articol x, îl comparăm pe x cu intrarea în nod pentru a dtetermina dacă x trebuie să fie adăugat în ramura din dreapta sau cea din stânga, și adăugându-l pe x la ramura potrivită îmbinăm această nouă ramură construită cu intrarea originală și cu cealaltă ramură. Dacă x este egal cu intrarea vom returna numai setul original. Dacă ni se cere să-l adăugăm pe x la un arbore gol, generăm un arbore care-l are pe x ca intrare și ramurile drepte și stângi nule. Iată procedura:
(define (adjoin-set x set)
(cond ( (null? set) (make-tree x ‘() ’( ) ) )
( (= x (entry set) ) set)
( (< x (entry set) )
(make-tree (entry set)
(adjoin-set x
(left-branch set) )
(right-branch set) ) )
( (> x (entry set) )
(make-tree (entry set)
(left-branch set)
(adjoin-set x
(right-branch set) ) ) ) ) )
Pentru calcularea intersecțiilor, totuși se dovedeîte că nu este un mod general pentru a înainta altfel decât a folosi aceeași strategie pe care am folosit-o în reprezentarea listelor neordonate. Aceasta înseamnă că scanăm să vedem dacă fiecare element din set1 este în set2, și dacă este aîa îl aplicăm la un set de intersecție pe care îl acumulăm. Din moment ce această căutare necesită timp aproximativ egal cu logaritmul numărului articolelor din set2 și din moment ce trebuie să facem această operație pentru fiecare element din set1, timpul total cerut creîte ca mărime egală cu set1 ori, logaritmul măsurii lui set2 sau O(nlog n) dacă cele două seturi sunt comparabile în mărime. aceasta este totuși mai bună decât reprezentarea listelor neordonate, dar nu chiar la fel de bună ca reprezentarea listelor ordonate. Din moment ce o implementare tipică a setului este ca să facă mai multe căutări decât intersecția, reprezentarea sub formă de arbori este de obicei de preferat.
Este o problemă suplimentară cu implementarea arborilor. Pretemția că, căutarea arborelui poate fi făcută în timp logaritmic se bazează pe presupunerea că arborele este balansat, adică subarborii drepți și stângi ai fiecărui arbore au aproximativ același număr de elemente, astfel încât fiecare arbore să conțină aproape jumătate din elementele părintelui său. Dar cum putem fi siguri că arborele pe care îl construim va fi balansat? Chiar dacă începem cu un arbore balansat adăugând elemente cu adjoin-set ar putea produce un rezultat nebalansat.Din moment ce poziția unui nou element adăugat depinde de modul în care se compară cu elementele deja existente în set ne putem aîtepta că dacă adăugăm elemente la întâmplare arborele va tinde să fie balansat pe medie. Dar aceasta nu este o garanție. De exemplu: dacă vom începe cu o multime vid[ și adăugăm numere de la 1 la 7 în succesiune vom sfârși cu un foarte nebalansat arbore arătat în figura 2.8.
1
2
3
4
5
6
7
figura 2.8
Arbore nebalansat produs de alipirea secventei 1-7
În acest arbore toți subarborii din stânga sunt goi și astfel nu are avantaj asupra unei simple liste ordonate. Un mod de a rezolva această problemă rste de a defini o operație care transformă un arbore arbitrar într-un arbore balansat cu aceleași elemente. Apoi vom face această transformare după fiecare cele câteva operații adjoin-set pentru a menține setul în balanță. De asemenea, există alte moduri de a rezolva această problemă majoritatea care implică proiectarea de noi structuri de date pentru care căutarea și inserarea pot fi făcute amândouă în O(log n) pași.
Mulțimi și salvarea informației
Am examinat opțiunile pentru folosirea listelor la reprezentarea mulțimilor și am văzut cum posibilitatea unei reprezentări pentru un obiect de date poate avea un impact mare asupra performanței programelor care folosesc date. Un alt motiv pentru concentrarea în seturi este acela că tehnicile discutate aici apar iar și iar în aplicațiile ce implică salvarea informațiilor. Să considerăm o bază de date ce conține un număr mare de înregistrari individuale-de exemplu dosarele de personal ale unei companii sau tranzacțiile într-un sistem de contabilitate. Un sistem tipic de administrație a datelor ia mult timp accesând sau modificând datele în înregistrări și de acea necesită o metodă eficientă de accesare a înregistrărilor. Acasta se face identificând o parte a unei înregistrări pentru a servi ca o cheie de identificare. O cheie poate fi orice, identifică în mod unic înregistrarea. Pentru un dosar de personal poate fi numărul de securitate social al unui angajat. Pentru un sistem contabil pote fi un număr de tranzacție. Orice ar fi cheia când definim înregistrarea, ca o structură de date ar trebui să includem o procedură key selector, care salvează cheia asociată cu o înregisrare dată. Acum reprezentăm baza de date ca un set de înregistrări. Pentru a localiza înregistrarea cu o cheie dată folosim o procedură lookup, care ia ca argument o cheie și o bază de dată, care returnează înregistrarea care are acea cheie sau nil dacă nu există nici o astfel de înregistrare. Lookup este reprezentată aproape în același mod ca și în element-of-se?. De exemplu dacă mulțimea de înregisrări este implementată ca și lista neordonată, am putea folosi procedura următoare:
(define (lookup given-key set-of-records)
(cond ( (null? set-of-records) nil)
( (equal? given-key (key (car set-of-records) ) )
(car set-of-records) )
(else (lookup given-key (cdr set-of-records) ) ) ) ).
Desigur sunt căi mai bune de a reprezenta decât ca liste neordonate. Sistemele de salvare a informațiilor în care înregistrările trebuie să fie la întâmplare accesate sun implementate în mod tipic de o metodă bazată pe arbori cum ar fi reprezentarea arborilor binari discutată anterior. În proiectarea unui astfel de sistem, metodologia deducerii datelor poate fi de mare ajutor. Proiectantul poate crea o implementație inițială folosind o reprezentațir simplă și directă cum ar fi listele neordonate. Aceasta va fi nepotrivit pentru un sistem final, dar poate fi folositoare în realizarea unei baze de date cu care să testăm restul sistemului. Mai târziu reprezentația datelor poate fi modificată să fie mai sofisticată. Dacă baza de dată este accesată în termeni de selectori și constructori abstracți acaeastă schimbare în reprezentare nu va necesita nici o schimbare în restul sistemului.
3.6 Exemplu: Codificarea Huffman a arborilor
Această secțiune furnizează practicii folosirea structurilor listă și reducerii datelor pentru a manipula arbori și seturi. Aplicația este de a găsi o metodă pentru reprezentarea datelor ca succesiuni de 0 și 1(biți). De exemplu, codul standard ASCII folosit pentru pentru a reprezenta textele în calculatoare codifică fiecare caracter ca o secvență de șapte biți. Folosind șapte biți ne va permite si distingem 27 sau 128, posibile caractere diferite. În general, dacă vrem să distingem N simboluri diferite, vom avea nevoie să folosim log2N biți pe simbol. Dacă toate mesajele noastre sunt compuse din opt simboluri A, B, C, D, E, F, G și H, putem alege un cod cu trei biți pe caracter, de exemplu:
A 000 C 010 E 100 G 110
B 001 D 011 F 101 H 111
Cu acest cod , mesajul:
BACADAEAFABBAAGAH
este codificat ca șirul de 54 de biți:
001000010000011000100000101000001001000000000110000111
Codurile cum ar fi ASCII și codul de la A la H descris mai sus sunt cunoscute ca și codurile de lungime fixă deoarece reprezintă fiecare simbol din mesaj cu același număr de biți. Este uneori avantajossă folosim codurile cu lungime variabilăîn care simboluri diferite pot fi reprezentate de numere diferite de biți. De exemplu, codul Morse nu foloseîte același numîr de puncte și linii pentru fiecare literă a alfabetului. În special E, cea mai frecventă literă, este reprezentată de un singur punct. În general, dacă mesajele noastre sunt în aîa fel încât anumite simboluri apar frecvent și altele foarte rar putem codifica datele mai eficient(folosind câțiva biți pe mesaj) dacă alocăm coduri mai scurte la simbolurile frecvente. Să luăm în considerare următorul cod alternativ pentru literele de la A la H:
A 0 C 1010 E 1100 G 1110
B 100 D1011 F 1101 H 1111
Cu acest cod același mesaj ca mai sus este codificat ca șirul următor:
100010100101101100011010100100000111001111
Acest șir conține 42 de biți, deci salvează mai mult de 20% din spațiu în comparație cu codul cu lungime fixă arătat mai sus.
Una dintre dificultățile folosirii unui cod cu lungime variabilă este să îtim când am ajuns la sfârșitul simbolului în citirea unei succesiuni de 0 și 1. Codul Morse rezolvă această problemă, folosind un cod separator(în acest caz o pauză) după sevvența de puncte și linii pentru fiecare literă. Altă soluție este să proiectăm codul în aîa fel încât nici un cod complet pentru orice simbol să fie început(prefixul) a codului pentru alt simbol. Un astfel de cod este numit cod-prefix. În exemplul de mai sus, A este codificat de 0, B este codificat de 100, astfel că nici un alt simbol nu poate avea un cod care începe cu 0 sau 100.
În general, putem ajunge la salvări semnificative dacă folosim codurile prefix cu lungime variabilă care are avantajul frecvențelor reciproce(relative) a simbolurilor din mesajele ce trebuiesc codificate. O schemă particulară pentru a face aceasta este metoda de codificare numită Huffman, după descoperitorul ei David Huffman. Un cod Huffman poate fi reprezentat ca un arbore binar ale căriu ramuri sunt simboluri ce sunt codificate. La fiecare nod nonramură a arborelui este un set ce conține toate simbolurile din ramurile care pleacă de la nod. În plus fiecărui simbol la o ramură și este asociat un numîăr de frecvență și fiecare nod nonramură conține o mărime care este suma tuturor secvențelor ramurilor de sub el. Mărimile nu sunt folosite în procesul de decodificare sau codificare. Vom vedea mai jos cum sunt folosite ele pentru a ajuta la construcția arborilor.
{ABCDEFGH} 17
AB {BCDEFGH} 9
{BCD} 5
B3 {CD} 2 {EFGH} 4
CI DI
{EF} 2
EI FI {GH} 2
GI HI
fig 2.9
Codificarea arborelui Huffman
Figura 2.9 arată arborele Huffman pentru codul de la A la H dat mai sus. Frecvența numerelor la ramuri indică faptul că arborele a fost proiectat pentru mesaje în care A apare cu frecvența relativă 8, B cu frecvența relativă 3 și celelalte litere cu frecvența relativă 1. Dând un arbore Huffman vom putea găsi codificarea oricărui simbol începând de la rădăcina și mergând până când ajungem la ramura care conține simbolul. De fiecare dată când coborâm pe o ramură stângă adăugăm un 0 la cod și de fiecare dată când coborâm o ramură în dreapta adăugăm un 1. De exemlu, începând de la rădăcina arborelui din figura 2.9, ajungem la ramura pentru D urmărind o ramură dreaptă apoi o ramură stângă, apoi o ramură dreaptă, apoi o ramură dreaptă, prin urmare codul pentru D este 1011
Pentru a codifica o succesiune de biți folosind un arbore Huffman începem de la rădăcină și folosim zerourile și unurile succesive ale succesiunii bit pentru a determina dacă să mergem pe ramura stângă sau dreaptă. De fiecare dată când ajungem la o ramură generăm un nou simbol în mesaj la care putem începe de la rădăcina arborelui pentru a găsi simbolul următor. De exemplu, să presupunem că avem dat arborele de mai sus și succesiunea 10001010. Începând de la rădăcină coborâm pe ramura dreaptă(deoarece primul bit al șirului este 1), apoi coborâm pe ramura stângă(deoarece al doilea bit este 0), apoi pe ramura stângă(deoarece al treilea bit este 0). Aceasta ne duce la ramura pentru B. Deci primul simbol al mesajului decodificat este B. Acum începem din nou de la rădăcină și facem o mi]care la stânga, deoarece următorul bit în șir este 0. Aceasta ne duce la ramura pentru A. Apoi începem din nou de la rădăcină cu restul șirului 1010, și deci mergem la dreapta, la stânga, la dreapta, la stânga și ajungem la C, deci întregul mesaj este BAC.
Generarea unui arbore Huffman
Dând un alfabet de simboluri și frecvențele lor relative, cum construim cel mai bun cod?(cu alte cuvinte care arbore va codifica mesajul cu cel mai mic număr de biți?). Huffman a dat un algoritm pentru a face aceasta și a arătat că codul rezultat este într-adevăr cel mai bun cod cu lungime variabilă pentru mesaje unde frecvența relativă a simbolurilor potriveîte frecvențele cu care codul a fost construit. Nu vom dovedi această optimalitate a codurilor Huffman aici, dar vom arăta cum sunt construiți arborii Huffman. Algoritmul pentru generarea unui arbore Huffman este foarte simplu. Ideea este să aranjăm arborele astfel încât simbolul cu frecvența cea mai mică să apară cel mai departe de rădăcină. Să începem cu mul\imea de noduri ramură împreună cu frecvențele lor cum sunt determinate de date inițiale de la care codul trebuie să fie construit. Acum găsim două ramuri co frecvențele cele mai mici și le unim pentru a produce un nod ce are aceste două noduri ca fiind ramurile sale stângă și dreaptă. Mărimea noului nod este suma celor două frecvențe. Îndepărtăm cele două ramuri din setul original și le înlocuim pe acestea cu acest nou nod. La fiecare pas, unim două noduri cu cele mai mici mărimi îndepărtându-le de set și înlocuindu-le pe acestea cu un nod care le are pe acestea două ca fiind ramurile stângă și dreaptă. Procesul se opreîte acolo unde a mai rămas doar un singur nod care este rădăcina întregului arbore. Iată cum a fost generat arboreleHuffman din figura 2.9:
Ramurile inițiale {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
Unim {(A 8) (B 3) ({C DȘ 2) (E 1) (F 1) (G 1) (H 1)}
Unim {(A 8) (B 3) ({C DȘ 2) ({E FȘ 2) (G 1) (H 1)}
Unim {(A 8) (B 3) ({C DȘ 2) ({E FȘ 2) ({G HȘ 2)}
Unim {(A 8) (B 3) ({C DȘ 2 ) ({E F G H Ș 4)}
Unim {(A 8) ({B C DȘ 5) ({E F G HȘ 4)}
Unim {(A 8) ({B C D E F G HȘ 9)}
Unirea finală {({A B C D E F G HȘ 17)}
Algoritmul nu specifică întotdeauna un arbore unic deoarece nodurile cu mărimile cele mai mici nu pot fi unice la fiecare pas. De asemenea, alegerea ordinii în care două noduri sunt unite este arbitrară.
Reprezentarea arborilor Huffman
Vom începe discutând modul în care arborii sunt reprezentați. Ramurile arborelui sunt reprezentate de o listă ce conține simbolul leaf, simbolul la ramura și mărime:
(define (make-leaf symbol weight)
(list ‘leaf symbol weight) )
(define (leaf? object)
(eq? (car object) ‘leaf) )
(define (symbol-leaf x) (cadr x) )
(define (weight-leaf x) (caddr x) )
Un arbore general va fi o listă de ramură stângă, ramură dreaptă, un set de simboluri și o mărime. Setul de simboluri va fi mai degrabă o listă de simboluri decât o reprezentare mai sofisticată a unui set. Când facem un arbore unind două noduri obținem mărimea arborelui ca sumă a mărimilor nodurilor și setul de simboluri ca uniune a simbolurilor pentru noduri. Din moment ce seturile de simbol sunt reprezentate ca liste putem forma unirea folosind procedura append pe care am definit-o înainte:
(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right) )
(+ (weight left) (weight right) ) ) )
Dacă facem un arbore în acest mod, vom avea următorii selectori:
(define (left-branch tree) (car tree) )
(define (right-branch tree) (cadr tree) )
(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree) )
(caddr tree) ) )
(define (weight tree)
(if (leaf? tree)
(weight-leaf tree)
(caddr tree) ) )
Procedurile de simboluri și mărimi trebuie să facă ceva uîor diferit depinzând de modul cum sunt apelate ele cu o ramură sau cu un arbore general. Aceste proceduri sunt simple exemple de operatori generici(operatori care pot lucra cu mai mai mult de un fel de date).
Procedura de decodare
Procedura următoare implementează algoritmul de decodare specificat mai sus. Ia ca argument o listă de zerouri și unuri, împreună cu un arbore Huffman.
(define (decode bits tree)
(decode-1 bits tree tree) )
Procedura de decodare-1 ia trei argumente: lista de biți, arborele și poziția curentă în arbore.Continuă să se mute în jos pe arbore alegând o ramură dreaptă sau stângă corespunzător cu faptul că, dacă următorul bit din listă este 0 sau 1(aceasta se face cu procedura choose-branch). Când ajungem la o ramură, returnează simbolul acelei ramuri ca fiind următorul simbol din mesaj(adunându-l la restul mesajului) și trece la decodarea restului mesajului începând de la rădăcina arborelui.
(define (decode-1 bits tree current-branth)
(if (null? bits)
‘( )
(let ( (next-branch
(choose-branch (car bits) current-branch) ) )
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (cdr bits) tree tree) )
(decode-1 (cdr bits) tree next-branch) ) ) ) )
(define (choose-branch bit branch)
(cond ( (= bit 0) (left-branch branch) )
( (= bit 1) (right-branch branch) )
(else (error “bad bit – CHOOSE-BRANCH” bit) ) ) )
Seturi de elemente influen|ate
În reprezentarea arborilor, fiecare nod de nonarbore conține un set de simboluri pe care noi trebuie să-l reprezentăm ca o listă simplă. Totuși, algoritmul generator de arbore discutat mai sus necesită faptul de a lucra cu seturi de ramuri și arbori fuzionând în mod succesiv cele mai mici două articole. Din moment ce ni se va cere să găsim în mod repetat cel mai mic articol din set este convenabil să folosim o reprezentare ordonată pentru acest tip de set.
Vom reprezenta un set de ramuri și arbori ca o listă de elemente aranjate în ordinea crescătoare a mărimii. Articolele sunt comparate ,comparând mărimea lor și elementele ce sunt adăugate în set nu sunt incluse deja în set.
(define (adjoin-set x set)
(cond ( (null? set) (list x) )
( (< (weight x) (weight (car set) ) ) (cons x set) )
(else (cons (car set)
(adjoin-set x (cdr set) ) ) ) ) )
Procedura următoare ia ca argument o listă de perechi cu simbol de frecvență cum ar fi ((A 4) (B 2) (C 1) (D 1)) și construieîte un set de ramuri ordonat inițial, gata pentru a fi unit în mod corespunzător algoritmului Huffman:
(define (make-leaf-set pairs)
(if (null? pairs)
‘( )
(let ((pair (car pairs) ) )
(adjoin-set (make-leaf (car pair) ; simbol
(cadr pair) ) ; frecvența
(make-leaf-set (cdr pairs) ) ) ) ) )
CAPITOLUL IV
Reprezentări multiple pentru date abstracte
Am introdus abstractizarea datelor, o metodă pentru a structura sistemele în aîa fel încât marea parte a unui program să fie specificată în mod independent de alegerile implicate în implementarea obiectelor de date pe care manipulează programul. De exemplu, am văzut cum să separăm proiectarea unui program care foloseîte numere raționale de implementarea numerelor raționale în termeni de mecanismele primitive ale limbajului de calcul pentru construirea datelor compuse. Ideea cheie a fost să ridice o barieră de abstracție – în acest caz, selectorii și constructorii pentru numere raționale(make-rat, numer, denom) – care izolează modul în care numerele raționale sunt folosite de reprezentația subliniată în termenii unei structuri de listă. O barireă similară de abstracție izolează detaliile procedurii care rezolvă operații aritmetice raționale(+rat, -rat, *rat, /rat) de procedura nivel cel mai înalt care foloseîte numere raționale. Programul ce rezultă are structura ca în figura 2.1. Aceste bariere de abstractizare a datelor sunt unelte puternice de controlare a complexității. Izolând reprezentația subliniată a obiectelor de date putem împărții sarcina proiectării unui program mare în sarcini mai mici care pot fi rezolvate separat. Dar felul abstracției de date pe care l-am prezentat nu este de ajuns de puternic încă. Într-un sistem mare ar putea să nu aibă sens să vorbim despre “reprezentarea subliniată“ a unui obiect de date.
Pentru a lua un exemplu simplu, numerele complexe pot fi reprezentate în două moduri aproape echivalente: într-o formă carteziană(părți reale și imaginare) și în formă polară(mărime și unghi). Câteodată forma carteziană este mai potrivită, iar cîteodată forma polară este mai potrivită. Într-adevăr este perfect plauzibil să ne imaginăm un sistem în care numerele complexe sunt reprezentate în amândouă modurile și în care operatorii pentru manipularea numerelor complexe va lucra cu oricare dintre reprezentații.
Acum vom învăța cum să facem față la datele care pot fi reprezentate în moduri diferite prin diferite părți de program. Aceasta necesită construirea unor proceduri de operatori generici, care pot opera cu date care pot fi reprezentate mai mult de un mod. Tehnica principală pentru construirea operatorilor generici va fi să lucrăm în termeni de obiecte de date care au tipul manifest, adică obiecte de date care care includ informații explicite despre modul cum sunt ele procesate. Vom discuta de asemenea programarea data-directed, o puternică și cnvenabilî strategie de implementare pentru sistemele de operatori generici. $ncepem cu exemplul simplu al numerelor complexe. Vom vedea cum tipurile manifest și stilul data-directed ne va da posibilitatea să proiectăm reprezentații carteziene și polare saparate pentru numere complexe în timp ce menținem noțiunea de obiecte de date de numere complexe abstracte. Vom realiza aceasta definind operatorii aritmetici pentru numere complexe (+c, -c, *c, /c) în termenii unor selectori care accesează părți ale unui număr compex, indeendent de modul în care numărul este reprezentat:
Utilizarea numerelor complexe
Pachetul complex aritmetic
Reprezentarea carteziană Reprezentarea polară
Structura listei și primitiva aritmetică
fig.2.10
Barierele data-abstraction în sistemul de numere complexe
Sistemul rezultat de numărul complex, cum este în fi în figura 2.10 conține două feluri diferite de bariere de abstracție. Barierele abstracție orizontale joacă același rol ca și cea din figura 2.1. Ele izolează operațiile de nivel înalt de reprezentațiile de nivel jos. În plus, există o barieră verticală care ne dă abilitatea de a priecta în mod separat și de a instala reprezentații alternative. În secțiunea 2.4, vom arăta cum să folosim tipurile manifest și stilul data-directed pentru a dezvolta un pachet de operații aritmetice generice. Aceasta furnizează operatori(add, mul, etc), care pot fi folosiți pentru a manipula tot felul de numere și pot fi ușor extinse când este nevoie de un fel nou de numere
Utilizarea numerelor
Pachetul aritmetic generic
Rational Complex arithmetic Real
arithmetic Rectangular Polar arithmetic
Structura listei și primitiva aritmetică
fig 2.11
Generarea sistemului aritmetic
Figura 2.11 arată structura sistemului pe care îl vom construi. Din perspectiva folosirii de către cineva a numerelor, există un singur operator add, care operează pe orice fel de numere sunt furnizate. De fapt ,add este o interfață generică care permite ca pachete aritmetice reale, raționale și complexe separate să fie accesate în mod uniform de programele care folosesc numere. Mai mult, orice pachet aritmetic individual(cum ar fi pachetul de numere complexe), poate fi în sine accesat prin operatori generici(cum ar fi +c), care combină pachetele proiectate pentru reprezentații diferite. De o importanță particulară pentru proiectantul de sistem este faptul că cineva poate proiecta pachete aritmetice individuale în mod separat și să le combine pentru a produce un pachet arimetic generic folosind stilul data directed, ca o interfață convențională.
4.1 Reprezentarea numerelor complexe
Vom dezvolta un sistem care performează operatorii aritmetici pe numere complexe ca un simplu, dar într-un fel irealistic exemplu a unui program care foloseîte operatori generici. Începem prin discutarea a două reprezentații plauzibile pentru numere complexe ca perechi ordonate: formă carteziană(parte reală și parte imaginară) și formă polară(mărime și unghi).
Secțiunea următoare ne va arăta cum amândouă reprezentații pot fi făcute să coexiste într-un singur sistem prin folosirea tipurilor manifest și a operatorilor generici și vom mai introduce programarea data-directed ca o tehnică pentru a organiza sistemele care folosesc operatori generici. Ca și numerele raționale, numerele complexe sunt reprezentate în mod natural ca perechi ordonate. Setul de numere complexe poate fi gândit ca un spațiu bidimensional cu două axe ortogonale, axa reală și axa imaginară.
Im
y z=x+iy=reiA
r
A
x
figura 2.12
Numere complexe ca vectori
Din acest punct de vedere numărul complex z=x+i*y(unde I2= -1), poate fi gândit ca un vector a cărui coordonată reală este x și a cărui coordonată imaginară este y. Adunarea numerelor complexe se reduce în această reprezentație la adunarea coordonatelor:
partea-reală ( z1+z2)=patea-reală (z1)+partea-reală (z2)
partea-imaginară (z1+z2)=partea-imaginară (z1)+partea-imaginară (z2)
Când înmulțim numerele complexe, este mai natural să ne gândim în termenii unei reprezentări a numărului complex în formă polară ca mărime și unghi cum este arătat în figura 2.12. Produsul a două numere complexe este vectorul obținut întinzând un număr complex prin lungimea celuilalt și apoi rotindu-l prin unghiul celuilalt:
marime(z1z2)=marime(z1) marime(z2)
unghi(z1z2)=unghi(z1) +unghi(z2)
Astfel, sunt două reprezentații diferite pentru numere complexe, care sunt potrivite pentru operații diferite. Totuși, din punctul de vedere al cuiva care scrie un program ce foloseîte numere complexe, principiul abstracției datelor sugerează faptul că toate operațiile de manipulare a numerelor complexe pot fi folositoare indiferent de care reprezentație este folosită de calculator. De exemplu , adesea este folositor să fim capabili să găsim mărimea unui număr complex, care este specificată de coordonatele carteziene. În mod similar, este adesea folositor să fim capabili să determinăm partea reală a unui număr complex, care este specificată de coordonatele polare. Pentru a proiecta un astfel de sistem, putem folosi aceeași strategie de abstracție a datelor, pe care am folosit-o în proiectarea pachetului cu numere raționale. Presupunem că operatorii pe numere complexe sunt implementați în termenii următorilor patru selectori: real-part,imag-part,magnitude și angle. De asemenea presupunem că avem proceduri pentru construirea numerelor complexe: make-rectangular, returnează un număr complex cu părți reale și imaginare date și make-polar returnează un număr complex cu mărime și unghi date. Aceste proceduri cu proprietatea că pentru orice număr complex z, amândouă
(make-rectangular (real-part z) (imag-pat z))
și
(make-polar (magnitude z) (angle z))
produc numere comlexe care sunt egale cu z.
Folosind acești constructori și selectori putem implementa numărul complex aritmetic folosind datele abstracte specificate de constructori și selectori cum am făcut pentru numerele raționale. După cum este arătat în formulele de sus, putem aduna și scădea numerele complexe în termeni de părți reale și imaginare în timp ce înmulțirea și împărțirea numerelor complexe se va face în termeni de mărimi și unghiuri:
(define (+c z1 z2)
(make-rectangular (+ (real-part z1) (real-part z2) )
(+ (imag-part z1) (imag-part z2) ) ) )
(define (-c z1 z2)
(make-rectangular (- (real-part z1) (real-part z2) )
(- (imag-part z1) (imag-part z2) ) ) )
(define (*c z1 z2)
(make-polar (* (magnitude z1) (magnitude z2) )
(+ (angle z1) (angle z2) ) ) )
(define (/c z1 z2)
(make-polar (/ (magnitude z1) (magnitude z2) )
(- (angle z1) (angle z2) ) ) )
Pentru a completa pachetul de numere complexe, trebuie să alegem o reprezentație și trebuie să implementăm constructorii și selectorii în termeni de numere primitive și structuri de liste primitive. Sunt două alegeri posibile evidente. Putem reprezenta un număr complex în formă carteziană ca o pereche (pate reală și parte imaginară) sau în formă polară ca o pereche (mărime și unghi) . Pe care o vom alege ?
Dacă reprezentăm un număr complex în formă carteziană, atunci selectarea părții reale și imaginare este directă, cum este construirea unui număr complex cu părți reale și imaginare date. Pentru a găsi mărimea și unghiul sau pentru a construi un număr complex, cu o mărime și un unghi dat, vom folosi relațiile:
x= r cosA, r =
y = r sinA, A=arctan (y,x),
care leagă părțile reale și imaginare(x,y) la mărimea și unghiul (r,A). Aceasta duce la folosirea constructorilor și selectorilor următori:
(define (make-rectangular x y) (cons x y) )
(define (real-part z) (car z) )
(define (imag-part z) (cdr z) )
(define (make-polar r a)
(cons (* r (cos a) ) (* r (sin a) ) ) )
(define (magnitude z)
(square (car z) ) (square (cdr z) ) ) ) )
(define (angle z)
(atan (cdr z) (car z) ) )
Pe de altă parte, putem alege, să implementăm numerele complexe în formă polară. Dacă este aîa, atunci selectarea mărimii și unghiului va fi directă, dar va trebui să folosim trigonometria pentru a afla părțile reale și imaginare.Iată setul de proceduri corespunzătoare:
(define (make-rectangular x y)
(cons (sqrt (+ (square x) (square y) ) )
(atan y x) ) )
(define (real-part z)
(* (car z) (cos (cdr z) ) ) )
(define (imag-part z)
(* (car z) (sin (cdr z) ) ) )
(define (make-polar r a) (cons r a) )
(define (magnitude z) (car z) )
(define (angle z) (cdr z) )
Disciplina abstracției datelor ne asigură că implementarea operatorilor numerelor complexe aritmetice +c, -c, *c, /c este independentă de care reprezentațe o vom alege.
4.2 Tipurile manifest
Un mod de a viziona abstractizarea datelor este ca o aplicație la proiectarea programului a “principiului de cel mai mic angajament”. Prin stabilirea selectorilor și constructorilor ca o barieră de abstracție, putem amâna până la ultimul moment posibil alegerea unei reprezentații concrete pentru obiectele de date și astfel să reținem flexibilitatea maximă în proiectarea sistemului. De fapt, principiul cu cel mai mic angajament poate fi dus în extremis decât cum am văzut până acum. Dacă dorim, putem menține ambiguitatea reprezentării chiar și după ce am proiectat selectorii și constructorii, hotărând să reprezentăm câteva numere complexe în formă polară și câteva în formă carteziană. Totuși, dacă amândouă feluri de reprezentații sunt incluse într-un singur sistem, vom avea nevoie de un mod pentru a distinge datele în formă carteziană de datele în formă polară. Altfel, dacă ni se va cere, de exemplu, să găsim mărimea unei perechi (3, 4), nu vom îti dacă să răspundem 5 (interpretând numărul în formă carteziană) sau 3 (interpretând numărul în formă polară). Un mod direct de a realiza această distincție este de a include un “tip ” – în acest caz, rectangular sau polar- ca părți a fiecărui număr complex. apoi când avem nevoie să manipulăm un număr complex, putem folosi tipul pentru a hotărî care selector îl vom aplica. Un obiect de date care are un tip, care poate fi recunoscut și testat se spune că are tip manifest. Pentru a manipula datele tipizate, vom presupune că avem două proceduri, type și contents, care extrag din obiectul de date tipul și conținuturile actuale (coordonate polare sau carteziene în cazul unui număr complex). Vom postula de asemenea o procedură, attach-type, care ia un tip și conținuturile și produce un obiect de date tipizate. Un mod direct de a implementa aceasta este să folosim structura obișnuită de listă:
(define (attach-type type contents)
(cons type contents) )
(define (type datum)
(if (not (atom? datum) )
(car datum)
(error “bad typed datum – TYPE” datum) ) )
(define (contents datum)
(if (not (atom? datum) )
(cdr datum)
(error “bad typed datum – CONTENTS” datum) ) )
Folosind aceste proceduri, putem defini predicatele rectangular? și polar?, care recunosc numerele polare și carteziene, respectiv:
(define (rectangular? z)
(eq? (type z) ‘rectangular) )
(define (polar? z)
(eq? (type z) ‘polar) )
Acum modificăm constructorii pentru numere complexe pentru a include tipul ca parte a numărului. Pentru a consrui un număr complex în formă carteziană, fiind date părțile reale și imaginare, folosim:
(define (make-rectangular x y)
(attach-type ‘rectangular (cons x y) ) )
Pentru a construi un număr complex în formă polară, fiind date mărimea și unghiul, folosim:
(define (make-polar r a)
(attach-type ‘polar (cons r a) ) )
Selectorii noștri abstracți pentru numere complexe sunt acum definiți în termeni de selectori potriviți pentru numere complexe netipizate. Putem folosi tipul număr complex pentru a selecta procedura potrivită, pentru a lucra cu un număr de un tip dat. Aceste proceduri pot fi împărțite în două “pachete”,unul care se ocupă cu formele carteziene și celălalt în formă polară. Folosim contents pentru a dezvălui elementele netipizate:
(define (real-part z)
(cond ( (rectangular? z)
(real-part-rectangular (contents z) ) )
( (polar? z)
(real-part-polar (contents z) ) ) ) )
(define (imag-part z)
(cond ( (rectangular? z)
(imag-part-rectangular (contents z) ) )
( (polar? z)
(imag-part-polar (contents z) ) ) ) )
(define (magnitude z)
(cond ( (rectangular? z)
(magnitude-rectangular (contents z) ) )
( (polar? z)
(magnitude-polar (contents z ) ) ) ) )
(define (angle z)
(cond ( (rectangular? z)
(angle-rectangular (contents z) ) )
( (polar? z)
(angle-polar (contents z) ) ) ) )
Ca și procedurile subliniate în fiecare din pachetele ce se ocupă cu numere complexe netipizate, putem folosi selectorii definiți n secțiunea anterioară după ce am renumit fiecare procedură astfel încât să evităm conflictele de nume. Iată selectorii pentru reprezentarea carteziană:
(define (real-part-rectangular z) (car z) )
(define (imag-part-rectangular z) (cdr z) )
(define (magnitude-rectangular z)
(sqrt(+ (square (car z) )
(square (cdr z) ) ) ) )
(define (angle-rectangular z)
(atan (cdr z) (car z) ) )
Selectorii pentru reprezentarea polară sunt:
(define (real-part-polar z)
(* (car z) (cos (cdr z) ) ) )
(define (imag-part-polar z)
(* (car z) (sin (cdr z) ) ) )
(define (magnitude-polar z) (car z) )
(define (angle-polar z) (cdr z) )
Utilizarea numerelor complexe
Pachetul aritmetic Complex
Pachetul cartezian Pachetul polar
Structura listei și primitiva aritmetică
fig.2.13
Structura sistemului generic aritmetic Complex
Sistemul de numere complexe ce rezultă are structura arătată în figura 2.13. Observăm că sistemul poate fi descompus în trei părți relativ independente: pachetul cu numere complexe aritmetice, pachetul reprezentării carteziene și pachetul reprezentării polare. Fiecare din aceste pachete ar fi putut fi proiectate fără să îtim nimic despre celelalte. De exemplu, pachetele polare și carteziene ar fi putut fi scrise separat de doi oameni separați și apoi amândouă să fi fost folsite ca reprezentații subliniate de un al treilea programator, implementând procedurile aritmetice complexe +c, -c, *c, /c în termenii unei interfețe abstracte constructor / selector.
Din moment ce fiecare obiect de date este etichetat cu tipul său, selectorii pot opera pe date într-un mod generic. Aceasta înseamnă, că fiecare selector poate fi definit să aibă un comporatament ce depinde de tipul particular al datei ce este aplicat. Când un selector generic operează pe un număr de tip polar, arată tipul și trece conținuturile netipizate la pachetul polar. Invers, când un număr este construit și ” exportat” din pachetul polar este dat un tip manifest astfel încât poate fi recunoscut potrivit de procedurile de nivel înalt. Această disciplină de a arăta și a ataîa tipurile că obiectele de date sunt trecute de la un nivel la altul, poate fi o strategie organizatorică importantă, după cum vodea în secțiunea următoare.
Deși acest mod de organizare a operatorilor generici este foarte valoros, există în sistemul nostru două puncte slabe. Unul este acel că procedurile de interfață generică (real-part, imag-part, magnitude și angle) trebuie să îtie despre toate reprezentațiile diferite. În secțiunea următoare vom introduce programarea data-directed, o tehnică ce poate fi folosită pentru a lucra cu această problemă. O altă slăbiciune a sistemului nostru este aceea că ,deși pachetele separate pt fi proiectate separat, trebuie să fim siguri că nu sunt două proceduri în întregul sistem ce au același nume. De aceea vom adăuga numele pachetului la fiecare dintre selectorii procedurii în exemplul de mai sus.
4.3 Programarea cu data-directed
Folosirea tipurilor manifest și a operatorilor generici este o unealtă puternică pentru obținerea modularității în proiectarea sistemului, dar tehnicile pe care le avem disponibile în acest moment sunt pre slabe pentru a rezolva probleme pe o scară mai largă. De exemplu, să presupunem că cineva a priectat un pachet folosind o reprezentație nouă pentru numerele complexe și ne cere nouă să punem față în față aceasta cu sistemul nostru de numere complexe. Am avea nevoie să identificăm această nouă reprezentație cu un tip și apoi să adăugăm câte o propoziție la fiecare dintre procedurile de intertfață generice(real-part, imag-part, magnitude, angle), pentru a verifica noul tip și accesa selectorul potrivit în noul pachet. Aceasta nu este chiar o problemă după cum arată sistemul de numere complexe, dar să presupunem că nu sunt numai două reprezentații diferite de numere complexe, ci sute. Să presupunem că există mai mulți selectori generici de menținut în interfața de date abstracte. Să presupunem de fapt că nici un orogramator nu știe toate procedurile de interfață sau toate reprezentațiile. Totuși , aceasta nu este probabil să fie cazul cu sistemele care fac operații aritmetice, problema este reală și trebuie să fie adresată în programe cum sunt sistemele de baze de date manageriale pe scară largă și sistemele de simboluri algebrice. Ce avem nevoie este un mijloc pentru modularizarea proiectării sistemului mai departe. Aceasta este furnizată de tehnica de programare cunoscută sub numele de data-directed.
Types
Polar Rectangular
real-part real-part-polar real-part-rectangular
Operators imag-part imag-part-polar imag-part-rectangular
magnitude magnitude-polar magnitude-rectangular
angle angle-polar angle-rectangular
Figura 2.14
Tabel cu operatorii pentru sistem de numere complexe
Pentru a înțelege cum funcționează programarea data-directed, începem cu observația că de c`te ori lucrăm cu un număr de operatori generici care sunt comuni la un număr de tipuri diferite, lucrăm de fapt cu un tabel bidimensional, cu operatorii ce conține operatorii posibili pe o axă și tipurile posibile pe altă axă. Intrările în tabel sunt procedurile ce implementează c`te un operator pentru fiecare din tipurile de operații prezente. În sistemul de numere complexe dezvoltate în secțiunea anterioară, corespondența dintre numele operatorului, tipul de date și procedura actuală a fost răsp`ndită printre diferite propoziții condiționale din procedurile generice de interfață. Dar acceași informație ar putea fi organizată într-un tabel după cum arată în figura 2.14. Programarea data-directed este o tehnică de proiectare a programelor pentru a lucra cu astfel de tabel în mod direct. Anterior am implementat în mecanismul care pune față în față pachetul de operații aritmetice complexe cu două pachete de reprezentații ca un set de proceduri. Aici vom implementa interfața ca o singură procedură ce are grijă ca acestor combinații a operatorului și tipului din tabel să li se găsească procedura de aplicare corectă și apoi o aplicăm conținutului din operatori. Dacă facem aceasta, apoi să adăgăm un nou pachet de reărezentații la sistem nu este nevoie să schimbăm nici o procedură existentă, avem nevoie să adăugăm noi intrări în tabel.
Pentru a implementa acest plan, presupunem că avem două proceduri put și get, pentru manipularea tabelului operator și tip:
(put <type> <op> <item>) instalează pe <item> în intrarea în tabel indexat de <type> și <op>
(get <type> <op>) are grijă de intrarea <type> și <op> și returnează articolul găsit aici. Dacă nu este găsit nici un articol, procedura returnează nil.
Deocamdată, putem presupune că put și get sunt operatori primitivi
în limbajul nostru . Iată cum operează sistemul de data-directed. Programatorul care a definit pachetul de reprezentație carteziană, l-ar putea instala în sistemul de operații aritmetice complexe, adăug`nd intrări în tabel, care spun sistemului cum să opereze pe numere carteziene:
(put ‘rectangular ‘ real-part real-part-rectangular)
(put ‘rectangular ‘ imag-part imag-part-rectangular)
(put ‘rectangular ‘magnitude magnitude-rectangular)
(put ‘rectangular ‘angle angle-rectangular)
Între timp un alt programator ar putea să lucreze la definițiile cu formă polară, independent de cele ale colegului său și definițiile complete ar pute fi în mod similar pusă față în față cu pachetul de numere complexe:
(put ‘polar ‘real-part real-part-polar)
(put ‘polar ‘imag-part imag-part-polar)
(put ‘polar ‘magnitude magnitude-polar)
(put ‘polar ‘angle angle-polar).
Pachetul de operații aritmetice complexe accesează singur tabela prin mijloace de procedură generală “operator” numită operate, care aplică un operator generic unui obiect uit`ndu-se în tabel sub numele operatorului și tipului obiectului aplicând procedura ce rezultă dacă este vreuna prezentă:
(define (operate op obj)
(let ( (proc (get (type obj) op) ) )
if (not (null? proc) )
(proc (contents obj) )
(error “Operator nedefinit pentru acest tip – OPERATE” )
(list op obj) ) ) ) )
Folosind operate, putem defini procedurile generice de interfață după cum urmează:
(define (real-part obj) (operate ‘real-part obj) )
(define (imag-part obj) (operate ‘imag-part obj) )
(define (magnitude onj) (operate ‘magnitude obj) )
(define (angle obj) (operate ‘angle obj) )
Aceste proceduri nu trebuie schimbate deloc, dacă se adaugă o nouă reprezentație la sistem.
Strategia generală de verificare a tipului unei date și apelarea unei proceduri potrivite se numește expedierea unui tip și programarea data-directed este un mod extrem de flexibil pentru a organiza expedierea. Acest fel de “interfață convențională“ pote fi folosită pentru a combina pachetele de reprezentații care au fost construite separat. Această tehnică este folosită regulat de programatorii experți pentru a spori extensibilitatea și modularitatea sistemelor lor.
Trecerea mesajelor
Ideea cheie a programării data-directed este de a trata operatorii generici în programe, ocup`ndu-se în mod implicit de tabelele operator și tip cum ar fi tabelul din figura 2.14 .Un stil mai tradițional de programare pe care l-am folosit a organizat trimiterea cerută pe tipuri pun`nd fiecare operator să aibă grijă de trimiterea proprie. De fapt, acest stil de programare descompune tabelul operator și tip în și ruri și fiecare procedură operatorie generică, reprezentând un șir al tabelului. O strategie de implementare alternativă este de a descompune tabela în coloane și în loc de a folosi “operatori inteligenți” ce trimit la tipul de date să lucreze cu “obiecte de date inteligente” , care trimit la nume de operatori. Putem face aceasta aranj`nd lucrurile astfel încât un obiect de date cum ar fi cum ar fi un număr cartezian să fie reprezentat ca o procedură ce ia ca date de intrare numele operațiilor cerute și face operațiile indicate. Într-o astfel de disciplină, make-rectangular ar pute fi scris astfel:
(define (make-rectangular x y)
(define (dispatch m)
(cond ( (eq? m ‘real-part) x)
( (eq? m ‘imag-part) y)
( (eq? m ‘magnitude)
(sqrt (+ (square x) (square y) ) ) )
( (eq? m ‘angle) (atan y x) )
(else
(error “Op necunoscut – MAKE-RECTANGULAR” m) ) ) )
dispatch)
Procedura operate corespunzătoare ce aplică o operațiune generică la un obiect de date aprovizionează pur și simplu numele operațiilor la obiectul de date și lasă obiectul să lucreze:
(define (operate op obj) (obj op) )
Observăm că “obiectul de date” returnat de make-rectangular este o procedură – procedura internă dispatch. Aceasta este o procedură care este invocată c`nd operate cere o operație de făcut.
Acest stil de programare se numește trecerea mesajului. Numele vine de la imaginea că un obiect de date este o entitate ce primește numele operației cerute ca un mesaj. Am văzut deja un exemplu de trecerea mesajelor, când am văzut că cons, car și cdr ar putea fi definite fără nici un obiect de date și numai proceduri. Aici vedem că trecerea mesajelor nu este un truc matematic, ci o tehnică folositoare pentru organizarea sistemelor cu operatori genericiVom continua să folosim programarea data-directed, pentru a discuta operatorii aritmetici generici. Trecerea mesajelor este o unealtă puternică pentru a structura programele de simulare.
CAPITOLUL V
Sisteme cu operatori generici
În scțiunea anterioară am văzut cum să proiectăm sistemele în care obiectele de date pot fi reprezentate în mai mult de un fel. Ideea cheie este de alega pachetul ce specifică operațiile cu date la mai multe pachete ce implementează reprezentații diferite prin mijloace de proceduri generice de interfață. Acum vom vedea cum să folosim acceași idee nu numai pentru a defini operatorii ce sunt generici la diferite reprezentații și de asemenea să definim operatorii ce sunt generici la diferite tipuri de operanzi.
Vom lua în considerare cum să proiectăm o mulțime de operatori aritmetici ce lucrează pe toate tipurile diferite de “nume”.Am văzut deja mai multe pachete diferite de operatori aritmetici: operatori aritmetici primitivi (+, -, *, /) construiți în limbajul nostru, operatori aritmatici cu numere raționale ( +rat, -rat, *rat, /rat) pe care i-am implementat la început și operatori aritmetici de numere complexe generici.Vom folosi acum tehnicile data-directed, pentru a construi un pachet de operatori aritmetici ce încorporează toate sistemele aritmetice pe care le-am construit deja. Mai mult, operatorii noștri vor fi extensibili în sensul că, dacă mai târziu vom veni cu o nouă clasă de numere, vom putea foarte ușor să le adăugăm pe acestea la sistem fără să schimbăm vreunul din programele pe care le-am descris deja.
5.1 Operatori aritmetici generici
Sarcina proiectării operatorilor aritmetici generici este la fel cu cea a proiectării operatorilor generici de numere complexe. Ne-ar plăcea de exemplu să aven un operator generic de adunare add, care ar lucra precum adunarea primitivă obișnuită + pe numere obișnuite, precum +rat pe numere raționale și +c pe numere complexe. Putem implementa procedura add și ceilalți operatori aritmetici generici, pentru a implementa selectorii generici pentru numere complexe. Vom atașa un tip manifest la fiecare fel de număr și vom face ca operatorii generici să trimită la un pachet potrivit, corespunzător cu tipul de date al argumentelor sale. Începem prin instalarea unui pachet pentru a lucra cu numere obișnuite, care sunt numere simple ale limbajului nostru. Ne vom referi la aceasta ca un tip number. Operatorii aritmetici din acest pachet sunt în mod esențial operatorii artmetici simpli:
(define (+ number x y)
(make-number (+ x y) ) )
(define (- number x y)
(make-number (- x y) ) )
(define (* number x y)
(make-number (* x y) ) )
(define (/ number x y)
(make-number (/ x y) ) )
Aici, make-number este o procedură ce atașează un tip manifest potrivit argumentului:
(define (make-number n)
(attach-type ‘number n) )
Următorul pas este de a lega operatorii din pachet la operatorii generici add, sub, mul și div. Ca și înainte ,vom plasa procedurile în tabel după tipul de date și numele operatorului generic:
(put ‘number ‘add +number)
(put ‘number ‘sub -number)
(put ‘number ‘mul *number)
(put ‘number ‘div /number)
Operatorii generici sunt definiți după cum urmează:
(define (add x y) (operate-2 ‘add x y) )
(define (sub x y) (operate-2 ‘sub x y) )
(define (mul x y) (operate-2 ‘mul x y) )
(define (div x y) (operate-2 ‘div x y) )
Ca și cu selectorii de numere complexe operatorii aritmetici generici vor folosi o procedură generală operate, ce face o trimitere în mod corespunzător cu tipul argumentului. Totuși , în timp ce selectorii pentru numere complexe au fost operatori cu un singur argument, operatorii aritmetici generici sunt operatori cu două argumente. Deci nu putem folosi aceeași procedură operate ca și înainte. În locul acesteia vom folosi următoarea procedură pentru a face trimitere:
(define (operate-2 op arg1 arg2)
(let ( (t1 (type arg1) ) )
(if (eq? t1 (type arg2) )
(let ( (proc (get t1 op) ) )
(if (not (null? proc) )
(proc (contents arg1) (contents arg2) )
(error
“Operator nedefinit de acest tip – OPERATE-2”
(list op arg1 arg2) ) ) )
(error “Operator nedefinit de acest tip – OPERATE-2”
(list op arg1 arg2) ) ) ) )
Operate-2 verifică dacă operanzii au acalași tip și dacă este așa, trimite la procedura care a fost instalată în tabel pentru tipul și operatorul care sunt date. Dacă nu există o astfel de procedură, atunci operate-2 semnalează o eroare. Dacă doi operanzi nu au același tip, operate-2 semnalează o eroare. Acesta nu este un lucru foarte corect de făcut. De exemplu, dacă încercăm să adunăm numărul (simplu) 3 cu numărul (complex) 2+4i, operate-2 se va pl`nge că tipurile nu se potrivesc. ȘI totuși ne-am aștepta ca un sistem rezonabil să producă răspunsul 5+4i. Pe de altă parte, se dovedește că aranjarea pentru acest fel de comporatament rezonabil deschide o posibilitate enormă de obțineri privind interacțiunile dintre date de diferite tipuri. Vom renunța la această problemă acum și ne vom întoarce la ea în secțiunea 4.2.
Interfațe ale pachetului de numere complexe
Acum când cadrul sistemului aritmetic generic este în loc, este ușor să încorporăm pachetul de numere complexe. Începem prin scrierea unei proceduri ce atașează tipul complex la numerele complexe astfel ìncât să potă fi recunoscute în afara pachetului de numere complexe:
(define (make-complex z)
(attach-type ‘complex z) )
Vom defini în continuare operatorii aritmetici complexi ce sunt apelați de operatorii generici ai reprezentării de numere complexe:
(define (+complex z1 z2) (make-complex (+c z1 z2) ) )
(define (-complez z1 z2) (make-complex (-c z1 z2) ) )
(define (*complex z1 z2) (make-complex (*c z1 z2) ) )
(define (/complex z1 z2) (make-complex (/c z1 z2) ) )
În final vom instala operatori aritmetici complexi în poziții potrivite în tabela de operatori aritmetici generici vor face trimiterea în mod corect:
(put ‘complex ‘add +complex)
(put ‘complex ‘sub -complex)
(put ‘complex ‘mul *complex)
(put ‘complex ‘add /complex)
Ceea ce avem aici este un sistem de tip două-nivele. Un număr complex tipic cum ar fi numărul construit de
(make-complex (make-rectangular 3 4) )
va fi reprezentat cum este în figura 2.15.
Tipul exterior (complex) este folosit pentru a direcționa numărul la pachetul de numere complexe. Odată înăuntrul pachetului de numere complexe, următorul tip (rectangular) este folosi pentru a direcționa numărul la pachetul de numere carteziene. În mod strict, rectangular și polar nu sunt tipuri de numere deloc, ci numai tipuri pentru conținutul unui număr complex.
figura 2.15
Obiectul construit de (make-complex (make-rectangular 3 4))
Într-un sistem mai mare și complicat, pot fi mai multe nivele fiecare fiind pus față în față cu următorul prin mijloacele unor operatori generici. Cum un obiect de date este trecut “în jos”, tipul exterior care este folosit pentru a-l direcționa la pachetul potrivit este dat la o parte(aplicând contents) și următorul nivel al tipului devine vizibil pentru a fi folosit pentru a trimite mai departe.
5.2 Combinarea operanzilor de diferite tipuri
Am văzut cum să definim un sistem aritmetic unit ce cuprinde numere obișnuite, numere complexe, numere raționale și orice alt tip de numere pe care am putea hotărî să -l inventăm, dar am ignorat o problemă imporatantă. Operatorii pe care i-am definit p`nă acum, tratează diferitele tipuri de date ca fiind complet independente. Astfel sunt pachete separate pentru a aduna, să spunem două numere obișnuite sau două numere complexe. Ceea ce nu am luat încă în considerare este faptul că este de înțeles să definim operațiile ce trec limitele tipurilor cum ar fi adunarea unui număr complex cu un număr obișnuit. Am ajuns la mari greutăți pentru a introduce bariere între părți ale programelor noastre astfel îcât să poată fi dezvoltate și înțelese în mod separat. Ne-ar plăcea să introducem noi operații în moduri controlate atent astfel încât să putem suporta operațiile de trecere a tipului fără să trecem în mod serios de limitele de modul. Un mod de a ne ocupa de operațiile de trecere a tipului este de a proiecta un operator diferit pentru fiecare pereche posibilă de tipuri pentru care operația este validă. De exemplu, am putea avea operații de adunare +number-complex(care adună un număr obișnuit cu un număr complex), +rational-complex, ș. a. m. d.Apoi am pute aranja acestea într-un tabel cu trei dimensiuni ce indexează procedurile potrivite după numele operatorului generic tipul primului argument și tipul celui de-al doilea argument. Suportul pentru un astfel de tabel ar putea fi introdus în procedura
operate-2 din secțiunea 2.4.1.
Această metodă a tabelului cu trei dimensiuni ne permite să combinăm numere de diferite tipuri, dar la un preț enorm. Dacă sunt n tipuri diferite în sistemul nostru avem nevoieîn general de a proiecta n2 versiuni diferite de fiecare operator generic. Într-un astfel de sistem costul introducerii unui nou tip nu este numai construirea unui pachet de operatori pentru acel tip, ci de asemenea construirea și instalarea unor proceduri ce implementează operațiile de trecere a tipului. Dacă sistemul nostru include nu numai operatori binari ci și operatori pe 3,4 sau mai multe argumente ce pot avea mai multe tipuri diferite, pedeapsa pentru introducerea unui nou tip este chiar mai severă.
Constrângere
În situații generale de operații, care nu sunt în mod complet în relație, purtându-se pe tipuri în mod complet nelegate, metoda folosirii unui tabel în trei dimensiuni, pentru a lucra cu operanzi de diferite tipuri poate fi într-un fel greoi, este cea mai bună metodă la care cineva pote să spere. Din fericire, putem în mod obișnuit să facem mai bine, având avantajul structurii de adunare ce poate fi latentă în sistemul nostru de tip. Adesea, diferitele tipuri de date nu sunt complet independente și pot exista moduri prin care obiectele de un anumit tip pot fi vizionate ca fiind de alt tip. Acest proces se numește constrângere. De exemplu, dacă suntem puși să combinăm în mod aritmetic un număr obișnuit cu un număr complex, putem viziona numărul obișnuit ca un număr complex a cărui parte imaginară este 0. Aceasta transformă problema în aceea a combinării a două numere complexe, care pot fi înm`nuite într-un mod obișnuit de pachetul operațiilor aritmetice complexe. În general putem implementa această idee, proiect`nd procedurile de restricțiece transformă un obiect de un anumit tip într-un obiect echivalent al altui tip. Iată o procedură tipică de restricțiece transformă un număr obișnuit dat într-un număr complex cu parte reală și parte imaginară 0:
(define (number ->complex n)
(make-complex (make-rectangular (contents n) 0) ) )
Instalăm aceste proceduri de constr`ngere, într-un tabel special de restricțieindexat după numele a două tipuri:
(put-coercion ‘number ’complex number -> complex)
În general, câteva din spațiile din tabel vor fi goale pentru că nu este posibil în mod general să constr`ngi un obiect de date arbitrare de fiecare tip în altfel de tipuri. De exemplu, nu avem moduri pentru a constrânge un număr complex arbitrar într-un număr obișnuit, astfel că nu va fi nici o procedură generală complex->number inclusă în tabel.
Odată ce tabela de restricțiea fost setată, putem mânui constr`ngerea într-un mod de date direcționate modific`nd procedura operate-2, dată înainte,după cum urmează. Când ni se cere să operăm pe două obiecte obj-1 și obj-2 , verificăm să vedem dacă au același tip. Dacă este așa trimitem la procedură pentru a se ocupa cu acel tip exact ca înainte. Dacă tipurile sunt diferite verificăm în tabelul de restricțiesă vedem dacă obiectul de tipul 1, pot fi constrânse la tipul 2. Dacă este așa, constrângem obj-1 și încercăm operația din nou. Dacă obiectele de tipul 1 nu pot fi în general constrânse la tipul 2, vom încerca constr`ngerea altfel pentru a vedea dacă există vreun mod pentru a constrânge obj-2 la tipul lui obj-1. Dacă nu există nici un mod cunoscut pentru a constr`nge vreunul din tipuri la celălalt renunțăm. Iată procedura:
(define (operate-2 op obj1 obj2)
(let ( (t1 (type obj1) ) (t2 (type obj2) ) )
(if (eq? t1 t2)
(let ( (proc (get t1 op) ) )
(if (not (null? proc) )
(proc (contents obj1) (contents obj2) )
(error
“Operator nedefinit în acest tip – OPERATE-2”
(list op obj1 obj2) ) ) )
(let ( (t1 ->t2 (get-coercion t1 t2) )
(t2 ->t1 (get-coercion t2 t1) ) )
(cond ( (not (null? t1 ->t2) )
(operate-2 op (t1 ->t2 obj2) obj2) ) )
( ( (null? t2 ->t1) )
(operate-2 op obj1 (t2 ->t1 obj2) ) )
(else
(error
“Operanzi care nu sunt în tip – OPERATE-2”
(list op obj1 obj2) ) ) ) ) ) ) )
Această schemă de restricții pentru operatori binari are multe avantaje asupra metodei de a folosi un tabel nestructurat pe trei dimensiuni, cum este arătat mai sus. Deși mai avem nevoie să scriem procedurile de restricție pentru a relata tipurile(posibil n2 proceduri pentru un sistem cu n tipuri). Aven nevoie să scriem numai o singură procedură pentru fiecare pereche de tipuri, mai degrabă decât o procedură diferită pentru fiecare pereche de tipuri și fiecare operatori generici. Ceea ce luăm în considerare aici este faptul că, transformarea potrivită dintre tipuri depind numai de tipuri în sine și nu de operatorul care trebuie aplicat. Pe de altă parte, există aplicații pentru care schema noastră de restricțienu este destul de generală. Chiar și când, niciunul dintre obiectele care trebuie să fie combinate nu pot fi convertite la tipul celuilalt. Există totuși posibilitatea de face această operație convertind am`ndouă obiectele la cel de-al treilea tip. Pentru a lucra cu o asemenea complexitate și a menține modularitatea în programele noastre este necesar în mod obișnuit să construim sisteme care au avantajul unei stucturi mai îndepărtate în relațiile dintre tipuri, după cum vom discuta în continuare.
Ierarhii de tipuri
Schema de restricțieprezentată mai sus s-a bazat pe existența relațiilor naturale dintre perechile de tipuri. Adesea există structuri mai globale în care tipuri diferite fac legătura cu altele. De exemplu, presupunem că vom construi un sistem aritmetic generic pentru a m`nui numere întregi raționale reale și numere complexe. Într-un altfel de sistem este natural de a privi un număr într-un mod special de număr rațional care este în schimb un fel special de număr real care este un fel special de număr complex. Ceea ce avem de fapt este o așa numită ierarhie a tipurilor în care de exemplu întregii sunt un subtip al numerelor raționale(adică orice operator care poate fi aplicat la un număr rațional, poate fi automat aplicat la un întreg). Invers , spunem că numerele raționale formează supertip(extratip) de întregi. Ierarhia particulară pe care o avem aici este de un mod foarte simplu în care fiecare tip are cel puțin un supertip și fiecare un subtip. O astfel de structură, numită turn este ilustrată în figura 2.16.
complex
real
rational
integer
fig 2.16
Tipurile turn
Dacă avem o structură turn, putem simplifica problema adăugării unui nou tip la ierarhie pentru care avem nevoie să specificăm cum tipul nou este încadrat în următorul tip superior de deasupra(supertip) și cum este supertipul al tipului de jos. De exemplu, dacă vrem să adunăm un întreg la un număr complex, nu avem nevoie să definim în mod explicit o procedură de restricțiespecială integer->complex. În schimb, definim cum un întreg poate fi transformat într-un număr rațional, și cum un număr rațional este transformat într-un număr complex. Vom permite apoi sistemului să transforme numărul întreg în număr complex prin acești pași și apoi să adunăm cele două numere complexe. Putem reproiecta procedura operate-2 în modul următor: pentru fiecare tip avem nevoie să furnizăm un operator raise, care să ridice obiectele la tipul de un nivel în turn. Apoi când sistemului i se cere să opereze pe două obiecte de tipuri diferite poate să ridice în mod succesiv la tipul superior până când cele două obiecte sunt la cele două nivele în turn.
Un alt avantaj al turnului este ecela că putem implementa ușor, că fiecare tip moștenește toate definițiile oferite de tipul superior. De exemplu, dacă nu furnizăm o procedură specială pentru găsirea părții reale a unui întreg, ne vom aștepta totuși că real-part va fi definită pentru întregi în virtutea faptului că întregii sunt un subtip al numerelor complexe. ntr-un turn putem face ca aceasta să se înt`mple printr-o modificare simplă la procedura operate. Dacă operatorul cerut nu este definit direct pentru tipul obiectului dat, ridicăm obiectul la tipul să u superior și încercăm din nou. Ne cățărăm astfel pe turn, transform`nd operanzii până unde mergem, până când fie vom găsi un nivel la care vom putea face operațiile dorite, fie vom ajunge în vârf(caz în care vom renunța).
Totuși , un alt avantaj al turnului pe o ierarhie mai generală este acela că ne oferă un mod simplu de a micșora un obiect de date la cea mai simplă reprezentație. De exemplu, dacă adunăm 2+3I cu 4-3I, ar fi bine să obținem răspunsul ca fiind întregul 6, decât numărul complex 6+0I.
Insuficiențele ierarhiilor
Dacă tipurile de date din sistemul nostru pot fi aranjate în mod natural într-un turn, simplifică foarte mult problema lucrului cu operatori generici pe tipuri diferite, după cum am văzut. Figura 2.17 ilustrează un aranjament mai complex de tipuri amestecate, aceasta arătând relațiile dintre tipuri diferite de figuri geometrice
poligon
patrulater
triunghi trapez kite
triunghi triunghi paralelogram
isoscel dreptunghic
dreptunghi romb
triunghi triunghi patrat
echilateral dreptunghic
isoscel
fig 2.17
Vedem că în general, un tip poate avea mai mult decât un subtip. Triunghiurile și patrulaterele, de exemplu, sunt am`ndouă subtipuri ale poligoanelor. În plus, un tip poate avea mai mult decât un extratip. De exemplu un triunghi isoscel dreptunghic poate fi privit fie ca un triunghi isoscel, fie ca unul dreptunghic. Această problemă a multiplelor supertipuri este în mod particular “țepoasă ”, pentru că înseamnă că nu este nici un mod unic de a “ridica” un tip în ierarhie. Găsirea supertipului “corect”, în care să aplicăm un operator la un obiect poate implica o căutare considerabilă prin întreaga rețea de tipuri în partea procedurii cum ar fi operate. Din moment ce în general sunt mai multe subtipuri pentru un tip este problemă similară în constrângerea unei valori în “jos” în ierarhia tip. Lucrând cu numere mari de tipuri interlegate și menținând în același timp modularitatea în proiectarea unor sisteme mai mari este foarte dificil și este o zonă cu o cercetare mai curentă.
5.3 Exemplu: Algebra simbolică
Manipularea expresiilor simbolice algebrice este un proces complex ce ilustrează multe din problemele cele mai grele ce apar în proiectarea unor sisteme pe o scară mai largă. O expresie algebrică, în general, poate fi vizionată ca o structură ierarhică un arbore de operatori aplicat la operanzi. Putem construi expresii algebrice începând cu un set de obiecte primitive, cum ar fi constante și variabile, și combinânu-le pe acestea prin mijloace de operatori generici cum ar fi adunarea și înmulțirea. Ca și în alte limbaje, formăm abstracții ce ne permit sș redefinim la obiectele compuse în termeni simpli. Abstracțiile tipice în algebra simbolică sunt idei cum ar fi combinații liniare, polinomiale, funcții raționale sau trigonometrice. Putem privi acestea ca “tipuri compuse” , care sunt adesea folositoare pentru direcționarea procesă rii expresiilor. De exemplu, am putea descrie expresia:
x2sin(y2+1)+xcos2y+cos(y3-2y2)
ca un polinom în x cu coeficienți funcții trigonometrice de polinom în y ai cărui coeficienți sunt întregi.
Nu vom încerca să dezvoltăm un sistem de manipulare algebrică complet. Astfel de sisteme sunt programe deosebit de complexe, care încadrează cunoștințe algebrice ad`nci și algoritmi eleganți. Ceea ce vom face este să ne uităm la o simplă dar importantă parte a manipulării algebrice:operații aritmetice cu polinoame.
Operații aritmetice asupra polinoamelor
Prima noastră sarcină în proiectarea unui sistem pentru a rezolva operații aritmetice pe polinoame este de a decide ce este un polinom. Polinoamele sunt definite în mod normal în legătură cu anumite variabile(nedeterminatele polinoamelor). Pentru simplicitate, ne vom restrânge la polinoame ce au o singură nedeterminată(polinoame univariate). În mod obișnuit definim un polinom ca fiind o sumă de termeni fiecare dintre ele fiind fie un coeficient, o putere a unei nedeterminate, fie un produs sau a unui coeficient a unei nedeterminate. Un coeficient este definit ca o expresie algebrică, care nu e dependent de nedeterminatea polinomului. De exemplu,
5×2+3x+7
este un simplu polinom în x și
(y2+1)x3+(2y)x+1
este un polinom în x ai cărui coeficienti sunt polinoame în y.Este primul dintre polinoame la fel cu polinomul 5y2+3y+7 ,sau nu? Un răspuns rezonabil ar pute fi “da, dacă considerăm un polinom fiind pur o funcție matematică, dar nu, dacă luăm în considerare un polinom ca fiind o formă sintactică“. Al doilea polinom este echivalent în mod algebric cu un polinom în y, ai cărui coeficienți sunt polinoame în x. Ar putea sistemul nostru să recunoască aceasta sau nu? Mai mult sunt și alte feluri de a reprezenta un polinom, de exemplu, ca un produs de factori, sau(pentru un polinom unuvariat) ca set de rădăcini sau ca o listare a valorilor polinomului la un set specificat de puncte. Putem face aceste chestiuni mai bune decizând dacă în sistemul nostru de manipulare algabrică un polinom va fi o formă sintactică particulară și nu în sensul său matematic subliniat. Acum trebuie să luăm în considerare cum să ne descurcăm la operații aritmetice la polinoame. În acest sistem simplu vom lua în considerare numai înmulțirea și împărțirea. Mai mult, vom insista ca două polinoame ce trebuie adunate să aibă aceeași nedeterminată. Vom aborda proiectarea sistemului nostru urmărind disciplina familiară a abstracției datelor. Vom presupune că un polinom constă dintr-o variabilă și o colecție de termeni și că vom avea selectori variable și term-list ce extrag exact acele părți dintr-un polinom. Toate operațiile aritmetice sunt făcute în termeni de liste; variabila este doar o extensie a tipului de polinom folosit pentru a verifica legitimarea operațiilor polinomiale. Vom presupune că avem un constructor make-polinomial, care construiește un polinom dintr-o variabilă dată și o listă de termeni. Următoarele proceduri sunt puncte de intrare în pachetul de manipulare a datelor:
(define (+poly p1 p2)
(if (same-variable? (variable p1) (variable p2) )
(make-polynomial (variavle p1)
(+terms (term-list p1)
(term-list p2) ) )
(error “Polinoamele nu sunt în aceeași variabilă – +POLY”(list p1 p2))))
(define (*poly p1 p2)
(if (same-variable? (variable p1) (variable p2) )
(make-polynomial (variable p1)
(*terms (term-list p1)
(term-list p2) ) ) 77.2
(error “Polinoamele nu sunt în aceeași variabilă – *POLY”(list p1 p2))))
Putem folosi programarea data-directed pentru a instala aceste noi proceduri în sistemul nostru de operații aritmetice generice:
(put ‘polynomial ‘add +poly)
(put ‘polynomial ‘mul *poly)
Adunarea polinoamelor este făcută în termeni de inteligență. Termenii de același ordin(cu aceeași putere a nedeterminatei) trebuie să fie combinați. Aceasta se face form`nd un nou termen de același ordin al cărui coeficient este suma coeficienților factorilor. Termenii într-un singur factor pentru care nu sunt termeni de același ordin în factorul celălt sunt acumulate simplu la suma polinoamelor care este construită. Pentru a manipula termeni de liste vom presupune că avem un constructor the-empty-termlist ce returnează un termen de listă vidă și un constructor adjoin-term ce alătură un nou termen la termenul listă. Vom presupune de asemenea că avem un predicat empty-termlist? ce ne spune dacă un termen listă dat este vid, un selector first-term ce axtrage termenul de ordin cel mai înalt dintr-un termen listă, și un selector rest-terms care returnează tot în afară de cel mai înalt termen. Dând un termen, vom presupune că avem doi selectori order și coeff, care returnează, respectiv, ordinul și coeficientul termenului. Acești operatori ne permit să considerăm amândoi termeni și lista de termeni ca abstracții de date, a căror reprezentație concretă ne vom ocupa mai târziu.
Iată procedura ce construiește lita de termeni pentru suma a două polinoame:
(define (+tems L1 L2)
(cond ( ( empty-termlist? L1) L2)
( (empty-termlist? L2) L1)
(else
(let ( ( first-term L1) ) (t2 (first-term L2) ) )
(cond ( (> (order t1) (order t2) )
(adjoint-term t1
(+terms (rest-terms L1) L2) ) )
( (< (order t1) (order t2) )
(adjoint term t2
(+terms L1 (rest-terms L2) ) ) )
(else
(adjoin – term (make -term (order t1)
(add (coeff t1)
(coeff t2) ) )
(+terms (rest-terms L1)
(rest-terms L2) ) ) ) ) ) ) ) Cel mai important lucru de notat aici este acela că folosim operatorul generic de adunare add pentru a aduna coeficienții și termenii ce trebuie combinați. Aceasta are consecințe puternice, după cum vom vedea mai jos. Pentru a înmulți două liste de termeni, înmulțim fiecare termen din prima listă cu toți termenii din lista cealaltă folosind în mod repetat procedura *-term-by-all-terms, ce înmulțește un termen dat cu toți termenii dintr-o listă de termeni dată. Polinoamele rezultate sunt acumulate într-o sumă. Înmulțind doi termeni se formează un termen al cărui ordin este suma ordinelor factorilor și al cărui coeficient este produsul coeficienților factorii:
(define (*terms L1 L2)
(if (empty-termlist? L1)
(the-empty-termlist)
(+terms (*-term-by-all-terms (first-term L1) L2)
(*terms (rest-terms L1) L2) ) ) )
(define (*-term-by-all-terms t1 L)
(if (empty-termlist? L)
(the-empty-termlist)
(let ( (t2 (first – term L) ) )
(adjoin-term (make-term (+ (order t1) (order t2) )
(mul (coeff t1) (coeff t2) ) )
(*-term-by-all-terms t1
(rest-terms L) ) ) ) ) )
Aceasta este aproximativ tot ce ste despre adunare și înmulțire polinoamelor. Observăm că din moment ce operăm pe termeni ce folosesc operatorii generici add și mul, pachetul polinomial va fi în mod automat capabil să se descurce cu orice tip de coeficient ce este cunoscut despre pachetul de operații aritmetice generice. Dacă vom include un mecanism de restricțiela cel discutat în 4.2 vom fi capabili în mod automat să ne descurcăm cu operații pe polinoame de tipuri diferite de coeficienți, cum ar fi
3×2+(2+3i)x+7și x4+2/3×2+(5+3i)
Deoarece am instalat operatorii de adunare și înmulțire a polinoamelor *poly și +poly în sistemul de operații aritmetice generice ca fiind operatorii add și mul pentru tipul polinomului sistemului nostru va fi capabil să se descurce cu operații polinomiale cum ar fi:
(y+1)x2+(y2+1)x+(y-1) și (y-2)x+(y3+7)
Motivul este că atunci c`nd sistemul încearcă să combine coeficienții va executa prin add și mul. Din moment ce coeficienții sunt ei însuși polinoame(în y), va fi combinat folosind +poly și *poly. Rezultatul este un fel de “recursie data-directed” în care , de exemplu, o chemăm la procedura *poly va rezulta în chemări recursie la procedura *poly pentru a înmulți coeficienții. Dacă coeficienții lor sunt ei înși și polinoame, direcționarea datelor ne va asigura că sistemul va urmării prin alt nivel de chemări recursive ș.a.m.d prin mai multe nivele după cum dictează structura de date.
Reprezentarea listelor term
În final trebuie să ne confruntăm serviciul de a implementa o bună reprezentare pentru liste de termeni. O listă de termeni este de fapt, un set de coeficienți făcuți cheie de către ordinul termenului. Totuși , oricare dintre meodele de reprezentare a setului cum am discutat în secțiunea 2.2.5. poate fi aplicată acestei sarcini. Pe de altă parte procedurile noastre +terms și *terms , va accesa totdeauna listele de termeni în mod secvențial de la ordinul superior la ordinul inferior. Astfel vom folosi un anumit fel de reprezentare ordonată. Cum am putea să structurăm lista ce reprezintă o listă de termeni? O considerație este “densitatea” polinoamelor pe care vrem să le manipulăm. Un polinom este dens dacă are coeficienți ce nu sunt în termenii majorității ordinelor. Dacă are mai mulți termeni 0 se spune că este rar. De exemplu,
A: x5+2×4+3×2-2x-5
este un polinom dens, în timp ce
B: x100+2×2+1
este unul rar.
Listele de termeni de polinoame dense sunt reprezentate cel mai eficient ca liste de coeficienți. De exemplu, polinomul A de sus ar fi reprezentat ca (1 2 0 3 -2 -5). Ordinul termenului în această reprezentare este lungimea sublistei ce începe cu coeficientul acelui termen decrementat cu 1. Aceasta ar fi o reprezentare teribilă pentru un polinom rar, cum este B. Ar fi o listă uriașă de zero întreruptă de câțiva termeni singuratici care nu sunt zero. Oreprezentare mai rezonabilă a unei liste de termeni a unui polinom rar este ca o listă de termeni care nu sunt 0. Fiecare termen este o listă ce conține ordinul termenului și coeficientul pentru acel ordin. Într-o astfel de schemă, polinomul B este în mod eficient reprezentat ca fiind ( (100 1) (2 2) (0 1)). După cum majoritatea operațiilor asupra polinoamelor sunt făcute pe polinoame rare vom folosi această metodă. Vom presupune că listele term aranjate de la termenii de ordin superior până la cel de ordin inferior. Din moment ce am făcut această decizie, implementarea selectorilor și constructorilor pentru termeni și listele term este directă:
(define (adjoin-term term term-list)
(if (=zero? (coeff term) )
term-list
(cons term term-list) ) )
(define (the-empty-termlist) '( ) )
(define (first-term term-list) (car term-list) )
(define (rest-terms term-list) (cdr term-list) )
(define (empty-termlist? term-list) (null? term-list) )
(define (make-term order coeff) (list order coeff) )
(define (order term) (car term) )
(define (coeff term) (cadr term) )
Acum numai c`teva proceduri răm`n a fi definite:
(define (make-polynomial variable term-list)
(atttach-type ' polynomial (cons variable term-list) ) )
(define (variable p) (car p) )
(define (term-list p) (cdr p) )
Ierarhii de tipuri în algebra simbolică
Sistemul nostru polinomial ilustrează cum obiectele de un anumit tip(polinoamele) pot fi de fapt obiecte complexe ce au obiectele de mai multe tipuri diferite ca părți. Aceasta nu posedă o mare dificultate în definirea operatorilor generici. Avem nevoie să instalăm operatori generici potriviți pentru efectuarea necesară manipulării părților tipurilor compuse. De fapt am văzut că polinomul formează un fel de “abstracție a datelor recursive” în care părți ale polinomului pot fi ele însele polinoame. Operatorii noștri generici și stilul de programare al datelor direcționate se poate descurca cu această complicație fără prea multă bătaie de cap. Pe de altă parte algebra polinomială este un sistem în care tipurile de date nu pot fi în mod natural aranjate sub formă de turn. De exemplu este posibil să avem polinoame în x al căror coeficient sunt polinoame în y. Este de asemenea posibil să avem polinoame în y ai căror coeficienți să fie polinoame în x. Nici unul dintre aceste tipuri nu este “mai presus” decât celălalt într-un mod natural, totuși este adesea necesar să adunăm împreună elemente din aceeași mulțime. Sunt mai multe feluri de a face aceasta: o posibilitate este de a converti un polinom la tipul celuilalt mărind și rearanjând termenii astfel încât amândouă polinoame să aibă aceeași variabilă principală. O altă posibilitate pote să impună o structură de turn, ordonând variabilele și totuși întotdeauna să convertească un polinom la o “formă canonică” cu variabila dominantă de cea mai înaltă prioritate și variabilă de cea mai joasă prioritate îngropată în coeficienți. Această strategie lucrează chiar bine except`nd faptul că această conversie poate lărgi în mod inutil un polinom, făcându-l greu de citit și poate mai puțin eficient de a lucra cu el. Strategia turnului nu este cu siguranță naturală pentru acest domeniu sau pentru orice alt domeniu unde utilizatorul poate inventa tipuri noi folosind în mod dinamic tipuri diferite în forme de combinare diferite cum ar fi funcțiile trigonometrice, serii de puteri și integrale. Nu trebuie să fie surprinzător că această restricțiede controlare este o problemă serioasă de proiectare pe scară largă a sistemului de manipulare algebrică. O mare parte din complexitatea unor astfel de sisteme privește relațiile dintre diferite tipuri. Într-adevăr este drept să spunem că nu am înțeles în mod concret constrângerea. De fapt nu am înțeles încă în mod complet conceptul de tip de date. Totuși ceea ce știm ne dă principii puternice de structurare și modularitate pentru a susține proiectarea unor sisteme mari.
Exercițiu extins: Funcții raționale
Putem extinde sistemul generic aritmetic pentru a include funcții raționale. Acestea sunt “fracții” al căror numitor și numărător sun polinoame ca:
Sistemul ar trebui să fie capabil să adune, să scadă, să înmulțească și să împartă funcțiile raționale și să execute calcule cum ar fi
Dacă modificăm pachetul aritmetic rațional astfel încât să folosească operatori generici, atunci vom face ce vom vrea except`nd reducerea fracțiilor la termenii cei mai mici. Putem reduce fracțiile polinomiale la termenii cei mai mici, folosind aceeași idee pe care am folosit-o cu întregii: modificând procedura make-rat astfel încât să împartă și numitorul și numărătorul la cel mai mare divizor comun al lor. Noțiunea de “cel mai mare divizor comun” are sens pentru polinoame. De fapt putem calcula cel mai mare divizor comun a două polinoame, folosind în mod esențial același algoritm al lui Euclid ce lucrează și la întregi este
(define (gcd a b)
(if ( =b 0)
a
(gcd b (remainder a b ) ) ) )
Folosind aceasta am putea face modificarea evidentă pentru a defini operatorul cel mai mare divizor comun ce lucrează pe liste de termeni:
(define (gcd-terms a b)
(if (empty-termlist? b)
a
(gcd-terms b (remainder-terms a b) ) ) )
unde remainder-terms alege componentul ce rămâne din listă returnat de operația de împărțire term-list sau terms care au fost implementate în exercițiu. Putem rezolva problema arătată în exercițiu dacă folosim următoarea modificare a algoritmului de cel mai mare divizor comun. Înaite de efectuarea oricărei împărțiri polinomiale în calculul celui mai mare divizor comun, înmulțim deâmpărțitul cu un factor întreg constant, ales pentru a garanta faptul că nu va apărea nici o fracție în timpul procesului de împărțire. Răspunsul nostru va fi astfel diferit de actualul cel mai mare divizor comun, printr-o constantă întreagă, dar aceasta nu contează în cazul reducerii funcțiilor raționale la cei mai mici termeni; cel mai mare divizor comun va fi folosit să împartă amândoi și numărătorul și numitorul, astfel că constanta întreagă se va anula. Mai precis, dacă P și Q sunt polinoame, atunci O1 să fie ordinul lui P și O2 să fie ordinul lui Q. Luăm pe c ca fiind coeficientul lui Q. Atunci poate fi arătat că dacă inmulțim pe P cu factorul de întregire c1+O1-O2 polinomul rezultat poate fi împărțit la Q folosind algoritmul /terms fără să introducem vreo fracție. Operația de înmulțire a deîmpărțitului cu această constantă și apoi să-l împărțim m este adesea pseudoîmpărțirea lui P la Q. Restul împărțirii este numit pseudorest. Astfel, iată cum să reducem o funcție rațională la cel mai mic termen:
Calculăm cel mai mare divizor comun al numărătorului și numitorului urmărind algoritmul lui Euclid, dar vom folosi mai degrabă pseudo-remainder dec`t remainder.
C`nd obținem cel mai mare divizor comun înmulțim și numitorul și numărătorul folosind același factor de întregire înainte de a împărți pri cel mai mare divizor comun astfel înc`t împărțirea la cel mai mare divizor comun să nu introducă nici un coeficient ne întreg. Cum factorul pe care îl folosim la coeficienți de conducere al celui mai mare divizor comun a crescut la puterea 1+O1-O2, unde O2 este ordinul celui mai mare divizor comun și O1 este maximul ordinelor numărătorilor și numitorilor. Aceasta va asigura că împărțind numitorul și numărătorul la cel mai mare divizor comun nu va introduce nici o fracție.
Rezultatul acestei operații va fi o funcție rațională cu coeficienți întregi. Coeficienții vor fi în mod normal foarte mari deoarece dintre toți factori întregi ultimul pas este de a îndepărta factorii inutili prin calcularea celui mai mare divizor comun(întreg) a tuturor coeficienților numărătorului și numitorului și împărțirea prin acest factor.
Calcularea celui mai mare divizor comun este în mijlocul oricărui sistem ce face operații pe funcții raționale.Algoritmul folosit mai sus, deși în mod matematic direct, este extre de lent.Încetineala este datorată în parte numărului mare de operații de împărțire și în parte mărimii enorme coeficienților intermediați generați de pseudoîmpărțiri. Una dintre zonele active în dezvoltarea sistemului de manipulare algebrică este proiectarea unor algoritmi mai buni pentru calcularea celui mai mare divizor comun al polinoamelor.
CAPITOLU VI
APLICA|II
#n acest capitol se prezint[ aplica\ii referitoare la arborii binari. Pentru a realiza aceste programe se folose]te limbajul Turbo Pascal.
Pentru a @n\elege modul de concepere al programelor se prezint[ c`teva informa\ii referitoare la ele.
Primul program genereaz[ un arbore binar pornind de la lista caracterelor asociate v`rfurilor la traversarea arborelui @n preordine, inordine ]i postordine; subarborii vizita\i sunt marca\i la intrare prin caracterul ´ . ´ . Cele trei modalit[\i de traversare au fost definite recursiv, astfel @nc`t procedurile care transcriu aceste opera\ii au fost ]i ele construite recursiv. Aceast[ traversare a arborelui presupune vizitarea fiec[rui nod o singur[ dat[, opera\ie identic[ cu o liniarizare a arborilor.
Cea de a doua aplica\ie realizeaz[ opera\iile de caracterizare a unui arbore binar (inserare, ]tergere, c[utare ). #n aceast[ aplica\ie se folosesc urm[toarele comenzi de forma :
I=intrarea unui stoc de obiecte de un anumit tip;
E=ie]irea unui singur obiect de un anumit tip;
L=afi]area tuturor obiectelor ]i a stocurilor existente;
S=oprirea programului.
program operatii_in_arborele_binar_de_cautare;
type reper=^nod;
nod=record
nume:string;
cant:byte;
stg,dr:reper
end;
var rad:reper;
comanda:char;nume_ob:string;numar_ob:byte;
procedure listare_inordine(p:reper);
begin
if p<>nil then
begin listare_inordine(p^.stg);
writeln(p^.nume,' ',p^.cant);
listare_inordine(p^.dr)
end
end;
procedure cautare_inserare(var p:reper);
begin
if p=nil { obiect nou }
then
begin new(p);
with p^do
begin nume:=nume_ob;
cant:=numar_ob;
stg:=nil;
dr:=nil
end
end
else
if nume_ob=p^.nume { obiectul exista }
then p^.cant:=p^.cant+numar_ob
else
if nume_ob<p^.nume { obiectul se cauta}
then cautare_inserare(p^.stg)
else cautare_inserare(p^.dr)
end;
procedure cautare(var p:reper);
var q:reper;
procedure cautare_stergere(var r:reper);
begin
if r^.dr=nil { r^=nodul cel mai din dreapta al }
then { subarborelui sting al lui p^ }
begin
q^.nume:=r^.nume; { mutarea informatiilor din r^ in q^ }
q^.cant:=r^.cant; { q^=p^ }
q:=r;
r:=r^.stg; { fiul sting al lui r^ se leaga in }
end { dreapta tatalui lui r^ }
else cautare_stergere(r^.dr) { se cauta numai spre dreapta}
end; { sfirsit Cautare-Stergere }
begin
if p=nil
then writeln('obiectul ',nume_ob,' nu exista')
else
if nume_ob=p^.nume { obiectul s-a gasit }
then
if p^.cant>1
then p^.cant:=p^.cant-1
else
begin
q:=p; { p^ identic cu q^ }
if q^.stg=nil { q^ nu are fiu sting }
then p:=q^.dr { fiul drept al lui p^ se leaga }
else { de tatal lui p^ }
if q^.dr=nil { q^ nu are fiu drept }
then p:=q^.stg { fiul sting al lui p^ se leaga }
{ de tatal lui p^}
else
cautare_stergere(q^.stg); { q^ are doi succesori }
{ cauta in subarborele sting }
{ cel mai din dreapta nod }
dispose(q)
end
else
if nume_ob<p^.nume { obiectul se cauta }
then cautare(p^.stg) { in subarborele sting }
else cautare(p^.dr) { in subarborele drept }
end;
begin
rad:=nil;
repeat
write('comanda:');
readln(comanda);
case comanda of
'i':begin
write('obiectul:');
readln(nume_ob);
write('cantitatea intrata:');
readln(numar_ob);
cautare_inserare(rad)
end;
'e':begin
write('obiectul care iese:');
readln(nume_ob);
cautare(rad)
end;
'l','s':listare_inordine(rad)
end
until comanda='s'
end.
program generarea_unui_arbore_binar_si_traversarea_lui;
type reper=^nod_arbore;
nod_arbore=record
inf:char;
stg,dr:reper
end;
var radacina:reper; {adresa radacinii arborelui}
caracter:char;
procedure generare_arbore(var p:reper);
{parametrul p se transmite prin adresa pentru a initializa}
{parametrul actual de apel cu valoarea pe care o primeste p}
begin
read(caracter);
if caracter<>'.' {se aloca memorie pentru un nod}
then begin
new(p);
p^.inf:=caracter;
generare_arbore(p^.stg); {gen.subarbore sting}
generare_arbore(p^.dr) {gen.subarbore drept}
end
else p:=nil {subarbore vid}
end;
procedure preordine(p:reper);
{p=parametru de tip valoare}
begin
if p<>nil then
begin
write(p^.inf); {se scrie informatia asociata nodului}
preordine(p^.stg); {se scriu inf subarborelui sting}
preordine(p^.dr) {se scriu inf subarborelui drept}
end
end;
procedure inordine(p:reper); {p=parametru de tip valoare}
begin
if p<>nil then
begin
inordine(p^.stg); {se scriu inf subarborelui sting}
write(p^.inf); {se scriu informatia asociata nodului}
inordine(p^.dr) {se scriu inf subarborelui drept}
end
end;
procedure postordine(p:reper); {p=parametru de tip valoare}
begin
if p<>nil then
begin
postordine(p^.stg); {se scriu inf subarborelui sting}
postordine(p^.dr); {se scriu inf subarborelui drept}
write(p^.inf) {se scriu informatia asociata nodului}
end
end;
begin
writeln('inf asoc nodurilor arborelui parcurs in preordine:');
generare_arbore(radacina);
writeln;writeln('arborele parcurs in preordine:');
preordine(radacina);
writeln;writeln('arborele parcurs inordine:');
inordine(radacina);
writeln;writeln('arborele parcurs in postordine:');
postordine(radacina);
writeln
end.
=== biblio ===
BIBLIOGRAFIE
[1] HARCLD ABELSON, GERALD JAY SUSSMAN, JULIE SUSSMAN
Structure and interpretation of computer programs
Seveateenth Printing,1995
[2] KNUTH D. E.
Tratat in programarea calculatoarelor, vol II
Ed.Tehnica, 1973
[3] DOINA RANCEA
Limbajul Turbo Pascal, vol II
Ed. Libris, Cluj, 1993
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Structuri Si Interpretari DE Programe (ID: 148836)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.