Computer Science › Especialização
Uma continuação é o resto da computação, reificado como função. Reescrever um programa em estilo de passagem de continuação (CPS) torna o fluxo de controle explícito (toda chamada vira chamada de cauda, todo resultado intermediário ganha nome), que é exatamente a forma usada por compiladores, pela desaçucarização de async/await, por geradores e por threads virtuais.
Um parser LR lê a entrada da esquerda para a direita e constrói a derivação mais à direita de trás para frente, usando uma pilha e um autômato finito sobre conjuntos de itens da gramática para decidir entre deslocar e reduzir. Entender as tabelas explica de onde vêm os conflitos shift/reduce e por que yacc, Bison e seus descendentes aceitam as gramáticas que aceitam.
O LLVM transforma o problema de M linguagens por N alvos em M mais N colocando no meio uma representação intermediária tipada em forma SSA. Frontends emitem IR baseada em memória, um pipeline de passes de análise e transformação (com o mem2reg à frente) a otimiza, e um backend a reduz a código de máquina.
System F acrescenta quantificação universal sobre tipos ao cálculo lambda simplesmente tipado, de modo que uma definição serve para todo tipo. Como uma função polimórfica não pode inspecionar o seu argumento de tipo, só o tipo já restringe o que ela pode fazer (\"teoremas de graça\"), a teoria por trás dos generics em Java, C#, Rust e Haskell.
A subtipagem deixa um valor de um tipo mais específico ocupar o lugar de um mais geral, e a regra dos tipos de função (contravariante no argumento, covariante no resultado) decide quais tipos genéricos podem ser substituídos. Contêineres mutáveis precisam ser invariantes para manter a segurança, e por isso os arrays do Java são um erro histórico e existem wildcards, in/out do Kotlin e quantificação limitada.
Sistemas de tipos subestruturais restringem quantas vezes um valor pode ser usado. Os tipos afins do Rust, mais a regra \"vários leitores ou um escritor\", dão segurança de memória e ausência de data races sem coletor de lixo, e a mesma disciplina (tipos lineares) aparece no Linear Haskell e em linguagens de pesquisa para recursos e protocolos.
Quando tipos podem mencionar valores, um tipo pode enunciar uma especificação precisa (um vetor de tamanho n, uma lista ordenada) e um programa desse tipo é uma prova de que ela vale. Pela correspondência de Curry-Howard, implicação é o tipo função, conjunção é o tipo par e quantificação universal é o tipo função dependente, e é assim que Lean, Coq/Rocq e Agda funcionam ao mesmo tempo como linguagens de programação e assistentes de prova.
A interpretação abstrata executa um programa sobre um domínio simplificado (sinais, intervalos) em vez de valores concretos, e uma conexão de Galois entre os dois garante que todo comportamento concreto é coberto. O alargamento (widening) força os laços a convergir, trocando precisão por terminação, e o resultado é uma análise correta que pode provar a ausência de classes inteiras de erros de execução.
Quase toda outra análise e otimização precisa saber a quais posições de memória um ponteiro ou referência pode se referir. A análise de Andersen, baseada em inclusão, resolve restrições de subconjunto com precisão e custo cúbico no pior caso, a de Steensgaard, baseada em unificação, funde classes de equivalência em tempo quase linear, e as sensibilidades a contexto, campo e heap decidem onde uma ferramenta real fica na curva de precisão e custo.
A execução simbólica roda um programa com entradas simbólicas, coletando uma condição de caminho em cada desvio e perguntando a um solver SMT se cada caminho é viável e qual entrada concreta o percorre. O teste concólico mistura execução concreta e simbólica para gerar um teste para cada caminho que consegue alcançar, ao preço da explosão de caminhos e de pouco raciocínio sobre laços, memória e o ambiente.
A lógica de Hoare falha quando ponteiros têm alias, porque qualquer asserção sobre uma célula pode ser invalidada por uma escrita através de outro nome. A lógica de separação acrescenta uma conjunção separadora P * Q, que significa que P e Q valem em partes disjuntas do heap, e uma regra de frame que estende uma prova sobre um footprint pequeno a qualquer heap maior; é a base do Infer, do VeriFast, do Viper e da prova do RustBelt.
Um fuzzer alimenta um programa com entradas mutadas e observa crashes. Fuzzers guiados por cobertura como AFL e libFuzzer instrumentam o alvo, guardam toda entrada que alcança código novo e mutam a partir delas, o que transforma uma busca cega exponencial em uma incremental; combinados com sanitizers, acham bugs de segurança de memória em parsers e código de protocolo em escala.
Tipos, interpretação abstrata, lógica de separação, execução simbólica e fuzzing dão cada um uma garantia diferente a um custo diferente. Este capstone escolhe uma técnica para três situações realistas (nulidade num monorepo Java grande, um parser C para entrada não confiável, um controlador que nunca pode levantar erro de execução) e declara para cada uma exatamente o que é garantido e o que não é.
O Language Server Protocol transforma o problema de integração editores vezes linguagens em editores mais linguagens colocando a análise atrás de uma interface JSON-RPC. Para que essa análise seja rápida a ponto de rodar a cada tecla, são necessários parsing tolerante a erros e consultas memoizadas guiadas por demanda com corte antecipado, a mesma ideia que sustenta os sistemas de build modernos.
Part of the Computer Science curriculum.
Uma continuação é o resto da computação, reificado como função. Reescrever um programa em estilo de passagem de continuação (CPS) torna o fluxo de controle explícito (toda chamada vira chamada de cauda, todo resultado intermediário ganha nome), que é exatamente a forma usada por compiladores, pela desaçucarização de async/await, por geradores e por threads virtuais.
Um parser LR lê a entrada da esquerda para a direita e constrói a derivação mais à direita de trás para frente, usando uma pilha e um autômato finito sobre conjuntos de itens da gramática para decidir entre deslocar e reduzir. Entender as tabelas explica de onde vêm os conflitos shift/reduce e por que yacc, Bison e seus descendentes aceitam as gramáticas que aceitam.
O LLVM transforma o problema de M linguagens por N alvos em M mais N colocando no meio uma representação intermediária tipada em forma SSA. Frontends emitem IR baseada em memória, um pipeline de passes de análise e transformação (com o mem2reg à frente) a otimiza, e um backend a reduz a código de máquina.
System F acrescenta quantificação universal sobre tipos ao cálculo lambda simplesmente tipado, de modo que uma definição serve para todo tipo. Como uma função polimórfica não pode inspecionar o seu argumento de tipo, só o tipo já restringe o que ela pode fazer (\"teoremas de graça\"), a teoria por trás dos generics em Java, C#, Rust e Haskell.
A subtipagem deixa um valor de um tipo mais específico ocupar o lugar de um mais geral, e a regra dos tipos de função (contravariante no argumento, covariante no resultado) decide quais tipos genéricos podem ser substituídos. Contêineres mutáveis precisam ser invariantes para manter a segurança, e por isso os arrays do Java são um erro histórico e existem wildcards, in/out do Kotlin e quantificação limitada.
Sistemas de tipos subestruturais restringem quantas vezes um valor pode ser usado. Os tipos afins do Rust, mais a regra \"vários leitores ou um escritor\", dão segurança de memória e ausência de data races sem coletor de lixo, e a mesma disciplina (tipos lineares) aparece no Linear Haskell e em linguagens de pesquisa para recursos e protocolos.
Quando tipos podem mencionar valores, um tipo pode enunciar uma especificação precisa (um vetor de tamanho n, uma lista ordenada) e um programa desse tipo é uma prova de que ela vale. Pela correspondência de Curry-Howard, implicação é o tipo função, conjunção é o tipo par e quantificação universal é o tipo função dependente, e é assim que Lean, Coq/Rocq e Agda funcionam ao mesmo tempo como linguagens de programação e assistentes de prova.
A interpretação abstrata executa um programa sobre um domínio simplificado (sinais, intervalos) em vez de valores concretos, e uma conexão de Galois entre os dois garante que todo comportamento concreto é coberto. O alargamento (widening) força os laços a convergir, trocando precisão por terminação, e o resultado é uma análise correta que pode provar a ausência de classes inteiras de erros de execução.
Quase toda outra análise e otimização precisa saber a quais posições de memória um ponteiro ou referência pode se referir. A análise de Andersen, baseada em inclusão, resolve restrições de subconjunto com precisão e custo cúbico no pior caso, a de Steensgaard, baseada em unificação, funde classes de equivalência em tempo quase linear, e as sensibilidades a contexto, campo e heap decidem onde uma ferramenta real fica na curva de precisão e custo.
A execução simbólica roda um programa com entradas simbólicas, coletando uma condição de caminho em cada desvio e perguntando a um solver SMT se cada caminho é viável e qual entrada concreta o percorre. O teste concólico mistura execução concreta e simbólica para gerar um teste para cada caminho que consegue alcançar, ao preço da explosão de caminhos e de pouco raciocínio sobre laços, memória e o ambiente.
A lógica de Hoare falha quando ponteiros têm alias, porque qualquer asserção sobre uma célula pode ser invalidada por uma escrita através de outro nome. A lógica de separação acrescenta uma conjunção separadora P * Q, que significa que P e Q valem em partes disjuntas do heap, e uma regra de frame que estende uma prova sobre um footprint pequeno a qualquer heap maior; é a base do Infer, do VeriFast, do Viper e da prova do RustBelt.
Um fuzzer alimenta um programa com entradas mutadas e observa crashes. Fuzzers guiados por cobertura como AFL e libFuzzer instrumentam o alvo, guardam toda entrada que alcança código novo e mutam a partir delas, o que transforma uma busca cega exponencial em uma incremental; combinados com sanitizers, acham bugs de segurança de memória em parsers e código de protocolo em escala.
Tipos, interpretação abstrata, lógica de separação, execução simbólica e fuzzing dão cada um uma garantia diferente a um custo diferente. Este capstone escolhe uma técnica para três situações realistas (nulidade num monorepo Java grande, um parser C para entrada não confiável, um controlador que nunca pode levantar erro de execução) e declara para cada uma exatamente o que é garantido e o que não é.
O Language Server Protocol transforma o problema de integração editores vezes linguagens em editores mais linguagens colocando a análise atrás de uma interface JSON-RPC. Para que essa análise seja rápida a ponto de rodar a cada tecla, são necessários parsing tolerante a erros e consultas memoizadas guiadas por demanda com corte antecipado, a mesma ideia que sustenta os sistemas de build modernos.