Posts com a tag: prog
Undefined behavior
2013-07-03 20:17 -0300. Tags: comp, prog, c, em-portugues
Hoje apresentei uma palestra-relâmpago no FISL sobre undefined behavior em C.
A palestra foi horrível, mas os slides ficaram decentes.
Update: Well, parece que existe um vídeo da palestra (minha parte começa aos 12:27). E foi menos pior do que eu tinha pensado...
Coisas que você não sabe sobre a glibc
2013-05-29 11:48 -0300. Tags: comp, prog, c, unix, em-portugues
Em algum momento do ano passado, por falta de coisa melhor para fazer, eu me parei a ler o manual da GNU libc. Não cheguei a ir muito longe, mas descobri um bocado de coisas interessantes no processo.
scanf
A scanf é uma das primeiras funções que vemos quando aprendemos C. Por isso mesmo, acabamos vendo só a funcionalidade básica para sobrevivência. Aí achamos que conhecemos a scanf e nunca mais nos preocupamos com ela. Ela possui um bocado de features interessantes, entretanto:
- A scanf retorna um inteiro que indica quantos itens ela conseguiu ler, ou EOF se nada foi lido e o fim do arquivo foi atingido. Por exemplo, se você chama scanf("%d %d", &x, &y) e o usuário digita 42 foo, ela atribui 42 a x, deixa y intacto, e retorna 1 (pois apenas um dos formatos pôde ser lido).
- A scanf deixa no buffer tudo o que ela não conseguiu ler. No exemplo acima, o trecho foo fica intacto na entrada esperando para ser lido.
Uma conseqüência disso é que um programa do tipo while (x!=0) scanf("%d", &x);, ao se deparar com uma entrada do tipo foo, entra em loop infinito (pois a scanf nunca consegue ler o %d, não altera o valor de x, e o foo fica para sempre no buffer de entrada).
- A menos que o formato especificado aceite ler espaços, a scanf engole whitespace até encontrar algo que possa ser lido pelo formato (ou que definitivamente não possa ser lido, como o foo acima).
- %s lê uma seqüência de caracteres não-whitespace, e não uma "string qualquer".
- GNU extension: se um formato que lê strings é precedido pelo modificador a, a scanf aloca memória automaticamente para a string lida, e o argumento correspondente ao formato deve ser do tipo char **. Por exemplo:
char *string; scanf("%as", &string); - Lembra que a scanf/printf aceitam tanto %d quanto %i para ler inteiros? Pois acontece que com a scanf, %d exige que o inteiro seja fornecido em decimal, e %i lê o inteiro em qualquer formato aceito pelo C (i.e., se começar com 0 é octal, se começar com 0x é hexadecimal).
- A scanf possui um "formato" %n, que não lê nada, mas grava no argumento correspondente (que deve ser um ponteiro para inteiro) o número de caracteres lidos até o ponto em que o %n ocorre. Isso é particularmente útil com a sscanf, pois permite saber em que ponto da string a sscanf parou a leitura.
Other I/O
Existe uma função getline(char **linha, size_t *tamanho, FILE *stream), que recebe um ponteiro para um buffer inicial e seu tamanho, lê uma linha de tamanho arbitrário, realocando o buffer e atualizando o tamanho automaticamente, e retorna o número de caracteres lidos (que pode ser menor que o buffer, em princípio). Se linha for um ponteiro para um ponteiro nulo, o buffer inicial será alocado automaticamente. E.g.:
char *buf = NULL; size_t bufsize, bytes_read; bytes_read = getline(&buf, &bufsize, stdin);
Também existe uma função getdelim, que faz a mesma coisa, mas usa um delimitador diferente de \n como fim da "linha".
Essas funções não são parte do C padrão, e sim das extensões do GNU e de versões recentes do POSIX.
- Existe uma dúzia de funções para I/O assíncrona, mas eu não cheguei a ler essa parte direito, então fica como exercício para o leitor. Aliás, existe tanta coisa relacionada a I/O que vale a pena dar uma olhada pelo menos no índice do manual.
Miscelânea
- Obstacks são uma estrutura de dados fornecida pela glibc que permite alocação rápida, mas exige que os objetos sejam desalocados na ordem inversa à em que foram alocados. Nunca experimentei, mas a idéia é interessante.
- É possível definir novos formatos para a printf usando register_printf_function e companhia.
- É possível criar novos tipos de streams, que podem ser usadas como se fossem arquivos. A glibc também vem com suporte a string streams, que permitem ler e escrever em strings como se elas fossem arquivos. (Estou sentindo um cheiro de Common Lisp aqui.)
No más
A glibc tem muita coisa (a versão em PDF do manual tem cerca de mil páginas). Vale a pena dar uma olhada no manual, nem que seja apenas para descobrir que tipo de recursos ela fornece, caso um dia você precise de algum deles.
fgetcsv: A cautionary tale
2013-05-18 01:52 -0300. Tags: comp, prog, web, php, rant, em-portugues
Quando eu reescrevi o blog system, eu resolvi manter o índice de posts em um arquivo CSV e usar as funções fgetcsv e fputcsv para manipulá-lo. Minha intuição prontamente me disse "isso é PHP, tu vai te ferrar", mas eu não lhe dei importância. Afinal, provavelmente seria mais eficiente usar essas funções do que ler uma linha inteira e usar a explode para separar os campos. (Sim, eu usei um txt ao invés de um SQLite. Eu sou feliz assim, ok?)
Na verdade o que eu queria era manter o arquivo como tab-separated values, de maneira que ele fosse o mais fácil possível de manipular com as ferramentas convencionais do Unix (cut, awk, etc.). As funções do PHP aceitam um delimitador como argumento, então pensei eu que bastaria mudar o delimitador para "\t" ao invés da vírgula e tudo estaria bem. Evidentemente eu estava errado: um dos argumentos da fputcsv é um "enclosure", um caractere que deve ser usado ao redor de valores que contêm espaços (ou outras situações? who knows?). O valor padrão para a enclosure é a aspa dupla. Acontece que a fputcsv exige uma enclosure: não é possível passar uma string vazia, ou NULL, por exemplo, para evitar que a função imprima uma enclosure em volta das strings que considerar dignas de serem envoltas. Lá se vai meu tab-separated file bonitinho. Mas ok, não é um problema fatal.
A segunda curiosidade é que a fgetcsv aceita um argumento "escape", que diz qual é o caractere de escape (\ por default). Evidentemente, você tem que usar um caractere de escape; a possibilidade de ler um arquivo em um formato em que todos os caracteres exceto o delimitador de campo e o "\n" tenham seus valores literais é inconcebível. Mas ok, podemos setar o escape para um caractere não-imprimível do ASCII (e.g., "\1") e esquecer da existência dele. Acontece que a fputcsv não aceita um caractere de escape, logo você não tem como usar o mesmo caractere não-imprimível nas duas funções. WTF?
Na verdade, agora testando melhor (já que a documentação não nos conta muita coisa), aparentemente a fputcsv nunca produz um caractere de escape: se o delimitador aparece em um dos campos, ele é duplicado na saída (i.e., a"b vira a""b). Evidentemente, não há como eliminar esse comportamento. Mas então o que será que faz o escape character da fgetcsv?
# php -r 'while ($a = fgetcsv(STDIN, 999, ",", "\"", "\\"))
{ var_export($a); echo "\n"; }'
a,z
array (
0 => 'a',
1 => 'z',
)
a\tb,z
array (
0 => 'a\\tb',
1 => 'z',
)
Ok, o escape não serve para introduzir seqüências do tipo \t. Talvez para remover o significado especial de outros caracteres?
a\,b,z array ( 0 => 'a\\', 1 => 'b', 2 => 'z', ) a b,z array ( 0 => 'a b', 1 => 'z', ) a\ b,z array ( 0 => 'a\\ b', 1 => 'z', )
Muito bem. Como vimos, o escape character serve para, hã... hmm.
Mas o fatal blow eu tive hoje, olhando a lista de todos os posts do blog e constatando que o post sobre o filme π estava aparecendo com o nome vazio. Eis que:
# php -r '
$h = fopen("entryidx.entries", "r");
while ($a = fgetcsv($h, 9999, "\t"))
if ($a[0]=="20120322-pi") var_export($a);'
array (
0 => '20120322-pi',
1 => 'π',
2 => '2012-03-22 23:53 -0300',
3 => 'film',
)
# LC_ALL=C php -r '
$h = fopen("entryidx.entries", "r");
while ($a = fgetcsv($h, 9999, "\t"))
if ($a[0]=="20120322-pi") var_export($a);'
array (
0 => '20120322-pi',
1 => '',
2 => '2012-03-22 23:53 -0300',
3 => 'film',
)
A próxima versão do Blognir deverá usar fgets/explode.
UPDATE: Aparentemente o problema só ocorre quando um caractere não-ASCII aparece no começo de um campo. Whut?
UPDATE 2:
"a b","c d" array ( 0 => 'a b', 1 => 'c d', ) "a"b","c"d" array ( 0 => 'ab"', 1 => 'cd"', ) "a\"b","c d" array ( 0 => 'a\\"b', 1 => 'c d', )
Noun-centric vs. verb-centric OO
2013-05-11 01:36 -0300. Tags: comp, prog, lisp, pldesign, em-portugues
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.
So many parens
2013-04-17 17:17 -0300. Tags: comp, prog, lisp, em-portugues
Pode-se dividir as pessoas em dois grupos, segundo sua reação ao serem apresentadas a features novas em uma linguagem de programação:
- "Whoa, que legal!"
- "Tá, e pra que serve?"
(Na verdade o que provavelmente existe é um continuum de quanta justificativa é necessária para provocar a reação "whoa, que legal" em uma dada pessoa, but I digress.) O que acontece aí é que eu (que estou no primeiro grupo, mostly) freqüentemente acho complicado pensar em um exemplo de uso de uma feature que convença alguém do segundo grupo de que a feature é interessante. Por exemplo, a pessoa me pergunta "mas por que Lisp tem tantos parênteses?", e eu respondo "Macros!", e a pessoa "why macros?", e eu "code transformation!", e a pessoa "why code transformation", e eu "what do you mean, why?".
Pois, agora acho que encontrei um exemplo decentemente convincente. Meu TCC consiste, entre outras coisas, em desenvolver uma linguagem de programação e integrá-la ao ambiente de programação DrRacket. Para isso, estou implementando a linguagem em Racket, um descendente de Scheme, uma linguagem da família Lisp. Dentre as inúmeras bibliotecas que acompanham o Racket, estão a parser-tools/lex e parser-tools/yacc. Essas bibliotecas implementam funcionalidade equiparável aos famosos programas lex e yacc, que geram analisadores léxicos e sintáticos, respectivamente, a partir de arquivinhos de regras.
A diferença, entretanto, é que as parser-tools são implementadas como macros em Racket, de maneira integrada com o resto da linguagem. Por exemplo, ao invés de usar um programa separado que lê um arquivo meio-em-C, meio-em-lex e gera um arquivo em C, a parser-tools/lex provê uma macro lexer que, quando compilada, produz uma função que recebe uma stream e devolve a próxima token encontrada na stream. Algo do tipo:
(define example-lexer
(lexer
[expressão valor-a-retornar]
[expressão valor-a-retornar]
...))
O parser funciona de maneira análoga. As macros, assim, permitem estender a linguagem com recursos sintáticos novos, sem que se tenha que usar ferramentas externas para fazer transformações de código (que potencialmente exigem reparsear o texto do programa, ao contrário do que acontece com as macros, que já recebem o programa pré-parseado como argumento). A vantagem da sintaxe uniforme (i.e., so-many-parens) é que os novos recursos adicionados mantêm a mesma cara do resto da linguagem, e que o parser do Lisp (que executa antes de a macro ser chamada) pode fazer o seu trabalho sem se preocupar com a semântica dos objetos que está parseando.
A conseqüência dessa integração é que o threshold a partir do qual vale a pena escrever uma transformação de código ao invés de fazer as coisas na mão é muito mais baixo em um Lisp do que em uma linguagem convencional. Por exemplo, certa vez eu estava escrevendo um typechecker/interpretador para uma linguagem simples. Logo que eu comecei a escrever, percebi que seria uma boa eu usar pattern matching para testar com que tipo de expressão o interpretador tinha se deparado. Por exemplo, ao invés de escrever algo do tipo:
;; Avalia a expressão 'expr' no ambiente de variáveis 'env'.
(defun evaluate (expr env)
(cond
;; Se a expressão for do tipo (+ x y), devolve x+y.
((eq (first expr) '+) (+ (evaluate (second expr) env)
(evaluate (third expr) env)))
;; Se for (if t x y), avalia o teste e a sub-expressão correspondente.
((eq (first expr) 'if) (if (evaluate (second expr) env)
(evaluate (third expr) env)
(evaluate (fourth expr) env)))
...))
eu queria poder escrever algo do tipo:
(defun evaluate (expr env)
(match-case
((+ x y) (+ (evaluate x env) (evaluate y env)))
((if test then else) (if (evaluate test env)
(evaluate then env)
(evaluate else env)))
...))
Em 17 linhas (não muito bonitas, mas só porque eu não estava muito preocupado com isso quando as escrevi) de Common Lisp, eu implementei uma macro match-case e segui escrevendo o programa. Se ao invés disso eu tivesse que escrever um programa externo para transformar o código, provavelmente não teria valido a pena o esforço.
#<eof>.
One man's gambiarra is another man's technique
2013-04-17 14:52 -0300. Tags: comp, prog, ramble, em-portugues
Certa feita (e de repente o "fecha" do espanhol não parece mais tão estranho), não me lembro mais em que contexto nem para quem, eu mostrei um código deste tipo com listas encadeadas em C:
for (item = list;
item && item->value != searched_value;
item = item->next) ;
Que tanto quanto me constasse, era a maneira de se procurar um valor em uma lista em C. Para minha surpresa na época, a pessoa disse que isso era gambiarra. (Eu dificilmente escreveria isso com um while, porque eu tenho uma propensão terrível a esquecer o item = item->next no final do while. Ou será que eu tenho essa propensão por não estar acostumado a fazer esse tipo de coisa com while? But I digress.)
Uma situação similar foi quando eu mostrei para alguém na monitoria de Fundamentos de Algoritmos que dava para usar "tail-recursion com acumuladores" para iterar sobre uma lista. Algo do tipo:
(define (média lista)
(média* lista 0 0))
(define (média* lista soma conta)
(cond [(empty? lista) (/ soma conta)]
[else (média* (rest lista) (+ soma (first lista)) (+ conta 1))]))
Que, novamente, é a maneira padrão de se fazer esse tipo de coisa em uma linguagem funcional (talvez com a definição de média* dentro do corpo de média, ao invés de uma função externa, mas whatever), e novamente a pessoa viu isso como uma "baita gambiarra". Provavelmente, o código imperativo equivalente (com atribuição de variáveis para manter a conta e a soma) é que seria visto como gambiarra por um programador Scheme.
Outro item de contenda é usar x++ em C para usar o valor atual de x em uma expressão e incrementá-lo na mesma operação (que é, bem, exatamente a definição do operador). Ok, usar um x++ perdido no meio de uma expressão grande pode ser fonte de confusão. Mas algo como:
var1 = var2++;
ou more likely:
item->code = max_code++;
não deveria ser nenhum mistério para quem conhece a linguagem.
A impressão que eu tenho é que as pessoas consideram "gambiarra" qualquer coisa feita de uma maneira diferente do que elas estão acostumadas. Eu mesmo já fui vítima desse efeito. No terceiro semestre eu escrevi um "banco de dados" em C (basicamente um programa que aceitava queries em uma linguagem facão, mantinha uns arquivos seqüenciais e montava uns índices em memória) para o trabalho final da disciplina de Classificação e Pesquisa de Dados. Como o conteúdo dos arquivos binários era determinado em tempo de execução pelas definições das tabelas, o programa continha um bocado de casts, manipulações de ponteiros e outras "curiosidades" do C no código. Até então, tinha sido o programa mais complicado que eu tinha escrito. Durante um bom tempo, quando o assunto surgia, eu costumava comentar que esse código era "cheio de gambiarras" e coisas de "baixo-nível". Um belo dia, uns dois ou três semestres depois, eu resolvi dar uma olhada no código, porque eu já não lembrava direito o que ele fazia de tão mágico. Para minha surpresa, minha reação ao olhar as partes "sujas" do código foi algo como "pff, que brincadeira de criança". (E para minha surpresa, as partes "sujas" me pareceram bastante legíveis.)
(Um ponto relacionado é que quando estamos ensinando/explicando alguma coisa, devemos nos lembrar que o que nos parece óbvio e simples pode não o ser para a pessoa que tem menos experiência no assunto, mas esse não era o tema original do post.)
Agora dando uma olhada nesse código de novo, lembrei de uma outra coisa que eu tinha pensando quando o tinha revisto pela primeira vez: que certos trechos do código poderiam ter sido simplificados se eu tivesse usado um goto fail; da vida em pontos estratégicos. O que nos leva ao próximo tópico...
Considered harmful?
Entre muitos nesse mundo da programação existe um culto irracional às Boas Práticas de Programação™. Não me entenda mal; muitas técnicas e práticas ajudam a tornar o código mais legível e fácil de manter. O problema é quando as "boas práticas" se tornam regras fixas sem uma boa justificativa por trás.
Um exemplo é a proibição ao goto. A idéia básica é: "Alguns usos do goto produzem código ilegível; logo, o goto não deve ser usado." Isso é mais ou menos equivalente a "facas cortam os dedos; logo, não devemos usar facas". Ok, usar uma faca para desparafusar parafusos quando se tem uma chave de fenda à mão não é uma boa idéia. Mas usar uma chave de fenda para passar margarina no pão também não é. Verdade que em linguagens de mais alto nível do que C (com exceções e try/finally e labeled loops e what-not) é extremamente raro encontrar um bom motivo para se usar um goto; mas em C, há uma porção de situações em que um goto bem utilizado é capaz de tornar o código mais simples e legível.
Outro exemplo é o uso de TABLEs em HTML. O fundamento por trás da "regra" que "proíbe" certos usos de TABLE é evitar que TABLEs sejam usadas apenas para layout, com coisas que não têm a semântica de uma tabela. So far, so good. Mas no post (que eu nunca mais encontrei) pelo qual eu fiquei sabendo sobre "tableless tables" (i.e., o uso de CSS para aplicar o layout gerado pelas TABLEs do HTML a outros elementos), lembro que um indivíduo tinha postado um comentário semi-indignado dizendo que "usar CSS para simular uma tabela é só uma tabela disfarçada, e não deve ser feito". Ou seja, o camarada internalizou a noção de "usar TABLEs é errado", mas não o porquê.
Outra manifestação do "culto" são coisas do tipo:
Q: O que acontece se eu converter um ponteiro em inteiro e de volta em ponteiro?
A: Isso é uma péssima prática de programação e você não deveria fazer isso.
que eu vejo com alguma freqüência no Stack Overflow, i.e., o camarada não responde a pergunta, e ao invés disso se limita a repetir o mantra "Não Deve Ser Feito".
A freqüência com que eu vejo esse tipo de coisa me preocupa um pouco, na verdade. Acho que o princípio por trás disso é o mesmo que está por trás de zoar/condenar/excluir as pessoas que possuem algum comportamento "non-standard". Mas isso é uma discussão para outro post.
Appendix A
17.4: Is goto a good thing or a bad thing?
Yes.
17.5: No, really, should I use goto statements in my code?
Any loop control construct can be written with gotos; similarly, any goto can be emulated by some loop control constructs and additional logic.
However, gotos are unclean. For instance, compare the following two code segments:
do { foo(); foo(); if (bar()) if (bar()) goto SKIP; break; baz(); baz(); quux(); quux(); } while (1 == 0); SKIP: buz(); buz();Note how the loop control makes it quite clear that the statements inside it will be looped on as long as a condition is met, where the goto statement gives the impression that, if bar() returned a nonzero value, the statements baz() and quux() will be skipped.
_____
(O título do post é uma paráfrase de uma paráfrase de uma expressão idiomática.)
The shell is completely wrong
2013-01-04 13:56 -0200. Tags: comp, prog, bash, unix, wrong, rant, em-portugues
![[Foto de John McCarthy com a legenda 'Programming: You're doing it completely wrong']](img/doing-it-wrong-small.jpg "A dificuldade que foi fazer esse layout funcionar é digna de post próprio")
Reading and splitting
2012-12-31 13:39 -0200. Tags: comp, prog, bash, em-portugues
Durante os últimos 354 anos eu estive splitando linhas em bash assim:
line="root:x:0:0:root:/root:/bin/bash"
IFS=":"
set -- $line
echo "$1" # root
echo "$7" # /bin/bash
# ou:
IFS=":"
fields=($line)
echo "${fields[0]}" # root
echo "${fields[6]}" # /bin/bash
Turns out que faz 354 anos que eu estou fazendo isso errado.
Acontece que expansão de parâmetros (i.e., $var) fora de aspas duplas não só causa word splitting (que é o que queremos), mas também causa pathname expansion (substituição de *, ?, ~ e afins pelos nomes de arquivo que casam com o padrão):
cd /
line='a*:b*:c*'
IFS=":"
fields=($line)
echo "${fields[0]}" # a*
echo "${fields[1]}" # bin
echo "${fields[2]}" # boot
echo "${fields[3]}" # c*
Esse problema nunca me ocorreu na prática, mas me dei conta disso depois de escrever o post sobre manipulação de strings em bash. O pior é que eu já sabia há muito tempo que variáveis fora das aspas sofrem pathname expansion, mas acho que adquiri o hábito de splitar strings assim antes de saber disso. Uma solução correta é usar o comando IFS=delimitadores read -a arrayname (que lê uma linha com campos separados por delimitadores e coloca os pedaços na variável arrayname) em conjunto com o operador <<<string (que alimenta a stdin do comando com a string):
line='a*:b*:c*'
IFS=":" read -a fields <<<"$line"
echo "${fields[0]}" # a*
echo "${fields[1]}" # b*
echo "${fields[2]}" # c*
De brinde agora é possível incluir : em um campo usando a seqüência \:, já que o read entende o \ como um indicador de que o próximo caractere deve ser interpretado literalmente (a menos que a opção -r (de raw) seja usada).
O último exemplo de splitting do post anterior (que procura o nome do shell de um usuário no /etc/passwd) ficaria assim:
#!/bin/bash
user="$1"
IFS=":"
while read -a campos line; do
if [ "${campos[0]}" = "$user" ]; then
echo "${campos[6]}"
fi
done </etc/passwd
Outra feature interessante do read é a opção -d, que permite especificar um caractere diferente de \n como terminador de linha. Isso é útil, por exemplo, em conjunto com o find -print0, que imprime os nomes dos arquivos separados pelo caractere \0 (ASCII NUL) ao invés de \n:
find . -name '*.bkp' -print0 | while IFS= read -d $'\0' file; do
echo "Arquivo $file será renomeado."
mv "$file" "${file%.bkp}~"
done
Isso garante que o script vai funcionar mesmo que o nome de algum arquivo contenha quebras de linha, o que faz com que o script não seja vulnerável ao usuário malandro que criar um arquivo chamado foo\n/bin/bash\nbar.bkp em seu home.
Manipulando strings em bash
2012-12-27 02:49 -0200. Tags: comp, prog, bash, em-portugues
Seguindo uma sugestão indireta, eis um post sobre as funções básicas de manipulação de strings do bash.
Antes de mais nada, gostaria de citar uma frase do manual do INTERCAL que me parece apropriada a respeito do bash:
Please be kind to our operators: they may not be very intelligent, but they're all we've got.
Dito isto, vamos ao ponto.
Parameter substitution
Como toda linguagem normal, bash possui variáveis.
person="Elmord" echo "$person's Magic Valley"
A sintaxe $nome invoca o que se chama de parameter expansion. 'Parâmetro' é um termo mais geral que 'variável' em bash, e inclui variáveis, argumentos recebidos por um script ou função ($1, $2, ...), e alguns valores especiais mantidos pelo bash (e.g., $$ (PID do shell), $* (todos os argumentos do script/função em uma string só), etc.). Em bash, todos os parâmetros são strings (ou quase: $*, $@ e aparentados são meio indecisos sobre se são strings ou arrays de strings).
$nome pode ser escrito como ${nome}. Isso é útil quando se deseja isolar o nome do parâmetro de uma string adjacente que poderia ser interpretada como parte do nome:
animal="Raposa"
echo "${animal}s não dão dinheiro."
Além disso, essa sintaxe estendida permite especificar modificações sobre o valor a ser retornado pela expansão. Entre as modificações mais usadas estão as remoções de prefixos e sufixos:
- ${nome#pattern}: Remove o menor prefixo que case com pattern
- ${nome##pattern}: Remove o maior prefixo que case com pattern
- ${nome%pattern}: Remove o menor sufixo que case com pattern
- ${nome%%pattern}: Remove o maior sufixo que case com pattern
(Mnemônico: # fica à esquerda (prefixo) de $ no teclado, % à direita (sufixo) de $.)
Por exemplo:
file="arquivo.feliz.html"
echo "$file" # arquivo.feliz.html
echo "${file%.*}" # arquivo.feliz (remove o menor sufixo do tipo .*, i.e., do último ponto em diante)
echo "${file##*.}" # html (remove o maior prefixo do tipo *., i.e., do começo até o último ponto)
echo "${file%%.*}" # arquivo (remove tudo do primeiro ponto em diante)
echo "${file#*.}" # feliz.html (remove apenas até o primeiro ponto)
Exemplo levemente mais elaborado:
path="foo/bar/baz/quux/hack"
echo "${path%/*}" # foo/bar/baz/quux
echo "${path%/*/*}" # foo/bar/baz
echo "${path%/*/*/*}" # foo/bar
echo "${path%/*/*/*/*}" # foo
echo "${path%/*/*/*/*/*}" # foo/bar/baz/quux/hack
No primeiro echo, removemos apenas o último componente do caminho. No segundo, removemos o menor sufixo que casa com /*/*, i.e., que consiste de uma barra, seguida por qualquer coisa (inclusive nada), seguido por outra barra, seguida por qualquer coisa (inclusive nada), o que resulta na eliminação dos dois últimos componentes do caminho. No último comando, o pattern não casa com nada (não há cinco barras na string), e portanto o resultado é o valor de path intacto. (Note que isso funciona porque estamos removendo o menor sufixo, com o operador % simples. Se usássemos o operador %% (i.e., ${path%%/*}, etc.) ficaríamos apenas com foo em todos os casos exceto o último.)
E se ao invés de remover os dois últimos componentes, quiséssemos ficar com apenas os dois últimos componentes? Infelizmente não existe um operador para remover o "segundo maior prefixo" que case com */. Uma maneira de conseguir isso é fazer a operação em dois passos:
path="foo/bar/baz/quux/hack"
prefix="${path%/*/*}" # coloca "foo/bar/baz" em prefix
echo "${path#"$prefix"}" # remove "foo/bar/baz" do começo de $path, deixando "/quux/hack"; ou
echo "${path#"$prefix/"}" # remove "foo/bar/baz/" do começo de $path, deixando "quux/hack"
Ou, de maneira mais abreviada (e talvez menos legível):
echo "${path#"${path%/*/*}"}"
Note as aspas ao redor da sub-expressão (${path#"prefix"}). Elas são necessárias porque o valor de $prefix poderia conter caracteres como *, que seriam interpretados como wildcards se não houvesse aspas.
Os wildcards que podem aparecer nas patterns são os mesmos que podem ser usados com nomes de arquivos: * (zero ou mais caracteres quaisquer), ? (um caractere qualquer), [abcde] (qualquer um dos caracteres listados; ranges do tipo A-Z, bem como classes de caracteres do tipo [:digit:], podem ser incluídos na lista), [^abcde] (qualquer caractere não listado). Se a opção shopt -s extglob estiver ativa, patterns estendidas também são aceitas, mas isso é assunto para outro post.
Outro tipo de modificação útil são as substituições de substrings:
- ${nome/pattern/string}: substitui a primeira ocorrência de pattern por string;
- ${nome//pattern/string}: substitui todas as ocorrências de pattern por string;
- ${nome/#pattern/string}: substitui uma ocorrência de pattern por string, desde que pattern ocorra no início de $nome;
- ${nome/%pattern/string}: substitui uma ocorrência de pattern por string, desde que pattern ocorra no fim de $nome.
A pattern de substituição sempre casa com a maior ocorrência (i.e., se x="foo.bar.baz.quux.hack", ${x/.*./BOOM} expande para fooBOOMhack). Aparentemente não há um meio de substituir o menor prefixo/sufixo. Go figure.
Outra modificação útil é o slicing: ${nome:início:tamanho} seleciona tamanho caracteres de $nome, começando pelo início-ésimo (contando do zero). início e tamanho são expressões aritméticas; portanto, nomes de variáveis podem ser usados sem $, e operações aritméticas podem ser realizadas diretamente, sem necessidade de usar a sintaxe usual para expansão aritmética ($((expressão))):
x="foobarbazquux"
echo "${x:6:3}" # baz
n=6
echo "${x:n:n/2}" # baz
Se tamanho for omitido, o trecho de início até o final da string é usado. Se início for negativo, conta-se a partir do final da string:
echo "${x:(-4):1}" # q
echo "${x:(-4)}" # quux
(Note que o - deve ser separado do : que o precede (com parênteses ou espaços, por exemplo), pois ${nome:-string} significa algo completamente diferente em bash (usa o valor de $nome, ou string se $nome for vazio).)
Se um índice negativo indicar uma posição antes do começo da string, o resultado é a string vazia. (Por quê? Por quê?)
${#nome} devolve o comprimento de $nome. Há outras modificações; para mais informações, procure por Parameter Expansion na manpage do bash.
Separando em pedacinhos
Uma operação comum sobre strings é separá-la em diversos componentes segundo algum caractere separador. Essa operação existe em diversas linguagens sob o nome de split. Por exemplo, em JavaScript:
js> x = "foo bar baz"
"foo bar baz"
js> partes = x.split(" ")
["foo", "bar", "baz"]
js> partes[1]
"bar"
(By the way: já experimentou dar Ctrl-Shift-K no Firefox?)
Bash é uma linguagem muito hábil em separar strings. Por sinal, bash é hábil demais em separar strings: qualquer parâmetro não envolto em aspas está sujeito ao infame word splitting: o valor resultante da expansão do parâmetro é separado em múltiplas "palavras", e cada palavra é tratada como um argumento separado. Por exemplo:
$ file="nome com espaços" $ ls "$file" ls: cannot access nome com espaços: No such file or directory $ ls $file ls: cannot access nome: No such file or directory ls: cannot access com: No such file or directory ls: cannot access espaços: No such file or directory
Isso significa que você deve colocar aspas maniacamente em torno de qualquer string com variáveis que você não quer que sejam splitadas. Isso também significa que você pode se aproveitar dessa feature para obter os pedacinhos individuais de uma string. Uma maneira de fazer isso é criando um array com o resultado da expansão:
partes=($file)
echo "${partes[0]}" # nome
echo "${partes[1]}" # com
echo "${partes[2]}" # espaços
echo "${#partes[@]}" # 3 (comprimento do array)
Outra maneira é substituir os argumentos posicionais do shell pelo resultado da expansão:
set -- $file echo "$1" # nome echo "$2" # com echo "$3" # espaços echo "$#" # 3O que define uma "palavra" são os separadores contidos na variável IFS (internal field separator): essa variável contém todos os caracteres que são considerados separadores. Por padrão, os separadores são espaços, tabs e newlines. Você pode setar essa variável para quaisquer outros caracteres, e remover a variável (com unset IFS) para restaurar os separadores originais. Por exemplo, se quiséssemos escrever um script para procurar no arquivo /etc/passwd (cujos campos são separados por :) o nome do shell de um determinado usuário, poderíamos fazer assim:
#!/bin/bash
user="$1"
IFS=":"
while read line; do
campos=($line)
if [ "${campos[0]}" = "$user" ]; then
echo "${campos[6]}"
fi
done </etc/passwd
Update: Há uma solução melhor.
Matching
Às vezes queremos saber se uma string casa com um determinado padrão. A maneira mais comum de se fazer isso é através do comando case:
case "$file" in
*.txt)
echo "É um arquivo de texto."
cat "$file"
;;
*.gif|*.jpg|*.png)
echo "É uma figurinha."
xloadimage "$file"
;;
*)
echo "Que que é isso, medeus?"
;;
esac
Cada cláusula do case começa com uma pattern, seguida de ). Os tipo de pattern aceitos são os mesmos usados para expansão de nomes de arquivos e para remoções de prefixo/sufixo e outras substituições de string. Cada cláusula é terminada com ;;. (O ;; na última cláusula é opcional.) Múltiplas patterns, separadas por |, podem ser especificadas.
As patterns do shell são um tanto quanto limitadas, o que exige uma certa dose de treta na hora de usá-las. Por exemplo, imagine que queiramos fazer um script que exige um número como argumento, e queremos que o script teste se o argumento foi passado corretamente. Não temos como especificar uma pattern que diga que apenas números são aceitos. A solução é especificar que se o argumento contiver algum caractere que não seja um número, o script deve emitir um erro:
case "$1" in
*[^0-9]*)
echo "Erro: argumento deve ser um número."
exit 1
;;
*)
echo "Eis um número: $1."
;;
esac
Parece bom? Quase: se uma string vazia for passada, nenhum dos caracteres que a compõem casa com [^0-9], e portanto a primeira pattern não casa, e portanto caímos na segunda cláusula do case, embora o argumento passado não seja um número. Para resolver esse problema, temos que incluir a string vazia na primeira cláusula:
case "$1" in
*[^0-9]*|)
echo "Erro: argumento deve ser um número."
exit 1
;;
*)
echo "Eis um número: $1"
;;
esac
Comandos externos
Até agora utilizamos apenas recursos internos do shell. Mas temos também à disposição a vasta gama de comandos de manipulação de texto do Unix, tais como cut, sed e tr. Se quisermos alimentar um desses comandos com o conteúdo de uma variável, podemos usar o comando echo em uma pipeline, e capturar o resultado com a sintaxe $(comando):
dmy="27/05/1990" ymd="$(echo "$dmy" | sed -re 's,(..)/(..)/(....),\3-\2-\1,')" echo "$ymd" # 1990-05-27
A partir do bash 3, é possível alimentar a entrada padrão de um comando com uma string através da sintaxe comando <<<string:
ymd="$(sed -re 's,(..)/(..)/(....),\3-\2-\1,' <<<"$dmy")"
Outras features
Este post não cobre todas as features de manipulação de strings no bash. (Em particular, faltou cobrir o comando [[ expressão ]] e suas habilidades com expressões regulares, as quais eu ainda não experimentei direito.) Para mais informações, dê uma olhada na manpage do bash. Sinta-se à vontade para acrescentar outras mandingas ou fazer perguntas nos comentários.
Sobre a performance de verificação de limites de vetor
2012-12-05 19:17 -0200. Tags: comp, prog, pldesign, em-portugues
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ó que não
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.
Conclusão
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).
Notas
* 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.
« Mais recentes / Newer posts | Mais antigos / Older posts »