Projetos Extras • Capítulo 16

Apenas o Começo


Embora fizemos bastante com nosso Lisp, ainda está longe de ser uma linguagem de programação inteiramente completa, pronta para produção. Se você tentar usá-la para qualquer projeto suficientemente grande, haverá uma certa quantidade de problemas que você vai topar e melhorias que terá que fazer. Resolver esses problemas seria o que a traria mais para o escopo de uma linguagem madura.

Aqui estão algumas das questões que você provavelmente iria encontrar, possíveis soluções para estes problemas e algumas outras ideias divertidas para melhorias. Algumas podem precisar de algumas centenas de linhas de código, outras alguns milhares. A escolha do que atacar é sua. Se você se afeiçoar à sua linguagem, talvez curta fazer alguns desses projetos.

Tipos Nativos


Atualmente nossa linguagem apenas envolve os tipos nativos C long e char*. Isto é bem limitante caso queira fazer qualquer tipo de computação útil. Nossas operações nestes tipos de dados são também bem limitadas. Idealmente nossa linguagem deveria envolver todos os tipos nativos C e permitir maneiras de manipulá-los. Uma das adições mais importantes seria a capacidade de manipular números decimais. Para isto você poderia envolver o tipo double e operações relevantes. Com mais de um tipo numérico precisamos nos certificar que os operadores aritméticos como + e - funcionam em todos eles, e em combinação.

Adicionar suporte a tipos nativos deve ser interessante para pessoas desejando fazer computação com números decimais e de ponto flutuante em suas linguagens.

Tipos Definidos pelo Usuário


Assim como adicionar suporte para tipos nativos, seria bom dar aos usuários a capacidade de adicionar seus próprios tipos, assim como usamos structs em C. A sintaxe ou maneira de usar isto é sua escolha. Esta é uma parte essencial de tornar nossa linguagem usável para qualquer projeto de tamanho razoável.

Esta tarefa pode ser interessante para qualquer pessoa com alguma ideia específica de como eles gostariam de desenvolver a linguagem, e como gostariam que o projeto final se pareça.

list

Lista importante • Brinque! SEJA FELIZ e vá para casa.

Literal para Listas


Alguns Lisps usam colchetes [] para dar uma notação literal para listas de valores avaliados. Isto é açúcar sintático para escrever coisas como list 100 (+ 10 20) 300. Em vez disso, ele te deixa escrever [100 (+ 10 20) 300]. Em algumas situações isto é claramente melhor, mas isso vai ocupar os caracteres [] que possivelmente poderia ser usados para propósitos mais interessantes.

Esta deve ser uma adição simples para pessoas querendo experimentar adicionar sintaxe extra.

Interação com Sistema Operacional


Uma parte essencial de erguer uma linguagem é dá-la capacidades apropriadas para abrir, ler e escrever arquivos. Isto significa envolver todas as funções C como fread, fwrite, fgetc, etc em equivalentes Lisp. Esta é uma tarefa relativamente tranquilo, mas requer escrever um grande número de funções envolvendo C (wrappers). É por isso que não fizemos em nossa linguagem.

Em nota similar, seria ótimo dar acesso à nossa linguagem a quaisquer chamadas ao sistema operacional que sejam apropriadas. Deveríamos dá-la capacidade de mudar o diretório, listar arquivos em um diretório e este tipo de coisa. Esta é uma tarefa fácil, mas novamente requer envolver bastantes funções C. É essencial para qualquer uso prático dessa linguagem como uma linguagem de scripts.

Pessoas desejando fazer uso da sua linguagem para fazer simples tarefas de scripts e manipulação de strings podem estar interessadas em implementar este projeto.

Macros


Muitos outros Lisps permitem você escrever coisas como (def x 100) para definir o valor 100 para x. Em nosso Lisp isto não funcionaria porque iria tentar avaliar o x para o valor que foi armazenado em x no ambiente. Em outros Lisps estas funções são chamadas macros, e quando encontradas elas param a avaliação dos seus argumentos e os manipulam não-avaliados. Elas permitem escrever coisas que parecem chamadas normais a funções, mas na verdade fazem coisas complexas e interessantes.

Estas são coisas divertidas de ter em uma linguagem. Elas fazem com que você possa colocar um pouco de mágica no funcionamento. Em muitos casos isso pode deixar a sintaxe melhor ou permitir o usuário não ter que se repetir.

Eu gosto como nossa linguagem lida com coisas como def e if sem recorrer a macros, mas se você não gosta como ela funciona atualmente, e quer que seja mais parecida com Lisps convencionais, isto pode ser algo que você esteja interessado em implementar.

Tabela Hash de variáveis


No momento, quando procuramos nomes de variáveis em nossa linguagem, simplesmente fazemos uma busca linear por todas as variáveis no ambiente. Isto se torna cada vez mais ineficiente quanto mais variáveis temos definidas.

Uma maneira mais eficiente de fazer isso é implementar uma Tabela Hash. Esta técnica converte o nome da variável em um inteiro e usa isto para indexar em um array de tamanho conhecido para encontrar o valor associado a este símbolo. Esta é uma estrutura de dados muito importante em programação e vai aparecer em todo lugar por causa da sua performance fantástica sob cargas pesadas.

Qualquer um interessado em aprender mais sobre estruturas de dados e algoritmos será espero de tentar implementar esta estrutura de dados ou uma de suas variações.

Alocação com Pool


Nosso Lisp é muito simples, não é rápido. Sua performance é relativa à algumas linguagens de scripting como Python e Ruby. A maior parte do overhead de performance em nosso programa vem do fato que fazer praticamente qualquer coisa requer que construamos e destruamos lval. Por isso, nós chamamos malloc muito frequentemente. Esta é uma função lenta porque requer que o sistema operacional faça um pouco de gerenciamento para nós. Ao fazer cálculos há bastante cópias, alocações e desalocações de tipos lval.

Caso desejarmos reduzir este overhead, precisamos reduzir o número de chamadas a malloc. Uma maneira de fazer isso é chamar malloc uma vez no começo do programa, alocando um grande "tanque" (pool) de memória. Devemos então substituir todas nossas chamadas a malloc por chamadas a alguma função que corte e distribua esta memória para uso no programa. Isto significa que estamos emulando um pouco do comportamento do sistema operacional, mas numa maneira local mais rápida. Esta ideia é chamada memory pool allocation (alocação de tanque de memória) e é uma técnica comum em desenvolvimento de jogos e outras aplicações sensíveis ao desempenho.

Isto pode ser complicado de implementar corretamente, mas conceitualmente não precisa ser complexo. Caso queira um método rápido de obter grandes ganhos em performance, dar uma olhada nisso pode lhe interessar.

Coleta de Lixo


Quase todas outras implementações de Lisps atribuem variáveis diferentemente do nosso. Elas não armazenam uma cópia do valor no ambiente, mas na verdade um apontador (ou referência) para ele diretamente. Como estão usando apontadores em vez de cópias, da mesma forma que em C, há muito menos overhead ao usar grandes estruturas de dados.

garbage

Coleta de Lixo • Junte aquela lata.

Se armazenamos apontadores a valores, no lugar de cópias, precisamos nos certificar que o dado apontado não é excluído antes que algum outro valor tente usá-lo. Queremos excluí-lo quando não há mais nenhuma referência a ele. Um método para fazer isto, chamado Mark and Sweep (marca e varre) é monitorar estes valores que estão no ambiente, assim como todo valor que foi alocado. Quando uma variável é colocada no ambiente, ela e tudo o que ela referencia é marcada. A seguir, quando desejamos liberar memória, podemos iterar sobre toda alocação e deletar qualquer uma que não esteja marcada.

Isto é chamado coleta de lixo (em inglês, garbage collection) e é uma parte integral de muitas linguagens de programação. Assim como em alocação com pools, implementar um coletor de lixo não precisa ser complicado, mas precisa ser feito cuidadosamente, em particular se você deseja fazê-lo eficiente. Implementar isto seria essencial para fazer esta linguagem prática para trabalhar com grande quantidades de dados. Um tutorial particularmente bom em implementar um coletor de lixo em C pode ser encontrado aqui (em inglês).

Isto deve interessar qualquer um interessado no desempenho da linguagem e desejando mudar a semântica de como variáveis são armazenadas e modificadas na linguagem.

Otimização de Chamada em Cauda (Tail Call Optimisation)


Nossa linguagem de programação usa recursão para fazer seu laço. Isto é conceitualmente uma maneira inteligente de fazê-lo, mas na prática é bem pobre. Funções recursivas chamam a si próprias para coletar todos os resultados parciais de uma computação, e só então combinam todos os resultados juntos. Este é um jeito bem desperdiçador de fazer computação quando resultados parciais podem ser acumulados como algum total sobre um laço. Isto é particularmente problemático para laços que serão rodados por muitas, ou infinitas, iterações.

Algumas funções recursivas podem ser automaticamente convertidas para laços while correspondentes, que acumulam totais passo a passo, em vez de tudo de uma vez. Esta conversão automática é chamada otimização de chamada em cauda (ou tail call optimization) e é uma otimização essencial para programas que fazem bastante iteração com recursão.

Pessoas interessadas em otimizações de compiladores e as correspondências entre diferentes formas de computação podem achar este projeto interessante.

Escopo Léxico


Quando nossa linguagem tenta buscar uma variável que já foi definida, ela joga um erro. Seria melhor se ela pudesse dizer quais variáveis não estão definidas antes de avaliar o programa. Isto poderia nos permitir evitar erros de digitação e outros bugs. Encontrar esses problemas antes do programa rodar é chamado escopo léxico, e usa as regras para definições de variáveis para tentar inferir quais variáveis estão definidas e quais não estão em cada ponto do programa, sem fazer qualquer avaliação.

Esta pode ser uma tarefa difícil de fazer corretamente, mas deve ser interessante para qualquer um que queira fazer sua linguagem de programação mais segura e menos propensa a erros.

static

Eletricidade Estática • Uma alternativa de arrepiar os cabelos.

Tipagem Estática


Cada valor no nosso programa tem um tipo associado a ele. Sabemos isto antes de qualquer avaliação ter acontecido. Nossas funções builtin também apenas recebem certos tipos como entrada. Deveríamos ser capazes de usar esta informação para inferir os tipos de novas funções e valores definidos pelo usuário. Também podemos usar esta informação para checar se as funções estão sendo chamadas com os tipos corretos antes de rodarmos o programa. Isto reduzirá quaisquer erros decorrentes de chamar funções com tipos incorretos antes da avaliação. Esta verificação é chamada de tipagem estática.

Sistemas de tipos são uma parte interessante e fundamental da ciência da computação. Eles são atualmente a melhor maneira que conhecemos de detectar erros antes de rodar um programa. Qualquer um interessado em segurança de uma linguagem de programação deve achar este projeto realmente interessante.

Conclusão


Muito obrigado por ler este livro. Espero que você encontrou algo interessante nas suas páginas. Se você curtiu, por favor conte a seus amigos a respeito. Se você vai continuar a desenvolver sua linguagem, então muito boa sorte e espero que você aprenda muitas coisas mais sobre C, linguagens de programação e ciência da computação.

Acima de tudo, espero que você tenha se divertido construindo seu próprio Lisp. Até a próxima!

Navegação

‹ Biblioteca Padrão

• Conteúdo •

Créditos ›