Curry[1] este un limbaj de programare logică funcțională experimentală[2] bazat pe limbajul Haskell. Acesta îmbină elementele de programare funcțională și logică, inclusiv integrarea programării constrângerilor.
Este aproape un superset al lui Haskell, lipsit de sprijin, mai ales pentru supraîncărcare folosind clase de tip, pe care unele implementări le furnizează oricum ca o extensie a limbajului, cum ar fi compilatorul curcubeului Münster[3].
Baze de programare logică funcțională
Noțiuni de bază
Un program funcțional este un set de funcții definite prin ecuații sau reguli. Un calcul funcțional constă în înlocuirea subexprimărilor cu subexprimări egale (în ceea ce privește definițiile funcțiilor) până când nu mai sunt posibile înlocuiri (sau reduceri) și se obține o valoare sau o formă normală. De exemplu, luați în considerare funcția dublă definită de
double x = x+x
Expresia “double 1” se înlocuiește cu 1+1. Acesta din urmă poate fi înlocuit cu 2 dacă interpretăm operatorul “+” care trebuie definit printr-un set infinit de ecuații, de exemplu, 1+1 = 2, 1+2 = 3 etc. În mod similar, se pot evalua expresiile imbricate (unde se citează subexpresiile care trebuie înlocuite):
În acest caz, ambele derivări conduc la același rezultat, o proprietate cunoscută drept confluență. Aceasta rezultă dintr-o proprietate fundamentală a limbilor funcționale pure, denumită transparență referențială: valoarea unui rezultat calculat nu depinde de ordinea sau timpul de evaluare, datorită absenței efectelor secundare. Acest lucru simplifică raționamentul și menținerea programelor funcționale pure.
Cât de multe limbi funcționale ca Haskell do, Curry acceptă definirea tipurilor de date algebrice prin enumerarea constructorilor lor. De exemplu, tipul de valori booleene constă în constructorii True și False care sunt declarați după cum urmează:
dataBool=True|False
Funcțiile pentru booleani pot fi definite prin potrivirea tiparelor, adică prin furnizarea mai multor ecuații pentru valorile diferite ale argumentului:
notTrue=FalsenotFalse=True
Principiul înlocuirii egal cu egal este încă valabil, cu condiția ca argumentele actuale să aibă forma cerută, de exemplu:
not '(not False)' → 'not True' → False
Structurile de date mai complexe pot fi obținute prin tipuri de date recursive. De exemplu, o listă de elemente, unde tipul de elemente este arbitrar (denotat de variabila de tip a), este fie lista goală “[]”, fie lista ne-goală “x:xs” constând dintr-un prim element x și o listă xs:
dataLista=[]|a:Lista
Tipul "List a" este de obicei scris ca [a] și listele finite x1:x2:...:xn:[] sunt scrise ca [x1,x2,...,xn]. Putem defini operațiuni pe tipuri recursive prin definiții inductive în cazul în care modelul de potrivire susține separarea convenabilă a diferitelor cazuri. De exemplu, operația de concatenare "++" pe listele polimorfe poate fi definită după cum urmează (declarația de tip opțională din prima linie specifică faptul că "++" are două liste ca intrare și produce o listă de ieșire, același tip nespecificat):
(++)::[a]->[a]->[a][]++ys=ys(x:xs)++ys=x:xs++ys
Dincolo de aplicarea sa pentru diverse sarcini de programare, operația "++" este de asemenea utilă pentru a specifica comportamentul altor funcții în liste. De exemplu, comportamentul unei funcții care are ultimul element dintr-o listă poate fi specificat după cum urmează: pentru toate listele last xs = e dacă ∃ys:ys++[e] = xs.
Pe baza acestei specificații, se poate defini o funcție care să satisfacă această specificație utilizând funcții de programare logică. În mod similar cu limbile logice, limbile logice funcționale oferă căutarea unor soluții pentru variabilele cuantificate existențial. Spre deosebire de limbile logice pure, ele sprijină rezolvarea ecuațiilor peste expresiile funcționale imbricate, astfel încât o ecuație precum ys++[e] = [1,2,3] este rezolvată prin instanțierea ys în listă [1,2] și e la valoarea 3. In Curry one can define the operation last as follows:
lastxs|ys++[e]=:=xs=ewhereys,efree
Aici, simbolul "=: =" este folosit pentru constrângerile ecuaționale pentru a oferi o distincție sintactică de la ecuațiile definitorii. În mod similar, variabilele suplimentare (adică variabilele care nu apar în partea stângă a ecuației definitorii) sunt explicit declarate de "unde ... free" pentru a oferi unele posibilități de a detecta bug-uri cauzate de tipărire. O ecuație condiționată a formulei l | c = r este aplicabil pentru reducere dacă condiția lui c a fost rezolvată. Spre deosebire de limbile pur funcționale în care condițiile sunt evaluate doar la o valoare booleană, limbile logice funcționale sprijină rezolvarea condițiilor prin ghicirea valorilor pentru necunoscute în condiție. În scopul rezolvării unor astfel de condiții se utilizează o îngustare așa cum este discutată în secțiunea următoare.
Îngustarea
Îmbinarea este un mecanism prin care o variabilă este legată de o valoare selectată dintre alternativele impuse de constrângeri. Fiecare valoare posibilă este încercată într-o anumită ordine, iar restul programului invocat în fiecare caz pentru a determina validitatea legării. Înlăturarea este o extensie a programării logice, prin faptul că efectuează o căutare similară, dar poate genera de fapt valori ca parte a căutării, mai degrabă decât să se limiteze doar la testarea acestora.
Îmbinarea este utilă deoarece permite unei funcții să fie tratată ca o relație: valoarea sa poate fi calculată "în ambele direcții". Exemplele din Curry din secțiunea anterioară ilustrează acest lucru.
După cum sa menționat în secțiunea anterioară, îngustarea poate fi considerată ca o reducere pe un grafic de termeni al programului și există adesea multe căi (strategii) diferite pentru a reduce un anumit graf de termeni. Antoy et al.[4] a demonstrat în anii 1990 că o strategie specială de îngustare, este optimă în sensul de a face o serie de reduceri pentru a ajunge la o "formă normală" corespunzătoare unei soluții care este minimă între strategiile solide și complete.
Modele funcționale
Regula care definește last arătat mai sus exprimă faptul că argumentul propriu-zis trebuie să se potrivească cu rezultatul micșorării expresiei ys++[e]. Curry poate exprima această proprietate și în următorul mod mai concis:
last(ys++[e])=e
Haskell nu permite o astfel de declarație, deoarece modelul din partea stângă conține o funcție definită (++). Un astfel de model este numit și model funcțional[5]. Modelele funcționale sunt activate de trăsăturile funcționale și logice combinate ale Curry și oferă suport pentru definirea concisă a sarcinilor care necesită potrivirea modelului profund în structurile de date ierarhice.
Non-determinism
Din moment ce Curry este capabil să rezolve ecuațiile care conțin apeluri funcționale cu valori necunoscute, mecanismul de execuție se bazează pe calcule nedeterministe, la fel ca la programarea logică. Acest mecanism sprijină și definirea operațiilor non-deterministe, adică operații care oferă mai mult de un rezultat pentru o intrare dată. Arhetipul operațiilor non-deterministe este operația infixată predefinită, ? . Numită operator de selecție, care returnează unul dintre argumentele sale. Acest operator este definit de următoarele reguli:
x ? y = x
x ? y = y
Astfel, evaluarea expresiei 0 ? 1 returnează 0, precum și 1. Calculul cu operații non-deterministe și calculul cu variabile libere prin îngustare are aceeași putere expresivă[6].
Regulile care definesc ? arată o caracteristică importantă a Curry: toate regulile sunt încercate pentru a evalua o anumită operațiune. Prin urmare, se poate defini prin
insertxys=x:ysinsertx(y:ys)=y:insertxys
o operație de introducere a unui element într-o listă într-o poziție indeterminată, astfel încât perm de funcționare definit de
perm[]=[]perm(x:xs)=insertx(permxs)
returnează orice permutare a unei anumite liste de intrări.
Strategii
Datorită absenței efectelor secundare, un program logic funcțional poate fi executat cu strategii diferite. Pentru a evalua expresiile, Curry folosește o variantă a strategiei de îngustare necesară, care combină evaluarea leneșă cu strategiile de căutare nedeterminate. Spre deosebire de Prolog, care utilizează backtracking pentru a căuta soluții, Curry nu stabilește o strategie specială de căutare. Prin urmare, există implementări ale lui Curry, cum ar fi KiCS2, unde utilizatorul poate selecta cu ușurință o strategie de căutare, cum ar fi căutare în adâncime (backtracking), căutare în lățime, căutare aprofundată sau căutare paralelă.
