hisham hm

Triângulos

Coisas que o Hisham pensa enquanto toma banho:

“Todo mundo lembra do que é um triângulo retângulo… e acho que triângulo equilátero também… afinal, equi-látero, lados iguais.

Mas acho que ninguém lembra do que diabos é um “triângulo escaleno”… que nome horrível. Como é o nome daquele com dois lados iguais, é escaleno mesmo? Não lembro! Pra tu ver. A diferença que um nome bom como “equilátero” e um nome ruim como “escaleno” fazem. Um deles a gente sempre lembra qual é.

Taí um bom problema: e se eu fosse dar um nome melhor para aquele triângulo com dois lados iguais, que nome seria? Duolátero? Bom, aí parece que o triângulo só tem dois lados, o que é um absurdo. Bom, o triângulo com dois lados iguais é aquele que se tu traçar uma reta saindo bem meio da “ponta” ela corta bem no centro do lado oposto, né… ficam dois triângulos retângulos iguaizinhos um de cada lado. Taí: “triângulo simétrico”. Aposto que se esse fosse o nome todo mundo ia lembrar qual triângulo é esse! Problema resolvido!”


You can’t automate SemVer, or: There is no way around Rice’s Theorem

Rice’s Theorem, proved in 1951, states that it is impossible to write a program that performs precisely any non-trivial analysis of the execution of other programs. More precisely, that’s impossible to code an analyzer for some non-trivial property that is able to decide whether an any given analyzed program has that property or not. And by “trivial property” we mean a property that either _all_ algorithms in the world have or _none_ has. So, yeah, “non-trivial property” is basically any property you can think of: “does it ever calculate 5 + 2”, “does it always use less than 10MB of memory”, “does it ever print something to the screen”, “does it ever access the network”?

At this point you might say “wait! I can write a program that checks if programs access the network or not! We can parse the code and if there are no calls whatsoever in it to any networking code such as connect(), then it doesn’t access the network!”. Sure, you can do that: but if the code has calls to connect(), you can’t decide for sure that it will access the network when it’s executed.

In 1936 Alan Turing proved that it is impossible to write a program that solves the Halting Problem, that is, to write an analyzer that checks programs and tells if it always terminates (”halts”) or it might enter an endless loop given some specific input. Okay, that’s a classic result, but that’s one property, how can Rice’s Theorem say we can’t make an analyzer for any property at all, even the silliest ones?

The proof for this amazingly powerful theorem is surprisingly simple. Turns out that if we had an analyzer for any silly property, we could use it to make a Halting Problem analyzer (which Turing proved to be impossible). Like this:

bool my_halting_problem_analyzer(Code analyzedProgram) {
   Code modifiedProgram = analyzedProgram + "; someCodeWithSillyProperty();"
   return my_silly_property_analyzer(modifiedProgram);
}

If the code in analyzedProgram always terminates, then the code in modifiedProgram will always reach the part that has the silly property, so my_silly_property_analyzer will return true, and my_halting_problem_analyzer returns true as well. If there is some input that makes the analyzedProgram hang in a loop, that means there’s some input that makes the silly property fail, resulting in false. Yay, we solved the Halting Problem using the silly property analyzer! Not.

Of course, this explanation is quite simplified1, so head to Wikipedia and your favorite formal languages book for the precise details. But the point stands that general semantic analysis of programs is impossible.

In particular, you can’t write a program that takes versions 1.0 and 1.1 of any program X and answer the question: “do they behave the same?”. In other words, it’s impossible to write an analyzer that looks at your master branch before you make a release and answers the question “should your new release tag be a major, minor or tiny release” according to the rules of SemVer (or any other API-compatibility-bound set of rules, for that matter).

This is because API compatibility is not only based on syntactically-expressible issues (that is, type signatures for functions and data structures). Any semantic changes to the code also break compatibility. A function may change its behavior but not its type signature (it still returns a string, but it used to be lower-case and it’s now upper-case), a struct can change they way it is used but the fields remain the same (field foo returned numbers from 0 to 10 and -1 when executed on Sundays, now it returns -1 on Saturdays as well). An automated tool won’t catch all this.

So, it is possible only to write a “pessimistic” tool, that may detect lots of situations syntactically and give the bad news: “hey, you must increment the major version here!”. But you can’t write a tool that is always able to look at code semantically and say the good news: “I assure you that no API behaviors have changed, you can safely name this a tiny version increase.”2

Yes, you can use test suites as an approximation for detecting semantic changes in API behaviors beyond type signatures and data structures. That would certainly improve your pessimistic analyzer — you’d be able to detect more situations where “you must increment major”. But even then it can only go so far, because in practice one can’t test for every possible input/output combination, so you still can’t be 100% sure. fuzz testing has uncovered bugs and unexpected behaviors even in programs with extensive test suites; as Dijkstra famously said, “Testing shows the presence, not the absence of bugs.” — likewise, test suites can show inconsistencies to the API specification, but not their adherence. So they can’t be taken to represent the semantics of a program entirely.

Anyway, in the end of the day, Rice’s Theorem shows us that general bullet-proof analysis of program behavior is not attainable, so no tool will ever be able to compare codebases and always tell us precisely that a new release is really “tiny-safe”. Semantic versioning just can’t be automated.


Uma leitura econômica sobre a crise política

Domingo passado eu vi algo que mais uma vez me deu subsídios para a minha teoria sobre a atual crise política. Eu assisti ao Fantástico.

O Fantástico é um programa que sempre repercute o grande fato da semana, que basicamente define a agenda do que estará “na boca do povo” na segunda-feira pela manhã. Bom, o grande fato da semana passada foi a condução coercitiva do Lula, então seria de se esperar que a maior reportagem do programa seria sobre isso.

Mas não foi. Provavelmente por terem se dado conta de que quanto mais espaço na mídia é dado ao Lula, pior para a oposição a ele. Muito já se discutiu sobre como ele usa da sua oratória e apelo popular para se colocar como vítima da situação, nem vou chover no molhado aqui. O curioso é qual foi a grande reportagem do Fantástico.

A maior fatia de tempo do Fantástico foi dedicada a mostrar mega-obras da Copa inacabadas. Grandes elefantes brancos, como terminais de ônibus sub-utilizados, linhas suspensas de VLT que ligam nada a lugar nenhum, cada uma delas retratadas através da história de uma pessoa da classe operária que seria beneficiada se a obra tivesse sido concluída. Em cada história, o custo milionário (ou bilionário!) da obra, a menção a verbas federais e estaduais, a justificativa do governo estadual responsável pela obra dizendo invariavelmente que “rompeu o contrato e vai fazer um novo e terminar a obra” e o nome da empreiteira envolvida. Odebrecht. OAS. Andrade Gutierrez. Na quarta, Mendes Júnior, menos presente nos noticiários da crise, aí então fizeram o complemento “também indiciada na Lava-Jato”.

Aí estão, estabelecidas, as grandes vilãs da corrupção no Brasil. Ao final de tudo, quando a poeira da disputa política baixar (e vários inimigos da crise de hoje terão certamente apertado as mãos), haverão nomes que enfim serão unanimidade como saco de pancadas: as empreiteiras. A esquerda, com justiça, as demonizarão com o argumento do financiamento privado de campanha e da corrupção inerente a esse modelo. A direita, com justiça, as demonizarão por terem feito cartéis, subvertido a livre concorrência e compactuado com esse governo que aí está. Enfim, coxinhas e petralhas concordarão com alguma coisa, e a liderança política que aparecer com esse discurso ganhará o apreço popular “acima da polarização” e a crise política, enfim, vai passar.

O custo real disso tudo será na economia nacional. Há mais de seis meses, vi um desses debates na GloboNews, à época que os cabeças das empreiteiras começaram a ser presos. Lembro do mediador perguntando para os analistas convidados:

“Mas tem tanta obra enorme no Brasil, Belo Monte, etc. — se todas as grandes empreiteiras estão envolvidas e elas quebrarem, quem vai tocar as obras?”

O analista não piscou para responder: “Ah, os americanos, os japoneses.”

Ao olhar a lista de doações das campanhas presidenciais, independentemente de partido, a gente vê basicamente a lista das maiores empresas de capital nacional. Ao olharmos a lista do Valor1000 das maiores empresas do Brasil, vemos que as empresas estrangeiras dominam todo tipo de área (eletroeletrônicos, veículos, telecom, etc.), e as empresas brasileiras no alto da lista se resumem a energia, construção civil e agronegócio. Não por acaso, são as áreas no centro da crise.

O Brasil é um país emergente, em desenvolvimento, e por esse processo de desenvolvimento passa a construção de uma infraestrutura enorme que o país precisa para crescer. Infraestrutura essa que já está consolidada em outros lugares já desenvolvidos. Decimar a indústria de infraestrutura nacional vai ser o saldo da crise, e a madura indústria de infraestrutura estrangeira está pronta para ocupar esse vazio.

Os grandes movimentos no tabuleiro do jogo em andamento não são o destino do Lula, ou do Cunha, ou da passeata na rua ou do julgamento no STF. Esse é o circo. São as renegociações do pré-sal, são as quebras dos contratos de infraestrutura, é o futuro das indústrias que ainda são nacionais.

Não estou aqui defendendo Odebrecht, Andrade Gutierrez ou quem quer que seja. Mas quando as empreiteiras que constroem o país forem todas estrangeiras, elas vão organizar os seus cartéis lá fora, longe do alcance dos grampos, batidas e operações da PF.


First time playing with OpenBSD

A list of notes on my first experience with OpenBSD:

* It wasn’t obvious at first which file to download, navigating their FTP site. I ended up with cd58.iso, which was the right choice. A tiny 7.8MB ISO!
* As soon as I typed “OpenBSD” as the VM name in VirtualBox, it gave me OpenBSD defaults. It defaulted to 64MB of RAM (only!), but I chose 256M, and the default 2G disk image.
* The first boot gave me a few options, including “Install” and “Autoinstall”. I chose “Autoinstall” since I thought that would install with the defaults, but it looked for an installation script in the local network (and obviously didn’t find it). Reboot, “Install” and off we go.
* No Dvorak options in the list of keyboards in the installer.
* I went with the default options and installed all offered packages (it offered me a list of coarse-grained bundles). It asked me about creating users, partitions, configuring network and if I wanted to run sshd by default.
* To enable Dvorak, the internet told me to do kbd us.dvorak nice.
* To make it permanent, I just grepped /etc for kbd and found out that cat us.dvorak > /etc/kbdtype would suffice.
* To install things, become root and then use pkg_add. For example: pkg_add wget
* By default it includes df but not free.
* To get color in the terminal, set TERM=wsvt25. htop showed in its usual colors!
* The default PATH includes the current (.) directory! Take that, Linux status quo!
* iconv is installed under /usr/local, and its library exports symbols with names such as libiconv_open instead of the usual iconv_open, which fools the typical AC_CHECK_LIB test in Autoconf. (In the source code, iconv_open works, so I guess iconv.h uses #define to translate the name. Added a hack to Dit to make it build cleanly out-of-the-box.


htop 2.0 released!

This week I finally released htop 2.0.0!

What’s new in htop 2.0

Since version 2.0, htop is now cross-platform!
Check out the video and slides of my presentation at FOSDEM 2016
about how this came to be. This release includes code supporting Linux, FreeBSD, OpenBSD and Mac OS X.

There are also, of course, some new features:

…And of course, lots of other tweaks and fixes!

Changelog

The changelog with the main new changes follows below. Special thanks
to everyone who contributed for this release, through bug reports, bug
fixes, new features and financial support for the platform abstraction
layer project!