Feeds:
Posts
Comentários

Estou “aposentando” este blog no wordpress. Agora, os novos posts aparecerão no meu próprio domínio: blog.ltcmelo.com/.

O post inaugural dessa migração é sobre o C++ front-end do Qt Creator.

English version

Alguns meses atrás resolvi implementar as operações aritméticas fundamentais para inteiros de precisão arbitrária. O principal motivo era mais curiosidade do que necessidade, já que existem várias boas bibliotecas por aí com esse foco. Ainda assim, achei que valeria à pena o exercício e diversão.

Originalmente estava atrás de algo bem simplista, mas ao longo do percurso o código acabou tomando mais forma e eventualmente se transformou em uma classe C++ de API bem definida. Basicamente, foram aparecendo as conexões lógicas, uma coisa foi levando a outra, e no final das contas acabei implementando mais do que planejado.

A referência que utilizei foi o volume de Seminumerical Algorithms do livro do Knuth, The Art of Computer Programming. Naturalmente, o legal é que mesmo o livro se preocupando em mencionar dicas de implementação, ainda há espaço para muitas questões no processo de conversão da descrição algorítmica para a o código final em C++.

Pontos interessantes que observei…

  • Antes que qualquer coisa, o primeiro passo foi pensar em qual o modelo de representação a ser usado. Bom, no mundo binário a opção mais comum é o complemento de dois. No entanto, no caso de precisão arbitrária em um nível mais alto a base numérica é tipicamente um inteiro grande, logo uma abordagem de magnitude e sinal passa a ser uma boa opção.
  • Considerando magnitude e sinal, há ainda um aspecto flexível que é justamente a questão do zero. Qualificá-lo explicitamente ou utilizar apenas dois sinais e inferi-lo a partir dos valores? Achei mais simples e consistente ter um atributo que indica se o número é positivo, negativo ou zero.
  • Qual estrutura de dados e onde colocar os dígitos mais significativos? Normalmente um vetor é uma boa opção. Fornece acesso aleatório, você pode controlar a alocação com certa previsibilidade, não há overhead de espaço, a memória é contínua e há um mapeamento “natural” das operações. Com relação a posição dos dígitos mais significativos, colocá-los no final do vetor é o convencional, já que permite o crescimento/decrescimento do inteiro de forma eficiente.
  • Continuando o parágrafo acima, existe a necessidade de eliminar zeros iniciais que podem resultar de algumas operações. Isso facilita a implementação em geral. Além disso, como o zero não é representado apenas pela magnitude também precisei adicionar verificações um pouco “artificiais” após alguns cálculos.
  • As operações de adição, subtração e multiplicação são bem intuitivas. Nada muito elaborado, o único cuidado é com o tratamento do carry. Já a divisão com resto, essa é outra história. Obviamente, você pode seguir um algoritmo simples de subtrações consecutivas, mas eu queria algo mais bacana. O algoritmo apresentado no livro do Knuth é baseado na normalização do divisor e dividendo e de se estimar um valor para o quociente. Alguns detalhes são não-triviais e eu diria que há um certo potencial para erros na implementação. ;-) Nota: Há duas correções deste algoritmo na errata do livro.
  • Saindo do planejado… Acaba que para a divisão acima tive que implementar também as operações de shift esquerda/direita. Elas são recomendadas para a etapa de normalização. As outras operações que são uma evolução natural de usabilidade são as de conversão entre a base da representação e a base decimal. Isso permite a construção e impressão fáceis dos números a partir de uma string.
  • Testes, é claro. Afinal de contas, você precisa verificar de alguma forma se as coisas estão funcionando. Como neste caso estamos lidando com números de precisão arbitrária você precisa de uma ferramenta auxiliar. Por exemplo, uma calculadora poderosa ou uma outra biblioteca de inteiros grandes.

Bom, eu já tinha disponibilidade o código há um tempinho, mas só agora resolvi escrever o blog. Ah, dê uma olhada nas notas antes…

O código está aqui: vlint (Very Long Integer)

Tchau!

Leandro Melo

Versão em Português

A couple months ago I decided to implement the fundamental arithmetic operations for integers with arbitrary precision. The main reason was mostly curiosity than need, since there are plenty of good libraries focused on this. Still, I thought it would be worth the exercise and the fun.

Originally I was after something quite simplistic, but along the way the code started gaining more form and it eventually became a C++ class with well defined API. Basically, the logical connections were prompting, one thing led to another, and in the end I implemented more than I actually planned.

The reference I used was the volume for Seminumerical Algorithms from Knuth‘s book The Art of Computer Programming. It’s cool that although the book does worry about giving implementation tips, there still room for many questions that appear in the process of converting the algorithmic descriptions into the final C++ code.

Interesting things I observed…

  • Prior to anything else, the first step was to think about which model should the representation rely on. Well, in the binary world the common option is two’s complement. However, in an arbitrary precision case from a higher level the numeric base is typically a big integer, so the sign and magnitude approach seems to be a good fit.
  • Considering sign and magnitude, there’s still a flexible aspect which is how exactly to handle the zero. Explicitly qualify it or use only the two signs and infer it from the values? I found it simpler and more consistent to have an extra attribute which tells whether the number is positive, negative, or the zero.
  • Which data-structure and where to place the most significant digits? Normally a vector is a good option. It provides random access, it’s possible to control allocation with certain predictability, no space overhead, memory is contiguous and there’s a “natural” mapping on how we do operations. Regarding the position of the digits, placing the most significant ones at the end of the vector is the conventional way, since it allows the integer to increase/decrease in an efficient manner.
  • Following on the paragraph above, there’s the need to eliminate leading zeros which might result from some operations. This easies the implementation in general. Besides that, because the zero is not represented only through the magnitude I had to add a few “artificial” verifications after some calculations.
  • Addition, subtraction, and multiplication are quite intuitive. Nothing really elaborate, the only care needed is when manipulating the carry. On the other hand, the division with remainder is a different story. Obviously you can go for an algorithm of consecutive subtractions, but I wanted something a bit fancier. The algorithm presented on Knuth’s book is based on normalizing the divisor and dividend and on the estimation of a value for the quotient. Some details are non-trivial and I would say there’s a potential for errors in the implementation. ;-) Note: There are two corrections from the algorithm available in the errata.
  • Going out of the plan… It turns out that for the division with remainder I had to implement the shift left/right operations. They are recommended for the normalization phase. The other operations which are a natural evolution for the sake of usability are the conversions between the base representation and the decimal base. This is in order to make construction and printing of the integers easy through a string.
  • Testing, of course. After all you need to make sure somehow that things are working as expected. Since in this case we are dealing with arbitrary precision you need an auxiliary tool. For instance a powerful calculator or maybe another big integer library.

Well, I had already published the code a while ago, but only now I decided to blog about it. Oh, and take a look at the notes…

You can find it here: vlint (Very Long Integer)

Tchau!

Leandro Melo

Qualidade de código

Go to english version

Recentemente tive a oportunidade de assitir uma palestra do Mark Shuttleworth na Linux Tag 2010. Naturalmente, foram abordados os assuntos de open-source de uma forma mais abrangente e do próprio Ubuntu. Não consegui acompanhar todos os detalhes pois não sou tão envolvido assim com Linux. Mas achei bem interessante quando ele abordou a questão de qualidade de código.

Em particular, gostei bastante do que foi dito com relação à revisão de código. É relativamente comum quando programadores externos a um projeto ou simplesmente menos experientes têm seus códigos revisados por alguém do núcleo principal. O que pode não ser tão perceptível imediatamente é que essa prática também é extremamente útil no sentido inverso. Dessa forma, o aprendizado se torna bem mais motivante já que o novo programador é diretamente exposto ao que é considerado um modelo de código de boa qualidade dentro de determinado contexto.

Com certeza essa é uma prática já utilizada em vários projetos e empresas. Mas talvez não tanto quanto poderia ser. Portanto, se sua equipe ainda não a utiliza vale à pena considerar esse item para as próximas discussões sobre melhorias no processo de desenvolvimento.

Continuando o assunto, também comecei a refletir sobre a existência de uma definição amplamente aceita e, principalmente, adotada na prática do que é um código de boa qualidade. Creio que na grande maioria dos ambientes profissionais esse ponto é teoricamente tido como importante. Mas será que na prática é assim mesmo? Além disso, será que a meritocracia empregada no dia-a-dia dos envolvidos considera de forma justa esse fator?

Arriscaria dizer que boa parte dos engenheiros de software já passaram por uma situação na qual foram cobrados por terem atrasado no desenvolvimento de determinado software. Realmente estimativas não são fáceis de serem feitas. E uma das razões que podem deixá-las falhas é quando são baseadas em uma visão simplista e puramente comparativa com base em algum componente ou biblioteca escrita por determinado programador dentro de um determinado tempo. Sendo que em certos casos esse tal programador acaba sendo considerado como um exemplo pois executa suas tarefas com rapidez e “eficiência”.

O problem nesse tipo de situação é que o simples fato de que alguém conseguiu escrever determinado software em determinado tempo significa algo próximo de nada se pontos relacionados à qualidade do código não forem avaliados. Além dos fatores óbvios que são o software atender aos requisitos desejados e conter poucos (quem sabe zero) bugs, a lista abaixo resume minhas principais expectativas com relação a um bom código-fonte.

  • Em primeiro lugar, o código deve ser altamente inteligível e limpo. Entender um programa é fácil para qualquer computador, mas nem sempre para um ser humano.
  • Deve haver boa reutilização de código. Trechos relativamente parecidos, funções compridas, abusos de herança, classes sobrecarregadas, entre outros, não são bons indicadores.
  • Mudanças de comportamento não muito complexas mas também não triviais devem ser suportadas por uma base flexível.
  • Pontos de extensão devem ser fornecidos. Idealmente da forma mais genérica possível.
  • Os recursos da linguagem de programação em questão devem ser usados da forma apropriada. Tanto o conhecimento da definição e estrutura da linguagem, assim como da API, devem ser visíveis.
  • Teste de unidade para os principais componentes. Dependendo do caso testes mais abrangentes também.
  • O código deve possuir uma única “cara”, desde técnicas/estilos de códificação até padrões arquiteturais. Isso promove a integridade conceitual do código.

Pode ser que os itens acima não sejam novidade para ninguém. No entanto, chutaria dizer que na maioria dos projetos eles não são levados em consideração de forma profunda. Isso devido à falta de visão (da importância do assunto) ou até mesmo devido à falta de competência e conhecimento técnico para realizar uma avaliação detalhista e precisa.

Além disso, há ainda um fator complicador: o tempo. Nem sempre é possível chegar a uma conclusão definitiva com relação à qualidade de um código se não houver momentos em que seja necessário lidar diretamente com extensões ou qualquer tipo de manutenção sobre ele (incluindo, naturalmente, correção de bugs). Nesses casos as facilidades ou dificuldades encontradas durante tarefas reais podem contribuir significativamente para um veredito final. E para que isso aconteça é necessário que o software tenha passado por etapas relevantes de seu ciclo de vida. Não há substituto para o tempo.

Já vi muitas iniciativas com intuito de melhorar a qualidade de um produto tendo foco em gestão ou modelos processuais. Apesar de ajudarem (se muito ou pouco, depende do caso eu acho), elas nem sempre atuam diretamente na essência do problema (na verdade, da solução) que é a qualidade do código. Para investir em qualidade de produto é obrigatório investir, entre outras coisas, na qualidade do código-fonte. Portanto, tenha revisores de código que realmente entendam bem de fundamentos da computação (como algoritmos e estruturas de dados), que conheçam bem as linguagens de programação, as tecnologias envolvidas, boas práticas de programação e arquitetura, e que gostem de estudar.

Leandro Melo

Source-code quality

Ir para versão em português

Recently I had an opportunity to watch a talk from Mark Shuttleworth at Linux Tag 2010. The subject of open-source was naturally approached together with discussions about Ubuntu. Since I am not that involved with Linux I could not follow all the details. Anyway, I thought it was particularly interesting when the topic of source-code quality was touched.

I really liked what was said with regards to code review. It is relatively common when programmers outside to the project or simply less experienced have their code reviewed by the core people. What could not be perceptive at the first sight is that this practice can also be extremely useful in the reverse way. Thus, learning becomes much more motivating since the new programmer is directly exposed to what is considered a model of good code quality within a given context.

Surely this is a practice already used in several teams in many projects. But maybe not as much as it could be. So if your team have not used it yet it might be worth to consider this item for the forthcoming discussion on improvements in the development process.

Continuing on the subject, I also began to reflect whether there is any widely accepted definition and especially adopted in practice of what is source-code of good quality. I think that in most professional environments that point is considered important at least in theory. But how does that reflect in practice? Also, does the meritocratic system applied (intentionally or not) on the involved engineers consider this factor in a fair manner?

I venture to say that a lot of software engineers have gone through a situation in which they were blamed for having delayed the development of certain software. Yes, estimates are not easy to make. Still, one of the reasons that may cause them to fail is when they are based on a simplistic and purely comparative basis of a component or library written by a particular programmer within a particular time frame. Eventually such programmer might even end up being taken as an example because she performs her tasks quickly and “efficiently.”

The problem in this kind of situation is that the mere fact that someone managed to write some code in some time means next to nothing if issues related to the quality of the code are not evaluated. Besides the obvious factors which are that the software meets the desired requirements and contain few (perhaps zero) bugs, the list below summarizes my main expectations of a good code.

  • First, the code should be highly intelligible and clean. Understanding a program is easy for any computer, but not always for a human being.
  • There should be good code reuse. Snippets which are very similar, long functions, abuses of inheritance, overloaded classes, among others, are not good indicators.
  • Not too complex changes which are not trivial either should be easily supported by a flexible basis.
  • Extension points should be provided. Ideally as generically as possible.
  • The features of the programming language in question must be properly used. Both the knowledge of the definition and structure of the language, as well as the API, should be visible.
  • Unit tests for the main components. Depending on the case even broader tests.
  • The code should have a single ‘face’, since programming techniques/coding style to architectural patterns. This promotes the conceptual integrity of the code.

It may be that the above are not news to anyone. However, one could take a wild guess saying that in most projects they are not taken into account from a deep perspective. This may be due to a lack of vision (of the importance of the issue) or even due to the lack of expertise and technical knowledge to conduct a detailed and precise analysis.

Moreover, there is a complicating factor: time. Not always you can reach a definitive conclusion regarding the quality of a code if you do not go through moments when it is necessary to deal with extensions or any kind of maintenance (including, of course, bug fixes). In such cases the ease or difficulties encountered in real tasks can contribute significantly to a final verdict. And for that to happen the software needs to have gone through relevant stages of its life cycle. There is no substitute for time.

I have seen many initiatives aiming to improve quality of a product with focus on management or procedural models. Although they do help (how much depends on the case I guess), they do not always act directly on the essence of the problem (actually, the solution) which is the quality of the source-code. To invest in the quality of a product it is fundamental to invest, among other things, in the quality of the code. Therefore, have good code reviewers who really understands programming principles (such as algorithms and data structures), who are very familiar with the programming languages and technologies involved, which are aware of well known design and architectural practices, and who like to study.

Leandro Melo

Recentemente resolvi fazer alguns testes relacionados a inicialização de objetos em C++ em diferentes ambientes. Tive algumas surpresas…

O padrão C++ define três tipos de inicialização:

  • zero-initialization – Neste texto traduzido como inicialização por zeros.
  • default-initialization – Traduzido como inicialização padrão.
  • value-initialization – Traduzido como inicialização por valor

O significado de cada um é explicado detalhadamente [§8.5.5]. Mas a linguagem e formalismo utilizados em documentos técnicos normalmente não são os mais triviais possíveis. Portanto, não é raro aparecerem algumas dúvidas.

O caso em que estava interessado é relativamente simples e abrange apenas um sub-conjunto das regras de inicialização. Colocando em termos práticos, queria analisar qual seria o valor de um membro inteiro de um struct em situações distintas.

Além de coisas mais simples e conhecidas como chamadas convencionais a construtores, as informações do padrão que considerei pertinentes para o seguinte trecho de código são as seguintes:

  • Um objeto construído através de um par vazio de parêntesis deve passar por uma inicialização por valor [§ 8.5.7]. Note que isso se aplica a uma inicialização do tipo T * t = new T(); [§ 5.3.4] ou até mesmo do tipo T();[§ 5.2.3].
  • Quando um objeto de tipo não-POD (Plain Old Data) não tem nenhum inicializador ele deve passar por uma inicialização padrão. Esse é o caso, por exemplo, de uma expressão como T * t = new T; ou T t;. No entanto, se o objeto for de tipo POD ele e seus sub-objetos não passam por inicialização alguma e, consequentemente, têm valor indeterminado [§ 8.5.9].
  • Uma inicialização padrão de um objeto tipo POD como int (não para arrays) resulta em uma inicialização por zeros [§ 8.5.5].
  • Uma inicialização por valor de um objeto de um tipo classe (excluindo union) promove uma inicialização por valor de seus membros não-estáticos e classes bases.
struct PlainOldData //POD
{
  int id_;
};

struct NonPOD_CompilerCtor
{
  int id() const { return id_; }

private:
  int id_;
};

struct NonPOD_UserCtor
{
  NonPOD_UserCtor() : id_() {}
  int id() const { return id_; }

private:
  int id_;
};

O programinha que escrevi apenas cria objetos dos tipos definidos acima com duas sintaxes diferentes. Em seguinda, inspeciono os valores do membro id_.

int main()
{
  PlainOldData * a = new PlainOldData;
  NonPOD_CompilerCtor * b = new NonPOD_CompilerCtor;
  NonPOD_UserCtor * c = new NonPOD_UserCtor;

  //...

  PlainOldData * d = new PlainOldData();
  NonPOD_CompilerCtor * e = new NonPOD_CompilerCtor();
  NonPOD_UserCtor * f = new NonPOD_UserCtor();

  //...
}

Os valores que esperava para o membro id_ são os seguintes:

  • a – O objeto é criado sem parêntesis e o tipo é POD. Logo, não há inicialização e o valor de id_ é indeterminado.
  • b – O objeto é criado sem parêntesis e o tipo é não-POD. Logo, a inicialização é padrão. No entanto, o construtor é o gerado pelo compilador, o qual não faz inicialização de nenhum membro. Portanto, o valor de id_ é indeterminado.
  • c – O objeto é criado sem parêntesis e o tipo é não-POD. Novamente, temos inicialização padrão. Agora, com a diferença de que existe um construtor definido pelo usuário que inicializa explicitamente id_. Este, então, sofre inicialização por valor, a qual resulta em inicialização por zeros devido ao fato de int ser POD.
  • d – O objeto é criado com parêntesis vazios e, assim como nos outros dois casos abaixo, a inicialização é por valor. Este caso se trata de um POD. Logo, a inicialização por valor resulta diretamente em inicialização por zeros.
  • e – Como dito acima, o objeto sofre inicialização por valor, já que foi criado com parêntesis vazios. O membro id_ também sofre inicialização por valor que, devido ao fato de se tratar de um POD, resulta em inicialização por zeros.
  • f – Novamente, inicialização por valor. Naturalmente, o construtor definido pelo usuário é invocado. Este inicializa por valor o membro id_, que por ser um POD sofre inicialização por zeros.

Testando com compiladores diferentes obtive os seguintes resultados.

Compilador a b c d e f
G++ 4.2.4 0 0 0 0 0 0
Mingw – G++ 4.4.0 Indeterm. Indeterm. 0 0 0 0
VC++ 2008 Express Indeterm. Indeterm. 0 0 0 0
Digital Mars 8.5.1 0 0 0 Indeterm. 0 0

Para completar a avaliação também resolvi utilizar sintaxes correspondentes às usadas acima só que com alocação na pilha.

int main()
{
  PlainOldData aa;
  NonPOD_CompilerCtor bb;
  NonPOD_UserCtor cc;

  //...

  PlainOldData const& dd = PlainOldData();
  NonPOD_CompilerCtor const& ee = NonPOD_CompilerCtor();
  NonPOD_UserCtor const& ff = NonPOD_UserCtor();

  //...
}

Já que nesses casos o fator determinante na inicialização é a presença ou não dos parêntesis, esperava obter exatamente os mesmos resultados do código anterior. Apenas uma observação: As referências para const dos últimos três casos são apenas uma estratégia artificial para testar a inicialização através da expressão X(), já que X x(); é na verdade a declaração de uma função que não recebe parâmetros e retorna X.

Desta vez os resultados foram os seguintes:

Compilador

aa

bb

cc

dd

ee

ff

G++ 4.2.4

Indeterm.

Indeterm.

0

0

0

0

Mingw – G++ 4.4.0

Indeterm. Indeterm. 0 0 0 0
VC++ 2008 Express

Indeterm.

Indeterm.

0

0

Indeterm.

0

Digital Mars 8.5.1

Indeterm.

Indeterm.

0

Indeterm.

0

0

Bom, como pode ser visto encontrei muitas variações de comportamento entre os compiladores. Espero não ter cometido alguma interpretação errônea pelos meandros do padrão, mas os únicos compiladores que foram conformantes na primeira leva de testes foram o G++ 4.4.0 (Mingw) e o Visual C++ 2008. Já para a segunda parte, na qual esperava exatamente os mesmos resultados, apenas o G++ 4.4.0.

Então, quais são as opções para lermos um arquivo inteiro para memória (armazenando-o em uma std::string, por exemplo) em C++? O programa abaixo ilustra algumas alternativas simples.

#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <string>

void stringstream_read_file();
void istream_iterator_read_file();
void istreambuf_iterator_read_file();

int main()
{
  //Lê copiando o buffer file stream para o string stream.
  stringstream_read_file();

  //Lê iterando pelo stream e fazendo extração com operator>>.
  istream_iterator_read_file();

  //Lê iterando diretamente pelo buffer e copiando caracteres.
  istreambuf_iterator_read_file();

  return 0;
}

void stringstream_read_file()
{
  std::ifstream fs("file.txt");
  if (!fs.good())
    std::cout << "Error." << std::endl;
  else
  {
    std::ostringstream ss;
    ss << fs.rdbuf();
    std::cout << ss.str() << std::endl;
  }
}

void istream_iterator_read_file()
{
  std::ifstream fs("file.txt");
  if (!fs.good())
    std::cout << "Error." << std::endl;
  else
  {
    fs.unsetf(std::ios_base::skipws); //Para manter os espaços.
    std::string s((std::istream_iterator<char>(fs)), std::istream_iterator<char>());
    std::cout << s << std::endl;
  }
}

void istreambuf_iterator_read_file()
{
  std::ifstream fs("file.txt");
  if (!fs.good())
    std::cout << "Error." << std::endl;
  else
  {
    std::string s((std::istreambuf_iterator<char>(fs)), std::istreambuf_iterator<char>());
    std::cout << s << std::endl;
  }
}

Outras idéias?

Seguir

Obtenha todo post novo entregue na sua caixa de entrada.