Calculul construcțiilor

Proiectarea structurilor ( CoC limba engleză calculul construcțiilor ) este un lambda calcul tip de ordin superior , în care tipurile sunt valori de primă clasă. Prin urmare, este posibil, în CoC, să se definească funcții care merg de la numere întregi la numere întregi, dar și numere întregi la tipuri sau tipuri la tipuri.

CoC se normalizează puternic , deși, conform teoremei incompletitudinii lui Gödel , este imposibil să se demonstreze această proprietate chiar în CoC, deoarece implică consistența sa .

CoC a fost inițial dezvoltat de Thierry Coquand .

CoC a fost sursa primelor versiuni ale asistentului Coq proof . Următoarele versiuni au fost construite din calculul construcțiilor inductive, care este o extensie a CoC care integrează tipuri de date inductive . În CoC-ul original, tipurile de date inductive trebuiau emulate folosind funcția lor de distrugere.

Modul de a defini calculul construcțiilor prin trei tipuri de dependențe se numește cub lambda și se datorează lui Henk Barendregt .

Bazele proiectării construcțiilor

Calculul construcțiilor poate fi considerat ca o extensie a corespondenței Curry-Howard . Acesta din urmă asociază fiecare termen al lambda-calculului pur și simplu tastat cu o dovadă în deducție naturală în logica propozițională intuiționistă și invers. Calculul construcțiilor extinde acest izomorfism la dovezile din calculul predicatelor intuiționiste în ansamblu, care include, prin urmare, dovezi ale formulelor cuantificate (care vor fi numite și „propoziții”).

Termeni

Un termen al calculului construcțiilor este construit folosind următoarele reguli:

$\ mathbb {T}$ este un termen (numit și Tip )
$\ mathbb {P}$ este un termen (numit și Prop , tipul tuturor propozițiilor)
Dacă și sunt termeni, la fel sunt: LA{\ displaystyle A} $LA$ B{\ displaystyle B} $B$
- ${\ displaystyle \ mathbf {(} AB)}$
- ( ) ${\ displaystyle \ mathbf {\ lambda} x: AB}$
- ( ) ${\ displaystyle \ forall x: AB}$

Calculul construcțiilor are cinci tipuri de obiecte:

Dovezile , care sunt ceea ce privește tipurile de propuneri ;
De Propunerile , care sunt , de asemenea , numite baieti mici ;
cele predicate , care sunt funcții care propunerile de returnare;
tip larg , care sunt tipuri de predicate ( de exemplu , P este un tip larg);
T în sine, care este tipul de tipuri largi.

Judecăți

În calculul construcțiilor, o judecată este o deducție de tipare:

{\ displaystyle x_ {1}: A_ {1}, x_ {2}: A_ {2}, \ ldots \ vdash t: B}

care poate fi citit ca implicație

dacă variabilele sunt tipuri , atunci termenul este tip .

{\ displaystyle x_ {1}, x_ {2}, \ ldots}

{\ displaystyle A_ {1}, A_ {2}, \ ldots}

t

B

Judecățile valabile pentru calculul construcțiilor sunt derivabile dintr-un set de reguli de inferențe. În cele ce urmează, să fie utilizată pentru a înțelege o secvență de asociații de tip și vom scrie K pentru a desemna fie P sau T . $\Gamma$ ${\ displaystyle x_ {1}: A_ {1}, x_ {2}: A_ {2}, \ ldots}$

{\ displaystyle {\ Gamma \ vdash A: P}}

înseamnă că termenul este o dovadă a propoziției în context . $LA$ $P$ $\Gamma$

Vom însemna că înseamnă „ are pentru tip și are pentru tip ” și rezultatul înlocuirii variabilei cu termenul din termen . ${\ displaystyle A: B: C}$ $LA$ $B$ $B$ $VS$ ${\ displaystyle B (x: = N)}$ $X$ $NU$ $B$

O regulă de inferență este scrisă în formă

{\ displaystyle {\ Gamma \ vdash A: B} \ over {\ Gamma '\ vdash C: D}}

care înseamnă

dacă este o judecată valabilă, la fel este.

{\ displaystyle \ Gamma \ vdash A: B}

{\ displaystyle \ Gamma '\ vdash C: D}

Reguli de inferență pentru calculul construcțiilor

Fel: ${\ displaystyle {{} \ over {} \ Gamma \ vdash \ mathbb {P}: \ mathbb {T}}}$

Variabil: ${\ displaystyle {\ Gamma \ vdash A: K \ over {\ Gamma, x: A \ vdash x: K}}}$

Abstracție: ${\ displaystyle {\ Gamma, x: A \ vdash t: B: K \ over {\ Gamma \ vdash (\ lambda x: At): (\ forall x: AB): K}}}$

Cerere: ${\ displaystyle {\ Gamma \ vdash M: (\ forall x: AB) \ qquad \ qquad \ Gamma \ vdash N: A \ over {\ Gamma \ vdash MN: B (x: = N)}}}$

Conversie: ${\ displaystyle {\ Gamma \ vdash M: A \ qquad \ qquad A = _ {\ beta} B \ qquad \ qquad \ Gamma \ vdash B: K \ over {\ Gamma \ vdash M: B}}}$

Definiți operatori logici

Calculul construcțiilor este foarte parsimonios atunci când se iau în considerare doar operatorii de bază: singurul operator logic care formează propozițiile este . Cu toate acestea, acest operator unic este suficient pentru a defini toți ceilalți operatori logici: $\ pentru toți$

{\ displaystyle {\ begin {matrix} A \ Rightarrow B & \ equiv & \ forall x: AB & (x \ notin B) \\ A \ wedge B & \ equiv & \ forall C: \ mathbb {P}. ( A \ Rightarrow B \ Rightarrow C) \ Rightarrow C & \\ A \ vee B & \ equiv & \ forall C: \ mathbb {P}. (A \ Rightarrow C) \ Rightarrow (B \ Rightarrow C) \ Rightarrow C & \\\ neg A & \ equiv & \ forall C: \ mathbb {P}. (A \ Rightarrow C) & \\\ există x: AB & \ equiv & \ forall C: \ mathbb {P}. (\ forall x: A. (B \ Rightarrow C)) \ Rightarrow C & \ end {matrix}}}

Definiți tipurile de date

Tipurile de date de bază utilizate în informatică pot fi definite în calculul construcțiilor:

Booleeni

{\ displaystyle \ forall A: \ mathbb {P} .A \ Rightarrow A \ Rightarrow A}

Numere întregi naturale

{\ displaystyle \ forall A: \ mathbb {P}. (A \ Rightarrow A) \ Rightarrow (A \ Rightarrow A)}

Tip produs

{\ displaystyle A \ times B}

{\ displaystyle A \ wedge B}

Unire dezarticulată

{\ displaystyle A + B}

{\ displaystyle A \ vee B}

Vezi și tu

Articole similare

Teoreticieni

Referințe

(ro) Thierry Coquand și Gerard Huet, „Calculul construcțiilor”. Informații și calcul , vol. 76, n o 2-3 (1988).
(fr) Pentru o sursă liber accesibilă, vezi Coquand și Huet, „Calculul construcțiilor” . Raport tehnic 530, INRIA, Centrul Rocquencourt (1986).
(ro) MW Bunder și Jonathan P. Seldin, „Variante ale calculului de bază al construcțiilor” (2004).

Sursa de traducere

(fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia din limba engleză intitulat „ Calculul construcțiilor ” ( vezi lista autorilor ) .