Lo que Codata, Management Stream y Logic nos enseñan sobre la programación

Tabla de enlaces

1. Introducción

2. Traduciendo al cálculo secuente

   2.1 Expresiones aritméticas

   2.2 Leting Bindings

   2.3 Definiciones de nivel superior

   2.4 Datos algebraicos y tipos de Codata

   2.5 Funciones de primera clase

   2.6 Operadores de management

3. Evaluación dentro de un contexto

   3.1 Contextos de evaluación para la diversión

   3.2 Centrarse en la evaluación en el núcleo

4. Reglas de escritura

   4.1 Reglas de escritura para la diversión

   4.2 Reglas de escritura para el núcleo

   4.3 Tipo de solidez

5. Perspectivas

   5.1 Los contextos de evaluación son de primera clase

   5.2 Los datos son duales a Codata

   5.3 Los vínculos de alquiler son duales para los operadores de management

   5.4 La transformación del caso del caso

   5.5 consumidores directos e indirectos

   5.6 Llamado por valor, llamado por nombre y eta-laws

   5.7 Lógica lineal y la dualidad de las excepciones

6. Trabajo relacionado

7. Conclusión, declaración de disponibilidad de datos y reconocimientos

A. La relación con el cálculo secuente

B. Reglas de escritura para la diversión

C. Semántica operativa de la etiqueta/goto

Referencias

Las concepts centrales de los cálculos que hemos presentado en esta perla no son novedosas: el 𝜆𝜇𝜇 así calculus tiene más de 20 años. Elegimos una variante de este cálculo que puede usarse como punto de partida para explorar todas las variantes que se han descrito en la literatura. Por lo tanto, esta sección de trabajo relacionada tiene la intención de proporcionar sugerencias para una mayor lectura y la oportunidad de profundizar en temas específicos que solo hemos mencionado.

6.1 El cálculo secuente

La base de nuestro núcleo del lenguaje es un sistema de asignación de términos para el cálculo secuente, un sistema lógico alternativo a la deducción pure. El cálculo secuente fue introducido originalmente por Gentzen en los artículos gentzen [1935a,b, 1969]. Para una introducción más exhaustiva al cálculo secuente como un sistema lógico, podemos recomendar los libros de Negri y Von Platón [2001] y Troelstra y Schwichtenberg [2000] que introducen el cálculo secuente y muestran cómo difiere de los sistemas de deducción pure que se enseñan más comúnmente.

6.2 Asignación de plazo para el cálculo secuente

El artículo authentic que introdujo el 𝜆𝜇𝜇 Mi-Calculus como un sistema de asignación de término para el cálculo secuente fue de Curien y Herbelin [2000]. Antes de enumerar algunos de los otros artículos, debemos prefacionarlos con el siguiente comentario sobre la notación:

Las razones de esta divergencia se explican fácilmente. La notación de Curien y Herbelin [2000] Con sus dos contextos γ y δ, ilustra perfectamente la correspondencia al cálculo secuente que funciona con secuentes γ ⊢ δ que contienen múltiples fórmulas en el lado izquierdo y derecho del torniquete. Esta correspondencia cercana al cálculo secuente es menos importante para nosotros. Descubrimos que dividir el contexto de esta manera a menudo hace que sea más difícil anotar reglas en su basic Generality cuando extendemos el lenguaje con otras características. Características que introducen una dependencia de enlaces posteriores en enlaces anteriores dentro de un contexto de tipificación, por ejemplo, cuando agregamos polimorfismo paramétrico, no encajen fácilmente en el formato de Curien y Herbelin [2000].

Con estos comentarios fuera del camino, podemos recomendar los artículos de Zeilberger [2008]Downen y Ariola [2014, 2018b, 2020]Munch-Maccagnoni [2009] y spiwack [2014] que nos fueron muy útiles cuando aprendimos sobre el 𝜆𝜇𝜇 Mi-Calculus.

6.3 tipos de codata

Los tipos de codata fueron inventados originalmente por Hagino [1989]. Tuvieron el mayor éxito en asistentes de prueba como AGDA, donde ayudan a eludir ciertos problemas técnicos que surgen cuando intentamos modelar tipos de coincripción. La coincidencia de copatrón como una forma de crear productores de tipos de Codata fue popularizada por Abel et al. [2013]aunque la thought básica del concepto había existido antes de eso, ver, por ejemplo, [Zeilberger 2008]. Pero probablemente el mejor punto de partida para obtener más información sobre los tipos de Codata es un artículo escrito por Downen et al. [2019].

6.4 Operadores de management y lógica clásica

La construcción de etiquetas/goto que estamos usando en diversión es un ejemplo de un operador de management, de los cuales el operador de Landin J J [Felleisen 1987; Landin 1965; Thielecke 1998] Probablemente sea el más antiguo. Su traducción al núcleo usa 𝜇-abstracciones, que también son una forma de operador de management que originalmente fue introducido por Parigot [1992] Antes de que se convirtiera en parte del 𝜆𝜇𝜇 Mi-Calculus de Curien y Herbelin [2000]. Los operadores de management tienen una relación importante con la lógica clásica a través del isomorfismo de curry-howard. Esta relación fue descubierta por Griffin [1989]; Se puede encontrar una introducción más exhaustiva en Sørensen y Urzyczyn [2006].

6.5 órdenes de evaluación diferentes

Ya hemos hablado sobre las estrategias de evaluación llamadas por valor y llamado por nombre, y cómo su diferencia puede explicarse por diferentes opciones de cómo se debe evaluar un par crítico. Filinski ya ha observado esta dualidad entre llamadas por valor y llamado por nombre [1989] y ha sido explorado con más detalle por Wadler [2003, 2005]. También hemos visto en la sección 5.6 cómo 𝜂-reducción solo funciona con tipos de datos en valor de llamada y con tipos de Codata en llamadas por nombre. Por lo tanto, muchas personas concluyen que la elección de una orden de evaluación tal vez no debería ser una decisión international, sino que debería depender del tipo. Este enfoque requiere rastrear la polaridad de los tipos y proporcionar conectivos de cambio adicionales que ayudan a mediar entre las diferentes órdenes de evaluación; El artículo de Downen y Ariola [2018a] es un buen punto de entrada para perseguir este tipo de preguntas que se discuten en detalle en [Zeilberger 2009] y [Munch-Maccagnoni 2013]. Un ejemplo bien conocido de la mezcla de órdenes de evaluación es el paradigma de valor de valor llamado [Levy 1999] que distingue los tipos de valor y los tipos de cálculo y subsume tanto llamado por valor y llamado por nombre.

7 conclusión

En esta perla funcional, hemos presentado el 𝜆𝜇𝜇˜calculus en la forma en que lo presentamos a nuestros colegas y estudiantes en la pizarra; compilando pequeños ejemplos de programas funcionales.

Creemos que esta es una mejor manera de introducir entusiastas del idioma de programación y escritores de compiladores en el 𝜆𝜇𝜇 Mi-Calculus, ya que no requiere un conocimiento previo del cálculo secuente. También hemos demostrado por qué estamos entusiasmados con este cálculo, dando ejemplos de cómo nos permite expresar aspectos como la evaluación estricta frente a la floja o las optimizaciones de compiladores como el caso de caso de una manera extremadamente clara. Queremos compartir nuestro entusiasmo por el cálculo y los idiomas secuenciales construidos sobre él con más personas, y con esta perla, esperamos que otros comiencen a escribir sus propios pequeños compiladores en el cálculo secuente y explorar las emocionantes posibilidades que ofrece.

Declaración de disponibilidad de datos

Este documento se acompaña de una implementación en Haskell. Tras la aceptación y publicación de este artículo, la implementación estará disponible permanentemente utilizando Zenodo.

Expresiones de gratitud

Nos gustaría agradecer a los revisores anónimos y a Paul Downen por sus comentarios, lo que nos ayudó enormemente a mejorar la presentación closing del documento.