Este post é parte de uma série sobre o lash, um shell que eu estou ideando.
Hoje vamos discutir a feature que dá nome ao shell, lambdas, ou blocos. (Na verdade eu pensei no nome primeiro e fiquei com ele porque consegui pensar num significado que o justificasse, mas não vamos nos ater a esses detalhes.)
(Em diversos pontos ao longo do texto eu vou dizer que certa feature em lash "é" de tal e tal jeito. Isso só significa que essa é a minha idéia atual sobre a feature, não que eu tenha decidido definitivamente que isso vai ser assim. Comentários e sugestões são sempre bem-vindos.)
Como mencionado anteriormente, a idéia em lash é usar blocos extensivamente ao invés de sintaxe especial para estruturas de controle (if, for, while, etc.). Blocos em lash são valores de primeira classe, i.e., podem ser passados como argumento para funções, por exemplo. Um bloco instanciado é uma closure, i.e., ele lembra do ambiente de variáveis em que foi criado. No geral, variáveis em lash têm escopo léxico, e não escopo dinâmico como em (ba)sh. (A coisa não é tão simples por conta de variáveis de ambiente e outros detalhes, mas discutiremos isso no futuro.)
Blocos são escritos entre chaves ({ comandos }). Blocos podem receber parâmetros, que podem ser declarados com uma sintaxe Ruby-like: {|param1 param2 ... paramN| comandos }. O último parâmetro pode ser precedido de @; nesse caso, ele coleta em um array os argumentos restantes da chamada ao bloco.
Não sei se permitir $1, $2, etc., para acessar os argumentos de um bloco é uma boa idéia; como tudo é bloco em lash, acho que isso ia dar muita confusão ao tentar acessar um argumento de função de dentro de um if e situações similares. Melhor é requerer que os parâmetros sejam declarados. ($1 e companhia talvez possam adquirir outros usos, e.g., em matching de expressões regulares, mas esse é um tópico que eu não vou abordar any time soon.)
Now the thorny questions.
O que acontece se o número de parâmetros e de argumentos não casar? No geral o ideal é gerar um erro de execução ou um warning, mas eu me pergunto se não há situações em que pode ser interessante permitir passar um bloco sem parâmetros para uma função que chama o bloco com alguns argumentos, nos quais o bloco não tem interesse. (Por exemplo, o if poderia chamar o bloco do "then" com o resultado retornado pelo teste do if, no qual não temos interesse a maior parte do tempo.) Uma possibilidade seria não permitir mismatch, exceto no caso em que o bloco não tem declaração de parâmetros at all, i.e., {|| true; } 42 é um erro, mas { true; } 42 não é. Mas eu imagino que isso possa fazer funções declaradas sem parâmetros engolirem silenciosamente argumentos passados por engano. Por ora, acho que mismatch vai ser sempre um erro/warning mesmo, enquanto não aparecer um caso de uso que definitivamente sugira que o contrário é desejável.
Quando eu digo return 42, quem retorna? O comportamento esperado é retornar da função em que o return se encontra, mas agora o corpo de um if ou foreach tecnicamente também é uma função, que provavelmente não é a função que o usuário tem em mente ao escrever um return.
Se o return retorna da função "esperada", também há o caso em que um bloco que contém um return é passado para uma função definida pelo usuário e chamada de dentro dessa função; nesse caso o return é um non-local exit, i.e., a função que retorna é a função onde o bloco foi definido, não a função que chamou o bloco. (Na verdade o caso do return dentro do if também é um non-local exit, mas é um caso com o qual nós já estamos acostumados.) Outros casos de controle de fluxo não-local são os comandos break e continue dentro de um while. Talvez fosse interessante introduzir uma construção mais geral a partir da qual esses casos mais específicos podem ser implementados, e que também poderia ser usada para implementar exceções. Ao mesmo tempo, eu gostaria que um return fosse uma operação "barata", então é necessário tomar algum cuidado antes de sair over-engineerando controle de fluxo. A construção que naturalmente "suggests itself" para a tarefa é continuations e call/cc, mas esse caminho me dá um certa preocupação, especialmente se continuações que retornam múltiplas vezes forem permitidas. (Incidentalmente, eu pretendo implementar as versões iniciais do shell em Chicken Scheme, o que tornaria tudo isso muito simples, mas eu quero manter aberta a possibilidade de reimplementar em alguma outra linguagem no futuro (e.g., Rust, depois que ele sair de alpha).) Além disso, seria necessário lidar com unwind-protect / dynamic-wind / interação de tratadores de exceção com continuations. Eu não estou gostando muito de toda essa complexidade que surgiu do nada enquanto eu estava tranqüilo aqui inventando meu shell.
Outra dificuldade é como fazer o return, que a princípio seria um comando como qualquer outro, retornar do bloco lexicamente apropriado, já que ele não recebe como argumento nada que lhe sirva para saber de que escopo léxico ele foi chamado. Ele não pode só retornar do contexto mais no topo da pilha de chamadas porque o return pode ser não-local. Por exemplo, em um código como:
def foo {
bar {|x| return $x}
}
def bar {|block|
$block 42
}
o return que será executado quando $block for invocado deve retornar de foo, não de bar. Uma solução é fazer todo comando receber implicitamente um argumento escondido que representa o escopo em que o comando foi chamado. That's kinda weird (e me lembra o &environment das macros do Common Lisp e o "dynamic environment argument" em Kernel), mas pode funcionar. Outra solução é fazer def (o comando de definição de função) introduzir uma função local return no escopo do corpo da função, i.e., cada função vê um return diferente, mas a princípio eu não pretendia nem introduzir funções nomeadas locais (more on that later).
Também dá para simplesmente tratar def, return e companhia como special operators e era isso. Eu não queria introduzir nenhum special operator na linguagem, mas talvez isso não seja muito prático. Preciso pensar melhor sobre isso. (No fim das contas, return, break e continue trabalham com escopo léxico, enquanto exceções e unwind-protect trabalham com escopo dinâmico, então a "óbvia" unificação dos conceitos não é tão direta assim.)
A princípio o filosoficamente correto seria que definições de função tivessem escopo léxico, assim como as variáveis. Porém, me parece que coisas do tipo:
if {whatever} {
def foo {
...
}
}
que define uma função global ou não dependendo de uma condição, são comuns em scripts e bashrcs da vida. Daria para introduzir comandos separados para definir funções locais e globais, mas realmente não vejo muita utilidade para funções locais (além de blocos anônimos) em um shell. Se você discorda, por favor se manifeste.
(Por um lado dá para argumentar que se você realmente precisar de uma função local, pode declarar uma variável local e atribuir um bloco a ela. Por outro lado, há a diferença de que o return dentro de um bloco retorna da função externa, não do bloco. Essa questão do return não vai deixar de me assombrar tão cedo.)
O uso de chaves para delimitar funções conflita com o uso de chaves em bash, que expande coisas como touch {1,2,3}.txt para touch 1.txt 2.txt 3.txt, bem como coisas como {01..99} para 01 02 ... 99. Uma solução para evitar a ambiguidade é, ao encontrar um {, continuar lendo até o primeiro espaço ou }, e se houver uma , ou .. não-escapado na string lida, considerar como um brace expansion, caso contrário como um bloco. Eu detesto esses look-aheads em parsing, mas talvez seja o caminho a seguir. (O próprio bash já faz alguma distinção contextual com relação às chaves, tratando chaves em comandos como cmd arg1 {arg2 arg3 como caracteres literais, mas em bash o parsing se dá em múltiplos passos, em que primeiro ocorre word splitting e depois brace expansion, o que torna esse tipo de coisa relativamente simples. No caso de blocos, não dá para realizar word splitting primeiro porque o bloco é mais do que só uma seqüência de "words" comuns.) Outra solução é mudar a sintaxe do brace expansion, que sequer é parte do sh to begin with (é uma extensão do bash). Discutiremos alternativas quando falarmos de arrays, em um post futuro.
Comandos no Unix possuem duas formas primárias de retornar informação para o chamador:
Queremos um mecanismo que permita retornar quaisquer valores, inclusive dados estruturados como listas e blocos. Eu vejo algumas possibilidades:
A sintaxe para chamar uma função e capturar o valor de retorno por enquanto é $[comando], pelo simples fato de que ela não está sendo usada para mais nada (em bash ela é uma sintaxe deprecated para avaliação aritmética, que hoje em dia se escreve $((expressão))), e, pode-se argumentar, porque lembra a função dos colchetes em Tcl. Eu me pergunto se ${comando} não seria uma escolha melhor, pois tem mais cara de "executa este bloco e pega o valor", mas essa sintaxe é usada em (ba)sh para delimitar nomes de variável (e.g., echo "Eu sabia essa com ${fruta}s), e não sei se é uma boa mudar isso.
Uma questão é se o reply de fato retorna da função, ou só "emite" o valor de retorno. Se o mecanismo de retorno escolhido for o (1) ou o (3), faz mais sentido retornar e sair da função, mas se a escolha for o (2), faz mais sentido emitir o valor, como se fosse um print, e seguir a execução, até porque seria possível imprimir múltiplos valores, no caso do pipeline de objetos (e aí fica a questão de como $[...] se comporta se o comando emite múltiplos valores).
Por hoje ficamos por aqui. Como sempre, feedback é muito bem-vindo.
Sim, meus caros, o mui lendário e prometido shell que eu estou há anos dizendo que quero escrever está mais perto do que nunca de talvez ser escrito. Isso se deve a uma decisão de vida curiosa que me deixou com mais tempo para projetos pessoais, pelo menos por enquanto.
A questão é: tem um trilhão de decisões de design que eu preciso tomar e que eu gostaria de pensar bem sobre e discutir antes de começar a implementar. Assim, me pareceu uma boa escrever sobre elas aqui para me ajudar a organizar as idéias e coletar comentários, sugestões e opiniões. A idéia original era escrever um único post com tudo, mas eu comecei a fazer isso ontem e me dei conta de que ele ia acabar ficando gigante. Então, o plano agora é escrever uma série de posts. Neste aqui, apresentarei as idéias básicas do novo shell, e nos próximos pretendo entrar nos detalhes de features mais específicas, tais como tipos de dados, quoting, closures, estruturas de controle, módulos, escopo de variáveis e afins.
Eu já escrevi um post (gigante) sobre o assunto antes, mas basicamente: o shell é uma péssima linguagem de programação. Embora o bash tenha adquirido inúmeras features ao longo dos anos, coisas que se esperam de qualquer linguagem de programação que se leve a sério, tais como dados estruturados de primeira classe e a possibilidade de retornar valores de funções sem criar um subprocesso, não existem até hoje. Acho que existe um círculo vicioso na evolução dos shells: shells não são vistos como linguagens de programação "de verdade" por seus usuários por terem programabilidade pobre, e os desenvolvedores de shells não melhoram a programabilidade do shell porque não há demanda dos usuários. A premissa do novo projeto é romper com essa idéia e tornar o shell uma linguagem "decente" como Perl, Python ou Ruby, sem entretanto perder as características que tornam um shell conveniente, i.e., a facilidade de chamar e combinar programas de linha de comando e de utilizá-lo como uma interface interativa para o sistema operacional.
Eis uma lista das idéias básicas que hão de guiar o desenvolvimento desse novo shell.
A sintaxe de uso interativo freqüente deverá permanecer largamente igual à do (ba)sh. Coisas como redirecionamentos simples (>, >>, <), pipes, globbing (*.txt, /dev/tty[1-8]), tilde expansion (cd ~/Desktop), etc., manterão a mesma sintaxe. A sintaxe dessas coisas é tradicional demais (e familiar até a usuários de ambientes não-Unix), então me parece melhor mantê-la igual, mesmo que isso limite as escolhas sintáticas para outras funcionalidades do shell.
Dito isto, compatibilidade com (ba)sh não é um objetivo do shell. A manutenção da sintaxe das funções mais comuns é mais uma questão de compatibilidade com os usuários de shell do que com os shells propriamente.
Uma das features mais importantes do shell novo é o suporte a dados estruturados de primeira classe. Isto é, arrays e dicionários podem ser armazenados em variáveis, dentro de outros arrays e dicionários, passados como argumento para funções, retornados por funções, etc. Isso implica a adição de um mecanismo para retorno de valores complexos por funções, bem como uma sintaxe para chamar uma função e capturar seu valor de retorno, sem criar um subshell para isso (diferente do $(...) do (ba)sh).
Outra feature importante é o suporte a closures, ou blocos de código de primeira classe. Isso permite a substituição de diversas estruturas de controle que têm sintaxe especial no (ba)sh (if, for, while, etc.) por comandos simples que recebem blocos de código como argumento, e também permite que novas estruturas de controle sejam definidas pelo usuário.
O suporte a closures e a funções com valores de retorno complexos nos possibilita fazer uma grande limpeza na sintaxe do shell, substituindo certos elementos de sintaxe questionável (e.g., ${var,,*}) por equivalentes mais legíveis (e.g., $[lowercase $var]). A idéia é inicialmente ter o mínimo de sintaxe especial. Porém, sintaxe minimalista não é necessariamente um princípio sagrado, e se for observado que algumas operações são freqüentes o suficiente para justificar uma sintaxe especial, tal sintaxe pode vir a ser acrescentada ao shell.
O shell deve facilitar a escrita de scripts robustos. Em (ba)sh é muito fácil escrever um script que aparentemente funciona corretamente, mas falha diante de nomes de arquivo com espaços ou quebras de linha, ou comandos que usam * ou ? com seu sentido literal e funcionam 99% do tempo, mas falham misteriosamente ocasionalmente, porque coisas como *~ são mantidas intactas pelo (ba)sh quando não há nenhum arquivo que case com o padrão, o que faz com que o comando funcione ou não dependendo do conteúdo do diretório atual, ou porque o (ba)sh expande caracteres epeciais em situações inesperadas. O shell deve ter um comportamento consistente, fácil de "reason about", sem dependências mágicas de contexto e do ambiente do usuário.
Uma preocupação secundária mas importante é que o shell deve ser razoavelmente rápido. Não necessariamente rápido como uma chita, mas idealmente com uma performance equiparável à de Python ou Ruby. (Isso não precisa ser uma preocupação inicialmente, mas é bom mantê-la em mente durante o design da linguagem.) O bash é absurdamente lento, e shell scripts em geral tendem a ser lentos por terem que usar comandos externos para diversas coisas que em outras linguagens seriam builtins ou bibliotecas. O que nos leva ao próximo item...
O shell deve ter suporte a bibliotecas, módulos ou algo do tipo para reuso de código. Idealmente, também deve ser possível escrever bibliotecas/módulos compilados que possam ser utilizados por scripts. Isso permite a adição de features sem engordar o shell. Deve ser fácil distribuir e instalar bibliotecas para o shell. Idealmente, também deve ser fácil determinar e instalar (semi-)automaticamente as bibliotecas das quais um script depende. Deve ser possível isolar namespaces para evitar conflitos de nomes.
Finalmente, features interativas, como edição de comandos e histórico, não devem ser parte do core do shell. Com suporte a bibliotecas/módulos, não há por que colocar essas funcionalidades no binário principal e carregá-las ao rodar scripts, que não precisam delas.
O fato de que o shell deve ser conveninete de usar interativamente, e de que desejamos manter um mínimo de "compatibilidade de usuário" com a sintaxe tradicional do sh, impõe certas restrições nas escolhas sintáticas do shell. Por exemplo, em uso interativo, strings literais são mais freqüentes do que variáveis, então faz sentido que strings não exijam aspas e variáveis sejam introduzidas por um símbolo especial ($). < e > possuem significados convencionais, então embora às vezes seja muito tentador utilizá-los como delimitadores para alguma outra coisa, o melhor é deixá-los em paz.
Essas restrições fazem com que seja difícil escolher uma sintaxe para certas features que seja "ergonômica" para programar e ao mesmo tempo não interfira e se encaixe direito com o resto do shell. Até hoje eu não encontrei uma sintaxe para capturar o resultado de uma função que me agrade totalmente, por exemplo.
Dito isso, embora eu seja da opinião de que "syntax matters", eu cheguei à conclusão de que, pelo menos inicialmente, considerações sintáticas não são tão importantes assim, já que em geral a sintaxe pode ser alterada mais adiante sem muito impacto no resto do projeto (pelo menos enquanto ele não for oficialmente released e não tivermos que lidar com esse negócio de "usuários"). Assim, vou aceitar por ora uma certa dose de bizarrice sintática quando não houver uma escolha obviamente melhor, deixando aberta a possibilidade de mudanças futuras.
Um outro fator ao qual eu pretendo dar um peso importante ao definir a sintaxe é o que podemos chamar de dificuldade de interpretação incorreta. Por exemplo, eu costumava não ir muito com a cara do uso de my em Perl para declarar variáveis locais, mas ele tem o mérito de deixar claro (para mim, pelo menos) que trata-se de uma declaração de variável (e não uma atribuição a variável já existente), e que o escopo dela é o bloco em que se encontra (e não a função ou o módulo ou whatever). let também é relativamente claro, mas let é um comando que faz algo diferente em bash (avaliação de expressões aritméticas e atribuição (não declaração)), então talvez seja melhor evitar essa palavra (mas ainda estou meio em dúvida).
Um contra-exemplo é a sintaxe para declaração de variáveis de ambiente temporárias: em um comando como
LC_ALL=C find /home | grep '[^A-Za-z0-9]'
o LC_ALL=C vale só para o find, ou para o grep também? (Resposta: só para o find.) Em um comando como
foo=42 echo $foo
$foo está no escopo da definição ou não? (Resposta: não.) No geral, acho preferível escolher uma sintaxe que não deixe dúvida de qual é a interpretação correta. Similarmente, se alguma distinção é importante, pode ser melhor obrigar o usuário a especificá-la ao invés de usar um default que freqüentemente pode não ser o que o usuário quer, ou que pode induzir ao erro alguém lendo o código escrito por outra pessoa. Por exemplo, eu não pretendo ter uma função len para strings no shell, mas sim funções como bytelen (número de bytes), charlen (número de codepoints Unicode) e charwidth (largura do texto na tela), exigindo que o programador seja específico quanto a o que quer dizer com "comprimento" da string. (Esses nomes ainda são meio questionáveis, pois o encoding das strings (que supostamente é UTF-8) fica implícito, mas ainda não pensei com calma sobre o assunto.)
Embora por enquanto nada esteja muito bem definido, para tornar as coisas um pouco mais concretas, eis um exemplo da cara que eu imagino que a tal linguagem vai ter:
# Função que retorna um dicionário contendo a quantidade de usuários
# que usam cada shell.
def count_shell_users {
my counts = %()
each_line </etc/passwd {|line|
my (user pass uid gid name home shell) = $[split $line ":"]
counts{$shell} = $(( $[or $counts{$shell} 0] + 1 ))
# (A sintaxe da linha acima provavelmente não é definitiva.)
}
reply $counts
}
# Função que retorna todos os elementos de uma lista que satisfaçam um predicado.
def filter {|list predicate|
my result = ()
each $list {|item|
if {$predicate $item} {
push $result $item
}
}
reply $result
}
# Exemplo de uso.
my dirs = $[filter (/etc/*) {|x| isdir $x}]
Por hoje ficamos por aqui. Nos próximos episódios trataremos de tópicos mais específicos. Perguntas, sugestões, opiniões, comentários, tanto sobre os tópicos abordados quanto sobre outras coisas que você gostaria de ver (ou não) num shell, são muito bem-vindos.
(By the way, não havendo conflito com nenhum projeto ativo, o shell a princípio deverá se chamar lash (lambda shell).)
Essa história de Heartbleed me lembrou de algumas coisas que eu tinha pensado meses atrás e não lembrava mais.
Para quem não sabe, o Heartbleed (concisamente explicado por este quadrinho do xkcd) é uma falha de segurança na OpenSSL (uma biblioteca que implementa os protocolos de comunicação segura SSL e TLS usada por basicamente todo o mundo) que permite a um atacante obter porções da memória do servidor potencialmente contendo dados como nomes de usuários, senhas, a chave privada do certificado servidor, etc.
Como 237% das falhas de segurança de software encontradas nos últimos 30 ou 40 anos, o Heartbleed é causado por um buffer overflow (tecnicamente "overread", pois trata-se de leitura e não escrita), e teria sido evitado se a OpenSSL tivesse sido escrita em uma linguagem que fizesse verificação de limites (bounds checking) antes de acessar uma posição de um vetor.
No fórum do xkcd, alguém escreveu:
Heartbleed is yet another example of why coding in C is a bad idea. A memcpy with an incorrect size caused all this because C compilers do no bounds checking. Heartbleed wouldn't have happened if OpenSSL had been written in, for example, Ada. Instead of an information leak that leaves no trace it would have been a denial of service at the worst.
Mais adiante na thread, alguém respondeu:
It's yet another example of why poorly written code is a bad idea. No amount of programming languages and frameworks is going to protect you from incompetent programmers.
A essa altura eu fechei a tab e fui ler outras coisas, porque se eu continuasse ali eu ia acabar respondendo com o equivalente virtual do soco na cabeça pra desentupir o cérebro. Isso é mais ou menos como ter um viaduto do qual diariamente caem carros há trinta anos, e se recusar a colocar um muro de proteção nas bordas, porque se alguém cai "a culpa é do motorista que foi incompetente".
Se bounds checking é uma coisa tão mágica, por que não está todo o mundo usando linguagens que fazem bounds checking? A resposta, obviamente, é performance, a propriedade mais importante de qualquer software. Does it work? No, but it's fast! Ok, chega de comentários sarcásticos por ora. Eu já falei sobre a performance de bounds checking em um post anterior, onde fiz alguns benchmarks com código em C com e sem bounds checking (implementado manualmente com ifs no código testando se o índice está dentro dos limites do vetor e abortando a execução caso contrário). As conclusões no final foram que:
Do segundo item depreende-se que um acesso bounds-checked a um vetor é cerca de 25% mais lento do que um acesso direto. Assumindo que a maioria dos programas não consiste primariamente de acessos a vetores, esses 25% talvez não fizessem tanta diferença, e o benefício seria maior que o custo. (Disclaimer: talvez no caso geral o slowdown seja maior que 25%. Talvez eu faça mais uns benchmarks, só para não perder o costume, quando estiver mais disposto. Read on.)
O primeiro item é mais interessante: em algumas circunstâncias é possível provar que todos os acessos a um vetor estarão dentro dos limites, e nesses casos não é necessário fazer qualquer verificação em tempo de execução. Por exemplo (assumindo uma função hipotética length_of, que retorna o comprimento de um vetor), em um loop como:
for (i=0; i < length_of(vector); i++)
printf("%d", vector[i]);
não é necessário verificar em tempo de execução se vector[i] está dentro dos limites do vetor, pois é possível ao compilador provar em tempo de compilação que i só adquire valores que são índices válidos do vetor. Para casos simples como esse, o gcc e outros compiladores já são capazes de fazer esse tipo de análise estática, como visto no post linkado; não se trata de uma tecnologia mítica e utópica. Os problemas começam a surgir quando temos coisas como:
int get(int vector[], int i) {
return vector[i];
}
void foo() {
...
for (i=0; i < length_of(vector); i++)
printf("%d", get(vector, i));
}
pois a função get não sabe que será chamada com um índice válido. Se o compilador fizer inlining de get no corpo de foo, ele será capaz de eliminar o bounds checking, mas, no caso geral, não queremos sempre fazer inlining (get poderia ser uma função grande chamada em diversos pontos do código, por exemplo), e a função get (que poderia ter sido compilada separadamente) não pode assumir que quem a chamar lhe passará um índice válido.
Mas ela pode exigir. Imagine que pudéssemos escrever algo do tipo:
int get(int vector[n], int i)
i>=0 && i<n;
{
return vector[i];
}
i>=0 && i<n é parte da assinatura da função: além de ela exigir que o primeiro argumento seja um vetor de int e o segundo um int, ela também exige que a condição especificada seja satisfeita. Com isso: (1) a função pode assumir que a condição é verdadeira dentro do corpo, eliminando assim o bounds checking; e (2) o encargo de testar se a condição é verdadeira é passado para o chamador da função (foo, no nosso exemplo), onde há contexto suficiente para determinar se a condição é sempre verdadeira em tempo de compilação (por conta de ocorrer dentro do for, no nosso exemplo). Se esse for o caso, o bounds check pode ser eliminado do programa; caso contrário, o check é realizado em tempo de execução, garantindo que o acesso será seguro.
Mesmo em loops em que o range não está evidentemente nos limites do vetor é possível utilizar uma pequena dose de falcatrua para "amortizar" os checks. Por exemplo, em uma função como:
int sum(int vector[], int start, int end) {
int i, total=0;
for (i=start; i<=end; i++)
total += vector[i];
return sum;
}
não é possível eliminar completamente o checking, pois não sabemos de antemão se start e end é uma faixa válida de índices do vetor. Mas nem por isso precisamos fazer o checking dentro do loop. Ao invés disso, podemos transformar o código em:
int sum(int vector[], int start, int end) {
int i, total=0;
int length = length_of(vector);
if (start < 0) out_of_bounds_exception();
if (end >= length) out_of_bounds_exception();
for (i=start; i<=end; i++)
total += vector[i];
return sum;
}
Se a execução passar dos ifs, então start e end são índices válidos no vetor, e não precisamos executar testes para cada acesso.
Só tem um pequeno problema na transformação acima: ela encerra o programa se end estiver além dos limites do vetor mesmo antes de vetor[end] ter sido acessado; basicamente uma exceção que ainda não aconteceu encerra o programa. Neste programa em particular isso não chega a ser um problema pois o comportamento observável do programa seria o mesmo, mas isso não é válido no caso geral. Por exemplo, poderia ser que eu soubesse de antemão que o vetor é encerrado por um valor 0, e escrevesse o código como:
int sum(int vector[], int start, int end) {
int i, total=0;
for (i=start; i<=end; i++) {
if (vector[i] == 0) break;
total += vector[i];
}
return sum;
}
Nesse caso, mesmo que eu passe um end inválido, pode ser que o meu programa termine com um resultado correto, desde que o vetor seja devidamente terminado com um 0. O compilador não tem dados suficientes para provar que o vetor terá o 0, entretanto, e portanto checks precisam ser inseridos. Ainda assim, é possível transformar o código em algo como:
int sum(int vector[], int start, int end) {
int i, total=0;
int length = length_of(vector);
if (start < 0) out_of_bounds_exception();
int bounded_end = min(end, length-1);
for (i=start; i<=bounded_end; i++) {
if (vector[i] == 0) break;
total += vector[i];
}
if (end>bounded_end && i>bounded_end) out_of_bounds_exception();
return sum;
}
que é menos trivial (e provavelmente pode ser escrito de maneira mais eficiente, mas menos clara para fins de exposição), mas preserva a semântica do programa (a prova é sugerida como exercício para o leitor).
Nem sempre os índices de vetores provêm de ranges seqüenciais. Um exemplo em que isso não ocorre é em uma busca binária, em que, para eliminar os checks, o compilador precisaria conseguir provar que (min+max)/2 está entre min e max*.
Outra situação é quando criamos um vetor de lookup reverso r que mapeia os valores de um vetor v aos índices correspondentes, i.e., se v[1] = 42, então r[42] = 1. Nesse caso, para eliminar os checks, o compilador precisa ter informação suficiente para saber que os valores de v são sempre índices válidos em r. O que pode ser viável se o tipo de v indicar qual é a faixa de valores válidos que o vetor pode conter. De qualquer forma, é interessante que esse tipo de assumption usualmente escondida sobre o comportamento do programa seja explicitamente expressível na linguagem, especialmente se tais declarações (1) não forem obrigatórias, e (2) forem usadas para melhorar performance. (Side-effect: as pessoas seriam incentivadas a documentarem melhor seus programas visando ganhar performance. Todos comemora.)
Bounds checking é só um componente de memory-safety. Outro aspecto importante é garantir que os ponteiros/referências apontam de fato para objetos válidos em memória, e não para áreas que já foram desalocadas (ou pior, realocadas para outros objetos). A solução clássica para o problema é gerência automática de memória com garbage collection, mas há outras soluções possíveis.
O fato de que, com a introdução de pré-condições, os tipos das funções falam mais sobre o que a função faz, provavelmente implica que os tipos das funções mudam com mais freqüência quando uma função é alterada, efetivamente alterando sua interface, uma vez que cabe ao chamador da função garantir que as pré-condições são satisfeitas. Isso torna mais provável que uma alteração em uma biblioteca exija a recompilação de todo o mundo que depende dela. A solução que eu proponho é distribuir tudo como bytecode e (re)compilar para código nativo transparentemente as needed (o que tem inúmeras outras vantagens, tais como não fixar a ABI, permitir compilar o código com ou sem certs instruções (e.g., SSE) dependendo de sua disponibilidade no processador, permitir se aproveitar de mandingas brabas dependentes de uma versão da arquitetura (e.g., assumir que ponteiros têm efetivamente 48 bits e não 64 no amd64) sem se preocupar se daqui a 5 anos elas não vão mais funcionar, pois o ambiente pode simplesmente testar se uma assumption é válida e recompilar caso contrário, etc.). Uma solução alternativa é the C++ way: não fazer nada a respeito.
1. Bounds checking, galera. De uma vez por todas. Entre acidentes e talvez-nem-tão-acidentes, depois de 30 anos tá na hora de a gente aprender, não?
2. Bounds checking não necessariamente implica perda de performance, pois o compilador pode determinar que certos checks não são necessários em tempo de execução. Em uma linguagem sem bounds checking, o programador tem que ou inserir os checks manualmente anyway para garantir que não ocorrerá nenhum buffer overflow, ou concluir que o check não é necessário pois o índice está garantidamente dentro do vetor. No primeiro caso o check está lá anyway com ou sem bounds checking automático; com o check automático não há o risco de o programador esquecer de fazer o teste. No segundo caso o programador pode (idealmente) escrever explicitamente o raciocínio que permite concluir que o check é desnecessário, o que, além de menos error-prone (já que, se o compilador não for capaz de concluir que o raciocínio é válido, seja porque o raciocínio está errado ou porque o compilador não é suficientemente esperto, ele vai inserir o check dinâmico), é benéfico do ponto de vista de engenharia de software.
P.S.: Idéias similares às apresentadas neste post já foram inventadas e reinventadas mais de oito mil vezes sob os nomes de dependent types, design by contract, e sabe-se lá mais que outros (sinta-se à vontade para citar referências nos comentários). É por este motivo que, embora o tópico seja perfeitamente o tipo de coisa na qual eu gostaria de trabalhar, eu provavelmente não vou nem tentar empurrar o tema da minha dissertação de mestrado para esse caminho. Mais sobre isso em um post futuro, talvez.
_____
* Ou ser informado disso pelo programador, como um "axioma" sem prova. Nesse caso introduz-se uma fonte bastante perigosa de potenciais bugs, pois um axioma incorreto poderia levar a transformações de código incorretas em pontos arbitrários do programa. Uma solução semi-aceitável neste caso particular é ter uma função na biblioteca padrão da linguagem que calcula a média de dois números, acompanhada de um axioma sobre o resultado. O problema é que se a habilidade de declarar axiomas sem prova for introduzida na linguagem, é praticamente certo que alguém vá usá-la incorretamente e criar outro Heartbleed. Outra alternativa é introduzir um meio de o programador escrever a prova do axioma, que o compilador seria então capaz de verificar. Isto é nada mais, nada menos do que uma aplicação de proof-carrying code.
Este post relata o que eu aprendi tentando misturar (ou combinar) uniões de tipos e polimorfismo paramétrico na mesma linguagem. Faz tempo que eu não escrevo um post de 20k que ninguém vai ler, então aproveito a oportunidade para documentar essas coisas todas antes que eu as esqueça. Este post está sujeito a alterações futuras (dada a impossibilidade técnica de produzir alterações passadas) caso eu lembre de mais algum detalhe.
Para quem não sabe, meu tema de TCC é criar uma linguagem de programação funcional didática. A motivação por trás disso é reduzir os problemas encontrados pelos alunos da disciplina de Fundamentos de Algoritmos (da qual eu fui monitor por três anos) com a linguagem Scheme/Racket (especificamente, com as linguagens didáticas do How to Design Programs, doravante HtDP).
Um dos problemas com essas linguagens é a falta de um sistema de tipos estático. Como conseqüência, as funções e estruturas no código escrito na disciplina normalmente são acompanhadas de um pequeno comentário em um formato semi-padrão indicando os tipos dos parâmetros e retorno das funções, campos de estruturas, etc. O problema é que essa informação não é usada pela linguagem, o que significa que (1) ela não é lá muito útil; (2) conseqüentemente os alunos tendem a não escrevê-la; (3) não há qualquer validação sobre o formato dos comentários, o que impede os alunos de "testar" se eles estão corretos. Para resolver isso, a nova linguagem (que, por motivos de piada interna maior, chama-se Faz), é estaticamente tipada e permite (na verdade exige) declarar os tipos das funções e estruturas.
O problema é que diversos exercícios do HtDP utilizam tipos mistos. Tipos mistos são uma maneira semi-formal de descrever os tipos de funções e de dados freqüentemente utilizados em linguagens dinamicamente tipadas. Por exemplo, se uma função área aceita como argumentos quadrados e círculos, pode-se definir um tipo misto "forma" constituído por quadrados e círculos e dizer que a função recebe uma forma e produz um número. No HtDP, tipos mistos são "definidos" por meio de comentários no código.
A maioria das linguagens estaticamente tipadas não permite definir tipos mistos dessa maneira. Ao invés disso, a maioria das linguagens funcionais estaticamente tipadas permitem a declaração de uniões etiquetadas (tagged unions), ou sum types. Por exemplo, em Haskell, um tipo para formas poderia ser escrito como:
data Forma = Retangulo Float Float
| Circulo Float
A declaração define o tipo (Forma) e os possíveis construtores de valores desse tipo (Retangulo, Circulo) e os tipos dos campos de cada construtor. Para criar um valor, escreve-se uma chamada ao construtor, tal como Retangulo 2 3 ou Circulo 4.
Uma união etiquetada é diferente de um tipo misto porque o tipo misto não exige uma etiqueta; é possível definir um tipo misto "número-ou-string" consistindo de números ou strings, por exemplo, sem definir novos construtores para o tipo novo. Embora a diferença possa parecer trivial, em muitos casos a ausência de tags é bastante conveniente. Por exemplo, alguns exercícios do HtDP definem uma "página Web" como uma lista contendo símbolos (palavras) e outras páginas Web (subpáginas). (I know, I know.) Um exemplo de "página Web" seria algo como:
(list 'Eis 'um 'exemplo 'de 'página 'web
(list 'the 'quick 'brown 'fox 'had 'better 'things 'to 'do)
(list 'whatever 'whatever 'bla))
Em Haskell, uma definição para esse tipo de dados ficaria algo como:
data Webpage = List [WebpageContent] data WebpageContent = Word String | Sub Webpage
E o exemplo ficaria:
List [Word "Eis", Word "um", Word "exemplo", Word "de", Word "página", Word "web",
Sub (List [Word "the", Word "quick", Word "brown", Word "fox", Word "had",
Word "better", Word "things", Word "to", Word "do"]),
Sub (List [Word "whatever", Word "whatever", Word "bla"])]
Que é "um pouco" menos conveniente. Poder-se-ia argumentar que a escolha de representação é tosca, mas de qualquer forma, uma vez que o meu objetivo era permitir transcrever os exercícios do HtDP para Faz com o mínimo de turbulência, eu queria encontrar alguma maneira de integrar os tipos mistos do HtDP na linguagem da maneira mais direta possível.
Então pensei eu: e que tal se adicionarmos uniões de tipos na linguagem? Uniões representam diretamente a idéia de tipos mistos. O usuário simplesmente diz:
tipo Coisas = Números U Strings
e agora 42 e "foo" pertencem ao tipo Coisas, sem necessidade de declarar tags. (Por baixo dos panos, a implementação guarda "tags" para saber os tipos dos valores, como em qualquer linguagem dinamicamente tipada, mas isso é um detalhe de implementação que não interessa ao usuário.) Simples, hã? Agora temos tipos mistos e tipagem estática. (By the way, a declaração acima é válida em Faz.)
Estranhamente, entretanto, aparentemente nenhuma linguagem estaticamente tipada usada por mais do que duas pessoas suporta uniões de tipos. Por que será?
Haskell e companhia suportam uma coisa chamada de polimorfismo paramétrico (também conhecida por tipos genéricos no mundo C++/Java). Nessas linguagens é possível declarar coisas como "listas de α, para todo α", ao invés de declarar um tipo novo para cada tipo de lista que se deseja utilizar. Também é possível escrever funções de tipos genéricos. Por exemplo, uma função para incluir um elemento em uma lista nessas linguagens possuiria um tipo como (α, lista de α) → lista de α, i.e., uma função que recebe um argumento de um tipo α qualquer, uma lista de elementos do mesmo tipo α, e produz uma lista do mesmo tipo. Uma função que implementa o operador de composição de funções (f∘g), i.e, que recebe duas funções e produz uma terceira função que é equivalente a aplicar a segunda sobre o resultado da primeira, teria um tipo como (α→β, β→γ) → (α→γ), indicando que as funções podem ser de quaisquer tipos, mas o resultado da primeira tem que ser do mesmo tipo do argumento da segunda (β), e a função resultante recebe um argumento do mesmo tipo do da primeira (α) e produz um resultado do mesmo tipo do da segunda (γ).
A verificação/inferência de tipos nessas linguagens é feita usando o famoso Hindley-Milner type system e extensões do mesmo. Os detalhes podem ser um pouco sórdidos, mas, a menos que eu esteja viajando completamente, a idéia do Hindley-Milner é extremamente simples: ao checar uma expressão, gera-se uma lista de constraints (restrições) que devem ser satisfeitas para que a expressão esteja bem tipada. Por exemplo, se temos as seguintes funções (e respectivos tipos):
compose : (α→β, β→γ) → (α→γ) bool_to_int : bool→int int_to_string : int→string
então uma chamada como compose(bool_to_int, int_to_string) só é bem-tipada se:
α→β = bool→int β→γ = int→string
Esta é a lista de constraints que devem ser satisfeitos. Do primeiro constraint, tem-se que:
α = bool β = int
e do segundo,
β = int γ = string
Como não há conflito entre os constraints, tem-se que a expressão é bem-tipada, e o tipo da chamada é α→γ = bool→string. Por outro lado, uma chamada como compose(bool_to_int, bool_to_int) produziria os constraints:
α→β = bool→int => α = bool
β = int
β→γ = bool→int => β = bool
γ = int
que não podem ser satisfeitos, e portanto a expressão é mal-tipada.
O Hindley-Milner foi feito para resolver constraints de igualdade. Em uma linguagem com relações de subtipagem (e.g., em que se pode declarar um tipo funcionário como subtipo de pessoa), aplicações de função não exigem mais que os tipos dos argumentos sejam iguais aos declarados para os parâmetros, mas sim que eles estejam contidos nos tipos dos parâmetros. Por exemplo, se pessoa tem os campos nome e idade, e funcionário tem os campos nome, idade e salário, então uma função como obtém_idade, do tipo pessoa → int, pode receber tanto pessoas quanto funcionários como argumentos.
E a presença de uniões de tipos basicamente introduz relações de subtipagem da maneira mais desenfreada possível: quaisquer dois tipos A e B possuem um supertipo comum, A U B. Isso significa que se temos uma função f do tipo (α, α) -> α, uma chamada como f(1, "foo") produz os constraints:
int ⊆ α strings ⊆ α
que é satisfatível com α = int U string. Note que, na verdade, int U string é apenas um limite inferior para α: qualquer outro supertipo, como int U string U char, ou ⊤ (top, o supertipo de todos os tipos), também serviria. Porém, intuitivamente int U string é o tipo mais "útil" inferível para a expressão, no sentido de que é o que mantém a informação mais precisa de que tipo de coisas se pode fazer com o resultado.
Nem sempre, entretanto, existe um único tipo "mais útil". A relação de subtipagem entre tipos funcionais possui uma propriedade curiosa: um tipo Sparam → Sreturn é subtipo de Tparam → Treturn, ou
Sparam → Sreturn ⊆ Tparam → Treturn
se
Tparam ⊆ Sparam e Sreturn ⊆ Treturn .
[Para entender essa inversão, você pode pensar assim: um tipo (S) é subtipo de outro (T) se S puder ser usado em qualquer lugar que T possa ser usado (e.g., funcionário é um tipo de pessoa porque um funcionário pode ser usado em qualquer lugar em que uma pessoa pode ser usada). Para que uma função (f) possa ser usada no lugar de outra (g), ela não pode exigir mais do argumento do que a outra, mas pode exigir menos (e.g., se g espera funcionários, então uma função que espere pessoas pode ser usada em seu lugar, pois funções que esperam pessoas também aceitam funcionários). Por outro lado, f tem que produzir um resultado tão bom ou melhor do que o da função que ela está substituindo (e.g., se g produzia pessoas, então f tem que produzir uma pessoa ou um funcionário, pois quem vai usar o resultado da função espera trabalhar com o resultado como se ele fosse uma pessoa).]
Agora imagine que temos uma função f do tipo (α→α) → (α→α), e uma função g do tipo int U string → int. A chamada f(g) produz o constraint:
int U string → int ⊆ α → α
de onde tem-se:
α ⊆ int U string int ⊆ α
Tanto α = int quanto α = int U string são soluções válidas para os constraints, e nenhuma é evidentemente melhor que a outra.
Coisas como a chamada compose(bool_to_int, int_to_string) da seção anterior agora produzem constraints do tipo:
α ⊆ bool int ⊆ β β ⊆ int string ⊆ γ
Destas, a única variável cujo tipo é fixado pelos constraints é β; as outras duas só possuem upper e lower bounds. Novamente, a solução "óbvia" ou "mais útil" seria α = bool, γ = string. Formalizar o "mais útil" no caso geral, entretanto, é um problema não-trivial e, como visto, nem sempre existe solução (o que fazer nesses casos é uma boa pergunta).
No Hindley-Milner, sempre que o constraint solver encontra um constraint da forma variável = whatever, ele substitui todas as ocorrências da variável por whatever no tipo e nos demais constraints, mesmo que whatever seja outra variável. Isso é válido porque os constraints são igualdades. No mundo da subtipagem, entretanto, igualar as variáveis nem sempre é a melhor solução. Por exemplo, considere as seguinte funções, escritas em um pseudocódigo funcional esquisito:
foo(f: α→β, g: α→γ, h: α→γ, k: β→γ) : Tripla(α→γ, α→γ, α→γ)
= Tripla(compose(f, k), g, h)
jogo_do_pim(x: Int) : Int U String
= if x mod 4 ≠ 0 then x
else "pim"
jogo_do_pi(x: Int) : Int U String U Char
= if x == 4 then 'π'
else if x mod 4 ≠ 0 then x
else "pim"
id(x: ι) : ι
= x
(Procurando por "jogo do pim" na Web encontrei um negócio interessante.) Agora, queremos tipar a chamada:
foo(jogo_do_pim, jogo_do_pi, id, id)
que produz os seguintes constraints, um para cada parâmetro/argumento (note que cada ocorrência de id usa variáveis de tipo separadas; caso contrário, todas as chamadas de id do programa teriam que ter o mesmo tipo):
Int → Int U String ⊆ α → β Int → Int U String U Char ⊆ α → γ ι → ι ⊆ α → γ ι′ → ι′ ⊆ β → γ
Digerindo esses constraints, temos:
α ⊆ Int Int U String ⊆ β α ⊆ Int Int U String U Char ⊆ γ α ⊆ ι ι ⊆ γ β ⊆ ι′ ι′ ⊆ γ
Se fôssemos igualar variáveis a la Hindley-Milner, teríamos, pelos dois últimos constraints, que α = γ e β = γ, e portanto α = β, mas não é possível resolver os constraints assim, pois α ⊆ Int e Int U String ⊆ β. Uma solução válida é:
α = Int β = Int U String γ = Int U String U Char
o que exemplifica que identificar/unificar as variáveis em constraints da forma α ⊆ β não é uma boa idéia na presença de union types (ou subtipagem em geral). Isso significa que podemos dar tchau para o Hindley-Milner. Só que agora temos um bocado de problemas. Por exemplo, suponha que temos os seguintes constraints:
α ⊆ Listas de β β ⊆ Listas de α
Isto é um ciclo, que produziria um tipo infinito, o que em princípio é um erro. O Hindley-Milner facilmente detecta esta situação: ao encontrar o primeiro constraint, ele substitui todas as ocorrências de α por Listas de β, e o segundo constraint fica β ⊆ Listas de Listas de β. De forma geral, um ciclo sempre leva em algum ponto a um constraint em que a mesma variável aparece dos dois lados, o que é fácil de detectar. Sem igualamento de variáveis, essa abordagem não funciona.
Side note: para evitar a unificação, uma coisa que eu tinha pensado era, ao encontrar constraints do tipo α ⊆ Listas de β, substituir todas as ocorrências de α por Listas de α′, refletindo o fato de que se sabe que α é uma lista, mas não se sabe ainda de quê. O problema é que nesse caso o algoritmo entra em loop, pois:
α ⊆ Listas de β => Listas de α′ ⊆ Listas de β (expansão de α)
β ⊆ Listas de α β ⊆ Listas de Listas de α′
=> α′ ⊆ β (cortando o construtor comum)
β ⊆ Listas de Listas de α′
=> α′ ⊆ Listas de β′
Listas de β′ ⊆ Listas de Listas de α′ (expansão de β)
=> α′ ⊆ Listas de β′
β′ ⊆ Listas de α′ (cortando o construtor comum)
(... and so on ...)
Problema dos ciclos à parte, como devemos tipar uma expressão como compose(id, id)? A expressão produz os seguintes constraints:
α ⊆ ι ι ⊆ β β ⊆ ι′ ι′ ⊆ γ
Qual é a solução? Unificar as variáveis? Mas em quais casos é correto unificar e em quais não é?
A existência de uniões de tipos torna possível declarar coisas como:
f(x: Par(Int, α) U Par(α, String)) : α
= if x.first ∈ Int then x.second
else x.first
Agora se chamarmos f(Par(5, "foo")), qual é a instanciação correta para tipo de x? α = Int ou α = String? Uma solução é detectar esse tipo de coisa e proibir que o mesmo tipo paramétrico apareça múltiplas vezes em uma união com um argumento que alterna entre concreto e abstrato. Da mesma forma, parâmetros de tipos como Int U α devem ser proibidos, pois a instanciação de α é ambígua quando o argumento é Int. E α U β também é ambíguo, pois para qualquer instanciação, a instanciação "flipada" (trocando os valores de α e β) também é válida. Supostamente essas restrições resolvem o problema, mas eu não estou quite sure quanto a isso.
Com o tempo limite para concluir o TCC se aproximando e a minha paciência/interesse no problema acabando, o que eu acabei fazendo foi um sério corte orçamentário na utilização de tipos paramétricos e uniões na linguagem. Para evitar o problema da unificação de variáveis, os casos em que ela é necessária são simplesmente proibidos: constraints da forma X ⊆ Y em que tanto X quanto Y contêm variáveis abstratas de tipos são rejeitados pelo typechecker. Isso significa que coisas como compose(id, id), em que tanto o parâmetro (α→β) quanto o argumento (ι→ι) são polimórficos, são rejeitadas. É tosco, mas pelo menos some com o problema. Além disso, uniões de tipos paramétricos também possuem algumas restrições (que eu ainda não defini direito, para ser sincero; quando eu terminar o TCC pode ser que eu edite esta seção).
Certa vez um sábio disse o seguinte:
Follow! But follow only if ye be man of valour! For the entrance to this cave is guarded by a creature, so foul, so cruel, that no man yet has fought with it and lived! Bones of full fifty men are strewn about its lair! So, brave knights, if you do doubt your courage or your strength come no further, for death awaits you all, with nasty, big, pointy teeth...
Acredito que ele estava falando de union types.
As linguagens orientadas a objetos convencionais são o que podemos chamar de noun-centric: as classes são a "unidade estrutural" mais importante, e os métodos (verbos) pertencem a classes (nomes). Um método é chamado sobre exatamente um objeto, e a escolha de que código será executado para a chamada depende da classe do objeto sobre o qual o método é chamado. A sintaxe objeto.método(args) reflete essa idéia.
Algumas outras linguagens, como Common Lisp e Dylan, entretanto, seguem um modelo "verb-centric": os métodos são definidos fora das classes. Métodos de mesmo "nome" (onde nome = símbolo + pacote ao qual pertence) são agrupados sob uma mesma generic function. As classes de todos os argumentos da generic function são consideradas na hora de escolher que código será executado. Em Common Lisp, a sintaxe (método arg1 arg2...) reflete essa ausência de preferência por um dos argumentos e a existência da função como algo externo a qualquer classe. (Não lembro mais de onde saíram os termos "noun-centric" e "verb-centric" para descrever essa diferença, mas eles não são invenção minha.)
As conseqüências na prática são várias. Uma delas é que no modelo verbocêntrico é possível criar novos métodos para classes existentes sem ter que modificá-las. Por exemplo, se você quiser criar um método novo para trabalhar com strings, você pode defini-lo e usá-lo como qualquer outro método sobre strings, ao invés de criar uma distinção artificial entre métodos nativos da classe String ("foo".method(42)) e métodos definidos somewhere else que trabalham com strings (RandomClass.method("foo", 42)). (Ruby, uma linguagem nominocêntrica, resolve esse problema permitindo "redefinições parciais" de classes. Essa solução, entretanto, tem o problema de que todos os métodos sobre uma classe compartilham o mesmo namespace, i.e., se dois arquivos diferentes quiserem definir method sobre uma mesma classe, as definições conflitarão. Em Common Lisp, cada method estaria em seu próprio pacote, o que evita esse problema.)
Outra vantagem do modelo verbocêntrico é que evitam-se decisões arbitrárias quanto a em que classe se deve incluir um método. Por exemplo, imagine que queiramos definir um método (match string regex), que retorna a primeira ocorrência de regex em string. Esse método vai na classe String, ou em RegEx? E se quisermos procurar por outras coisas além de regexes dentro da string (e.g., outras strings)? E se quisermos procurar regexes em coisas que não são strings (e.g., streams)? No modelo verbocêntrico, essa decisão simplesmente não existe; basta definir match para todas as combinações de tipos de argumentos possíveis.
Uma terceira conseqüência desse modelo é que o conceito de "interface" é desnecessário: "implementar uma interface" consiste em especializar os métodos desejados para a classe em questão. (De certa forma, pode-se imaginar cada generic function como uma interface de um método só, e cada definição de método para a generic function como a implementação da interface para uma combinação de classes. De certa forma, pode-se imaginar muitas coisas.) Uma desvantagem disso é que se perde a garantia estática provida pelas interfaces de que de uma dada classe implementa um conjunto de métodos relacionados. (Garantias estáticas não são exatamente um ponto forte do Common Lisp.)
No modelo nominocêntrico, é possível descrever chamadas de métodos em termos de troca de mensagens: quando escrevemos obj.foo(23, 42), podemos pensar que estamos enviando a mensagem foo(23, 42) para o objeto obj. De fato, em Smalltalk, uma das primeiras linguagens orientadas a objeto, as mensagens são objetos de primeira classe, e é possível fazer algumas coisas interessantes com elas (como por exemplo repassá-las para outros objetos, ou definir um método doesNotUnderstand que trata todas as mensagens que uma classe não reconhece). O modelo de troca de mensagens também é interessante em implementações de objetos distribuídos: nesse caso, uma chamada de método sobre um objeto remoto é de fato uma mensagem enviada pela rede para a máquina onde o objeto se encontra. Uma desvantagem do modelo verbocêntrico é que o a descrição em termos de troca de mensagens não é mais aplicável: um método é chamado sobre múltiplos objetos, e portanto não há um "receptor" da mensagem.
Há quem diga que o CLOS (Common Lisp Object System) não é de fato orientação a objetos, mas sim um paradigma diferente que é capaz de expressar orientação a objetos e (um bocado de) outras coisas (muitas delas não abordadas neste post, tais como before/after methods (que lembram programação orientada a aspectos) e method combinations). Hoje em dia eu me vejo inclinado a concordar com essa posição, já que o CLOS foge da idéia de objetos como caixinhas fechadas manipuladas apenas através dos métodos expostos pela classe correspondente. Encapsulamento é possível em Common Lisp (basta não exportar os nomes dos slots (a.k.a. propriedades, atributos, membros) no pacote onde foram definidos), mas a noção de objeto = dados + operações se perde, de certa forma. Os objetos são apenas os dados, e as operações somos nós estão contidas nas generic functions / métodos.
Como é sabido e notório, implementações normais de C e C++ não fazem verificação de limite de vetor (bounds checking)*. Como também é sabido e notório, essa é uma fonte inexaurível de bugs obscuros e vulnerabilidades de segurança. Dado que esses problemas têm incomodado a humanidade há mais de 30 anos, pergunto: por que diabos compiladores C/C++ não implementam verificação de limites? A resposta normalmente dada é de que isso é feito em nome da performance: verificação de limites é custosa, e se o código for corretamente escrito é desnecessária, logo bounds checking é um desperdício de tempo de execução. Mas será que bounds checking é tão custoso assim?
Testemos, pois. Faremos um benchmark simples comparando a performance de uma função com e sem bounds checking. Para fazermos a verificação de limites, armazenaremos o tamanho dos vetores em uma posição de memória antes do conteúdo "útil" do vetor:
int *make_vector(int length) {
int *vector = malloc(sizeof(int) * (length+1));
vector[0] = length; // Armazena o tamanho no início da região de memória.
vector++; // Aponta 'vector' para o resto da região.
int i;
for (i=0; i<length; i++)
vector[i] = i;
return vector;
}
#define lengthof(v) ((v)[-1])
Nossa função de teste recebe dois vetores e soma cada elemento do segundo ao respectivo elemento do primeiro um determinado número de vezes. (Um compilador suficientemente inteligente poderia substituir o loop de N iterações por uma multiplicação por N, distorcendo os resultados. "Felizmente" esse não é o caso com o GCC (ou provavelmente qualquer compilador C existente).)
void test(int *restrict v1, int *restrict v2, int iterations) {
int length = lengthof(v1);
int i;
while (iterations-- > 0) {
for (i=0; i<length; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=lengthof(v1)) exit(42);
if (i<0 || i>=lengthof(v2)) exit(42); // i<0 redundante
#endif
v1[i] += v2[i];
}
}
}
Note que, como o mesmo índice i é usado duas vezes, temos dois testes i<0. A idéia é simular como um compilador simplista inseriria as verificações de limite; um compilador mais esperto poderia juntar as duas verificações em um if só e eliminar as verificações redundantes. Porém, deixemos o teste extra aí, já que em geral não teremos necessariamente o mesmo índice para todos os acessos de array de um determinado trecho de código. (Estranhamente, o GCC é esperto o suficiente para notar que o corpo dos dois ifs é igual, mas não para notar o teste redundante, mesmo com otimizações ativadas.)
Por fim, nossa main() cria dois vetores e chama a função de teste:
int main() {
test(make_vector(10000), make_vector(10000), 10000);
return 0;
}
Compilemos e testemos:
# gcc -std=c99 -O2 version0.c && time ./a.out real 0m0.385s user 0m0.384s sys 0m0.000s # gcc -DBOUNDS_CHECK -std=c99 -O2 version0.c && time ./a.out real 0m0.704s user 0m0.700s sys 0m0.000s
Quase duas vezes o tempo! (Como curiosidade, sem o i<0 redundante o tempo de execução com bounds checking cai para 0.660s, em "user time".) Mas não tiremos conclusões precipitadas. Quem sabe se usarmos outra representação para o par (tamanho, dados)? Uma struct, por exemplo:
typedef struct vector_t {
int length;
int content[0]; // GCC ftw
} vector_t;
vector_t *make_vector(int length) {
vector_t *vector = malloc(sizeof(vector_t) + sizeof(int)*length);
vector->length = length;
int i;
for (i=0; i<length; i++)
vector->content[i] = i;
return vector;
}
#define lengthof(v) ((v)->length)
void test(vector_t *restrict v1, vector_t *restrict v2, int iterations) {
int length = lengthof(v1);
int i;
while (iterations-- > 0) {
for (i=0; i<length; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=lengthof(v1)) exit(42);
if (i<0 || i>=lengthof(v2)) exit(42);
#endif
v1->content[i] += v2->content[i];
}
}
}
Será que faz diferença?
# gcc -std=c99 -O2 version1.c && time ./a.out real 0m0.386s user 0m0.384s sys 0m0.000s # gcc -DBOUNDS_CHECK -std=c99 -O2 version1.c && time ./a.out real 0m0.505s user 0m0.504s sys 0m0.000s
E não é que faz? Olhando o assembly gerado pelo GCC (gcc -S -fverbose-asm), a principal diferença que eu percebo é que na versão com vetor puro o GCC lê o endereço de lengthof(v2) de uma variável temporária armazenada na pilha, carrega o endereço em %eax e testa i contra %eax, enquanto na versão com struct o valor de lengthof(v2) é lido diretamente como (%esi), já que o tamanho do vetor é o primeiro item da região de memória. Sinceramente não sei por que o GCC não lê lengthof(v2) na versão com vetor como -4(%esi), já que %esi fica com o endereço de v2. Experimentei substituir a carga em %eax e comparação de i contra %eax por um teste direto de i contra -4(%esi); o resultado é o mesmo (verificado com um printf a facão) e o tempo cai dos 0.704s para 0.555s. Go figure.
Mas essa história de registradores nos dá outra idéia. O tamanho dos vetores não muda durante a execução da função. Talvez se copiarmos esses valores para variáveis locais antes de entrar no loop, o compilador os mantenha em registradores, acelerando a checagem:
void test(vector_t *restrict v1, vector_t *restrict v2, int iterations) {
int length1 = lengthof(v1);
int length2 = lengthof(v2);
int i;
while (iterations-- > 0) {
for (i=0; i<length1; i++) {
#ifdef BOUNDS_CHECK
if (i<0 || i>=length1) exit(42);
if (i<0 || i>=length2) exit(42);
#endif
v1->content[i] += v2->content[i];
}
}
}
E agora?
# gcc -std=c99 -O2 version2.c && time ./a.out real 0m0.386s user 0m0.384s sys 0m0.000s root@pts4 bounds2(0)# gcc -DBOUNDS_CHECK -std=c99 -O2 version2.c && time ./a.out real 0m0.387s user 0m0.388s sys 0m0.000s
Conclusão: bounds checking é eficiente se implementado corretamente. Todos os desenvolvedores de compiladores C são tolos e ignorantes. Nós, mentes iluminadas, implementaremos um compilador C com bounds checking e recompilaremos o kernel e todo o universo com bounds checking, tornando todo o software em existência mais seguro, sem perda de performance. Brindemos à nossa glória.
Só tem um problema: nossa verificação assume que, a partir da variável pela qual acessamos o vetor, podemos consultar seu tamanho, que armazenamos em uma posição fixa em relação à área de dados do vetor. O problema é que C permite fazer aritmética de ponteiros: um ponteiro pode apontar para qualquer ponto dentro de um vetor, não necessariamente para o seu começo. Conseqüentemente, a partir de um ponteiro arbitrário não necessariamente sabemos como encontrar o tamanho da região. Em C ainda há o agravante de que vetores e ponteiros não são tipos distintos: não se pode saber se uma função com um argumento do tipo int[] está recebendo um ponteiro para um "vetor completo" ou para uma região arbitrária dentro do vetor. (O próprio conceito de "vetor completo" não faz muito sentido em C.)
Diversas soluções já foram propostas. [Disclaimer: o que se segue são divagações sobre as possíveis soluções. Ênfase na parte "divagações".] Uma das mais simples é representar todos os ponteiros como triplas (ponteiro, limite_inferior, limite_superior), permitindo a verificação de limites para ponteiros arbitrários. O problema é que todos os ponteiros passam a ocupar o triplo do espaço, o que aumenta o tamanho de estruturas de dados com ponteiros (e.g., listas, árvores e outras estruturas recursivas), gera mais empilhamentos na passagem de argumentos para funções e possivelmente consome mais registradores. (Não sei quão válido é o ponto sobre os registradores, já que armazenar (base, length, i) ou (lower, ptr, upper) dá mais ou menos na mesma (exceto no caso em que é necessário armazenar o ponteiro para um vetor e um índice (i.e., (lower, ptr, upper, i)) (mas nada que o compilador não pudesse otimizar, I guess))).
Outro problema com essa solução é que a alteração do formato dos ponteiros implica que código com bounds checking (e ponteiros triplos, também conhecidos como "fat pointers") não pode interagir diretamente com código sem bounds checking (com pointeiros simples). Conseqüentemente, tem-se que recompilar tudo para usar bounds checking, incluindo bibliotecas. (Nossa solução original também tem esse problema, talvez em menor grau: é preciso armazenar o tamanho de cada vetor em seu início. Os ponteiros não mudam de formato, mas o código assume coisas diferentes sobre a região apontada pelos mesmos.)
Segundo estes relatos, o uso de fat pointers desse tipo provoca um aumento de mais de 100% em tempo de execução e quase duplica o tamanho dos dados nos benchmarks utilizados (o que os autores consideram "boa performance"; go figure).
Uma solução intermediária seria armazenar o tamanho de cada região no início da mesma e representar os ponteiros como um par (base, offset), a la Lisp Machine. Não vi ninguém sugerir isso entre os artigos que eu andei lendo, e não sei até que ponto isso seria melhor. Um problema de armazenar o tamanho junto com a região de memória é quando o programador deseja alocar regiões de memória com algum alinhamento, por questões de performance. Por exemplo, o programador pode fazer uma chamada a posix_memalign(&ptr, 4096, 4096), para obter uma região alinhada com uma página de memória; o tamanho da região teria que ser armazenado antes da página. Se duas dessas regiões são alocadas, duas páginas extra são alocadas apenas para conter o tamanho de cada região. (Por outro lado, uma implementação "ingênua" de malloc e posix_memalign já armazena o tamanho da região e outros dados antes da região.)
Soluções que não envolvem alterar o formato dos ponteiros e vetores trabalham armazenando os dados sobre limites em uma tabela ou outra estrutura de dados indexada pelo ponteiro cujos limites se deseja consultar. Uma das soluções mais elaboradas instrumenta todas as ocasiões de alocação e liberação de memória, tanto por malloc quanto na pilha, bem como operações aritméticas sobre ponteiros, com chamadas a funções que fazem o controle de limites. O código resultante é compatível com código sem bounds checking, mas a instrumentação tem um overhead significativo sobre o tempo de execução do programa. É uma solução útil para debugar software, já que permite instrumentar o programa sem recompilar as bibliotecas, mas não serve como um mecanismo permanente de verificação de limites.
A conclusão que eu tiro disso é: pense 44 vezes antes de incluir aritmética de ponteiros (ou ponteiros em geral) em uma linguagem. Além de dificultar bounds checking eficiente, ponteiros atrapalham a vida do compilador na hora de efetuar certas outras otimizações. Talvez o melhor seja acessar vetores sempre através de vetor/índice, e deixar o compilador se encarregar de substituir o par vetor/índice por um ponteiro como uma otimização. Se você incluir ponteiros em uma linguagem, considere mantê-los como um tipo distinto dos tipos de vetor (que carregam consigo o tamanho do vetor). Se performance for importante, me parece uma idéia melhor fazer bounds checking por padrão e fornecer uma declaração de compilação que permita eliminar os testes quando necessário, do que não fazer verificações por padrão e deixar o trabalho sujo nas mãos do programador (que invariavelmente esquece de fazê-lo ou comete um erro uma hora ou outra).
* Tecnicamente não é correto dizer que C não faz bounds checking, mas sim que a linguagem não exige bounds checking e as implementações da linguagem não o fazem. Por sinal, o compilador de C que vinha com o Genera fazia bounds checking (pelo simples fato de que todo acesso a memória na Lisp Machine era checked).
De maneira similar, uma linguagem que "faz bounds checking" apenas garante que todo acesso além do limite de um vetor será detectado. Uma implementação não precisa necessariamente inserir testes em tempo de execução, se ela puder provar de antemão que um acesso fora dos limites nunca ocorrerá. Por exemplo, em um loop do tipo for (i=0; i<lengthof(v); i++) em que i não é alterado no corpo do loop, acessos do tipo v[i] certamente estão dentro dos limites (i.e., i>=0 && i<lengthof(v) é sabidamente verdadeiro em tempo de compilação), e portanto verificações de limite não precisam ser inseridas no código.
Addendum: vide comentário.
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-trivial1. 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 problemas2, 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?3 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:
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:
(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.
E é assim a vida do desenvolvedor de linguagens de programação.
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.
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.