Primul contact cu Logo l-am avut prin intermediul fiicei mele, pe vremea aceea elevă în clasele primare. La orele de informatică, făceau tot felul de desene cu ajutorul unor comenzi asemănătoare celor prin care se comandă un plotter. Ştiam câte ceva despre Logo, dar până atunci n-am avut curiozitatea să-l cunosc mai îndeaproape. Dar, cum datoria de părinte m-a obligat... Surpriza a fost că, dincolo de "grafica ţestoasei", Logo este un limbaj de programare cât se poate de serios, care se pretează excelent la o mulţime de aplicaţii, de la lingvistică şi până la robotică.
Puţină istorie
Totul a pornit de la studiile unui psiholog elveţian, pe nume Jean Piaget, privind mecanismele învăţării la copii. Rezultatele sale s-au constituit într-o nouă teorie a educaţiei, numită constructivism, teorie care a revoluţionat ştiinţa pedagogică. Pe scurt, constructivismul consideră cunoaşterea ca fiind produsul creaţiei intelectuale a celui care învaţă, rezultând din interacţiunea acestuia cu oamenii şi mediul înconjurător. Pare foarte natural, dar adesea practica pedagogică neglijează încă acest adevăr simplu: învăţarea este un act de creaţie, nu de memorare. Transpunerea în practica a teoriei lui Piaget avea deci nevoie de instrumente specifice.
Pe la mijlocul anilor '60, un matematician care lucrase cu Piaget ajunge în Statele Unite. Şi nu oriunde, ci tocmai la MIT (Massachusetts Institute of Technology). Numele sau: Seymour Papert. La MIT, Papert înfiinţează, împreună cu Marvin Minsky, Laboratorul de Inteligenţă Artificială, care devine curând incubatorul unor realizări excepţionale. Aici, împreuna cu o echipa de specialişti, Papert realizează în 1967 prima versiune de Logo, un limbaj de programare care îşi propune să fie un instrument didactic în sensul teoriei lui Piaget, un instrument care să stimuleze tocmai acea creaţie intelectuala care stă la baza învăţării.
Dat fiind faptul că provine din mediile ştiinţifice legate de inteligenţa artificială, nu este o surpriză că Logo se bazează pe un limbaj de programare clasic în acest domeniu: Lisp (programatorii profesionişti încă îl consideră un dialect al acestuia). De la Lisp a moştenit Logo flexibilitatea şi puterea calculului simbolic, care l-au recomandat pentru numeroase proiecte avansate în matematică, lingvistică, robotică, muzică şi alte domenii. Spre deosebire însă de Lisp, Logo a fost gândit ca un "instrument pentru învăţare", deci trebuia să fie în primul rând accesibil neofiţilor (chiar şi copiilor), să fie expresiv şi, mai ales, simplu.
Restul e istorie. La sfârşitul anilor '70 apar calculatoarele personale şi primele implementări Logo pentru acestea (mai întâi Apple II şi Texas Instruments TI 99/4). Răspândirea PC-urilor în deceniul următor va aduce cu sine utilizarea limbajului pe scară largă în multe şcoli din întreaga lume. Cartea lui Brian Harvey, "Computer Science Logo Style" (MIT Press, 1985, 1997), în trei volume, recomandă Logo ca un limbaj "serios" pentru învăţarea ştiinţei calculatoarelor la nivel academic.
Înainte de a începe
Rostul acestui articol este doar de a furniza un quick start programatorilor deja experimentaţi, în absenţa unor cărţi pretenţioase sau a unor tutoriale. În consecinţă, expunerea ce urmează nu se pretinde nici riguroasă şi nici exhaustivă.
Nu există un standard al limbajului Logo, dar există numeroase implementări. În cele ce urmează, voi folosi dialectul Berkeley Logo, unul dintre cele mai răspândite în medii Unix, Macintosh şi DOS. Versiunea cea mai utilizată sub Windows, MSWLogo, utilizează nucleul Berkeley Logo, aşa că toate exemplele din articol rulează fără nici o modificare.
Cunoştinţele de Lisp sunt utile pentru Logo, dar nu sunt obligatorii. Am evitat comparaţii cu alte limbaje, dar uneori referinţele la Tcl sau Python pot fi utile.
Elementele primordiale
Logo este un limbaj destinat interpretării care, într-o primă fază, poate fi folosit în regim conversaţional. Promter-ul implicit este de obicei ? (semnul întrebării), care invită utilizatorul să introducă comenzi, pe care mediul încearcă să le interpreteze. De exemplu:
? print "Hello!
Hello!
În principiu, elementele sintactice din Logo se împart în proceduri şi date.
Procedurile sunt de două feluri:
Funcţii - cele care returnează o valoare:
Comenzi - cele care nu returnează valori, dar execută diverse acţiuni.
Cele mai multe proceduri acceptă argumente, care pot fi date furnizate ca atare sau produse de alte proceduri (în speţă funcţii). De exemplu:
? print first "Hello!
H
Interpretarea se petrece în două faze:
Evaluarea unei proceduri se face doar după ce au fost evaluate toate argumentele sale. Se poate spune că evaluarea este iniţiată de la stânga spre dreapta, dar se realizează efectiv de la dreapta spre stânga.
Structuri de date
Logo lucrează cu trei tipuri de date fundamentale: cuvinte, liste şi tablouri.
Un cuvânt este un fel de şir de caractere. Pentru a nu fi evaluate (Logo încearcă să evalueze tot ce-i stă în cale), cuvintele sunt prefixate cu caracterul ghilimele ("). Pentru a introduce într-un cuvânt caractere "mai speciale", cum ar fi cele considerate de Logo ca fiind delimitatori (spaţiu, paranteze, operatori infix etc.), acestea sunt precedate de caracterul backslash ("\"). De exemplu:
? print "Hello,\ world!\n\(test\)
Hello, world!
(test)
Un aspect extrem de interesant este legat de numere. Numerele sunt simple cuvinte, pe care însă interpretorul le recunoaşte, astfel încât nu este obligatoriu să fie prefixate cu ghilimele. Totuşi, prefixarea este importantă în anumite situaţii, deoarece inhibă evaluarea:
? print 17 + word "3. 145
20.145
? print 17 + word 3. 145
3162
În primul caz, funcţia word (care formează un cuvânt prin concatenarea argumentelor) a primit ca prim argument cuvântul "3.", pe când în al doilea caz a primit ca prim argument cuvântul "3", rezultat din evaluarea numărului "3.".
Cert este însă că toate procedurile care lucrează cu cuvinte lucrează şi cu numere. Desigur, invers nu este valabil: funcţiile aritmetice nu acceptă decât numere.
O listă este o structură care cuprinde mai multe elemente, care pot fi cuvinte, tablouri sau alte liste. Listele se încadrează între paranteze drepte. Un caz particular de listă este lista vidă, notată "[]". În mod normal, listele nu se evaluează:
? print [Hello, world!]
Hello, world!
Există însă mai multe posibilităţi de a "evalua" o listă:
? run [print [Hello, world!]]
Hello, world!
În fine, tablourile se aseamănă cu listele, diferenţa fiind că au un număr fix de elemente. Elementele pot fi cuvinte, liste sau alte tablouri. Tablourile se scriu între acolade şi nu se evaluează:
? print {alfa beta [a b c] {1 2 etc}}
{alfa beta [a b c] {1 2 etc}}
Deoarece tablourile pot cuprinde alte tablouri, este evident că se pot construi cu uşurinţă tablouri multidimensionale.
Variabile
În Logo variabilele nu sunt tipizate şi, în principiu, nu reprezintă altceva decât o cale de a referi printr-un cuvânt o structură de date:
? make "nume "valoare
În urma comenzii de mai sus, a fost creată variabila nume care, în acest caz, desemnează cuvântul "valoare". Structura de date desemnată de o variabilă poate fi obţinută prin funcţia thing sau prin prefixarea numelui variabilei cu caracterul ":" (care de fapt este înlocuită de interpretor cu secvenţa thing "):
? print thing "nume
valoare
? print :nume
valoare
Altfel spus, variabilele reprezintă o cale de indirectare către o valoare. Un aspect interesant este faptul că această indirectare poate fi multiplă:
? make "nume "valoare
? make "valoare [Hello, world!]
? print thing thing nume
Hello, world!
? print thing :nume
Hello, world!
De remarcat că deşi notaţia :nume este mai comodă, pentru indirectări multiple se impune folosirea funcţiei thing.
Proprietăţi
O structură ceva mai specială în Logo o constituie listele de proprietăţi. Pentru cei familiarizaţi cu limbajul Lisp, noţiunea e simplă, dar pentru muritorii de rând voi preciza că aceste liste de proprietăţi sunt asemănătoare "dicţionarelor" din Smalltalk sau Python sau "tablourilor asociative" din alte limbaje. În principiu, o listă de proprietăţi are un nume şi se compune dintr-o mulţime de perechi formate dintr-un cuvânt care desemnează un nume de proprietate şi o valoare corespunzătoare. Asemănarea cu dicţionarele constă din faptul că numele proprietăţii este de fapt cheia de acces la valoarea proprietăţii (numele proprietăţilor pot fi şi numere):
? pprop "prop "wprop "valoare
? pprop "prop "lprop [Hello, world!]
În felul acesta am creat lista de proprietăţi prop, în care am specificat două proprietăţi (wprop şi lprop) cu valorile corespunzătoare. Valorile pot fi extrase pe baza numelor proprietăţilor:
? print gprop "prop "wprop
valoare
Există şi posibilitatea de a obţine o listă formată din numele proprietăţilor urmate (pe poziţiile pare) de valorile corespunzătoare:
? show plist "prop
[lprop [Hello, world!] wprop valoare]
Observaţie: spre deosebire de print, comanda show afişează lista, nu doar conţinutul ei.
Principala calitate a listelor de proprietăţi o reprezintă libertatea de a memora orice fel de informaţii. Pentru a păstra neîngrădită această libertate, tentativa de a extrage o proprietate care nu există nu este considerată o eroare, ci va produce ca rezultat lista vidă. De remarcat că nu există posibilitatea de a discerne dacă lista vidă este valoarea corespunzătoare unei proprietăţi existente sau este generată datorită absenţei proprietăţii cerute.
O deosebire importantă faţă de dicţionarele (din Python, de exemplu): listele de proprietăţi nu sunt considerate variabile. Aceasta înseamnă că în acelaşi spaţiu de lucru (workspace) pot avea variabile şi liste de valori purtând acelaşi nume.
Proceduri
Tot ceea ce interpretorul întâlneşte în afara structurilor de date se consideră nume de procedură şi se încearcă evaluarea:
? print Hello
I don't know how to Hello
În afară de clasificarea în funcţii şi comenzi, procedurile mai pot fi clasificate în primitive (care, pentru performanţă, sunt "zidite" în interpretor), proceduri de bibliotecă (care sunt scrise în Logo şi sunt încărcate automat) şi proceduri utilizator (scrise în Logo, dar încărcate doar la comandă). De remarcat că, în afară de încărcarea implicită, nu există nici o diferenţă între funcţiile de bibliotecă şi funcţiile utilizator.
O procedură poate avea ca nume orice cuvânt valid, cu singura condiţie ca numele să nu coincidă cu numele altei proceduri din spaţiul de lucru. Numele poate însă să coincidă cu numele unei variabile sau a unei liste de proprietăţi.
Unele primitive dispun implicit de un nume alternativ, mai scurt, care poate fi utilizat mai eficient în regim conversaţional. De pildă pr pentru print, bf pentru butfirst etc. Pe de altă parte, orice nume de procedură poate fi "tradus" cu ajutorul comenzii 'copydef':
? copydef "scrie "print
? scrie "Salut!
Salut!
Deşi în mod implicit toate procedurile admit un număr fix de argumente (de obicei minimal), unele dispun şi de o "formă multiplă" prin care acceptă oricâte argumente. Sintactic formele multiple se scriu prin încadrarea între paranteze rotunde a numelui procedurii împreună cu argumentele:
? (pr "Hello, (word "w "orld "!))
Hello, world!
Trebuie menţionat şi faptul că există proceduri care acceptă şi o formă infix. Este cazul operaţiilor aritmetice (sum, difference, product, quotient) şi a comparaţiilor.
În fine, se cuvine menţionat faptul că primitivele şi procedurile de bibliotecă sunt oarecum polimorfe, încercând să trateze uniform diferite structuri de date. De exemplu, funcţia list - care formează o listă din argumentele primite - admite ca argumente cuvinte, liste sau tablouri. Funcţia first returnează primul element când este aplicată asupra listelor şi tablourilor şi primul caracter când se aplica asupra unui cuvânt.
Predicate
O categorie oarecum specială de funcţii sunt cele care returnează o valoare de adevăr (true sau false). De obicei numele acestor funcţii are terminaţia "p":
? print wordp "cuvint
true
Valorile de adevăr pot fi combinate cu ajutorul operaţiilor logice not, and şi or. Aceste operaţii returnează, desigur, doar valori de adevăr, deci pot fi considerate tot predicate (cu observaţia că nu se termină în "p").
Mai trebuie amintit în acest context că predicatele lessp, greaterp şi equalp admit şi formele infix "<", ">" şi "=" (deşi pentru equalp documentaţia nu precizează acest lucru). Primele două nu admit decât argumente numerice, în timp ce equalp este aplicabil oricăror structuri de date.
Un caz mai special este predicatul .eq (o altă excepţie de la regula terminaţiei în "p"). În primul rând, se remarcă faptul că numele predicatului este prefixat cu caracterul "." (punct), ceea ce în Logo este o convenţie pentru a desemna procedurile "periculoase", nerecomandate începătorilor. Spre deosebire de equalp, predicatul .eq va returna true doar în situaţia în care cele două argumente ale sale sunt, de fapt, unul şi acelaşi obiect. Acest lucru este uneori important, deoarece un modificator aplicat asupra unuia dintre obiecte îl va afecta şi pe celălalt:
? make "alfa [a b c]
? make "beta :alfa
? pr .eq :alfa :beta
true
? make "gama [a b c]
? pr .eq :alfa :gama
false
? .setfirst :alfa "primul
? show :beta
[primul b c]
Procedura .setfirst schimbă primul element al listei furnizate ca prim argument cu un nou element, pe care-l primeşte ca al doilea argument. Acţiunea ei este asemănătoare cu cea a comenzii:
? make :alfa fput "primul butfirst :alfa
Diferenţa este că funcţia fput (ca dealtfel majoritatea procedurilor din Logo) lucrează cu o copie a listei, deci valoarea variabilei beta nu ar fi afectată. Funcţia .setfirst este considerată periculoasă deoarece nu verifică circularitatea listei asupra căreia este aplicată. De exemplu, secvenţa următoare conduce la blocarea interpretorului Logo:
? make "alfa [a b c]
? .setfirst :alfa :alfa
? print :alfa
O ultimă precizare legată de predicate: valorile true şi false nu au nimic special. Sunt simple cuvinte:
? print first "alfa = "alfa
t
Proceduri utilizator
Desigur, pentru a-şi merita numele de "limbaj de programare", Logo trebuie să permită utilizatorului să dezvolte programe. În acest scop, Logo dispune de o construcţie specială cu ajutorul căreia se pot defini proceduri, care pot fi comenzi sau funcţii. Modul în care se editează un program depinde de la un interpretor la altul, de obicei la comanda edit fiind furnizat un editor de text. Iată un exemplu de definiţie de procedură:
to salut
print [Hello, world!]
end
Comanda to pregăteşte interpretorul Logo să primească definiţia unei proceduri, al cărei nume (şi, eventual, argumente) îi sunt furnizate ca parametri. De remarcat faptul că to este o "formă specială", deoarece argumentele sale nu sunt evaluate (altfel al fi trebuit să scriem to "salut). Liniile următoare vor conţine "corpul" procedurii, format din apeluri de proceduri Logo, urmat de linia end, care încheie definiţia. Odată ce această procedură este "înregistrată" în spaţiul de lucru, ea poate fi folosită în mod interactiv:
? salut
Hello, world!
O procedură poate să aibă argumente. Cazul cel mai simplu este cel în care numărul de argumente este fix. Să considerăm deci următoarea definiţie:
to inc :numar
output :numar + 1
end
Parametrul formal se precizează imediat după numele procedurii şi, prin convenţie, este prefixat cu caracterul ":", ceea ce sugerează faptul că acesta este o variabilă. Ceea ce este special în cazul parametrilor formali este faptul că ei sunt variabile locale, vizibilitatea lor fiind limitată la domeniul procedurii.
Comanda output (forma scurtă: op) este cea care opreşte execuţia procedurii şi returnează valoarea pe care o primeşte ca argument. O comandă înrudită este stop, care însă nu returnează nici o valoare. Este evident că procedurile încheiate prin output sunt funcţii iar cele încheiate prin stop sunt comenzi.
Este clar acum că funcţia inc nu face altceva decât să incrementeze cu o unitate argumentul. O extensie posibilă ar fi să putem furniza funcţiei inc încă un argument, opţional, prin care să specificăm "pasul" incrementării. În lipsa acestuia, se incrementează cu o unitate:
to inc :numar [:pas 1]
output :numar + :pas
end
Iată şi modalităţile de folosire:
? print inc 12
13
? print (inc 12 3)
15
Valoarea implicită a argumentului opţional se specifică, la modul general, printr-o expresie. Această expresie (în cazul nostru este o simplă constantă: 1) se evaluează la momentul apelului şi poate cuprinde şi valorile parametrilor formali care figurează în stânga ei.
În fine, există şi posibilitatea de a furniza unei proceduri un număr neprecizat de parametri. Acest lucru se precizează plasând după parametrii obligatorii şi cei opţionali (dacă există) un parametru formal încadrat de paranteze drepte:
to max :in1 [:in2 difference :in1 1] [:rest]
; corpul procedurii
end
Parametrul formal va fi o listă care la apel va culege toate intrările furnizate după cele obligatorii şi cele opţionale. În cazul de mai sus, procedura poate fi apelată cu un parametru (caz în care al doilea, :in2, va fi calculat pe baza expresiei), cu doi parametri (caz în care :in2 va primi valoarea celui de-al doilea argument furnizat) sau cu mai mulţi parametri, caz în care următorii parametri vor fi culeşi în lista :rest. De exemplu, pentru apelul:
? pr (max 4 2 7 3 1)
vom avea :in1 = 4, :in2 = 2 şi :rest = [7 3 1].
O observaţie: parametrii opţionali sunt uneori folosiţi pentru a introduce şi iniţializa o variabilă locală, evitând astfel declaraţia prin comanda local şi iniţializarea prin make. Aceste variabile pot fi adesea utile în cazul unor proceduri recursive. Riscul este ca utilizatorul să apeleze procedura cu argumentul opţional, ceea ce conduce la o iniţializare greşită.
Programare
Logo nu are instrucţiuni propriu-zise, ci doar apeluri de procedură. Există însă proceduri care permit ramificarea şi iteraţia, ceea ce permite programarea unor proceduri oricât de complexe. Mai mult, există posibilitatea de a inventa noi structuri de control.
Comanda if acceptă două argumente, al doilea fiind obligatoriu o listă cu "instrucţiuni" (de fapt apeluri de proceduri). Dacă primul argument este true, atunci se execută instrucţiunile din lista primită ca al doilea argument. Dacă primul argument este false nu se întâmplă nimic. Este o eroare ca primul argument sa nu fie nici true şi nici false. Comanda ifelse acceptă trei argumente şi este clar care este rolul celui de-al treilea.
Ca prim exemplu, voi implementa funcţia max pe care am invocat-o în secţiunea precedentă, cu diferenţa că voi pretinde doi parametri obligatorii (cum este normal pentru o funcţie care determină maximul):
to max :in1 :in2 [:rest]
local "lmax ; variabilă locală
ifelse :in1 > :in2 ~
[make "lmax :in1] ~
[make "lmax :in2]
if emptyp :rest [op :lmax]
op (max :lmax first :rest bf :rest)
end
In privinţa declaraţiei, lucrurile sunt clare. Comanda local creează o variabilă care este locală funcţiei. În privinţa funcţiei ifelse e necesară o precizare: caracterul "~" are rolul de a "rupe" liniile. Se observă că funcţia este recursivă, apelul final implicând maximul dintre primele două argumente, primul argument din lista :rest şi apoi celelalte argumente rămase.
Iată însă ce se întâmplă dacă apelăm funcţia:
pr (max 8 2 7 9 2)
> doesn't like [9 2] as input in max
[ifelse :in1 > :in2 [make "lmax :in1] [make "lmax :in2]]
Nu este tocmai ce-am aşteptat... Greşeala este în ultima linie: funcţia bf produce o listă, pe când în apelul funcţiei max nu trebuie să avem decât numere.
Pentru a evita această problemă, putem să "compunem" cu ajutorul primitivei sentence (pe scurt se) o listă care să cuprindă forma corectă de apel, după care vom forţa "evaluarea" acestei liste cu procedura run. Precizare: funcţia se formează o listă din argumentele sale. Dacă un argument este listă, atunci în lista rezultată sunt incluse doar elementele listei:
to max :in1 :in2 [:rest]
local "lmax
ifelse :in2 > :in1 ~
[make "lmax :in2] ~
[make "lmax :in1]
if emptyp :rest [op :lmax]
run (se "op "\(max ":lmax first :rest ~
bf :rest "\))
end
Această versiune este corectă. După cum se vede, recursivitatea este una dintre căile cele mai fireşti de a programa în Logo. Există însă şi posibilitatea de a scrie şi versiuni iterative:
to maxim :in1 :in2 [:rest]
local "lmax make "lmax :in1
make "rest fput :in2 :rest
local "i make "i 1
repeat count :rest ~
[if :lmax < item :i :rest ~
[make "lmax item :i :rest]
make "i :i + 1]
op :lmax
end
Comanda repeat execută lista de instrucţiuni primită ca al doilea argument de un număr de ori precizat de primul argument. În cazul nostru, primul argument este funcţia count care numără elementele unei structuri de date (în cazul cuvintelor, numără caracterele).
Ce-a mai rămas
Nu am vorbit în această prezentare despre posibilităţile de lucru cu fişiere, despre comunicarea cu utilizatorul, nimic despre grafica ţestoasei (turtle graphic), despre controlul spaţiului de lucru (workspace) sau despre şabloane (templates). Nu m-am referit nici la construirea macrourilor sau la variabilele speciale.
MSWLogo (nu este un produs Microsoft!) dispune de toate ingredientele necesare realizării interfeţei grafice (ferestre, dialoguri, controale etc.) precum şi de proceduri pentru grafică bitmap, de proceduri specializate pentru comunicaţii în reţele TCP/IP precum şi de un întreg arsenal multimedia. Numeroasele exemple furnizate cuprind, printre altele, programe de inteligenţă artificială, de criptografie, un evaluator de expresii regulate, programe de animaţie şi chiar un interpretor de Pascal.
Logo nu este (numai) o jucărie. Din păcate, există puţine materiale introductive suficient de clare şi concise iar documentaţiile disponibile constau aproape exclusiv din descrierea, mai mult sau mai puţin formală, a primitivelor şi a procedurilor de bibliotecă. Speranţa mea este că după lectura acestui articol aceste documentaţii să vă fie de folos.
Un exemplu complet
Este vorba de un joc. Două grupuri de câte trei broscuţe se întâlnesc pe o punte. Un grup vine din dreapta iar celălalt din stânga şi încearcă să-şi continue drumul sărind unele peste altele. Broscuţele pot să se deplaseze doar sărind (înainte sau înapoi) peste una sau peste două broscuţe, presupunând că există mereu un loc liber printre ele. Problema s-a rezolvat când toate broscuţele care vin din dreapta se găsesc în stânga, indiferent unde este spaţiul liber.
Putem reprezenta situaţia printr-o listă, în care există trei elemente notate cu "<" (corespunzătoare broscuţelor care vin din dreapta), trei elemente notate cu ">" (broscuţele care vin din stânga) şi un element "-" (liniuţă) care corespunde spaţiului liber.
O mutare poate fi specificată prin indicarea broscuţei care sare, a direcţiei saltului (stânga sau dreapta) şi a lungimii (peste una sau peste două). Observăm însă că e mai simplu să considerăm că "sare" de fapt spaţiul liber. Aceste salturi le putem codifica prin cuvinte de genul "LD", unde L este lungimea ("2" sau "3") iar D este direcţia ("s" pentru stânga, "d" pentru dreapta).
Iată o variantă de rezolvare, pornind de la situaţia iniţială din enunţ (în dreptul poziţiei am notat şi mutarea care se va aplica):
[> > > - < < <] 3s
[- > > > < < <] 2d
[> > - > < < <] 3d
[> > < > < - <] 2s
[> > < - < > <] 3s
[- > < > < > <] 2d
[< > - > < > <] 2d
[< > < > - > <] 3s
[< - < > > > <] 2d
[< > < - > > <] 3d
[< > < < > > -] 2s
[< > < < - > >] 3s
[< - < < > > >]
O rezolvare "brută" este posibilă (se generează toate mutările posibile) dar este ineficientă şi... n-are nici un farmec. Voi considera o funcţie obiectiv (F) de evaluare a poziţiilor, funcţie care va trebui maximizată. O variantă simplă de definire a acestei funcţii este următoarea: definim un număr natural ale cărui cifre le obţinem înlocuind cu "0" elementele ">" şi cu "1" elementele "<" (se ignoră spaţiul liber"). În felul acesta, funcţia va avea ca maxim valoarea 111000.
Algoritmul (un backtracking clasic) este următorul: mutările posibile dintr-o poziţie dată se aplică în ordinea crescătoare a evaluărilor (prin funcţia F) poziţiilor rezultate. Dacă printr-un şir de mutări se ajunge într-o poziţie care a mai fost generată, se revine la poziţia precedentă şi se aplică următoarea mutare posibilă. Dacă se epuizează mutările disponibile, se revine la poziţia precedentă şi se repetă procedeul.
Este sigur că dacă există o rezolvare posibilă, algoritmul o va găsi (deoarece, la limită, se generează toate mutările posibile). Este însă greu de dovedit că rezolvarea obţinută prin acest algoritm este cea mai scurtă cu putinţă. Rezolvarea dată ca exemplu (din 12 mutări) a fost obţinută prin acest algoritm. Fără folosirea funcţiei de evaluare, rezultatul a fost obţinut din 47 de mutări.
Sursa din caseta "Un joc cu broscuţe" a fost testată sub MSWLogo. Implementarea se referă la un caz mai general decât cel enunţat. Se poate porni din orice poziţie validă iar numărul broscuţelor nu este fix. În plus, se pot indica şi alte mutări decât cele din enunţ (de pildă, în variabila m se pot adăuga mutările "4d" şi "4s"). În aceste condiţii, există posibilitatea ca anumite configuraţii să nu admită soluţie.
Implementarea nu are ca principal obiectiv performanţa, ci încearcă să fie cât mai clară şi să ilustreze diferite metode utilizate în programarea Logo. Comentariile (introduse prin caracterul ";") încearcă să sporească lizibilitatea. Descrierea procedurilor folosite le găsiţi în "Memo Logo".
Enjoy!
Rezolvare:
to joc :p
;--------------------------------------------
;--- Procedura principala
;--------------------------------------------
make "m [2d 3d 2s 3s] ; lista mutarilor
make "r [] ; rezultatul
make "max maxim :p
if emptyp :max ~
[pr "Configuratia\ este\ gresita]
if not incearca :p eval :p ~
[pr "Nu\ am\ gasit\ rezolvarea stop]
pr "Mutarile\ sunt:
prezinta :r
end
to maxim :p [:m "]
;--- Calculeaza maximul posibil pentru evaluare
;--- Verifica totodata daca pozitia initiala este valida
foreach :p ~
[ifelse equalp ? "> [make "m word :m 0]
[ifelse equalp ? "< [make "m word 1 :m]
[if not equalp ? "- [op "]]]]
op :m
end
to prezinta :list
; --- Comanda pentru afisarea elementelor listei :list
; --- in ordine inversa (de la sfirsit spre inceput)
ifelse emptyp :list ~
[stop] ~
[prezinta bf :list]
show first :list
end
to incearca :poz :v
;--- Procedura care implementeaza backtracking-ul.
;--- Al doilea argument este furnizat pentru a
;--- evita o noua evaluare a pozitiilor generate.
if memberp :poz :r [op "false]
push "r :poz
; singura iesire cu "true este cind se atinge maximul
if :max = eval :poz [op "true]
local "posibile make "posibile aplicabile :poz
while [not emptyp :posibile] ~
[test incearca aplica :poz first first :posibile ~
last first :posibile ~
iff [make "posibile bf :posibile ]
ift [op "true]]
op "false
end
to eval :poz [:e " ]
;--- Evalueaza pozitia :poz
;--- Produce cuvintul vid daca primeste la intrare
;--- lista vida (ca rezultat al aplicarii unei
;--- mutari imposibile)
if emptyp :poz [op :e]
if not equalp "- first :poz ~
[ifelse "< = first :poz ~
[make "e word :e "1] ~
[make "e word :e "0]]
op (eval bf :poz :e)
end
to aplicabile :poz [:l []]
;--- Returneaza o lista cu mutarile aplicabile pozitiei :poz.
;--- Fiecare mutare este reprezentata printr-o pereche
;--- compusa din codul mutarii si evaluarea pozitiei obtinute.
foreach :m ~
[make "l insereaza :l list ? eval aplica :poz ? ]
op :l
end
to insereaza :list :pair
; --- insereaza in lista :list perechea :pair
; --- astfel incit lista sa fie ordonata descrescator
; --- dupa al doilea element al perechilor
if emptyp last :pair [op :list]
if emptyp :list [op fput :pair :list]
ifelse not lessp last :pair last first :list ~
[op fput :pair :list] ~
[op (combine first :list insereaza bf :list :pair)]
end
to aplica :poz :mut
;--- aplica pozitiei :poz mutarea :mut
make "poz listtoarray :poz
local "n make "n count :poz
; determina pozitia spatiului liber ("p)
for [i 1 :n 1] ~
[if equalp "- item :i :poz ~
[make "p :i]]
; determina noua pozitie a spatiului
ifelse equalp item 2 :mut "d ~
[make "b :p + first :mut] ~
[make "b :p - first :mut]
; verifica daca noua pozitie este valida
if or :b < 1 :b > :n [op []]
; aplica miscarea
setitem :p :poz item :b :poz
setitem :b :poz "-
op arraytolist :poz
end
