Sobre o projeto
Na primavera de 2020, como parte da prática da primavera no Centro de Ciência da Computação, eu estava desenvolvendo um novo design para a linguagem de programação OCaml sob a orientação estrita de Dmitry Kosarev .
Por que OCaml
OCaml é uma das implementações mais bem-sucedidas e desenvolvidas de sincretismo de programação industrial (portanto, multi-paradigma, multi-plataforma, compilador muito rápido, alta produtividade de código gerado) e matemática (daí o sistema de tipo de última geração com uma implementação poderosa de inferência de tipo, expressividade e extensibilidade linguagem, proximidade com notação matemática e semântica).
Ao mesmo tempo, a comunidade lingüística é muito seletiva e lentamente adiciona à língua apenas construções altamente exigidas, desde que não introduzam restrições à língua existente. Portanto, o núcleo da linguagem é muito pequeno e intuitivo, e OCaml é usado com prazer por desenvolvedores industriais e, digamos, matemáticos do Departamento de Álgebra Superior e Teoria dos Números da Universidade Estadual de São Petersburgo .
Para um mergulho mais profundo no tópico, sugiro dar uma olhada nos artigos OCaml para as massas e Por que OCaml .
Atualmente, estão em curso trabalhos para implementar um sistema multicore para OCaml, aliado a efeitos algébricos, que irão simultaneamente aumentar o desempenho geral da linguagem e eliminar as limitações existentes do sistema de tipos associadas ao facto de a linguagem permitir cálculos impuros.
Correspondência de padrões e padrões ativos
Meu trabalho se concentrou principalmente na construção de correspondência de padrões, amplamente usada em linguagens de programação funcionais.
Para ilustrar, considere um exemplo simples de rotação de um nó em uma árvore binária. No estilo imperativo mais comum, o código provavelmente seria assim:

type 'a tree =
| Node of 'a tree * 'a * 'a tree
| Nil
let rotate_left' t =
if is_node t
then
let a = get_left t in
let p = get_value t in
let r = get_right t in
if is_node r
then
let b = get_left t in
let q = get_value t in
let c = get_right t in
Node(Node(a,p,b),q,c)
else t
else t
E aqui está exatamente o mesmo código escrito usando a construção de correspondência de padrões:
let rotate_left = function
| Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
| Node _ | Nil as x -> x
Ao usar este design, temos as seguintes vantagens:
- alta expressividade;
- verificação de integridade , que é uma propriedade crítica para verificação de exatidão e refatoração de programa;
- esquemas de compilação eficientes.
A verificação de integridade significa que o compilador, conhecendo a definição de tipo, pode verificar para cada correspondência se é verdade que todas as alternativas possíveis foram analisadas e que não há ramificações inacessíveis, não importa o quão complexas as amostras e não importa como elas se cruzam umas com as outras. Portanto, se você alterar a definição de tipo (adicionar novas alternativas, remover ou alterar as existentes), o compilador gentilmente fornecerá todos os locais no código que foram diretamente afetados.
Por exemplo, se eu adicionar novas construções à árvore sintática, o compilador me mostrará o código de digitação AST até o corpo da função, onde preciso escrever o código de digitação para novas construções:

Esta propriedade torna o OCaml muito resistente à refatoração e outras alterações de código.
Apesar de todas as vantagens descritas, existe também uma limitação muito séria na aplicabilidade. Você percebeu isso? A definição do tipo deve ser pública (para que o compilador possa mostrar as alternativas que a compõem). E isso, é claro, quebra imediatamente até as abstrações mais simples. Por exemplo, se quisermos definir a interface de lista mais simples, é impossível dizer com antecedência qual definição de tipo exportar:
module type List = sig
type 'a t (* = ? *)
val cons: 'a -> 'a t -> 'a t
val empty: 'a t
val head: 'a t -> ('a * 'a t) option
end
No entanto, esse problema não é fundamental e, como observado em 1987, é possível obter correspondência de padrões em tipos abstratos.
Formulação do problema
Desde 1987, muitos projetos diferentes foram apresentados na literatura para resolver o problema, aqui estão apenas alguns deles:

No início do projeto, o trabalho já havia sido feito em uma escolha razoável e objetiva de uma solução específica para implementação , a mais vantajosa era a extensão de padrões ativos implementada na linguagem F #.
O objetivo do projeto era começar a implementar Padrões Ativos para o compilador OCaml e progredir o máximo possível.
Padrões ativos
A própria ideia de padrões ativos (bem como extensões semelhantes) é muito simples: uma vez que a abstração é alcançada ocultando a implementação dentro da função, é necessário permitir uma chamada para uma função dentro da correspondência de padrões que converteria o valor desconhecido do tipo de dados abstrato em uma lista conhecida de alternativas. Os padrões ativos codificam essa lista de alternativas dentro do nome da função. Portanto, na interface da lista acima, você precisa adicionar a seguinte função
(|Cons|Nil|)
:
module type List = sig
type 'a t
val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
val cons: 'a -> 'a t -> 'a t
val empty: 'a t
val head: 'a t -> ('a * 'a t) option
end
O resultado é um tipo de soma anônima
choice2
que tem a seguinte definição (existem tipos semelhantes gerados até choice32
):
type ('a, 'b) choice2 =
| Choice2_1 of 'a
| Choice2_2 of 'b
Assim, a função
(|Cons|Nil|)
irá converter a lista para uma de duas alternativas: ou para um par de início e fim da lista, ou para uma alternativa vazia, significando que a lista estava vazia.
Definir tal função para uma lista padrão é trivial e ficaria assim:
let (|Cons|Nil|) = function
| [] -> Nil
| x :: xs -> Cons(x, xs)
Como exemplo de uso, considere uma função que remove duplicatas consecutivas em uma lista:
(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
| Nil -> nil
| Cons(x, Nil) -> cons x empty
| Cons(x, Cons(y, rest)) ->
if x = y
then destutter (cons y rest)
else cons x (destutter (cons y rest))
Observe que todos os benefícios da correspondência de padrões são mantidos: a sintaxe de correspondência é a mesma e as verificações de integridade podem funcionar por completo. A compilação eficiente de tal solução está além do escopo desta visão geral, mas também é possível.
Progresso
Como parte deste trabalho, foi possível implementar a análise e digitação da extensão para o compilador OCaml versão 4.09, os resultados são apresentados aqui .
O analisador do compilador é implementado usando o gerador de analisador Menhir avançado . Menhir tem um manual bastante completo e detalhado , mas mesmo com ele nem sempre fica claro como se pode definir a regra de inferência, como não e por quê. O patch do analisador resultante é muito pequeno e simples, mas o caminho para ele passa por 10-15 conflitos shift-reduce e reduce-reduce, cuja análise e correção demorou algum tempo:

Gostaria de prestar homenagem aos desenvolvedores do Menhir e agradecê-los pelo trabalho realizado no detalhamento e esclarecimento dos erros. Uma vez que o gerador de analisador falhou em ilustrar o conflito e teve que desmontá-lo usando o autômato construído para 1500 estados. Isso exigia, é claro, uma ordem de magnitude a mais de tempo.
A digitação de extensões era especialmente difícil. O código de digitação tem cerca de 37.000 linhas e quase não está documentado, tornando difícil para um iniciante descobrir. Fui salvo por um artigo de Oleg Kiselev , que explica os principais aspectos da implementação.
Outra conclusão que tirei para mim mesmo é não esquecer de usar as versões antigas do projeto. Por exemplo, aqui está uma comparação quantitativa do mesmo tipo de digitação para as versões 2019 e 2005:

A versão 2019 contém análises e avisos do compilador, bem como detalhes técnicos adicionais nos quais eu não estava interessado. Para entender, bastou olhar para a versão de 2005, que contém apenas ações-chave.
Finalmente, a principal conclusão que tirei durante meu trabalho é a confirmação de que a documentação para projetos de código aberto é extremamente importante. Por mais expressiva que seja a linguagem, o código-fonte só pode dizer como uma função se comporta, não o que ela faz ou por que o faz daquela maneira. É muito difícil ler as cadeias de chamadas
type_self_pattern
-> type_cases
-> t ype_pat
-> type_pat'
-> type_pat_aux
e descobrir qual função você precisa; ou apenas um nome de parâmetroconstr
adivinhe quais construtores e por que devem ser escritos aqui.
A necessidade de olhar para os casos de uso toda vez retarda o programador e se cansa muito rapidamente: deixe-me lembrar a regra "sete, mais ou menos dois" - a mesma quantidade de objetos que uma pessoa pode, em média, simultaneamente ter em mente. E quando você finalmente entende o significado do parâmetro dentro da sexta função aninhada e de repente percebe que você não se lembra por que precisava dele, ou acontece que não precisava dele, fica muito triste por causa do tempo gasto.
Conclusão
Como parte de um projeto, fui capaz de implementar análise e digitação para padrões ativos. O compilador que apliquei pode analisar e digitar o arquivo com qualquer exemplo de uso de padrões ativos.
Em seguida, você precisa modificar o esquema de compilação (OCaml usa compilação de otimização não trivial de correspondência de padrões) e verificações de integridade de esquema, que foram quase completamente reescritas pela equipe de desenvolvimento do compilador OCaml durante o projeto.
Espero que esta implementação ainda seja concluída, com ou sem mim. Apesar de todas as dificuldades, foi ótimo tentar desenvolver um compilador industrial para sua linguagem favorita.
Autor:
Alexander Bashkirov é aluno do Centro de Ciência da Computação e do programa de bacharelado do 4º ano em Engenharia de Software na St. Petersburg State University, funcionário da JetBrains.