Tabela de links
- Introdução
- 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
- Avaliação dentro de um contexto
3.1 Contextos de avaliação para diversão
3.2 foco na avaliação no núcleo
- 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
- 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
- Trabalho relacionado
- 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
5.3 Letrações são duplas para controlar os operadores
O construto de etiqueta em diversão é traduzido para uma ligação 𝜇 no núcleo. Além disso, ao considerar a regra de digitação para o rótulo 𝛼 {𝑡} na Seção 4.1, podemos ver que ela corresponde diretamente à digitação de uma ligação com o rótulo 𝛼 sendo a covariável ligada. Da mesma forma, uma ligação é traduzida para uma ligação e digitar uma ligação de letra, corresponde de perto à digitação de um termo no núcleo. Dessa forma, rótulos e letragens são duplos um para o outro, da mesma maneira 𝜇 e 𝜇𝜇. A dualidade pode ser estendida a outros operadores de controle, como chamada/CC.
Como se vê, o construto de etiquetas está intimamente relacionado à chamada/CC. Na verdade, existem apenas duas diferenças. Primeiro, a etiqueta 𝛼 {𝑡} tem o fichário 𝛼 para a continuação incorporada no construto, assim como a variação de chamada/cc denominada Let/CC (que Reynolds [1972] chamado escape). A segunda e mais importante diferença é que a invocação da continuação capturada pelo rótulo 𝛼 {𝑡} acontece através de um grupo de linguagem explícito Goto (𝑡; 𝛼). Isso facilita a tradução do núcleo, pois podemos simplesmente inserir outra ligação para descartar a continuação restante exatamente no local onde a continuação capturada é invocada. Por outro lado, com chamadas/CC e LET/CC, a continuação é aplicada da mesma maneira que uma função normal, tornando necessário redefinir a variável que a continuação capturada está ligada ao traduzir para o núcleo. Isso obscurece a dualidade para letrações que são tão evidentes para o rótulo e o Goto.
Para ver isso, aqui está uma tradução de let/cc 𝑘 𝑡 para o núcleo
[let/cc 𝑘 𝑡] ≔ 𝜇𝛼.⟨cocase {AP (𝑥, 𝛽) ⇒ ⟨𝑥 | 𝛼⟩} | 𝜇𝑘. ˜ ⟨[𝑡] | 𝛼⟩⟩
A essência da tradução ainda é que a continuação atual é capturada pela externa 𝜇 e ligada a 𝛼. Mas agora também temos que transformar esse 𝛼 em uma função (o cocase aqui) que descarta seu contexto (aqui ligado a 𝛽) e liga essa função a 𝑘, o que é feito usando 𝜇𝜇. Para chamada/CC, a dualidade é ainda mais obscurecida, pois o aglutinante para a continuação está oculto na função a que a chamada/CC é aplicada. Para a tradução, essa função deve ser aplicada ao cocase acima e à continuação capturada 𝛼, resultando no período seguinte (cf. também [Miquey 2019]).
[call/cc 𝑓] ≔ 𝜇𝛼.⟨[𝑓 ] | AP (cocase {AP (𝑥, 𝛽) ⇒ ⟨𝑥 | 𝛼⟩}, 𝛼)⟩
Outros operadores de controle para continuações não eliminados podem ser traduzidos de maneira semelhante. Por exemplo, considere C de Felleisen [Felleisen et al. 1987]. A diferença para ligar/CC é que C descarta a continuação atual se não for invocada em algum lugar do termo c, enquanto a chamada/CC a deixa no lugar e, portanto, se comporta como um não-Op se a continuação capturada nunca for invocada. A única mudança que precisa ser feita na tradução para o núcleo é que a continuação de nível superior ⋆ deve ser usada para o corte externo em vez de usar a continuação capturada. Isso é mais facilmente visto para uma variação de C, que tem o aglutinante para a continuação incorporada no operador e onde a invocação da continuação é explícita, semelhante à etiqueta/goto. Chamando esta etiqueta de variação, obtemos a seguinte tradução
[labelC 𝛼 {𝑡 }] ≔ 𝜇𝛼.⟨[𝑡] | ⋆⟩
Aqui, a dualidade para letrações é evidente novamente. A tradução para C em si é então obtida da mesma maneira que para Call/CC
[C 𝑓 ] ≔ 𝜇𝛼.⟨[𝑓 ] | AP (cocase {AP (𝑥, 𝛽) ⇒ ⟨𝑥 | 𝛼⟩}, ⋆)⟩
5.4 A transformação de caso de caso
Uma transformação importante nos compiladores funcionais é a transformação de caso de caso. Maurer et al. [2017] Dê o seguinte exemplo dessa transformação. O termo
se (se 𝑒1 então 𝑒2 outro 𝑒3) então 𝑒4 outro 𝑒5
pode ser substituído pelo termo
se 𝑒1 então (se 𝑒2 então 𝑒4 outro 𝑒5) outro (se 𝑒3 então 𝑒4 outro 𝑒5).
Os lógicos chamam esses tipos de conversões comutativas de transformações e desempenham um papel importante no estudo do cálculo seqüente. Mas como Maurer et al. [2017] Mostrar, eles também são importantes para os escritores do compilador que desejam gerar código eficiente.
No cálculo, as conversões de deslocação não precisam ser implementadas como um passe especial do compilador. Eles caem de graça como uma instância especial de Reductions! Vamos ilustrar esse ponto, traduzindo o exemplo de Maurer et al. Para o cálculo 𝜆𝜇𝜇 cálculo. Primeiro, vamos traduzir os dois exemplos usando a sintaxe de correspondência de padrões:
Vamos agora traduzir esses dois termos no 𝜆𝜇𝜇 𝜆𝜇𝜇 cálculo:
Podemos ver que, apenas reduzindo todos os Redexes sublinhados, reduzimos esses dois exemplos para o mesmo termo.
Autores:
(1) David Binder, Universidade de Tübingen, Alemanha;
(2) Marco Tzschentke, Universidade de Tübingen, Alemanha;
(3) Marius Muller, Universidade de Tübingen, Alemanha;
(4) Klaus Ostermann, Universidade de Tübingen, Alemanha.
