Por que precisamos de efeitos algébricos

• Efeitos algébricos são um recurso de linguagem que captura e trata o fluxo de controle como exceções retomáveis; são um recurso central do Ante e também são usados de forma central em linguagens de pesquisa como Koka, Effekt, Eff e Flix
• Com o mesmo mecanismo, é possível criar generators, exceções, async, corrotinas e diferenciação automática no nível de biblioteca, e graças ao polimorfismo de efeitos, funções como map podem ser escritas apenas uma vez, independentemente do tipo de efeito
• Se injeção de dependência e passagem de contexto, como acesso a banco de dados, saída, logging e passagem de estado, forem transformadas em efeitos, mocks de teste, coleta de saída e filtragem de logs podem ser tratadas trocando handlers
• Quando efeitos como can IO, can Print e can Fail aparecem na assinatura da função, isso é vantajoso para garantir pureza, gravação/reprodução e auditoria de segurança, embora efeitos já permitidos possam se propagar sem querer para handlers existentes
• A fraqueza tradicional era a preocupação com eficiência, mas linguagens recentes vêm reduzindo o custo com otimizações para efeitos tail-resumptive, evidence passing, limitação a um único resume e especialização de handlers

---

Modelo básico de efeitos algébricos

• Efeitos algébricos também são chamados de effect handlers e podem ser entendidos pelo modelo de “exceções retomáveis”
• No pseudocódigo de Ante, declara-se uma função de efeito e marca-se na assinatura da função, com can, que aquele efeito pode ser usado
  • Chamar uma função de efeito como say_message: Unit -> Unit equivale a “lançar” o efeito
  • A função chamadora expõe essa possibilidade na assinatura, como em foo () can SayMessage
• A expressão handle captura o efeito de forma parecida com try/catch e continua o cálculo interrompido ao chamar resume
  • Se o handler de say_message executar print "Hello World!" e depois chamar resume (), o cálculo original continua e retorna 42
• O nome “algébrico” é, em grande parte, um termo legado; na prática, effect handlers é uma descrição mais precisa, mas usa-se “efeitos algébricos” por ser um nome mais familiar para os usuários

Fluxo de controle definido pelo usuário

• Efeitos algébricos permitem implementar vários recursos de linguagem com um único mecanismo
  • generators
  • exceções
  • async
  • corrotinas
  • diferenciação automática
• O polimorfismo de efeitos reduz o problema de what color is your function
  • map (input: Vec a) (f: a -> b can e): Vec b can e expressa que, qualquer que seja o efeito e realizado pela função de entrada f, map também realiza o mesmo efeito
  • O mesmo map pode ser usado junto com saída em stdout, chamadas de função assíncronas e yield de stream
  • Muitas linguagens com effect handlers omitem a variável de efeito e, permitindo usar a forma familiar map (input: Vec a) (f: a -> b): Vec b
• Exceções podem ser implementadas tratando o efeito de forma a não chamar resume
  • Define-se o efeito Throw a com throw: a -> never_returns
  • Ao dividir por zero, chama-se throw "error: Division by zero!", e o handler imprime a mensagem sem retomar o cálculo
• Generators podem ser implementados com o efeito Yield a e yield: a -> Unit
  • Percorre-se os elementos de um vetor chamando yield elem
  • O handler de filter chama yield x novamente quando o valor produzido satisfaz a condição e segue para o próximo elemento com resume ()
  • O handler de my_for_each executa a função f para cada valor produzido e continua com resume ()
• Um escalonador cooperativo também pode ser criado com o efeito yield: Unit -> Unit, em que o handler assume o controle e alterna para a execução de outra função
  • O exemplo de scheduler do Effekt mostra esse padrão
• Vários efeitos se compõem bem entre si, e isso é apontado como uma vantagem de usabilidade em relação a outras abstrações de efeito

Injeção de dependência e testabilidade

• Efeitos também podem ser usados em aplicações de negócio comuns para injeção de dependência
• Em vez de passar diretamente um objeto de banco de dados como argumento, pode-se definir um efeito Database
  • No formato tradicional, algo como business_logic (db: Database) (x: I32) recebe o objeto de banco como argumento
  • Na forma baseada em efeitos, fica business_logic (x: I32) can Database, e internamente a função chama query "..."
• A escolha do banco de dados concreto fica a cargo de um handler em um nível mais alto da pilha de chamadas
  • É possível trocar o banco de produção por outro ou substituí-lo por um mock para testes
  • Um handler mock_database pode ignorar a mensagem query e sempre fazer resume com DbResponse.Ok
• Se a saída também for tratada como efeito, durante os testes é possível coletá-la como string sem escrever diretamente em stdout
  • Um handler print_to_string captura chamadas print msg e as acumula na string all_messages com quebras de linha
  • output_messages pode validar o valor de retorno 1234 e a string de mensagens sem saída real
• Logging pode ser transformado em saída condicional usando o efeito Log e LogLevel
  • log_handler chama print msg quando o nível da mensagem é igual ou superior ao limite configurado
  • foo () with log_handler Error imprime apenas logs de erro

APIs mais limpas e passagem de contexto

• Efeitos algébricos permitem representar com efeitos o padrão de objeto de Context propagado por todo o programa ou biblioteca
• O efeito Use a pode ser visto como um efeito de estado, oferecendo get: Unit -> a e set: a -> Unit
  • O handler state guarda o estado inicial, retorna o contexto atual em get e o atualiza para o novo contexto em set
  • A definição de exemplo de state ignora regras de ownership, e uma implementação real pode exigir a restrição Copy a
• O exemplo de armazenar strings em um vetor e passar índices como chaves mostra o custo de propagar contexto
  • Sem efeitos, push_string, get_string, append_with_separator e example precisam continuar recebendo strings como argumento
  • Na implementação baseada em efeitos, as operações primitivas push_string e get_string chamam get/set, e o código de nível superior não precisa passar strings diretamente
• Essa abordagem se encaixa bem quando uma biblioteca encapsula a passagem de contexto interna
  • O usuário da biblioteca não precisa se preocupar com os detalhes internos de como o contexto é propagado
  • Para não ficar preso a um tipo específico de contexto, é possível abstrair as funções necessárias por meio de interfaces

Substituição de variáveis globais e estilo direto

• APIs como geração de números aleatórios ou alocação de memória, que parecem sem estado por fora mas exigem estado na prática, podem ser expressas com efeitos em vez de variáveis globais
• O exemplo de geração aleatória mostra o incômodo de ter de propagar manualmente um objeto Prng por todo o programa
  • Um Prng global é conveniente, mas traz as desvantagens de valores globais, como a necessidade de thread safety
  • Com random: Unit -> U8 do efeito Random, o usuário só precisa deixar explícito que em algum ponto acima na pilha de chamadas o efeito será inicializado por um handler
  • Depois, para trocar por /dev/urandom ou outra fonte de aleatoriedade, basta substituir o handler, sem mudar o restante da pilha de chamadas
• A alocação de memória também pode ser expressa com o efeito Allocate
  • allocate: (size: Usz) -> Alignment -> Ptr a
  • free: Ptr a -> Unit
  • Na maioria das chamadas usa-se o allocator global, e em um tight loop é possível adicionar um handler ao corpo do loop para trocar por um arena allocator
• Efeitos possibilitam estilo direto em vez de passar resultados embrulhados em valores dedicados
  • Com Maybe t, é preciso encadear o caminho de sucesso com and_then e map
  • Açúcar sintático como o ? do Rust existe para manter o foco no caminho feliz
  • Em uma versão baseada em efeitos, get_line_from_stdin (): String can Fail, IO e parse (s: String): U32 can Fail podem ser escritos como código sequencial comum, com line = ..., x = ..., x * 2
• O tratamento de falha pode ser feito aplicando um handler para sair do caminho principal quando necessário
  • get_line_from_stdin () with default "42" trata o efeito Fail com um valor padrão
• Tipos de erro diferentes também se compõem naturalmente como listas de efeitos
  • LibraryA.foo (): U32 can Throw LibraryA.Error
  • LibraryB.bar (): U32 can Throw LibraryB.Error
  • my_function pode declarar juntos Throw LibraryA.Error, Throw LibraryB.Error e Throw MyError
  • Se a repetição ficar longa, é possível criar um alias de tipo como AllErrors = can Throw ...
  • O mesmo efeito Throw String é unificado em um só; se quiser separá-los, é preciso um tipo wrapper como MyError

Pureza, reexecução e auditoria de segurança

• A maioria das linguagens com effect handlers, com exceção aproximada de OCaml, usa efeitos em todos os lugares onde efeitos colaterais podem ocorrer
  • Em Ante, sem algo como can Print ou can IO, não é possível usar efeitos colaterais
  • Definições extern não podem ser verificadas pelo compilador, então é preciso confiar na definição de tipo
  • Há planos para permitir executar o efeito IO apenas em modo debug, preservando a segurança de efeitos no modo release
• Algumas funções exigem uma função pura como entrada
  • Ao criar uma thread, a thread criada não deve poder chamar handlers que pertencem à thread atual
  • spawn_all (functions: Vec (Unit -> a pure)): Vec a can IO aceita apenas funções puras, executa todas em threads e espera sua conclusão
• Software Transactional Memory (STM) é uma técnica de concorrência que requer funções puras
  • Ao executar várias funções simultaneamente, se durante a transação um valor for alterado por outra thread, a transação correspondente é reiniciada
  • O protótipo de prova de conceito do Effekt está em effekt-stm
• A pureza também pode oferecer possibilidades de gravação/reprodução semelhantes ao utilitário de depuração rr
  • Dois handlers, record e replay, tratam os efeitos de nível mais alto exportados por main, normalmente IO
  • record grava a ocorrência do efeito e seu resultado, depois repassa para o handler IO embutido para processamento real
  • replay não executa o IO real e usa os resultados do log de efeitos
  • Gravar por padrão em builds de debug pode permitir depuração determinística
• A lista de efeitos na assinatura da função ajuda na auditoria de segurança, de forma semelhante a Capability Based Security
  • get_pi: Unit -> F64 permite saber que a função não está fazendo IO escondido em segundo plano
  • Se após uma atualização de biblioteca get_pi: Unit -> F64 can IO, então, a menos que a função chamadora já exija IO, o código passará a apresentar erro
  • O ideal é declarar apenas os efeitos mínimos necessários; por exemplo, declarar Print em vez de IO completo
  • Adicionar um novo efeito é tratado como uma mudança que quebra semantic versioning
  • Materiais relacionados incluem Capability Based Security e Designing with Static Capabilities and Effects

Limites e estratégias de implementação

• Uma das limitações da abordagem com efeitos é a possibilidade de tratamento não intencional
  • Se uma função passar a exigir IO, a função chamadora pode não gerar erro caso já permita IO
  • O mesmo vale para o efeito Fail: se uma função de biblioteca que antes não falhava passar a poder falhar, ela pode se propagar para um handler Fail já existente
  • Esse comportamento pode ser aceitável dependendo do caso, mas pode divergir da intenção quando se queria um tratamento separado, como fornecer um valor padrão
• A principal desvantagem tradicional era a preocupação com eficiência, mas a saída compilada dos efeitos melhorou bastante nos últimos tempos
• Muitas linguagens de efeitos algébricos otimizam efeitos tail-resumptive como chamadas normais de closure
  • Efeitos tail-resumptive são aqueles em que o handler chama resume por último
  • A maioria dos efeitos reais se enquadra aqui, e a maior parte dos exemplos do texto também está nessa categoria
  • Exceções, por não chamarem resume de forma alguma, são tratadas como caso à parte
• As estratégias de otimização variam entre as linguagens
  • Koka usa evidence passing e eleva os efeitos até seus handlers para compilar para C sem runtime
  • Ante e OCaml limitam resume a no máximo uma chamada
    • Essa restrição exclui alguns efeitos, como não determinismo
    • Em compensação, simplifica o gerenciamento de recursos e permite implementar continuações internas com mais eficiência, por exemplo com segmented stacks
  • Effekt especializa completamente os handlers e os remove do programa
    • Essa abordagem impõe a limitação de que a maioria das funções seja second-class
    • É possível obter funções first-class em forma boxed e migrar para isso em um modelo pay-as-you-go
    • Materiais relacionados incluem a documentação de captures do Effekt e o artigo