Programarea funcțională în parte Haskell 1

Aleksey Beshenov. scriitor tehnic, un specialist independent

programare imperativă

Cele mai frecvente limbi imperative. în care calculul reduce la executarea în serie de instrucțiuni. Soluție la limba imperativă este redusă la o descriere a ceea ce trebuie făcut pentru a obține rezultatul. Exemple clasice - Fortran (1957), ALGOL (1958) și C (1972).

limbi sunt aproape de imperativului arhitectura von Neumann. Ei ocupă o pondere semnificativă de cod atribuie valori variabilelor.

Variabilele sunt tratate ca memorie variabil în timp. Valorile curente ale variabilelor dintr-un program de schimbă starea.

Codul imperativ EXEMPLU - procedura factorialului în C:

Aici, repetarea multiplicării exprimate în termeni de ciclu. În procesul de calcul al valorilor de schimbare ale lui x și n variabile.

limbajele funcționale sunt declarativă - în programul lor formulează cu exactitate rezultatul necesar al calculului, în ceea ce privește dependența funcțiilor între ele, precum și detaliile de calcul (de exemplu, modul în care valoarea ar trebui să fie plasat în memorie și trimise) sunt suportate de limba de punere în aplicare.

Caracteristici și funcționalitate

În sens matematic, funcția f. X → Y - este, în general se asociază cu un element x din setul X (regiune), elementul y = f x a unei multitudini de Y (Codomeniu).

Figura 1. Funcția f. X → Y

Este important ca funcția a fost definită corect, adică. E. Relativ la valoarea sa pentru fiecare argument ar trebui să fie nici o ambiguitate.

În cazul în care valorile sunt definite pentru toate elementele câmpului, atunci funcția este apelată definită peste tot; în caz contrar este numit parțială.

Ca și în matematică, ne interesează în limbile funcționale nu există celule care dețin valori diferite. Variabilele sunt pur și simplu nume de valori.

În mod normal, funcțiile de locuri de muncă într-o limbă funcțională utilizată ecuația. De exemplu,

n - formale funcția argument fac. Pe partea dreaptă, după = semnul explică faptul că funcția face cu argumentul său. Funcțiile de bază pentru multiplicare și scădere sunt scrise prin infix (astfel cum este prevăzut între argumentele) operatorii * și -.

Există două ecuații. La calcularea funcției ecuației sunt vizualizate în secvență. Dacă n = 0, este utilizată prima ecuație. Dacă n ≠ 0, atunci nu va funcționa, și activat al doilea.

Notă: Argumentele funcției sunt afișate lângă numele său cu un spațiu. Acest lucru este convenabil, deoarece utilizarea funcției este foarte frecvente în programele funcționale (Tabelul 1).

În continuare, ne vom concentra pe sintaxa si semantica Haskell.

Scrierea în matematică

Scrierea în Haskell

Tabelul 1. Înregistrarea funcție de aplicație în matematică I V Haskell

Ecuațiile fac este o funcție specificată mai degrabă decât o secvență de acțiuni pe calcul, așa cum a fost cod imperativ.

Acesta utilizează recursie, t. E. determinat prin ea însăși Fac. Această definiție funcționează pentru că fac exprimat în termeni de caz mai simplu și, eventual, (dacă n ≥ 0), ajunge la bază cazul n = 0. Calculul inst 3 la o astfel de determinare poate fi făcută după cum urmează (pentru fiecare pas este simplificat expresii sunt subliniate):

Aici am aplicat la valoarea f 3. Acest 3 numit argumentul real.

Abordarea funcțională se axează pe expresii de evaluare, mai degrabă decât executarea de comenzi. De fapt, programul funcțional - această expresie, precum și punerea sa în aplicare a expresiei de calcul corespunzătoare.

În calcul, rescriem expresia, înlocuind valorile pentru variabilele și aplicarea funcției până la un rezultat final.

Rețineți că, pentru n <0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

Acum vom scrie funcția care calculează pentru k întreg și coeficientul binom reale r

Dacă k ≥ 0, avem expresia, unde numitorul este că numai un anumit număr k factorial, iar numărătorul - nivelul în scădere factorialului (scăderea puterii factorial)

Scriem pentru ea o definiție recursiv:

În prima ecuație, r nu este utilizat, astfel încât să puteți utiliza un substitut _ și scrie FFP _ 0 = 1.

Putem vedea că

(Check it out). Prin urmare, ecuația poate fi înlocuită cu un factorial

Odată ce am înregistrat FFP ecuația funcției. acesta poate fi considerat ca o cutie neagră abstractă, cu două intrări și o ieșire nu este îngrijorătoare despre ceea ce se întâmplă în interior. Tot ceea ce este important acum pentru noi - aceasta este reprezentarea corectă a intrărilor în funcție de producție.

Figura 2. Cutia neagră care calculează gradul de scădere a factorial

Ia-o altă cutie neagră (/) cu două intrări x și y și randamentul privat x / y:

va calcula un astfel de sistem:

Figura 3. Diagrama cutiei negre pentru a calcula coeficientul binomială

Aceasta corespunde expresiei

Definiți funcția dorită:

binc acum, de asemenea, poate fi considerat un abstract black-box și se aplică în determinarea altor caracteristici.

EXEMPLU calcularea binc 6 februarie:

Când ne-am conectat cutia neagră, vrem să spunem că acestea sunt, în primul rând, dau întotdeauna același rezultat pentru aceleași intrări și, în al doilea rând, nu afectează funcționarea altor cutii.

Acest lucru conduce la conceptul important de puritate.

Atunci când apelați o procedură într-un limbaj imperativ, noi de multe ori nu doar trece-l argumentele și pentru a obține rezultatul, dar ne așteptăm ca efect secundar - ceva care nu este asociat cu transferul de argumente în valoarea returnată (datele de ieșire într-un fișier, schimbați o variabilă globală, etc.). Din păcate, de multe ori apar efectele secundare, chiar dacă aceasta nu este prevăzută.

Dacă funcția are efecte secundare, calculul cu aceleași argumente într-un alt context poate da rezultate diferite.

În cazul în care efectele secundare sunt multe, cod de programare mai complicat există mai multe greșeli și devine dificil să se verifice corectitudinea ambelor mijloace formale și informale.

Aici noi nu numim o procedură funcție, deoarece prezența efectelor secundare ale procedurii nu este similară cu o funcție în sens matematic (numit uneori funcții pure astfel).

Fiecare expresie într-o limbă funcțională corespunde valorii sale; Calculul modifică doar expresia, dar valoarea nu este afectată.

Programarea fără efecte secundare pot fi luate în considerare pe deplin prin aplicarea funcțiilor la argumente.

Limba fără efecte secundare declarat a fi pur funcționale.

Limbi, cum ar fi ML și schema, în general, sunt funcționale în stil, dar permite atât atribuirea și a efectelor secundare.

La început poate părea că o limbă pur funcțională nu este practic, dar nu este așa - pentru programarea de succes trebuie doar să citiți câteva idei simple și elegante (precum și uitați despre obiceiurile vechi).

Lenea și lipsa de rigoare

Când se apelează primul argument calculat prin valoarea funcției, și apoi transferat în valorile funcției corpului obținute. Când apelați argumentele de necesitate a trecut neevaluate și calculată în organism funcție, numai dacă este necesar.

Aproximativ, acest lucru corespunde cu faptul că, în limbi funcționale se numește o evaluare energetică și leneș. În cazul în care tot ceea ce viguros calculat că este posibil, și în leneș - tot ce este necesar. (Am amâna o abordare formală a acestei probleme, atât timp cât se va explica ceea ce este în modelul de calcule bazate pe limbaje funcționale.)

O funcție se numește strict unul dintre argumentele sale, în cazul în care valoarea sa este întotdeauna necesară pentru a obține un rezultat. Dacă valoarea nu este necesară întotdeauna, funcția se numește permisivă în ceea ce acest argument.

De exemplu, funcția binc nostru va necesita întotdeauna valoarea k. dar valoarea r este necesară numai în cazul în care k ≥ 0.

În conformitate cu aceasta, vorbim despre limbi străine cu semantica stricte și limbajul cu semantica non-stricte. ( „lipsa de rigoare“ și „leneș“ - nu sunt identice, dar similare concepte.)

Limba strictă evaluează argumentele înainte de aplicarea funcției. Astfel, în cazul în care calculul expresiei e nu este finalizat (sau bucle este oprită cu o eroare), funcțiile aplicației f e este, de asemenea, nu se calculează.

În calculul limbaj non-strict este necesar. Dacă f laxe, atunci calculul f e poate fi finalizată, chiar și în cazul în care calculul nu este completă e.

indică o listă a trei elemente. fac calcul (-1) bucle. Prin urmare, calculul listei de asemenea, va bucla.

Acum, lăsați funcția de lungime returnează lungimea unei liste. expresie

Nu va fi calculată într-un limbaj strict, dar rezultatul este un non-strict 3, deoarece pentru calcularea elementelor de valorile lor nu sunt necesare.

Exemple de limbaje non-stricte: Miranda și Haskell. limbi stricte - ML și sistem.

Întrebarea de rigoare este subțire, și nu poate fi redus la un simplu „Ce este mai convenabil și mai eficiente?“> Transferul de calcul amânat în locul valorilor în apelul funcției este asociată cu un cost. Cu toate acestea, în multe situații lene salvează calcule sau scrie expresii care nu ar calcula sau să fie calculate infinit într-o limbă viguroasă.

Lipsa de rigoare este o caracteristică independentă în ceea ce privește puritatea, deși în multe privințe ajută limba să se abțină de la reacții adverse.

O scurtă istorie

Una dintre primele limbi, cu stil funcțional au fost LISP (1958), APL (1964), ISWIM (1966) și FP (1977).

Până la sfârșitul anilor 1980, au existat deja o mulțime de limbi funcționale. Printre cei care au avut un impact semnificativ asupra Haskell:

• ML (1973) - prima limbă cu dactilografiate Hindley-Milner.
• SASL. KRC. Miranda (1972-1985) - una dintre prima limbă leneș.
• Hope (1980) - una dintre prima limbă cu tipuri de date algebrice. Haskell dezvoltat de un grup mare de cercetători din anul 1987. Acesta este numit în onoarea lui Haskell Curry.

Figura 4. Originea Haskell

Obiectivul principal pe care sa axat proiectarea - Haskell a trebuit să adune experiența disponibilă în domeniul limbajului pur funcționale non-stricte.

Inovații Haskell - clase de tip și monade. Alte puncte forte, împrumutate din alte limbi - tipuri de date, Prelucrare algebrice, potrivire de model. (Aici, vom prezenta pur și simplu un set de cuvinte cheie, toate aceste concepte vor fi explicate în curând.)

Ultima descriere înregistrată - Haskell 98, dar limba este în continuă evoluție și complicată; Este programat să Haskell-ish“.

Haskell a devenit cel mai popular limbaj pur funcțional non-strictă. Pe Haskell a implementat mai multe proiecte complexe:

• Compilatoare și alte instrumente de dezvoltare.
• Distribuit sistem de control al versiunii Darcs.
• Managerul de ferestre xmonad.
• HAppS aplicatii web-server.
• Interpret / Pug compilator pentru Perl 6 limbi.
• Sistemul de operare Casa.
• Hardware descriere limbaj Lava.
• Sistemul de procesare a LOLITA limbajului natural.
• Sistem de demonstrare Teoreme Equinox / Paradox si Agda.

Principalele surse de informații despre Haskell

În Haskell există o comunitate largă și prietenos.

Principala sursă de informații - serverul haskell.org.

Acesta a liste de discuții, inclusiv:

• [email protected] - discuție liberă.
• [email protected] - o temă simplă pentru începători.

Există un foarte plin de viață IRC-canal #haskell pe irc.freenode.net. Este posibil pentru a obține rapid răspunsul pe cale amiabilă aproape orice întrebare.

execuție Editarea și codul

implementari Haskell

Formal, Haskell nu are nici o singură implementare „standard“.

Pentru o abordare interactivă Îmbrățișările interpret ușor.

De asemenea, există un proiect interesant Yhc. compilează codul sursă pentru bytecode, si heliu - formare versiunea Haskell, prietenos pentru nou-veniți (de exemplu, emiterea mesajelor de eroare). Cu toate acestea, ele sunt încă în curs de dezvoltare.

Standardul de facto a fost compilator / GHC interpret. El este cel mai avansat, în toate respectă și oferă o serie de extensii experimentale. Ne vom concentra pe ea.

Vom fi în primul rând interesat în programul ghci interactiv, care este convenabil pentru a testa exemplele de formare.

Deci, după instalarea GHC, puteți rula într-un terminal de ghci:

Aici Preludiu - este numele modulului încărcat. Preludiul conține definiții de bază, și este întotdeauna activată în mod implicit. Studiind sau rescrierea propriul lor cod Prelude, începătorii pot învăța o mulțime. (Suntem, de asemenea, o parte va face.)

Simbolul> înseamnă că ghci așteaptă de intrare de utilizator. Acesta poate fi expresia Haskell, precum și instrucțiunile pentru interpret.

← și → tastele puteți muta cursorul pe linia de comandă ghci. ↑ și ↓ pentru a parcurge istoria comenzilor înainte și înapoi.

În schimb Prelude> sau alte nume de module, vom continua să scrie ghci> (dacă doriți să facă același lucru, rulați comanda ghci: set „ghci>“ prompt).

Pentru a începe ghci poate fi folosit ca un calculator avansat:

Operatorii cu aceeași adoptate în alte limbi (a se vedea tabelul 2).

Tabel 2. Operatorii aritmetici de Prelude

Pentru ei este utilizat în x înregistrare și prioritatea corespunzătoare. De exemplu, 2 * 3 + 4 corespunde (2 * 3) +4. și 2 ^ 3 ^ 4 - 2 ^ (3 ^ 4). Pentru a modifica prioritatea adoptată, este posibil să se plaseze paranteze.

În ghci are o variabilă specială ea. egală cu valoarea ultimei expresie evaluată cu succes.

Editați codul sursă

Pentru Haskell codul folosit .hs fișiere de extindere.

Dacă scrieți cod în Haskell în fișierul foo.hs. definițiile sunt încărcate în comanda ghci: încărcare foo. În paralel, puteți edita fișierul și, dacă este necesar, reporniți definiția folosind: reincarca.

Actuala comandă schimbare director: cd (de exemplu, cd / home / Bob.).

Puteți descărca articol atașat la codul sursă și se calculează expresia:

Acestea și alte comenzi pot fi reduse - în loc de: încărcare utilizate: l. în schimb: reîncarcă -: r, și așa mai departe.

Listă de ecrane shell: ajutor. Pentru a ieși din ghci trebuie să tastați: renunțe.

Pe parcursul prezentării noastre vor fi întâlnite în mod frecvent exemple de simplu, constând din una sau două ecuații. Acestea pot fi încorporate imediat în ghci folosind lasa:

Dacă mai multe ecuații, acestea trebuie să fie închise în paranteze și separate prin virgulă (într-un articol viitor, vom discuta acest post).

concluzie