Fazer é fácil, difícil é saber o que fazer

2012-10-12 02:27 -0300. Tags: comp, prog, pldesign, em-portugues

Criar uma linguagem de programação é ao mesmo tempo mais fácil e mais difícil do que parece à primeira vista. A princípio, implementar um compilador ou um interpretador para uma linguagem de programação razoavelmente útil parece uma tarefa complicada. À medida em que nos familiarizamos com o assunto, a tarefa parece cada vez mais simples. Não precisamos nos preocupar com eficiência nas versões iniciais; podemos escrever um compilador simples, que gere código da maneira mais direta (e ineficiente) possível, e depois podemos reescrevê-lo aos poucos para que gere código melhor. Parece simples, não?

E de fato é, em grande parte. Na verdade, implementar é a parte mais fácil. A parte realmente difícil de se criar uma linguagem é o design, e esta é uma coisa da qual eu nunca tinha me dado conta até tentar eu mesmo criar uma linguagem não-trivial¹. Criar uma linguagem "igual às outras" é fácil; criar uma linguagem com características que a façam valer a pena em comparação com as linguagens existentes não é uma tarefa trivial.

Há pouco mais de um ano, eu resolvi que iria criar uma linguagem Lisp-like que resolveria todos os problemas do Common Lisp. O Common Lisp existe há quase trinta anos, todo o mundo sabe que a linguagem tem problemas², e no entanto até hoje ninguém apareceu com uma alternativa compelling. Está mais do que na hora de alguém fazer isso, não?³ Eu resolvi tentar. Na pior das hipóteses, o projeto seria divertido e eu aprenderia alguma coisa com ele.

E de fato eu aprendi. Na verdade, fora alguns experimentos simples, eu quase não escrevi código nessa história. Ao invés de criar o Next Great Lisp, eu descobri que a tarefa é muito mais difícil do que parece, e ao mesmo tempo me dei conta dos porquês de diversas decisões de design do Common Lisp. Sim, Common Lisp é bizarro em vários aspectos, mas é fantástico como as diversas bizarrices interagem entre si para criar um todo mais ou menos coerente. Essa coesão não é muito óbvia, e só é realmente apreciada quando se pára para pensar a fundo sobre as coisas. Tente mudar um aspecto do design da linguagem, e a mudança implica mudar outra coisinha, que implica mudar uma terceira, e assim por diante. Algumas mudanças levam a uma reação em cadeia que acaba levando a linguagem na direção do Scheme. Algumas produzem conflitos difíceis de resolver. Algumas envolvem fazer algum tradeoff em que não é claro que caminho seguir. Enfim, não é simples. Explicar os problemas que eu encontrei exigiria explicar alguns aspectos das linguagens Lisp que talvez não sejam familiares à maioria dos leitores (fica para outro post, quem sabe); ao invés disso, oferecerei um exemplo que há de ser mais compreensível.

Recentemente andei ideando uma outra linguagem (Lisp-like, for sure). A idéia é que a linguagem fosse:

dinamicamente tipada, com declarações de tipos opcionais;
capaz de interagir transparentemente com código escrito em C;
orientada a objetos, com herança e generic functions (o equivalente Common-Líspico de métodos: funções em que os tipos dos argumentos determinam que código será chamado).

Em uma linguagem dinamicamente tipada, em geral, todo valor carrega consigo uma tag que indica seu tipo, de modo que o tipo pode ser descoberto em tempo de execução. Tipicamente, em uma arquietura de 32 bits, números inteiros simples são representados com (por exemplo) 30 bits de valor, mais 2 bits de tag, que indicam que o valor é um inteiro, e não um ponteiro ou um caractere. Operações aritméticas têm que levar em conta que os dois bits inferiores do valor são a tag, e devem ser isolados na realização da operação e mantidos no resultado. Essas operações a mais sobre o número para gerenciar a tag implicam alguma perda em performance. (Um inteiro simples com tag é conhecido como um fixnum no mundo Lisp e em Ruby.)

A idéia é que, na nossa linguagem, se o tipo de uma variável não for declarado, assume-se que ela pode conter qualquer coisa, e portanto os dados têm que carregar uma tag. Mas se a variável for explicitamente marcada com um tipo (digamos, int32), sabe-se de antemão que a variável só pode conter dados daquele tipo, e portanto uma representação "bruta" (sem tag) pode ser usada. O ganho é tanto em performance quanto em interoperabilidade com funções escritas em C, que trabalham com valores brutos. Além disso, podemos usar todos os 32 bits do valor para guardar o número, o que aumenta a faixa de representação.

Agora, se queremos ter tipos correspondentes aos do C, teremos os tipos int32 e int64 (equivalentes ao int e long long int). Se queremos manter as coisas compatíveis com o C, um número como 4 pertence a ambos os tipos. A questão é: 4:int32 e 4:int64 são valores distintos? Em uma linguagem dinamicamente tipada, o ideal é que a resposta fosse não: tudo o que importa é o valor 4. Se eu escrevo uma função:

(defun square (x: int32) -> int32
  (* x x))

eu espero que ela aceite qualquer inteiro na faixa de representação de um int32. Se o meu 4 é o resultado de uma expressão que retorna um int32 ou um int64, ou mesmo um inteiro com tag, pouco deveria importar.

(defun whatever (x:int32, y:int64, z)
  (print (square x))
  (print (square y))
  (print (square z)))

(whatever 4 4 4)

Assim, int32 é um subtipo de int64. Mas será que é isso que queremos? Imagine que nós tenhamos uma generic function:

(defun print-hex (x: int32)   (printf "%8x\n" x))
(defun print-hex (x: int64)   (printf "%16lx\n" x))

Isto é, queremos imprimir uma representação em hexadecimal dos bytes que compõem o número; o número de bytes a serem impressos depende do tipo do número. Agora, se temos o seguinte código:

(defun whatever (x: int64)
  (print-hex x))

(whatever 4)

Qual dos métodos de print-hex será chamado? Se int32 é um subtipo de int64, então o método que recebe int32 é mais específico do que o método com int64; logo, (print-hex 4) deverá sempre cair na versão com int32, o que pode não ser o comportamento desejado.

Por outro lado, se decidimos que é o método com int64 que deveria ser chamado, estamos decidindo que 4:int32 e 4:int64 são valores distintos. Isso implica que a função square apresentada anteriormente não pode ser chamada com um 4:int64, o que é um tanto quanto desagradável.

Possíveis soluções:

Manter 4:int32 e 4:int64 distintos.
- Aceitar que (square 4:int64) não vai funcionar. Incomodar-se pelo resto da vida com o fato de que as coisas não têm exatamente o tipo esperado e o compilador/runtime reclama que não encontra métodos correspondentes aos tipos passados.
- Quando uma função é chamada com int64 e não existe método para int64, mas existe para int32, fazer uma conversão automática. O problema é que outro módulo do programa (ou uma biblioteca) pode definir o método inexistente, já que métodos podem ser adicionados à generic function por outros módulos. Logo, pode ser que não se saiba em tempo de compilação se uma conversão é apropriada.
  - Uma solução seria criar implicitamente um método para int64 que faz a conversão e chama o método para int32, e permitir a redefinição de métodos por outros módulos. O sistema precisa garantir que um método definido pelo usuário terá precedência sobre o método auto-gerado (o que é importante caso o método definido pelo usuário possa ser carregado antes do auto-gerado).
Tratar 4:int32 e 4:int64 como o mesmo valor.
- Aceitar que (print-hex 4:int64) chama o método para int32. Frustrar-se ocasionalmente diante desse fato. Além disso, o fato de que int64 possui subtipos implica que se o compilador encontra código do tipo:
```
(defun foo (x: int64) -> int64
  (* 100 x))

(defun bar (y: int64) -> int64
  (foo y))
```
  ele não pode compilar a chamada a foo como uma chamada direta ao método com int64, mas sim deverá fazer uma verificação dinâmica, porque pode ser que outro módulo defina foo com int32, e nesse caso (bar 4) deverá chamar essa outra foo, pois int32 é mais específico na hierarquia de tipos.
  - Uma solução é distinguir entre métodos despachados pelos tipos estáticos dos argumentos e métodos que usam o tipo dinâmico (i.e., métodos não-virtuais e virtuais na terminologia C++). O problema é que isso afetará não só os ints, como quaisquer outras definições de foo, inclusive as que usem classes definidas pelo usuário. Not cool, if you ask me.
  - Outra solução é tratar os tipos tagged e não-tagged diferentemente: tipos tagged são despachados dinamicamente, tipos untagged estaticamente. Mas nesse caso, se o tipo estático é int32 e a função só está definida para int64, o que acontece? Conversão automática e chamada ao método com int64? Mas e se outro módulo adicionar o método com int32?
    - Tratar os ints não-tagged como exceções, e não permitir definição de métodos sobre eles em múltiplos módulos?
    - Simplesmente não permitir a definição de um método para int32 e int64 ao mesmo tempo, tornando a função print-hex impossível?
    - Tratar tipos não-tagged como não-objetos, a la C++ e Java?
    - ...?

E é assim a vida do desenvolvedor de linguagens de programação.

Notas

1 Hatter não conta como não-trivial; a linguagem é bem simples, programar nela é que não é.

2 Tenho a impressão de que na comunidade Common Lisp existe um consenso geral de que a linguagem tem problemas e que poderia ser melhor, mas ainda assim ela é melhor do que as alternativas.

3 Tentativas não faltam. Quão compelling são os resultados é subjetivo.

Comentários / Comments (1)

Masonic Press Agency | My Fraternity , 2023-03-12 02:47:49 +0000 #

Os valores maçónicos incluem a fraternidade, a igualdade, a tolerância, a filantropia e o desenvolvimento pessoal.

A Maçonaria é uma organização que busca promover o bem-estar da humanidade e da sociedade como um todo, através da prática desses valores.

A Maçonaria não é uma religião e não possui dogmas religiosos específicos.

Os membros da Maçonaria são livres para seguir a religião de sua escolha e são incentivados a respeitar as crenças religiosas dos outros. A organização valoriza a liberdade de pensamento e a busca pelo conhecimento, incentivando os membros a se desenvolverem pessoalmente e a trabalhar para o bem da humanidade.

O site "Masonic Press Agency" é uma excelente fonte de informações sobre a Maçonaria e seus valores.

Ele reúne uma vasta quantidade de informações e notícias relacionadas à Maçonaria, permitindo que os membros e não membros possam se manter atualizados sobre os acontecimentos e as práticas da organização.

Estamos disponíveis para apoiar o autor deste blog em sua busca por informações sobre a Maçonaria e seus valores.

My Fraternity | Masonic Press Agency

Elmord's Magic Valley

Computers, languages, and computer languages. Às vezes em Português, sometimes in English.