Computer Science › Software + Computação Distribuída
Os RECURSOS de uma linguagem (o que ela deixa um programador dizer) são uma questão completamente separada da sua IMPLEMENTAÇÃO (como uma máquina faz o que foi dito de fato acontecer); esta disciplina cobre a segunda, construindo um interpretador tree-walking enquanto deixa a compilação completa para a disciplina irmã `compilers`.
Antes de qualquer interpretador poder ser construído, uma linguagem precisa de uma definição matemática que resolva toda questão de \"para o que esta expressão avalia?\" sem ambiguidade; a semântica operacional de passo pequeno fornece isso como um conjunto de regras de inferência `t → t'`, e um interpretador é exatamente essas mesmas regras tornadas executáveis.
A gramática inteira do cálculo lambda não tipado tem três construtos, uma variável, uma abstração (definição de função) e uma aplicação (chamada de função), nada mais; esta minimalidade extrema é deliberada, pois é o que torna o cálculo tratável de estudar completamente e, ainda assim, poderoso o bastante para codificar aritmética, booleanos e recursão a partir destas três peças.
A redução beta, `(λx. t1) t2 → t1[x := t2]`, é a única regra de computação do cálculo lambda, o mecanismo de \"chamada de função\" em si; mas ela subespecifica a avaliação: call-by-value (reduzir o argumento a um valor primeiro) e call-by-name (substituir o argumento não avaliado) são as duas respostas clássicas de QUANDO ela pode disparar, e elas podem genuinamente divergir na terminação.
Com apenas três construtos e uma regra de redução, o cálculo lambda não tem números, booleanos, `if` nem recursão nomeada embutidos, ainda assim as codificações de Church mostram que todos esses podem ser construídos como termos lambda comuns, a demonstração concreta de que o cálculo lambda é genuinamente Turing-completo.
A análise léxica é o primeiro passo que impõe QUALQUER estrutura sobre o texto-fonte bruto, agrupando um fluxo plano de caracteres nos menores tokens significativos com os quais um parser está disposto a trabalhar, um problema de linguagem regular (um DFA basta) mantido deliberadamente separado do problema livre de contexto do parsing.
O parsing recupera a estrutura gramatical de um fluxo plano de tokens, construindo uma árvore de sintaxe abstrata (AST) que mantém só o que importa para o significado e descarta sintaxe (parênteses, palavras-chave) que existia puramente para guiar o parse; precedência e associatividade são codificadas diretamente na estrutura de aninhamento da gramática, e a descida recursiva traduz essa gramática quase mecanicamente em código.
Uma função `eval` que recursa sobre uma AST, com um caso por tipo de nó, é a semântica operacional de passo pequeno TORNADA EXECUTÁVEL, cada regra de inferência vira um ramo, e a estratégia de reexecutar a árvore do zero a cada vez é um trade-off honesto de simplicidade por velocidade.
Um nome de variável não é o valor que ele guarda, um ambiente é a estrutura de dados de tempo de execução (uma cadeia de mapeamentos) que de fato conecta os dois, e escopo léxico vs. dinâmico é uma escolha de design real sobre contra qual ambiente uma variável é resolvida.
No nível de implementação, uma closure é simplesmente um par (código da função, o ambiente ativo onde a função foi definida), e o ambiente capturado sobrevive ao retorno da chamada envolvente pela razão comum de que algo (a própria closure) ainda guarda uma referência viva a ele, não por nenhum mecanismo especial.
Um `if` ou um `while` não é um caso mágico especial para um interpretador, é mais um tipo de nó de AST cuja regra de avaliação decide quais dos seus filhos avaliar, e quantas vezes, inteiramente em termos de maquinaria já construída.
Quando um interpretador tree-walking avalia uma chamada de função, há de fato DUAS pilhas de chamadas crescendo juntas: a do programa interpretado (uma cadeia de objetos Environment) e a do próprio interpretador (quadros reais de pilha da linguagem hospedeira), e conflatar as duas é uma fonte comum de confusão e de crashes surpreendentes.
A tipagem estática verifica os tipos de um programa com um passo separado ANTES de ele rodar, rejeitando certas categorias de erro de imediato sem nenhuma execução, enquanto a tipagem dinâmica difere esse mesmo erro ao exato momento em que uma operação mal tipada é de fato tentada; nenhuma é estritamente superior, ambas são pontos de design reais ainda em uso ativo hoje.
O slogan \"programas bem tipados não dão errado\" não é uma aspiração vaga, ele se decompõe em exatamente duas propriedades prováveis: progresso (um termo bem tipado ou é um valor ou consegue dar um passo) e preservação (dar um passo nunca muda o tipo de um termo); provadas juntas por indução, elas constituem uma prova formal completa de segurança de tipos.
O cálculo lambda simplesmente tipado adiciona exatamente duas coisas ao cálculo não tipado, um tipo base e tipos de função (`τ → τ`), com toda abstração anotando o tipo do seu parâmetro; esta mudança mínima basta para construir um cálculo comprovadamente seguro em tipos, ao custo direto de perder poder expressivo genuíno, tornado concreto na impossibilidade de tipar o combinador Y.
A inferência de tipos recupera o tipo de um termo sem exigir que todo parâmetro carregue uma anotação explícita, atribuindo uma variável de tipo fresca a cada incógnita, gerando restrições de igualdade a partir de como o termo é estruturado, e resolvendo-as via unificação, o mesmo algoritmo central (unificação de Robinson) que subjaz à ligação de variável lógica do Prolog.
O gerenciamento manual de heap já mostrou exatamente como um vazamento ou um ponteiro pendurado acontece, uma runtime de linguagem com gerenciamento automático de memória existe especificamente para tornar essa classe inteira de bug estruturalmente impossível, ao custo de trabalho em tempo de execução que um programa C nunca paga.
Cada peça construída nesta disciplina, scanner, parser, AST, ambiente, closures, fluxo de controle, um verificador de tipos, ligada em conjunto num pequeno interpretador funcional, espelhando como o próprio capstone da disciplina de CPU montou portas lógicas e um datapath numa máquina funcional.
Part of the Computer Science curriculum.
Os RECURSOS de uma linguagem (o que ela deixa um programador dizer) são uma questão completamente separada da sua IMPLEMENTAÇÃO (como uma máquina faz o que foi dito de fato acontecer); esta disciplina cobre a segunda, construindo um interpretador tree-walking enquanto deixa a compilação completa para a disciplina irmã `compilers`.
Antes de qualquer interpretador poder ser construído, uma linguagem precisa de uma definição matemática que resolva toda questão de \"para o que esta expressão avalia?\" sem ambiguidade; a semântica operacional de passo pequeno fornece isso como um conjunto de regras de inferência `t → t'`, e um interpretador é exatamente essas mesmas regras tornadas executáveis.
A gramática inteira do cálculo lambda não tipado tem três construtos, uma variável, uma abstração (definição de função) e uma aplicação (chamada de função), nada mais; esta minimalidade extrema é deliberada, pois é o que torna o cálculo tratável de estudar completamente e, ainda assim, poderoso o bastante para codificar aritmética, booleanos e recursão a partir destas três peças.
A redução beta, `(λx. t1) t2 → t1[x := t2]`, é a única regra de computação do cálculo lambda, o mecanismo de \"chamada de função\" em si; mas ela subespecifica a avaliação: call-by-value (reduzir o argumento a um valor primeiro) e call-by-name (substituir o argumento não avaliado) são as duas respostas clássicas de QUANDO ela pode disparar, e elas podem genuinamente divergir na terminação.
Com apenas três construtos e uma regra de redução, o cálculo lambda não tem números, booleanos, `if` nem recursão nomeada embutidos, ainda assim as codificações de Church mostram que todos esses podem ser construídos como termos lambda comuns, a demonstração concreta de que o cálculo lambda é genuinamente Turing-completo.
A análise léxica é o primeiro passo que impõe QUALQUER estrutura sobre o texto-fonte bruto, agrupando um fluxo plano de caracteres nos menores tokens significativos com os quais um parser está disposto a trabalhar, um problema de linguagem regular (um DFA basta) mantido deliberadamente separado do problema livre de contexto do parsing.
O parsing recupera a estrutura gramatical de um fluxo plano de tokens, construindo uma árvore de sintaxe abstrata (AST) que mantém só o que importa para o significado e descarta sintaxe (parênteses, palavras-chave) que existia puramente para guiar o parse; precedência e associatividade são codificadas diretamente na estrutura de aninhamento da gramática, e a descida recursiva traduz essa gramática quase mecanicamente em código.
Uma função `eval` que recursa sobre uma AST, com um caso por tipo de nó, é a semântica operacional de passo pequeno TORNADA EXECUTÁVEL, cada regra de inferência vira um ramo, e a estratégia de reexecutar a árvore do zero a cada vez é um trade-off honesto de simplicidade por velocidade.
Um nome de variável não é o valor que ele guarda, um ambiente é a estrutura de dados de tempo de execução (uma cadeia de mapeamentos) que de fato conecta os dois, e escopo léxico vs. dinâmico é uma escolha de design real sobre contra qual ambiente uma variável é resolvida.
No nível de implementação, uma closure é simplesmente um par (código da função, o ambiente ativo onde a função foi definida), e o ambiente capturado sobrevive ao retorno da chamada envolvente pela razão comum de que algo (a própria closure) ainda guarda uma referência viva a ele, não por nenhum mecanismo especial.
Um `if` ou um `while` não é um caso mágico especial para um interpretador, é mais um tipo de nó de AST cuja regra de avaliação decide quais dos seus filhos avaliar, e quantas vezes, inteiramente em termos de maquinaria já construída.
Quando um interpretador tree-walking avalia uma chamada de função, há de fato DUAS pilhas de chamadas crescendo juntas: a do programa interpretado (uma cadeia de objetos Environment) e a do próprio interpretador (quadros reais de pilha da linguagem hospedeira), e conflatar as duas é uma fonte comum de confusão e de crashes surpreendentes.
A tipagem estática verifica os tipos de um programa com um passo separado ANTES de ele rodar, rejeitando certas categorias de erro de imediato sem nenhuma execução, enquanto a tipagem dinâmica difere esse mesmo erro ao exato momento em que uma operação mal tipada é de fato tentada; nenhuma é estritamente superior, ambas são pontos de design reais ainda em uso ativo hoje.
O slogan \"programas bem tipados não dão errado\" não é uma aspiração vaga, ele se decompõe em exatamente duas propriedades prováveis: progresso (um termo bem tipado ou é um valor ou consegue dar um passo) e preservação (dar um passo nunca muda o tipo de um termo); provadas juntas por indução, elas constituem uma prova formal completa de segurança de tipos.
O cálculo lambda simplesmente tipado adiciona exatamente duas coisas ao cálculo não tipado, um tipo base e tipos de função (`τ → τ`), com toda abstração anotando o tipo do seu parâmetro; esta mudança mínima basta para construir um cálculo comprovadamente seguro em tipos, ao custo direto de perder poder expressivo genuíno, tornado concreto na impossibilidade de tipar o combinador Y.
A inferência de tipos recupera o tipo de um termo sem exigir que todo parâmetro carregue uma anotação explícita, atribuindo uma variável de tipo fresca a cada incógnita, gerando restrições de igualdade a partir de como o termo é estruturado, e resolvendo-as via unificação, o mesmo algoritmo central (unificação de Robinson) que subjaz à ligação de variável lógica do Prolog.
O gerenciamento manual de heap já mostrou exatamente como um vazamento ou um ponteiro pendurado acontece, uma runtime de linguagem com gerenciamento automático de memória existe especificamente para tornar essa classe inteira de bug estruturalmente impossível, ao custo de trabalho em tempo de execução que um programa C nunca paga.
Cada peça construída nesta disciplina, scanner, parser, AST, ambiente, closures, fluxo de controle, um verificador de tipos, ligada em conjunto num pequeno interpretador funcional, espelhando como o próprio capstone da disciplina de CPU montou portas lógicas e um datapath numa máquina funcional.