Hispanopedia Wiki
Articulo de referencia

cálculo lambda tipado simple

El cálculo lambda tipado simplemente ( ⁠ λ → {\displaystyle \lambda ^{\to }} ⁠ ), una forma de teoría de tipos , es una interpretación tipada del cálculo lambda con un solo cons...

Hispanopedia WikiContenido en espanolLectura gratuita

El cálculo lambda tipado simplemente ( ⁠λ→{\displaystyle \lambda ^{\to }}⁠ ), una forma de teoría de tipos , es una interpretación tipada del cálculo lambda con un solo constructor de tipos ( ⁠→{\displaystyle \to }) que construye tipos de funciones . Es el ejemplo canónico y más simple de un cálculo lambda tipado. El cálculo lambda tipado simple fue introducido originalmente por Alonzo Church en 1940 como un intento de evitar el uso paradójico del cálculo lambda no tipado . [ 1 ]

El término tipo simple también se utiliza para referirse a extensiones del cálculo lambda de tipo simple con construcciones como productos , coproductos o números naturales ( Sistema T ) o incluso recursión completa (como PCF ). Por el contrario, los sistemas que introducen tipos polimórficos (como el Sistema F ) o tipos dependientes (como el Marco Lógico ) no se consideran de tipo simple . Los tipos simples, excepto la recursión completa, todavía se consideran simples porque las codificaciones de Church de tales estructuras se pueden hacer utilizando solo→{\displaystyle \to }y variables de tipo adecuadas, mientras que el polimorfismo y la dependencia no pueden.

Sintaxis

En la década de 1930, Alonzo Church buscó utilizar el método logístico : [ a ] su cálculo lambda , como lenguaje formal basado en expresiones simbólicas, consistía en una serie numerablemente infinita de axiomas y variables, [ b ] pero también un conjunto finito de símbolos primitivos, [ c ] que denotaban abstracción y alcance, así como cuatro constantes: negación, disyunción, cuantificación universal y selección respectivamente; [ d ] [ e ] y también, un conjunto finito de reglas I a VI. Este conjunto finito de reglas incluía la regla V modus ponens, así como IV y VI para sustitución y generalización respectivamente. [ d ] Las reglas I a III se conocen como conversión alfa, beta y eta en el cálculo lambda. Church buscó utilizar el inglés solo como un lenguaje sintáctico (es decir, un lenguaje metamatemático) para describir expresiones simbólicas sin interpretaciones. [ f ]

En 1940, Church optó por una notación de subíndice para denotar el tipo en una expresión simbólica. [ b ] En su presentación, Church utilizó solo dos tipos base:o{\displaystyle o}para "el tipo de proposiciones" yyo{\displaystyle \iota }para "el tipo de individuos". El tipoo{\displaystyle o}no tiene constantes de término, mientras queyo{\displaystyle \iota }tiene un término constante. Frecuentemente el cálculo con un solo tipo base, usualmenteo{\displaystyle o}⁠ , se considera. Los subíndices de las letras griegas ⁠α{\displaystyle \alpha },​​β{\displaystyle \beta }⁠ , etc. denotan variables de tipo; el subíndice entre paréntesis(αβ){\displaystyle (\alpha \beta )}indica el tipo de funciónβ→α{\displaystyle \beta \to \alpha }⁠ . Iglesia 1940 p.58 usó 'flecha o ⁠→{\displaystyle \to }' para denotar significa , o es una abreviatura de . [ g ] En la década de 1970 se utilizaba la notación de flecha independiente; por ejemplo, en este artículo símbolos sin subíndiceσ{\displaystyle \sigma }yτ{\displaystyle \tau }puede abarcar varios tipos. El número infinito de axiomas se consideró entonces una consecuencia de aplicar las reglas I a VI a los tipos (véase axiomas de Peano ). De manera informal, el tipo de funciónσ→τ{\displaystyle \sigma \to \tau }se refiere al tipo de funciones que, dada una entrada de tipo ⁠σ{\displaystyle \sigma }⁠ , producir una salida de tipo ⁠τ{\displaystyle \tau }⁠ . Por convención,→{\displaystyle \to }asociados a la derecha:σ→τ→ρ{\displaystyle \sigma \to \tau \to \rho }se lee comoσ→(τ→ρ){\displaystyle \sigma \to (\tau \to \rho )}⁠ .

Para definir los tipos, un conjunto de tipos base ,B{\displaystyle B}⁠ , primero deben definirse. A veces se les llama tipos atómicos o constantes de tipo . Una vez corregido esto, la sintaxis de los tipos es:

τ::=τ→τ∣TwhmirmiT∈B.{\displaystyle \tau \;{{:}{:=}}\;\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B.}

Por ejemplo ,B={a,b}{\displaystyle B=\{a,b\}}⁠ , genera un conjunto infinito de tipos que comienzan con ⁠a{\displaystyle a},​​b{\displaystyle b},​​a→a{\displaystyle a\to a},​​a→b{\displaystyle a\to b},​​b→b{\displaystyle b\to b},​​b→a{\displaystyle b\to a},​​a→(a→a){\displaystyle a\to (a\to a)}, ... ,(b→a)→(a→b){\displaystyle (b\to a)\to (a\to b)}, ...

También se fija un conjunto de constantes de término para los tipos base. Por ejemplo, se podría suponer que uno de los tipos base es nat , y sus constantes de término podrían ser los números naturales.

La sintaxis del cálculo lambda de tipos simples es esencialmente la del propio cálculo lambda. El términoincógnita:τ{\displaystyle x{\mathbin {:}}\tau }denota que la variableincógnita{\displaystyle x}es de tipoτ{\displaystyle \tau }⁠ . El término sintaxis, en forma Backus-Naur , es referencia variable , abstracciones , aplicación o constante :

mi::=incógnita∣λincógnita:τ.mi∣mimi∣do{\displaystyle e\;{{:}{:=}}\;x\mid \lambda x\mathbin {:} \tau .e\mid e\,e\mid c}

dóndedo{\displaystyle c}es un término constante. Una referencia variableincógnita{\displaystyle x}Se considera vinculado si se encuentra dentro de una vinculación de abstracción .incógnita{\displaystyle x}Un término es cerrado si no hay variables no ligadas .

En comparación, la sintaxis del cálculo lambda sin tipado no tiene tales tipos ni constantes de término:

mi::=incógnita∣λincógnita.mi∣mimi{\displaystyle e\;{{:}{:=}}\;x\mid \lambda x.e\mid e\,e}

Mientras que en el cálculo lambda tipado, cada abstracción (es decir, función) debe especificar el tipo de su argumento.

Reglas de mecanografía

Para definir el conjunto de términos lambda bien tipados de un tipo dado, se define una relación de tipado entre términos y tipos. Primero, se introducen contextos de tipado o entornos de tipado .Γ,Δ,…{\displaystyle \Gamma ,\Delta ,\dots }, que son conjuntos de supuestos de tipado. Un supuesto de tipado tiene la forma ⁠incógnita:σ{\displaystyle x{\mathbin {:}}\sigma }⁠ , que significa variableincógnita{\displaystyle x}tiene tipoσ{\displaystyle \sigma }⁠ .

La relación de tipadoΓ⊢mi:σ{\displaystyle \Gamma \vdash e{\mathbin {:}}\sigma }indica quemi{\displaystyle e}es un término de tipoσ{\displaystyle \sigma }en contextoΓ{\displaystyle \Gamma }⁠ . En este casomi{\displaystyle e}Se dice que está bien tipificado (teniendo tipo ⁠σ{\displaystyle \sigma }⁠ ). Las instancias de la relación de tipado se denominan juicios de tipado . La validez de un juicio de tipado se demuestra proporcionando una derivación de tipado , construida utilizando reglas de tipado (en la que las premisas por encima de la línea nos permiten derivar la conclusión por debajo de la línea). El cálculo lambda tipado simple utiliza estas reglas: [ h ]

En palabras,

  1. Siincógnita{\displaystyle x}tiene tipoσ{\displaystyle \sigma }en ese contexto, entoncesincógnita{\displaystyle x}tiene tipoσ{\displaystyle \sigma }⁠ .
  2. Las constantes de término tienen los tipos base apropiados.
  3. Si, en cierto contexto conincógnita{\displaystyle x}que tiene tipoσ{\displaystyle \sigma }⁠ ,mi{\displaystyle e}tiene tipoτ{\displaystyle \tau }⁠ , entonces, en el mismo contexto sin ⁠incógnita{\displaystyle x},​​λincógnita:σ. mi{\displaystyle \lambda x{\mathbin {:}}\sigma .~e}tiene tipo​σ→τ{\displaystyle \sigma \to \tau }⁠ .
  4. Si, en cierto contexto,mi1{\displaystyle e_{1}}tiene tipoσ→τ{\displaystyle \sigma \to \tau }y​mi2{\displaystyle e_{2}}tiene tipoσ{\displaystyle \sigma }, entoncesmi1 mi2{\displaystyle e_{1}~e_{2}}tiene tipoτ{\displaystyle \tau }⁠ .

Ejemplos de términos cerrados, es decir, términos que se pueden tipificar en el contexto vacío, son:

  • Para cada tipoτ{\displaystyle \tau }⁠ , un términoλincógnita:τ.incógnita:τ→τ{\displaystyle \lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau }( función identidad /I-combinador),
  • Para tiposσ,τ{\displaystyle \sigma ,\tau }⁠ , un términoλincógnita:σ.λy:τ.incógnita:σ→τ→σ{\displaystyle \lambda x{\mathbin {:}}\sigma .\lambda y{\mathbin {:}}\tau .x{\mathbin {:}}\sigma \to \tau \to \sigma }(el combinador K) y
  • Para tiposτ,τ′,τ″{\displaystyle \tau ,\tau ',\tau ''}⁠ , un términoλincógnita:τ→τ′→τ″.λy:τ→τ′.λz:τ.incógnitaz(yz):(τ→τ′→τ″)→(τ→τ′)→τ→τ″{\displaystyle \lambda x{\mathbin {:}}\tau \to \tau '\to \tau ''.\lambda y{\mathbin {:}}\tau \to \tau '.\lambda z{\mathbin {:}}\tau .xz(yz):(\tau \to \tau '\to \tau '')\to (\tau \to \tau ')\to \tau \to \tau ''}(el combinador S).

Estas son las representaciones tipificadas en cálculo lambda de los combinadores básicos de la lógica combinatoria .

Cada tipoτ{\displaystyle \tau }Se le asigna un orden, un número .o(τ){\displaystyle o(\tau )}⁠ . Para tipos base, ⁠o(T)=0{\displaystyle o(T)=0}; para tipos de función ,o(σ→τ)=máximo(o(σ)+1,o(τ)){\displaystyle o(\sigma \to \tau )={\mbox{max}}(o(\sigma )+1,o(\tau ))}⁠ . Es decir, el orden de un tipo mide la profundidad de la flecha anidada más a la izquierda. Por lo tanto:

o(yo→yo→yo)=1{\displaystyle o(\iota \to \iota \to \iota )=1}
o((yo→yo)→yo)=2{\displaystyle o((\iota \to \iota )\to \iota )=2}

Semántica

Interpretaciones intrínsecas frente a extrínsecas

En términos generales, existen dos maneras diferentes de asignar significado al cálculo lambda simplemente tipado, al igual que a los lenguajes tipados en general, denominadas intrínsecas frente a extrínsecas, ontológicas frente a semánticas, o de estilo Church frente a de estilo Curry. [ 1 ] [ 7 ] [ 8 ] Una semántica intrínseca solo asigna significado a términos bien tipados, o más precisamente, asigna significado directamente a las derivaciones de tipado. Esto tiene como efecto que a términos que difieren únicamente en las anotaciones de tipo se les pueden asignar significados diferentes. Por ejemplo, el término identidadλincógnita:inortet. incógnita{\displaystyle \lambda x{\mathbin {:}}{\mathtt {int}}.~x}sobre los números enteros y el término identidadλincógnita:bool. incógnita{\displaystyle \lambda x{\mathbin {:}}{\mathtt {bool}}.~x}En los booleanos, puede significar cosas diferentes. (Las interpretaciones clásicas previstas son la función identidad en los enteros y la función identidad en los valores booleanos). En contraste, una semántica extrínseca asigna significado a los términos independientemente de su tipado, como se interpretarían en un lenguaje sin tipado. Desde esta perspectiva,λincógnita:inortet. incógnita{\displaystyle \lambda x{\mathbin {:}}{\mathtt {int}}.~x}yλincógnita:bool. incógnita{\displaystyle \lambda x{\mathbin {:}}{\mathtt {bool}}.~x}significan lo mismo (es decir, lo mismo que ⁠λincógnita. incógnita{\displaystyle \lambda x.~x}⁠ ).

La distinción entre semántica intrínseca y extrínseca se asocia a veces con la presencia o ausencia de anotaciones en abstracciones lambda, pero, estrictamente hablando, este uso es impreciso. Es posible definir una semántica extrínseca en términos anotados simplemente ignorando los tipos (es decir, mediante el borrado de tipos ), al igual que es posible dar una semántica intrínseca a términos no anotados cuando los tipos se pueden deducir del contexto (es decir, mediante la inferencia de tipos ). La diferencia esencial entre los enfoques intrínseco y extrínseco radica en si las reglas de tipado se consideran como la definición del lenguaje o como un formalismo para verificar propiedades de un lenguaje subyacente más primitivo. La mayoría de las diferentes interpretaciones semánticas que se analizan a continuación pueden verse desde una perspectiva intrínseca o extrínseca.

Teoría de ecuaciones

El cálculo lambda tipado simple (STLC) tiene la misma teoría ecuacional de βη-equivalencia que el cálculo lambda no tipado , pero sujeto a restricciones de tipo. La ecuación para la reducción beta [ i ]

(λincógnita:σ. t)tú=βt[incógnita:=tú]{\displaystyle (\lambda x{\mathbin {:}}\sigma .~t)\,u=_{\beta }t[x:=u]}

se sostiene en contextoΓ{\displaystyle \Gamma }cuando seaΓ,incógnita:σ⊢t:τ{\displaystyle \Gamma ,x{\mathbin {:}}\sigma \vdash t{\mathbin {:}}\tau }y​Γ⊢tú:σ{\displaystyle \Gamma \vdash u{\mathbin {:}}\sigma }⁠ , mientras que la ecuación para la reducción de eta [ j ]

λincógnita:σ. tincógnita=ηt{\displaystyle \lambda x{\mathbin {:}}\sigma .~t\,x=_{\eta }t}

se mantiene siempreΓ⊢t:σ→τ{\displaystyle \Gamma \vdash t{:}\sigma \to \tau }yincógnita{\displaystyle x}no aparece libre ent{\displaystyle t}La ventaja del cálculo lambda tipado es que STLC permite acortar (es decir, reducir ) los cálculos potencialmente no terminantes. [ 9 ]

Semántica operacional

Asimismo, la semántica operacional del cálculo lambda simplemente tipado puede fijarse como en el cálculo lambda no tipado, utilizando la evaluación por nombre , por valor u otras estrategias de evaluación . Como en cualquier lenguaje tipado, la seguridad de tipos es una propiedad fundamental de todas estas estrategias de evaluación. Además, la fuerte propiedad de normalización descrita a continuación implica que cualquier estrategia de evaluación terminará en todos los términos simplemente tipados. [ 10 ]

Semántica categórica

El cálculo lambda tipado simple enriquecido con tipos de producto, operadores de emparejamiento y proyección (conβη{\displaystyle \beta \eta }-equivalencia) es el lenguaje interno de las categorías cerradas cartesianas (CCC), como observó por primera vez Joachim Lambek . [ 11 ] Dada cualquier CCC, los tipos básicos del cálculo lambda correspondiente son los objetos , y los términos son los morfismos . Recíprocamente, el cálculo lambda simplemente tipado con tipos producto y operadores de emparejamiento sobre una colección de tipos base y términos dados forma una CCC cuyos objetos son los tipos, y los morfismos son clases de equivalencia de términos.

Existen reglas de tipado para emparejamiento , proyección y término unitario . Dados dos términoss:σ{\displaystyle s{\mathbin {:}}\sigma }y​t:τ{\displaystyle t{\mathbin {:}}\tau }⁠ , el término(s,t){\displaystyle (s,t)}tiene tipoσ×τ{\displaystyle \sigma \times \tau }⁠ . Asimismo, si uno tiene un plazo ⁠tú:τ1×τ2{\displaystyle u{\mathbin {:}}\tau _{1}\times \tau _{2}}⁠ , entonces hay términosπ1(tú):τ1{\displaystyle \pi _{1}(u){\mathbin {:}}\tau _{1}}yπ2(tú):τ2{\displaystyle \pi _{2}(u){\mathbin {:}}\tau _{2}}donde elπi{\displaystyle \pi _{i}}corresponden a las proyecciones del producto cartesiano. El término unitario , de tipo 1, escrito como(){\displaystyle ()}y vocalizado como 'nil', es el objeto final . La teoría ecuacional se extiende de igual manera, de modo que uno tiene

π1(s:σ,t:τ)=s:σ{\displaystyle \pi _{1}(s{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )=s{\mathbin {:}}\sigma }
π2(s:σ,t:τ)=t:τ{\displaystyle \pi _{2}(s{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )=t{\mathbin {:}}\tau }
(π1(tú:σ×τ),π2(tú:σ×τ))=tú:σ×τ{\displaystyle (\pi _{1}(u{\mathbin {:}}\sigma \times \tau ),\pi _{2}(u{\mathbin {:}}\sigma \times \tau ))=u{\mathbin {:}}\sigma \times \tau }
t:1=(){\displaystyle t{\mathbin {:}}1=()}

Esto último se lee como " si t tiene tipo 1, entonces se reduce a cero ".

Lo anterior se puede convertir entonces en una categoría tomando los tipos como objetos . Los morfismosσ→τ{\displaystyle \sigma \to \tau }son clases de equivalencia de pares(incógnita:σ,t:τ){\displaystyle (x{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )}donde x es una variable (de tipo ⁠σ{\displaystyle \sigma }) y t es un término (de tipoτ{\displaystyle \tau }⁠ ), que no contiene variables libres, excepto (opcionalmente) x . El conjunto de términos en el lenguaje es el cierre de este conjunto de términos bajo las operaciones de abstracción y aplicación .

Esta correspondencia puede extenderse para incluir "homomorfismos de lenguaje" y functores entre la categoría de categorías cartesianas cerradas y la categoría de teorías lambda simplemente tipadas.

Parte de esta correspondencia puede extenderse a categorías monoidales simétricas cerradas mediante el uso de un sistema de tipos lineal .

Semántica de la teoría de la demostración

El cálculo lambda de tipos simples está estrechamente relacionado con el fragmento implicacional de la lógica intuicionista proposicional , es decir, el cálculo proposicional implicacional , a través del isomorfismo de Curry-Howard : los términos corresponden precisamente a las demostraciones en la deducción natural , y los tipos habitados son exactamente las tautologías de esta lógica.

A partir de su método logístico, Church 1940 [ 1 ] p.58 estableció un esquema axiomático , [ 1 ] p. 60, que Henkin 1949 completó [ 3 ] con dominios de tipo (por ejemplo, los números naturales, los números reales, etc.). Henkin 1996 p. 146 describió cómo el método logístico de Church podría buscar proporcionar una base para las matemáticas (aritmética de Peano y análisis real), [ 4 ] a través de la teoría de modelos .

Sintaxis alternativas

La presentación dada anteriormente no es la única forma de definir la sintaxis del cálculo lambda de tipos simples.

Borrado de tipos

Una alternativa es eliminar por completo las anotaciones de tipo (de modo que la sintaxis sea idéntica al cálculo lambda sin tipado), al tiempo que se garantiza que los términos estén bien tipados mediante la inferencia de tipos de Hindley-Milner . El algoritmo de inferencia es terminante, sólido y completo: siempre que un término sea tipificable, el algoritmo calcula su tipo. Más precisamente, calcula el tipo principal del término , ya que a menudo un término sin anotar (como ⁠λincógnita. incógnita{\displaystyle \lambda x.~x}⁠ ) ​​puede tener más de un tipo ( ⁠inortet→inortet{\displaystyle {\mathtt {int}}\to {\mathtt {int}}},​​bool→bool{\displaystyle {\mathtt {bool}}\to {\mathtt {bool}}}, etc., que son todos ejemplos del tipo principalα→α{\displaystyle \alpha \to \alpha }⁠ ).

Verificación de tipos bidireccional

Otra presentación alternativa del cálculo lambda tipado simple se basa en la verificación de tipos bidireccional [ 12 ] , que requiere más anotaciones de tipo que la inferencia de Hindley-Milner pero es más fácil de describir. El sistema de tipos se divide en dos juicios, que representan tanto la verificación como la síntesis , escritosΓ⊢mi⇐τ{\displaystyle \Gamma \vdash e\Leftarrow \tau }yΓ⊢mi⇒τ{\displaystyle \Gamma \vdash e\Rightarrow \tau }respectivamente. Operacionalmente, los tres componentesΓ{\displaystyle \Gamma },​​mi{\displaystyle e}y​τ{\displaystyle \tau }son todos insumos para el juicio de verificaciónΓ⊢mi⇐τ{\displaystyle \Gamma \vdash e\Leftarrow \tau }⁠ , mientras que el juicio de síntesisΓ⊢mi⇒τ{\displaystyle \Gamma \vdash e\Rightarrow \tau }solo tomaΓ{\displaystyle \Gamma }ymi{\displaystyle e}como entradas, produciendo el tipoτ{\displaystyle \tau }como resultado. Estos juicios se derivan mediante las siguientes reglas:

Obsérvese que las reglas [1]–[4] son ​​casi idénticas a las reglas (1)–(4) anteriores , salvo por la cuidadosa selección de los juicios de verificación o síntesis. Estas selecciones pueden explicarse de la siguiente manera:

  1. Siincógnita:σ{\displaystyle x{\mathbin {:}}\sigma }está en el contexto, podemos sintetizar tipoσ{\displaystyle \sigma }para​incógnita{\displaystyle x}⁠ .
  2. Los tipos de constantes de término son fijos y pueden sintetizarse.
  3. Para comprobar esoλincógnita. mi{\displaystyle \lambda x.~e}tiene tipoσ→τ{\displaystyle \sigma \to \tau }En algún contexto, extendemos el contexto conincógnita:σ{\displaystyle x{\mathbin {:}}\sigma }y comprobar quemi{\displaystyle e}tiene tipoτ{\displaystyle \tau }⁠ .
  4. Simi1{\displaystyle e_{1}}sintetiza tipoσ→τ{\displaystyle \sigma \to \tau }(en algún contexto), ymi2{\displaystyle e_{2}}comprobaciones contra el tipoσ{\displaystyle \sigma }(en el mismo contexto), entoncesmi1 mi2{\displaystyle e_{1}~e_{2}}sintetiza tipoτ{\displaystyle \tau }⁠ .

Obsérvese que las reglas de síntesis se leen de arriba abajo, mientras que las reglas de verificación se leen de abajo arriba. Nótese en particular que no necesitamos ninguna anotación en la abstracción lambda de la regla [3], porque el tipo de la variable ligada se puede deducir del tipo en el que verificamos la función. Finalmente, explicamos las reglas [5] y [6] de la siguiente manera:

  1. Para comprobar esomi{\displaystyle e}tiene tipoτ{\displaystyle \tau }⁠ , basta con sintetizar el tipo ⁠τ{\displaystyle \tau }⁠ .
  2. Simi{\displaystyle e}comprobaciones contra el tipoτ{\displaystyle \tau }⁠ , entonces el término anotado explícitamente(mi:τ){\displaystyle (e{\mathbin {:}}\tau )}sintetiza​τ{\displaystyle \tau }⁠ .

Debido a estas dos últimas reglas que establecen una relación entre síntesis y verificación, es fácil ver que cualquier término bien tipificado pero sin anotaciones puede verificarse en el sistema bidireccional, siempre que insertemos suficientes anotaciones de tipo. De hecho, las anotaciones solo son necesarias en los β-redexes.

Observaciones generales

Dada la semántica estándar, el cálculo lambda simplemente tipado es fuertemente normalizador : toda secuencia de reducciones termina eventualmente. [ 10 ] Esto se debe a que la recursión no está permitida por las reglas de tipado: es imposible encontrar tipos para combinadores de punto fijo y el término de bucle .Ω=(λincógnita. incógnita incógnita)(λincógnita. incógnita incógnita){\displaystyle \Omega =(\lambda x.~x~x)(\lambda x.~x~x)}La recursión se puede agregar al lenguaje mediante un operador especial .Fiincógnitaα{\displaystyle {\mathtt {fix}}_{\alpha }}de tipo(α→α)→α{\displaystyle (\alpha \to \alpha )\to \alpha }o agregando tipos recursivos generales , aunque ambos eliminan la normalización fuerte.

A diferencia del cálculo lambda sin tipos, el cálculo lambda con tipos simples no es Turing completo . Todos los programas en el cálculo lambda con tipos simples terminan. En el cálculo lambda sin tipos, existen programas que no terminan y, además, no existe un procedimiento de decisión general que pueda determinar si un programa termina.

Resultados importantes

  • Tait demostró en 1967 queβ{\displaystyle \beta }-la reducción es fuertemente normalizadora . [ 10 ] Como corolarioβη{\displaystyle \beta \eta }La equivalencia es decidible . Statman demostró en 1979 que el problema de normalización no es elemental , [ 13 ] una demostración que posteriormente fue simplificada por Mairson. [ 14 ] Se sabe que el problema está en el conjuntomi4{\displaystyle {\mathcal {E}}^{4}}de la jerarquía de Grzegorczyk , [ 15 ] y más precisamente, es completa en la clase de complejidad llamada TOWER . [ 16 ] Berger y Schwichtenberg dieron una prueba de normalización puramente semántica (véase normalización por evaluación ) en 1991. [ 17 ]
  • El problema de la unificación paraβη{\displaystyle \beta \eta }La equivalencia es indecidible. Huet demostró en 1973 que la unificación de tercer orden es indecidible [ 18 ] , y esto fue mejorado por Baxter en 1978 [ 19 ] y luego por Goldfarb en 1981 [ 20 ] al demostrar que la unificación de segundo orden ya es indecidible. Colin Stirling anunció en 2006 una prueba de que el emparejamiento de orden superior (unificación donde solo un término contiene variables existenciales) es decidible, y se publicó una prueba completa en 2009. [ 21 ]
  • Podemos codificar los números naturales mediante términos del tipo(o→o)→(o→o){\displaystyle (o\to o)\to (o\to o)}( Números de la Iglesia ). Schwichtenberg demostró en 1975 que enλ→{\displaystyle \lambda ^{\to }}Exactamente los polinomios extendidos se pueden representar como funciones sobre numerales de Church; [ 22 ] estos son aproximadamente los polinomios cerrados bajo un operador condicional.
  • Un modelo completo deλ→{\displaystyle \lambda ^{\to }}se da interpretando los tipos base como conjuntos y los tipos de función por el espacio de funciones de la teoría de conjuntos . Friedman demostró en 1975 que esta interpretación es completa paraβη{\displaystyle \beta \eta }-equivalencia, si los tipos base se interpretan mediante conjuntos infinitos. [ 23 ] Statman demostró en 1983 queβη{\displaystyle \beta \eta }La -equivalencia es la equivalencia máxima que es típicamente ambigua , es decir cerrada bajo sustituciones de tipo ( Teorema de ambigüedad típica de Statman ). [ 24 ] Un corolario de esto es que se cumple la propiedad del modelo finito , es decir, los conjuntos finitos son suficientes para distinguir términos que no están identificados porβη{\displaystyle \beta \eta }-equivalencia.
  • Plotkin introdujo las relaciones lógicas en 1973 para caracterizar los elementos de un modelo que son definibles por términos lambda. [ 25 ] En 1993, Jung y Tiuryn ​​demostraron que una forma general de relación lógica (relaciones lógicas de Kripke con aridad variable) caracteriza exactamente la definibilidad lambda. [ 26 ] Plotkin y Statman conjeturaron que es decidible si un elemento dado de un modelo generado a partir de conjuntos finitos es definible por un término lambda ( conjetura de Plotkin-Statman ). Loader demostró que la conjetura era falsa en 2001. [ 27 ]

Notas

  1. ↑ Alonzo Church (1956) Introducción a la lógica matemática pp.47-68 [ 2 ]
  2. 1 2 Church 1940, p.57 denota variables con subíndices para su tipo:aα,bα,...zα,...a¯α,b¯α,...z¯α,...{\displaystyle a_{\alpha },b_{\alpha },...z_{\alpha },...{\bar {a}}_{\alpha },{\bar {b}}_{\alpha },...{\bar {z}}_{\alpha },...}[ 1 ]
  3. ↑ Church 1940, p.57: los símbolos primitivos 2º y 3º enumerados ( ) denotan alcance:λ,(,),norteoo,Aooo,Πo(oα),yoα(oα){\displaystyle \lambda ,(,),N_{oo},A_{ooo},\Pi _{o(o\alpha )},\iota _{\alpha (o\alpha )}}[ 1 ]
  4. 1 2 Iglesia 1940, pág. 60:norteoo,Aooo,Πo(oα),yoα(oα){\displaystyle N_{oo},A_{ooo},\Pi _{o(o\alpha )},\iota _{\alpha (o\alpha )}}son cuatro constantes que denotan respectivamente negación, disyunción, cuantificación universal y selección. [ 1 ]
  5. ^ Iglesia 1940, p.59 [ 1 ] Henkin 1949 p.160; [ 3 ] Henkin 1996 p.144 [ 4 ]
  6. ↑ Iglesia 1940, pág. 57 [ 1 ]
  7. ↑ Church 1940 p.58 enumera 24 fórmulas abreviadas. [ 1 ]
  8. ↑ Este artículo muestra a continuación 4 juicios de tipografía , en palabras.Γ{\displaystyle \Gamma }es el entorno de escritura . [ 5 ]
  9. ↑ El ' ⁠=β{\displaystyle =_{\beta }}⁠ ' denota el proceso de producir la sustitución de la expresión u por x, en la forma t.
  10. ↑ El ' ⁠=η{\displaystyle =_{\eta }}⁠ ' denota el proceso de producir la expansión de la forma t aplicada a x.
  1. 1 2 3 4 5 6 7 8 9 10 Church, Alonzo (junio de 1940). "Una formulación de la teoría simple de tipos" ( PDF) . Journal of Symbolic Logic . 5 (2): 56– 68. doi : 10.2307/2266170 . JSTOR 2266170. S2CID 15889861. Archivado del original (PDF) el 12 de enero de 2019.  
  2. ↑ Church, Alonzo (1956) Introducción a la lógica matemática
  3. 1 2 Leon Henkin (septiembre de 1949) La completitud del cálculo funcional de primer orden pág. 160
  4. 1 2 Leon Henkin (junio de 1996) El descubrimiento de mis pruebas de completitud
  5. ↑ Aprendizaje hedonista: aprender por el simple placer de hacerlo (Última actualización: 25 de noviembre de 2021, 14:00 UTC) Comprender los juicios de mecanografía
  6. ↑ Pfenning, Frank, Church y Curry: Combinando la tipificación intrínseca y extrínseca (PDF) , pág. 1 , consultado el 26 de febrero de 2022 
  7. ↑ Curry, Haskell B (1934-09-20). "Funcionalidad en lógica combinatoria" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 20 (11): 584– 90. Bibcode : 1934PNAS...20..584C . doi : 10.1073 / pnas.20.11.584 . ISSN 0027-8424 . PMC 1076489. PMID 16577644 .   (presenta una lógica combinatoria de tipo extrínseco, posteriormente adaptada por otros al cálculo lambda) [ 6 ]
  8. ↑ Reynolds, John (1998). Teorías de los lenguajes de programación . Cambridge, Inglaterra: Cambridge University Press. págs. 327, 334. ISBN  9780521594141.
  9. ↑ Norman Ramsey (Primavera de 2019) Estrategias de reducción para el cálculo lambda
  10. 1 2 3 Tait, WW (agosto de 1967). " Interpretaciones intensionales de funcionales de tipo finito I" . The Journal of Symbolic Logic . 32 (2): 198– 212. doi : 10.2307/2271658 . ISSN 0022-4812 . JSTOR 2271658. S2CID 9569863 .   
  11. ↑ Lambek, J. (1986). «Categorías cerradas cartesianas y λ-cálculos tipados» . Combinadores y lenguajes de programación funcional . Notas de clase en informática. Vol. 242. Springer. págs. 136–175 . doi : 10.1007/3-540-17184-3_44 . ISBN   978-3-540-47253-7.
  12. ↑ Dunfield, Jana; Krishnaswami, Neel (30 de junio de 2022). "Bidirectional Typing" . ACM Computing Surveys . 54 (5): 1– 38. arXiv : 1908.05839 . doi : 10.1145/3450952 . ISSN 0360-0300 . 
  13. ↑ Statman, Richard (1 de julio de 1979). "El cálculo λ tipado no es recursivo elemental" . Theoretical Computer Science . 9 (1): 73–81 . doi : 10.1016/0304-3975(79)90007-0 . hdl : 2027.42/23535 . ISSN 0304-3975 . 
  14. ↑ Mairson, Harry G. (14 de septiembre de 1992). "Una demostración simple de un teorema de Statman". Theoretical Computer Science . 103 (2): 387– 394. doi : 10.1016/0304-3975(92)90020-G . ISSN 0304-3975 . 
  15. ↑ Statman, Richard (julio de 1979). "El cálculo λ tipado no es recursivo elemental" . Theoretical Computer Science . 9 (1): 73–81 . doi : 10.1016/0304-3975(79)90007-0 . hdl : 2027.42/23535 . ISSN 0304-3975 . 
  16. ↑ Nguyên, Lê Thành Dũng (2024-09-05). "La convertibilidad simplemente tipada es TOWER-completa incluso para términos lambda seguros" . Métodos lógicos en informática . 20 (3) 11344. doi : 10.46298/lmcs-20(3:21)2024 . ISSN 1860-5974 . 
  17. ↑ Berger, U.; Schwichtenberg, H. (julio de 1991). "Una inversa del funcional de evaluación para el cálculo lambda tipado" . [ 1991 ] Actas del Sexto Simposio Anual del IEEE sobre Lógica en Ciencias de la Computación . págs. 203–211 . doi : 10.1109/LICS.1991.151645 . ISBN  0-8186-2230-X. S2CID 40441974 . 
  18. ↑ Huet, Gérard P. (1 de abril de 1973). "La indecidibilidad de la unificación en la lógica de tercer orden". Information and Control . 22 (3): 257– 267. doi : 10.1016/S0019-9958(73)90301-X . ISSN 0019-9958 . 
  19. ↑ Baxter, Lewis D. (1 de agosto de 1978). "La indecidibilidad del problema de unificación diádica de tercer orden" . Information and Control . 38 (2): 170– 178. doi : 10.1016/S0019-9958(78)90172-9 . ISSN 0019-9958 . 
  20. ↑ Goldfarb, Warren D. (1 de enero de 1981). "La indecidibilidad del problema de unificación de segundo orden". Theoretical Computer Science . 13 (2): 225– 230. doi : 10.1016/0304-3975(81)90040-2 . ISSN 0304-3975 . 
  21. ↑ Stirling, Colin (22 de julio de 2009). "Decidibilidad del emparejamiento de orden superior". Métodos lógicos en informática . 5 (3) 757: 1– 52. arXiv : 0907.3804 . doi : 10.2168/LMCS-5(3:2)2009 . S2CID 1478837 . 
  22. ^ Schwichtenberg, Helmut (1 de septiembre de 1975). "Definierbare Funktionen imλ-Kalkül mit Typen" . Archiv für mathematische Logik und Grundlagenforschung (en alemán). 17 (3): 113– 114. doi : 10.1007/BF02276799 . ISSN 1432-0665 . S2CID 11598130 .  
  23. ↑ Friedman, Harvey (1975). «Igualdad entre funcionales» . Coloquio de lógica . Notas de clase en matemáticas. Vol. 453. Springer. pp. 22–37 . doi : 10.1007/BFb0064870 . ISBN   978-3-540-07155-6.
  24. ↑ Statman, R. (1 de diciembre de 1983) .λ{\displaystyle \lambda }-funcionales definibles yβη{\displaystyle \beta \eta }conversión" . Archiv für mathematische Logik und Grundlagenforschung . 23 (1): 21– 26. doi : 10.1007/BF02023009 . ISSN 1432-0665 . S2CID 33920306 .  
  25. ↑ Plotkin, GD (1973). Lambda-definibilidad y relaciones lógicas (PDF) (Informe técnico). Universidad de Edimburgo . Recuperado el 30 de septiembre de 2022 .
  26. ↑ Jung, Achim; Tiuryn, Jerzy (1993). "Una nueva caracterización de la definibilidad lambda" . Cálculos lambda tipados y aplicaciones . Notas de clase en informática. Vol. 664. Springer. págs. 245–257 . doi : 10.1007/BFb0037110 . ISBN   3-540-56517-5.
  27. ↑ Loader, Ralph (2001). "La indecidibilidad de la λ-definibilidad" . Lógica, significado y computación . Springer Netherlands. págs. 331–342 . doi : 10.1007/978-94-010-0526-5_15 . ISBN  978-94-010-3891-1.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1351943962 "