Pregunta "¿Qué parte de Hindley-Milner no entiendes?"


yo jurar solía haber una camiseta en venta con las palabras inmortales:


Que parte de

Hindley-Milner

Vos si no ¿entender?


En mi caso, la respuesta sería ... ¡todo!

En particular, a menudo veo una notación como esta en los documentos de Haskell, pero no tengo ni idea de qué significa eso. No tengo idea de qué rama de las matemáticas se supone que es.

Reconozco las letras del alfabeto griego, por supuesto, y símbolos como "∉" (que generalmente significa que algo no es un elemento de un conjunto).

Por otro lado, nunca he visto "⊢" antes (Wikipedia afirma que podría significar "partición") Tampoco estoy familiarizado con el uso del vinculum aquí. (Por lo general, denota una fracción, pero eso no Aparecer para ser el caso aquí.)

Si alguien al menos pudiera decirme por dónde empezar a buscar para comprender qué significa este mar de símbolos, sería útil.


750
2017-09-21 14:29


origen


Respuestas:


  • los barra horizontal significa que "[arriba] implica [abajo]".
  • Si hay expresiones múltiples en [arriba], luego considérelos anded juntos; todo lo [arriba] debe ser verdadero para garantizar el [abajo].
  • : medio tiene tipo
  •  medio es en. (Igualmente  significa "no está en").
  • Γ generalmente se usa para referirse a ambiente o contexto; en este caso, se puede considerar como un conjunto de anotaciones de tipo, emparejando un identificador con su tipo. Por lo tanto x : σ ∈ Γ significa que el medio ambiente Γ incluye el hecho de que x tiene tipo σ.
  •  puede leerse como demuestra o determina. Γ ⊢ x : σ significa que el medio ambiente Γ determina que x tiene tipo σ.
  • , es una forma de incluso suposiciones adicionales específicas en un ambiente Γ.
    Por lo tanto, Γ, x : τ ⊢ e : τ' significa que el medio ambiente Γ, con la suposición adicional y primordial de que x tiene tipo τ, demuestra que e tiene tipo τ'.

560
2017-09-21 17:28



Esta sintaxis, si bien puede parecer complicada, es bastante simple. La idea básica proviene de la lógica: la expresión completa es una implicación, siendo la mitad superior las suposiciones y la mitad inferior el resultado. Es decir, si sabes que las expresiones principales son verdaderas, puedes concluir que las expresiones de abajo también son verdaderas.

Símbolos

Otra cosa a tener en cuenta es que algunas letras tienen significados tradicionales; particularmente, Γ representa el "contexto" en el que se encuentra, es decir, los tipos de otras cosas que ha visto. Así que algo así como Γ ⊢ ... significa "la expresión ... cuando conoces los tipos de cada expresión en Γ.

los  símbolo esencialmente significa que puedes probar algo. Asi que Γ ⊢ ... es una declaración que dice "Puedo probar ... en un contexto Γ. Estas declaraciones también se llaman juicios de tipo.

Otra cosa a tener en cuenta: en matemáticas, al igual que ML y Scala, x : σ significa que x tiene tipo σ. Puedes leerlo como Haskell's x :: σ.

Qué significa cada regla

Entonces, sabiendo esto, la primera expresión se vuelve fácil de entender: si sabemos eso x : σ ∈ Γ (es decir, x tiene algún tipo σ en algún contexto Γ), entonces sabemos que Γ ⊢ x : σ (es decir, en Γ, x tiene tipo σ) Entonces, realmente, esto no te dice nada súper interesante; simplemente te dice cómo usar tu contexto.

Las otras reglas también son simples. Por ejemplo, tomar [App]. Esta regla tiene dos condiciones: e₀ es una función de algún tipo τ a algún tipo τ' y e₁ es un valor de tipo τ. Ahora sabes qué tipo obtendrás al aplicar e₀ a e₁! Espero que esto no sea una sorpresa :).

La siguiente regla tiene una sintaxis más nueva. Particularmente, Γ, x : τ solo significa el contexto compuesto por Γ y el juicio x : τ. Entonces, si sabemos que la variable x tiene un tipo de τ y la expresión e tiene un tipo τ', también sabemos el tipo de función que toma x y devoluciones e. Esto solo nos dice qué hacer si hemos descubierto qué tipo de una función toma y qué tipo devuelve, por lo que tampoco debería sorprendernos.

El siguiente solo te dice cómo manejarlo let declaraciones. Si sabes que alguna expresión e₁ tiene un tipo τ Mientras x tiene un tipo σ, Entonces un let expresión que se une localmente x a un valor de tipo σ hará e₁ tener un tipo τ. En realidad, esto solo te dice que una declaración de let esencialmente te permite expandir el contexto con un nuevo enlace, que es exactamente lo que let ¡hace!

los [Inst] la regla se refiere a subtipos. Dice que si tienes un valor de tipo σ' y es un subtipo de σ ( representa una relación de ordenamiento parcial) entonces esa expresión es además de tipo σ.

La regla final se refiere a generalizar tipos. Un resumen rápido: una variable libre es una variable que no es introducida por un enunciado let o lambda dentro de alguna expresión; esta expresión ahora depende del valor de la variable libre de su contexto. La regla dice que si hay alguna variable α cual es no "libre" en cualquier cosa en tu contexto, entonces es seguro decir que cualquier expresión cuyo tipo conozcas e : σ tendrá ese tipo de alguna valor de α.

Cómo usar las reglas

Entonces, ahora que entiendes los símbolos, ¿qué haces con estas reglas? Bueno, puedes usar estas reglas para descubrir el tipo de varios valores. Para hacer esto, mira tu expresión (por ejemplo f x y) y encuentre una regla que tenga una conclusión (la parte inferior) que coincida con su declaración. Llamemos a lo que está tratando de encontrar su "objetivo". En este caso, miraría la regla que termina en e₀ e₁. Cuando haya encontrado esto, ahora debe encontrar reglas que demuestren todo lo que está por encima de la línea de esta regla. Estas cosas generalmente corresponden a los tipos de subexpresiones, por lo que esencialmente estás recurriendo a partes de la expresión. Simplemente haz esto hasta que termines tu árbol de pruebas, que te da una prueba del tipo de tu expresión.

Lo que todas estas reglas hacen es especificar exactamente -y en el detalle matemáticamente pedante habitual: P- cómo descubrir los tipos de expresiones.

Ahora, esto te suena familiar si alguna vez has usado Prolog; estás básicamente computando el árbol de pruebas como un intérprete humano de Prolog. ¡Existe una razón por la cual Prolog se llama "programación lógica"! Esto también es importante ya que la primera forma en que se me presentó el algoritmo de inferencia H-M fue implementándolo en Prolog. Esto es sorprendentemente simple y hace que lo que está pasando sea claro. Sin duda debes probarlo.

Nota: Probablemente cometí algunos errores en esta explicación y me encantaría que alguien los señale. De hecho, voy a cubrir esto en clase en un par de semanas, así que tendré más confianza en ese momento: P.


301
2017-09-21 16:49



si alguien al menos podría decirme dónde empezar a buscar para comprender lo que significa este mar de símbolos

Ver "Fundamentos prácticos de los lenguajes de programación.", capítulos 2 y 3, sobre el estilo de la lógica a través de juicios y derivaciones. Todo el libro es ahora disponible en Amazon.

Capitulo 2

Definiciones inductivas

Las definiciones inductivas son una herramienta indispensable en el estudio de los lenguajes de programación. En este capítulo desarrollaremos el marco básico de las definiciones inductivas y daremos algunos ejemplos de su uso. Una definición inductiva consiste en un conjunto de reglas para derivar juicios, o aserciones, de una variedad de formas. Los juicios son declaraciones sobre uno o más objetos sintácticos de un tipo específico. Las reglas especifican condiciones necesarias y suficientes para la validez de un juicio y, por lo tanto, determinan completamente su significado.

2.1 Sentencias

Comenzamos con la noción de un juicio, o afirmación sobre un objeto sintáctico. Haremos uso de muchas formas de juicio, incluidos ejemplos como estos:

  • norte  nat - norte es un número natural
  • norte = n1 + n2 - norte es la suma de n1 y n2
  • τ  tipo - τ es un tipo
  • mi : τ - expresión mi tiene tipo τ
  • mi ⇓ v - expresión mi tiene valor v

Una sentencia establece que uno o más objetos sintácticos tienen una propiedad o una relación mutua. La propiedad o relación en sí misma se llama forma de juicio, y el juicio de que un objeto u objetos tienen esa propiedad o están en esa relación se dice que es un ejemplo de esa forma de juicio. Una forma de juicio también se llama predicado, y los objetos que constituyen una instancia son asignaturas. Nosotros escribimos un  J para el juicio que afirma que J sostiene de un. Cuando no es importante enfatizar el tema del juicio, (el texto corta aquí)


69
2017-09-21 15:24



La notación proviene de deducción natural.

⊢ se llama símbolo torniquete.

Las 6 reglas son muy fáciles.

Var la regla es una regla bastante trivial: dice que si el tipo de identificador ya está presente en su entorno de tipo, entonces para inferir el tipo, simplemente lo toma del entorno tal como está.

App regla dice que si tienes dos identificadores e0 y e1 y puede inferir sus tipos, entonces puede inferir el tipo de aplicación e0 e1. La regla dice así si sabes eso e0 :: t0 -> t1 y e1 :: t0 (¡el mismo t0!), entonces la aplicación está bien tipada y el tipo es t1.

Abs y Let son reglas para inferir tipos para lambda-abstracción y let-in.

Inst La regla dice que puedes sustituir un tipo con uno menos general.


44
2017-09-21 16:21



¿Cómo entiendo las reglas de Hindley-Milner?

Hindley-Milner es un conjunto de reglas en forma de cálculo secuencial (no deducción natural) que dice que puede deducir el tipo (más general) de un programa de la construcción del programa sin declaraciones explícitas de tipo.

Los símbolos y la notación

Primero, expliquemos los símbolos

  • 𝑥 es un identificador (informalmente, un nombre de variable).
  • : means es un tipo de (informalmente, una instancia de, o "is-a").
  • σ (sigma) es una expresión que es una variable o función.
  • ∈ significa que es un elemento de
  • Γ (Gamma) es un ambiente.
  •  (el signo de aserción) significa afirma (o lo demuestra, pero contextualmente "afirma" se lee mejor)
  • Γ⊦ 𝑥  :  σ se lee así Γ afirma 𝑥, una σ
  • 𝑒 es una instancia real (elemento) de tipo σ.
  • τ (tau) es un tipo: básico, variable (α), funcional τ → τ 'o producto τ × τ '
  • τ → τ ' es un tipo funcional donde τ y τ ' son tipos.
  • λ𝑥.𝑒 medio λ (lambda) es una función anónima que toma una discusión, 𝑥y devuelve una expresión 𝑒.
  • dejar  𝑥  = 𝑒₀  en  𝑒₁ significa en expresión, 𝑒₁, sustituto 𝑒₀ donde quiera 𝑥 aparece.
  •  significa que el elemento anterior es un subtipo (informalmente - subclase) de este último elemento.
  • α es una variable de tipo.
  • α.σ es un tipo, ∀ (para todas) las variables de argumento, αregresando σ expresión
  • gratis (Γ) significa que no es un elemento de las variables de tipo libre de Γ definidas en el contexto externo. (Las variables enlazadas son sustituibles.)

Todo sobre la línea es la premisa, todo lo que sigue es la conclusión (Per Martin-Löf)

Lo que sigue aquí son interpretaciones en inglés de las declaraciones lógicas, seguidas de una explicación.

Variable

VAR Logic Diagram

Dado 𝑥 es un tipo de σ (sigma), un elemento de Γ (Gamma),
concluir Γ afirma 𝑥 es un σ.

Esto es básicamente una tautología: un nombre de identificación es una variable o una función.

Aplicación de función

APP Logic Diagram

Dado Γ afirma 𝑒₀ es un tipo funcional y Γ afirma 𝑒₁ es un τ
concluir Γ afirma que aplicar la función 𝑒₀ a 𝑒₁ es un tipo τ '

Esto significa que si sabemos que una función devuelve un tipo y lo aplicamos a un argumento, el resultado será una instancia del tipo que sabemos que devuelve.

Abstracción de funciones

ABS Logic Diagram

Dado Γ y 𝑥 del tipo τ afirma 𝑒 es un tipo, τ '
concluir Γ afirma una función anónima, λ de 𝑥 expresión de retorno, 𝑒 es de tipo τ → τ '.

Esto significa que si sabemos que 𝑥 es de tipo τ y, por lo tanto, una expresión 𝑒 es de tipo τ ', entonces una función de 𝑥 expresión regresiva 𝑒 es de tipo τ → τ'.

Deje la declaración variable

LET Logic Diagram

Dado Γ afirma 𝑒₀, de tipo σ, y Γ y 𝑥, de tipo σ, afirma 𝑒₁ de tipo τ
concluir Γ afirma let 𝑥 = 𝑒₀ in 𝑒₁ de tipo τ

Esto significa que si tenemos una expresión 𝑒₀ que es un σ (que es una variable o una función), y algún nombre, 𝑥, también un σ, y una expresión 𝑒₁ de tipo τ, entonces podemos sustituir 𝑒₀ por 𝑥 cada vez que aparezca dentro de 𝑒₁.

Instanciación

INST Logic Diagram

Dado Γ afirma 𝑒 del tipo σ 'y σ' es un subtipo de σ '
concluir Γ afirma 𝑒 es de tipo σ

Esto significa que si una instancia es de un tipo que es un subtipo de otro tipo, también es una instancia de ese super-tipo.

Esto nos permite usar la instanciación de tipo en el sentido más general de que una expresión puede devolver un tipo más específico.

Generalización

GEN Logic Diagram

Dado Γ afirma 𝑒 es un σ y α no es un elemento de las variables libres de Γ,
concluir Γ afirma 𝑒, escribe para todas las expresiones de argumento α devolviendo una expresión σ

Esto significa que podemos generalizar un programa para aceptar todos los tipos de argumentos que no estén ya vinculados en el ámbito que los contiene (variables que no son locales). Estas variables vinculadas son sustituibles.

Conclusión

Estas reglas combinadas nos permiten probar el tipo más general de un programa afirmado, sin necesidad de anotaciones de tipo, lo que permite que varios tipos se acepten correctamente como entrada (polimorfismo paramétrico).


23
2018-02-03 23:01



Hay dos formas de pensar en e: σ. Uno es "la expresión e tiene tipo σ", otro es "el par ordenado de la expresión ey el tipo σ".

Ver Γ como el conocimiento sobre los tipos de expresiones, implementado como un conjunto de pares de expresiones y tipos, e: σ.

El torniquete ⊢ significa que del conocimiento de la izquierda, podemos deducir lo que está a la derecha.

La primera regla [Var] se puede leer así:
Si nuestro conocimiento Γ contiene el par e: σ, entonces podemos deducir de Γ que e tiene tipo σ.

La segunda regla [Aplicación] se puede leer:
Si desde Γ podemos deducir que e_0 tiene el tipo τ → τ ', y nosotros desde Γ podemos deducir que e_1 tiene el tipo τ, entonces nosotros desde Γ podemos deducir que e_0 e_1 tiene el tipo τ'.

Es común escribir Γ, e: σ en lugar de Γ ∪ {e: σ}.

La tercera regla [Abs] se puede leer así:
Si desde Γ extendido con x: τ puede deducir que e tiene el tipo τ ', entonces desde Γ podemos deducir que λx.e tiene el tipo τ → τ.

La cuarta regla [Let] se deja como un ejercicio. :-)

La quinta regla [Inst] se puede leer:
Si desde Γ podemos deducir que e tiene el tipo σ ', y σ' es un subtipo de σ, entonces nosotros desde Γ podemos deducir que e tiene el tipo σ.

La sexta y última regla [Gen] puede leerse:
Si desde Γ podemos deducir que e tiene el tipo σ, y α no es una variable de tipo libre en ninguno de los tipos en Γ, entonces desde Γ podemos deducir que e tiene el tipo ∀α σ.


16
2018-04-25 14:55