O que codata, fluxo de controle e lógica nos ensinam sobre programação

Tabela de links

1. Introdução
2. Traduzindo -se ao cálculo seqüente

   2.1 Expressões aritméticas

   2.2 Deixe as ligações

   2.3 Definições de nível superior

   2.4 Dados algébricos e tipos de codata

   2.5 Funções de primeira classe

   2.6 Operadores de controle

3. Avaliação dentro de um contexto

   3.1 Contextos de avaliação para diversão

   3.2 foco na avaliação no núcleo

4. Regras de digitação

   4.1 Regras de digitação para diversão

   4.2 Regras de digitação para núcleo

   4.3 Tipo de solidez

5. Percepções

   5.1 Os contextos de avaliação são de primeira classe

   5.2 Os dados são duplos para codata

   5.3 Letrações são duplas para controlar os operadores

   5.4 A transformação de caso de caso

   5.5 Consumidores diretos e indiretos

   5.6 Callg-By-Value, Call-By-Name e Eta-Laws

   5.7 Lógica linear e a dualidade de exceções

6. Trabalho relacionado
7. Conclusão, declaração de disponibilidade de dados e reconhecimentos

A. A relação com o cálculo seqüente

B. Regras de digitação para diversão

C. Semântica operacional da etiqueta/goto

Referências

As idéias centrais dos cálculos que apresentamos nesta pérola não são novos: o cálculo “agora tem mais de 20 anos. Escolhemos uma variante desse cálculo que pode ser usada como ponto de partida para explorar todas as variantes que foram descritas na literatura. Portanto, esta seção de trabalho relacionada se destina a fornecer sugestões para leitura adicional e a chance de se aprofundar em tópicos específicos que apenas abordamos.

6.1 O cálculo seqüente

A base do nosso núcleo de idioma é um sistema de atribuição a termo para o cálculo seqüente, um sistema lógico alternativo à dedução natural. O cálculo seqüente foi originalmente introduzido por Gentzen nos artigos Gentzen [1935a,b, 1969]. Para uma introdução mais completa ao cálculo seqüente como um sistema lógico, podemos recomendar os livros de Negri e Von Platão [2001] e Troelstra e Schwichtenberg [2000] que introduzem o cálculo seqüente e mostram como ele difere dos sistemas de dedução natural que são mais comumente ensinados.

6.2 Termo atribuição para o cálculo seqüente

O artigo original que introduziu o 𝜆𝜇𝜇 𝜆𝜇𝜇 cálculo como um sistema de atribuição a termo para o cálculo seqüente foi por Curien e Herbelin [2000]. Antes de listarmos alguns dos outros artigos, devemos precedi -los com a seguinte observação sobre a notação:

” alt=”” aria-hidden=”true” />

As razões para essa divergência são facilmente explicadas. A notação de Curien e Herbelin [2000] Com seus dois contextos γ e δ ilustra perfeitamente a correspondência ao cálculo seqüente que opera com seqüentes γ ⊢ δ que contêm várias fórmulas no lado esquerdo e direito da catraca. Essa correspondência estreita ao cálculo seqüente é menos importante para nós. Descobrimos que dividir o contexto dessa maneira geralmente torna mais difícil anotar regras em toda a sua generalidade quando estendemos o idioma com outros recursos. Recursos que introduzem uma dependência de ligações posteriores sobre ligações anteriores em um contexto de digitação, por exemplo, quando adicionamos polimorfismo paramétrico, não se encaixam facilmente no formato de Curien e Herbelin [2000].

Com essas observações fora do caminho, podemos recomendar os artigos de Zeilberger [2008]Downen e Ariola [2014, 2018b, 2020]Munch-Maccagnoni [2009] e Spiwack [2014] que foram muito úteis para nós quando aprendemos sobre o cálculo.

6.3 Tipos de codata

Os tipos de codata foram originalmente inventados por Hagino [1989]. Eles tiveram o maior sucesso em assistentes de prova, como a AGDA, onde ajudam a contornar certos problemas técnicos que surgem quando tentamos modelar tipos coindutores. A correspondência copattern como uma maneira de criar produtores de tipos de codata foi popularizada por Abel et al. [2013]embora a idéia básica do conceito já existisse antes disso, veja, por exemplo, [Zeilberger 2008]. Mas provavelmente o melhor ponto de partida para saber mais sobre os tipos de codata é um artigo escrito por Downen et al. [2019].

6.4 Operadores de controle e lógica clássica

A gravadora/construto Goto que estamos usando em diversão é um exemplo de operador de controle, do qual o operador de Landin J J [Felleisen 1987; Landin 1965; Thielecke 1998] Provavelmente é o mais antigo. Sua tradução para os usos 𝜇-abstrações, que também são uma forma de operador de controle que foi originalmente introduzido por Parigot [1992] Antes de se tornar parte do 𝜆𝜇𝜇 𝜆𝜇𝜇 cálculo de Curien e Herbelin [2000]. Os operadores de controle têm uma relação importante com a lógica clássica através do isomorfismo de curry-howard. Este relacionamento foi descoberto por Griffin [1989]; Uma introdução mais completa pode ser encontrada em Sørensen e Urzyczyn [2006].

6.5 Pedidos de avaliação diferentes

Já conversamos sobre as estratégias de avaliação de maneira chamada e chamada por nome, e como a diferença deles pode ser explicada por diferentes opções de como um par crítico deve ser avaliado. Essa dualidade entre o valor de chamada e o nome de chamada já foi observado por Filinski [1989] e foi explorado em mais detalhes por Wadler [2003, 2005]. Também vimos na Seção 5.6 como 𝜂 Redução funciona apenas com tipos de dados em valor chamada e com tipos de codata em nome de chamada. Muitas pessoas concluem, portanto, que a escolha de uma ordem de avaliação talvez não seja uma decisão global, mas deva depender do tipo. Essa abordagem requer rastrear a polaridade dos tipos e o fornecimento de conectivos de turno adicionais que ajudam a mediar entre as diferentes ordens de avaliação; o artigo de Downen e Ariola [2018a] é um bom ponto de entrada para buscar esses tipos de perguntas que são discutidas em detalhes em [Zeilberger 2009] e [Munch-Maccagnoni 2013]. Um exemplo bem conhecido de mixagem de ordens de avaliação é o paradigma de chamada-pressionamento [Levy 1999] que distingue tipos de valor e computação e subumes, de chamada por valor e chamada por nome.

7 Conclusão

Nesta pérola funcional, apresentamos o cálculo da maneira como a apresentamos a nossos colegas e estudantes no quadro branco; compilando pequenos exemplos de programas funcionais.

Achamos que essa é uma maneira melhor de introduzir entusiastas e escritores de compiladores em linguagem de programação no 𝜆𝜇𝜇 𝜆𝜇𝜇 cálculo, pois isso não requer conhecimento prévio do cálculo seqüente. Também mostramos por que estamos entusiasmados com esse cálculo, dando exemplos de como ele nos permite expressar aspectos como avaliação estrita versus preguiçoso ou otimizações do compilador como o caso de caso de uma maneira extremamente clara. Queremos compartilhar nosso entusiasmo pelo cálculo e idiomas seqüentes construídos com mais pessoas e, com essa pérola, esperamos que outros comecem a escrever seus próprios pequenos compiladores no cálculo seqüente e explorar as possibilidades emocionantes que ele oferece.

Declaração de disponibilidade de dados

Este artigo é acompanhado por uma implementação em Haskell. Após a aceitação e publicação deste artigo, a implementação será disponibilizada permanentemente usando o Zenodo.

Agradecimentos

Gostaríamos de agradecer aos revisores anônimos e Paul Downen por seus comentários, o que nos ajudou muito a melhorar a apresentação final do artigo.