🔗 Programming language research is a Human Science
Some people often tell me that, due to my various interests, they actually find it weird that I ended up studying Computer Science and not some of the Humanities. I try to explain them that my specific field of interest, programming languages, is actually a Human Science. And that is so for one simple reason: if there was no people, if computing was restricted to computers and there was no human factor, machine language — the binary code that processors actually run — would be enough. Programming languages exist because of people, not because of computers.
This quote puts it rather nicely:
“Programming is a science dressed up as art, because most of us don’t understand the physics of software, and it’s rarely if ever taught. The physics of software is not algorithms, data structures, languages and abstractions. These are just tools we make, use, throw away. The real physics of software is the physics of people.
Specifically, our limitations when it comes to complexity, and our desire to work together to solve large problems in pieces. This is the science of programming: make building blocks that people can understand and use easily, and people will work together to solve the very largest problems.” — Peter Hintjens et al., ØMQ - The Guide
Programming languages are the bridge we use to communicate our ideas to the machine, but also to communicate our ideas among our fellow programmers, and even to ourselves. Like natural languages, programming languages are constantly evolving (at a much faster pace, even!), as we try to balance the tension between being precise and unambiguous and being understandable and eloquent; to be able, in the same piece of prose, to tell a machine what to do and to tell another person what we mean. And this is by no means a matter of numbers.
🔗 Os suíços e suas armas, parte 2: contrapontos
Recebi hoje de várias pessoas o link para o artigo “Os suiços [sic] e suas armas“, uma tradução de um texto da NRA, organização americana pró-armas, considerado o grupo de lobby mais influente dos EUA.
O assunto é interessante e relevante, mas duas coisas me incomodam a respeito do texto.
Uma, menos importante, é que certamente muita gente que lê tira dele apenas um argumento para conversa de churrasco de fim de semana do tipo “ó, mas na Suíça todo mundo tem arma e funciona!” (vide a seção de comentários).
A segunda, mais importante, é a fraqueza dos argumentos. Embora a experiência da Suíça seja sim algo a ser estudado e compreendido ao se falar da relação de uma sociedade com armas, e embora o texto faça ressalvas no início e no final de que tratam-se de sociedades diferentes e isso deve ser levado em conta, os argumentos centrais são distorções construídas de modo a pintar um quadro de que botar arma na casa de todo mundo “resolve”. Vejamos:
Num país onde o povo é armado não pode haver outra forma de governo que não seja democrático.
Mentira. Os dados desmentem: o Yemen tem propriedade de armas per capita maior que a Suíça e é uma ditadura, assim como a Arábia Saudita, que também figura no Top 10.
Uma velha anedota suíça reza que o príncipe alemão Wilhelm Hohenzollern certa vez, quando em visita a Suíça, foi convidado a assistir um dos inúmeros treinamentos militares a que os cidadãos desse país são submetidos. A um dado momento perguntou ao comandante do exercício: Quantos homens em armas você possue? Foi-lhe respondido: Um milhão. O príncipe, posteriormente Kaiser da Alemanha, então indagou:
O que você faria se cinco milhões de meus soldados cruzassem sua fronteira amanhã? Ao que o comandante suíço replicou: Cada um de meus homens daria cinco tiros e iria para casa!
Uma bela anedota pró-armas, mas mesmo que isso fosse verdade no tempo do Reino da Prússia, todos nós sabemos que hoje em dia isso é balela. Desde os avanços tecnológicos da Primeira Guerra Mundial, uma guerra não se vence pelo número de homens. E essa é uma falha central do texto: dizer que a população da Suíça ter um rifle em casa é o que defende o país. Estamos na era de armas nucleares e aeronaves não-tripuladas. Dizer em negrito e itálico que “o suíço não tem um exército: eles são o exército” pode ser muito bonito e patriótico, mas não faz disso verdade. O que protege a Suíça são os seus acordos internacionais.
Como sempre os anti-armas estão errados, mas isso não torna o grupo favorável necessariamente certo.
Não me classifico como “anti-armas”, mas acho uma frase dessas um absurdo para um texto argumentativo.
Completamente mobilizado, o exército suíço apresenta 15,2 homens por quilometro quadrado; em contraste, os EUA e a Rússia tem apenas 0,2 soldados por Km2.
A comparação é ridícula, já que não leva em conta a dimensão e densidade demográfica dos países.
Realmente, somente Israel tem mais exército por Km2.
…e veja como as coisas são pacíficas por lá. Como podemos ver, isso não prova nada para nenhum dos lados do argumento.
Em 1977, o movimento INICIATIVA MUNCHENSTEIN propôs permitir aos cidadãos a escolha do trabalho social, ou em hospitais, como alternativa ao serviço militar. A proposição foi rejeitada nas urnas e nas 2 casas do parlamento (o “Bundesversammlung’s Nationalrat” e o “Standerat”).
O que o texto não diz é que em 1992 essa proposição foi aprovada. Com 83% dos votos, os suíços votaram pela introdução de um artigo adicional à constituição, permitindo serviço civil alternativo. A lei entrou em vigor em 1996, e agora os suíços podem optar por prestar serviço civil em ONGs, trabalhando com agricultura, hospitais, centros para a juventude, proteção ambiental, pesquisa em universidades, reflorestamento, etc. Os tempos mudaram e as necessidades da sociedade também.
Os ultrajados usuários de armas suíças formaram, então, um grupo chamado Pro Tell, em homenagem do herói nacional Guilherme Tell.
Agora ele é um “herói nacional”, enquanto o próprio texto anteriormente estabelece que trata-se de uma lenda. Como muito dos argumentos do texto que tenta justificar políticas “atuais” (que, como acabamos de ver, não correspondem à realidade atual) com anedotas históricas, o grupo Pro Tell sustenta o seu nome na imagem mítica do herói armado.
A maioria dos suíços ainda vive em famílias patriarcais tradicionais. De fato, a Suíça tem a mais baixa porcentagem de mães trabalhando em relação a qualquer país europeu. Enquanto no resto do mundo as mulheres estavam lutando por igualdade de direitos, os suíços ainda estavam decidindo se as mulheres poderiam ou não votar (a longa demora na aprovação do sufrágio feminino, deve ter algo a ver com a questão dos direitos civis e o serviço militar).
As escolas são severas e os adolescentes têm menos liberdade do que na maior parte da Europa. Os estudos mostram que os adolescentes suíços, diferentemente daqueles nos outros países, sentem-se mais próximos de seus pais do que de seus amigos. A comunicação entre as gerações é muito fácil.
Entre os fatores que contribuem para a harmonia entre gerações está o serviço militar, que oferece uma oportunidade para todos os grupos masculinos interagirem entre si.
Eu conseguiria imaginar alguém da National Rifle Association escrevendo isso para o público conservador americano, mas será que algum dos meus amigos que mandou esse link acredita nessas coisas, e acha que são pontos positivos famílias patriarcais, menos direitos às mulheres, escolas severas e menos liberdade para os jovens? Bom, uma coisa que posso dizer é que outro lugar em que todas essas coisas são igualmente comuns é no mundo árabe, e portanto não acho que essas coisas geram sociedades saudáveis e democráticas.
Esse “exemplo histórico de democracia” está longe de ser um modelo ideal. As mulheres só obtiveram direito de voto em 1971, e apenas em 1985 ganharam direitos iguais no Código Civil, com uma votação de 60% a 40%.
Tudo isso, juntamente com várias outras atividades levadas a cabo na Suíça envolvendo diversas faixas etárias, têm servido para inibir a separação de gerações, alienação, e o crescimento de uma cultura jovem à parte, que tem se tornado, de maneira crescente, uma característica de muitos outros países desenvolvidos.
O texto diverge rapidamente a uma apologia ao conservadorismo.
Será que se o exército começasse a vender canhões e metralhadoras a preços subsidiados ao povo haveria um declínio da criminalidade em nosso país? Certamente não, nos primeiros trinta anos.
Como assim “nos primeiros trinta anos”? A ressalva é risível, como se distribuir canhões e metralhadores levaria a uma estabilidade de longo prazo. O próprio texto coloca que a cultura militarista na Suíça se sustenta em uma construção social de séculos e omite outros fatores importantes que viabilizam a posição de neutralidade do país. Fatores esses que, ao meu ver, são hoje os essenciais.
A Suíça manteve-se em paz no período das guerras mundiais por ser o “banco do mundo”. O franco suíço era a única moeda livremente convertível em escala mundial. Assim como tácitos acordos mantinham os QGs das forças aéreas dos Aliados e do Eixo intactos enquanto os demais prédios (e a população civil) de Berlim e Londres eram bombardeados, o valor estratégico para ambos os lados de manter instituições financeiras sólidas imunes à guerra era bem conhecido e nada tinha a ver com os rifles que a população civil guardava em casa.
Hoje, na realidade de uma Europa em processo de gradual unificação, a Suíça mantém-se como o “loophole” da União Europeia. Enquanto os países da Europa sujeitam a sua população a um conjunto cada vez maior de leis comuns, o sistema financeiro europeu tem na Suíça um ponto de apoio imune às regulamentações da União. Os acordos da UE comumente incluem ou excluem a Suíça seguindo uma lógica que mantém o status “especial” das instituições financeiras suíças enquanto gradualmente sujeitam a sua população ao mesmo conjunto de regras do resto do continente.
Cada cidadão que entra para o exército suíço recebe um exemplar do Soldatenbusch. Lá estão os rudimentos das táticas e técnicas militares, instruções sobre como se proteger das guerras nuclear, química e bacteriológica, assim como técnicas de ocultamento e construção de abrigos.
Mas o Soldatenbusch não é apenas um manual militar. Trata-se de algo mais profundo que podemos definir como um “Manual do Cidadão”. Lá, ao lado de uma sinopse da história do país, o soldado encontrará capítulos mostrando a importância da democracia, a importância da participação do soldado nos plebiscitos comunais, e a importância de sua arma na defesa desses valores.
Folheando o Soldatenbusch percebe-se que os princípios democráticos estão firmemente arraigados na população.
Serviço militar obrigatório, toda a população sujeita a um livro que é o “manual” que ensina quais devem ser os seus valores (como o Livro Vermelho de Mao Tse Tung?), resultando em uma sociedade militarista, conservadora, e com histórico reportado de racismo (e não apenas em relação àquelas com pele mais escura) e intolerância? Não, obrigado.
A discussão sobre a legislação em relação às armas na nossa sociedade é extremamente válida, mas por favor não venham usar textos como esse ou argumentos como “na Suíça todo mundo tem arma e lá é bom!”. Todos os aspectos de uma sociedade influenciam uns aos outros e produzem os resultados que aparecem nas estatísticas, tanto os positivos como os negativos. Não vamos simplificar o discurso e nem mascarar a discussão com anedotas históricas, ilusões patrióticas, conservadorismo velado e frases bonitas.
🔗 Audacious with classic Winamp 1.x skin
Inspired by my friend Tiago, I installed the classic Winamp skin in my MP3 player of choice, Audacious. I had forgotten how useable it is — better contrast and easier targets to click than all of the other skins shipped by default with Audacious.
A port of the Winamp skin is available at Gnome-Look.
For your copy’n'pasting pleasure, here’s how to dowload, unpack and install it from the command line:
wget http://gnome-look.org/CONTENT/content-files/64790-Winamp.tar.gz tar zxvpf 64790-Winamp.tar.gz mkdir -p ~/.local/share/audacious/Skins mv Winamp ~/.local/share/audacious/Skins
For Audacious 2.x: In Audacious, choose View → Interface → Winamp Classic Interface. Open Preferences (Ctrl+P) and go to the Skinned Interface pane.
For Audacious 3.x: In Audacious, choose File → Settings… → “Appearance” tab. In “Interface Settings” choose “Winamp Classic Interface”.
There should be a “Winamp” entry in the list of skins now. Pick it and enjoy this true classic.
🔗 Top 10 Manic Street Preachers videos
The best Manic Street Preachers videos, as chosen by the Manics themselves:
10. Motorcycle Emptiness
9. A Design for Life
8. Faster
7. (It’s Not War) Just the End of Love
6. If You Tolerate This Your Children Will Be Next
5. Found That Soul
4. Kevin Carter
3. You Love Us (both versions!)
The Heavenly Records version from the indie days:
The major label version from Sony Records:
2. Empty Souls
1. Love’s Sweet Exile
Since they added “forgot everything must go as well”, here it is:
Also, in true Manics fashion, they also listed their top 5 worst videos. Here’s their list:
- So Why So Sad
- She is Suffering
- The Everlasting
- From Despair To Where
- There by the Grace of God
🔗 Understanding, at last, the Y Combinator - a programmer-friendly perspective
This post is aimed towards comp sci students who studied lambda calculus but never really “got” the Y Combinator, the best-known fixed point combinator. Lambda calculus does not feature recursion, but using fixed point combinators, we can easily produce recursive functions, making it able to describe all computable functions (in other words, equivalent to a universal Turing machine). Here’s our friend Y:
Y = λf· (λx· f (x x)) (λx· f (x x))
With it, you can write a non-recursive version of a function, apply Y to it, and you get the equivalent recursive functionality, even though lambda calculus does not provide recursive functions. It’s not hard to understand what it does, but the mystery for me was always how it does it.
In my experience, a major barrier to understanding it was having to deal with several unfamiliar things at the same time, each of which makes a different part of my brain uncomfortable: the semantics of lambda calculus, the syntax of lambda calculus, and the problem at hand.
So, to focus on the problem at hand, let’s get rid of the rest.
Semantics of lambda calculus: untyped lambda calculus amounts (roughly speaking) to a very simple functional language with lazy evaluation. All we have is functions, but through smart encodings we can represent numbers and booleans with nicely crafted chains of functions. To simplify things, then, let’s just assume we already have numbers, arithmetic, if/then/else. Next, let’s get rid of lazy evaluation and switch to early evaluation, which is what we’re used to use in typical imperative programming languages. To do this, we’ll have to use this variant of Y, which is called Z:
Z = λf· (λx· f (λy· x x y)) (λx· f (λy· x x y))
Yes, it is a bit longer (we added the blue bits), but believe me, it’s easier to understand, and once you get this, it’s just a matter of recalling lazy evaluation from those functional programming classes and applying the same logic to Y.
Next, the syntax: lambda calculus is made of terms, abstractions and applications, which in programming language parlance are just variables, function declarations and function calls. Therefore, we can simply rewrite it using some familiar notation and get rid of the weird syntax and precedence rules for now. I won’t even use a functional language: let’s take a restricted form of Lua, using only features provided by lambda calculus to make the syntax clearer:
Z = function(f) return (function(x) return f(function (y) return (x(x))(y) end) end)(function(x) return f(function (y) return (x(x))(y) end) end) end
All right, it’s not exactly readable. But we’ll get there. Assuming you’re comfortable with functions as first-class values that can be returned and passed as arguments, the weirdest thing here is that in the first return we have a function being declared and called “inline”, receiving as a parameter another function identical to itself. Let’s make this flow a bit clearer by using local variables, but strictly as “aliases”. In other words, it won’t run any different, so we don’t use any extra features that are not part of lambda calculus — note that the our use of local variables here will be equivalent to macro substitution:
Z = function(f) local f1 = function(x) return f(function (y) return (x(x))(y) end) end local f2 = function(x) return f(function (y) return (x(x))(y) end) end return f1(f2) end
Ok, so this is the function we want to understand. It still makes no sense, but we can see that Z
calls one function (f1
) passing to it an identical function (f2
). These identical functions return the result of calling f
(the thing we want to make recursive), but giving as its argument another function that uses something that calls itself (x(x)
). A strong scent of self-reference in all this — no wonder, as we know the key to recursion is in there somewhere. But let’s stop trying to reverse-engineer it. Let’s build it instead.
First, let’s recall what this function is good for. What we’d like to have is recursive functions, like this one that calculates the factorial:
fact = function(n) if n == 0 then return 1 else return n * fact(n-1) end end
But we can’t have this in lambda calculus. Actually, all of it is fine, except for the recursive call to fact(). We don’t have recursion yet.
The best we can do is to write a function that does one step of the recursion and leaves the next step to be done by someone else. Like this:
stepper = function(next_step, n) if n == 0 then return 1 else return n * next_step(n-1) end end
However, I said we would only use features provided by lambda calculus, which means we don’t have multiple arguments. Fortunately, through currying, we can get the equivalent to multiple arguments. This is one aspect of lambda calculus which I won’t hide in Lua syntax because it will come handy in our understanding. We’ll need to make stepper
like this:
stepper = function(next_step) return function(n) if n == 0 then return 1 else return n * next_step(n-1) end end end
The difference is that now, instead of doing stepper(some_next_step, 5)
, we have to do stepper(some_next_step)(5)
.
What this stepper
construction makes clear is that we now have a “factory” function that returns our would-be-recursive function, except it only runs one step and uses another function that knows how to run the next step. You can think that stepper(next_step)
actually returns a “step”, which is then run by calling it with (5)
.
But we need a function to run the next step to pass to stepper
. How to obtain it? We call the factory to get the next step. Yes, like stepper(stepper)
.
Indeed, note that if we run stepper(stepper(stepper(stepper(stepper(stepper())))))(5)
, we get the equivalent result as fact(5)
. (You can try it in the Lua interpreter!)
Of course, we don’t want to write it like that. The plan, therefore, is to get a function that combines all these calls. It’s time for the combinator:
combinator = function(stepper) -- ? end
This function is meant to return something to replace all these nested stepper()
s, so we want it to return a function that accepts our input argument:
combinator = function(stepper) return function(arg) -- ? end end
And it needs to run stepper()
on the argument, of course, so it computes our desired function. But what will we pass as the next step?
combinator = function(stepper) return function(arg) return stepper( --[[ ? ]] )(arg) end end
Well, if what we want to produce is stepper(stepper(stepper(stepper(...
then maybe what we need is to pass it stepper()
again?
combinator = function(stepper) return function(arg) return stepper(stepper)(arg) -- no! end end
This is wrong because it will only run stepper
twice (and of course we know the combinator doesn’t look like this). Think of stepper(stepper)
function as it runs. If we pass 5
as the argument we get stepper(stepper)(5)
. It will get 5
as n
and stepper
as the next_step
argument. It will eventually call next_step(n-1)
, that is stepper(4)
. But stepper
expects a function as the argument, and not a number. In fact, if we run this in the Lua interpreter we get a type error. (In untyped lambda calculus we have no notion of “type error”, of course: what we get is just a lambda expression that makes no sense for us.)
We need to give stepper
a function, so looks like we’ll have to make one.
combinator = function(stepper) local some_function = function() -- ? end return function(arg) return stepper(some_function)(arg) end end
(Again, I’m using a local variable here strictly as a “macro substitution”, just to make things more readable.)
To find out what to put in some_function
, let’s think of what it will be used for. It will be passed to stepper
, and therefore be used as the
combinator = function(stepper) local some_function = function(arg) -- ? end return function(arg) return stepper(some_function)(arg) end end
If we’re receiving a parameter, it’s fair to assume we’ll have to do something with it. What we want to do with our input arguments is to run steps on them, so let’s get a step with stepper
and do it.
combinator = function(stepper) local some_function = function(arg) return stepper( --[[ ? ]] )(arg) end return function(arg) return stepper(some_function)(arg) end end
Oh-oh, we’re back to the problem of what to give stepper
! Does this mean we got into a loop? Well, note that if we just kept on doing the same, we would get the equivalent to stepper(stepper(stepper(...)))
:
combinator = function(stepper) local and_yet_another_step = -- ... !!! local yet_another_step = function(arg) return stepper(and_yet_another_step)(arg) end local another_step = function(arg) return stepper(yet_another_step)(arg) end return function(arg) return stepper(another_step)(arg) end end
But no, it does not mean we’re stuck in a loop. It means we’re getting close.
What we missed is that when we considered what to pass to the first stepper
, we simply said it had to be a function taking the numeric argument. But what we want is a function that returns the result of stepper
’s computation, but also produces the function for the next step! What we need is another factory-style function like when we transformed fact
into stepper
. Instead of going down one step, we’ll make a factory function that generates another function that goes down one step. While we’re at it, and that’s a key point, we’ll remove from it the responsibility of figuring out how to descend to the next level. We’ll do it just like when we did when we got rid of the recursion — just assume you get what you need as a parameter:
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step)(arg) end end return function(arg) return stepper(make_step)(arg) end end
With a function like make_step
, we can produce as many steps as we want. If you are mathematically inclined, by now you may be thinking of induction: yes, have we just constructed a way of solving one step of our problem assuming we have the solution for the next. That’s the spirit.
So, are we there yet? Does this work?
Not yet. Remember when we tried to do stepper(stepper)
? It didn’t work because stepper
doesn’t want a factory as an argument. It wants an actual step (remember that in our example it will use it to get the factorial of n-1). In other words, we don’t want to pass it a factory like make_step
. We want make_step
to make us a step. So let’s call it!
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step)(arg) end end return function(arg) return stepper(make_step( --[[ ? ]] ))(arg) end end
Ok, we’ll call it, but what will we give it? Let’s look at what the argument of make_step
is used for.
Wait a second, it is used to make a step as well! So, do we just give it… itself?
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end return function(arg) return stepper(make_step(make_step))(arg) end end
Yes, we pass it to itself. And we do the same with next_step
too, since we’re doing the exact same thing. You see, here is where everything comes together: to have recursion, we need to have self-reference; and in lambda calculus, while a lambda term cannot reference itself in an abstraction (function definition), we have that a lambda term, when bound to a variable, can be applied to itself. The function above is indeed a fixed point combinator.
You may be finding strange that make_step passes itself as a parameter, then calls itself passing itself as a parameter… is this an infinite loop? Not necessarily, because in between each step, we don’t run stepper(next_step(next_step))
right away. It is “packed” inside a function(arg)...end
. (These are the extra lambdas that the Z combinator has compared to the Y combinator.)
Speaking of that, is this code the same as the straight Lua translation of the Z combinator I presented above? Let’s recap:
Z = function(f) return (function(x) return f(function (y) return (x(x))(y) end) end)(function(x) return f(function (y) return (x(x))(y) end) end) end
Doesn’t look much like it, does it? But let’s take a closer look at our combinator. Turns out that in that final return, instead of building that step function explicitly, we can simply call make_step
and get the same results:
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end return make_step(make_step) end
(In compiler terms, it is as if the first iteration had been “unrolled” before.)
Remember when I said the local variables were just macro substitutions? If we expand the two instances of make_step
, we get this:
combinator = function(stepper) return (function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end)(function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end) end
Now, the only difference is that stepper
is being called inside function(arg)...end
, while in the other one it’s being called outside. It works the same, because the purpose of function(arg)...end
there is just to “hold” the expansion of arguments between each call of stepper
. We need this because Lua does not use lazy evaluation. To make our function just like Z, we do this:
combinator = function(stepper) return (function(next_step) return stepper(function(arg) return (next_step(next_step))(arg) end) end)(function(next_step) return stepper(function(arg) return (next_step(next_step))(arg) end) end) end
There we are! The exact same function, only with different variable names.
Finally, to test it:
local factorial_step = function(f) return function (n) if n == 0 then return 1 else return n * f(n - 1) end end end local factorial = combinator(factorial_step) print(factorial(5)) -- we get 120, yet no function in our code ever calls itself
As we can see, there’s nothing magical about the Y combinator: it produces recursion by using the only form of self-reference provided by the lambda calculus, which is self-application of variables. To get the loop started, since there’s no way to bind the outermost abstraction (function) to a term (variable) so it can apply to (call) itself, it is simply written down twice.
I tried to explain this this as clearly I could (given the assumptions I made about prior knowledge about programming languages and basic lambda calculus). This was actually the flow of thought I followed when understanding the combinator. It clearly follows a “programmer” mindset, which may not be the best method for everyone, but I hope it may be useful for others as it was for me. Corrections, comments and suggestions are welcome.
Follow
🐘 Mastodon ▪ RSS (English), RSS (português), RSS (todos / all)
Last 10 entries
- There are two very different things called "package managers"
- Last day at Kong
- A Special Hand
- How to change the nmtui background color
- Receita de Best Pancakes
- That time I almost added Tetris to htop
- Receita de Orange Chicken
- Receita de frango empanado no panko
- Receita de cebola caramelizada
- Receita rápida de crepe