Lambda terning

Lambda-terning ( λ-terning ) er en visuel klassifikation af otte maskinskrevne lambda-regninger med eksplicit typetildeling (kirketypesystemer ) . Terningen er organiseret efter mulige afhængigheder mellem typerne og vilkårene i denne kalkulering og danner en naturlig struktur for konstruktionskalkylen . Ideen med λ-kuben blev foreslået i 1991 af den hollandske logiker og matematiker Henk Barendregt . Yderligere generaliseringer af lambda-terningen kan opnås ved at overveje systemet af ren type .

Struktur af λ-terningen

I λ-kubesystemer tildeles variabler til en af to slags: eller . Alle gyldige udtryk er også sorteret. Påstanden om, at et udtryk tilhører en sortering, er bygget oven på skrivepåstanden, det vil sige, at udsagnet lyder som følger: elementet har en type og hører til sorten . Sorteringen bruges til almindelige variable og termer i λ-regningen, sorteringen bruges til variable og typeudtryk. Derfor behandles sorteringstyper og sorteringselementer i λ-kubesystemer som krydsende. For eksempel kan typen af et udtryk skrives som et element af en "højere" slags . Kultivartyper kaldes undertiden slægter . $\ast$ $\Boks$ $A:B:C$ $EN$ $B$ $C$ $\ast$ $\Boks$ $\ast$ $\Boks$ $(\lambda x:\alpha .\,x):(\alpha \to \alpha ):\ast$ $(\alpha \to \alpha ):\ast :\Box$ $\Boks$

Afhængighed forstås som evnen til at definere og bruge funktioner, der kortlægger elementer af en slags til en anden (eller den samme). Elementerne af en sortering er afhængige af elementerne af en sortering , hvis: $s_{1}$ $s_{2}$

for et gyldigt udtryk , der muligvis indeholder en variabel , kan vi definere en lambda-abstraktion ; ${\displaystyle F[x]:\tau :s_{1))$ ${\displaystyle x:\sigma :s_{2))$ ${\displaystyle (\lambda x:\sigma .\,F[x]):(\sigma \to \tau ):s_{1))$
funktionen skal have lov til at gælde for et element , og resultatet skal være et element af type sort , altså . $G:(\sigma \to \tau ):s_{1}$ ${\displaystyle Y:\sigma :s_{2))$ $\tau$ $s_{1}$ ${\displaystyle (G\,Y):\tau :s_{1))$

Terningens grundspids er det system, der svarer til den enkelt indtastede lambdaregning . Termer (elements of sort ) afhænger af termer; typer (sorteringselementer ) deltager ikke i afhængigheder. De tre akser, der kommer ud fra grundspidsen, giver anledning til følgende systemer: $\lambda ^{\højrepil }$ $\ast$ $\Boks$

udtryk afhængig af typer: system (lambda-regning med polymorfe typer, system F ); $\lambda 2$
typer afhængig af typer: system (lambda-regning med operatorer over typer); $\lambda \underline {\omega }$
term afhængige typer: system (lambda-regning med afhængige typer ). $\lambda P$

De resterende systemer er forskellige kombinationer af de anførte afhængigheder. Det rigeste system (polymorfe lambdaregning af højere orden med afhængige typer) er faktisk en konstruktionskalkyl . $\lambda P\omega$

Egenskaber for λ-kubesystemer

Alle lambda-terningsystemer har den stærke normaliseringsegenskab : ethvert tilladt udtryk (og type) kan reduceres til en enkelt normalform efter et endeligt antal β-reduktioner .

Support i programmeringssprog

Forskellige funktionelle sprog understøtter en anden delmængde af typesystemerne repræsenteret i lambda-terningen.

Haskell , ML - λ2 ( system F )
I en begrænset form understøtter Haskell (i GHC -implementeringen siden de seneste versioner) brug af "typefamilier". $\lambda \underline {\omega }$
Coq , Agda - ( konstruktionsberegning ) $\lambda P\omega$

Lambda terning

Struktur af λ-terningen

Egenskaber for λ-kubesystemer

Support i programmeringssprog

Links