Xanadu : programare imperativă cu tipuri dependente

Sursă originală: http://www.cs.bu.edu/~hwxi/Xanadu/Xanadu.html

Hongwei Xi


Investigator principalHongwei Xi
StudențiChihuan Chen (absolvent), Sa Cui (absolvent), Likai Liu ( licențiat ), Rui Shi (absolvent), Dengping Zhu (absolvent)
A sustineNSF CCR-0224244, 2000-2004
Cuvinte cheieTipuri dependente, programare imperativă, Xanadu, DTAL

Ne propunem să îmbogățim programarea imperativă practică cu o disciplină de tip care permite specificarea și deducerea unor informații mult mai precise despre programe decât cele impuse în limbi precum Java și Standard ML (SML).

Motivația primară pentru dezvoltarea unei astfel de discipline de tip este de a permite programatorului să exprime mai multe proprietăți ale programului cu tipuri și apoi să impună aceste proprietăți prin verificarea tipului. Este bine cunoscut faptul că o disciplină de tip, cum ar fi cea impusă în Java sau SML, poate facilita în mod eficient detectarea erorilor de program. Prin urmare, se poate aștepta ca o disciplină de tip mai puternică să ajute la detectarea mai multor erori de program, ceea ce duce la producerea de software mai robust.

În general, există două instrucțiuni pentru extinderea unui stil de tip Hindley-Milner cum ar fi cel din LMS. Una este să o extindem astfel încât mai multe programe să poată fi admise ca fiind corecte de tip, iar cealaltă să fie extinsă astfel încât programele să poată fi atribuite tipuri mai precise. Suntem interesați în primul rând de acesta din urmă.

Noțiunea de tipuri dependente, care a fost în mare parte inventată pentru modelarea programelor cu mai multă acuratețe, a fost studiată timp de cel puțin trei decenii. Cu toate acestea, utilizarea tipurilor dependente în programarea practică a fost rară dacă există, iar acest lucru, credem, este cauzat în principal de o mare dificultate în proiectarea unui algoritm de inferență de tip practic pentru un sistem dependent de tip. Am prezentat o abordare a abordării dificultății în proiectarea Dependent ML (DML), care extinde ML cu o noțiune de formă restrânsă de tipuri dependente. De asemenea, se demonstrează că tipurile dependente din LMM pot facilita eliminarea verificării legată de matrice, eliminarea clauzei de potrivire a șablonului, eliminarea etichetelor de verificare și reprezentarea fără etichete a tipurilor de date. Evident, o întrebare imediată este dacă putem profita de niște beneficii similare prin încorporarea tipurilor dependente în programarea imperativă. Propunem să abordăm această întrebare prin proiectarea unui limbaj de programare imperativ definit dependent.

Există încă o motivație pentru încorporarea tipurilor dependente în programarea practică. Într-un mediu de calcul neimprumut, cum ar fi Internetul, este posibil ca codul mobil primit de la o sursă necunoscută să nu fie de încredere. Prin urmare, destinatarii codului trebuie adesea să efectueze anumite verificări statice și / sau dinamice asupra codului mobil primit pentru a preveni apariția unor consecințe nedorite, cum ar fi încălcarea securității. Am proiectat o limbă de asamblare dependentă (DTAL) în care sistemul de tip poate garanta siguranța memoriei codului DTAL, unde siguranța memoriei constă atât în ​​siguranța tipului, cât și în inscripționarea în condiții de siguranță. Cu toate acestea, este dificil să compilați în codul DTAL un program scris într-o limbă precum Java, deoarece de multe ori pare ineficient să sintetizezi dintr-un astfel de program informațiile de tip necesare în codul DTAL.

Pe scurt, ne propunem să proiectăm un limbaj de programare imperativ de tip dependent, pentru a studia utilizarea tipurilor dependente în programarea practică imperativă atât la nivel de sursă, cât și la nivel de asamblare. Ne așteptăm ca acest studiu să conducă, în cele din urmă, la producția de software care nu este doar mai robust, ci și mai puțin costisitor de întreținut.

Ce este Xanadu?

Xanadu este un limbaj de programare imperativ. Iată o scurtă introducere ( ppt ).

Exemple de programe în Xanadu:

Prezentăm câteva exemple realiste în Xanadu în sprijinul caracterului practic al Xanadu.

  • Căutare binară:Următoarea este o implementare a căutării binare pe o gamă integeră în Xanadu. Noutatea implementării este adnotarea după cuvântul cheie invariant . Această adnotare este un tip dependent care afirmă anumite informații la punctul de intrare al bucla. În acest caz, adnotarea precizează că variabilele joase și înalte au tipuri int (i) și int (j) la punctul de intrare în buclă pentru unele întregi i și j astfel încât atât 0 <= i <= n și 0 <= j + 1 <= n țineți apăsat. Aceasta este o buclă invariantă, care poate garanta operația de subscripting a matricei vec [mid]în corpul bucla este în siguranță, adică nu poate ieși din limite. Punctul crucial este că verificarea de tip în Xanadu poate verifica automat dacă un program invariant ca acesta, furnizat de programator, este într-adevăr un program invariabil corect.În plus, este de asemenea verificat automat în Xanadu dacă o variabilă este deja inițializată înainte de a fi citită.{N: noapte} int bsearch (cheie: int, vec [n]: int) { var: int joasă, mijlocie, înaltă; int x ;; scăzut = 0; mare = arraysize (vec) – 1; invariante:

[i: int, j: int | 0 <= i <= n, 0 <= j + 1 <= n]

(scăzut: int (i), înalt: int (j)) în timp ce (low <= high) { mijloc = (scăzut + ridicat) / 2; x = vec [mijloc]; dacă (cheie == x) {retur mediu; } altfel dacă (cheie <x) {high = mid-1; } altfel {low = mid + 1; } } retur -1; } Lista inversă:

Acest exemplu demonstrează că în sistemul de tip Xanadu poate fi verificat faptul că o funcție de inversare a listei este de conservare a lungimii.

Următoarea declarație declară o listă polimorfică tip <‘a> . Cei doi constructori Nil și con asociat tipului de uniune sunt listați cu lista de listă (0) și {n: nat} ‘a * <‘ a> listă (n) -> <‘a> ) , respectiv, în sensul că Nil este o listă cu lungimea 0 și Cons întoarce o listă cu lungimea n +! atunci când este dat un element și o listă de lungime n . Rețineți că {n: nat} indică faptul că n , o variabilă index de tip de nat nat , este cuantificată universal. nat este tipul de indice de tip care reprezintă un număr natural.

listă union <'a> cu nat {
 Nil (0);
 {n: nat} Cons (n ​​+ 1) din lista "a * <'a' (n)
}
	

Următoarele elemente implementează funcția inversă din listă. Antetul funcției afirmă că pentru numerele naturale m și n , rev_app ia o pereche de liste cu lungimile m și n și returnează o listă cu lungimea m + n . Este clar că ieșirea , ceea ce înseamnă că un program se oprește anormal, nu poate fi executat niciodată în timpul execuției și, prin urmare, nu este necesar în acest caz. Din păcate, aceste informații nu pot fi captate în sistemul de tip Xanadu.

(a) {m: umed, n: umed}
<a> lista (m + n) rev_app
 (lista) (xs: <'a> (m), ys: <' a> lista (n)) {
   var: 'ax ;;
  
   invariante:
     

[m1: nat, n1: nat m1 + n1 = m + n]

(xs: <‘a> listă (m1), ys: <‘ a> listă (n1)) în timp ce (adevărat) { comuta (xs) { caz Nil: return ys; caz Cons (x, xs): ys = Contra (x, ys); } } Ieșire; } Funcția inversă a listei poate fi implementată după cum urmează. Antetul funcției indică faptul că aceasta este o funcție de conservare a lungimii.

(A) {n: noapte}
<a> listă (n) inversă (xs: <'a> listă (n)) {
   retur rev_app (xs, Nil);
}
	

Înmulțirea matricei rare:

Punem în aplicare multiplicarea între o matrice rară și un vector. Definim o înregistrare polimorfă <‘a> sparseArray pentru a reprezenta matricea de dimensiuni reduse în care fiecare element este de tip “a” . <a> sparseArray este indexat cu o pereche de numere naturale (m, n) , care reprezintă numărul de rânduri și numărul de coloane dintr-o matrice rară. Să sa fie un record de tip < ‘a> sparseArray (m, n) . Apoi sa are trei componente, și anume, rând , col șidate . În mod evident, tipurile atribuite rândului șicol indică faptul că sa și sa.col returnează dimensiunile lui sa Tipul atribuit datelor indică faptul că sa.dataeste o matrice de dimensiune m . În această matrice, fiecare element, care reprezintă un rând dintr-o matrice rară, este o listă de perechi și fiecare pereche constă dintr-un număr natural mai mic de n și un element de tip “a” .

{M: noapte, n: noapte}
înregistrați <a> sparseArray (m, n) {
  rând: int (m);
  col: int (n);
  date [m]: <int [0, n) * 'a> listă
}
	

Funcția mat_vec_mult are o matrice rară de dimensiuni (m, n) și un vector punct float cu dimensiunea n și returnează un vector punct float cu dimensiunea m . Rețineți că funcția list_vec_mult este utilizată pentru calculul produsului punct al unui rând în matricea rară și vectorul. Punctul pe care îl facem este că sistemul tip de Xanadu poate garanta toate operațiile de inscripționare a array-urilor din acest exemplu pentru a fi în siguranță la run-time.

{N: noapte}
pluti
list_vec_mult (xs: <int [0, n) * float> listă, vec [n]: float) {
  var: int i; float f, suma;

  sum = 0,0;
  în timp ce (adevărat) {
    comuta (xs) {
      caz Nil: suma retur;
      caz Cons ((i, f), xs): suma = suma +. f *. vec [i];      
    }
  }
  Ieșire;    
}

{M: noapte, n: noapte}
<float> matrice (m)
mat_vec_mult(mat: <float> sparseArray(m, n), vec[n]: float) {
  a fost: noaptea în; rezultatul float [];

  rezultat = newarray (mat.row, 0.0);

  pentru (i = 0; i <mat.row; i = i + 1) {
    result[i] = list_vec_mult (mat.data[i], vec);
  }
  rezultatul retur;
}
	    

heapsort:

Îți poți da seama de unul singur 🙂

{Max:} nat
înregistrați <a> heap (max) {
  max: int (max);
  dimensiune mutable: [dimensiune: nat | dimensiune <= max] int (dimensiune);
  date [max]: "a
}

{max: nat, i: nat i <max}
unitate heapify (heap: <float> heap (max), i: int (i)) {
  var: dimensiune int, stânga, dreapta;
       temperatura plutitoare;
       cea mai mare: [a: nat | un <max] int (a) ;;

  stânga = 2 * i + 1; dreapta = 2 * i + 2;

  dimensiune = heap.size; cel mai mare = i;

  dacă (marcă <stânga <) {
    dacă (heap.data [stânga]> .heap.data [i]) {cel mai mare = stânga; }
  }

  dacă (dimensiune dreapta <) {
    dacă (heap.data [dreapta]>. heap.data [cea mai mare]) {cea mai mare = dreapta; }
  }

  dacă (cel mai mare <> i) {
    temp = heap.data [i];
    heap.data [i] = heap.data [cel mai mare];
    heap.data [cel mai mare] = temp;
    heapify (heap, cel mai mare);
  }
}

{Max:} nat
unitatea de construcție (heap: <float> heap (max)) {
  var: int i, mărimea;
 
  dimensiune = heap.size;
 
  invariant: [i: int | i <max] (i: int (i))
  pentru (i = mărime / 2 - 1; i> = 0; i = i - 1) {
    heapify (heap, i);
  }
}

{Max:} nat
unitate heapsort (heap: <float> heap (max)) {
  var: int dimensiune, i; temperatura plutitoare;

  clădire (heap);
  invariant: [i: int | i <max] (i: int (i))
  pentru (i = heap.max - 1; i> = 1; i = i - 1) {
    temp = heap.data [i];
    heap.data [i] = heap.data [0];
    heap.data [0] = temp;
    heap.size = i;
    heapify (heap, 0);
  }
}
	

Eliminarea Gaussiană:

Îți poți da seama de unul singur 🙂

{m: umed, n: umed}
matricea de înregistrare <a> (m, n) {
  rând: int (m);
  col: int (n);
  date [m] [n]: "a
}

{m: umed, n: umed, i: umed, j: umed | i <m, j <m}
unitate
Variabilitatea lui (data [m] [n]: float, i: int (i), j:
  var: temp []: float;
  temp = date [i];
  date [i] = date [j];
  date [j] = temp;
}

{n: nat, i: nat i <n}
unitate
(n): float, n: int (n), i: int (i)) {
  var: float x ;;

  x = r [i]; r [i] = 1,0; i = i + 1;

  invariant: [i: nat] (i: int (i))
  în timp ce (i <n) {r [i] = r [i] /. X; i = i + 1;}
}

{n: nat, i: nat i <n}
unitate
(n): float, s [n]: float, n: int (n), i:
  var: float x ;;

  x = s [i]; s [i] = 0,0; i = i + 1;

  invariant: [i: nat] (i: int (i))
  în timp ce (i <n) {s [i] = s [i] -. X *. r [i]; i = i + 1;}
}

{m: nat, n: nat, i: nat m> i, n> i}

[k: nat k <m]

int (k) rMax (date [m] [n]: float, m: int (m), i: int var: nat j; float x, y; max: [k: nat k <m] int (k); max = i; x = fabs (date [i] [i]); j = i + 1; în timp ce (j <m) { y = fabs (date [j] [i]); dacă (y> .x) {x = y; max = j; } j = j + 1; } retur max; } {n: nat n> 0} unitatea gauss (mat: <float> matricea (n, n + 1)) { var: date plutitoare [] [n + 1]; noaptea i, j, max, n ;; date = mat.data; n = mat.row; pentru (i = 0; i <n; i = i + 1) { max = rowMax (date, n, i); normă (date [max], n + 1, i); șterge rând (date, i, max); pentru j = i + 1; j <n; j = j + 1) { rowElim (date [i], date [j], n + 1, i); } } } Mai multe exemple:

Puteți găsi mai multe exemple aici .

Lucrări pe sau legate de Xanadu

  • Hongwe Xi , Facilitarea Verificării Programului cu tipuri dependente, decembrie 1999. ( proiect )
  • Hongwe Xi , programarea imperativă cu tipuri dependente, decembrie 1999. ( proiect ) ( rezumat extins )
  • Hongwei Xi și Robert Harper , un limbaj al adunării inscripționate, raport tehnic OGI-CSE-99-008, iulie 1999. ( bibtex ) ( ps ) ( pdf ) ( rezumat extins )

Slide-uri

O discuție despre Xanadu poate fi găsită aici

Punerea în aplicare

O implementare a prototipului nedocumentat al Xanadu poate fi găsită aici . Păstrați tonul.


Hongwei Xi